Товарищи, помогите с заданием по логике.
нужно привести формулу эквивалентными преобразованиями к сднф и скнф:
(x1 ∧ !x2 V x3 ∧ x4) ∧ (x2 V x4) ∧ (x1 V !x3 V !x4)
ps:
V - дизъюнкция
∧ - конъюнкция
! - отрицание
очень нужно, товарищи!
Ответы
Ответ:Для получения СДНФ (совершенной дизъюнктивной нормальной формы) нам нужно раскрыть скобки и объединить конъюнкции с помощью дизъюнкций, чтобы получить каждую возможную комбинацию переменных. Затем мы можем использовать отрицания для приведения каждого литерала в форму, которую можно использовать в дизъюнкции. Используя эти шаги, мы можем привести данную формулу к СДНФ:
(x1 ∧ !x2 ∧ x2 ∧ x1 ∧ x4 ∧ !x3) ∨
(x1 ∧ !x2 ∧ x2 ∧ x3 ∧ x4 ∧ !x3) ∨
(x1 ∧ x2 ∧ x2 ∧ x1 ∧ x4 ∧ !x3) ∨
(x1 ∧ x2 ∧ x2 ∧ x3 ∧ x4 ∧ !x3)
Для получения СКНФ (совершенной конъюнктивной нормальной формы), нам нужно привести каждую возможную комбинацию переменных к конъюнкции литералов с помощью дизъюнкций, используя отрицания для приведения каждого литерала в форму, который может быть использован в конъюнкции. Мы можем привести данную формулу к СКНФ следующим образом:
(x1 ∨ x2 ∨ x3) ∧ (!x2 ∨ x4) ∧ (!x3 ∨ x4)
Пошаговое объяснение:
Відповідь:
Для приведения данной логической формулы к СДНФ (совершенной дизъюнктивной нормальной форме) и СКНФ (совершенной конъюнктивной нормальной форме) необходимо выполнить следующие шаги:
Применить закон дистрибутивности для упрощения формулы:
(x1 ∧ !x2 V x3 ∧ x4) ∧ (x2 V x4) ∧ (x1 V !x3 V !x4)
= (x1 ∧ !x2 ∧ x2 V x3 ∧ x2 V x4 ∧ !x2 V x4 ∧ !x2 V x1 ∧ x4 ∧ !x3) // раскрытие скобок
= (x1 ∧ !x2 V x3 ∧ x2 V x4) ∧ (x1 ∧ !x2 V x4 ∧ !x3) // упрощение
Привести полученную формулу к СДНФ, используя закон дистрибутивности:
(x1 ∧ !x2 V x3 ∧ x2 V x4) ∧ (x1 ∧ !x2 V x4 ∧ !x3)
= (x1 ∧ !x2 ∧ x3 ∧ x2 ∧ x1 ∧ !x2 ∧ x4) V
(x1 ∧ !x2 ∧ x3 ∧ x2 ∧ !x4 ∧ x1 ∧ !x2 ∧ x4) V
(x1 ∧ !x2 ∧ x4 ∧ !x3 ∧ x1 ∧ !x2 ∧ x4) V
(x1 ∧ !x2 ∧ x4 ∧ !x3 ∧ !x4 ∧ x1 ∧ !x2 ∧ x4) // применение закона дистрибутивности
= x1 ∧ !x2 ∧ x3 ∧ x2 ∧ x4 V
x1 ∧ !x2 ∧ x3 ∧ x2 ∧ !x4 V
x1 ∧ !x2 ∧ x4 ∧ !x3 ∧ x4 V
x1 ∧ !x2 ∧ x4 ∧ !x3 ∧ !x4 ∧ x4 // устранение тождественно ложных слагаемых
Таким образом, СДНФ данной формулы выглядит следующим образом:
(x1 ∧ !x2 ∧ x3 ∧ x2 ∧ x4) V
(x1 ∧ !x2 ∧ x3 ∧ x2 ∧ !x4) V
(x1 ∧ !x2 ∧ x4 ∧ !x3 ∧ x4) V
(x1 ∧ !x2 ∧ x4 ∧ !x3)
Привести исходную формулу к СКНФ, используя закон дистрибутивности:
(x1 ∧ !x2 V x3 ∧ x4) ∧ (x2 V x4) ∧ (x1 V !x3 V !x4)
= (x1 V !x3 V !x4) ∧ (x1 ∧ !x2 V x3 ∧ x4) ∧ (x2 V x4) // перестановка множителей
= (x1 V !x3 V !x4) ∧ (x1 ∧ !x2 ∧ x3