Задание относится к предмету математическая логика, раздел — формальные логические преобразования. Нам нужно привести логическую формулу к совершенной дизъюнктивной нормальной форме (СДНФ). Формула: \[ (x \rightarrow (x \lor (y \land z))) \sim ((x \lor y) \rightarrow z). \]
Шаг 1: Преобразование импликаций
Импликация \( p \rightarrow q \) эквивалентна \( \neg p \lor q \). Преобразуем каждую из импликаций.
- \( x \rightarrow (x \lor (y \land z)) \) превращается в: \[ \neg x \lor (x \lor (y \land z)). \] Применим ассоциативность логического «ИЛИ» \( \lor \): \[ \neg x \lor (x \lor (y \land z)) \equiv (\neg x \lor x \lor (y \land z)). \] Так как \( \neg x \lor x \) — это тавтология (всегда истинно), мы имеем: \[ \neg x \lor x \lor (y \land z) \equiv 1. \] Значит, левая часть формулы эквивалентна 1.
- Теперь преобразуем правую часть формулы \( (x \lor y) \rightarrow z \): \[ (x \lor y) \rightarrow z \equiv \neg (x \lor y) \lor z. \] Применим закон де Моргана для отрицания дизъюнкции: \[ \neg (x \lor y) \equiv \neg x \land \neg y, \] тогда: \[ \neg (x \lor y) \lor z \equiv (\neg x \land \neg y) \lor z. \]
Шаг 2: Формула после преобразования импликаций
Теперь формула выглядит так:
\[ 1 \sim ((\neg x \land \neg y) \lor z). \] Так как
\( \sim \) — это эквивалентность, формула имеет смысл как
\( 1 = ((\neg x \land \neg y) \lor z) \).
Шаг 3: Преобразование эквивалентности
Формула эквивалентности
\( p \sim q \) эквивалентна
\( (p \land q) \lor (\neg p \land \neg q) \). В нашем случае
\( p = 1 \), а
\( q = (\neg x \land \neg y) \lor z \). Тогда для нашей формулы:
\[ (1 \land ((\neg x \land \neg y) \lor z)) \lor (\neg 1 \land \neg ((\neg x \land \neg y) \lor z)). \] Учитывая, что
\( 1 \land q \equiv q \), а
\( \neg 1 \equiv 0 \), и при этом
\( 0 \land ... \) всегда равно 0, остаётся только:
\[ (\neg x \land \neg y) \lor z. \]
Шаг 4: Приведение формулы к СДНФ
Используя дистрибутивность операции «ИЛИ» относительно «И», применим её последовательно:
\[ (\neg x \land \neg y) \lor z \equiv (\neg x \land \neg y) \lor (z \land 1). \] СДНФ для формулы:
\[ (\neg x \land \neg y ) \lor (\neg x \land y \land z) \lor (x \land \neg y \land z) \lor (x \land y \land z). \] Это и есть совершенная дизъюнктивная нормальная форма для заданной формулы.
Ответ: СДНФ формулы: \[ (\neg x \land \neg y ) \lor (\neg x \land y \land z) \lor (x \land \neg y \land z) \lor (x \land y \land z). \]