§ 19. Таблицы истинности

Определения и обозначения

Логическая переменная — величина, принимающая одно из двух значений: истина или ложь. Обычно их обозначают латинскими буквами p, q, r, а значения записывают как И и Л либо как 1 и 0. Эти обозначения позволяют кратко записывать высказывания и проверять разные варианты их истинности.

Логическое выражение — выражение из логических переменных, операций и скобок. В результате вычисления оно получает одно значение: истина или ложь. Выражение помогает описать составное условие, например «идёт дождь и дует ветер», а затем выяснить, выполняется ли оно.

Логическая операция — правило, по которому из одного или нескольких исходных логических значений получают новое. Отрицание ¬ меняет значение на противоположное, конъюнкция ∧ соответствует «и», а дизъюнкция ∨ — «или». Знание этих правил необходимо, чтобы правильно вычислять составные условия.

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

Как это устроено

У каждой логической переменной есть два возможных значения, поэтому при добавлении новой переменной число сочетаний удваивается. Для одной переменной их два, для двух — четыре, для трёх — восемь; в общем случае получается 2ⁿ наборов. Это число важно: если пропустить хотя бы один вариант, таблица не покажет поведение выражения во всех ситуациях.

Наборы удобно перечислять в постоянном порядке, чтобы не пропускать и не дублировать их. Для двух переменных получаем ИИ, ИЛ, ЛИ, ЛЛ: сначала меняется значение q, а затем p. Для трёх переменных можно записать сначала все сочетания для двух последних, а потом повторить их при другом значении первой. Систематический порядок делает полный перебор проверяемым.

Сложное выражение вычисляют по частям: сначала выполняют действия в скобках, затем учитывают приоритет операций. Например, в выражении ¬p ∨ q сначала находят ¬p, а после этого выполняют дизъюнкцию с q. Если разбить выражение на отдельные действия, легче увидеть, откуда взялся итог и на каком шаге могла возникнуть ошибка.

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

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

Значения основных логических операций

Каждая строка задаёт значения p и q, а столбцы справа показывают результат соответствующей операции. Например, конъюнкция истинна лишь в первой строке, где оба значения — И. Импликация ложна только во второй строке, когда из истинного p следует ложное q.

Разбор задач

Задача 1. Найти значение ¬p ∨ q, если p = истина, q = ложь

Здесь нужно сначала определить результат отрицания p, а затем объединить его с q с помощью дизъюнкции. Такой порядок следует из строения выражения: отрицание относится только к p.

1. Запишем значения переменных: p = И, q = Л.
2. Вычислим ¬p: отрицание истины равно лжи, поэтому ¬p = Л.
3. Вычислим Л ∨ Л. Дизъюнкция истинна, если истинно хотя бы одно значение, но здесь оба ложны.

Ответ: ¬p ∨ q = Л.

Задача 2. Построить таблицу истинности выражения (p ∨ q) ∧ ¬p

В выражении есть скобки, отрицание и конъюнкция, поэтому удобно отдельно вычислять части. Для двух переменных существует четыре набора; в таблице сначала найдём p ∨ q и ¬p, затем их конъюнкцию.

1. Перечислим наборы p и q: ИИ, ИЛ, ЛИ, ЛЛ.
2. Вычислим p ∨ q: получим И, И, И, Л, поскольку дизъюнкция ложна только при двух ложных значениях.
3. Вычислим ¬p: получим Л, Л, И, И.
4. Для каждой строки найдём конъюнкцию промежуточных результатов: Л, Л, И, Л.

Ответ: итоговый столбец выражения содержит значения Л, Л, И, Л. Значит, выражение истинно только при p = Л и q = И.

Задача 3. Проверить равносильность ¬(p ∧ q) и ¬p ∨ ¬q

Чтобы сравнение было полным, проверим оба выражения на всех четырёх наборах p и q. Для первого выражения сначала найдём p ∧ q, затем его отрицание; для второго отдельно вычислим ¬p и ¬q, а после этого их дизъюнкцию.

1. Запишем наборы: ИИ, ИЛ, ЛИ, ЛЛ.
2. Для ¬(p ∧ q) получим: сначала p ∧ q = И, Л, Л, Л, затем отрицание даёт Л, И, И, И.
3. Для ¬p ∨ ¬q получим: значения ¬p равны Л, Л, И, И, а ¬q — Л, И, Л, И.
4. Вычислим дизъюнкцию этих столбцов: Л, И, И, И.
5. Сравним итоговые значения в каждой строке: они совпадают во всех четырёх случаях.

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

Типичные ошибки

Пропускать наборы или повторять их — значит построить неполную таблицу либо добавить лишнюю строку. Так часто происходит, когда варианты перечисляют без системы. Проверьте количество строк по формуле 2ⁿ и убедитесь, что каждый набор встречается ровно один раз.

Конъюнкцию иногда считают истинной, если истинно хотя бы одно высказывание. Это правило относится к дизъюнкции, а конъюнкция требует истинности обоих значений. Для самопроверки найдите в таблице строку И, Л: результат p ∧ q должен быть Л.

Если не соблюдать скобки и приоритет операций, промежуточные значения будут вычислены не в том порядке. Причина ошибки — попытка сразу получить ответ для всего длинного выражения. Разбейте его на части и сверяйте каждый шаг с записью выражения, особенно если в нём есть скобки.

Нельзя объявлять выражения равносильными по совпадению результатов лишь в нескольких строках. Не проверенный набор может оказаться тем самым случаем, где ответы различаются. Составьте полный список из 2ⁿ строк и сравните значения в каждой из них.

Связь с другими темами

Для работы с таблицами нужно различать значения «истина» и «ложь», знать логические операции и уметь вычислять логические выражения. Эти навыки помогают понимать, что именно означает каждый столбец и как получить его значения. Без правил операций таблица превращается в набор символов, а не в обоснованный расчёт.

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

Что запомнить

• Логическое выражение принимает значение истины или лжи.
• Для n переменных таблица содержит 2ⁿ наборов.
• Каждый набор значений переменных занимает отдельную строку.
• Сложное выражение вычисляют с учётом скобок и приоритета операций.
• Промежуточные столбцы помогают не терять шаги вычисления.
• Равносильные выражения совпадают по значениям на всех наборах.