Синтаксис языка предикатов первого порядка

Предикатом, или логической функцией называется функция от любого числа аргументов, принимающая истинност­ные значения: И (истинна - 1) и Л (ложь — 0). Аргументы принимают значения из произвольного, конечного или бесконечного множества D, называемого предметной областью. Предикат от n аргументов называют n - местным предикатом.

Предикат F(x), определенный на предметной области D, за­дает определенное свойство элементам множества D и интерпретируется как высказывание «х обладает свойством F», причем F принимает значение И, если это высказывание истинно, и значение Л, если оно ложно. Предикат F(x₁, x₂,,.., x_N) задает отношение между элементами x₁, x₂,,.., x_N и интерпретируется как высказывание «x₁, x₂,,.., x_N находятся между собой в отношении F». Пусть, например, D — множество натуральных чисел. Тогда предикат F(x) может обозначать, что «х - четное число» или «х - нечетное число», а предикат G(х,у) – «х больше у» или «х делится на у» и т.д.

Алфавит языка предикатов первого порядка включает множество следующих символов:

· разделители: запятая, открывавшая и закрывающая скобка:

· константы, обозначаемые строчными буквами или соедине­нием таких букв, например: “а”, ”друг”;

· переменные, обозначаемые прописными буквами например “Х”, “АДРЕС” ;

· предикаты, обозначаемые прописными буквами, например: Р, Q, БОЛЬШЕ ;

· функции, устанавливающие зависимость и отображающие значения одной предметной области в значения другой (или той же), n-местные функции могут служить аргументами предиката. Функции будем обозначать строчными буквами: f, g.

· логические операции:

1. “ ù ” (отрицание или дополнение). Высказывание “ ùА” читается “не А”. Оно истинно (И), если высказывание А - лож­но (Л);

2. “/\” (конъюнкция). Высказывание “АÙВ” читается “А и В”. Оно истинно в том случае, когда истинно как А так и В;

3. “Ú” (дизъюнкция). Высказывание “AvB” читается “А или В”. Оно истинно, если истинно хотя бы одно из высказываний;

4. “®” (импликация). Высказывание “А®B” читается “если А, то В”. Оно ложно в том и только в том случае, если А истинно, а В ложно;

5. “«“ (эквивалентность). Высказывание “А«В” читается “А тогда и только тогда, когда В”. Оно истинно тогда и толь­ко тогда, когда А и В имеют одно и то же истинностное значение;

· кванторы:

6. “$” (квантор существования). Высказывание $А читается “существует А”.

7. “"” (квантор общности). Высказывание "А читается “для любого А”.

Пропозициональной формойилиформулой алгебры логики называют всякое высказывание, составленное из некоторых исходных высказываний посредством логических операций. Дру­гими словами, если F и G — пропозициональные формы, то ùF, (FÚG), (FÙS), (F®G) и (F«G) — пропозициональные формы.

Определение формулы — основного объекта в логике преди­катов включает понятие “терм”.

Терм— выражение, включающее константы, переменные или n‑местные функции f(t₁,..., t_N), где t₁,..., t_N - термы. Нап­ример, f(X,Y), вес(b), f(b, вес(Z)) — термы. Выражения Р(Х, голубой) и вес(Р(b)) не являются термами, так как Р - преди­кат, а не терм.

Атом илиэлементарная (атомная) формула - это выражение, включающее константы, переменные, функции и предикаты. Таким образом, если Р — n-местный предикат, а t₁,..., t_N — термы, то P(t₁,..., t_N) — атом. Например, выражения Р(Х, голубой), ABC, ВХОД(стол, Х, под(окно)) являются атомами, но не f(X,Y) или под(окно).

Формулаилиправильно построенная формула (ППФ)определяется следующим образом :

всякий атом есть ППФ;

если G и H — ППФ, а X — переменная, тогда (ùН), (GÚН), (GÙH), ($X)G, ("X)Н — ППФ.

Примерами ППФ являются:

P(a,X,f(Y,a,b)), G(X,Y)®F(a,b), (P(a)®(G(b)/\ ùF(a))).

Выражение “первого порядка” во фразе “исчисление предикатов первого порядка” связано с определением ППФ, в которых запрещается квантифицировать символы предикатов и функций. Например, ("Р)Р(а) и ("f)("X)P(f(X),b) не являются ППФ логики предикатов первого порядка.

На практике ППФ используется для представления знаний. Например, ППФ ("X)(M(X)®F(X)) может выражать, что “все матери есть женщины”, условившись, что М(Х) означает:

“Х - есть мать” и что F(X) - “Х - есть женщина”,

Не всегда легко представить знания, выраженные на естественном языке, с помощью ППФ. Например, выражение “если два объекта равны, то они имеют одинаковые свойства” можно представить так:

"P"X"Y(PABHO(X,Y)®(P(X)«P(Y))).

Но это выражение не является формулой первого порядка, так как квантифицируется предикат.

Правилом вывода называют процедуру, которая из одной или нескольких ППФ производит другие ППФ. Например, правило вывода: G и (G®H) производит одну ППФ Н; из ППФ ("Х)G(Х) и любой константы “а” получают ППФ G(а), т.е. все значения X в G заменяются на “а”; из двух ППФ (ùН) и (G®Н) производит ППФ (ùG).

Задавая фиксированное множество правил вывода можно рассматривать следующее семейство проблем: исходя из выбран­ного множества ППФ применением некоторого числа раз правил вывода можно получить заранее заданную ППФ.

Исходные ППФ называют аксиомами, а ППФ, полученные из правил вывода, называют теоремами. Цель применения правил вывода, ведущих от аксиом к теореме, называют доказательством теоремы.