§ 2. Таблица истинности логической формулы

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

Логическая переменная — величина, принимающая одно из двух значений: «истина» или «ложь». Переменные обычно обозначают заглавными латинскими буквами A, B, C, а значения записывают цифрами 1 и 0 соответственно. Такая запись позволяет коротко описывать условия и однозначно указывать, истинно ли каждое из них.

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

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

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

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

Число строк с наборами переменных определяется количеством различных переменных в формуле. У каждой переменной два варианта — 0 и 1, поэтому для n переменных получается 2ⁿ комбинаций: варианты перемножаются. Например, для трёх переменных их будет 2 × 2 × 2 = 8; именно столько строк нужно, чтобы рассмотреть все случаи.

Наборы значений записывают систематически, иначе легко случайно пропустить комбинацию или внести её дважды. Для двух переменных удобно перечислить 00, 01, 10, 11: A меняется реже, а B — в каждой следующей строке. Для трёх можно записать 000, 001, 010, 011, 100, 101, 110, 111; здесь C меняется чаще всего, B — через строку, A — через четыре строки.

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

Отрицание меняет значение выражения на противоположное: из 1 получается 0, из 0 — 1. Для бинарной операции, то есть операции с двумя аргументами, результат находят по значениям обоих аргументов. Например, конъюнкция требует, чтобы оба значения были равны 1, а дизъюнкция становится истинной, если хотя бы одно из них равно 1.

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

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

Сначала найди в таблице строку с нужными значениями A и B, затем прочитай результат в столбце выбранной операции. Для отрицания достаточно значения A, а остальные операции используют оба аргумента. Особенно проверь импликацию: она даёт 0 только в строке, где A = 1, а B = 0.

Разбор задач

Построить таблицу истинности для формулы ¬A ∨ B.

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

1. Записываем четыре набора для A и B: 00, 01, 10, 11. Это все сочетания двух переменных, поскольку 2² = 4.

2. Строим столбец ¬A: для строк, где A = 0, ставим 1; где A = 1, ставим 0. Получаем значения 1, 1, 0, 0.

3. Вычисляем ¬A ∨ B по правилу дизъюнкции: результат равен 1, если хотя бы один аргумент равен 1. Итоговый столбец будет 1, 1, 0, 1.

Ответ: формула ложна только при A = 1 и B = 0; в остальных трёх наборах она истинна.

Построить таблицу истинности формулы (A ∧ B) → A.

Скобки показывают, что сначала нужно найти значение A ∧ B, а затем использовать его как левую часть импликации. Промежуточный столбец помогает не перепутать аргументы и увидеть, откуда берётся результат.

1. Записываем наборы A и B в порядке 00, 01, 10, 11. Для каждого набора отдельно проверяем, истинны ли обе переменные одновременно.

2. В столбце A ∧ B получаем 0, 0, 0, 1: конъюнкция истинна только в последней строке. Правая часть импликации — это исходное значение A, то есть 0, 0, 1, 1.

3. Сравниваем значения левой и правой частей в каждой строке. Импликация ложна лишь при сочетании 1 → 0, а такого набора здесь нет.

Ответ: итоговый столбец состоит из единиц, поэтому формула тождественно истинна.

Построить таблицу истинности формулы (A ∨ B) ∧ (¬A ∨ C).

В формуле три переменные, поэтому нужно рассмотреть восемь наборов. Выражение состоит из двух скобок, соединённых конъюнкцией: сначала вычислим каждую скобку, затем проверим, истинны ли они одновременно.

1. Записываем наборы A, B, C: 000, 001, 010, 011, 100, 101, 110, 111. Проверяем, что перечислены все сочетания от 000 до 111 без повторов.

2. Вычисляем ¬A: значения по строкам — 1, 1, 1, 1, 0, 0, 0, 0. Затем находим A ∨ B: получаем 0, 0, 1, 1, 1, 1, 1, 1.

3. Для второй скобки ¬A ∨ C получаем 1, 1, 1, 1, 0, 1, 0, 1. Обе скобки соединены знаком ∧, поэтому в итоговом столбце ставим 1 лишь там, где в обоих промежуточных столбцах стоят единицы.

4. Последовательный просмотр строк даёт итоговые значения 0, 0, 1, 1, 0, 1, 0, 1. В каждой строке результат зависит от двух уже вычисленных скобок, а не от одной переменной отдельно.

Ответ: формула истинна для наборов 010, 011, 101 и 111, а для остальных наборов ложна.

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

Можно пропустить или повторить набор переменных, если записывать их без порядка. Обычно это случается, когда ученик перебирает сочетания наугад и забывает, что каждое значение переменной должно встретиться во всех нужных комбинациях. Проверка проста: число строк должно равняться 2ⁿ, а наборы должны быть различными.

Иногда импликацию считают ложной, если хотя бы одна её часть равна 0. Так путают её с конъюнкцией, где действительно нужны два значения 1. Проверь строку по правилу: A → B равно 0 только при A = 1 и B = 0.

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

Некоторые не повторяют одинаковые значения переменных в соседних строках и считают, что их можно объединить. Но в таблице важен не отдельный столбец, а целый набор: две строки с одинаковым A могут отличаться значениями B или C. Убедись, что каждая строка соответствует отдельному сочетанию и их общее число равно 2ⁿ.

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

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

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

• Для n переменных таблица содержит 2ⁿ наборов.
• Каждая строка таблицы соответствует одному набору значений переменных.
• Значение сложной формулы вычисляют по её подформулам.
• Импликация ложна только в случае «истина → ложь».
• Последний столбец показывает результат для всей формулы.
• Формула тождественно истинна, если в итоговом столбце стоят только единицы.