Найти совершенную конъюнктивную нормальную форму (СКНФ) для логической функции, заданной таблицей истинности

Область задания:

Предмет: Дискретная математика (Булева алгебра)
Раздел: Логические функции. Совершенная конъюнктивная нормальная форма (СКНФ)

Задача:

Найти совершенную конъюнктивную нормальную форму (СКНФ) для логической функции, заданной таблицей истинности.

Шаги решения:

1. Напоминаем, что такое СКНФ:

СКНФ — это представление логической функции в виде конъюнкции дизъюнктов, где:

• В каждом дизъюнкте переменные либо берутся с инверсией, либо без, в зависимости от строки таблицы истинности с \(f(x, y) = 0\).

2. Выбираем строки таблицы с \(f(x, y) = 0\):

По таблице видно:

• \(f(0, 1) = 0\) → \(x = 0\), \(y = 1\),
• \(f(1, 1) = 0\) → \(x = 1\), \(y = 1\).

3. Записываем дизъюнкты для каждой строки с \(f = 0\):

• Для строки \(x = 0\), \(y = 1\): \(x \lor \overline{y}\),
• Для строки \(x = 1\), \(y = 1\): \(\overline{x} \lor \overline{y}\).

4. Соединяем дизъюнкты с помощью конъюнкции:

СКНФ: \[ (x \lor \overline{y}) \land (\overline{x} \lor \overline{y}) \].

5. Правильный ответ:

\[ (x \lor \overline{y}) \land (\overline{x} \lor \overline{y}) \].

Окончательный выбор:

Ответ: \( (x \lor \overline{y}) \land (\overline{x} \lor \overline{y}) \).