Пример. Если сигнатура S = состоит из одного двуместного предикатного символа, то ее интерпретация Â = называется графом (в этом случае А есть множество вершин, а Q - отношение их смежности). Если Q - частичный (линейный) порядок на А, то Â называется частично (линейно) упорядоченным множеством или просто частичным (линейным) порядком.
Интерпретации позволяет увидеть в формуле осмысленное высказывание, которое утверждает нечто об объектах предметной области. Но, для установления истинности или ложности этого высказывания таблиц истинности явно недостаточно. В этом легко убедиться, сравнив выразительные возможности пропозиционального языка и вновь построенного. Именно поэтому нам потребуется механизм установления логических значений формул при определенной интерпретации ее сигнатуры.
С этой целью введем следующее определение.
Означиванием g переменных из множества Х предметных переменных над множеством А назовем однозначное отображение g: X ® A. Иными словами, означивание указывает конкретный объект из А, который подставляется на место каждой переменной.
Если t - терм сигнатуры S, его переменные содержатся в X, то означивание g: X ® A следующим образом определяет значение t[g] Î A терма t в Â:
1) если t есть переменная x, то t[g] = g(x);
2) если t = f(t1, ..., tn), то t[g] = nÂ(f)(t1[g], ..., tn[g]).
Означивание позволяет вместо t(x1, ..., xn)[g] писать t(a1, ..., an), где ai = g(xi), i = 1, 2, ..., n. В записи t(a1, ..., an) указаны конкретные объекты носителя интерпретации, которые подставлены на места переменных.
Пример. В алгебраической системе из примера на стр.18 значение терма x + y при означивании g(x) = 1 и g(y) = 3 равно 1 + 3 = 4.
Поясним это определение.
Когда осуществляется означивание переменных терма, то на их места подставляются имена конкретных объектов из области интерпретации. В итоге первоначальное множество всех объектов, описываемое термом, сужается вплоть до одного предмета. Действительно, результирующее множество включает лишь единственный объект, задаваемый той суперпозицией свойств, которая определяется суперпозицией отображений, образующих терм.
Теперь можно сформулировать методику определения логического значения любой формулы с заданной интерпретацией. Сравнив ее с таблицами истинности из предыдущего раздела, легко увидеть существенные различия, которые определяются разность выразительных возможностей языков.
Определим одно из важнейших понятий этого раздела: отношение “в интерпретации Â формула F истинна при означивании g ее свободных переменных” (обозначается ú=ÂF[g] ). (Здесь и далее знак Û есть сокращение для выражения “тогда и только тогда, когда”, а знак Þ - для выражения “из левой части следует правая часть”.)
1. Если F = r(t1, ..., tn), r - это предикатный символ, n ³ 0, и t1,..., tn совокупность термов, то ú=ÂF[g] Û (t1[g], ..., tn[g])Î r . Иными словами, кортеж значений термов t1, ..., tn при означивании g всех их переменных принадлежит отношению r.
2. Если F = ØB, тоú=ÂF[g] Û неверно, что ú=ÂB[g] (этот факт будем обозначать ú¹ÂB[g]).
3. Если F = B1 Ú B2, тоú=ÂF[g] Û ú=ÂB1[g] или ú=ÂB2[g].
4. Если F = B1 Ù B2, тоú=ÂF[g] Û ú=ÂB1[g] и ú=ÂB2[g].
5. Если F = B1 É B2, то ú=ÂF[g] Û из ú=ÂB1[g] следует ú=ÂB2[g]. В четырех последних случаях формальное отношение ú=ÂF[g] определяется с использованием содержательных терминов “неверно, что”, “или”, “и”, “из ... следует”. Тем самым предполагается, что эти содержательные термины понимаются однозначно.
6. Если F = "xB, то ú=ÂF[g] Û для любого означивания g¢, такого, что gFV(F) = g¢FV(F) и x Î Def g¢, имеет место ú=ÂB[g¢]. Здесь утверждается, что истинность формулы F в интерпретации Â при фиксированных значениях пусть а1, а2, ..., аn ее свободных переменных х1, х2, ..., хn (задаваемых g) определяется в зависимости от значений формулы B, с теми же подставленными объектами а1, а2, ..., аn, когда переменная х пробегает все значения носителя интерпретации. И если при каждом из этих значений формула В истинна, то истинной оказывается и формула F. Именно поэтому переменная х называется связанной, так как при определении истинностного значения формулы F не фиксируется одно ее значение, а рассматриваются все из области интерпретации.
7. Если F = $xB, то ú=ÂF[g] Û существует такое означивание g¢, что gFV(F) = g¢FV(F) и x Î Def g¢, имеет место ú=ÂB[g¢]. Этот случай с одной стороны напоминает предыдущий, а с другой - имеет существенное отличие. Здесь утверждается, что истинность формулы F в интерпретации Â при фиксированных значениях, пусть а1, а2, ..., аn, ее свободных переменных х1, х2, ..., хn (задаваемых g) определяется в зависимости от значений формулы B, с теми же подставленными объектами а1, а2, ..., аn, когда переменная х пробегает все значения носителя интерпретации. И если при каком-либо из этих значений формула В истинна, то истинной оказывается и вся формула F.