Булева алгебра

1.

2.

Формула, полученная в результате
преобразований и содержащая только
операции конъюнкции, дизъюнкции и
отрицания, называется булевой формулой.
Буль - американский математик; заложил
основы алгебры двоичных чисел.

3.

Среди булевых формул выделяют 4
специальных вида:
Дизъюнктивная нормальная форма (ДНФ);
Совершенная дизъюнктивная нормальная
форма (СДНФ);
Конъюнктивная нормальная форма (КНФ);
Совершенная конъюнктивная нормальная
форма (СКНФ);

4.

Конъюнктивным одночленом от переменных
называется конъюнкция этих переменных
или их отрицаний, обозначается Кi .
Дизъюнктивным одночленом от переменных
называется дизъюнкция этих переменных
или их отрицаний, обозначается Di .

5.

Дизъюнктивной нормальной формой (ДНФ)
называется дизъюнкция конъюнктивных
одночленов т.е. К1˅К2˅К3˅… ˅Кр;
Конъюнктивной нормальной формой (КНФ)
называется конъюнкция дизъюнктивных
одночленов т.е. D1˄D2 ˄D3˄… ˄Dn;

6.

Одночлен (дизъюнктивный или конъюнктивный)
от переменных Х1, Х2, …, Хn называется
совершенным, если в него от каждой пары Хi,
¬Xi входит ровно одна буква.
Нормальная форма (дизъюнктивная или
конъюнктивная) от переменных Х1, Х2, …, Хn
называется совершенной, если в неё входят
только совершенные одночлены
(конъюнктивные или дизъюнктивные
соответственно) от Х1, Х2, …, Хn .Обозначаются
СДНФ или СКНФ.

7.

Алгебра (Σ, , V, ͞ ), основным множеством
которой является все множество логических
функций Σ, а операциями – дизъюнкция,
конъюнкция и отрицание, называется
булевой алгеброй логических функций.
Операции булевой алгебры называются
булевыми операциями.
ᶺ

8.

1.
Ассоциативный (сочетательный)
x 1 x 2 x 3 x 1 x 2 x 3 ; x 1 x 2 x 3 x 1 x 2 x 3 ;
2.
Коммутативный (переместительный)
x1 x 2 x 2 x1 ; x1 x 2 x 2 x1 ;
3.
Дистрибутивный (распределительный)
x x x x x x x ;
1
2
3
1
2
1
3
x x x x x ( x x );
1
2
3
1
2
1
3

9.

4.
Идемпотентности
x x x; x x x
5.
Двойного отрицания
6.
x x
Поглощения
x 0 0; x 1 x;
7.
Противоречия
x 0 0; x 1 1
x x 0;

10.

8.
Исключения третьего
x x 1
9.
Силлогизма (дедуктивного заключения)
10.
Де Моргана
x y y z x z
x1 x 2 x1 x 2 ;
x1 x 2 x1 x 2 ;