Какая из следующих конъюнктивных нормальных форм эквивалентна формуле: (¬x ⊕ y) → (y ∧ z)

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

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

Чтобы выяснить, какая из предложенных конъюнктивных нормальных форм (КНФ) эквивалентна данной формуле, давайте сначала разберемся с исходной формулой: (¬x ⊕ y) → (y ∧ z).

1. Раскроем импликацию: Формула вида A → B эквивалентна ¬A ∨ B. Поэтому (¬x ⊕ y) → (y ∧ z) преобразуется в ¬(¬x ⊕ y) ∨ (y ∧ z).

2. Разберемся с исключающим ИЛИ (исключающее или, XOR): ¬x ⊕ y эквивалентно (¬x ∧ ¬y) ∨ (x ∧ y). Следовательно, ¬(¬x ⊕ y) будет эквивалентно ¬((¬x ∧ ¬y) ∨ (x ∧ y)), что по законам де Моргана преобразуется в (x ∨ y) ∧ (¬x ∨ ¬y).

3. Подставим это обратно в формулу: Теперь наша формула выглядит как ((x ∨ y) ∧ (¬x ∨ ¬y)) ∨ (y ∧ z).

4. Применим дистрибутивность: Перепишем формулу, применяя дистрибутивное свойство логики:

   ((x ∨ y) ∧ (¬x ∨ ¬y)) ∨ (y ∧ z) = [(x ∨ y) ∨ (y ∧ z)] ∧ [(¬x ∨ ¬y) ∨ (y ∧ z)]

5. Упростим выражения:

   • (x ∨ y) ∨ (y ∧ z) = x ∨ y (так как y ∨ (y ∧ z) = y)
   • (¬x ∨ ¬y) ∨ (y ∧ z) = ¬x ∨ ¬y ∨ z (так как (¬y ∨ (y ∧ z)) = ¬y ∨ z)

6. Получаем итоговую формулу: x ∨ y ∧ (¬x ∨ ¬y ∨ z)

Теперь сравним с предложенными вариантами:

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

Сравнивая с нашей итоговой формулой x ∨ y ∧ (¬x ∨ ¬y ∨ z), мы видим, что первый вариант точно соответствует нашему результату.

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