Question

Приведите данные формулы равносильным преобразованиями к ДНФ. Приведите данные формулы равносильными преобразованиями к КНФ

Answer 1

Для начала, давайте разберемся, что такое ДНФ и КНФ.

ДНФ (дизъюнктивная нормальная форма) — это логическая формула, в которой логическое ИЛИ используется для объединения конъюнкций литералов и их отрицаний. Литералом можно считать переменную или ее отрицание.

КНФ (конъюнктивная нормальная форма) — это логическая формула, в которой логическое И используется для объединения дизъюнкций литералов и их отрицаний.

Теперь перейдем к преобразованию данной формулы к ДНФ.

Исходная формула: ¬p ∨ (q ∧ r) ∧ (¬p ∨ s)

1. Начнем с раскрытия скобок: ¬p ∨ (q ∧ r) ∧ (¬p ∨ s) = ¬p ∨ (q ∧ r) ∨ (¬p ∨ s)

2. Теперь распределим дизъюнкцию над конъюнкцией: (¬p ∨ (q ∧ r) ∨ (¬p ∨ s)) = (¬p ∨ q ∨ s) ∧ (¬p ∨ r ∨ s)

Таким образом, данная формула равносильна ДНФ: (¬p ∨ q ∨ s) ∧ (¬p ∨ r ∨ s)

Теперь перейдем к преобразованию данной формулы к КНФ.

1. Приведем формулу к отрицанию над конъюнкцией: ¬(¬p ∨ q ∨ s) ∨ ¬(¬p ∨ r ∨ s)

2. Используем закон Де Моргана для внутренних отрицаний: (p ∧ ¬q ∧ ¬s) ∨ (p ∧ ¬r ∧ ¬s)

Таким образом, данная формула равносильна КНФ: (p ∧ ¬q ∧ ¬s) ∨ (p ∧ ¬r ∧ ¬s)

Вот и все! Мы представили данную формулу равносильными преобразованиями к ДНФ и КНФ. Если у вас возникнут еще вопросы, не стесняйтесь задавать.