Какая из булевых функций записана в конъюнктивной нормальной форме (КНФ)

• (y ∨ ¬z) ∧ (¬x ∨ ¬z)
• ¬(y ∨ ¬z) ∧ (¬x ∨ ¬z)
• (y ∧ ¬z) ∨ (¬x ∧ ¬z)
• ¬((y ∨ ¬z) ∧ (¬x ∨ ¬z))
• (y ∨ ¬z) ∧ ¬(¬x ∨ ¬z)
  

Другие предметы Университет Булевы функции и нормальные формы дискретная математика булевы функции конъюнктивная нормальная форма КНФ логика университет математическая логика учебные материалы примеры задач теоретическая информатика Новый

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

Конъюнктивная нормальная форма (КНФ) - это логическое выражение, которое представляется в виде конъюнкции (операция "И") нескольких дизъюнкций (операция "ИЛИ"). То есть, КНФ имеет следующий вид:

• (A1 ∨ A2 ∨ ... ∨ An) ∧ (B1 ∨ B2 ∨ ... ∨ Bm) ∧ ... ∧ (Z1 ∨ Z2 ∨ ... ∨ Zk)

Где A, B, Z - это логические переменные или их отрицания.

Теперь давайте проанализируем предложенные выражения:

1. (y ∨ ¬z) ∧ (¬x ∨ ¬z)
2. ¬(y ∨ ¬z) ∧ (¬x ∨ ¬z)
3. (y ∧ ¬z) ∨ (¬x ∧ ¬z)
4. ¬((y ∨ ¬z) ∧ (¬x ∨ ¬z))
5. (y ∨ ¬z) ∧ ¬(¬x ∨ ¬z)

Теперь оценим каждое из этих выражений на соответствие КНФ:

• (y ∨ ¬z) ∧ (¬x ∨ ¬z) - это выражение в КНФ, так как оно является конъюнкцией двух дизъюнкций.
• ¬(y ∨ ¬z) ∧ (¬x ∨ ¬z) - это выражение не в КНФ, так как первая часть ¬(y ∨ ¬z) не является дизъюнкцией.
• (y ∧ ¬z) ∨ (¬x ∧ ¬z) - это выражение не в КНФ, так как оно является дизъюнкцией, а не конъюнкцией.
• ¬((y ∨ ¬z) ∧ (¬x ∨ ¬z)) - это выражение не в КНФ, так как оно является отрицанием конъюнкции.
• (y ∨ ¬z) ∧ ¬(¬x ∨ ¬z) - это выражение не в КНФ, так как вторая часть ¬(¬x ∨ ¬z) не является дизъюнкцией.

Таким образом, единственное выражение, которое соответствует конъюнктивной нормальной форме, это:

(y ∨ ¬z) ∧ (¬x ∨ ¬z)