Таблицы истинности операций эквивалентности и импликации
Эквивалентность | Импликация | ||||
А | В | А~В | А | В | А®В |
0 | 0 | 1 | 0 | 0 | 1 |
0 | 1 | 0 | 0 | 1 | 1 |
1 | 0 | 0 | 1 | 0 | 0 |
1 | 1 | 1 | 1 | 1 | 1 |
Другим примером может служить логическая операция импликацииили логического следования (А®В, A IMP B), иначе говоря, «ЕСЛИ А, то В» (табл. 2.7). Высказывания, образованные с помощью логических операций из простых, называются сложными. Истинность сложных высказываний можно установить, используя таблицы истинности. Например, истинность сложного высказывания определяется табл. 2.8.
Т а б л и ц а 2.8
Таблица истинности высказывания
А | В | |||
0 | 0 | 1 | 1 | 1 |
0 | 1 | 1 | 0 | 0 |
1 | 0 | 0 | 1 | 0 |
1 | 1 | 0 | 0 | 0 |
Если рассматривать буквы А,В,С…вкачестве переменных, принимающих два значения 1 и 0, то в этом случае логическая формула является булевой функцией.
Для правильного вычисления значения логических формул необходимо задать порядок выполнения логических операций. Сначала выполняется операция отрицания «‾», затем конъюнкция «Ù», дизъюнкция «Ú», затем импликация → и, последней, эквивалентность ↔. Как и в алгебре, скобки необходимы для изменения порядка действий (т. е. первыми выполняются операции, заключенные в скобки), а равноправные операции вычисляются слева направо.
Рассмотрим пример вычисления значений логической формулы.
Необходимо сначала определить и , затем выполнить дизъюнкцию Ú , после этого подсчитать значение выражения, стоящего в скобках А↔ Ú , далее выполнить конъюнкцию высказываний Ù и, наконец, соединить вычисленные значения высказываний левой и правой части исходной формулы с помощью импликации.Порядок выполнения операций будет следующим:
|
|
Высказывания, у которых таблицы истинности совпадают, называются равносильными. Для обозначения равносильных высказываний используют знак «=» (A = B). Рассмотрим сложное высказывание (табл. 2.9).
Т а б л и ц а 2.9
Таблица истинности выражения
А | В | |||||
0 | 1 | 0 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 1 | 0 | 0 | 0 |
1 | 0 | 1 | 0 | 1 | 0 | 1 |
Если сравнить эту таблицу с таблицей истинности операции эквивалентности высказываний А и В (см. табл. 2.7), то можно увидеть, что высказывания и А ~ В тождественны, т. е. (А ~ В) = .
В алгебре высказываний можно проводить тождественные преобразования, заменяя одни высказывания равносильными им другими высказываниями.
Свойства логических операций
Исходя из определений дизъюнкции, конъюнкции и отрицания, устанавливаются свойства этих операций и взаимные распредели-тельные свойства. Приведем примеры некоторых из этих свойств:
|
|
- коммутативность (перестановочность)
, ;
- закон идемпотентности
, ;
- двойное отрицание
;
- сочетательные (ассоциативные) законы
, ;
- распределительные (дистрибутивные) законы
, ;
- поглощение
, ;
- склеивание
, ;
- операция переменной с ее инверсией
; ;
- операции с константами (0 − false, 1 − true)
, , , ;
- законы де Моргана:
(условно его можно назвать 1-й);
(2-й) - описывает результаты отрицания переменных, связанных операциями И, ИЛИ.
Сложные высказывания, истинные (true) для любых значений истинности, входящих в них простых высказываний, называются тождественно-истинными. Наоборот, тождественно-ложными явля-ются формулы, принимающие значение false для любых значений входящих в него простых высказываний.
В табл. 2.10 приведено доказательство истинности дистрибутивного закона: значения высказываний в 5-й и 8-й колонках – одинаковы. Аналогичным образом могут быть доказаны и другие тождества.
Т а б л и ц а 2.10
Дата добавления: 2018-05-12; просмотров: 3911; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!