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

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

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

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

Конъюнктивная нормальная форма (КНФ) — это форма записи булевой функции, которая представляет собой конъюнкцию (логическое "И") нескольких дизъюнкций (логическое "ИЛИ") литералов. Каждый литерал — это либо переменная, либо её отрицание. Пример КНФ: (A ∨ B) ∧ (¬C ∨ D).

Теперь давайте проанализируем каждую из предложенных функций:

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

Это выражение соответствует КНФ. Оно состоит из двух дизъюнкций: (y ∨ z) и (¬x ∨ ¬z), соединённых конъюнкцией.

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

Это выражение не соответствует КНФ, так как вторая часть (¬x ∨ ¬(¬z ∨ y)) содержит вложенную дизъюнкцию (¬z ∨ y), что нарушает правила КНФ.

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

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

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

Это выражение не соответствует КНФ, так как первая часть (¬(x ∨ y) ∨ ¬z) содержит отрицание дизъюнкции (x ∨ y), что нарушает правила КНФ.

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

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

Таким образом, только первое выражение (y ∨ z) ∧ (¬x ∨ ¬z) записано в конъюнктивной нормальной форме.