Пример. Рассмотрим как устанавливается выполнимость формулы F = "xA(x) Ú B(x, y) в некоторой интерпретации Â при означивании g, Def g = {x, y}. Для того, чтобы выполнялось отношениеú=ÂF[g] требуется, чтобы имело место ú=Â"xA(x)[g] или ú=ÂB(x, y)[g]. Установление выполнимости ú=ÂB(x, y)[g] не вызывает затруднений, так как в этом случае надо присвоить фиксированные значения свободным переменным x и у. Рассмотрим теперь установление первого отношения ú=Â"xA(x)[g]. По определению, для этого требуется выполнить следующие действия: подставить всевозможные значения переменной х, принадлежащие носителю рассматриваемой интерпретации, и для каждого из этих значений установить истинность формулы A.
Подчеркнем еще раз, что при установлении истинности формулы в некоторой интерпретации ее свободным переменным означивание g придает фиксированные значения, а для связанных - наоборот, рассматриваются их всевозможные означивания. При этом, для устанавливания истинности формулы $xB(х) в интерпретации Â, достаточно указать по меньшей мере одно значение (пусть а) переменной х, при котором формула B(а) истинна в интерпретации Â.
Если же устанавливается истинность формулы "xB в интерпретации Â, то для этого необходимо, чтобы при любом значении а переменной х формула B(а) была истинной в интерпретации Â.
Из приведенных рассуждений ясно, что свободные переменные существенно отличаются от связанных. Если при интерпретации формулы свободным переменным присваиваются некоторые фиксированные значения, то связанные либо пробегают все значения носителя (в случае квантора общности), либо для них выбирается в точности одно (в случае квантора существования). Таким образом, при установлении выполнимости формул в интерпретации кванторы общности и существования напрямую связаны с перебором носителя интерпретации. Но перебор, определяемый квантором общности, отличается от перебора, определяемого квантором существования: первому соответствует конъюнктивное, а второму - дизъюнктивное соединения формул, когда на место связанной переменной поочередно подставляются все элементы интерпретации. Будем обозначать их соответственно и .
Пример. Пусть сигнатура S содержит единственный двухместный предикатный символ P, две константы a и b, а в интерпретации Â = <{a, b}, P> отношение P задается следующим образом: P = {(a, b), (b, a)}. Рассмотрим следующие формулы: а) P(x, a); б) $xP(x, a); в) "xP(x, a); г) P(x, a) É P(a, x).
а°. Очевидно, что если задать такое означивание g, что g(x) = b, то выполняется отношениеú=ÂP(x, a)[g], так как (b, a) Î P. Для любого иного означивания g¢ имеем ú¹ÂP(x, a)[g¢].
б°. Для формулы б) имеем ú=Â$xP(x, a)[g], так как для формулы а) уже было показано, что при означивании g(x) = b имеет место отношение ú=ÂP(x, a)[g]. Тем самым найдено то значение b переменной х, при котором пара (x, a) принадлежит отношению P.
в°. Для формулы в) имеем ú¹Â"xP(x, a)[g], так как существует означивание g¢ именно g¢(x) = a, такое, что (a, a) Ï P. Иными словами, не при всяком значении переменной x Î{a, b} пара (x, a) принадлежит P.
г°. Формула г) истинна в  при любом означивании g. Покажем, что из того, что имеет место отношение ú=ÂP(x, a)[g], вытекает ú=ÂP(a, x)[g]. Действительно, если g(x) = a, то ú¹ÂP(x, a)[g], а если g(x) = b, то выполняются отношения ú=ÂP(x, a)[g] иú=ÂP(a, x)[g]. Следовательно, и формула "x(P(x, a) É P(a, x)) истинна в  при любом означивании (так как множество ее свободных переменных пусто).
Пример. Было показано, что формулы P(x, a) É P(a, x) и "x(P(x, a) É P(a, x)) из примера на стр.??? истинны в приведенной там интерпретации. Аналогично легко доказать, что формула "x"y (P(x, y) É P(y, x)) в ней также истинна.
Пример. Формула "x"y"z(x · (y + z) = x · y + x · z) истинна в арифметике натуральных чисел, если · интерпретируется как умножение, а + - как сложение.
Пример. Формула "x"y"z(Q(x, y)ÙQ(y, z) É Q(x, z)) истинна в любом полном графе, но не истинна в некоторых неполных.
Упражнение.
1. Доказать, что если формула истинна в интерпретации, содержащей m > 0 элементов, то она истинна в любой интерпретации с меньшим числом элементов.
2. Доказать, что если формула выполнима в интерпретации, содержащей m > 0 элементов, то она выполнима в любой интерпретации с большим числом элементов.
Замечание. Если формула F содержит свободные вхождения переменных, то в некоторой интерпретации она может быть истинной при одном означивании и ложной при другом. Действительно, формула P(x, a) из примера на стр.??? истинна в Â, если g(x) = b, и ложна, если g(x) = a.
Пример. Пусть сигнатура S =
, и ее интерпретация  = , где A - множество, содержащее не менее двух элементов, и < - отношение порядка. Тогда формула P(x, y) выполнима в  лишь при означивании g(x) < g(y). При других означиваниях переменных x и y эта формула не выполнима. Следовательно, про нее нельзя доказать ни ú=ÂP(x, y), ни ú¹ÂP(x, y). Но заведомо верны отношения: ú¹Â"х"уP(x, y), ú=Â$х$уP(x, y) и ú=Â"х$уP(x, y).