Page 35 - 4496

Формула або функція рівносильна своїй двоїстій
функції, називається самодвоїстою.

2.16 Розвинення булевих функцій за змінними

Введемо позначення:
x   x   x , де  приймає значення 0 або 1.

Тоді
 приx   0
x   
 x при   1
Якщо  = х , то x x  xx  xx  x  x  1.
Твердження. Кожна функція алгебри логіки
f (x 1 , x 2 ,..., x n ) може бути подана у такій формі:
f (x 1 , x 2 ,..., x m ; x m 1 ,..., x n ) 

 V  1 , , m x 1 1  x 2 2   x m  m ( f  1 , 2 ,..., m ; x m 1 ,..., x n ) ,
1 m  n
де V – символ узагальненої диз'юнкції.
Диз'юнкція береться за всіма можливими наборами
значень змінних x , x ,..., x m .Це подання називається
1
2
розвиненим функції за m змінними x , x ,..., x m
1
2
Теорема
Кожна функція алгебри логіки може бути виражена у
вигляді формули через заперечення , кон'юнкцію, диз'юнкцію.
Доведення:
Оскільки будь-яка функція алгебри логіки може
приймати тільки два значення 0 або 1 , то розглянемо два
випадки
1) f (x 1 , x 2 ,..., x n )  . 0
Тоді f ( x , x ,..., x )  x i x . i , деi 1 n , .
2
n
1
2) f (x 1 , x 2 ,..., x n )  . 1 , тоді на основі попереднього
твердження f ( x , x ,..., x )  V f ( 1 , 2 ,..., n )  1
n
1
2
Тобто функція виражається у вигляді формули через
заперечення, кон'юнкцію, диз'юнкцію.
32