Пусть задано некоторое множество M = {m1, m2, …, mk, …}, в котором m1, m2, …, mk – какие-то определенные предметы из этого множества. Обозначим любой предмет из этого множества через х и назовем х предметной переменной. Тогда высказывания об этих предметах будем обозначать в виде P(m1), Q(m1, m2) и т. д., причем такие высказывания могут быть как истинными, так и ложными.
Предикат на множестве M есть логическая функция, определенная на M, при фиксировании аргументов которой она превращается в высказывание со значениями {T, F}.
В общем случае через P(x1, x2, …, xn) обозначим n-местный предикат, обладающий тем свойством, что, приписав значения переменным x1, x2, …, xn из соответствующих областей определения, получим высказывание со значениями {T, F}.
Важную роль в исчислении предикатов играют кванторы существования ($) и всеобщности ("). Для предиката Р(х) выражение "х Р(х) означает, что для всякого х из области определения предиката выражение Р(х) истинно. Выражение $х Р(х) означает, что существует х из области определения предиката, для которого выражение Р(х) истинно.
Таким образом, в исчислении предикатов используются:
1. Предметные переменные x1, x2, …, xn.
2. Предметные константы a, b, c, d, … .
3. Предикатные буквы A, B, C, D, … .
4. Функциональные буквы f, g, h, … .
5. Логические операторы Ø, É, Ù, Ú, Û.
6. Кванторы ", $.
Формулируются следующие правила построения термов:
1. Всякая предметная переменная или предметная константа есть терм.
2. Если f – функциональная буква и t1, t2, …, tn – термы, то f(t1, t2, …, tn) есть терм.
Формулируются следующие правила построения атомов (атомарных формул):
1. Всякое переменное высказывание есть атом.
2. Если А – предикатная буква, а t1, t2, …, tn – термы, то А(t1, t2, …, tn) есть атом.
Формулы исчисления высказываний конструируются по следующим правилам:
1. Всякий атом есть формула.
2. Если А и В – формулы и х – предметная переменная, то каждое из выражений ØА, А ÉВ, АÙВ, АÚВ, АÛВ, "хА, $хА есть формула.
Введем понятия свободного и связанного вхождения переменной в формулу. Вхождение переменной х в данную формулу называется связанным, если х является переменной входящего в эту формулу квантора ("х или $х) или находится в области действия входящего в эту формулу квантора; в противном случае вхождение переменной х в данную формулу называется свободным. Соответствующая переменная называется свободной или связанной.
В общем случае выражение "хi1"хi2 … "хir A(x1, x2, …, xn), где хi1, хi2,… хir являются подмножеством множества переменных x1, x2, …, xn, означает, что для любых значений, придаваемых переменным хi1, хi2,… хir из области определения A(x1, x2, …, xn), истинность A(x1, x2, …, xn) зависит только от свободных переменных, входящих в эту формулу. Аналогичное утверждение справедливо для квантора существования.
Если к формуле A(x1, x2, …, xn) применить n раз какие-либо кванторы, то получится выражение z1х1z2х2 … znхn A(x1, x2, …, xn), где zI Î{", $}, представляющее собой некоторое постоянное высказывание, которое называется замкнутой формулой, т. е. формулой без свободных переменных.
Формулы исчисления предикатов имеют смысл только тогда, когда имеется какая-нибудь интерпретация входящих в нее символов. Под интерпретацией I в исчислении предикатов понимается всякая система, состоящая из непустого множества M, называемого областью интерпретации, и какого-либо соответствия, относящего каждой предикатной букве Аi некоторое n-местное отношение в M (т. е. Mn®{T,F}), каждой функциональной букве fi – некоторую n-местную функцию в M (т. е. Mn®M) и каждой предметной константе аi – некоторый элемент из M.
Интерпретация формулы исчисления предикатов – отношение, которое каждой предикатной букве ставит в соотвествие значение истины, либо ложь.
Областью истинности J предиката называется подмножество M, на котором предикат принимает значение «истина» (Т).
При заданной интерпретации предметные переменные пробегают значения из M, а логическим связкам и кванторам придается их обычный смысл (см. п. 6.1.1).
Для данной интерпретации любая формула без свободных переменных представляет собой высказывание, которое может быть истинным или ложным, а всякая формула со свободными переменными выражает некоторое отношение на области интерпретации, причем это отношение может быть истинным для одних значений переменных из области интерпретации и ложным для других.
Для выяснения факта, истинна или ложна формула в данной интерпретации I, необходимо, задав область интерпретации, интерпретировать прежде всего все термы, входящие в формулу, затем атомы и, наконец, саму формулу. Если область интерпретации конечна, то можно выяснить истинность или ложность любой формулы, перебрав все различные элементы множества Mn, где n – число различных переменных, входящих в формулу. Однако на практике М часто настолько велико или бесконечно, что необходим логический вывод.