Лекции ДМ

Некоторые логические операции. Двоичное сложение.

Пополним список уже известных логических операций, а именно, познакомимся со штрихом Шеффера, стрелкой Пирса и операцией двоичного сложения. На последней остановимся более подробно.

Штрих Шеффера – это новое высказывание , обозначаемое х|y, ложное тогда и только тогда, когда оба высказывания х и у истинны. Приведем таблицу истинности:

х	у	x\|у
0	0	1
0	1	1
1	0	1
1	1	0

Легко заметить, что штрих Шеффера – это отрицание конъюнкции или дизъюнкция отрицаний х и у: Следовательно, штрих Шеффера можно прочесть следующим образом: не х или не у.

Используя основные равносильности, можно эту операцию выразить и через другие, например:

Отрицание высказывания можно представить в виде :

Стрелка Пирса – это новое высказывание, обозначаемое х у, истинное тогда и только тогда, когда оба высказывания ложны. Приведем таблицу истинности:

х	у	ху
0	0	1
0	1	0
1	0	0
1	1	0

Стрелка Пирса – это отрицание дизъюнкции или конъюнкция отрицаний х и у:

Стрелку Пирса можно прочесть так: не х и не у.

Отрицание высказывания выражается через стрелку Пирса:

Пример: составить КНФ и ДНФ для формулы

Используя новые равносильности и основные равносильности , преобразуем формулу:

Полученная формула является одновременно ДНФ и КНФ.

Двоичное сложение – это новое высказывание, обозначаемое х+у, ложное тогда и только тогда. Когда оба высказывания имеют одинаковые логические значения. Приведем таблицу истинности:

х	у	х +у
0	0	0
0	1	1
1	0	1
1	1	0

Двоичное сложение – это отрицание эквиваленции:

Познакомимся с законами для двоичного сложения:

коммутативность: х+у  у+х;
ассоциативность: х+у+z  x+(y+z);
дистрибутивность: x(y+z)  xy +xz;
х+0  х;

Рассмотрим использование данной операции в вопросе представления булевой функции единственным образом, наряду с совершенными формулами.

Содержание