1. Сравните методы синтеза логических выражений с помощью ДНФ и КНФ. Когда лучше использовать каждый из них?
Методы синтеза логических выражений с помощью дизъюнктивной нормальной формы (ДНФ) и конъюнктивной нормальной формы (КНФ) различаются в подходе к представлению логической функции. ДНФ представляет функцию как дизъюнкцию (или сумму) конъюнкций (или произведений) элементарных переменных и их отрицаний. Это удобно для случаев, когда требуется выделить отдельные условия, при которых выражение истинно. КНФ, напротив, представляет функцию как конъюнкцию дизъюнкций, что упрощает работу с условиями, при которых выражение ложно. ДНФ предпочтительна для задач анализа истинности выражений, тогда как КНФ удобнее для проверки выполнимости или работы с системами ограничений.
2. Предложите простой метод перехода от КНФ к ДНФ. Продемонстрируйте его на примере выражения X = (А + ¬В) • (¬А + В). Как называется эта логическая операция?
Для перехода от КНФ к ДНФ используется преобразование, основанное на раскрытии всех возможных комбинаций переменных. Рассмотрим выражение X = (A + ¬B) • (¬A + B). Шаги: Раскрываем скобки с помощью дистрибутивности: X = (A • ¬A) + (A • B) + (¬B • ¬A) + (¬B • B). Упрощаем выражение, исключая противоречивые комбинации (A • ¬A и ¬B • B равны нулю): X = (A • B) + (¬A • ¬B).
Это преобразование называется операцией исключающего "или" (XOR).
3. Используя дополнительные источники, выясните, как перейти от ДНФ к КНФ, используя законы де Моргана. Продемонстрируйте этот метод на примере выражения X = А•¬В +¬А•В. Как называется эта логическая операция?
Для перехода от ДНФ к КНФ используется применение законов де Моргана. Рассмотрим пример X = A • ¬B + ¬A • B. Шаги: Записываем выражение как отрицание отрицания: X = ¬(¬(A • ¬B + ¬A • B)). Применяем закон де Моргана к внутреннему отрицанию: ¬(¬(A • ¬B) • ¬(¬A • B)). Раскрываем отрицания: X = (¬A + B) • (A + ¬B).
Этот процесс также выражает логическую операцию исключающего "или" (XOR), но в форме КНФ.