![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Опр. ПНФ называется формула, имеющая вид:
, где
,
причем формула F (x 1, x 2, …, x n) не содержит импликаций и кванторов. Отрицания относятся только к простейшим формулам, входящим в F. Q 1 x 1 Q 2 x 2 … Q k x k - кванторная приставка (префикс). F (x 1, x 2, …, x n) называется матрицей.
Пример:
1) – ПНФ;
2) – не ПНФ, но легко написать равносильную ей ПНФ:
Т. Для любой формулы ЛП существует равносильная ей ПНФ
Чтобы найти ПНФ, нужно:
1) А®B ~ ØAÚB;
2) законы де Моргана;
3) равносильности (3)-(10); 4) ДНФ.
Пример: найти ПНФ, равносильную данной:
1)
- ПНФ ДНФ
2)
не содержит х
не содержит х 1
– ПНФ.
20. Основные равносильности ЛП, их док-во.
Опр. Две формулы F1 и F2 сигнатуры s называются равносильными, если они в любой модели той же сигнатуры на любых наборах элементов из этой модели принимают одинаковые значения истинности, т.е. в одной и той же модели они одновременно истинны либо одновременно ложны.
Обозн.: F1 ~ F2.
Замечание: Если формулы равносильны в АВ, то они равносильны и в ЛП, т.к. таблицы истинности остаются прежними.
Например:
ØØ"хР(x,y) ~ "хР(x,y);
ØP(x)&ØQ(y) ~ Ø(P(x)ÚQ(y)).
Равносильности ЛП
Формулы доказываются методом Генцена.
Замечания:
1) Формулы
и
не равносильны, но из истинности второй следует истинность первой. Обратное неверно.
2) Формулы
и
не равносильны, но из истинности первой следует истинность второй. Обратное неверно.
3) Формулы
и
не равносильны, но из истинности второй следует истинность первой. Обратное неверно.
Дата публикования: 2014-12-08; Прочитано: 634 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!