Тавтология и противоречие. 
Равносильность высказываний

Формула х₂,лг_я) называется тавтологией или тождественно истиной формулой, если при любых значениях высказываний х_х> х₂, значение F= 1.

Например, рассмотрим формулу Л vД, соответствующую высказыванию «этот треугольник прямоугольный или косоугольный». Эта формула истинна и тогда, когда треугольник прямоугольный, и тогда, когда треугольник не прямоугольный.

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

Формула F (x 1, х₂, …, х_п) называется противоречием или тождественно ложной формулой, если при любых значения высказываний х_1у х₂,…, х_п значение F = 0.

Формула называется выполнимой, если существует такой набор значений переменных, при котором эта формула принимает значение 1. Формула называется опровержимой, если существует такой набор значений переменных, при котором эта формула принимает значение 0.

Пример 4.14. Рассмотрим формулу А & -Л, которой соответствует, например, высказывание «Катя — самая высокая девочка в классе, и в классе есть девочки выше Кати». Очевидно, что эта формула ложна, так как-либо Л, либо^Л обязательно ложно.

Пример 4.15. Выясним, является ли следующая формула тождественно истинной: F — [(Л —> В) & -'В] —> -*Л.

Решение. Построим таблицу (табл. 4.13) истинности заданной формулы, используя определения логических операций.

Таблица 4.13

Таблица истинности для решения примера 4.15.

Так как последний столбец состоит только из 1, то формула тождественно истинна.

Пример 4.16. Выясним, является ли следующая формула выполнимой:

Решение. Построим таблицу истинности (табл. 4.14) заданной формулы, используя определения логических операций.

Таблица истинности для решения примера 4.16.

Таблица 4.14

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

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

• • по каждой формуле строится таблица истинности;
• • полученные таблицы сравниваются по каждому набору значений переменных.

Пример 4.17. Являются ли формулы -> (х & у) = (-ес) v (—•*/) равносильными?

Решение. Построим таблицу истинности для заданных формул (табл. 4.15), используя определения логических операций.

Таблица 4.15

Таблица истинности для решения примера 4.17

Рассматривая столбцы 4 и 7, видим, что заданные формулы полностью совпадают по каждому набору значений переменных, из чего следует, что формулы равносильны.

Пример 4.18. Указать элементарные высказывания, их составляющие, написать формулы данных высказываний и построить таблицу истинности. Указать, какие из высказываний равносильны:

• • 5: «Если ученик 1 неверно сделал задачу или если ученик 2 просчитал задачу правильно, то и ученик 3 сделал это без ошибок»;
• • S₂. «Если ученик 1 правильно просчитал задачу, то либо ученик 2 ошибся, либо ученик 3 сделал ее верно»;
• • S₃: «Либо ученик 1 неверно просчитал задачу, либо ученик 2 решил ее верно в том и только в том случае, если ученик 3 решил ее верно».

Очевидно, данные сложные высказывания составлены из следующих элементарных:

• • А: «Ученик 1 правильно просчитал задачу»;
• • В: «Ученик 2 правильно просчитал задачу»;
• • С: «Ученик 3 правильно просчитал задачу».

Используя основные логические связки, запишем формулы данных высказываний:

Составим таблицу истинности данных высказываний (табл. 4.16).

Таблица 4.16

Таблица истинности для решения примера 4.18.

Из таблицы видно, что высказывания и S₂ равносильны.

Пример 4.19. Пусть х, у, z — следующие элементарные высказывания: х — а — четное число; у — b — четное число; z — произведение ab — четное число.

Написать формулы и построить функции данных формул для следующих высказываний:

• • S{. «Если а — четное число, а b — нечетное, то произведение а и Ь делится на 2»;
• • S₂: «Произведение чисел а и b делится на 2 в том и только в том случае, если аиЬ четные»;
• • 5₃: «Если каждое из чисел а и b нечетно, то их произведение не делится на 2»;
• • 5₄: «Произведение чисел а и b не делится на 2 в том и только в том случае, если а и b нечетные».

Какие из формул 5_1? S₂, 5₃, 5₄ равносильны?

Решение:

• • 5_t = х & «Ч/ —> г;
• • S₂ = z
• • 5₃ = Чг & у) -> -г;
• • S_A =² <-» ^Х & ^у.

Таблица 4.17

Таблица истинности для решения примера 4.19.

Функции формул 5₂, 5₃, S₄ представлены столбцами таблицы истинности этих формул (табл. 4.17), откуда следует, что S₂ и 5^ равносильны.