Нормальна форма формули у логіці предикатів

Нормальна форма формули у логіці предикатів — це формула, яка містить лише операції кон'юнкції, диз'юнкції та кванторні операції, а операція заперечення відноситься до елементарних формул.

З допомогою рівностей алгебри висловлень й логіки предикатів кожну формулу логіки предикатів можна привести до нормальної формули.

Теорема про нормальну форму

Теорема: Кожна формула логіки предикатів має нормальну форму.

Доведення: Перш ніж доводити теорему, встановимо 4 равносильності, які необхідні нам надалі. В них передбачається, що формула Н не містить вільної змінної х:

1. $\forall xW(x)\lor H=\forall x(W(x)\lor H)$
2. $\exists xW(x)\lor H=\exists x(W(x)\lor H)$
3. $\forall xW(x)\land H=\forall x(W(x)\land H)$
4. $\exists xW(x)\land H=\exists x(W(x)\land H)$

Встановимо першу з цих рівносильностей. Решта - аналогічно.

Нехай $\forall xW(x)\lor H$ істинна для деякої області М. Тоді на М істинно чи $\forall xW(x)$, чи $H$. В першому випадку $W(x)$ тотожно істинний на М предикат і через те, що $H$ не містить х, $W(x)\lor H$ теж тотожно істинний на М предикат, і тоді $\forall xW(x)\lor H$ - істинно. У другому випадку, якщо істинно $H$, то істинно і $W(x)\lor H$ незалежно від х, а значить $\forall x$ з М.

Нехай тепер $\forall xW(x)\lor H$ хибно. Тоді $\forall xW(x)$ і $H$ хибні. Тобто існує ${x_{0}}\in M$, такий що $W(x_{0})$ хибно. Але тоді $W(x)\lor H$ хибно, бо $\forall xW(x)\lor H$ хибно.

Доведемо тепер теорему методом індукції. Для елементарних формул наше твердження істинне, бо вони самі є нормальними формами. Будь-яку формулу можна записати, використовуючи операції $\land ,\lor ,\neg ,$, тому достатньо показати, що якщо $W_{1}$ і $W_{2}$ мають нормальні форми, то і $\neg W_{1}$, $W_{1}\land W_{2}$, $W_{1}\lor W_{2}$ теж мають нормальні форми. Нехай $W_{1}$ і $W_{2}$ мають нормальні форми ${\widetilde {W_{1}}}$ і ${\widetilde {W_{2}}}$, де

${\widetilde {W_{1}}}=\forall x_{1}...\forall x_{i}\exists x_{i+1}...\exists x_{n}V_{1}(x_{1}...x_{n})$

${\widetilde {W_{1}}}=\exists y_{1}...\exists y_{i}\forall y_{i+1}...y_{m}V_{2}(y_{1}...y_{m})$

Тоді формулі $W_{1}\lor W_{2}$ рівносильна формула ${\widetilde {W_{1}}}\lor {\widetilde {W_{2}}}$, яка може завжди бути приведена до нормальної форми з використанням рівностей 1 – 2:

${\widetilde {W_{1}}}\lor {\widetilde {W_{2}}}=\forall x_{1}[\forall x_{2}...\forall x_{i}\exists x_{i+1}...\exists x_{n}V_{1}(x_{1}...x_{n})\lor \exists y_{1}...\exists y_{i}\forall y_{i+1}...y_{m}V_{2}(y_{1}...y_{m})]=\forall x_{1}...\forall x_{i}\exists x_{i+1}...\exists x_{n}\exists y_{1}...\exists y_{i}\forall y_{i+1}...y_{m}[V_{1}(x_{1}...x_{n})\lor V_{2}(y_{1}...y_{m})]$

Таким чином, отримана нормальна форма формули $W_{1}\lor W_{2}$. Аналогічно, з рівностей 3,4 отримаємо, що можна побудувати нормальну форму і для $W_{1}\land W_{2}$. Нарешті, якщо відома нормальна форма ${\widetilde {W_{1}}}$ формули ${W_{1}}$, то нормальна форма ${\overline {W_{1}}}$ має вигляд:

${\overline {W_{1}}}={\overline {\forall x_{1}...\forall x_{i}\exists x_{i+1}...\exists x_{n}V_{1}(x_{1}...x_{n})}}=\exists x_{1}...\exists x_{i}\forall x_{i+1}...\forall x_{n}{\overline {V_{1}(x_{1}...x_{n})}}$

Таким чином встановлено, що будь-яка формула логіки предикатів має нормальну форму.

Алгоритм приведення формули до нормальної форми

Для приведення формули до нормальної форми потрібно виконати наступні операції:

1. виключити операції $\rightarrow$, ~, якщо вони є;
2. зменшити область знаків заперечення;
3. перейменувати змінні так, щоб можна було винести квантори в початок формули.

Приклад

$\neg (\forall xP(x)\rightarrow \exists xQ(x))=\neg (\neg (\forall xP(x))\lor \exists xQ(x))=\forall xP(x)\land \forall x\neg Q(x)=\forall xP(x)\land \forall y\neg Q(y)=\forall x\forall yP(x)\neg Q(y)$

Посилання

• Алгоритмы приведения к нормальным формам (рус.) [Архівовано 16 січня 2014 у Wayback Machine.]
• Префиксная нормальная форма (рус.) [Архівовано 29 листопада 2014 у Wayback Machine.]
• Основи логіки предикатів [Архівовано 29 листопада 2014 у Wayback Machine.]