Интерпретация формулы логики предикатов: как задать смысл

Сама по себе формула логики предикатов - вроде $\forall x\,(P(x)\to Q(x))$ - ничего не утверждает. Это пустой синтаксический скелет: символы $P$, $Q$, $x$ не привязаны ни к чему конкретному. Чтобы у формулы появился смысл и можно было спросить «истинна она или ложна», её нужно интерпретировать: выбрать область, договориться, что означает каждый предикатный и функциональный символ, какой объект обозначает каждая константа. Ниже разберём, из чего складывается интерпретация, как по ней вычислять истинность формулы с кванторами и как искать модель или контрпример. Если нужно разобрать конкретную формулу - соберите запрос в форме сразу под введением.

Что такое интерпретация

Интерпретация (или структура) для языка логики предикатов - это способ наделить смыслом все нелогические символы языка. Формально интерпретация $\mathcal{I}$ состоит из двух частей:

1. Область интерпретации $D$ (она же носитель, универсум, domain) - непустое множество объектов, о которых идёт речь. Это могут быть натуральные числа, люди, точки плоскости, строки - что угодно, лишь бы множество было непустым.
2. Означивание символов - правило, которое каждому нелогическому символу сопоставляет объект нужного типа над областью $D$:
   • каждой константе $c$ - конкретный элемент $c^{\mathcal{I}}\in D$;
   • каждому $n$-местному функциональному символу $f$ - функцию $f^{\mathcal{I}}\colon D^n\to D$;
   • каждому $n$-местному предикатному символу $P$ - отношение $P^{\mathcal{I}}\subseteq D^n$, то есть множество тех наборов, на которых предикат истинен.

Логические символы - связки $\neg,\land,\lor,\to$, кванторы $\forall,\exists$, равенство - смысла не меняют: они интерпретируются всегда одинаково. Меняется только трактовка предметных символов. Поэтому одна и та же формула в разных интерпретациях может быть и истинной, и ложной.

Рассчитать для своей задачи

Область интерпретации задаёт горизонт

Выбор области - первый и решающий шаг. Кванторы $\forall x$ и $\exists x$ пробегают именно по области $D$, и от её состава напрямую зависит истинность.

Рассмотрим формулу $\forall x\,\exists y\,(y > x)$ - «для всякого $x$ найдётся больший $y$». На области натуральных чисел $\mathbb{N}$ она истинна: для любого числа есть следующее. На конечной области, скажем $D=\{0,1,2\}$ с обычным порядком, она уже ложна: для $x=2$ большего элемента нет. Сама формула не изменилась - изменился горизонт, по которому бегает квантор.

Отсюда практическое правило: прежде чем оценивать истинность, всегда явно фиксируйте, какое множество вы взяли за область. Большинство студенческих ошибок в задачах на интерпретацию - это молчаливая подмена области (например, переход от целых к натуральным) уже по ходу рассуждения.

Означивание предикатов, функций и констант

Когда область выбрана, нужно расшифровать каждый символ. Удобно держать в голове три типа объектов.

Константы обозначают конкретные элементы. Если в формуле есть $a$, мы говорим: «пусть $a^{\mathcal{I}}=0$». Теперь всюду, где встречается $a$, имеется в виду нуль.

Функциональные символы превращают объекты в объекты. Двухместный $+$ на $\mathbb{N}$ интерпретируется обычным сложением: $+^{\mathcal{I}}(3,4)=7$. Важно, что функция должна быть тотальной - определена на всех наборах из $D^n$, иначе это не интерпретация в классическом смысле.

Предикатные символы превращают объекты в истину или ложь. Одноместный $P$ задаёт подмножество области (те $x$, для которых $P(x)$ истинно); двухместный $R$ задаёт отношение - множество пар. Например, на людях предикат «$\text{Родитель}(x,y)$» - это множество всех пар, где первый действительно родитель второго.

Рассчитать для своей задачи

Оценка истинности: от атомов к кванторам

Имея полную интерпретацию, истинность формулы вычисляют рекурсивно, снизу вверх - это и называют семантикой Тарского.

1. Терм оценивается в элемент области. Константа $c$ даёт $c^{\mathcal{I}}$; переменная $x$ - текущее присвоенное ей значение; составной терм $f(t_1,\dots,t_n)$ - результат применения $f^{\mathcal{I}}$ к значениям подтермов.
2. Атомарная формула $P(t_1,\dots,t_n)$ истинна, если набор значений термов попал в отношение $P^{\mathcal{I}}$. Равенство $t_1=t_2$ истинно, когда термы означивают один и тот же элемент.
3. Связки считаются как в логике высказываний: $\neg,\land,\lor,\to$ применяются к уже вычисленным истинностным значениям подформул.
4. Кванторы перебирают область. $\forall x\,\varphi$ истинна, если $\varphi$ истинна при каждом значении $x$ из $D$. $\exists x\,\varphi$ истинна, если хотя бы при одном.

Ключевой момент с кванторами: при $\forall x$ и $\exists x$ мы временно подставляем вместо $x$ всевозможные элементы области и смотрим на истинность тела. Поэтому для конечной области оценку можно довести до конца механически, перебором. Та же логика лежит в основе перевода формулы в предварённую нормальную форму - там кванторы выносят в префикс, не меняя смысла.

Модель, контрмодель и общезначимость

Через интерпретацию определяются центральные понятия семантики.

Интерпретация $\mathcal{I}$ называется моделью формулы $\varphi$, если $\varphi$ в ней истинна. Записывают $\mathcal{I}\models\varphi$. Если истинна ложна - это контрмодель (контрпример).

Дальше - три уровня «силы» формулы:

• Выполнима (satisfiable) - есть хотя бы одна модель. Чтобы доказать выполнимость, достаточно предъявить одну подходящую интерпретацию.
• Опровержима - есть хотя бы одна контрмодель.
• Общезначима (валидна, тавтология предикатов) - истинна в любой интерпретации. Например, $\forall x\,P(x)\to\exists x\,P(x)$ общезначима (область непуста, потому из «все» следует «существует»).

Чтобы опровергнуть общезначимость, нужен ровно один контрпример: одна интерпретация, где формула ложна. А чтобы доказать общезначимость, перебором не обойтись - интерпретаций бесконечно много, нужен синтаксический вывод или семантическое рассуждение в общем виде.

Рассчитать для своей задачи

Как строить интерпретацию под задачу

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

1. Выпишите все нелогические символы формулы: константы, функции, предикаты с их местностью. Это список того, что предстоит означить.
2. Выберите минимальную область. Часто хватает двух-трёх элементов - на маленькой конечной области всё проверяется перебором. Не берите $\mathbb{R}$, если задача решается на $\{a,b\}$.
3. Подберите означивание под цель. Хотите истинность - настройте предикаты так, чтобы тело квантора выполнялось; хотите ложность - наоборот, оставьте «дырку», на которой $\forall$ срывается.
4. Проверьте оценкой по Тарскому, начиная с атомов. Особое внимание - порядку кванторов: $\forall x\,\exists y$ и $\exists y\,\forall x$ задают разные условия.

Этот цикл - «выписать символы, взять малую область, означить под цель, проверить перебором» - закрывает почти все учебные задачи на интерпретацию.

Частые ошибки

• Пустая область. В классической логике предикатов область обязана быть непустой, иначе ломаются законы вроде $\forall x\,P(x)\to\exists x\,P(x)$. Не берите $D=\varnothing$.
• Подмена области по ходу. Начали с целых, незаметно перешли к натуральным - и истинность «поплыла». Фиксируйте $D$ один раз.
• Частичная функция. Функциональный символ должен быть определён на всех наборах. «Деление» на области с нулём - типичная ловушка.
• Путаница порядка кванторов. $\forall x\,\exists y\,R(x,y)$ («у каждого свой $y$») слабее, чем $\exists y\,\forall x\,R(x,y)$ («один $y$ на всех»). При интерпретации это разные проверки.
• Свободная переменная как утверждение. Формулу со свободной переменной нельзя называть истинной или ложной в интерпретации без присвоения значения этой переменной.

FAQ

Чем интерпретация отличается от модели? Интерпретация - это любая структура (область плюс означивание символов). Моделью формулы она становится только тогда, когда формула в ней истинна. То есть «модель» - это «интерпретация, согласованная с данной формулой».

Зачем нужна область, разве нельзя обойтись предикатами? Без области кванторы не определены: $\forall x$ и $\exists x$ бессмысленны, пока не сказано, по какому множеству бегает $x$. Область задаёт сам диапазон значений переменных, и от неё прямо зависит истинность.

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

Коротко

Интерпретация формулы логики предикатов - это выбор непустой области и означивание всех констант, функций и предикатов над ней. Только после этого у формулы появляется истинностное значение, которое вычисляется по Тарскому: термы дают элементы, атомы проверяются по отношениям, связки считаются как в логике высказываний, а кванторы перебирают область. Если формула истинна - интерпретация её модель; если ложна - контрмодель. Истинная во всех интерпретациях формула общезначима; чтобы опровергнуть общезначимость, хватает одного контрпримера на малой конечной области.