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

Пусть задано некоторое множество M = {m₁, m₂, …, m_k, …}, в котором m₁, m₂, …, m_k – какие-то определенные предметы из этого множества. Обозначим любой предмет из этого множества через х и назовем х предметной переменной. Тогда высказывания об этих предметах будем обозначать в виде P(m₁), Q(m₁, m₂) и т. д., причем такие высказывания могут быть как истинными, так и ложными.

Предикат на множестве M есть логическая функция, определенная на M, при фиксировании аргументов которой она превращается в высказывание со значениями {T, F}.

В общем случае через P(x₁, x₂, …, x_n) обозначим n-местный предикат, обладающий тем свойством, что, приписав значения переменным x₁, x₂, …, x_n из соответствующих областей определения, получим высказывание со значениями {T, F}.

Важную роль в исчислении предикатов играют кванторы существования () и всеобщности (). Для предиката Р(х) выражение х Р(х) означает, что для всякого х из области определения предиката выражение Р(х) истинно. Выражение х Р(х) означает, что существует х из области определения предиката, для которого выражение Р(х) истинно.

Таким образом, в исчислении предикатов используются:

1. Предметные переменные x₁, x₂, …, x_n.

2. Предметные константы a, b, c, d, … .

3. Предикатные буквы A, B, C, D, … .

4. Функциональные буквы f, g, h, … .

5. Логические операторы , , , , .

6. Кванторы , .

Формулируются следующие правила построения термов:

1. Всякая предметная переменная или предметная константа есть терм.

2. Если f – функциональная буква и t₁, t₂, …, t_n – термы, то f(t₁, t₂, …, t_n) есть терм.

Формулируются следующие правила построения атомов (атомарных формул):

1. Всякое переменное высказывание есть атом.

2. Если А – предикатная буква, а t₁, t₂, …, t_n – термы, то А(t₁, t₂, …, t_n) есть атом.

Формулы исчисления высказываний конструируются по следующим правилам:

1. Всякий атом есть формула.

2. Если А и В – формулы и х – предметная переменная, то каждое из выражений А, А В, АВ, АВ, АВ, хА, хА есть формула.

Введем понятия свободного и связанного вхождения переменной в формулу. Вхождение переменной х в данную формулу называется связанным, если х является переменной входящего в эту формулу квантора (х или х) или находится в области действия входящего в эту формулу квантора; в противном случае вхождение переменной х в данную формулу называется свободным. Соответствующая переменная называется свободной или связанной.

В общем случае выражение х_i1х_i2 … х_ir A(x₁, x₂, …, x_n), где х_i1, х_i2,… х_ir являются подмножеством множества переменных x₁, x₂, …, x_n, означает, что для любых значений, придаваемых переменным х_i1, х_i2,… х_ir из области определения A(x₁, x₂, …, x_n), истинность A(x₁, x₂, …, x_n) зависит только от свободных переменных, входящих в эту формулу. Аналогичное утверждение справедливо для квантора существования.

Если к формуле A(x₁, x₂, …, x_n) применить n раз какие-либо кванторы, то получится выражение ₁х₁₂х₂ … _nх_n A(x₁, x₂, …, x_n), где _I {, }, представляющее собой некоторое постоянное высказывание, которое называется замкнутой формулой, т. е. формулой без свободных переменных.

Формулы исчисления предикатов имеют смысл только тогда, когда имеется какая-нибудь интерпретация входящих в нее символов. Под интерпретацией I в исчислении предикатов понимается всякая система, состоящая из непустого множества M, называемого областью интерпретации, и какого-либо соответствия, относящего каждой предикатной букве А_i некоторое n-местное отношение в M (т. е. Mⁿ{T,F}), каждой функциональной букве f_i – некоторую n-местную функцию в M (т. е. MⁿM) и каждой предметной константе а_i – некоторый элемент из M.

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

Областью истинности J предиката называется подмножество M, на котором предикат принимает значение «истина» (Т).

При заданной интерпретации предметные переменные пробегают значения из M, а логическим связкам и кванторам придается их обычный смысл (см. п. 6.1.1).

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

Для выяснения факта, истинна или ложна формула в данной интерпретации I, необходимо, задав область интерпретации, интерпретировать прежде всего все термы, входящие в формулу, затем атомы и, наконец, саму формулу. Если область интерпретации конечна, то можно выяснить истинность или ложность любой формулы, перебрав все различные элементы множества Mⁿ, где n – число различных переменных, входящих в формулу. Однако на практике М часто настолько велико или бесконечно, что необходим логический вывод.