Язык логики предикатов

Утверждения о свойствах объектов и отношениях между ними

Утверждения, которые можно сформулировать с помощью средств логики высказываний (пропозициональной логики) всегда относятся к конкретным свойствам конкретных предметов, объектов, ситуаций. Мы уже сталкивались с примерами таких утверждений: "Сегодня идет дождь", "Вася любит Олю", "Если А - преступник, то В - не виновен", "Если цена на нефть растет и страна продает нефть, то растут и доходы ее бюджета" и т.п. Эти утверждения строятся из элементарных высказываний (пропозициональных переменных) с помощью логических связок (операций). Например, последнее из приведенных утверждений может быть формально записано как $$(X \wedge Y) \to Z$$, где X, Y и Z - это переменные, обозначющие, соответственно, высказывания " цена на нефть растет", "страна продает нефть" и "растут и доходы бюджета".

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

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

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

Свойства: зеленый, тяжелый, голубоглазый, победный, девятиэтажный, деревянный, отличник, ...

Отношения: ... является братом ..., ... занимает должность ... с зарплатой ..., ... больше чем ..., ... находится внутри ..., ... любит ..., ... имеет цвет ..., ... случится после ..., ... владеет ..., и т.п.

Функции: отец ..., лучший_ друг ..., вдвое_больший_ чем ..., сумма ... и ..., группа_студента ..., самый_любимый_кинофильм ..., ...

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

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

" Два умножить на три равно шесть"

Здесь объекты: два, три и шесть; функция: умножить, отношение: равно.

"Все бармаглоты живут в зеленых домах"

Объекты: бармаглоты, дома; свойство: зеленый; отношение: жить_в.

"Некоторые предприятия в Твери являются банкротами"

Объекты: Тверь, предприятия; свойство: банкрот; отношение: "быть" ("являться").

С формализацией этих понятий мы уже знакомы: объекты - это множества; свойства - подмножества; а отношения и функции имеют обычный математический смысл.

Напомним некоторые определения из лекции 1. Декартовым (прямым) произведением множеств A1, ... , An называется множество последовательностей длины n ( n -ок)

$$A_1 \times \ldots A_n =\{ <a_1,\ldots, a_n>\ |\ a_1 \in A_1, \ldots , a_n \in A_n \} .$$

Если A1= ... =An=A, то A1 \times ... An называется декартовой (прямой) степенью множества A и обозначается через An. Пусть A0 - это множество, состоящее из одной пустой последовательности $$\varepsilon$$ длины 0.

n -местным (или n -арным) отношением на множествах A1,... , An называется любое подмножество $$P \subseteq A_{1}\timesx \dots \setminus \times A_{n}$$. Поэтому понятие свойства (подмножества) совпадает с понятием одноместного отношения. Отношение $$f \subseteq A_{1} \times \dots \times A_{n} \times B$$ называется n -местной (или n -арной) функцией из A1 x ... x An в B, если оно для каждого набора аргументов $$<a_{1},\dots , a_{n}>, a_{i}\in A_{i}$$, содержит не более одного набора вида <a1,..., an, b>. В этом случае пишем f(a1, ..., an) =b.

С каждым отношением $$P \subseteq A_{1} \times \dots \times A_{n}$$ можно связать его характеристическую функцию, которую мы будем обозначать той же буквой,

$$P(x_1,\ldots, x_n)= \left\{ \begin{array}{ll} 1, \mbox{ если} <x_1, \ldots, x_n >} \in P \\ 0, \mbox{ в противном случае.} \end{array} \right.$$

Как обычно, будем ассоциировать 1 с логическим значением "истина", а 0 - со значением "ложь". Такие характеристические функции отношений будем называть n -местными предикатами (используются также термины: предикат размерности n, n -арный предикат, предикат валентности n ) и говорить об их истинности или ложности на соответствующих наборах аргументов. Таким образом, предикат - это отображение, сопоставляющее каждому набору своих аргументов одно из логических значений: 1 или 0. Если потребуется, размерность предиката будет указываться соответствующим индексом вверху: P(n) будет означать, что у предиката P имеется n аргументов.

Мы будем рассматривать также функции и предикаты размерности нуль. Множество A0 одноэлементно (содержит единственную последовательность длины 0 ). Поэтому функции из A0 в A отождествляются с элементами множества A. Такие функции называются константными или просто константами. Предикатов размерности нуль ровно два: 1 (истина) и 0 (ложь).

Вообще говоря, типы объектов-аргументов предиката, т.е. типы множеств A1, ... , An, могут быть различными. Например, у предиката выпускает(Предприятие, Товар), определяющего связь между предприятиями и выпускаемыми ими товарами, первым аргументом является название предприятия, а вторым - одного из выпускаемых им товаров. Но далее для простоты мы будем рассматривать только предикаты и функции, все аргументы которых принадлежат одному множеству объектов A. Это ограничение не очень существенно. Можно выделять в A объекты нужных типов с помощью свойств - одноместных предикатов. В нашем случае выражение выпускает(X,Y) можно уточнить, введя предикаты предприятие(1) и товар(1) и записав конъюнкцию:

$$предприятие(X) \wedge товар(Y) \wedge выпускает(X,Y)$$.

Язык логики предикатов

В определениях формальных языков, таких, как логические языки или языки программирования, выделяют два основных аспекта: синтаксис и семантику. Синтаксис \index{Синтаксис} определяет алфавит, из символов которого строятся выражения языка, и правила, выделяющие из множества всех слов в данном алфавите правильно построенные выражения. Для логических языков такие выражения обычно называются формулами, а для языков программирования - программами. Семантика \index{Семантика} занимается определением смысла, значения этих выражений. Для формул большинства логических языков значением является одно из истиностных значений: 1 (истина) или 0 (ложь), которое приписывается формуле в зависимости от интерпретации входящих в нее символов языка. Например, значения формул логики высказываний зависят от значений входящих в них булевых переменных. Значения формул определяемой в этом параграфе логики предикатов будут зависеть от интерпретации предикатов и функций языка, а также от значений входящих в эти формулы переменных.

Синтаксис: формулы логики предикатов

Формулы языка логики предикатов включают в себя символы (имена) предикатов из некоторого Множества $${\bf P}= \{ P_1^{(n_1)}, P_2^{(n_2)},\ldots , P_k^{(n_k)}, \ldots \}$$, символы (имена) функций из некоторого множества $${\bf F}= \{ f_1^{(m_1)}, f_2^{(m_2)}, \ldots , f_j^{(m_j)},\ldots \}$$, символы (имена) констант из некоторого множества C={ c1, c2, ... }, логические связки $$\{ \neg , \wedge , \vee , \to \}$$, кванторы всеобщности $$\forall$$ и существования $$\exists$$ и вспомогательные символы (скобки, запятые). Первые три множества образуют сигнатуру языка: $$\Sigma = < P, F, C>$$. \index{Сигнатура} Зафиксируем некоторое счетное множество объектных переменных Var (такие переменные также называют предметными или индивидными ). Они предназначены для обозначения элементов множества (объектов), на котором определены функции и предикаты ; обычно в таком качестве используют латинские буквы x, y,z,u,v,w, xi, yj, zk и т.п. В каждой формуле будет использоваться конечное число переменных, так что счётного набора переменных нам хватит. Чтобы не возникла путаница, будем считать, что переменные отличны от всех имен констант, функций и предикатов.

Определим понятие терма данной сигнатуры $$\Sigma.$$

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

Объектная переменная из Var есть терм.

Символ константы из C есть терм.

Если t1,...,tk - термы, а f(k) - символ функции из F, то f(t1,...,tk) есть терм.

Термы, не содержащие переменных, назовем замкнутыми.

Термы служат для задания объектов. Замкнутые термы задают объекты непосредственно.

Пример 7.1. Пусть F={отец(1), лучший_друг(1), зарплата(1), + (2)}, а C= {"Петр", "Джон", "Ольга", 0, 1, 2, ... }.

Тогда самый простой способ задать объект - это указать соответствующую константу, например, "Петр", "Джон", 0, 1, 47, .... Терм +(17, 25) задает объект 42, терм лучший_ друг(отец("Петр" ) ) задает объект - лицо, являющееся лучшим другом отца объекта "Петр", а терм зарплата(лучший_ друг(отец("Петр") ) ) задает объект-число, представляющее зарплату этого лица. Значениями переменных также являются объекты. Поэтому термы с переменными задают конкретные объекты при подстановке значений вместо переменых. Приведем еще несколько примеров термов данной сигнатуры: x, отец (x), зарплата(лучший_ друг(отец(отец(z)))), +(зарплата(лучший_ друг(отец(z)) ), +(зарплата ("Ольга" ), 1000)), отец(5), +(отец("Ольга" ), 1000)) . Отметим, что последние два терма построены в соответствии с нашими правилами, но неясно, какие объекты они могут задавать. Это зависит от определения функции отец на числах и функции + на парах аргументов вида (Лицо, Число). Часто во множество объектов включают специальный объект "ОШИБКА", который является значением функций на некорректных аргументах.

Выражения x +10, отец ("Джон", "Петр"), +(100)}, лучший_друг("Мария") термами данной сигнатуры не являются. (Определите почему.)

Определение 7.2. Атомная формула.

Если t1 и t2 - термы, то выражение (t1 = t2) является атомной формулой.

Любой предикатный 0 -местный символ из P является атомной формулой.

Если P(k) (k >= 1) - предикатный k -местный символ из P, а t1,...,tk - термы, то выражение P(t1,...,tk) является атомной формулой.

Пример 7.2. Рассмотрим сигнатуру $$\Sigma _{1} = < P, F, C>$$, в которой P= { живут_рядом(2), сын(2), дочь(2), родственники(2), человек(1), число(1), <= (2)}, а функции F и константы C определены в примере выше.

Тогда следующие выражения являются атомными формулами: "Джон" = "Петр", "Петр" = 6, отец("Ольга") = "Петр", +(3,5) = +(1, +(6,1)), зарплата(лучший_ друг(отец(z)) = 5000}, живут_рядом("Джон","Ольга"), сын( "Джон","Ольга"), дочь("Ольга", x), родственники(лучший_ друг("Джон"), отец( x)) и т.п.

Формулы логики предикатов строятся по таким правилам:

Определение 7.3. Формула.

Всякая атомная формула есть формула.

Если $$\phi$$ - формула, то $$\neg \varphi$$ - формула.

Если $$\phi$$ и $$\psi$$ - формулы, то выражения $$(\varphi \wedge \psi )$$, $$(\varphi \vee \psi )$$, $$(\varphi \to \psi )$$ также являются формулами.

Если $$\phi$$ - формула, а $$x \in Var$$ - объектная переменная, то выражения $$\forall x \varphi$$ и $$\exists x \varphi$$ являются формулами (в этом случае $$\forall x\varphi$$ и $$\exists x\varphi$$ называются областью действия квантора $$\forall x$$ или $$\exists x$$ соответственно).

Понятие подформулы для формул логики предикатов определяется естественным образом. Во-первых, сама формула является своей подформулой. Во-вторых, если формула имеет вид $$\neg \varphi$$, $$\forall x \varphi$$ или $$\exists x \varphi$$, то ее подформулами также являются все подформулы формулы $$\phi,$$ а если она имеет вид $$(\varphi \wedge \psi )$$, $$(\varphi \vee \psi )$$ или $$(\varphi \to \psi )$$, то ее подформулами также являются все подформулы формул $$\phi$$ и $$\psi.$$

Определим также понятия связанных и свободных переменных формулы. Вхождение переменной x в формулу $$\phi$$ называется связанным, если оно входит в область действия некоторого квантора $$\forall x$$ или $$\exists x$$ . В противном случае, оно называется свободным. Квантор $$\forall x$$ ( $$\exists x$$ ) связывает в формуле $$\forall x \varphi$$ ( $$\exists x \varphi$$ ) все свободные вхождения переменной x в подформулу $$\phi.$$

Пусть в некоторой сигнатуре имеются два двуместных предиката P(2), Q(2). Тогда в формуле

$$\forall x (\exists x(P(x,y) \wedge \forall y Q( x, y )) \vee \neg P(x,x))$$

оба вхождения x в подформулу $$(P(x,y) \wedge \forall y Q( x, y ))$$ связаны квантором $$\exists x$$, первое вхождение y является свободным, а второе - связано квантором $$\forall y$$. Оба вхождения x в подформулу $$\neg P(x,x)$$ связаны квантором $$\forall x$$.

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

Пример 7.3. Рассмотрим примеры формул в сигнатуре $$\Sigma _{1}$$ из примера 7.2:

$$\varphi_1= \varphi_1= \forall x( \textit{человек(x)} \rightarrow \exists y (\textit{человек(y)} \wedge \textit{живут\_рядом( x,y ) ) }$$

В этой формуле все вхождения переменных x и y являются связанными и, следовательно, $$\varphi _{1}$$ - замкнутая формула. Содержательно, она утверждает, что у всякого человека имется человек-сосед. Понятно, что истинность этого утверждения не зависит от имен переменных, использованных в формуле.

$$\varphi_2= \exists y[\textit{человек(y)} \wedge( \forall x \ \textit{родственники( x, y )}\vee \\ \vee \neg \textit{живут\_рядом}( x,y ) \wedge (\textit{зарплата(y)} \geq 35) )]$$

В формуле $$\varphi _{2}$$ все вхождения переменной y являются связанными, первое вхождение x также связано, а второе вхождение x свободно, так как не входит в область действия квантора $$\forall x$$. Таким образом x в $$\varphi _{2}$$ является связанной и свободной. Эта формула утверждает что имеется такой человек, который состоит в родственных отношениях со всеми или не живет рядом с x и имеет зарплату >= 35. Ясно, что истинность этой формулы зависит от значения свободной переменной x.

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

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

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

Определенную таким образом систему будем обозначать как $$\mathcal{A}= <A; \Sigma >$$, используя для предикатов и функций системы их имена из сигнатуры $$\Sigma.$$

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

Определение 7.5. Состоянием (оценкой) системы $$\mathcal{A}=<A; \Sigma>$$ назывется отображение $$\sigma : Var \to A$$, которое каждой переменной $$x \in Var$$ сопоставляет ее значение в данном состоянии $$\sigma (x)$$.

Имея систему и состояние, можно говорить о значениях термов и формул на данном состоянии системы. Мы будем считать, что в определениях ниже зафиксирована некоторая система $$\mathcal{A}=<A; \Sigma>$$, будем через $$\sigma (t)$$ и $$\sigma (\varphi )$$ обозначать значение терма t и формулы $$\phi$$ на состоянии $$\sigma$$ системы $$\mathcal{A}$$. И то, и другое определяется индукцией по построению термов и формул соответственно.

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

Для переменной $$x \in Var$$ $$\sigma (x)$$ уже определено в состоянии $$\sigma.$$

Если t является константой $$c \in C$$, то $$\sigma (c)$$ не зависит от $$\sigma$$ и равно значению этой константы при данной интерпретации

(напомним, в интерпретации каждой константе сопоставлен некоторый элемент основного множества).

Если t имеет вид f(t1,...,tm), где $$f^{(m)} \in F$$ - символ m - местной функции, а t1,...,tm - термы, то $$\sigma (t)$$ есть $$f_{A}(\sigma (t_{1}),\dots , \sigma (t_{m}))$$, где fA есть функция, соответствующая символу f в системе $$\mathcal{A}$$.

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

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

Если $$\varphi =(t_{1} = t_{2})$$, где t1 и t2 - термы, то $$\sigma (\varphi )=1$$, если $$\sigma (t_{1})=\sigma (t_{2})$$, и $$\sigma (\varphi )=0$$, если $$\sigma (t_{1}) \ne \sigma (t_{2})$$.

Пусть $$\varphi = P^{(0)}$$ - 0 -местный предикатный символ из P и PA - это 0 -местный предикат, сопоставленный ему в $$\mathcal{A}$$. Тогда $$\sigma (P)= P_{A} \in \{ 1,0\}$$.

Пусть $$\varphi = P(t_{1},\setminus dots,t_{k})$$, где P(k) - предикатный k -местный символ из P, t1,...,tk - термы, а PA - это k -местный предикат, сопоставленный P(k) в $$\mathcal{A}$$. Тогда

$$\sigma(P(t_1,\dots,t_k)) = P_A(\sigma(t_1), \ldots , \sigma(t_k)).$$

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

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

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

Если $$\varphi = \neg \varphi _{1}$$, то $$\sigma (\varphi ) = \neg \sigma (\varphi _{1})$$.

Если $$\phi$$ имеет одну из форм $$(\theta \wedge \psi )$$, $$(\theta \vee \psi )$$ или $$(\theta \to \psi )$$, то значение $$\sigma (\varphi )$$

равно значению $$\sigma (\theta ) \wedge \sigma (\psi ), \sigma (\theta ) \vee \sigma (\psi )$$ или $$\sigma (\theta ) \to \sigma (\psi )$$, соответственно.

Если $$\varphi = \forall x \psi$$, то $$\sigma (\varphi ) = 1$$, если $$\sigma '(\psi ) =1$$ для $$\sigma '$$, которое может отличаться от $$\sigma$$ только значением переменной x, т.е. такого $$\sigma '$$, что $$\sigma '(y) = \sigma (y)$$ при $$y \ne x$$, иначе $$\sigma (\varphi ) = 0$$.

Если $$\varphi = \exists x \psi$$, то $$\sigma (\varphi ) = 1$$, если существует такое состояние $$\sigma '$$, которое может отличаться от $$\sigma$$ только значением переменной x, для которого $$\sigma '(\psi ) =1$$, иначе $$\sigma (\varphi ) = 0$$.

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

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

Предложение 7.1. Пусть $$\mathcal{A}$$ - система сигнатуры $$\Sigma,$$ $$\phi$$ - формула той же сигнатуры, $$V(\varphi )$$ - множество ее свободных переменных. Тогда для любых двух состояний $$\mathcal{A}$$ $$\sigma _{1}$$ и $$\sigma _{2}$$, совпадающих на $$V(\varphi )$$ (т.е. таких, что для всякой $$x \in V(\varphi )$$ $$\sigma _{1}(x) = \sigma _{2}(x)$$ ), имеет место равенство $$\sigma _{1}(\varphi ) = \sigma _{2}(\varphi )$$.

Доказательство получается индукцией по построению формулы $$\phi.$$ Действительно, утверждение, очевидно, справедливо для значений термов и атомных формул. Из предположения о его справедливости для формул $$\varphi _{1}$$ и $$\varphi _{2}$$ его легко перенести на формулы вида $$\neg \varphi _{1}$$ и $$\varphi _{1}$$ $$\circ$$ $$\varphi _{2}$$, где $$\circ$$ $$\in \{ \wedge , \vee , \to \}$$. ( Проведите это рассуждение самостоятельно!). Пусть теперь $$\varphi = Qx \varphi _{1}$$, где $$Q \in \{ \forall , \exists \}$$, а $$x \in Var$$. Тогда $$V(\varphi ) = V(\varphi _{1} ) \setminus \{ x\}$$. Пусть $$\sigma _{1}$$ и $$\sigma _{2}$$ - состояния, совпадающие на $$V(\varphi )$$. Рассмотрим множества состояний, отличающихся от них только на x: $$\sigma ^{x}_{1}=\{ \sigma ' | \sigma '(y)=\sigma _{1}(y) \ при \ y \ne x\}$$ и $$\sigma ^{x}_{2}\} ==\{ \sigma '' | \sigma ''(y)=\sigma _{2}(y)\ при \ y \ne x \}$$. Для каждого состояния $$\sigma ' \in \sigma ^{x}_{1}$$ в $$\sigma ^{x}_{2}$$ имеется состояние $$\sigma ''$$, совпадающее с $$\sigma '$$ на $$V(\varphi _{1} )$$. Верно и обратное. Поэтому по предположению индукции в $$\sigma ^{x}_{1}$$ имеется состояние $$\sigma '$$, для которого $$\sigma '(\varphi _{1}) = 1$$ тогда и только тогда, когда в $$\sigma ^{x}_{2}\}$$ имеется состояние $$\sigma ''$$, для которого $$\sigma '' (\varphi _{1}) = 1$$. Отсюда и из определения значения формулы $$\varphi = Qx \varphi _{1}$$ следует, что $$\sigma _{1}(\varphi ) = \sigma _{2}(\varphi )$$.

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

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

Определение 7.9. Формула $$\phi$$ называется истинной на системе $$\mathcal{A}$$, если для любого состояния $$\sigma$$ этой системы $$\sigma (\varphi ) = 1$$. В этом случае пишем $$\mathcal{A} \models \varphi$$.

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

Пример 7.4. В качестве примера рассмотрим следующую систему $$\mathcal{A}_1= <A_1; \Sigma_1>$$ для определенной выше примере 7.2 сигнатуры $$\Sigma _{1}$$.

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

x	отец(x)	лучший_друг(x)	зарплата(x)
петр	иван	джон	20
джон	петр	ольга	35
ольга	джон	петр	20
иван	$$\infty$$	мария	40
мария	иван	петр	30

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

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

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

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

$$\sigma(x)=\textit{петр}, \sigma(y)=\textit{ольга}, \sigma(z)=\textit{иван}, \sigma( i)= 1, \sigma( n)= 30, \sigma( k)= 2.$$

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

$$\sigma(+(7, +(2, 6)) = 15,\sigma(+(i, +(2, n)) = 33, \\\sigma(\textit{отец( лучший\_друг( мария))) = иван , }\\\sigma(\textit{зарплата(лучший\_друг(отец(x))) = 30,}\\\sigma(+(\textit{зарплата}(y), k))= 22,\ \ \sigma(+(x, k))= \infty.$$

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

$$\varphi_1= \forall x( \textit{человек(x)} \rightarrow \exists y (\textit{человек(y)} \wedge \textit{живут\_рядом( x,y ) ) }$$ и

$$\varphi_2= \exists y[\textit{человек(y)} \wedge( \forall x \ \textit{родственники( x, y )} \vee \\ \vee (\neg \textit{живут\_рядом}( x,y ) \wedge ( 35 \leq \textit{зарплата(y)}) )].$$

Чтобы оценить первую из них на состоянии $$\sigma,$$ мы должны проверить ее подформулу $$(человек(x) \to \exists y (человек(y) \wedge живут\_ рядом( x,y ))$$ на всех состояниях $$\sigma '$$, совпадающих с $$\sigma$$ на всех переменных кроме, быть может, x. Если $$\sigma '(x)$$ - число или $$\infty,$$ то $$\sigma '(человек(x))=0$$, а вся импликация = 1. Если же $$человек(\sigma '(x)) =1$$, т. е $$\sigma '(x) \in \{ петр, джон, ольга, иван, мария\}$$, то легко проверить, что для каждого из этих значений x найдется такое значение $$\sigma ''(y)$$, для которого выполнено $$человек(\sigma ''(y))$$, и что имеет место $$живут\_ рядом( \sigma '(x),\sigma ''(y) )$$. Например, если $$\sigma '(x) = джон$$, то в качестве $$\sigma ''(y)$$ следует взять иван. Таким образом формула $$(человек(y) \wedge живут\_рядом( x,y ) )$$ будет иметь значение 1 на состоянии $$\sigma ''$$, совпадающем с $$\sigma '$$ на всех переменных кроме, быть может, y. Следовательно, мы показали, что $$\sigma ( \varphi _{1}) = 1$$. Заметим, что так как $$\varphi _{1}$$ - замкнутая формула, то на самом деле, мы показали, что она имеет значение 1 на любом состоянии системы $$\mathcal{A}_1$$, т.е. что $$\mathcal{A}_1 \models \varphi_1$$.

Для оценки значения $$\sigma ( \varphi _{2})$$ нужно постараться найти такого человека $$\tilde{y}$$, для которого выполняется хотя бы одна из подформул $$\forall x \ \textit{родственники}( x, \tilde{y} )$$ или $$(\neg \textit{живут\_рядом(петр} ,\tilde{y} )$$ $$\wedge (\textit{зарплата}(\tilde{y}) \geq 35) )$$ (напомним, что $$\sigma (x) = петр$$ ). Из определения предиката родственники в $$\mathcal{A}_1$$ следует, что первая из этих формул не выполняется ни для какого $$\tilde{y}$$. Что касается второй подформулы, то она верна при $$\tilde{y} = иван$$ или $$\tilde{y} = джон$$, поскольку оба они не являются соседями петр а и имеют зарплату >= 35. Таким образом, $$\sigma (\varphi _{2}) = 1$$.

Эквивалентные формулы и нормальные формы

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

Определение 7.10. Формулы $$\phi$$ и $$\psi$$ сигнатуры $$\Sigma$$ называются эквивалентными, если для любой системы $$\mathcal{A}$$ этой сигнатуры и любого ее состояния $$\sigma$$ имеет место равенство $$\sigma (\varphi ) = \sigma (\psi )$$. В этом случае пишем $$\varphi \equiv \psi$$.

Отметим сначала, что все эквивалентности булевых формул, приведенные в лекции 4: законы ассоциативности и коммутативности для конъюнкции и дизъюнкции, законы дистрибутивности, двойного отрицания, де Моргана и др., остаются справедливыми и для формул логики предикатов. Поэтому и для них мы примем соглашение об упрощенной записи, которое позволяет опускать скобки в формулах, содержащих только операции конъюнкции или только операции дизъюнкции. Разрешим также опускать внешние скобки в формулах, внешняя функция которых $$\wedge , \vee$$ или $$\to.$$ Например, формула $$(\forall x P(x,y) \to ((\exists y P(y,y) \vee Q(x,y,z)) \vee R(x, u)))$$ может быть упрощенно записана как $$\forall x P(x,y) \to (\exists y P(y,y) \vee Q(x,y,z) \vee R(x, u))$$.

Для логики предикатов остается справедливым и правило замены эквивалентных подформул:

если $$\psi$$ является подформулой формулы $$\varphi , \psi \equiv \psi _{1}$$ и формула $$\varphi _{1}$$ получена из формулы $$\phi$$ заменой некоторого вхождения $$\psi$$ на $$\psi _{1}$$, то $$\varphi \equiv \varphi _{1}$$.

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

Новые эквивалентности связаны с кванторами.

Теорема 7.1. Для любых формул $$\varphi (x)$$ и $$\psi$$ таких, что $$\psi$$ не содержит свободно переменной x, имеют место следующие эквивалентности.

$$\begin{array}{ll} (1)\ \neg \forall x \varphi(x)\ \equiv\ \exists x \neg \varphi(x), (2)\ \neg \exists x \varphi(x)\ \equiv\ \forall x \neg \varphi(x),\\ (3)\ (\psi \wedge \forall x \varphi(x))\ \equiv\ \forall x (\psi \wedge \varphi(x)), (4)\ (\psi \wedge \exists x \varphi(x))\ \equiv\ \exists x (\psi \wedge \varphi(x)),\\ (5)\ (\psi \vee \forall x \varphi(x))\ \equiv\ \forall x (\psi \vee \varphi(x)) , (6)\ (\psi \vee \exists x \varphi(x))\ \equiv\ \exists x (\psi \vee \varphi(x)),\\ (7)\ (\psi \rightarrow \forall x \varphi(x))\ \equiv\ \forall x (\psi \rightarrow \varphi(x)) , (8)\ (\psi \rightarrow \exists x \varphi(x))\ \equiv\ \exists x (\psi \rightarrow \varphi(x)),\\ (9)\ (\forall x \varphi(x) \rightarrow \psi)\ \equiv\ \exists x (\varphi(x) \rightarrow \psi) , (10)\ ( \exists x \varphi(x) \rightarrow \psi)\ \equiv\ \forall x (\varphi(x) \rightarrow \psi) \end{array}$$

Доказательства всех этих эквивалентностей получаются непосредственно из определения значения формул на состояниях. Рассмотрим, например, первую из них. Для любого состояния $$\sigma$$ имеем $$\sigma (\neg \forall x \varphi (x))\setminus \equiv \setminus \neg \sigma ( \forall x \varphi (x))$$. Это значение равно 1 тогда и только тогда, когда $$\sigma ( \forall x \varphi (x))= 0$$ или, по определению значения квантора $$\forall,$$ когда найдется такое состояние $$\sigma '$$, совпадающее с $$\sigma$$ вне x, для которого $$\sigma '( \varphi (x))= 0$$. Но это эквивалентно истинности формулы $$\exists x \neg \varphi (x)$$ на состоянии $$\sigma.$$

Рассмотрим еще эквивалентности (9) и (10), которые, на первый взгляд, могут удивить - квантор всеобщности превращается при вынесении за скобки в квантор существования и наоборот. Доказательство (9) получается с помощью булевых эквивалентностей и пунктов (1) и (4) настоящей теоремы:

$$(\forall x \varphi(x) \rightarrow \psi)\ \equiv\ (\neg \forall x \varphi(x) \vee \psi)\ \equiv\ (\exists x \neg \varphi(x) \vee \psi) \equiv \\\equiv \exists x (\neg \varphi(x) \vee \psi)\ \equiv\ \exists x (\varphi(x) \rightarrow \psi)$$

Эквивалентность (10) доказывается аналогично.

Останутся ли эквивалентности (2) - (8) справедливыми, если мы не будем требовать, чтобы формула $$\psi$$ не содержала свободных вхождений переменной x? Нет! Рассмотрим, например, для арифметической сигнатуры две формулы $$\varphi = (x=x)$$ и $$\psi = (x=0)$$. Тогда формула $$(\psi \wedge \forall x \varphi )= ((x=0) \wedge \forall x (x=x))$$, представляющая левую часть эквивалентности (3) истинна на состоянии $$\sigma,$$ в котором $ $$\sigma$$ (x)=0.$ А формула $$\forall x ((x=0) \wedge (x=x))$$, представляющая ее правую часть, ложна на всех состояниях. Чтобы корректно вынести за скобки квантор в формуле $$(\psi (x) \wedge \forall x \varphi (x) )$$, в которой $$\psi (x)$$ содержит x свободно, нужно предварительно переименовать связанную переменную в $$\forall x \varphi (x)$$. Это позволяют сделать следующие эквивалентности, справедливость которых следует из предложения 7.1.

Лемма 7.1.О замене связанных переменных.

$$\forall x \varphi (x) \equiv \forall y \varphi (y)$$, где $$\varphi (x)$$ не содержит y, а $$\varphi (y)$$ получается заменой всех свободных вхождений x в $$\varphi (x)$$ на y.

$$\exists x \varphi (x) \equiv \setminus \exists y \varphi (y)$$, где $$\varphi (x)$$ не содержит y, а $$\varphi (y)$$ получается заменой всех свободных вхождений x в $$\varphi (x)$$ на y.

Используя эту лемму, можем получить следующую цепочку эквивалентностей: $$((x=0) \wedge \forall x (x=x)) \equiv ((x=0) \wedge \forall y (y=y)) \equiv \forall y ((x=0) \wedge (y=y))$$. В общем случае, если переменная y не входит в $$\psi (x)$$ и в $$\varphi (x)$$, справедлива эквивалентность $$(\psi (x) \wedge \forall x \varphi (x) ) \equiv \forall y (\psi (x) \wedge \varphi (y) )$$.

Определение 7.11. Формула вида $$Q_{1} x_{1} Q_{2} x_{2} \dots Q_{n} x_{n} \varphi$$, где $$\phi$$ - бескванторная формула, а каждый символ Qi - это один из кванторов $$\forall$$ или $$\exists,$$ называется предваренной (или пренексной) нормальной формой. Последовательность кванторов Q1 x1 Q2 x2 ... Qn xn называется ее приставкой, а бескванторная формула $$\phi$$ - матрицей этой нормальной формы.

Теорема 7.2. О предваренной форме.

Для всякой формулы $$\phi$$ существует формула $$\psi$$ в предваренной нормальной форме такая, что $$\varphi \equiv \psi$$.

Доказательство следует из теоремы 7.1 и леммы 7.1. Мы приведем его в виде процедуры, которая позволяет построить предваренную форму $$\psi$$ по исходной формуле $$\phi.$$ Процедура состоит из двух этапов. На первом этапе, используя лемму 7.1, заменим все связанные переменные в $$\phi$$ на новые так, чтобы

разные кванторы связывали разные переменные и

имена всех связанных переменных не пересекались с именами свободных переменных

формулы $$\phi.$$

На втором этапе используя эквивалентности (3) - (10) теоремы 7.1 поочередно выносим кванторы за скобки. Именно, последовательно заменяем каждую подформулу вида $$(\varphi _{1} \hat{} Qz \varphi _{2})$$, где $$Q \in \{ \forall , \exists \} , \hat{} \in \{ \wedge , \vee , \to \}$$ на эквивалентную формулу $$Qz(\varphi _{1}\hat{} \varphi _{2})$$, и каждую подформулу вида $$(Qz\varphi _{1} \to \varphi _{2})$$ на формулу $$Q'z(\varphi _{1} \to \varphi _{2})$$, где $$Q' = \exists$$ при $$Q= \forall$$ и $$Q'= \forall$$ при $$Q = \exists$$. Если после этого вынесенный квантор стоит сразу после операции отрицания $$\neg,$$ то, применяя эквивалентности (1), (2), проносим отрицание в глубь формулы. Заметим, что порядок выноса кванторов определен неоднозначно, в зависимости от него в результате могут получиться эквивалентные формулы с разными кванторными приставками.

Пример 7.1. Рассмотрим пример. Пусть $$\varphi = (\exists y P(x,y) \wedge \neg (\forall x P(x,y) \to \exists x Q(x, z)))$$.

Ее свободные переменные: x, y и z (у x и y имеются также и связанные вхождения). Выберем в качестве новых имен для связанных переменных u, v и w и заменим ими "старые" связанные переменные. Получим эквивалентную формулу $$\varphi _{1} = (\exists u P(x,u) \wedge \neg (\forall v P(v,y) \to \exists w Q(w, z)))$$. На следующем этапе выносим кванторы за скобки (в качестве индексов у знаков эквивалентности указаны номера применяемых эквивалентностей):

$$\varphi_1 \equiv_{(4)} \exists u (P(x,u) \wedge \neg(\forall v P(v,y) \rightarrow \exists w Q(w, z))) \equiv_{(8)} \exists u (P(x,u) \wedge \\ \neg\exists w(\forall v P(v,y) \rightarrow Q(w, z))) \equiv_{(9)} \exists u (P(x,u) \wedge \neg\exists w\exists v (P(v,y) \rightarrow Q(w, z)))\\ \equiv_{(2)(2)}\exists u (P(x,u) \wedge \forall w\forall v \neg(P(v,y) \rightarrow Q(w, z))) \equiv_{(3)(3)} \exists u \forall w \forall v (P(x,u) \wedge\\ \neg(P(v,y) \rightarrow Q(w, z))).$$

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

$$\exists u \forall w \forall v (P(x,u) \wedge P(v,y) \wedge \neg Q(w, z)).$$

Задачи

Следующие четыре задачи относятся к системе \codecal{A}1 из примера 7.4 и ее состоянию $$\sigma : \sigma (x)= петр, \sigma (y)= ольга, \sigma (z)= иван,\sigma ( i)= 1, \sigma ( n)= 30, \sigma ( k)= 2$$.

Задача 7.1. Определите значение $$\sigma _{1}( \varphi _{2})$$ формулы $$\varphi _{2}$$ на состоянии $$\sigma _{1}$$, отличающемся от $$\sigma$$ только значением $$\sigma _{1}(x) = иван$$.

Задача 7.2. Выделите в следующих формулах свободные и связанные вхождения переменных и определите значения этих формул на состоянии $$\sigma$$ системы $$\mathcal{A}_1$$.

$$\varphi _{3} = \forall x \forall z (живут\_ рядом(x, z) \to родственники(x,z))$$

$$\varphi _{4} = \forall x (живут\_ рядом(x, y) \to (отец(x) = иван))$$.

$$\varphi _{5} = \forall u \exists v [живут\_ рядом(u, лучший_{д}руг(v)) \vee \setminus (зарплата(x) \le зарплата(v))]$$

$$\varphi _{6} = \exists v [\neg живут\_ рядом(v, z) \to (зарплата(отец(v) \le n)]$$.

Задача 7.3. Запишите формулы, выражающие следующие свойства системы $$\mathcal{A}_1$$, и проверьте их истинность на этой системе.

Рядом с каждым человеком А живет некто, отец которого является лучшим другом А.

У каждого человека не более одного соседа.

Если у соседа некоторого человека А зарплата больше чем у А, то этот сосед является родственником А.

Есть человек, у которого не менее 2-х детей.

Никто не является лучшим другом для более чем 2-х людей.

Задача 7.4. Запишите формулы, которые истинны на состояниях $$\sigma$$ системы $$\mathcal{A}_1$$,удовлетворяющих следующим условиям.

$$\sigma (x)$$ - человек, зарплата которого больше 20 и не больше 35.

$$\sigma (x)$$ и $$\sigma (y)$$ - это люди, у которых один и тот же лучший друг.

$$\sigma (x)$$ - человек с максимальной зарплатой, равной $$\sigma (n)$$.

$$\sigma (x)$$ - человек, получающий большую зарплату, чем его отец.

Найдите все значения переменных, на которых истинны соответствующие формулы.

Задача 7.5. Арифметикой называется система $$({\bf N}; +^{(2)}, *^{(2)}; 0, 1)$$, где основное множество N={0, 1, 2, ...} - множество натуральных чисел, функции + и * - обычное сложение и умножение, а 0 и 1 - соответствующие числа.

Запишите формулы со свободными переменными из { x, y, z}, которые истинны в арифметике тогда и только тогда, когда

x меньше y ;

x является четным числом;

y является простым числом;

x и y взаимно просты;

z лежит в интервале между x и y ;

сложение (умножение) коммутативно;

существует бесконечно много простых чисел.

Задача 7.6. Представьте каждое из следующих предложений формулой логики предикатов, определив в каждом случае подходящую сигнатуру.

Не все студенты изучают и анализ, и историю.

Только один студент не сдал экзамен по дискретной математике.

Только один студент сдал все экзамены на отлично.

Максимальные баллы, полученные по дискретной математике, превышают максимальные баллы, полученные по информатике.

Каждый, кто не любит всех вегетарианцев, является странным человеком.

Имеется брадобрей, бреющий только тех жителей города, которые не бреются сами.

Политики могут обманывать всех людей некоторое время, они могут обманывать некоторых людей все время, но они не могут обманывать всех людей все время.

Задача 7.7. Напишите формулу логики предикатов, истинной только на всех системах, основное множество которых состоит из одного элемента (2-х , 3-х,..., k элементов).

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

Задача 7.9. Проведите доказательство эквивалентностей (2) - (8).

Задача 7.10. Доказажите следующие эквивалентности, показывающие, что одноименные кванторы можно менять местами:

$$\forall x \forall y \varphi \equiv \forall y \forall x \varphi$$,

$$\exists x \exists y \varphi \equiv \exists y \exists x \varphi$$.

Задача 7.11. Докажите, что разноименные кванторы менять местами нельзя, т.е., что формулы $$\forall x \exists y \varphi$$ и $$\exists x \forall y \varphi$$ не эквивалентны.

Задача 7.12. Приведите к предваренной нормальной форме следующие формулы, считая, что $$\phi$$ и $$\psi$$ - бескванторные.

$$\neg \forall z \neg \forall x \exists y \forall u \varphi$$,

$$\exists x \forall y \psi (x,y) \to \exists x \forall y \psi (x,y)$$,

$$\neg ( \forall x \forall y \varphi (x,y,z) \vee (\forall z \psi (x,z) \wedge \neg \exists y\psi (x,y)))$$.