Решим задачу по шагам, как это удобно для школьника.
Задача
У мальчика Коли есть мама, папа, дедушка и бабушка. Коля пойдёт гулять на улицу, если ему разрешат хотя бы двое родственников.
Для краткости обозначим родственников Коли через буквы:
мама — \(x_1\)
папа — \(x_2\)
дедушка — \(x_3\)
бабушка — \(x_4\)
Условимся обозначать согласие родственников единицей, несогласие — нулём.
Возможность пойти погулять обозначим буквой \(f\).
Коля идёт гулять — \(f = 1\).
Коля гулять не идёт — \(f = 0\).
Составить таблицу истинности.
По таблице истинности составить СКНФ.
Решение
1. Определение входных и выходных данных
У нас есть 4 входные переменные, которые обозначают согласие или несогласие каждого родственника:
\(x_1\) — мама
\(x_2\) — папа
\(x_3\) — дедушка
\(x_4\) — бабушка
Каждая из этих переменных может принимать значение 0 (несогласие) или 1 (согласие).
Выходная переменная \(f\) обозначает, пойдёт ли Коля гулять:
\(f = 1\) — Коля идёт гулять
\(f = 0\) — Коля не идёт гулять
Условие для Коли: он пойдёт гулять, если ему разрешат хотя бы двое родственников. Это означает, что сумма значений \(x_1 + x_2 + x_3 + x_4\) должна быть больше или равна 2.
2. Составление таблицы истинности
Так как у нас 4 входные переменные, то количество возможных комбинаций будет \(2^4 = 16\).
Мы будем перечислять все возможные комбинации значений \(x_1, x_2, x_3, x_4\) и для каждой комбинации определять значение \(f\).
Для удобства добавим столбец "Сумма согласий", чтобы было легче определить значение \(f\).
| \(x_1\) (мама) |
\(x_2\) (папа) |
\(x_3\) (дедушка) |
\(x_4\) (бабушка) |
Сумма согласий (\(x_1+x_2+x_3+x_4\)) |
\(f\) (Коля идёт гулять) |
| 0 |
0 |
0 |
0 |
0 |
0 |
| 0 |
0 |
0 |
1 |
1 |
0 |
| 0 |
0 |
1 |
0 |
1 |
0 |
| 0 |
0 |
1 |
1 |
2 |
1 |
| 0 |
1 |
0 |
0 |
1 |
0 |
| 0 |
1 |
0 |
1 |
2 |
1 |
| 0 |
1 |
1 |
0 |
2 |
1 |
| 0 |
1 |
1 |
1 |
3 |
1 |
| 1 |
0 |
0 |
0 |
1 |
0 |
| 1 |
0 |
0 |
1 |
2 |
1 |
| 1 |
0 |
1 |
0 |
2 |
1 |
| 1 |
0 |
1 |
1 |
3 |
1 |
| 1 |
1 |
0 |
0 |
2 |
1 |
| 1 |
1 |
0 |
1 |
3 |
1 |
| 1 |
1 |
1 |
0 |
3 |
1 |
| 1 |
1 |
1 |
1 |
4 |
1 |
3. Составление СКНФ (Совершенной Конъюнктивной Нормальной Формы)
СКНФ строится по тем строкам таблицы истинности, где функция \(f\) принимает значение 0.
Для каждой такой строки мы составляем дизъюнкцию (логическое ИЛИ) переменных. Если переменная в строке равна 0, то она берётся без инверсии. Если переменная равна 1, то она берётся с инверсией (отрицанием).
Затем все эти дизъюнкции объединяются конъюнкцией (логическим И).
Строки, где \(f = 0\):
1. \(x_1=0, x_2=0, x_3=0, x_4=0\):
Дизъюнкция: \((x_1 \lor x_2 \lor x_3 \lor x_4)\)
2. \(x_1=0, x_2=0, x_3=0, x_4=1\):
Дизъюнкция: \((x_1 \lor x_2 \lor x_3 \lor \overline{x_4})\)
3. \(x_1=0, x_2=0, x_3=1, x_4=0\):
Дизъюнкция: \((x_1 \lor x_2 \lor \overline{x_3} \lor x_4)\)
4. \(x_1=0, x_2=1, x_3=0, x_4=0\):
Дизъюнкция: \((x_1 \lor \overline{x_2} \lor x_3 \lor x_4)\)
5. \(x_1=1, x_2=0, x_3=0, x_4=0\):
Дизъюнкция: \(( \overline{x_1} \lor x_2 \lor x_3 \lor x_4)\)
Теперь объединим эти дизъюнкции конъюнкцией:
\[
f = (x_1 \lor x_2 \lor x_3 \lor x_4) \land (x_1 \lor x_2 \lor x_3 \lor \overline{x_4}) \land (x_1 \lor x_2 \lor \overline{x_3} \lor x_4) \land (x_1 \lor \overline{x_2} \lor x_3 \lor x_4) \land (\overline{x_1} \lor x_2 \lor x_3 \lor x_4)
\]
Это и есть Совершенная Конъюнктивная Нормальная Форма для данной функции.
