Предикатная формула (формула логики предикатов) – формула, содержащая знаки булевых операций и кванторов.
Более точно, в формулах участвуют:
· символы предметных переменных X, Y, Z…;
· символы предикатов;
· логические символы ¬, &, , →, ~;
· символы кванторов и .
Предикатной формулой (одновременно определяются понятия свободных и связанных переменных) называется выражение, построенное по следующим правилам.
1) Если P – символ предиката, X1, X2,…,Xt – символы переменных (не обязательно различных), то P(X1, X2,…,Xt) – предикатная формула; все её переменные свободные.
2) Если А – формула, то ¬А – тоже формула с теми же свободными и связанными переменными.
3) Если А, В – формулы и нет переменных, свободных в одной из них и связанных в другой, то А&В, А В, А→В, А ~В – тоже формулы с теми же свободными и связанными переменными.
4) Если А – формула, содержащая свободную переменную Х (и, быть может, другие переменные – свободные и связанные), то выражения : А(Х)и : А(Х) – предикатные формулы; в каждой из них переменная Х переходит из множества свободных в множество связанных, т. е. число свободных переменных уменьшается, а число связанных увеличивается на 1. При этом формула А называется областью действия квантора.
В формуле должны быть правильным образом расставлены скобки, определяющие области действия кванторов и порядок выполнения логических и кванторных операций. Однако для сокращения записи могут быть удалены излишние скобки (считается, что знак квантора связывает сильнее, чем знак логической операции), также можно записывать кванторные формулы без знака “:”.
Пример 9.11.
Пусть Р(Х,Y) = Х ≤ Y для действительных чисел Х, Y R.
Это двухместный предикат с предметной областью на числовой плоскости. Область истинности – полуплоскость, ограниченная биссектрисой I и III координатных углов, включающая точки границы (на рис. показано серым цветом).
Формулы Р(Х,Y) и Р(Х,Y) – одноместные предикаты со свободными переменными Y и, соответственно, Х. Область истинности – пустое множество, т.к. не существует ни наибольшего, ни наименьшего среди действительных чисел.
Предикат Р(Х,Y) – одноместный со свободной переменной Y. Его область истинности – вся числовая ось, т. к. какое бы ни было Y, существует меньшее число Х.
Рассмотрим тот же предикат Р(Х,Y) = Х ≤ Y на предметной области натуральных чисел: Х, YN = . Область истинности предиката – целочисленные точки I координатного угла (включая точки оси координат), расположенные над биссектрисой и на ней (на рис. показано выделенными точками).
Область истинности для предиката Р(Х,Y) – пустое множество, а для : Р(Х,Y) область истинности состоит из одного числа 0. Отсюда можно заключить, что предикат есть истинное высказывание (обе переменных связанные), поскольку существует наименьшее натуральное число 0.
Формулы называются эквивалентными, если при любых подстановках констант они принимают одинаковые значения. В частности, все ТИ-формулы и ТЛ-формулы – эквивалентны.
Пример 9.12.
Если Р(Х,Y) = Х >Y , Q(X,Y) = X ≤ Y, то (Х,Y) и Q (X,Y) – равносильные формулы; при других интерпретациях P и Q эти формулы могут не быть равносильными.
Пример 9.13.
Х Р(Х) и Х Р(Х) равносильны на одноэлементном множестве М: если существует подходящий Х, то, поскольку других значений нет, истинно и второе суждение. На множестве, содержащем более одного элемента, это уже не так.
Целью логики предикатов является исследование множества ТИ-формул, входящих в любую теорию. При этом выделяются две проблемы:
2) проверка формулы на истинность (проблема разрешающей процедуры).
В логике предикатов используются различные приёмы, в том числе эквивалентные соотношения, позволяющие выполнять корректные преобразования предикатных формул. В логике (алгебре) предикатов справедливы все эквивалентные соотношения алгебры высказываний, а так же собственные эквивалентные соотношения, включающие связки .
1. Перенос квантора через отрицание (законы де Моргана для предикатов):
¬ x A(x) ≡ x ¬A(x);
¬ x A(x) ≡ x ¬A(x).
2. Вынесение квантора за скобки
Если формула А(Х) содержит свободную переменную Х, а формула В не содержит Х и в них нет переменных, свободных в одной из формул и связанных в другой, то:
Х (А(x) & В) ≡ ( x А(x)) & В;
Х (А(x) & В) ≡ ( x А (x)) & В;
Х (А(x) В) ≡ ( x А(x)) В;
Х (А(x) В) ≡ ( x А (x)) В.
3. Законы коммутативности для одноименных кванторов:
x( y A (x,y)) ≡ y( x А(x,y));
x ( y А (x, y)) ≡ y ( x А (x,y)).
Коммутативность дает возможность использовать более короткую запись:
Х, Y, Z : P(X,Y,Z) или Х,Y : Q(X,Y,Z) и т. п.
4. Законы дистрибутивности кванторов:
X : (P(X)&Q(X)) ≡ X : P(X) & X : Q(X)
X : (P(X) Q(X)) ≡ X : P(X) X : Q(X)
Предикатная формула находится в приведённой форме, если в ней используются операции квантефикации, отрицания, конъюнкции, дизъюнкции, причём отрицание относится лишь к предикатным буквам.
Пример 9.14.
Представить в приведённой форме предикат .
Решение.
Воспользуемся формулой замены операции импликации: .
.
Воспользуемся теоремами об отрицании кванторов. Получим:
. Так как кроме кванторов , символов конъюнкции, дизъюнкции и отрицания в формуле не используются другие символы предикатных операций, а отрицание относится только к предикатным буквам, то приведённая форма получена.
