Логические законы

Пример 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 и связываем их дизъюнкцией.

Полученное высказывание можно упростить, используя теоретико-множественное преобразование высказывания (будет рассмотрено ниже).