Примеры
Пример 1.7
Доказать равносильность формул, используя их таблицы истинности:
а) ;
б) ;
в) .
Решение
а) Сравним таблицы истинности для правой и левой частей:
Итоговые столбцы таблиц истинности (выделены фоном) совпадают, значит, формулы равносильны.
б)
Итоговый столбец совпадает с первым столбцом, значит, эта формула равносильна Х.
в)
Пример 1.8
Исключить возможно большее число скобок:
а) ;
б) .
Ответы
а) ;
б) .
Пример 1.9
Восстановить максимальное число скобок, ориентируясь на формальное определение формулы:
а) ;
б) .
Ответы
а) ;
б) .
Пример 1.10
Оптимизировать формулы:
а) ;
б) .
Решение
а) Удаляя «лишние» скобки, получим:
.
б) Применяя последовательно основные логические законы (III.2.), (II.1.), (I.5.), (IV.8.) и (IV.1.) и удаляя «по пути» скобки, получим:
.
Пример 1.11
Доказать равносильность формул, используя логические законы:
а);
б) .
Решение
а) Преобразуем левую формулу к виду правой формулы, последовательно применив логические законы (I.6.), (I.6.) и (I.2.):
.
б) Применим к левой формуле логические законы (III.1.), (II.2.) и (II.1.):
.
Пример 1.12
Определить, является ли формула тавтологией, противоречием или ни тем, ни другим:
а) ;
б) ;
в) ;
г) .
Решение
а) Приведем формулу к наиболее простому виду, последовательно исключая импликации по логическому закону (III.1.) и убирая двойные отрицания по закону (II.1.):
.
Полученная формула не является логической константой, следовательно, исходная формула не является ни тавтологией, ни противоречием.
б) Применим логические законы (II.2.), (IV.7.) и (IV.2.):
.
Исходная формула – противоречие.
в) Применим (III.1), (I.6), (IV.8) и (IV.1):
Исходная формула не является ни тавтологией, ни противоречием.
г) Применим (III.1), (II.3), (II.2), (II.1), (I.2), (IV.1), (I.5), (IV.3):
Исходная формула не является ни тавтологией, ни противоречием.