Логические функции. Построение логического выражения с данной таблицей истинности
До этого момента мы считали, что логическое выражение уже задано и нам надо что-то с ним сделать (построить таблицу истинности, упростить и т. п.). Такие задачи называются задачами анализа , в них требуется исследовать заданное выражение. При проектировании различных логических устройств, в том числе и узлов компьютеров, приходится решать обратную задачу — строить логическое выражение по готовой таблице истинности, которая описывает нужное правило обработки данных. Эта задача называется задачей синтеза.
В качестве простейшего примера построим логическое выражение, тождественное операции импликации X = А → В, по её таблице истинности (рис. 3.16).
Способ 1.
В таблице истинности мы выделяем все строки, где логическое выражение равно единице. Тогда выражение может быть записано как логическая сумма выражений, каждое из которых истинно только в одном_случае.
Например, выражение ¬А • ¬В истинно только при А = 0 и В = 0, т. е. только в первой строке таблицы. Выражение ¬А•В истинно только во второй строке, а А • В — только в последней. Существует простое правило: если в этой строке переменная равна нулю, она входит в произведение с отрицанием, а если равна 1, то без отрицания.
Складывая выражения для всех отмеченных строк (кроме третьей, где функция равна нулю), получаем:
Такая запись — дизъюнкция простых конъюнкций — называется дизъюнктивной нормальной формой (ДНФ).
Упрощаем это выражение:
Таким образом, мы вывели формулу, которая позволяет представить импликацию через операции НЕ и ИЛИ.
Способ 2.
Если в таблице истинности нулей меньше, чем единиц, удобнее сначала найти формулу для обратного выражения, ¬Х а потом применить операцию НЕ. В данном случае выражение равно нулю в единственной строке, при А = 1 и В = 0, и только в этой строке ¬X = 1, поэтому, используя предыдущий способ, получаем: ¬Х = А • ¬В. Теперь остается применить операцию НЕ и закон де Моргана:
Рассмотрим более сложный пример, когда выражение зависит от трёх переменных. В этом случае в таблице истинности будет 8 строк. Отметим все строки, где X = 1, и для каждой из них построим выражение, истинное только для этой комбинации переменных (рис. 3.17).
Теперь выполним логическое сложение — построим ДНФ:
Упрощение этого выражения даёт
Используя способ 2, получаем
Тогда
В данном случае второй способ оказался проще, потому что в последнем столбце таблицы истинности нулей меньше, чем единиц.
Способ 3.
При небольшом количестве нулей можно использовать ещё один метод. Попробуем применить операцию НЕ к исходному выражению для ¬X из предыдущего примера, без предварительного упрощения:
Применяя закон де Моргана, получим:
Используя закон де Моргана ещё два раза (для обеих скобок), находим:
Заметим, что выражение в каждой скобке ложно только для одной комбинации исходных данных, при которых X = 0. Таким образом, для каждой строки таблицы истинности, где выражение равно 0, нужно построить логическую сумму, в которую переменные, равные в этой строке единице, входят с отрицанием, а равные нулю — без отрицания. Выражение для X — это произведение полученных сумм.
Такая запись — конъюнкция простых дизъюнкций — называется конъюнктивной нормальной формой (КНФ).
В нашем примере выражение упрощается с помощью распределительного закона для операции И и закона исключённого третьего:
Неудивительно, что мы получили тот же ответ, что и раньше.
Иногда при упрощении выражений может потребоваться искусственный приём, который сначала вроде бы усложняет запись, но затем позволяет получить более простую форму. Например, рассмотрим выражение
Учитывая, что В + ¬В= 1, можно представить второе слагаемое в виде
Тогда получаем
