Основы логики предикатов первого порядка

Логика – наука о формах, методах и законах интеллектуальной познавательной деятельности, формализуемых с помощью логического языка. Описания предметных областей, выполненные с помощью логических языков, называются логическими (формальными) моделями [2]. Основная идея подхода при построении логических моделей состоит в том, что вся информация, необходимая для решения прикладных задач, рассматривается как совокупность фактов (аксиом) и утверждений, которые представляются как формулы в некоторой логике. Знания отображаются совокупностью таких формул, а получение новых знаний сводится к реализации процедур логического вывода.

Логика предикатов первого порядка является дальнейшим развитием традиционной логики Аристотеля и логики высказываний. Одним из ключевых понятий логики высказываний является непосредственно высказывание – выражение, записанное с помощью определенного синтаксиса, которому можно приписать истинностное значение (истина или ложь). Например, выражения «В сутках 24 часа» или «Инопланетяне существуют» являются высказываниями, так как могут быть истинными или ложными (в зависимости от принятой объективной или субъективной точки зрения). При этом само выражение в логике высказываний представляется неделимым целым, т.е. его нельзя разделить на отдельные компоненты и соответственно использовать сведения об его структуре.

Логика предикатов позволяет расчленить высказывание, представленное в виде предиката, на предикатный символ[1] (выражение, означающее свойство сущности или тип отношения между сущностями) и терм/термы (выражение/выражения, означающие значение свойства сущности или связываемые отношением сущности). Непосредственным аналогом предиката в программировании является логическая (булева) функция, где имя функции – предикатный символ, а ее аргументы – термы. Например, в предикате (логической функции) «простое_число(X)»: «простое_число» – предикатный символ (имя функции), а «X» – терм (аргумент функции). При одних значениях X (например, 13 или 17) это высказывание истинно, при других (например, 10 или 18) – ложно.

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

Для элементов языка логики предикатов используется следующий синтаксис:

· логическая константа – true (истина) и false (ложь);

· константа – символьное выражение, начинающееся со строчной буквы (например, cat, blue);

· переменная – символьное выражение, начинающееся с прописной буквы или знака подчеркивания (например, X, Сat, _blue);

· функция и предикат – символьное выражение, начинающееся со строчной буквы, за которым следует список аргументов (термов), заключенных в скобки (например, кошка(катя), sin(X), друзья(вася, петя));

· список – упорядоченный набор элементов (константы, переменные или предикаты), указанных через запятую и заключенных в квадратные скобки (например, [red, blue], [X, Сat, _blue], [кошка(катя)]);

· терм – константа, переменная, функция или список;

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

o Ø – отрицание;

o Ù – логическое И (конъюнкция, логическое умножение);

o Ú – логическое ИЛИ (дизъюнкция, логическое сложение);

o ® (Þ) – импликация (если - то);

o « (º) – эквивалентность;

· квантор переменной – логический оператор, с помощью которого высказывание о какой-либо сущности преобразуется в высказывание о совокупности (множестве) таких сущностей:

o $ – квантор существования;

o " – квантор всеобщности;

· вспомогательный символ – круглые скобки, запятая, +, - и т. п.;

· формула (предложение, правило, правильно построенная формула) – предикат, логическое выражение или одна из следующих конструкций: ØА, AÙB, AÚB, A®B, A«B, ("X) A и ($X) А, где A и B – формулы,
а X – переменная. Результатом вычисления формулы является либо истина, либо ложь.

Приоритет операций и кванторов при исчислении формул показан ниже.

В скобках показаны операции (кванторы) с одинаковым приоритетом. Если в формуле используются операции (кванторы) с одинаковым приоритетом, то порядок исчисления слева-направо. Изменение порядка исчисления можно добиться за счет использования круглых скобок.

Примеры формул:

· если Маша мать X и Y, то X является братом или сестрой Y:

мать(маша, X) Ù мать(маша, Y) ® брат(X, Y) Ú сестра(X, Y).

· если X – человек, то он смертен:

человек(X) ® смертен(Х).

Квантор существования $ указывает, что предложение истинно, по крайней мере, для одного значения переменной. Например, $X друзья(X, петя) – существует, по крайней мере, один субъект X, который является другом Пети.

Квантор всеобщности " указывает, что предложение истинно для всех значений переменной. Например, "X человек(X) ® смертен(Х) – все люди смертны.

При комбинации кванторов важен порядок их использования. Например, для предиката любит(Х, Y), означающего, что X любит Y (обратное необязательно):

· "X$Y любит(Х, Y) – любой Х любит хотя бы одного Y;

· "Y$X любит(Х, Y) – любого Y любит хотя бы один Х;

· $X"Y любит(Х, Y) – существует такой Х, который любит всех;

· $Y"X любит(Х, Y) – существует такой Y, которого любят все;

· "X"Y любит(Х, Y) и "Y"Х любит(Х, Y) – любой X любит всех Y и любой Y любим всеми X (эквивалентные предложения);

· $X$Y любит(Х, Y) – существует такой X, который любит хотя бы одного Y;

· $Y$Х любит(Х, Y) – существует такой Y, которого любит хотя бы один X.

Основы Пролога

Наиболее известным языком логического программирования, реализующим модифицированную логику предикатов первого порядка, является Пролог (Prolog – PROgramming LOGig, логическое программирование). В нем отсутствует возможность использования кванторов, а составные формулы записываются в виде фраз Хорна.

Программа на Прологе состоит из предложений (формул), каждое из которых должно заканчиваться точкой. В общем случае предложение имеет вид:

B :- A₁, ... , A_n.

B – заголовок или голова предложения, A₁, ..., A_n – тело. В предложении ключевой логической операцией является перевернутая импликация
(B :- A эквивалентно B A). Символ «:-» означает «следует из», символ «,» – конъюнкция (логическое И, Ù).

При необходимости применения дизъюнкции (логическое ИЛИ, Ú) используется символ «;», действующий до следующей дизъюнкции, окончания правила или закрывающей круглой скобки.

Таблица 1