Интерпретация I исчисления предикатов K с областью интерпретацией M – это набор функций, который сопоставляет:
- каждой предметной константе a элемент I(a)ÎM;
- каждому n-местному функтору f операцию I(f):Mn®M.
- каждому n-местному предикату Р отношение I(P)Ì Mn.
Для нас имеют смысл только интерпретированные предикаты, т. е. те, которым поставлены в соответствие некоторые отношения (для одноместных предикатов – свойства).
Пример.
Рассмотрим 3 формулы.
1. P(x,y)
2.
3.
В качестве области интерпретации возьмем множество целых положительных чисел и интерпретируем P(x,y) как отношение .
Тогда формула 1 – это предикат. Он принимает значение истинно при любых a,b принадлежащих множеству целых положительных чисел, если .
Формула 2 – это предикат, который принимает значение истинно при x=1, т. е. он выражает свойство, что для каждого положительного целого числа y .
Формула 3 – это предикат, который всегда будет истинен. Он выражает свойство: существует положительное целое число y, для которого .
Формула называется истинной, если она выполняется на любом наборе элементов М.
Формула называется ложной, если она не выполняется на любом наборе элементов М.
Формула общезначима (тавтология), если она истинна в любой интерпретации.
Теорема: Любая выводимая в исчислении предикатов формула – общезначима.