Язык предикатов

Теоретические исследования математических моделей вычислений играют важную роль в формировании технологии использования компьютерной техники. Каждая такая модель вносит свой вклад в реальную технологию. Развитие технологии в обход теоретических исследований часто приводит к неуклюжим, трудным для восприятия и, в конечном счете, малопроизводительным видам деятельности.

Исследования универсальных методов доказательства в рамках логики предикатов дают повод для разработки на их основе новых языков программирования. Опыты, проведенные в 70-х годах прошлого века, показали перспективность использования этих методов в реальных технологиях автоматической переработки информации.

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

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

"Строительные материалы", из которых конструируются формулы и предложения языка предикатов:

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

Замечания

Предикатные символы используются для обозначения предложений, в которых некоторые слова заменены переменными, так что при замене переменных именами конкретных объектов получаются высказывания об этих объектах, которые можно оценить при определенных обстоятельствах как истинные или ложные. Каждое такое предложение называется высказывательной формой, а количество различных переменных, входящих в такое предложение, — ее арностью или местностью. Например, предложение "Река

является притоком реки " — двухместная форма, которая при замене переменной на собственное имя "Волга" превращается в одноместную форму. "Река является притоком реки Волга". А если еще и переменную

заменить именем "Ока", то получим истинное высказывание. Если же переменную заменить именем "Енисей", то — ложное.
При имеем дело с конкретным высказыванием.
Функциональные символы используются для обозначения отображений (функций).
Нульместные функции называются также константами.

Основными конструкциями языка предикатов являются термы и формулы.

Правила образования термов

Любая переменная или константа является термом.
Если — функциональный -местный символ, а — термы, то выражение

является термом.

Замечания

Многоточие, используемое в определении терма, не следует понимать буквально, поскольку таких символов в нашем распоряжении нет. При любом конкретном значении мы обходимся без многоточий.
Если в терме нет переменных, то он интерпретируется как имя некоторого объекта, если же переменные есть, то терм удобно рассматривать как схему для образования имени. Например, — терм, который при замене переменной константой превращается в терм , являющийся именем вполне конкретного числа, хотя и нетрадиционным. Под выражением мы понимаем здесь функциональный символ, хотя и состоящий из трех латинских букв.
В термах, построенных с помощью функциональных двухместных символов, традиционно используется инфиксная форма записи, при которой знак функции помещается между аргументами, например пишется вместо .Аналогичное замечание справедливо и для двухместных предикатов.

Аналогичное замечание справедливо и для двухместных предикатов.

Правила образования формул

Если — -местный предикатный символ, а — термы, то выражение является формулой (атомарной).
Если и — формулы, то выражения , , и являются формулами.
Если — формула, а — переменная, то выражения , являются формулами.

Замечания

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

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

Пример.

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

Рассмотрим следующую интерпретацию нашей сигнатуры. Пусть универсумом рассуждения будет множество точек плоскости, это означает, что значениями переменных являются точки. Далее, пусть

— точка, являющаяся серединой отрезка ,
— точка, симметричная точке

относительно некоторой точки,
— предикат, означающий равенство точек и .

При такой интерпретации нелогических символов , приведенная выше формула есть утверждение о том, что середина отрезка симметрична середине отрезка с концами, симметричными точкам .

Очевидно, что это утверждение истинно.

Рис. 14.1.

Рассмотрим еще одну интерпретацию нашей сигнатуры. Пусть на этот раз универсумом рассуждения будет множество действительных чисел, исключая число :

— произведение чисел ,
— число, обратное числу ,
— "".

Рассматриваемая нами формула является теперь утверждением о том, что для любых двух чисел из нашего универсума выполняется равенство

Очевидно, что это утверждение истинно. Нетрудно привести примеры интерпретаций, при которых наша формула ложна. Следующие примеры показывают, что существуют формулы, тождественно истинные, то есть истинные при любой интерпретации, а также тождественно ложные.

Примеры. Пусть и — одноместные предикатные символы.

— тождественно истинная формула.
— тождественно ложная формула.
— истинность этой формулы зависит от интерпретации предикатных символов и .

Если в формуле есть свободные переменные, то она получает конкретное истинностное значение при означивании этих переменных.

Формула называется выполнимой, если она истинна хотя бы при одной интерпретации.

Две формулы называются логически равносильными, если при любой интерпретации предикатных и функциональных символов и при любом означивании свободных переменных они имеют одно и то же истинностное значение.

Например, формулы

не являются логически равносильными, а формулы

логически равносильны.

Логическую равносильность формул будем обозначать знаком , например,

Заметим, что в этом выражении фигурирует не одна формула, а две, соединенные знаком логической равносильности.

Содержание раздела