Определение: Две формулы F 1 и F 2 логики предикатов называются равносильными на множестве M, если при любой подстановке в эти формулы вместо предикатных переменных любых конкретных предикатов, определенных на M, эти формулы превращаются в равносильные предикаты ( F 1 + = F 2 + ). Если формулы F 1 и F 2 равносильны на любых множествах, то они называются просто равносильными ( F 1 = F 2). В частности, все ТИ формулы (тавтологии) равносильны, и все ТЛ формулы равносильны.
Формулы ( x)(P(x) Q(x)) ≠ ( 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.
5. 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, у)).
Равносильности, связанные с заменой переменных : 1 1. ( x)( F (x)) = ( y )( F ( y )). 1 2. ( x)( F (x)) = ( y )( F ( y )). Отношение равносильности рефлексивно, симметрично и транзитивно, поэтому можно заменять одну равносильную формулу другой. В процессе равносильных преобразований можно использовать равносильности, известные из алгебры высказываний.
Определение. Приведенной формой для формулы логики предикатов называется такая равносильная ей формула, в которой из операций алгебры высказываний имеются только операции , и отрицания −, причем знаки отрицания − относятся лишь к предикатным переменным и высказываниям. Теорема 1 : для каждой формулы логики предикатов существует приведенная форма. Теорема доказывается методом полной математической индукции по числу логических связок, с использованием равносильностей 1 − 12, законов Моргана и замены операций , ↔ операциями и .
1. Найти равносильную приведенную форму для формулы : Решение : 2. Найти равносильную приведенную форму для формулы : F(x,y) = Решение : F(x,y) = = =
Определение. Предваренной нормальной формой для формулы логики предикатов называется такая ее приведенная форма, в которой все кванторы стоят в начале, а область действия каждого из них распространяется до конца формулы. ПНФ − это формула вида : ( K 1 x 1 ), …, ( K m x m )(F(x 1, …, x 1 )), где K i есть один из кванторов или ( i= 1,…m, m ≤ n), причем формула F не содержит кванторов и является приведенной формулой. Пример :
Теорема 2. Для каждой формулы логики предикатов существует ПНФ. Теорема доказывается методом полной математической индукции по числу операций , , ,, , применяемых к предикатным переменным. Если формула атомарна (состоит из одного предиката), то она представляет предваренную форму. Нужно научиться находить предваренные нормальные формы для формул, (F 1 F 2 ), (F 1 F 2 ), если известны предваренные нормальные формы F*, F 1 * и F 2 * формул F, F 1 и F 2 соответственно.
Для того, чтобы построить ПНФ для всякой формулы логики предикатов достаточно выполнить дей c твия : 1. Заменить операции и ↔ операциями , , , используя равносильные преобразования. 2. Используя равносильные преобразования, вынести кванторы из под операций отрицания. 3. Используя законы Моргана, отнести отрицания к предикатным переменным. 4. Используя равносильные преобразования, убрать кванторы в начало формулы, применяя, в случае необходимости, переименование переменных.
1. Найти равносильную предваренную форму для формулы : Решение : 2. Найти равносильную предваренную форму для формулы : F(x) =
3. Найти равносильную предваренную форму для формулы :
Задача : написать определение монотонно возрастающей функции на отрезке [a, b], в виде формулы логики предикатов и его отрицание. Функция f(x) называется м онотонно возрастающей на отрезке [a, b], если для любых x, y из неравенства x < y следует, что f(x) f(y). На языке логики предикатов это запишется так ( с помощью ПНФ) : Напишем отрицание этой формулы : Осталось записать эту формулу в ПНФ.
Определение. Формула G логики предикатов называется логическим следствием формул F 1, F 2 … F n если при всякой интерпретации, при которой формулы F 1, F 2 … F n принимают значение истина, формула G также принимает значение истина. Этот факт обозначается : F 1, F 2, …, F n |=G. Формулы F 1, F 2 … F n называют посылками, а формулу G − заключением.
1. F 1, F 2, …, F n | = F i, i = 1, 2, …, n. 2. Если F 1, F 2, …, F n |= G i, для i = 1, 2, …, t, и если G 1, G 2, …, G t |= H, то F 1, F 2, …, F n |= H. 3. Если F 1, F 2, …, F n |= G и G = H, то F 1, F 2, …, Fn |= H. 4. F 1, F 2, …, F n |= G F 1 F 2 … F n G является общезначимой формулой. 5. F 1, F 2, …, F n |= G, F 1, F 2, …, F n -1 |= F n G ( теорема дедукции ). Две формулы равносильны тогда и только тогда, когда каждая из них является логическим следствием другой.
