Решение задачи: Найти СДНФ и СКНФ для формулы f = x ∨ y → ¬(y ∧ z)

Ниже представлено подробное решение задачи №7, оформленное для переписывания в школьную тетрадь. Задача 7. Найти СДНФ и СКНФ для формулы \( f = x \lor y \to \overline{y \land z} \). Решение: 1) Составим таблицу истинности для данной функции. Всего переменных три (\( x, y, z \)), значит будет \( 2^3 = 8 \) строк. \[ \begin{array}{|c|c|c|c|c|c|c|} \hline x & y & z & x \lor y & y \land z & \overline{y \land z} & f \\ \hline 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ \hline 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ \hline 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ \hline 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ \hline 1 & 0 & 0 & 1 & 0 & 1 & 1 \\ \hline 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ \hline 1 & 1 & 0 & 1 & 0 & 1 & 1 \\ \hline 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ \hline \end{array} \] 2) Составим СДНФ (Совершенную Дизъюнктивную Нормальную Форму). СДНФ составляется по строкам, в которых функция \( f \) принимает значение 1. Для каждой такой строки записывается конъюнкция переменных: если переменная равна 0, берем её с отрицанием, если 1 — без. Строки с \( f=1 \): (0,0,0), (0,0,1), (0,1,0), (1,0,0), (1,0,1), (1,1,0). \[ f_{СДНФ} = (\bar{x} \land \bar{y} \land \bar{z}) \lor (\bar{x} \land \bar{y} \land z) \lor (\bar{x} \land y \land \bar{z}) \lor (x \land \bar{y} \land \bar{z}) \lor (x \land \bar{y} \land z) \lor (x \land y \land \bar{z}) \] 3) Составим СКНФ (Совершенную Конъюнктивную Нормальную Форму). СКНФ составляется по строкам, в которых функция \( f \) принимает значение 0. Для каждой такой строки записывается дизъюнкция переменных: если переменная равна 1, берем её с отрицанием, если 0 — без. Строки с \( f=0 \): - Для строки (0,1,1): \( (x \lor \bar{y} \lor \bar{z}) \) - Для строки (1,1,1): \( (\bar{x} \lor \bar{y} \lor \bar{z}) \) \[ f_{СКНФ} = (x \lor \bar{y} \lor \bar{z}) \land (\bar{x} \lor \bar{y} \lor \bar{z}) \] Ответ: СДНФ: \( (\bar{x}\bar{y}\bar{z}) \lor (\bar{x}\bar{y}z) \lor (\bar{x}y\bar{z}) \lor (x\bar{y}\bar{z}) \lor (x\bar{y}z) \lor (xy\bar{z}) \) СКНФ: \( (x \lor \bar{y} \lor \bar{z}) \land (\bar{x} \lor \bar{y} \lor \bar{z}) \)