Предваренная нормальная форма (ПНФ), ее нахождение

Опр. ПНФ называется формула, имеющая вид:

, где ,

причем формула F (x ₁, x ₂, …, x _n) не содержит импликаций и кванторов. Отрицания относятся только к простейшим формулам, входящим в F. Q ₁ x ₁ Q ₂ x ₂ … Q _k x _k - кванторная приставка (префикс). F (x ₁, x ₂, …, x _n) называется матрицей.

Пример:

1) – ПНФ;

2) – не ПНФ, но легко написать равносильную ей ПНФ:

Т. Для любой формулы ЛП существует равносильная ей ПНФ

Чтобы найти ПНФ, нужно:

1) А®B ~ ØAÚB;

2) законы де Моргана;

3) равносильности (3)-(10); 4) ДНФ.

Пример: найти ПНФ, равносильную данной:

1)

- ПНФ ДНФ

2)

не содержит х

не содержит х ₁

– ПНФ.

20. Основные равносильности ЛП, их док-во.

Опр. Две формулы F1 и F2 сигнатуры s называются равносильными, если они в любой модели той же сигнатуры на любых наборах элементов из этой модели принимают одинаковые значения истинности, т.е. в одной и той же модели они одновременно истинны либо одновременно ложны.

Обозн.: F1 ~ F2.

Замечание: Если формулы равносильны в АВ, то они равносильны и в ЛП, т.к. таблицы истинности остаются прежними.

Например:

ØØ"хР(x,y) ~ "хР(x,y);

ØP(x)&ØQ(y) ~ Ø(P(x)ÚQ(y)).

Равносильности ЛП

Формулы доказываются методом Генцена.

Замечания:

1) Формулы

и

не равносильны, но из истинности второй следует истинность первой. Обратное неверно.

2) Формулы

и

не равносильны, но из истинности первой следует истинность второй. Обратное неверно.

3) Формулы

и

не равносильны, но из истинности второй следует истинность первой. Обратное неверно.