Найти Совершенную Дизъюнктивную Нормальную Форму (СДНФ) функции

Предмет: Дискретная математика

Раздел: Логика, булевы функции. Нормальные формы.

Задача: Найти Совершенную Дизъюнктивную Нормальную Форму (СДНФ) функции. Функция дана в логической форме следующим образом: \[ f(x,y,z) = (\neg x \to y) \leftrightarrow ((y \land z) \to (x \land z)). \]

ШАГ 1: Преобразуем выражение \(\neg x \to y\)

Импликация \(p \to q\) равносильна логическому выражению \(\neg p \lor q\). Применим это правило: \[ \neg x \to y \equiv x \lor y. \] Теперь функция принимает вид: \[ f(x, y, z) = (x \lor y) \leftrightarrow ((y \land z) \to (x \land z)). \]

ШАГ 2: Преобразуем правую часть \((y \land z) \to (x \land z)\)

Как и в предыдущем шаге, заменим импликацию на дизъюнкцию: \[ (y \land z) \to (x \land z) \equiv \neg(y \land z) \lor (x \land z). \]

Используем правило де Моргана: \[ \neg(y \land z) \equiv \neg y \lor \neg z. \]

Получаем: \[ (y \land z) \to (x \land z) \equiv (\neg y \lor \neg z) \lor (x \land z). \] Теперь функция выглядит так: \[ f(x, y, z) = (x \lor y) \leftrightarrow ((\neg y \lor \neg z) \lor (x \land z)). \]

ШАГ 3: Теперь раскроем эквиваленцию \(\leftrightarrow\)

Эквиваленция \(p \leftrightarrow q\) равносильна \((p \land q) \lor (\neg p \land \neg q)\). Применим это преобразование к основному выражению.

Обозначим:

• \(P = x \lor y\),
• \(Q = (\neg y \lor \neg z) \lor (x \land z)\).

Тогда: \[ f(x, y, z) = (P \land Q) \lor (\neg P \land \neg Q). \] Здесь \(P \equiv (x \lor y)\) и \(Q \equiv (\neg y \lor \neg z) \lor (x \land z)\).

Заменив \(P\) и \(Q\) на их выражения, можно начинать дальнейшие упрощения через раскрытие скобок и преобразование логических операций, после чего построить СДНФ.

Для подробного рассчёта СДНФ нужно полностью расписать истинностную таблицу для каждого возможного набора переменных x, y, и z, чтобы построить дизъюнкцию «истинных» наборов логических переменных.

Подробные вычисления СДНФ потребуют развёртывания и упрощения выражений для всех сочетаний \(x, y, z\).