Пример. Найдем интерпретацию, содержащую два элемента {a, b}, на которой формула
F = "x$y(P(x,y) É (P(y,x) Ú Q(x))
истинна. Допустим, что символы P, Q интерпретируются на множестве M = {a, b} отношениями соответственно P, Q. Чтобы формула F была истинной в этой интерпретации, необходимо, чтобы была истинной формула
F = (P(x,y) É (P(y,x) Ú Q(x)) =
=(P(a,a)É(P(a,a)ÚQ(a)))Ù(P(a,b)É(P(b,a)ÚQ(a)))Ù
Ù(P(b,a)É(P(a,b)ÚQ(b)))Ù(P(b,b)É(P(b,b)ÚQ(b))).
Эта пропозициональная формула, поэтому приведем ее к д.н.ф.:
(ØP(a,a)ÚP(a,a)ÚQ(a))Ù(ØP(a,b)ÚP(b,a)ÚQ(a))Ù
Ù(ØP(b,a)ÚP(a,b)ÚQ(b))Ù(ØP(b,b)ÚP(b,b)ÚQ(b)) =
= (ØP(a,b)ÚP(b,a)ÚQ(a))Ù(ØP(b,a)ÚP(a,b)ÚQ(b)) =
= ØP(a,b)ØP(b,a)ÚØP(b,a)Q(a)ÚP(a,b)P(b,a)ÚP(a,b)Q(a)Ú ÚØP(a,b)Q(b)ÚP(b,a)Q(b)ÚQ(a)Q(b).
Легко заметить, что каждый дизъюнкт определяет ту интерпретацию предикатной сигнатуры исходной формулы, при которой она истина. Для того, чтобы не выписывать все возможные интерпретации, которых в данном случае насчитывается семь, приведем так называемую контрмодель для этой формулы. Контрмоделью формулы называется такая интерпретация, на которой она ложна. В частности, рассматриваемая формула будет всегда ложной при следующих интерпретациях: P(a,b), ØP(b,a), ØQ(a) и ØP(a,b), P(b,a), ØQ(b).
Пример. Покажем, что совокупность формул: "x$yP(x,y),"xØP(x,x) и "x"y"z(P(x,y)ÙP(y,z)ÉP(x,z)) ложна на любой интерпретации из двух элементов. Для этого, рассмотрим все означивания этих формул на множестве M = {a, b}:
"xÎM $yÎMP(x,y),
"xÎM ØP(x,x),
"xÎM"yÎM"zÎM P(x,y) Ù P(y,z) É P(x,z).
Легко показать, что приведение конъюнкции трех последних формул к конъюнктивной нормальной форме дает в итоге тождественно ложное выражение
P(a,b) Ù P(b,a) Ù (ØP(a,b) Ú ØP(b,a)).
Таким образом, при любом означивании три исходные формулы не могут быть одновременно истинными при любой интерпретации на множестве из двух элементов.
Упражнение. Показать, что формулы из последнего примера не могут быть истинными ни при какой интерпретации их предикатных символов на конечном множестве объектов.
Формула F называется общезначимой (обозначается ú=F), если она истинна в любой интерпретации. Следовательно, не общезначимая формула не истинна по меньшей мере в одной интерпретации. Иными словами, при некотором означивании ее свободных переменных в этой интерпретации она не истинная.
Формула называется выполнимой, если она истинна в некоторой интерпретации, которая в этом случае называется ее моделью. Из определения легко увидеть, что невыполнимая формула ложна в каждой интерпретации.
Легко увидеть, что формула общезначима тогда и только тогда, когда ее отрицание невыполнимо. С другой стороны, формула выполнима тогда и только тогда, когда ее отрицание не общезначимо.
Отношение выполнимости одной формулы следующим образом обобщается на множество формул.
Множество D = {Ai: i Î I} формул называется выполнимым в интерпретации Â, если при некотором означивании g всех свободных переменных этих формул верно, что ú=ÂAi[g]. Множество D называется выполнимым, если оно выполнимо в некоторой интерпретации. Если множество D выполнимо в интерпретации Â, то говорят, что Â есть модель D. Множество формул, не выполнимое ни в какой интерпретации, называется невыполнимым.
Очевидно, что если D есть выполнимое множество формул и для некоторого множества D1 имеет место включение D1 Í D, то D1 также выполнимо. С другой стороны, если множество D невыполнимо, то это еще не значит, что невыполнимо всякое его подмножество. Очевидно, что в невыполнимом множестве может существовать некоторое выполнимое собственное подмножество.
Формула F называется логическим следствием множества F1, F2, ..., Fn формул (обозначается F1, F2, ..., Fn ú= F), если формула F1 Ù F2 Ù ... Ù Fn É F общезначима. Если D есть бесконечная система формул, то будем полагать, что формула F логически следует из D (обозначается Dú= F), если в D найдется конечное множество формул, из которых следует F. Нетрудно увидеть, что заключение правила modus ponens есть логическое следствие его посылок.
Обозначим C(D) совокупность всех формул, которые содержатся в D или являются их логическими следствиями. По аналогии с предыдущим множество D назовем непротиворечивым, если C(D) не содержит противоречия. В противном случае, оно противоречиво.
Для языка первого порядка, по аналогии с пропозициональным случаем, также справедливо, что множество формул непротиворечиво тогда и только тогда, когда оно выполнимо, т.е. для него имеется модель. Следовательно, если множества формул рассматривать как содержания сознания, которые представляют собой описания некоторой реальной или воображаемой, существующей или выдуманной, возможной или невозможной, мыслимой или немыслимой ситуации и т.д., то такие идеальные содержания имеют предметные интерпретации лишь в том случае, когда они непротиворечивы. Т.е. внутренняя непротиворечивость и объективная реализуемость связаны самым непосредственным образом.