Табличный способ решения логических задач
Табличный способ решения логических задач — это последовательная проверка всех возможных наборов значений логических переменных. Сначала выражение переводят в удобную форму, затем составляют таблицу истинности и выбирают строки, в которых условие выполняется.
Основная идея табличного способа
Любая логическая переменная принимает одно из двух булевых значений: 0 — ложь или 1 — истина. Если переменных несколько, им соответствуют наборы значений. Например, для двух переменных \(A\) и \(B\) возможны наборы \(00\), \(01\), \(10\), \(11\).
Истинностный набор — это конкретная строка значений всех переменных, например \(A=1\), \(B=0\), \(C=1\). Табличный способ перебирает истинностные наборы и проверяет значение всего логического выражения.
Для \(n\) различных переменных нужно проверить \(2^n\) строк. Поэтому сначала полезно определить число переменных и понять, не заданы ли дополнительные условия, которые сразу исключают часть наборов. Правила составления строк разобраны на странице построения таблицы истинности, а число строк подробнее рассматривается на странице о числе строк таблицы истинности.
Если логическое выражение содержит \(n\) независимых переменных, его таблица истинности имеет \(2^n\) строк. Каждая строка должна содержать один и только один возможный набор значений переменных.
Как строить таблицу
В задаче обычно встречаются отрицание, конъюнкция, дизъюнкция и импликация. Их значения вычисляют поэтапно, добавляя отдельный столбец для каждого промежуточного выражения. Это уменьшает количество ошибок и делает решение проверяемым.
- Отрицание \(\neg A\) меняет 1 на 0, а 0 на 1.
- Конъюнкция \(A\land B\) равна 1 только при \(A=1\) и \(B=1\).
- Дизъюнкция \(A\lor B\) равна 0 только при \(A=0\) и \(B=0\).
- Импликация \(A\to B\) ложна только в случае \(A=1\), \(B=0\).
- Исключающее ИЛИ \(A\oplus B\) истинно, когда значения различаются; подробнее — на странице исключающего ИЛИ.
Порядок вычисления определяется приоритетом логических операций и скобками. Если порядок может вызвать сомнение, ставьте промежуточные столбцы в соответствии со скобками в логических выражениях. Полезно сначала выписать переменные, затем простые части выражения и только после этого — итоговый столбец.
| Операция | Когда результат равен 1 | Когда результат равен 0 |
|---|---|---|
| \(\neg A\) | \(A=0\) | \(A=1\) |
| \(A\land B\) | \(A=1\) и \(B=1\) | Во всех остальных случаях |
| \(A\lor B\) | Хотя бы одно значение равно 1 | \(A=0\) и \(B=0\) |
| \(A\to B\) | Во всех случаях, кроме \(A=1\), \(B=0\) | \(A=1\), \(B=0\) |
В каком случае импликация \(P\to Q\) принимает значение 0?
Алгоритм решения задачи
Табличный способ особенно удобен, когда нужно найти значения переменных, при которых выражение истинно, или определить соответствие между именами, местами, числами и высказываниями. Не следует угадывать ответ: таблица должна охватывать все допустимые случаи.
- Выделите все логические переменные и обозначьте их буквами.
- Запишите условие задачи в виде логического выражения.
- Определите количество возможных строк: \(2^n\), если нет дополнительных ограничений.
- Составьте столбцы переменных и промежуточных частей выражения.
- Заполните строки в едином порядке: например, от \(00\ldots0\) до \(11\ldots1\).
- Вычислите итоговое выражение в каждой строке.
- Оставьте строки с нужным результатом и переведите их обратно на язык условия.
Если итоговая формула имеет вид \(X\land Y\), сначала проверяйте строки, где \(X=1\) и \(Y=1\). Если она имеет вид \(X\lor Y\), исключайте только строки, где оба значения равны 0. Такой приём сокращает вычисления, но полный перебор остаётся способом проверки.
Разобранный пример
Три высказывания \(A\), \(B\) и \(C\) связаны условием \(F=(A\to B)\land(B\to C)\). Найдите все истинностные наборы, для которых \(F=1\).
Здесь три переменные, поэтому без дополнительных условий будет \(2^3=8\) строк. Вычислим сначала две импликации, затем их конъюнкцию.
| A | B | C | \(A\to B\) | \(B\to C\) | \(F=(A\to B)\land(B\to C)\) |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 |
Итак, подходящие наборы: \(000\), \(001\), \(011\) и \(111\). Их можно описать словами так: если \(A\) истинно, то истинны также \(B\) и \(C\); если \(B\) истинно, то истинно \(C\).
Показать короткую проверку Решение
Используем равенство импликации: \(F=(\neg A\lor B)\land(\neg B\lor C)\). Первый множитель требует лишь, чтобы случай \(A=1\), \(B=0\) не встречался. Второй запрещает случай \(B=1\), \(C=0\). Поэтому допустимы только цепочки значений \(A\le B\le C\): \(000\), \(001\), \(011\), \(111\).
Ограничения и упрощение перебора
В реальных задачах переменные могут быть связаны дополнительными условиями: ровно одно высказывание истинно, хотя бы два объекта выбраны, значения различны или один объект находится левее другого. Такое условие тоже переводят в логическую формулу и добавляют в итоговую проверку.
Здесь \(G\), \(H\) и \(K\) — основное условие и ограничения. Строка подходит, только если все множители равны 1. При большом числе переменных можно сначала отбрасывать строки, нарушающие самое простое ограничение, а затем вычислять сложное выражение.
Если два выражения принимают одинаковые значения на каждом истинностном наборе, они логически эквивалентны. Поэтому выражение можно преобразовать по законам логики или правилам булевой алгебры, а затем построить более короткую таблицу.
Например, выражение \(A\lor(A\land B)\) эквивалентно \(A\). В таблице достаточно проверить четыре набора для \(A\) и \(B\), но закон поглощения позволяет сразу сократить вычисления.
1. Пропуск строки или повтор одного набора. 2. Неверное значение импликации: она ложна только при \(1\to0\). 3. Вычисление без учёта скобок и приоритета. 4. Путаница между \(¬(A\land B)\) и \((\neg A\land\neg B)\). 5. Выбор строк, где истинна только часть условия. 6. Отсутствие проверки, что переменные действительно различны или независимы.
Перебор с помощью программы
Если переменных много, ту же идею можно реализовать программно: два вложенных цикла перебирают значения, а условие выводит подходящие наборы. Но программа не заменяет понимание таблицы: важно правильно записать логическое выражение и проверить порядок операций.
1from itertools import product 2 3for A, B, C in product([0, 1], repeat=3): 4 F = ((not A) or B) and ((not B) or C) 5 if F: 6 print(A, B, C)
Самопроверка
Проверьте понимание темы
Главное
- Табличный способ перебирает все истинностные наборы и вычисляет значение выражения в каждой строке.
- Для \(n\) переменных обычно требуется \(2^n\) строк.
- Промежуточные части выражения выносят в отдельные столбцы и вычисляют с учётом скобок и приоритета.
- Импликация ложна только в случае \(1\to0\); это самая частая причина ошибок.
- Дополнительные условия объединяют с основным выражением через конъюнкцию, а подходящими считают строки, где итог равен 1.
- После таблицы нужно перевести найденные наборы обратно в формулировку задачи.