Исчисление высказываний: формулы и таблицы истинности

Исчисление высказываний - раздел формальной логики, который изучает, как истинность сложного утверждения зависит от истинности его частей. Вместо содержания простых утверждений в нём используют переменные , и логические связки: «не», «и», «или», «если … то». Это позволяет проверять структуру рассуждения, даже когда тема задачи меняется.
Начните с импликации : выберите значения условия и следствия в калькуляторе. Единица означает истину, ноль - ложь. Особенно внимательно рассмотрите случай, когда условие истинно, а следствие ложно.
Высказывания и формулы
Высказывание в классической логике - повествовательное утверждение, которому при выбранной интерпретации приписывают одно из двух значений: истину или ложь. Например, «число 8 чётное» истинно, а «число 8 нечётное» ложно. Вопрос «который час?» и приказ «закройте окно» сами по себе не получают такого значения и потому не являются высказываниями в этой модели.
Пусть означает «число делится на 4», а - «число чётное». Из них можно построить формулу : «если число делится на 4, то оно чётное». Чтобы оценить её для конкретного числа, достаточно знать значения и . Внутреннее устройство каждого простого утверждения при этом не рассматривается.
Такое упрощение полезно, но имеет границу: в логике высказываний формула не раскрывает, что такое число или делимость. Чтобы выразить утверждение обо всех числах и исследовать внутреннее строение фразы, нужны переменные предметной области и кванторы логики предикатов.
Основные логические связки
Связка задаётся правилом, по которому из значений частей получают значение целой формулы. В классической логике используют следующие операции:
- - отрицание: истинно, когда ложно.
- - конъюнкция: истинна, только когда истинны оба высказывания.
- - дизъюнкция: истинна, когда истинно хотя бы одно, включая случай, когда истинны оба.
- - материальная импликация: ложна лишь при и .
- - эквиваленция: истинна, когда значения и совпадают.
Скобки показывают состав формулы. Например, отрицает совместную истинность двух утверждений, а требует ложности первого и истинности второго. При , первая формула истинна, вторая ложна. Порядок операций имеет значение, поэтому в учебной записи лучше явно ставить скобки.
Таблица истинности импликации
Для двух переменных есть набора значений. В каждой строке последовательно применяем правило связки:
| 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 |

Последние два столбца совпадают на всех наборах, поэтому формулы равносильны: . В выделенной строке обещанное условие выполнено, а результат нет. В строках с ложным условием материальная импликация считается истинной независимо от значения . Так определена именно формальная связка; из этого не следует, что между событиями обязательно есть причинная связь.
Например, для числа 6 условие «делится на 4» ложно, а утверждение «чётное» истинно. Формула при такой оценке истинна. Однако формальная таблица сама по себе не проверяет, действительно ли все числа, делящиеся на 4, чётные: для этого нужна ещё информация о числах. Ограничения сопоставления материальной импликации с обычным «если … то» обсуждаются в Stanford Encyclopedia of Philosophy.
Как построить таблицу для сложной формулы
Рассмотрим . Сначала перечислим все четыре набора и , затем отдельно вычислим импликацию и только после этого - конъюнкцию:
| 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 0 |
Последний столбец совпадает со столбцом : исходная формула равносильна конъюнкции. Это можно заметить и по смыслу: она одновременно требует и запрещает сочетание истинного с ложным . При трёх независимых переменных понадобится уже строк, а в общем случае для переменных - . Каждая строка должна отличаться хотя бы одним значением от остальных.
Удобный порядок работы: выпишите переменные, составьте полный перечень наборов, выделите внутренние подформулы и вычисляйте столбцы изнутри наружу. Повторяющейся переменной в одной строке всегда присваивают одно и то же значение. Таблица проверяет формальную структуру; её вывод зависит от того, правильно ли исходные фразы переведены в символы.
Тавтология, противоречие и выполнимость
Формула называется тавтологией, или общезначимой, если истинна при каждой оценке. Пример - : независимо от значения один из двух членов дизъюнкции истинен. Формула , напротив, ложна в каждой строке и называется противоречием.
Формула выполнима, если найдётся хотя бы одна оценка, при которой она истинна. Например, выполнима при , хотя не является тавтологией. Для опровержения общезначимости достаточно одного набора с нулём; для подтверждения выполнимости достаточно одного набора с единицей. Полная таблица нужна, когда подходящий пример или контрпример не найден заранее.
На больших формулах перебор быстро растёт. Альтернативой может быть метод аналитических таблиц: он раскрывает формулы по правилам и ищет совместимую ветвь. Его цель та же - выяснить, существует ли оценка с нужными свойствами, - но порядок поиска другой.
Равносильности и преобразование формул
Две формулы равносильны, когда при каждой общей оценке они принимают одинаковое значение. Это сильнее совпадения в одной строке: для проверки нужно сопоставить все строки таблицы. Если формулы равносильны, одну можно заменить другой как часть более сложной формулы, сохранив её значение при любой оценке. Например, замена импликации на дизъюнкцию с отрицанием помогает свести выражение к меньшему набору операций.
Ещё один полезный пример - законы де Моргана: отрицание конъюнкции равносильно дизъюнкции отрицаний . Аналогично, равносильно . Они помогают правильно разбирать условие «неверно, что выполнены оба требования»: для его истинности достаточно нарушения хотя бы одного требования, а не обязательно обоих.
Проверить первый закон можно на крайних случаях. При двух единицах конъюнкция истинна, поэтому обе части равносильности ложны. Если хотя бы одна переменная равна нулю, конъюнкция ложна, её отрицание истинно, и хотя бы одно отрицание справа тоже истинно. Такой разбор охватывает все четыре сочетания и объясняет, почему замена работает.
Логическое следование и правила вывода
Формула логически следует из посылок, если не существует оценки, на которой все посылки истинны, а ложно. Это отношение между посылками и заключением; его нельзя путать со значением одной импликации в отдельной строке.
Проверим посылки и . В таблице выше только первая строка делает обе посылки истинными, и в ней . Значит, следует из этих посылок. Правило вывода называется модус поненс: из и выводят . Соответствующая формула является тавтологией.
Обратное рассуждение не работает: из и нельзя заключать . Контрпример - , : обе посылки истинны, заключение ложно. Чтобы проверить такой вывод, достаточно найти одну подобную строку. Другое корректное правило, модус толленс, использует отрицание следствия: из и выводят .
Где применяется исчисление высказываний
В программе условия ветвления складываются из логических операций. Например, правило доступа «пользователь вошёл в систему и имеет разрешение» можно выразить как . Таблица выявит наборы, на которых правило разрешает действие. Но программа также может работать с ошибками, отсутствующими данными и состояниями, которые не описаны этой двухзначной моделью: их нужно определить отдельно.
Такие же таблицы помогают проектировать цифровые схемы и сравнивать формулы. Некоторые связки позволяют выразить все остальные: об этом подробнее в статье про штрих Шеффера и стрелку Пирса. В доказательствах же различают семантическую проверку по оценкам и синтаксический вывод по правилам: оба способа отвечают на связанные вопросы, но выполняются разными шагами.
Частые ошибки
- Считать «или» исключительно разделительным. В обычной дизъюнкции случай тоже даёт истину.
- Объявлять импликацию ложной при ложном условии. По таблице ложна только строка , .
- Выводить причину из истинности импликации. Материальная связка сама не описывает причинность.
- Проверять вывод на произвольной одной строке. Ищите строку с истинными посылками и ложным заключением; если её нет среди всех оценок, вывод корректен.
- Менять значение одной переменной внутри строки. Все вхождения при одной оценке обозначают одно значение.
FAQ
Чем исчисление высказываний отличается от логики предикатов?
Первое обращается с простыми высказываниями как с целыми. Вторая дополнительно раскрывает свойства и отношения объектов, использует предметные переменные и кванторы.
Является ли всякая истинная формула тавтологией?
Нет. Формула истинна при оценке , но ложна при . Тавтология истинна при любой оценке её переменных.
Достаточно ли таблицы истинности для проверки вывода?
Для конечного набора формул классической логики высказываний - да: перечислите все оценки и проверьте строки, где все посылки истинны. Это проверка формальной корректности, а не фактической истинности посылок.
Коротко
Исчисление высказываний строит формулы из простых утверждений и связок, а таблица истинности показывает их значения на всех оценках. Она позволяет проверять равносильность, выполнимость и логическое следование. Для импликации решающая строка - истинное условие и ложное следствие: только тогда формула равна нулю.
Читайте также

Закон контрапозиции: формула и примеры
Закон контрапозиции в логике: как преобразовать импликацию, проверить равносильность по таблице истинности и применить её в доказательствах и программировании.

Импликация и эквивалентность: таблица истинности
Импликация и эквивалентность в логике: полная таблица истинности, разбор четырёх строк, обратное утверждение и необходимые и достаточные условия на примерах.

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

Модус толленс: правило вывода от противного с примерами
Модус толленс простыми словами: схема правила вывода через отрицание консеквента, символьная запись, отличие от модус поненс, ошибка отрицания антецедента и разбор примеров для студентов.

Дешифратор и шифратор: таблицы и примеры
Дешифратор и шифратор в цифровых схемах: таблицы истинности 2 на 4 и 4 на 2, логические формулы, примеры выбора линии, приоритет входов и активные уровни сигналов.

Логические элементы И, ИЛИ, НЕ: таблица истинности
Как работают логические элементы И, ИЛИ и НЕ: таблицы истинности, обозначения, примеры расчёта схем и типичные ошибки при работе с двоичными сигналами.