Проверка равносильности таблицей истинности
Проверка равносильности таблицей истинности — надёжный способ сравнить два логических выражения. Нужно перечислить все наборы значений переменных, вычислить оба выражения в каждой строке и убедиться, что результаты совпадают везде.
Что значит «выражения равносильны»
Логические выражения называют равносильными, если при любом наборе значений входящих в них переменных они принимают одинаковые значения. Обозначают это так: \(F \equiv G\). Равносильность сильнее, чем совпадение в нескольких проверенных случаях: необходимо совпадение во всех возможных строках таблицы истинности.
Два логических выражения \(F\) и \(G\) равносильны, если для каждого набора значений переменных выполняется \(F = G\).
Чтобы проверить равносильность выражений таблицей истинности, достаточно сравнить их значения в каждой строке. Если хотя бы в одной строке результаты различаются, выражения неравносильны.
Операции, их обозначения и порядок вычисления рассматриваются на странице логические операции. Перед работой полезно повторить построение таблицы истинности, особенно порядок перебора наборов нулей и единиц.
Алгоритм проверки таблицей истинности
Пусть требуется сравнить выражения \(F\) и \(G\). В таблице должны быть отдельные столбцы для всех переменных, промежуточных действий и итоговых значений обоих выражений.
- Выпишите все переменные, которые встречаются хотя бы в одном из выражений.
- Определите число строк: для \(n\) переменных потребуется \(2^n\) наборов значений.
- Заполните столбцы переменных всеми наборами нулей и единиц.
- Разбейте каждое выражение на простые операции и создайте промежуточные столбцы.
- Вычислите значение первого выражения в каждой строке.
- Вычислите значение второго выражения в каждой строке.
- Сравните два итоговых столбца. Полное совпадение означает равносильность.
Если выражения содержат три переменные, таблица имеет \(2^3=8\) строк; для четырёх переменных — \(2^4=16\) строк. Переменная, которая встречается только в одном выражении, всё равно включается в таблицу: иначе нельзя проверить все наборы.
Для сложных выражений сначала выписывайте отдельные столбцы для отрицаний, затем для конъюнкций, дизъюнкций и других операций. Подписывайте столбцы коротко: например, \(\neg A\), \(B\land C\), \((\neg A)\lor(B\land C)\).
Как вычислять выражения без ошибок
В каждой строке вычисляйте выражение в соответствии со скобками и приоритетом операций. Обычно сначала выполняется отрицание \(\neg\), затем конъюнкция \(\land\), затем дизъюнкция \(\lor\). Если в условии используются другие обозначения, например «и», «или», «не», сначала переведите их к единому виду.
Отрицание меняет 0 на 1 и 1 на 0. Конъюнкция равна 1 только тогда, когда оба операнда равны 1. Дизъюнкция равна 0 только тогда, когда оба операнда равны 0. Для составных отрицаний полезно повторить отрицание сложного высказывания.
| A | B | \(A\land B\) | \(A\lor B\) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Сколько строк должна содержать таблица для сравнения двух выражений с переменными \(A\), \(B\) и \(C\)?
Разобранный пример
Проверим таблицей истинности, равносильны ли выражения \(F=\neg(A\land B)\) и \(G=\neg A\lor\neg B\). Это классический закон де Моргана, но в задаче важно уметь подтвердить его непосредственно по строкам.
Сравнить \(F=\neg(A\land B)\) и \(G=\neg A\lor\neg B\) для всех значений переменных \(A\) и \(B\).
Переменных две, поэтому понадобится четыре строки. Добавим промежуточные столбцы \(A\land B\), \(\neg(A\land B)\), \(\neg A\), \(\neg B\) и итоговый столбец \(\neg A\lor\neg B\).
| A | B | \(A\land B\) | \(\neg(A\land B)\) | \(\neg A\) | \(\neg B\) | \(\neg A\lor\neg B\) |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Так как столбцы \(F\) и \(G\) совпали полностью, выражения равносильны: \(\neg(A\land B)\equiv\neg A\lor\neg B\).
Как оформить ответ и найти различие
В экзаменационной записи полезно явно указать переменные, число строк и итог сравнения. Например: «Переменные \(A\), \(B\), поэтому \(2^2=4\) строки. Последние столбцы совпадают: \(1,1,1,0\). Следовательно, выражения равносильны».
Если найдено хотя бы одно несовпадение, достаточно привести номер строки или соответствующий набор значений. Это набор называется контрпримером к равносильности. Остальные строки в таком случае можно не вычислять, если требуется только доказать, что выражения неравносильны.
1. Проверяют только несколько удобных наборов, а не все строки. 2. Забывают переменную, встречающуюся лишь в одном выражении. 3. Путают порядок операций и убирают скобки. 4. Сравнивают промежуточные столбцы вместо итоговых. 5. Считают выражения равносильными из-за совпадения почти всех строк: одной различающейся строки достаточно для отрицательного ответа.
Табличная проверка всегда даёт правильный результат, но для длинных выражений таблица может быть большой. Тогда сначала пытаются преобразовать выражения с помощью законов булевой алгебры, а затем при необходимости проверяют результат таблицей. С этим способом связана страница преобразование логических выражений. Законы идемпотентности, нуля и единицы помогают сокращать промежуточные вычисления: закон идемпотентности и законы нуля и единицы.
Связь с заданиями экзамена
В заданиях на логические выражения таблица истинности может быть нужна для доказательства равносильности, выбора подходящего выражения или проверки условия на всех наборах переменных. Для заданий о равносильных логических выражениях важно различать два требования: доказать совпадение значений во всех строках и найти хотя бы одну строку, где значения различаются.
- Все переменные из обоих выражений выписаны.
- Число строк равно \(2^n\).
- Для сложных частей созданы промежуточные столбцы.
- Итоговые значения сравнены построчно.
- Вывод сформулирован явно: равносильны или неравносильны.
Быстрая проверка
Главное
- Равносильные выражения имеют одинаковые значения при каждом наборе переменных.
- Для \(n\) переменных строят \(2^n\) строк.
- Сначала вычисляют промежуточные операции, затем сравнивают итоговые столбцы.
- Полное совпадение означает равносильность; одно несовпадение является контрпримером.
- В ответе нужно указать переменные, число строк и ясный итог проверки.