Логические выражения и нормальные формы

Предмет: Математическая логика

Раздел: Логические выражения и нормальные формы

Решение задания №1

Формула: $f=-((\overline{x}\wedge y\iff \overline{y})\Rightarrow (x\vee y))$

Шаг 1: Раскрытие эквивалентности

Эквивалентность можно заменить эквивалентным выражением:
$a\iff b=(a\vee \overline{b})\wedge (\overline{a}\vee b)$

Применяем к $(\overline{x}\wedge y\iff \overline{y})$:

$(\overline{x}\wedge y\iff \overline{y})=((\overline{x}\wedge y)\vee y)\wedge (\overline{(\overline{x}\wedge y)}\vee \overline{y})$

Упрощаем:

$(\overline{x}\wedge y\vee y)\wedge ((x\vee \overline{y})\vee \overline{y})$

$(y\vee \overline{x})\wedge (x\vee \overline{y}\vee \overline{y})$

$(y\vee \overline{x})\wedge (x\vee \overline{y})$

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

$f=-(((y\vee \overline{x})\wedge (x\vee \overline{y}))\Rightarrow (x\vee y))$

Импликация заменяется по правилу $A\Rightarrow B=\overline{A}\vee B$:

$f=-(\overline{((y\vee \overline{x})\wedge (x\vee \overline{y}))}\vee (x\vee y))$

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

$f=-((\overline{(y\vee \overline{x})}\vee \overline{(x\vee \overline{y})})\vee (x\vee y))$

$f=-(((\overline{y}\wedge x)\vee (\overline{x}\wedge y))\vee (x\vee y))$

Шаг 3: Упрощение

Так как $(x\vee y)$ уже присутствует, вся скобка становится истинной, а отрицание даёт ложь:
$f=0$

Следовательно, СКНФ и СДНФ не существуют, так как функция тождественно равна 0.

Решение задания №2

Формула:
$(\mathrm{\neg }\mathrm{\exists }yP(x,y)\Rightarrow \mathrm{\neg }\mathrm{\forall }x\mathrm{\forall }yQ(x,y))\Rightarrow R(x)$

Шаг 1: Преобразование к отрицаниям

Используем правило:
$\mathrm{\neg }\mathrm{\exists }yP(x,y)=\mathrm{\forall }y\mathrm{\neg }P(x,y)$
$\mathrm{\neg }\mathrm{\forall }x\mathrm{\forall }yQ(x,y)=\mathrm{\exists }x\mathrm{\exists }y\mathrm{\neg }Q(x,y)$

Подставляем:
$(\mathrm{\forall }y\mathrm{\neg }P(x,y)\Rightarrow \mathrm{\exists }x\mathrm{\exists }y\mathrm{\neg }Q(x,y))\Rightarrow R(x)$

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

$A\Rightarrow B=\mathrm{\neg }A\vee B$

Применяем к первой импликации:
$(\mathrm{\neg }\mathrm{\forall }y\mathrm{\neg }P(x,y)\vee \mathrm{\exists }x\mathrm{\exists }y\mathrm{\neg }Q(x,y))\Rightarrow R(x)$

Применяем ко второй импликации:
$\mathrm{\neg }(\mathrm{\neg }\mathrm{\forall }y\mathrm{\neg }P(x,y)\vee \mathrm{\exists }x\mathrm{\exists }y\mathrm{\neg }Q(x,y))\vee R(x)$

Шаг 3: Упрощение

Используем закон де Моргана:
$(\mathrm{\forall }y\mathrm{\neg }P(x,y)\wedge \mathrm{\forall }x\mathrm{\forall }yQ(x,y))\vee R(x)$

Это и есть пренексная нормальная форма (ПНФ).