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

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

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

Заданная формула: $\text{[}(\mathrm{\neg }x\vee \mathrm{\neg }y)\to \mathrm{\neg }(z\oplus x),\text{]}$

где:

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

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

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

$\text{[}(\mathrm{\neg }x\vee \mathrm{\neg }y)\to \mathrm{\neg }(z\oplus x)\equiv \mathrm{\neg }(\mathrm{\neg }x\vee \mathrm{\neg }y)\vee \mathrm{\neg }(z\oplus x).\text{]}$

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

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

$\text{[}\mathrm{\neg }((z\wedge \mathrm{\neg }x)\vee (\mathrm{\neg }z\wedge x)).\text{]}$

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

$\text{[}\mathrm{\neg }((z\wedge \mathrm{\neg }x)\vee (\mathrm{\neg }z\wedge x))\equiv \mathrm{\neg }(z\wedge \mathrm{\neg }x)\wedge \mathrm{\neg }(\mathrm{\neg }z\wedge x).\text{]}$

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

$\text{[}\mathrm{\neg }(z\wedge \mathrm{\neg }x)\equiv \mathrm{\neg }z\vee x,\mathrm{\neg }(\mathrm{\neg }z\wedge x)\equiv z\vee \mathrm{\neg }x.\text{]}$

Итак:

$\text{[}\mathrm{\neg }(z\oplus x)\equiv (\mathrm{\neg }z\vee x)\wedge (z\vee \mathrm{\neg }x).\text{]}$

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

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

$\text{[}\mathrm{\neg }(\mathrm{\neg }x\vee \mathrm{\neg }y)\vee ((\mathrm{\neg }z\vee x)\wedge (z\vee \mathrm{\neg }x)).\text{]}$

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

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

$\text{[}\mathrm{\neg }(\mathrm{\neg }x\vee \mathrm{\neg }y)\equiv x\wedge y.\text{]}$

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

$\text{[}(x\wedge y)\vee ((\mathrm{\neg }z\vee x)\wedge (z\vee \mathrm{\neg }x)).\text{]}$

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

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

$\text{[}(x\wedge y)\vee [(\mathrm{\neg }z\vee x)\wedge (z\vee \mathrm{\neg }x)].\text{]}$

Раскроем $\text{(}[(\mathrm{\neg }z\vee x)\wedge (z\vee \mathrm{\neg }x)]\text{)}$ по дистрибутивности:

$\text{[}(\mathrm{\neg }z\vee x)\wedge (z\vee \mathrm{\neg }x)\equiv (\mathrm{\neg }z\wedge z)\vee (\mathrm{\neg }z\wedge \mathrm{\neg }x)\vee (x\wedge z)\vee (x\wedge \mathrm{\neg }x).\text{]}$

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

$\text{[}\mathrm{\neg }z\wedge \mathrm{\neg }x\vee x\wedge z.\text{]}$

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

$\text{[}(x\wedge y)\vee (\mathrm{\neg }z\wedge \mathrm{\neg }x)\vee (x\wedge z).\text{]}$

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

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

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