Равносильные формулы логики предикатов. Правила вывода

логики предикатов
называются равносильными на множестве M,

если при
любой подстановке в эти формулы вместо предикатных
переменных любых конкретных предикатов, определенных на
M, эти формулы превращаются в равносильные предикаты
(F1+ = F2+).

Если формулы F1 и F2 равносильны на любых множествах,
то они называются просто равносильными (F1 = F2) .
В частности, все ТИ формулы (тавтологии) равносильны, и все
ТЛ формулы равносильны.

(x)(P(x))  (x)(Q(x)).

Подставим вместо предикатных переменных

P(x) и Q(x)
конкретные предикаты A(x) и B(x), определенные на
множестве N, где A(x) есть "x  четное", а B(x) есть
"x  нечетное". Тогда правая формула превращается в
истинное высказывание «существует четное натуральное
число и существует нечетное натуральное число». Левая
формула превратится в ложное высказывание «существует
натуральное число, которое четное и которое нечетное».

равносильных формул следует, что
F1 = F2

тогда и только тогда, когда формула F1 ↔ F2
есть тавтология. Поэтому из ранее полученных тавтологий
получаем:
1.
2.

3.
4.

6.
7.
8.

Формулы 5 8 имеют место, если формула Q не содержит x.
9. (x)(y)(P(x, у)) = (y)(x)(P(x, у)).
10. ( x)(y)(P(x, у)) = ( y)(x)(P(x, у)).

(x)(F(x)) = (y)(F(y)).
12. (x)(F(x)) = (y)(F(y)).
Отношение равносильности рефлексивно, симметрично

и
транзитивно, поэтому можно заменять одну равносильную
формулу другой. В процессе равносильных преобразований
можно использовать равносильности , известные из алгебры
высказываний.

формулы логики
предикатов называется такая равносильная ей

формула, в
которой из операций алгебры высказываний имеются только
операции ,  и отрицания −, причем знаки отрицания −
относятся лишь к предикатным переменным и высказываниям.

Теорема 1: для каждой формулы логики предикатов существует
приведенная форма.
Теорема доказывается методом полной математической
индукции по числу логических связок , с использованием
равносильностей 1−12, законов Моргана и замены операций
, ↔ операциями  и  .

форму для формулы:

Решение:

2. Найти равносильную приведенную форму для формулы: F(x,y) =

Решение: F(x,y) =
=
=

для формулы логики предикатов называется такая

ее
приведенная форма, в которой все кванторы стоят в начале,
а область действия каждого из них распространяется до
конца формулы.
ПНФ − это формула вида: (K1x1), …, (Kmxm)(F(x1, …, x1)), где
Ki есть один из кванторов  или  (i= 1,…m, m ≤ n), причем
формула F не содержит кванторов и является приведенной
формулой.
Пример:

каждой формулы логики предикатов

существует ПНФ.
Теорема доказывается методом полной математической
индукции по числу операций , , ,, , применяемых к
предикатным переменным. Если формула атомарна (состоит
из одного предиката), то она представляет предваренную
форму. Нужно научиться находить предваренные нормальные
формы для формул , (F1  F2), (F1  F2) ,
если известны предваренные нормальные формы F*, F1* и F2*
формул F, F1 и F2 соответственно.

построить ПНФ для всякой формулы
логики предикатов достаточно выполнить дейcтвия:

1. Заменить операции  и ↔ операциями , , ,
используя равносильные преобразования.
2. Используя равносильные преобразования, вынести кванторы из под операций отрицания.
3. Используя законы Моргана, отнести отрицания к предикатным переменным.
4. Используя равносильные преобразования, убрать
кванторы в начало формулы, применяя, в случае
необходимости, переименование переменных.

для формулы:

Решение:



2. Найти равносильную предваренную форму для формулы:
F(x) =

написать определение монотонно возрастающей функции на отрезке [a, b],

в виде формулы логики предикатов и его отрицание.
Функция f(x) называется монотонно возрастающей на отрезке [a, b], если для любых x, y из неравенства x < y следует , что f(x) f(y). На языке логики предикатов это запишется так (с помощью ПНФ):

Напишем отрицание этой формулы:


Осталось записать эту формулу в ПНФ.

логики предикатов называется
логическим следствием формул F1, F2 …

Fn если при всякой
интерпретации, при которой формулы F1, F2 … Fn
принимают значение истина, формула G также принимает
значение истина.

Этот факт обозначается: F1, F2, …, Fn |=G.

Формулы F1, F2 … Fn называют посылками, а формулу G −
заключением.

 i = 1, 2, …, n.
2. Если F1,

F2, …, Fn |= Gi, для i = 1, 2, …, t, и
если G1, G2, …, Gt |= H, то F1, F2, …, Fn |= H.
3. Если F1, F2, …, Fn |= G и G = H, то F1, F2, …, Fn |= H.
4. F1, F2, …, Fn |= G  F1  F2  … Fn  G является
общезначимой формулой.
5. F1, F2, …, Fn |= G,  F1, F2, …, Fn-1 |= Fn  G
(теорема дедукции).
Две формулы равносильны тогда и только тогда, когда
каждая из них является логическим следствием другой.