Как проверить тавтологию: пошаговое решение

Дано: формула $F = \bigl((A \to B) \wedge (B \to C)\bigr) \to (A \to C)$ от трёх переменных. Найти: является ли она тавтологией, и подтвердить вывод тремя независимыми способами.

Тавтология - формула, истинная на любом наборе значений переменных, поэтому вся проверка сводится к одному вопросу: найдётся ли хотя бы один набор, на котором формула ложна. Быстрее всего отвечает метод от противного: предполагаем $F = 0$ и разматываем импликации, пока не упрёмся в противоречие. Ответ: формула является тавтологией, опровергающего набора не существует, все восемь строк таблицы дают единицу, а в КНФ каждый из четырёх дизъюнктов содержит переменную вместе с её отрицанием. Калькулятор сверху переключает три способа проверки на этой же формуле и считает вердикт ещё для трёх.

Решение по шагам

Дано. $F = \bigl((A \to B) \wedge (B \to C)\bigr) \to (A \to C)$, переменные $A$, $B$, $C$.

Найти. Тавтология ли $F$, то есть истинна ли она на всех наборах значений.

Шаг 1. Переформулируем задачу. Проверять «истинна везде» в лоб дорого: наборов уже $2^3 = 8$, а для десяти переменных их больше тысячи. Отрицание проверяется дешевле: формула не является тавтологией тогда и только тогда, когда существует хотя бы один опровергающий набор, на котором $F = 0$. Значит, будем искать такой набор, и если поиск упрётся в противоречие, вопрос закрыт.

Шаг 2. Предполагаем, что формула ложна. Внешняя операция здесь импликация, а она ложна ровно в одном случае: посылка истинна, следствие ложно.

$$X \to Y = 0 \iff X = 1 \text{ и } Y = 0 .$$

Из предположения $F = 0$ сразу получаются два равенства:

$$(A \to B) \wedge (B \to C) = 1, \qquad A \to C = 0 .$$

Шаг 3. Раскручиваем следствие. Импликация $A \to C$ ложна только при $A = 1$ и $C = 0$. Выбора здесь нет: обе переменные определились однозначно, ветвиться не на что.

Шаг 4. Раскручиваем посылку. Конъюнкция истинна, только если истинны оба множителя, поэтому $A \to B = 1$ и $B \to C = 1$. Подставляем известное $A = 1$: из $1 \to B = 1$ следует $B = 1$. Подставляем найденное $B = 1$ во вторую импликацию: из $1 \to C = 1$ следует $C = 1$.

Шаг 5. Ловим противоречие. На шаге 3 получилось $C = 0$, на шаге 4 - $C = 1$. Одна переменная не может принимать оба значения сразу, значит предположение $F = 0$ несовместно: набора, опровергающего формулу, не существует ни одного.

Ответ. Формула $\bigl((A \to B) \wedge (B \to C)\bigr) \to (A \to C)$ является тавтологией. Это закон транзитивности импликации, он же цепное правило: если из $A$ следует $B$, а из $B$ следует $C$, то из $A$ следует $C$.

Проверка таблицей истинности

Метод от противного укладывается в пять строк рассуждения, но на контрольной обычно просят ещё и таблицу. Переменных три, поэтому строк ровно $2^3 = 8$, а промежуточные столбцы заводятся по одному на каждую операцию в порядке приоритета. Сам порядок заполнения разобран в задаче как построить таблицу истинности, нас здесь интересует только итоговый столбец.

Ноль в столбце $F$ мог появиться только там, где следствие $A \to C$ равно нулю, то есть в строках 4 и 6, где $A = 1$ и $C = 0$. Но ровно в этих строках обнуляется и посылка: при таких $A$ и $C$ любое значение $B$ ломает одну из двух импликаций. Если $B = 0$, ложной становится $A \to B$, если $B = 1$ - ложной становится $B \to C$. А импликация с ложной посылкой истинна, поэтому в обеих строках $F = 1$.

Ответ по таблице. Столбец $F$ - восемь единиц подряд, ни одного нуля. Формула тождественно истинна, вывод совпал с методом от противного. Перебор дал тот же результат, но написать пришлось в несколько раз больше: это нормальная плата за то, что таблица не требует догадок.

Приведение к КНФ: третий способ

Третий способ не перебирает наборы вообще, а работает с записью формулы. Формулу приводят к конъюнктивной нормальной форме - конъюнкции дизъюнктов, где под знаком отрицания стоят только переменные. Делается это в три хода: импликации заменяют по правилу $X \to Y = \neg X \vee Y$, отрицания опускают к переменным по законам де Моргана, а затем раскрывают скобки распределительным законом. Те же преобразования используются в задаче как упростить логическое выражение, только цель там другая: там запись укорачивают, а здесь загоняют в стандартный вид.

Убираем внешнюю импликацию и вносим отрицание внутрь:

$$F = \neg\bigl((A \to B) \wedge (B \to C)\bigr) \vee (\neg A \vee C) = (A \wedge \neg B) \vee (B \wedge \neg C) \vee \neg A \vee C .$$

Теперь раскрываем скобки: дизъюнкция двух конъюнкций даёт четыре дизъюнкта, и к каждому дописываются свободные литералы $\neg A$ и $C$:

$$F = (A \vee B \vee \neg A \vee C) \wedge (A \vee \neg C \vee \neg A \vee C) \wedge (\neg B \vee B \vee \neg A \vee C) \wedge (\neg B \vee \neg C \vee \neg A \vee C) .$$

Признак тавтологии в КНФ простой: формула тождественно истинна тогда и только тогда, когда каждый дизъюнкт содержит какую-нибудь переменную вместе с её отрицанием. Работает он потому, что дизъюнкт ложен, только когда ложны все его литералы разом, а пара $X$ и $\neg X$ этого не допускает при любом значении $X$. Если же в дизъюнкте контрарной пары нет, каждому литералу можно назначить ноль независимо от остальных, и опровергающий набор строится руками.

Проверяем наши четыре дизъюнкта: в первом и втором есть $A$ и $\neg A$, в третьем - $B$ и $\neg B$, в четвёртом - $C$ и $\neg C$. Все четыре тождественно истинны, конъюнкция единиц тоже единица. Третий способ подтвердил ответ: формула является тавтологией. О второй канонической форме, СДНФ, и о том, зачем она нужна, написано в разборе совершенной дизъюнктивной нормальной формы.

Тавтология, выполнимость и противоречие

Проверка на тавтологию всегда заканчивается одним из трёх вердиктов, и они отличаются только тем, что стоит в столбце $F$.

Между крайними строками таблицы есть двойственность: формула $F$ является тавтологией тогда и только тогда, когда $\neg F$ тождественно ложна. Поэтому в прикладной логике задачу обычно переворачивают: берут отрицание формулы, приводят его к КНФ и отдают SAT-решателю с вопросом «есть ли выполняющий набор». Ответ «нет» означает, что исходная формула тавтология. Метод от противного из шагов 2-5 - ручная версия ровно этой процедуры.

Какой способ выбирать

Таблица истинности выигрывает, когда переменных три или четыре, а проверяющий хочет видеть перебор целиком. Её минус - рост $2^n$: пять переменных дают 32 строки, десять уже 1024, и вручную такую таблицу не заполнить.

Метод от противного хорош, когда внешняя операция - импликация или дизъюнкция: у них ложное значение достигается единственным способом, поэтому значения переменных определяются однозначно и рассуждение идёт по прямой. Если же внешняя операция конъюнкция, её ноль можно получить несколькими способами, и приходится разбирать случаи ветвлением.

Приведение к КНФ удобно, когда формула и так близка к нужному виду или когда её всё равно требуется упростить. Плюс способа в том, что он не зависит от числа переменных: критерий проверяется по записи, а не перебором наборов.

Частые ошибки

• Проверили формулу на двух-трёх наборах, получили единицы и записали в тавтологии. Единица на отдельном наборе доказывает только выполнимость; тавтология требует всех $2^n$ строк.
• В методе от противного предполагают $F = 1$ и ждут противоречия. Предполагать надо ложность: доказательство идёт от опровергающего набора.
• Забывают, что импликация с ложной посылкой истинна, и ставят ноль в строках 4 и 6. Именно эта ошибка чаще всего превращает тавтологию в «не тавтологию».
• Читают формулу без учёта приоритета: конъюнкция сильнее импликации, поэтому $(A \to B) \wedge (B \to C) \to (A \to C)$ - это импликация с посылкой-конъюнкцией, а не конъюнкция двух импликаций.
• Из условия «дизъюнкция равна единице» делают однозначный вывод о значениях слагаемых. Единица дизъюнкции допускает три варианта, и здесь нужен разбор случаев, иначе противоречие окажется выдуманным.
• В КНФ ищут контрарную пару во всей формуле, а не в каждом дизъюнкте отдельно. Достаточно одного дизъюнкта без пары, чтобы формула перестала быть тавтологией.

FAQ

Чем тавтология отличается от равносильности формул? Равносильность - это отношение между двумя формулами, тавтология - свойство одной. Связаны они так: формулы $X$ и $Y$ равносильны тогда и только тогда, когда $X \leftrightarrow Y$ является тавтологией. Поэтому любая проверка равносильности сводится к проверке эквивалентности на тождественную истинность.

Можно ли доказать тавтологию, подставив несколько удачных наборов? Опровергнуть можно: достаточно одного набора с $F = 0$, и вопрос закрыт. Доказать подстановкой нельзя - нужен либо полный перебор, либо рассуждение, покрывающее все наборы сразу, как метод от противного или критерий по КНФ.

Что делать, если переменных много? При $n > 5$ таблица перестаёт быть инструментом: для двадцати переменных это больше миллиона строк. Работают метод от противного, метод резолюций и приведение к КНФ с проверкой на выполнимость; на этом же принципе построены промышленные SAT-решатели.

Бывают ли тавтологии без импликаций? Да, и самые известные записываются короче нашей: $A \vee \neg A$ - закон исключённого третьего, $\neg(A \wedge \neg A)$ - закон противоречия. Обе проверяются таблицей из двух строк и обе состоят из одного дизъюнкта с контрарной парой.

Коротко

1. Тавтология - формула, истинная на всех $2^n$ наборах; проверять удобнее обратное утверждение, то есть искать набор с $F = 0$.
2. Метод от противного: предположить $F = 0$, раскрутить операции до значений переменных и поймать противоречие. Противоречие есть - тавтология, противоречия нет - найденный набор и будет контрпримером.
3. Таблица истинности: $2^n$ строк, промежуточный столбец на каждую операцию; восемь единиц в столбце $F$ означают тождественную истинность.
4. КНФ: убрать импликации, опустить отрицания, раскрыть скобки и проверить, в каждом ли дизъюнкте есть переменная вместе с её отрицанием.
5. Для $F = \bigl((A \to B) \wedge (B \to C)\bigr) \to (A \to C)$ все три способа дали один ответ: это тавтология, закон транзитивности импликации.