Математическая логика и теория алгоритмов (120

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

5)α β α β;

6)α β α β.

Утверждения 5 и 6 называются соотношениями Моргана. Из них вытекает следующий важный факт: пусть формула α составлена из атомов A,B,... и связок , ,−; тогда формула α равносильна формуле, полученной из α заменой A,B,... на A,B,... и заменой связок и на и соответственно.

Из этого факта следует простой способ приведения формулы

αк КНФ: нужно рассмотреть формулу α, привести ее к ДНФ, а к

ней применить отрицание − по указанному правилу.

Пример 1.3. Приведем к КНФ формулу α = ABC BC. Имеем

α(A B C)(B C) AB C. Отсюда α (A B)C.

Еще одно применение приведенных формул состоит в следу-

ющем. Если формула содержит в себе связки (стрелки) →,↔, то можно избавиться от них (т. е. обойтись связками −, , ), последовательно применяя правила эквивалентности 3 и 4; этим способом можно получить ДНФ, не прибегая к функциям истинности.

Пример 1.4. Найдем ДНФ для формулы α = A → (B → C), а также для ее отрицания α. Будем преобразовывать не сами формулы, а их функции истинности (в частности, заменим конъюнкции умножениями). Имеем α = A (B C) = A B C. Далее,

α = ABC.

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

Указанные эквивалентности полезны для построения правильных рассуждений (не только в математике). Например, из утверждения 4 следует равносильность высказываний α → β и β → α (оба эти высказывания равносильны высказыванию α β). На этой равносильности основан хорошо известный прием, называемый доказательством от противного. Предположим, Вы желаете доказать, что из α следует β. Эта цель будет достигнута, если Вы докажете, что если нарушено β, то нарушено также α. Разумеется, высказывания α → β и β → α не равносильны; подмена одного другим нередко приводит к ошибкам.

Логическое следование. Говорят, что формула β логически

следует из формул α1,..., αn, если формула α1 ... αn → β есть тавтология (т. е. |= α1 ... αn → β); в этом случае пишут

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

Если от формул αi, β перейти к их функциям истинности (мы обозначаем их так же, как сами формулы), то утверждение (1.2) будет означать, что

для всех значений независимых переменных, через которые выражены функции αi, β.

Таким образом, равенство (1.3) дает простой (иногда громоздкий) способ проверки логического следования (1.2).

Теорема 1.1. Перечисленные ниже утверждения равносильны:

1)α1,..., αn |= β;

2)α1,..., αn, β |= F;

3)α1 ... αn β F;

4)если истинностные функции формул α1,..., αn принима-

ют значение 1 на некотором булевом векторе, то и истинностная функция формулы β принимает на этом векторе значение 1.

Утверждение 4 можно сформулировать так: каждый раз, когда истинны все αi, истинна также β.

Для доказательства перейдем к функциям истинности (обозначив их так же, как сами формулы); введем также функцию γ = α1 ··· αn. Тогда доказательство сведется к проверке равносильности следующих уравнений: γ → β = 1, γ β → 0 = 1, γ β = 0. Каждое из этих уравнений выполняется только тогда, когда γ = 0 или β = 1. Следовательно, написанные уравнения равносильны. Теорема доказана.

Итак, согласно теореме проверка условия (1.2) сводится к проверке того факта, что α1 ... αn β F. Эту проверку можно упростить следующим образом. Запишем каждую из формул α1,..., αN, β в КНФ, т. е. в виде дизъюнкции нескольких ЭД; для краткости ЭД называют дизъюнктом. Выпишем все дизъюнкты, участвующие в указанных КНФ; пусть это будут D1,...,Dr. Тогда утверждение α1 ... αn β F превращается в утверждение D1 ... Dr F, а это равенство означает, что

Окончательный вывод таков: проверка логического следования (1.2) сводится к проверке более простого логического следования (1.4), где Di — дизъюнкты.

12

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

Как уже сказано, простейший способ проверить утверждение (1.4) состоит в переходе к функциям истинности, т. е. к проверке равенства D1 ...Dr = 0 для булевых функций. В подразд. 1.3 мы опишем другой способ, называемый методом резолюций. Он более громоздок, но ценен тем, что в дальнейшем его можно будет применять к более сложным языкам.

1.3. Метод резолюций в языке высказываний

Лемма о резолюциях. Для любых формул α, β, θ имеет место логическое следование α θ, β θ |= α β.

Доказательство. Перейдем от формул к их функциям истинности (обозначаемым так же, как формулы). Надлежит проверить, что они удовлетворяют (тождественно) равенству (α θ)(β θ) → → (α β) = 1 (здесь для краткости мы пишем фукции без указания их независимых переменных, пробегающих множество {0,1}).

Перепишем его в виде (x1 x3)(x2 x3) → (x1 x2) = 1, где xi {0,1} = 1. Читатель без труда проверит это тождество, соста-

вив таблицу для рассматриваемой функции. Лемма доказана. Формулу α β, написанную в этой лемме, называют резолюци-

ей формул α θ и β θ (записывается в виде α β = res(α θ, β θ)). Говорят также, что формула θ входит в формулы α θ и α θ контрарно (т. е. в одну из них входит в виде θ, а в другую — в виде θ). Заметим, что резолюция дизъюнктов A и A есть F (пустой дизъюнкт).

Чтобы применить эту лемму к исследованию логического следования, введем следующее понятие.

Обозначим через S набор дизъюнктов, указанный в утверждении (1.4). Пусть дана цепочка формул ξ1,..., ξm, такая, что каждая из них либо принадлежит набору S, либо есть резолюция какихлибо двух предшествующих формул этой цепочки. Такую цепочку называют резолютивной цепочкой, а также резолютивным выводом

формулы ξm из набора S. Из леммы ясно, что все формулы ξi (и, в частности, последняя формула ξm) логически следуют из набора дизъюнктов S.

Итак, для проверки утверждения (1.2) (а также равносильного ему утверждения (1.4)) достаточно построить резолютивный вывод пустого дизъюнкта из набора S. Это сводится к следующим шагам.

13

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

В наборе S отыскиваем такую пару дизъюнктов, в которые некоторый атом (например, A) входит контрарно (т. е. в один из дизъюнктов — в виде A, в другой — в виде A). Находим резолюцию этой пары, т. е. удаляем из дизъюнктов A и A и берем дизъюнкцию оставшихся частей. Полученный дизъюнкт добавляем к набору S. С полученным новым набором дизъюнктов поступаем так же, как с исходным набором S, и т. д. Работа заканчивается тогда, когда получится пустой дизъюнкт либо когда процесс перестанет давать новые дизъюнкты. В первом случае утверждение (1.2) истинно, а во втором — ложно.

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

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

Случай 2. Допустим,что возникли два дизъюнкта Di,Dj, один из которых есть часть другого, т. е. Di = Dj D , где D — дизъюнкт. Тогда более длинный дизъюнкт можно удалить. Это следует из равенства (Dj D )Dj = Dj (оно равносильно следующему равенству для булевых функций: (x1 x2)x1 = x1; читателю рекомендуется проверить это соотношение).

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

внекоторые дизъюнкты (например, в D1 и D2) входит A, но ни

водин из дизъюнктов Di не входит A. Пусть утверждение (1.4) справедливо. Тогда функции истинности дизъюнктов удовлетворя-

ют (тождественно) равенству D1 ...Dr = 0. Подставим 1 вместо A. Тогда D1 и D2 обратятся в 1 (поскольку x 1 = 1), что приведет

14

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

к равенству D3 ...Dr = 0; возвращаясь от функций истинности к формулам, можно записать D3 ...Dr |= F. Итак, отбрасывание дизъюнктов D1 и D2 не повлияло на справедливость утверждения (1.4), что и требовалось доказать.

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

Оно равносильно тому, что α1, α2, α3, α4, β |= F. Запишем эти формулы в КНФ. Формулы α1, α2, α3, а также β = C A уже имеют вид КНФ. Приведем к КНФ формулу α4. Для этого рассмотрим формулу α4 и приведем ее к ДНФ. Имеем (используя формулу (1.1)) α4 = A BCD AB. Отсюда α4 = (A BCD)(A B) =

=AB ABCD. Еще раз применим отрицание, получим α4 =

=(A B)(A B C D), и КНФ построена. Выпишем все дизъюнкты, встречающиеся в полученных КНФ; тогда инте-

ресующее нас логическое следование равносильно тому, что

B,C D,A D,A B,A B C D,C,A |= F. Сначала выполним очищение указанного набора формул. Можно удалить пятую формулу, ибо она содержит в себе шестую, затем удалить четвертую, ибо она содержит первую; из оставшихся формул можем удалить первую, так как она содержит уникальный атом B. В итоге останутся следующие четыре формулы: 1) C D; 2) A D; 3) C; 4) A. Построим новые формулы, применяя резолюции; для каждой новой формулы запишем, из каких предыдущих формул она получается (как их резолюция). Получим формулы: 5) D = res(1,3); 6) A = res(2,5); 7) F = res(4,6). Итак, логическое следование доказано.

Упражнение. Проверьте утверждение A C,C → B,B →

→ A |= A → (B → C).

15

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

2. ЯЗЫК ПРЕДИКАТОВ

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

2.1. Синтаксис языка предикатов

Алфавит языка предикатов. Алфавит ЯП включает: а) символы переменных x,y,z,...;

б) символы констант a,b,c,...;

в) функциональные символы (буквы) fi, gi,..., где i — число аргументов (мест), i = 0;

г) предикатные символы (буквы) Pi, Qi,..., где i — число аргументных мест, i 0;

д) логические символы-связки: ¬, , , →; е) — квантор всеобщности (читается «для всех», «для

любого»); — квантор существования (читается «существует», «найдется»); скобки, запятая, точка и т. д.

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

Термы и формулы. Термы определяются согласно следующим правилам:

а) символ константы или символ переменной суть термы;

б) если fk — функциональный символ, а t1,...,tk — термы, то слово fk(t1,...,tk) есть терм.

Например, g2(h2(c,x),g2(x,h2(c,y))) — термы; g2, h2 — двухместные функциональные символы; c — константа; x, y — переменные.

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

а) слово Pk(t1,...,tk), где Pk — k-местный предикатный символ, а t1,...,tk — термы, есть формула (такие формулы называются атомарными);

16

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

б) если A,B — формулы, то ¬(A),(A B),(A B),(A) → (B) также формулы (здесь допустимо опускать некоторые скобки — согласно утверждениям, описанным в подразд. 1.2);

в) если A — формула и x — переменная, то x(A) и x(A) также суть формулы.

Выражение x или x называется кванторной приставкой; x — переменной кванторной приставки, а A — областью действия кванторной приставки.

Например, формула x z((P2(f2(x,y)) R) → yQ2(z,y)) читается так: «для всякого x существует такое z, что если истинны формула P2(f2(x,y)) и R, то существует y, для которого истинна формула Q2(z,y)».

Любое подслово формулы, являющееся формулой, называется подформулой данной формулы. Подформула вида x(β) или x(β) называется кванторной подформулой. Иногда далее будем применять обозначение Qx(β), понимая под Q один из кванторов — или .

Свободные и связанные вхождения переменных. Каждое вхождение переменной в формулу может быть либо свободным, либо связанным. Вхождение переменной х называется связанным в следующих двух случаях:

а) х участвует в кванторной приставке x или x;

б) х входит в область действия одного из кванторов — x или x.

Любое другое вхождение переменной х в формулу называется

свободным.

Например, в формуле xP2(x,y) → Q1(x) имеем три вхождения переменной х в формулу, два связанных вхождения подчеркнуты.

Формула называется замкнутой формулой или предложением,

предложение, поскольку для каждой из переменных букв z, x имеются свободные вхождения (читателю следует найти эти вхождения), а переменная y имеет единственное вхождение, причем оно свободное.

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

17

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

формула α содержит в себе кванторную подформулу Qx(β). Заменим в этой подформуле переменную x любой другой переменной, которая не встречается в подформуле β. Это и есть операция переименования. Если в формуле α содержится кванторная подформула Qx(β), причем β не содержит букву x, то условимся отбрасывать неработающую, т. е. пустую кванторную приставку Qx.

Используя две указанные операции, можно перейти от любой формулы α к формуле θ, обладающей следующим свойством: если θ содержит подформулу Qx(β), то буква x содержится в β и не содержится свободно нигде более в данной формуле θ. Такую формулу назовем чистой.

Пример 2.1. Рассмотрим формулу α = xP1(f1(x)) z Q2(x,z). Здесь переменная x связана в формуле xP1(f1(x)) и свободна в формуле zQ2(x,z), поэтому α в чистом виде будет выражена формулой θ = yP1(f1(y)) zQ2(x,z).

В дальнейшем мы будем иногда опускать верхние индексы в записи предикатных и функциональных символов.

Подстановка терма в формулу. Пусть формула α содержит свободное вхождение переменной х, а t — терм. Образуем новую формулу, заменив все свободные вхождения буквы x указанным термом. Эту операцию называют подстановкой (терма вместо переменной) и записывают в виде S = {t|x}. Подстановка называется правильной, если любая переменная, входящая в t, остается свободной в полученной после подстановки формуле S = {t|x}. Допустимы только правильные подстановки.

Пример 2.2. α = yP(x,y,z), t = f(x,y). В этом случае подстановка S = {t|x} = {f(x,y)|x} (она приводит к формулеyP(f(x,y),y,z)) является неправильной. Правильной является подстановка α = uP(f(x,y),u,z).

2.2. Интерпретации. Семантика языка предикатов

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

а) указать множество D, называемое областью интерпретации; символы переменных, входящих в формулу, будем интерпретировать как переменные, пробегающие множество D;

18

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

б) каждому константному символу a,b,... поставить в соответствие элементы из D, обозначаемые обычно через a0, b0 ...;

в) каждому функциональному символу fk поставить в соответствие конкретную функцию y = f0k(x1,...,xk), где xi D,y D; г) каждому предикатному символу Pk поставить в соответствие k-местное отношение на множестве D, т. е. подмножество

множества P0k Dk.

Отметим, что каждый терм, содержащий только константы, также обретает интерпретацию как элемент множества D .

Пример 2.3. Пусть дана формула α = xP2(x,a). Рассмотрим следующую интерпретацию: D = [0,3], a0 = 1, P02 = {(x,y): x[0,3], y [0,3], x+y 3}. Тогда α интерпретируется как x(x+ + 1 3), т. е. x(x 2).

Остановимся подробнее на одноместных предикатах и интерпретации содержащих их формул. Если D — область интерпретации, то, как уже сказано, P1 интерпретируется как подмножество области D. Часто удобнее интерпретировать P1 как свойство элементов области D и считать, что упомянутое подмножество есть множество элементов, обладающих этим свойством.

Истинность предложений в данной интерпретации. Область истинности формулы. Дадим определение истинности или ложности формулы ЯП в заданной интерпретации. Пусть α — предложение, т. е. формула без свободных вхождений переменных. Тогда ее истинность определяется следующим образом:

1) пусть формула α атомарна, т. е. α = Pk(t1,...,tk), причем ti не содержит переменных. Пусть терм ti интерпретирован как bi D. В этом случае будем считать α истинной в данной интерпретации, если (b1,...,bk) P0k. Здесь P0k Dk — k-местное отношение на D, которое служит интерпретацией этого предикатного символа;

2)eсли для предложений α, β уже известна их истинность, то оценка (т. е. установление истинности либо ложности) формул ¬α,

αβ, α β, α → β, α ↔ β устанавливается по тем же формулам, что и в ЯВ;

3)если α = xθ, где θ содержит свободное вхождение пе-

ременной x, то, выполнив подстановку {a|x}, где a — константа, получаем формулу θ{a|x} без свободных вхождений переменных. Будем считать, что α = xθ истинна в данной интерпретации,

19

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

если при любой интерпретации символа a, т. е. при замене a на a0 D, формула θ{a|x} истинна;

4) если α = xθ, то, как и в случае 3, рассматриваем формулу θ{a|x}. Если существует замена a на a0 D, при которой формула θ{a|x} истинна, то будем считать, что формула α = xθ истинна в данной интерпретации.

Рассмотрим теперь формулу, не являющуюся предложением; пусть, например, переменные x, y (и только они) имеют свободные вхождения. Пусть задана некоторая интерпретация рассматриваемой формулы. Выполним подстановки a|x, b|y (здесь a, b — некоторые константные символы, не входящие в исходную формулу). Мы получили предложение, в котором интерпретированы все символы, кроме символов a, b. Мы можем «доинтерпретировать» их произвольными элементами a0, b0, взятыми из области D. Множество тех пар a0, b0, для которых рассматриваемая формула истинна (при указанной интерпретации), называется областью истинности формулы.

Пример 2.4. Пусть x yP2(x,y)D = [0,1]. В качестве области интерпретации возьмем отрезок D = [0,1], а символ P2 интерпретируем как подмножество квадрата, заданное неравенствами 2x − 1 y 2x. Покажем, что в этой интерпретации формула истинна. Для этого отбросим кванторную приставку x и в оставшейся формуле зам´еним свободную переменную x константным символом a. Получили формулу yP2(a,y). Интерпретируем символ a точкой 1/2. При этой интерпретации полученная формула истинна, так как формула P2(a,b) истинна, если буква a интерпретирована как 1/2, а буква b интерпретирована произвольной точкой отрезка [0, 1].

На с. 21 приведены еще четыре примера: в первых двух — предложения, в двух других — предикаты. Изображены области интерпретации. Мы уже убедились, что первое предложение истинно. Читателю следует проверить, что второе предложение ложно и что области истинности для третьего и четвертого примеров

— это отрезки [0, 1] и [0, 1/2] соответственно.

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

20