Замечание. Говоря в последующем о термах и формулах, будем опускать добавление “сигнатуры S“, если ясно о какой сигнатуре идет речь.
Каждая совокупность формул, в свою очередь, определяет собственную сигнатуру: ее предикатная часть состоит из всех символов предикатов этих формул, а функциональная - из совокупности функциональных символов, с указанием местности этих символов. Поэтому в последующем иногда будем говорить о предикатной (функциональной) сигнатуре формул. Очевидно, что конечное множество формул определяет конечную сигнатуру.
Если A есть произвольная формула, то запись A(x1, x2, ..., xn) обозначает, что формула A содержит множество{x1, x2, ..., xn} предметных переменных, которые в ней не связаны кванторами. Это так называемые свободные переменные, названные так, чтобы отличать их от связанных, т.е. таких, которые находятся под управлением кванторов.
Запись A(t1, t2, ..., tn) обозначает, что на некоторых аргументных местах формулы встречаются термы t1, t2, ..., tn. Тем самым выделяется ряд аргументов, которые по каким-либо причинам представляют интерес. Не обязательно, чтобы в эту формулу входили все перечисленные термы t1, t2, ..., tn, некоторые из них могут входить фиктивно. Кроме того, среди этих термов могут быть и совпадающие.
Пример. В формуле А(х, х, t) выделены два множества аргументных мест, на которых располагается свободно переменная х, и некоторая совокупность мест, где расположен терм t. При этом переменная х может располагаться и на некоторых аргументных местах формулы А помимо выделенных. Может быть и так, что такая переменная вовсе отсутствует в этой формуле, т.е. входит в нее фиктивно. Из этой формулы путем различных подстановок могут быть получены формулы A(y, x, t), A(y, y, t), A(t1, t2, t) и т.п.
Для пропозиционального случая таблица истинности, определяет логические значения формулы при заданных значениях ее пропозициональных переменных. Поэтому она есть связующее звено между идеальными объектами - формулами и предметным миром, под которым мы понимаем логическую функцию, задаваемую таблицей. Для введенного более широкого языка ограничиться лишь таблицей истинности не представляется возможным. Но, тем не менее, имеется возможность также установить соответствие между формулой и ее истинностными значениями в зависимости от значений объектов, подставленных вместо ее предметных переменных.
Введем следующее определение.
Упорядоченная пара Â = называется интерпретацией сигнатуры S, если выполняются следующие условия:
А есть непустое множество (называемое носителем интерпретации);
n - отображение множества предикатных и функциональных символов сигнатуры S в множество отношений и отображений, определенных на множестве А, а множества символов констант в множество А. При этом
если r есть предикатный символ, то nÂ(r) есть отношение на А, местность которого совпадает с местность r;
если f есть функциональный символ, то nÂ(f) есть отображение А ® А, местность которого совпадает с местность f;
если с есть константа, то nÂ(с) есть элемент множества А.
Если задана интерпретация сигнатуры S, то говорим, что формулы этой сигнатуры интерпретируются в Â.
Если
S = есть сигнатура, то интерпретацию Â сигнатуры S обозначим следующим образом:
 = ,
где rn, fk, cm суть соответственно отношение nÂ(rn), отображение nÂ(fk), определенные на множестве А, и константа nÂ(cm)Î А.
Поясним, что здесь имеется в виду.
Отметим, во-первых, что сигнатура есть чисто синтаксическое понятие: в естественном языке ей соответствует лишь набор элементарных, базисных терминов (лексем). Во-вторых, как правило, всякий термин естественного языка в нашем представлении связан с конкретным объектом или множеством однородных объектов. Тем самым, он наделен определенным смыслом. Именно такая осмысленность лексем позволяет понимать о чем идет речь в том или ином конкретном случае.
Поэтому, определяя интерпретацию сигнатуры, мы тем самым фиксируем содержательное значение (смысл) ее символов: фиксируем предметную область, отношения, отображения и объекты которой подставляются на места элементов сигнатуры, когда необходимо выяснить истинность или ложность той или иной формулы. Т.е. эти объекты и отношения интерпретируют синтаксические конструкции формулы.
Пример. Алгебраическая система Â = , где N - множество натуральных чисел, + и · - операции сложения и умножения, 0 и 1 обозначают соответственно нуль и единицу натурального ряда, называется арифметикой натуральных чисел и является интерпретацией сигнатуры S = < f1, f2; c1, c2>, состоящей из двух функциональных символов и двух констант.