Похожие презентации:
Булева алгебра
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 ;