Пример 2 Построить таблицу истинности для В = ~(p -> q) / q.
Таблица истинности
----T---T----T--------T----------¬
¦ p ¦ q ¦p->q¦~(p->q) ¦~(p->q)/q¦
+---+---+----+--------+----------+
¦ 1 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦
¦ 1 ¦ 0 ¦ 0 ¦ 1 ¦ 0 ¦
¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦
¦ 0 ¦ 0 ¦ 1 ¦ 0 ¦ 0 ¦
+---+---+----+--------+----------+
¦ шаг ¦1 ¦ 2 ¦ 3 ¦
L-------+----+--------+-----------
Если при построении таблицы истинности составного высказывания результат во всех строках оказался однозначным, то такое составное высказывание называют логическим законом.
1. Логические законы для дизъюнкции:
(p / q) = (q / p); (p / p) = p;
(p / 0) = p; (p / 1) = 1.
2. Логические законы для конъюнкции:
(p / q) = (q / p); (p / p) = p;
(p / 0) = 0 ; (p / 1) = p.
3. Закон двойного отрицания:
p = ~(~p)
4. Законы де-Моргана:
~(p / q) = (~p / ~q); ~(p / q) = (~p / ~q).
5. Закон контрапозиции:
(p -> q) = (~q -> ~p).
3.4 Построение заданных составных высказываний
В ряде практических случаев возникает необходимость построения составных высказываний с заданной таблицей истинности. Один из методов построения дает следующая теорема.
Теорема. Всякая логическая функция, кроме const "0" может быть представлена в виде дизъюнкции основных конъюнкций. Такое- представление называется "совершенной дизъюнктивной нормальной формой" представляемой функции (СДHФ ). Const "0" можно представить как p / ~p.
Таблица основных конъюнкций для трех аргументов
----T---T---T---------------T------------¬
¦ p ¦ q ¦ r ¦ осн-ые кон-ции¦ строка ист.¦
+---+---+---+---------------+------------+
¦ 1 ¦ 1 ¦ 1 ¦ p / q / r ¦ 1 ¦
¦ 1 ¦ 1 ¦ 0 ¦ p / q /~r ¦ 2 ¦
¦ 1 ¦ 0 ¦ 1 ¦ p /~q / r ¦ 3 ¦
¦ 1 ¦ 0 ¦ 0 ¦ p /~q /~r ¦ 4 ¦
¦ 0 ¦ 1 ¦ 1 ¦~p / q / r ¦ 5 ¦
¦ 0 ¦ 1 ¦ 0 ¦~p / q /~r ¦ 6 ¦
¦ 0 ¦ 0 ¦ 1 ¦~p /~q / r ¦ 7 ¦
¦ 0 ¦ 0 ¦ 0 ¦~p /~q /~r ¦ 8 ¦
L---+---+---+---------------+-------------
Для того, чтобы получить функцию с заданной таблицей истинности, достаточно выбрать в таблице основные конъюнкции из строк, в которых значения функции равны 1 и связать их знаками дизъюнкции.
Пример. Построить составное высказывание, которое истинно в строках 2 и 6 (т.е. с таблицей истинности 01000100).
А = (p / q /~r)/(~p / q /~r) - выбираем из таблицы основные конъюнкции из строк 2 и 6 и связываем их дизъюнкцией.
Полученное высказывание можно упростить, используя теоретико-множественное преобразование высказывания (будет рассмотрено ниже).