Семантика: системы и значения формул на их состояниях

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

Определение 7.4. Алгебраической системой или просто системой¹⁾. Сигнатуры называется непустое множество Aвместе с отображением, которое каждому n -местному предикатному (функциональному) символу из сопоставляет n-местный предикат ( n -местную функцию) на , а каждой константе из - некоторый элемент из A. A называется основным множеством системы. Если множество F имен функций в пусто, то соответствующую систему часто называют моделью.

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

Определим теперь интерпретации свободных переменных.

Определение 7.5. Состоянием (оценкой) системы назывется отображение , которое каждой переменной сопоставляет ее значение в данном состоянии .

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

Определение 7.6. Значение терма.

• Для переменной уже определено в состоянии
• Если t является константой , то не зависит от и равно значению этой константы при данной интерпретации
• (напомним, в интерпретации каждой константе сопоставлен некоторый элемент основного множества).
• Если t имеет вид f(t₁,...,t_m), где - символ m - местной функции, а t₁,...,t_m -термы, то есть , где f_A есть функция, соответствующая символу f в системе .

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

Определение 7.7. Значение атомной формулы.

• Если , где t₁ и t₂ - термы, то , если , и , если .
• Пусть - 0 -местный предикатный символ из P и P_A - это 0 -местный предикат, сопоставленный ему в . Тогда .

· Пусть , где P^(k) - предикатный k -местный символ из P, t₁,...,t_k - термы, аP_A - это k -местный предикат, сопоставленный P^(k) в . Тогда

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

Определение 7.8. Значение формулы.

Если - атомная формула, то ее значение определено выше. Значения сложных формулопределяются следующим образом.

• Если , то .
• Если имеет одну из форм , или , то значение
• равно значению или , соответственно.
• Если , то , если для , которое может отличаться от только значением переменной x, т.е. такого , что при , иначе .
• Если , то , если существует такое состояние , которое может отличаться от только значением переменной x, для которого , иначе .

Прокомментируем два последних пункта. Для истинности формулы вида (она читается: "для всехx имеет место (выполняется, истинно, справедливо) ") на состоянии нужно убедиться в том, что формула истинна при замене x любым элементом , т.е. на любом состоян ии, получающемся из изменением значения на переменной x: . Для истинности формулы вида (она читается: "существует такое x, что имеет место (выполняется, истинно, справедливо) ") насостоянии достаточно найти такое значение , что при подстановке a вместо x в формулу она будет истинна при неизменившихся значениях остальных свободных переменных.

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

Предложение 7.1. Пусть - система сигнатуры - формула той же сигнатуры, - множество ее свободных переменных. Тогда для любых двух состояний и , совпадающих на (т.е. таких, что для всякой ), имеет место равенство .

Доказательство получается индукцией по построению формулы Действительно, утверждение, очевидно, справедливо для значений термов и атомных формул. Из предположения о его справедливости для формул и его легко перенести на формулы вида и , где . ( Проведите это рассуждение самостоятельно!). Пусть теперь , где , а . Тогда . Пусть и - состояния, совпадающие на . Рассмотрим множества состояний, отличающихся от них только на x: и . Для каждого состояния в имеется состояние , совпадающее с на . Верно и обратное. Поэтому по предположению индукции в имеется состояние , для которого тогда и только тогда, когда в имеется состояние , для которого . Отсюда и из определения значения формулы следует, что .

Из этого предложения немедленно вытекает

Следствие. Значение замкнутой формулы не зависит от состояния, на котором она оценивается, т.е. либо на всех состояниях системы она истинна, либо на всех состояниях системы эта формула ложна.

Определение 7.9. Формула называется истинной на системе , если для любого состояния этой системы . В этом случае пишем .

Формула называется тождественно истинной (общезначимой), если она истинна на всехалгебраических системах своей сигнатуры. В этом случае пишем . Тождественно истинные формулы называют также законами логики.

Пример 7.4. В качестве примера рассмотрим следующую систему для определенной выше примере 7.2 сигнатуры .

Ее основное множество A₁ включает множество натуральных чисел N={0, 1, 2, ... }, для которых истинен предикат число и множество людей { петр, джон, ольга, иван, мария }, для которых истинен предикат человек (мы используем для объектов-людей имена, начинающиеся со строчных букв, чтобы отличить их от имен констант из сигнатуры). Пусть, кроме того, A₁ включает специальный объект соответствующий неопределенному (или ошибочному) значению. Константы интерпретируются естественным образом: числовые - соответствующими числами, имена людей - людьми с теми же именами.

x	отец(x)	лучший_друг(x)	зарплата(x)
петр	иван	джон
джон	петр	ольга
ольга	джон	петр
иван		мария
мария	иван	петр

Функция + на числах интерпретируется обычным сложением, а в остальных случаях ее значением является Интерпретации остальных функций заданы в таблице (для числовых аргументов все они равны ). Предикат интерпретируется обычным образом на числах и ложен, если хоть один его аргумент не число ( мы будем для него использовать стандартную форму записи x <= y вместо <=(x,y)). Остальные предикаты зададим перечислением пар, на которых они истинны:

живут_рядом = { (ольга,петр), (петр, ольга), (иван, джон), (джон, иван), (мария, ольга), (ольга, мария) }

родственники = { (ольга,петр), (петр, ольга), (джон, петр), (петр, джон), (ольга, джон), (джон, ольга), (иван, мария), (мария, иван) }.

Пусть множество переменных Var= {x, y, z, i, n, k, ...} и состояние определяет их значения следующим образом:

Определим значения некоторых термов на

Рассмотрим теперь введенные выше формулы

и

Чтобы оценить первую из них на состоянии мы должны проверить ее подформулу на всех состояниях , совпадающих с на всех переменных кроме, быть может, x. Если - число или то , а вся импликация = 1. Если же , т. е , то легко проверить, что для каждого из этих значений x найдется такое значение , для которого выполнено , и что имеет место . Например, если , то в качестве следует взять иван. Таким образом формула будет иметь значение 1 на состоянии , совпадающем с на всех переменных кроме, быть может, y. Следовательно, мы показали, что . Заметим, что так как - замкнутая формула, то на самом деле, мы показали, что она имеет значение 1 на любомсостоянии системы , т.е. что .

Для оценки значения нужно постараться найти такого человека , для которого выполняется хотя бы одна из подформул или (напомним, что ). Из определения предиката родственники в следует, что первая из этих формул не выполняется ни для какого . Что касается второй подформулы, то она верна при или , поскольку оба они не являются соседямипетр а и имеют зарплату >= 35. Таким образом, .

Эквивалентные формулы и нормальные формы С понятием эквивалентности формул мы уже знакомились, когда рассматривали булевы формулы (формулы логики высказываний). Для логики предикатов эквивалентность определяется следующим образом. Определение 7.10. Формулы и сигнатуры называются эквивалентными, если для любой системы этой сигнатуры и любого ее состояния имеет место равенство . В этом случае пишем . Отметим сначала, что все эквивалентности булевых формул, приведенные в лекции 4: законы ассоциативности и коммутативности для конъюнкции и дизъюнкции, законы дистрибутивности, двойного отрицания, де Моргана и др., остаются справедливыми и для формул логики предикатов. Поэтому и для них мы примем соглашение об упрощенной записи, которое позволяет опускать скобки в формулах, содержащих только операции конъюнкции или только операции дизъюнкции. Разрешим также опускать внешние скобки в формулах, внешняя функция которых или Например, формула может быть упрощенно записана как . Для логики предикатов остается справедливым и правило замены эквивалентных подформул: если является подформулой формулы и формула получена из формулы заменой некоторого вхождения на , то . Доказательство этого правила получается индукцией по определению значения формулы на состоянии системы (см. задачу 7.8). Новые эквивалентности связаны с кванторами. Теорема 7.1. Для любых формул и таких, что не содержит свободно переменной x, имеют место следующие эквивалентности. Доказательствавсех этих эквивалентностей получаются непосредственно из определения значения формул на состояниях. Рассмотрим, например, первую из них. Для любого состояния имеем . Это значение равно 1 тогда и только тогда, когда или, по определению значения квантора когда найдется такое состояние , совпадающее с внеx, для которого . Но это эквивалентно истинности формулы на состоянии Рассмотрим еще эквивалентности (9) и (10), которые, на первый взгляд, могут удивить - квантор всеобщности превращается при вынесении за скобки в квантор существования и наоборот. Доказательство (9) получается с помощью булевых эквивалентностей и пунктов (1) и (4) настоящей теоремы: Эквивалентность (10) доказывается аналогично. Останутся ли эквивалентности (2) - (8) справедливыми, если мы не будем требовать, чтобы формула не содержала свободных вхождений переменной x? Нет! Рассмотрим, например, для арифметической сигнатуры две формулы и . Тогда формула , представляющая левую часть эквивалентности (3) истинна насостоянии в котором $ (x)=0.$ А формула , представляющая ее правую часть, ложна на всех состояниях. Чтобы корректно вынести за скобки квантор в формуле , в которой содержит x свободно, нужно предварительно переименоватьсвязанную переменную в . Это позволяют сделать следующие эквивалентности, справедливость которых следует из предложения 7.1. Лемма 7.1.О замене связанных переменных. , где не содержит y, а получается заменой всех свободных вхождений x в на y. , где не содержит y, а получается заменой всех свободных вхождений x в на y. Используя эту лемму, можем получить следующую цепочку эквивалентностей: . В общем случае, если переменная y не входит в и в , справедлива эквивалентность . Определение 7.11. Формула вида , где - бескванторная формула, а каждый символ Qi - это один из кванторов или называется предваренной (или пренексной)нормальной формой. Последовательность кванторов Q1 x1 Q2 x2 ... Qn xn называется ее приставкой, а бескванторная формула - матрицей этой нормальной формы. Теорема 7.2. О предваренной форме. Для всякой формулы существует формула в предваренной нормальной форме такая, что . Доказательство следует из теоремы 7.1 и леммы 7.1. Мы приведем его в виде процедуры, которая позволяет построить предваренную форму по исходной формуле Процедура состоит из двух этапов. На первом этапе, используя лемму 7.1, заменим все связанные переменные в на новые так, чтобы разные кванторы связывали разные переменные и имена всех связанных переменных не пересекались с именами свободных переменных формулы На втором этапе используя эквивалентности (3) - (10) теоремы 7.1 поочередно выносим кванторы за скобки. Именно, последовательно заменяем каждую подформулу вида , где на эквивалентную формулу , и каждую подформулу вида на формулу , где при и при . Если после этого вынесенный квантор стоит сразу после операции отрицания то, применяя эквивалентности (1), (2), проносим отрицание в глубь формулы. Заметим, что порядок выноса кванторов определен неоднозначно, в зависимости от него в результате могут получиться эквивалентные формулы с разными кванторными приставками. Пример 7.1. Рассмотрим пример. Пусть . Ее свободные переменные: x, y и z (у x и y имеются также и связанные вхождения). Выберем в качестве новых имен для связанных переменных u, v и w и заменим ими "старые" связанные переменные. Получим эквивалентную формулу . На следующем этапе выносим кванторы за скобки (в качестве индексов у знаков эквивалентности указаны номера применяемых эквивалентностей): Далее можно упрощать матрицу формулы, используя известные эквивалентности булевой логики. В данном случае получим формулу