Интерпретации. 
Дискретный анализ. 
Формальные системы и алгоритмы

В исчислении высказываний формула принимает значение «истина» или «ложь», если присвоены истинностные значения всем входящим в неё переменным. В исчислении предикатов ситуация более сложная. Формула исчисления предикатов описывает некоторое утверждение о свойствах (предикатах) объектов. Чтобы интерпретировать это утверждение, нужно указать, о каких объектах и каких их свойствах идёт речь. Интерпретацией формулы в общем случае будет /с-арный предикат, который, вообще говоря, истинен или ложен в зависимости от выбора значений входящих в формулу переменных. Если к = 0, то такой предикат является одним из истинностных значений истиной или ложью — независимо от значений входящих в формулу переменных.

Пример 3.11. Рассмотрим формулу А (х, у), А € V2, х, у? X. Чтобы дать её возможную интерпретацию, будем, например, полагать, что х, у принимают значения во множестве целых чисел, а А — бинарный предикат «х меньше у». Таким образом, интерпретацией нашей формулы является предикат сравнения чисел.

А что можно сказать в этой интерпретации про формулу /хА (х, у)? В соответствии с неформальным пониманием квантора всеобщности мы должны интерпретировать эту формулу как утверждение «для всех х выполнено, что х меньше у». Это утверждение задаёт унарный предикат: при фиксированном значении у оно истинно или ложно.

Наконец, если рассмотреть формулу 3 уУ хА (х, у), то она будет интерпретироваться как 0-арный предикат (истина или ложь) и означать утверждение «существует такое целое число, которое больше любого другого числа». (Это утверждение, конечно, ложно.).

Пример 3.11 показывает, как интерпретировать элементарные формулы. Кроме того, из этого примера видно, что применение кванторов понижает арность предиката. Однако из этого примера не вполне ясно, как интерпретировать формулу / х/ хА (х, у) (и какова арность предиката-интерпретации этой формулы). Все такие неясности будут устранены формальным определением, которое приводится ниже. А пока рассмотрим пример интерпретации формулы с термами общего вида.

Пример 3.12. Интерпретируем формулу VxE (f (u, ж), х) на множестве целых чисел, считая, что Е € V2 ~ бинарный предикатный символ, интерпретируемый как предикат равенства, f? J-2 — бинарный функциональный символ, интерпретируемый как умножение аргументов, х? X — символ переменной, и? J-о — константа, которую мы интерпретируем как число 1. Тогда написанная выше формула выражает следующее утверждение «для любого х выполнено равенство 1-х = х». Это 0-арный предикат, который принимает по очевидным причинам значение «истина».

Аналогично интерпретируются и более сложные формулы. Рассмотрим ещё один пример.

Пример 3.13. Рассмотрим формулу.

в интерпретации примера 3.12.

Терм /(х, ж) означает (интерпретируется как) х², терм f (x, f (x, x))-x-x² = х³. А вся формула означает утверждение: «для любого х из того, что куб целого числа х равен квадрату х, следует, что квадрат х числа равен х». Это утверждение истинно (посылка истинна лишь для 0 и 1, но для этих чисел справедливо равенство х² = х).

Для формального определения интерпретации оказывается полезным следующее техническое понятие.

Определение 3.14. Множество предикатных и функциональных символов с указанием арностей называется сигнатурой. Если в формулу входят только предикатные и функциональные символы из сигнатуры <�т, то такая формула называется формулой в сигнатуре а.

(Напомним, что константы — это функциональные символы арности 0, так что сигнатура может включать в себя и константы.).

Пример 3.15. Формула /xE (f (u, х), х) из примера 3.12 является формулой в сигнатуре Е, /, и, где Е — бинарный предикатный символ, / — бинарный функциональный символ, а и — 0-арный функциональный символ (константа).

Определение 3.16. Интерпретацией М. сигнатуры а назовём непустое множество М (область интерпретации) и соответствие интерпретации, которое каждому к-арному функциональному символу / из <7 сопоставляет функцию [f]: М^к —> Л/, отображаюп jy ю М^к в М, а каждому А-ар ному предикатному символу А из а — А:-арное отношение [А] на А/, т. е. [А] С М^к.

Пример 3.17 (продоллсепие примера 3.15). Пусть областью интерпретации является множество действительных чисел Ш, символу Е соответствует отношение равенства.

символу / — операция сложения.

а константе и соответствует 0, т. е. [и] = 0.

Этими условиями определяется некоторая интерпретация формул в сигнатуре E, f, u примера 3.15, в том числе и формулы из примера 3.12.

Интерпретация символов продолжается на все формулы и термы в сигнатуре а. Термам соответствуют функции со значениями в области интерпретации А/, а формулам — предикаты на А/. Будем обозначать интерпретации формул и термов, заключая их в квадратные скобки и выделяя полужирным начертанием как это уже сделано в определении интерпретации.

Для формальных определений нам удобно будет представлять формулы и термы как деревья. Как уже говорилось, листья такого дерева помечены переменными или константами (0-арными функциональными символами).

Определение 3.18 (правила оценки). Пусть каждой переменной которой помечен некоторый лист дерева,.

присвоено значение из области интерпретации — оценка перельет toil.

В таком случае можно определить оценку всех остальных вершин дерева по следующим рекурсивным правилам:

• • оценка листа — это оценка переменной, которой помечен лист, или интерпретация константы, которой помечен лист;
• • оценка вершины, помеченной к-арпым функциональным символом /, равна [f](vi,…, гд.), где Vi — оценки потомков данной вершины;
• • оценка вершины, помеченной символом А, который является /с-арным предикатным символом, равна значению предиката [А] на наборе (гц,…, г-^), где Vi — оценки потомков данной вершины;
• • оценка вершины, помеченной символом 1, является отрицанием оценки её потомка (у такой вершины ровно один потомок);
• • оценка вершины, помеченной символом —", равна импликации V—?V2 оценок щ, V2 её потомков;^[1]

Обратите внимание, что в последнем случае нужно оценивать потомка вершины, помеченной кванторным блоком V х, при разных, вообще говоря, оценках переменных.

Замечание 3.19. Напомним, что вершинам дерева формулы отвечают подформулы. Поэтому написанные выше правила оценки определяют оценки всех подформул формулы.

Пример 3.20. Рассмотрим формулу /xE (f (u> ж), ж) в интерпретации, построенной в примере 3.17. Оценим эту формулу при значении переменной ж, равном 1. Оценка терма f (u, x) но второму правилу из данного выше списка равна 0+1 = 1. Оценка формулы E (f (u, x), x) по третьему правилу оценки равна значению предиката [Е] на наборе (1,1), т. е. равна истине.

Теперь осталось оценить значение самой формулы. Здесь нужно применить последнее правило оценки, т. е. вычислить оценку формулы E (f (u, x), x) при всех возможных оценках переменных, отличающихся лишь значением х. Повторив все предыдущие рассуждения для оценки переменной ж, равной а, мы получаем, что оценка E (f (u, ж), ж) равна, истине, так как 0 + а = а. Значит, оценка всей формулы /xE (f (u, ж), ж) равна истине.

Пример 3.21. Оценим в той же интерпретации формулу /х /хЕ (х, у) при оценке переменных ж = 1, у = 1.

Оценка формулы Е (х, у) — истина. Однако при ж = 0, у = 1 оценка формулы Е (ж, у) — ложь, поэтому по последнему правилу оценки мы заключаем, что оценка формулы /хЕ (х, у) — ложь.

Более того, по аналогичной причине оценка формулы /хЕ (х, у) — ложь при любой оценке переменных ж, у. В частности, это означает, что оценка исходной формулы V жУ хЕ (х, у) — ложь при оценке переменной ж = 1, у = 1.

Пример 3.22. Оценим в той же интерпретации формулу /xE (y, z) при оценке переменных у = 1, z = 1.

Оценка формулы Е (у, z) — истина. Для оценки формулы V хЕ (х, z) по последнему правилу оценки нужно оценить Е (у. z) при всех оценках у и z, которые отличаются от данной значением переменной х. Но такая оценка единственна и совпадает с исходной. Таким образом, оценка всей формулы — истина.

Мы определим теперь интерпретации термов и формул с помощью введённой процедуры оценки.

Определение 3.23. Интерпретацией терма t является функция [t], которая отображает набор (а,…, а к) значений переменных ад, …, ад, входящих в терм, в оценку этого терма при оценке переменных = (ц.

Пример 3.24 (продолжение примера 3.17). Несложно проверить, что

Интерпретацией формулы является некоторый предикат. Проще всего определить его как оценку формулы при некоторой оценке переменных. В этом случае получаем п-арный предикат, где п — количество входящих в формулу переменных.

Однако уже из самой структуры формулы можно заметить, что значение такого предиката не зависит от некоторых значений входящих в него переменных. Мы укажем эти переменные и избавимся от них в определении интерпретации формулы.

Определение 3.25. В формуле /хА подформула А называется областью действия квантора. Вхождение переменной х называется связанным, если х входит в область действия некоторого квантора по х или в кванторный блок

Ух. Все остальные вхождения переменных называются свободными.

Переменные, имеющие свободные вхождения в формулу, будем называть параметрами формулы.

Если смотреть на формулы как на деревья, то область действия квантора — это дерево потомков той вершины, которая помечена данным квантором. Вхождение переменной х в формулу свободно, если на пути от листа, помеченного этим вхождением х, до корня дерева не встречается вершина с пометкой Ух.

Пример 3.26. Рассмотрим формулы.

В первом случае кванторов вообще нет, поэтому все вхождения — свободные.

Во вторую формулу х входит 4 раза. Первые три вхождения — связанные, последнее — свободное. Переменная у первый раз входит в формулу свободно, второй раз — связанно (как переменная квантора). Единственное вхождение г свободно. Заметим, что второй квантор берётся, но переменной, которая ни разу не встречается в его области действия. Это допустимо, но нашим правилам, хотя и не имеет особого смысла, как вскоре станет ясно.

В третьей формуле третье вхождение переменной — свободно (напомним, что приоритет импликации ниже, чем приоритет квантора), а остальные — связанны.

Задача 3.3. Укажите параметры формулы.

Лемма 3.27. Оценка формулы, А зависит только от, значений параметров формулы А.

Доказательство. Индукция по построению формулы. Для элементарных формул утверждение очевидно, так как все переменные входят в элементарную формулу свободно.

Если формула имеет вид ~В. В—>С, то её параметры являются параметрами В (или С во втором случае). А по правилам оценки оценка формулы А зависит лишь от оценки формулы В (и оценки С во втором случае), которые по индуктивному предположению зависят только от параметров этих формул.

У формулы А вида V ?-8 параметры те же, что и у В. за исключением переменной х. По последнему правилу оценки оценка формулы А не зависит от оценки переменной х. ?

Лемма 3.27 обеспечивает корректность следующего определения.

Определение 3.28. Интерпретацией [А] формулы А назовём fc-арный предикат, где к — число параметров формулы А. которые мы обозначим ад,…, од. Этот предикат истинен при некотором наборе значений параметров (aj,…, a*,) тогда и только тогда, когда истинна оценка формулы А при некоторой оценке переменных формулы, в которой ау = aj.

Мы также будем говорить, что формула А выражает предикат Р в интерпретации АЛ, если [А] = Р в интерпретации АЛ.

Замечание 3.29. Определение 3.28 может показаться избыточным. Как уже говорилось, сама оценка формулы является предикатом. Однако этот предикат зависит от всех переменных, входящих в формулу, а формальная зависимость от связанных переменных иногда бывает неудобна. Впрочем, принципиального значения эта разница не имеет.

Формула без свободных вхождений переменных называется замкнутой. Замкнутая формула интерпретируется как 0-арный предикат (истина или ложь). Таким образом, в заданной интерпретации замкнутые формулы становятся истинными или ложными.

Задачи.

• 3.4. Проверьте истинность следующих утверждений.
• 1) Формула ИП имеет вид (на месте многоточий стоят какие-то символы)

… /х... X.. .

и между квантором и вторым из указанных вхождений переменной х нет других кванторов. Тогда оба указанных вхождения х связанные.

2) Формула ИП имеет вид (на месте многоточий стоят какие-то символы).

… /х. .. X.. .

и между квантором и вторым из указанных вхождений переменной х нет закрывающих скобок. Тогда оба указанных вхождения х связанные.

3) Формула ИП имеет вид (на месте многоточий стоят какие-то символы) где А — предикатный символ, а х — символ переменной. Тогда указанные вхождения х либо оба связанные, либо оба свободные.

4) Формула ИП имеет вид (на месте многоточий стоят какие-то символы) где А — предикатный символ, а х — символ переменной, причём между указанными вхождениями х нет предикатных символов. Тогда указанные вхождения х либо оба связанные, либо оба свободные.

• 3.5. Приведите пример формулы исчисления предикатов, которая в одной интерпретации задаёт предикат равенства «х = у», а в другой — предикат неравенства «х Ф у».
• 3.6. Существует ли такая формула ИП в сигнатуре из унарных предикатных и функциональных символов, что в некоторой интерпретации на бесконечной области она выражает предикат равенства «а; = у«?
• 3.7. Пусть F — замкнутая формула ИП в сигнатуре из унарных предикатных и функциональных символов. Докажите, что если F истинна в некоторой интерпретации на конечной области, то F также истинна в некоторой интерпретации на бесконечной области.

• [1] оценка вершины, помеченной символом /х, равна истине тогда и только тогда, когда оценка её потомкаистинна при всех возможных оценках переменных, отличающихся от данной лишь значением переменной х. Оценкой форльулы является оценка корня её дерева. Во всех указанных случаях оценка вершины, не являющейся листом, однозначно определяется оценками вершин, которые лежат ниже (т. е. путь из которых в корень проходит через данную вершину), а оценка листа также определена однозначно. Поэтому данное определение корректно.