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

Предикатом, или логической функцией называется функция от любого числа аргументов, принимающая истинност­ные значения: И (истинна - 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. “Ú” (дизъюнкция). Высказывание “ A v B ” читается “ А или В ”. Оно истинно, если истинно хотя бы одно из высказываний;

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).

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

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