Найти ДНФ и КНФ логической формулы с помощью метода равносильных преобразований

Данный пример относится к области математической логики, подразделу логических исчислений.

Задание: найти ДНФ (дизъюнктивную нормальную форму) и КНФ (конъюнктивную нормальную форму) логической формулы с помощью метода равносильных преобразований.

Заданная формула: \[ (\neg x \vee \neg y) \rightarrow \neg (z \oplus x), \]

где:

• \(\neg\) — логическое отрицание,
• \(\vee\) — логическая дизъюнкция (ИЛИ),
• \(\rightarrow\) — логическая импликация,
• \(\oplus\) — логическое сложение по модулю 2 (исключающее ИЛИ, XOR).

Шаг 1. Преобразование импликации

Импликацию \( A \rightarrow B \) можно заменить на выражение \(\neg A \vee B\). Применим это преобразование:

\[ (\neg x \vee \neg y) \rightarrow \neg (z \oplus x) \equiv \neg (\neg x \vee \neg y) \vee \neg (z \oplus x). \]

Шаг 2. Преобразование исключающего ИЛИ (\(\oplus\))

\( z \oplus x \equiv (z \wedge \neg x) \vee (\neg z \wedge x) \). Тогда отрицание \(\neg (z \oplus x)\) будет равно:

\[ \neg \left((z \wedge \neg x) \vee (\neg z \wedge x)\right). \]

Применим закон де Моргана:

\[ \neg \left((z \wedge \neg x) \vee (\neg z \wedge x)\right) \equiv \neg (z \wedge \neg x) \wedge \neg (\neg z \wedge x). \]

Распишем отрицания для каждой части:

\[ \neg (z \wedge \neg x) \equiv \neg z \vee x, \quad \neg (\neg z \wedge x) \equiv z \vee \neg x. \]

Итак:

\[ \neg (z \oplus x) \equiv (\neg z \vee x) \wedge (z \vee \neg x). \]

Шаг 3. Подстановка в исходное выражение

Теперь вернемся к формуле:

\[ \neg (\neg x \vee \neg y) \vee \left((\neg z \vee x) \wedge (z \vee \neg x)\right). \]

Шаг 4. Преобразование \(\neg (\neg x \vee \neg y)\)

Применим закон де Моргана:

\[ \neg (\neg x \vee \neg y) \equiv x \wedge y. \]

Таким образом, формула примет вид:

\[ (x \wedge y) \vee \left((\neg z \vee x) \wedge (z \vee \neg x)\right). \]

Шаг 5. Приведение к дизъюнктивной нормальной форме (ДНФ)

Сначала раскроем скобки с помощью дистрибутивности:

\[ (x \wedge y) \vee \left[(\neg z \vee x) \wedge (z \vee \neg x)\right]. \]

Раскроем \(\left[(\neg z \vee x) \wedge (z \vee \neg x)\right]\) по дистрибутивности:

\[ (\neg z \vee x) \wedge (z \vee \neg x) \equiv (\neg z \wedge z) \vee (\neg z \wedge \neg x) \vee (x \wedge z) \vee (x \wedge \neg x). \]

Упрощаем выражение:

\[ \neg z \wedge \neg x \vee x \wedge z. \]

Теперь подставим обратно:

\[ (x \wedge y) \vee (\neg z \wedge \neg x) \vee (x \wedge z). \]

Это и есть дизъюнктивная нормальная форма (ДНФ).

Шаг 6. Приведение к конъюнктивной нормальной форме (КНФ)

Для КНФ воспользуемся тем, что данные преобразования уже дали нам упрощенную форму. Приведем к КНФ, используя двойственное преобразование закона дистрибутивности: