Примеры. Доказать равносильность формул, используя их таблицы истинности:

Пример 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):

Исходная формула не является ни тавтологией, ни противоречием.

Дата добавления: 2014-01-06