Синтаксис: формулы логики предикатов

Формулы языка логики предикатов включают в себя символы (имена) предикатов из некоторого Множества , символы (имена) функций из некоторого множества , символы (имена) констант из некоторого множества C={ c₁, c₂, ... }, логические связки , кванторы всеобщности и существования и вспомогательные символы (скобки, запятые). Первые три множества образуют сигнатуру языка: . \index{Сигнатура} Зафиксируем некоторое счетное множество объектных переменных Var (такие переменные также называют предметными или индивидными ). Они предназначены для обозначения элементов множества (объектов), на котором определены функции ипредикаты ; обычно в таком качестве используют латинские буквы x, y,z,u,v,w, x_i, y_j, z_k и т.п. В каждой формуле будет использоваться конечное число переменных, так что счётного набора переменных нам хватит. Чтобы не возникла путаница, будем считать, что переменные отличны от всех имен констант, функций и предикатов.

Определим понятие терма данной сигнатуры

Определение 7.1. Терм. Термом называется выражение, состоящее из переменных, запятых, скобок и символов сигнатуры, которое можно построить по следующим правилам.

• Объектная переменная из Var есть терм.
• Символ константы из C есть терм.
• Если t₁,...,t_k - термы, а f^(k) - символ функции из F, то f(t₁,...,t_k) есть терм.

Термы, не содержащие переменных, назовем замкнутыми.

Термы служат для задания объектов. Замкнутые термы задают объекты непосредственно.

Пример 7.1. Пусть F={отец⁽¹⁾, лучший_друг⁽¹⁾, зарплата⁽¹⁾, + ⁽²⁾}, а C= {"Петр", "Джон", "Ольга", 0, 1, 2, ... }.

Тогда самый простой способ задать объект - это указать соответствующую константу, например,"Петр", "Джон", 0, 1, 47, .... Терм +(17, 25) задает объект 42, терм лучший_ друг(отец("Петр" ) ) задает объект - лицо, являющееся лучшим другом отца объекта "Петр", а терм зарплата(лучший_ друг(отец("Петр") ) ) задает объект-число, представляющее зарплату этого лица. Значениями переменных также являются объекты. Поэтому термы с переменными задают конкретные объекты при подстановке значений вместо переменых. Приведем еще несколько примеров термов данной сигнатуры:x, отец (x), зарплата(лучший_ друг(отец(отец(z)))), +(зарплата(лучший_ друг(отец(z)) ), +(зарплата ("Ольга" ), 1000)), отец(5), +(отец("Ольга" ), 1000)) . Отметим, что последние дватерма построены в соответствии с нашими правилами, но неясно, какие объекты они могут задавать. Это зависит от определения функции отец на числах и функции + на парах аргументов вида (Лицо, Число). Часто во множество объектов включают специальный объект "ОШИБКА", который является значением функций на некорректных аргументах.

Выражения x +10, отец ("Джон", "Петр"), +(100)}, лучший_друг("Мария") термами данной сигнатуры не являются. (Определите почему.)

Определение 7.2. Атомная формула.

• Если t₁ и t₂ - термы, то выражение (t₁ = t₂) является атомной формулой.
• Любой предикатный 0 -местный символ из P является атомной формулой.
• Если P^(k) (k >= 1) - предикатный k -местный символ из P, а t₁,...,t_k - термы, то выражениеP(t₁,...,t_k) является атомной формулой.

Пример 7.2. Рассмотрим сигнатуру , в которой P= { живут_рядом⁽²⁾, сын⁽²⁾, дочь⁽²⁾, родственники⁽²⁾, человек⁽¹⁾, число⁽¹⁾, <= ⁽²⁾}, а функции F и константы C определены в примере выше.

Тогда следующие выражения являются атомными формулами: "Джон" = "Петр", "Петр" = 6, отец("Ольга") = "Петр", +(3,5) = +(1, +(6,1)), зарплата(лучший_ друг(отец(z)) = 5000}, живут_рядом("Джон","Ольга"), сын( "Джон","Ольга"), дочь("Ольга", x), родственники(лучший_ друг("Джон"), отец( x)) и т.п.

Формулы логики предикатов строятся по таким правилам:

Определение 7.3. Формула.

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

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

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

Пусть в некоторой сигнатуре имеются два двуместных предиката P⁽²⁾, Q⁽²⁾. Тогда в формуле

оба вхождения x в подформулу связаны квантором , первое вхождение yявляется свободным, а второе - связано квантором . Оба вхождения x в подформулу связаны квантором .

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

Пример 7.3. Рассмотрим примеры формул в сигнатуре из примера 7.2:

1.

В этой формуле все вхождения переменных x и y являются связанными и, следовательно, - замкнутая формула. Содержательно, она утверждает, что у всякого человека имется человек-сосед. Понятно, что истинность этого утверждения не зависит от имен переменных, использованных в формуле.

2.

В формуле все вхождения переменной y являются связанными, первое вхождение x также связано, а второе вхождение x свободно, так как не входит в область действия квантора . Таким образом x в является связанной и свободной. Эта формула утверждает что имеется такой человек, который состоит в родственных отношениях со всеми или не живет рядом с x и имеет зарплату >= 35. Ясно, что истинность этой формулы зависит от значения свободной переменной x.