Дискретная математика (стр. 2 )

Определение дизъюнкции может быть записано в виде следующей таб­лицы истинности:

0	0	0
0	1	1
1	0	1
1	1	1

4 Эквиваленция. Эквиваленцией двух высказываний, а и b, на­зывается высказывание a ~ b (аb или а ≡ b), читаемое «а тогда и только тогда, когда b» (или «а, если и только если b», или «а равносильно b»), которое истинно лишь в том случае, когда оба высказывания имеют одинаковые значения истинности.

Определение эквиваленции может быть записано в виде следующей таблицы истинности:

0	0	1
0	1	0
1	0	0
1	1	1

5  Импликация. Импликацией двух высказываний, а и b, называется высказывание аb (аb), читаемое «если а, то b», которое ложно тогда и только тогда, когда а истинно и b ложно.

Читается также: «а влечет за собой b», «из а следует b», «а достаточное условие b», «b необходимое следствие а», «b при условии, что а» и др.

Это определение может быть записано в виде следующей таблицы истин­ности:

0	0	1
0	1	1
1	0	0
1	1	1

Высказывания, образующие импликацию аb, имеют специальные назва­ния: а – посылка (гипотеза, антецедент), b – заключение (вывод, консек­вент).

Замечание. При определении логических операций алгебры высказыва­ний не имеет значения содержание высказываний, а учитывается лишь их зна­чение истинности. Любая бинарная логическая операция (конъюнкция, дизъ­юнкция, эквиваленция и импликация) над двумя высказываниями образует сложное высказывание, причем если его составляющие не связаны по содержа­нию, то такое сложное высказывание считается бессмысленным.

Пример 1. Построить таблицу истинности для логического высказывания

а b.

Решение

Выполняя по очереди операции отрицания: а, b и дизъюнкцию этих отрицаний, а b, сведем полученные результаты в следующую таблицу истин­ности:

0	0	1	1	1
0	1	1	0	1
1	0	0	1	1
1	1	0	0	0

1.2 Зависимости между операциями.

Основные равносильности для булевых операций

Первые три из введенных операций: отрицание «», дизъюнкцию «» и конъюнкцию «» – принято называть булевыми, а другие две операции: эквиваленция «~» и импликация «» – могут быть выражены через булевы операции согласно следующей теореме.

Теорема. Справедливы следующие равносильности:

аb b;

а ~ b (аb)(ba) (b)( a) (ab)( )

Для булевых операций имеет место следующая теорема.

Теорема. Справедливы следующие 19 основных равносильностей для булевых операций алгебры высказываний:

0 a – закон двойного отрицания

} – коммутативные законы

} – ассоциативные законы

} – дистрибутивные законы

} – законы идемпотентности

} – законы де Моргана

} – законы нуля и единицы

} – законы поглощения

17 а 1 – закон исключенного третьего

18 а 0 – закон противоречия

Под высказывательной формулой (формой), или формулой алгебры высказываний, понимается осмысленное выражение, полученное из символов элементарных высказываний, символов высказывательных переменных, знаков логических операций (конечного числа) и скобок, определяющих порядок действий. Более четко формула определяется следующим образом: