Построение выражения по таблице истинности
💻 Информатика · 8 класс
Восстановление выражения по таблице
Иногда задана готовая таблица истинности, а нужно найти логическое выражение, которое ей соответствует. Это обратная задача к построению таблицы: вместо вычисления значений мы по значениям собираем формулу. Такой навык помогает проектировать логические схемы, которые должны вести себя строго определённым образом, и составляет основу разработки цифровых устройств.
Любая таблица истинности задаёт логическую функцию: какому набору входных значений какой результат соответствует. По этой функции всегда можно построить выражение, причём существует надёжный способ, который работает для любой таблицы. Он называется построением совершенной дизъюнктивной нормальной формы.
Идея метода
Смотрим только на те строки таблицы, где итоговое значение равно единице. Для каждой такой строки записываем конъюнкцию (логическое И) всех переменных: переменную берём как есть, если в строке она равна единице, и с отрицанием, если равна нулю. Получается выражение, которое истинно ровно при этом наборе значений. Затем все полученные конъюнкции объединяем дизъюнкцией (логическим ИЛИ), чтобы итоговое выражение становилось истинным в любой из нужных строк.
Разбор примера
| A | B | F |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Единицы стоят во второй и третьей строках. Запишем для каждой из них свою конъюнкцию, учитывая значения переменных в этих строках.
Строка A=0, B=1: (НЕ A) И B
Строка A=1, B=0: A И (НЕ B)
Объединяем эти конъюнкции через ИЛИ:
F = ((НЕ A) И B) ИЛИ (A И (НЕ B))Это выражение принимает значение «истина» ровно тогда, когда переменные различны: одна равна единице, другая нулю. Такая операция называется исключающим ИЛИ. Чтобы убедиться в правильности, можно подставить наборы значений обратно в выражение и сравнить результаты с исходной таблицей — они должны полностью совпасть.
Если бы единиц в таблице не было вовсе, выражение тождественно равнялось бы нулю. А если бы во всех строках стояли единицы, выражение было бы всегда истинным. В общем же случае количество конъюнкций равно числу единиц в итоговом столбце.
Частая ошибка: берут строки, где результат равен нулю, или путают, когда ставить отрицание. Запоминайте: для этого метода работают только строки с единицей в итоговом столбце, а отрицание ставится у тех переменных, которые в строке равны нулю.
Кратко о главном
- Выражение строят по строкам, где итог равен единице.
- Для каждой такой строки записывают конъюнкцию переменных.
- Переменную берут с отрицанием, если в строке она равна нулю.
- Все конъюнкции объединяют дизъюнкцией; число конъюнкций равно числу единиц.