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

Каждая формула ИП представляет собой некоторую конечную последовательность символов этого исчисления. Опишем символы исчисления предикатов.

1) Малые латинские буквы с индексами или без них:

Эти символы носят название переменных предметов.

2) Большие латинские буквы с индексами внизу или без них:

называются переменными высказываниями.

3) Большие латинские буквы с индексами вверху:

и эти же символы с индексами внизу:

Эти символы носят название переменных предикатов от переменных ( ) .

4) Символы ИВ:

5) Скобки

( ).

6) Символы

и .

Определение формул

В принципе, каждая формула является словом в алфавите, содержащем все указанные выше символы. Мы должны определить, какие слова называются формулами.

1. Каждое переменное высказывание есть формула .

2. Если — символ переменного предиката, - символы предметных переменных, не обязательно различных, то слово есть формула. За такими формулами мы сохраним название переменного предиката.

Формулы, определенные в 1 и 2, мы будем называть элементарными формулами. В элементарных формулах все предметные переменные являются свободными.

3 . Пусть формула содержит свободную переменную . Тогда слова

_, (1)

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

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

( & ), ( ), ( ), , (2)

являются формулами. При этом свободные переменные в формулах и остаются свободными во всех формулах (2), а связанные переменные в формулах и остаются связанными в формулах (2).

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

Из 1 - 4 видно, что все формулы ИВ являются также формулами ИП .

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

1. . Это слово является формулой.

2. . Это слово является формулой.

3. . Это слово не является формулой согласно п.4.

В записи формул внесем некоторые изменения:

1) опускаются внешние скобки;

2) опускаются скобки по правилу: & связывает сильнее, чем и , а связывает сильнее, чем :

_;

3) для облегчения чтения длинных формул заменим круглые cкобки на прямые: ;

4) знак отрицания будем ставить над формулой, то есть вместо будем писать ;

5) в записи предиката опускаем верхний индекс , а знак отрицания, относящийся к предикату, будем ставить над символом предиката, например: .

Примеры.

1. Формула сокращенно может быть записана в виде: .

2. Формула запишется в виде .

3. Формула запишется так: .

Пусть формула имеет вид или . Тогда областью действия квантора (cоответственно ) называется формула .

Итак, для того чтобы слово из символов ИП было формулой, необходимо, чтобы соблюдались свойства:

а) в формуле свободные и связанные переменные обозначены разными буквами;

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

Нарушение этих условий мы будем называть коллизией переменных.

Пример. - это слово не является формулой согласно п.б). Но слово является формулой, так как мы не требовали, чтобы при составлении формул ( & ), ( ), ( ) из и переменные, связанные различными кванторами в формулах и , были различными.