Лекции по математической логике / AkimovLogica4.doc

1.  Логика

1.0.      Введение

1.1.      Операции логики Буля

1.2.      Формы представления булевых операций

1.3.      Методы доказательства в логике Буля

1.4.      Задания на практическую работу по логике высказываний

1.5.      Введение в логику высказываний

Под высказыванием мы будем понимать грамматически правильное повество­вательное предложение, про которое можно сказать, что оно либо истинно, либо ложно, например:

«Киев — столица Украины»,

«Париж — столица России».

Первое высказывание является истинным, второе — ложным. Возьмем два простых высказывания:

А = «На улице идет дождь»,

В = «Над моей головой раскрыт зонтик»,

С помощью пяти логических связок можно образовать следующие сложные высказывания:

1)      отрицание: -А = «На улице не идет дождь»;

2)      дизъюнкция:
-A v В = «На улице не идет дождь или над моей головой раскрыт зонтик»;

3)      конъюнкция:

А & -В = «На улице идет дождь и над моей головой не раскрыт зонтик»;

4)      импликация:

А à В = «Если на улице идет дождь, то над моей головой раскрыт зонтик»;

5)      эквивалентность:

В ~ А = «Над моей головой раскрыт зонтик тогда и только тогда, когда на улице идет дождь».

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

• Отрицание.

Высказывание А по-другому можно прочитать так:

«Истинно то, что на улице идет дождь».

Поэтому, если А = 0 , то это означает, что на улице не идет дождь. Дополняющее

высказывание -А также ориентируется на истинное высказывание, т.е. его следует понимать как

«Истинно то, что на улице не идет дождь».

Тогда -А = 1 будет обозначать ту же самую ситуацию, что и в предыдущем случае, т.е. отсутствие дождя.

• Дизъюнкция.

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

Р = «Петр находится в кинотеатре» ,

Q = «Петр находится в бассейне» .

Если для нас не столь важно, где находится Петр, то мы, конечно, можем исполь­зовать союз «или» с включенным в него союзом «и», формально записав:

P v Q = «Петр находится в кинотеатре или/и в бассейне».

Но если нам нужно точно установить, где находится Петр, то мы обязаны исклю­чить случай одновременного присутствия Петра в кинотеатре и бассейне, т е формально записать:

(Р v Q) & -(P & Q) .

Подобные высказывания называются строгой дизъюнкцией, которая означает: «либо Р, либо Q, но не Р и Q одновременно». И хотя, с точки зрения логики Буля эта логическая операция равносильна операции симметрической разности:

P + Q = (P v Q) & (-P v -Q),

исторически сложилось так, что символ «+» в логике высказываний не использу­ется.

• Конъюнкция.

Логический союз «и» необязательно должен представляться через грамматический союз «и». В частности, выше приведенное выражение можно прочитать несколько иначе:

А & В = «На улице идет дождь, а над моей головой не раскрыт зонтик».

Союзы «a» и «но» по смыслу часто совпадают с союзом «и», поэтому они используются в сложных конъюнктивных предложениях.

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

«Ему стало страшно и он убил человека»,

«Он убил человека и ему стало страшно».

Здесь некоммутативность двух простых предложений очевидна, поскольку мы имеем дело со скрытой импликацией, когда одно простое предложение обусловливает другое.

• Импликация.

Высказывание типа «если А, то В » носит объясняющий характер Оно как бы разъясняет нам, почему имеет место событие В — потому что имело место событие А. Это свойство импликации особенно ценно для логики высказываний, о чем мы подробно остановимся в следующем подразделе.

Объясняющий характер импликации тесно связан с причинно-следственным отношением, при котором А выступает в роли причины, а В — следствия. Причинно-следственная связь между А и В грамматически может быть офор млена предложениями: «А является достаточным основанием для В», «В , потому что А», «В при условии выполнения А» и т.д. Если под А и В понимать прежние высказывания, то результат причинно-следственного отношения можно оформить следующей таблицей истинности. Вторая строка таблицы говорит об отсутствии причинно-следственного отношения между событиями А и В.

Таблица

A	B	AàB	Результаты
0	0	1	Останусь сухим
1	0	0	Вымокну
0	1	1	Останусь сухим
1	1	1	Останусь сухим

• Эквивалентность.

Высказывание «А эквивалентно В» может быть с успехом заменено на «А равно В», «А тождественно В», «А равносильно В», «А тогда и то­лько тогда, когда В» и т.д. Так как эквивалентность выражается через конъюнк­цию двух импликаций:

А ~ В = (А à В) & (В à А),

то это отношение часто возникает при одновременном выполнении двух усло­вий: «из А следует В» и «из В следует А». Таким образом, при эквивалентности двух событий невозможно одному из них приписать роль только причины, а дру­гому — только следствия. Например, два события:

R = «Нарастание анархии в обществе»,

S = «Падение авторитета власти»,

являются вполне равнопорядковыми событиями, поскольку причиной нараста­ния анархии в обществе является падение авторитета власти; и наоборот, падение авторитета власти происходит из-за нарастания анархии в обществе. В данной си­туации бессмысленно обвинять только власть в слабости и некомпетентности или обвинять народ в несознательности и недисциплинированности.

События R и S образуют логический круг; их будем называть сильно связанны­ми событиями и выражать следующими тождественными формами:

R ~ S = (R & S) ~ (R v S) = (R v S) à (R & S).

Понятие «сильной связанности» совпадает с понятием «эквивалентности», если речь идет о двух событиях. Но возьмем, к примеру, хорошо известное объ­яснение, на чем держится Земля:

Земля (X) держится на трек китах (Y), киты (Y) держатся на водах океана (Z), океан (Z) держится на Земле (X),

Последовательность, куда входят три названных объекта X, Y и Z, тоже обра­зуют логический круг:

 (Y à X) & (Z à Y) & (X à Z)

Однако отношение эквивалентности (быть взаимной опорой друг для друга) между всеми тремя объектами, т.е.

X~Y~Z,

здесь не возникает, да и не могло возникнуть, так как мы ведь не утверждаем, что 3емля является непосредственной опорой для китов (X ~ Y), или что киты являют­ся непосредственной опорой для вод океана (Y ~ Z). Поэтому эквивалентность в данном случае проявляется в весьма своеобразной форме:

(X & Y & Z) ~ (X v Y v Z) или (X v Y v Z) à (X & Y & Z) ,

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

3. В заключение этого вводного подраздела хотелось бы подчеркнуть важность различия между языком и метаязыком, между объектными и субъектными высказываниями. Пренебрегая этим различием, мы рискуем впасть в противоречие, которое называется логическим парадоксом.

С древних времен известен так называемый «Парадокс лжеца». Изложим его суть.

«Я — лжец», — сказал лжец,

Итак, некий лжец сообщает о себе, что он лжец. Следовательно, здесь он выступает в своем противоположном качестве, а именно — нелжеца. Поэтому пpиведенное высказывание на самом деле нужно понимать иначе:

«Я — лжец», — сказал нелжец.

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

Парадокс возник потому, что в приведенных высказываниях не делается раз граничения между двумя принципиально различными логическими уровнями. Помимо «лжеца» или «нелжеца» в данной логической ситуации участвует субъект (метанаблюдатель). Если провести четкое синтаксическое отделение смыслового содержания, которое должно относиться к нам, как метанаблюдателям от прочей семантики объектных персонажей, то логическое противоречие буде снято. Ситуацию с лжецом необходимо представлять следующим образом:

«Я — лжец», — сказал лжец.

«Это истинно», — сказал метанаблюдатель.

«Я — лжец», — сказал нелжец.

«Это ложно», — сказал метанаблюдатель.

«Я — нелжец», — сказал лжец.

«Это ложно», — сказал метанаблюдатель.

«Я — нелжец», — сказал нелжец.

«Это истинно», — сказал метанаблюдатель.

ложно * ложно = истинно,

истинно * ложно = ложно,

ложно * истинно = ложно

истинно * истинно = истинно.

Если приведенные четыре конструкции записать через два слова истинно и ложно, то получим обыкновенную таблицу умножения для группы из двух эле­ментов типа плюс и минус единицы. Однако источником противоречий в логике высказываний необязательно является смешение именно объектного и субъект­ного уровней. Неопределенность может возникнуть между различными объект­ными уровнями. В качестве примера приведем следующую фразу: «Нет правил без исключений». Но фраза, стоящая здесь в кавычках сама является правилом. Так какое исключение должно следовать из него? Разберем это противоречие, несколько изменив его семантику. Пусть имеется высказывание:

А = «Любое высказывание является ложным».

Так как А является высказыванием, на него должно распространяться сказан­ное в предложении А. Рассмотрим два случая:

1) Пусть А = 1. Это означает, что А = «А = 0» = 1, т.е. А = 0.

2) Пусть А = 0. Это означает, что А = «А = 0» = 0, т.е. А = 1.

Таким образом, в обоих случаях имеем противоречие. Чтобы его избежать, нужно произвести логическое разграничение всего множества высказываний на два принципиально различных класса — А и В. В этом случае формальная запись пер­воначальной фразы будет иметь вид: А = «В = 0»; тогда при А = 1, В = 0 и при А=0, В = 1

Приведем еще один пример известного парадокса. Английский логик Бертран Рассел поведал такую притчу:

В одной из деревень жил парикмахер. Он брил всех тех жителей деревни, кто не брился сам.

Рассел задался вопросом: может ли парикмахер побрить самого себя? Начинаем рассуждать: если парикмахер захочет побрить самого себя, то как житель этого се­ления, который бреется сам, он не вправе это сделать; но если парикмахер не ста­нет бриться, то уже как житель селения, который не бреется сам, он обязан будет себя побрить.

Выразим семантику этого противоречия формальным языком, Обозначим че­рез А парикмахера и пусть Р(А, В) означает высказывание «А бреет В». Тогда си­туацию, которую мы имеем в селении, можно описать двумя метавысказывания-ми:

1) Если Р(В, В) = 0, то Р(А, В) = 1.

2) Если Р(В, В) = 1, то Р(А, В) = 0.

Когда парикмахер рассматривается в качестве рядового жителя селения (А = В), оба метавысказывания становятся внутренне противоречивыми:

1) Если Р(А, А) = 0, то Р(А, А) = 1.

2) Если Р(А, А) = 1, то Р(А, А) = 0.

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

1.6.      Построение доказательств в логике высказываний

1.6.1.   

Логика — это наука о способах доказательства. Выясним, в чем, собственно, со­стоит различие в построении доказательств в логике высказываний и логике Буля.

В булевой логике все доказательства строились на отношении эквивалентно­сти. Даже если в множественных выражениях и фигурировало отношение вклю­чения, что является частным случаем отношения порядка, то его мы переводили в тождество. Две логические функции считались эквивалентными, если они дава­ли на соответствующих наборах аргументов абсолютно одинаковые значения нулей и единиц. При использовании формальной записи логических выраже­ний отдельные звенья цепи любого доказательства там были связаны через сим­вол равенства «=». Отношение эквивалентности удовлетворяет трем законам —

рефлексивности: А = А;

симметричности: если А = В , то В = А;

транзитивности: если А = В и В = С, то А = С.

В логике высказывании все доказательства строятся на отношении порядка, т.е. на отношении, которое существует между причиной и следствием. Здесь уже от­дельные звенья цепи доказательства связаны символом импликации. Однакс символ импликации « -> » при логическом выводе мы будем заменять на символ « =$• », подобно тому, как в логике Буля используются два символа эквивалентно­сти — « ~ » и « = ». Символ « ~ » является объектным, а « = » — субъектным. Таким образом, следует различать язык логики высказываний и метаязык исследовате­ля. Во избежание путаницы введем еще два метасимвола: вместо объектной конъ­юнкции « » будем использовать субъектный символ метаконъюнкции — «,»,< вместо объектной дизъюнкции « » — субъектную метадизъюнкцию « ; ». Тогда утверждение, которое требуется доказать, в логике высказываний оформляется в виде следующего причинно-следственного отношения:

Р1, Р2, ... , Р_n-1, Р_n => C, (1.1)

где Р_i — посылка (причина), С — заключение (следствие). Читается: «Если посылки Р1, Р2, ... , Р_n-1, Р_n истинны, то заключение С тоже истинно» или, по-другому «Если причины Р1, Р2, ... , Р_n-1, Р_n имели место, то будет иметь место и следст­вие С».

Чтобы не спутать объектное высказывание (предложение) с субъектным высказыванием, справедливость которого мы намереваемся установить, условимся предложения типа (1.1) называть клаузой (clause).

Клауза — это метапредложение, в котором использовано отношение порядка, оформленное через символ метаимпликации « => ». Как и отношение эквивалентности, отношение порядка удовлетворяет трем законам: рефлексивности: А => А; антисимметричности: если , то ; транзитивности: если А => В и В => С, то А => С.

 В отличие от эквивалентности отношение порядка предполагает выполнение закона антисимметричности, который можно записать так:

если А=>В и В=>А, то А = В.

Клауза есть именно формальная запись доказываемого предложения. Вместо букв в ней можно подставить объектные высказывания, и тогда клауза наполня­ется конкретным содержанием, которое уже именуется семантикой или леген­дой. Пример клаузы:

А->В, А => В.

Если принять, что

А = сверкнула молния, В = грянул гром, то можно составить следующую легенду:

Известно, что если сверкнула молния, то после этого грянет гром. Молния сверк­нула. Следовательно, должен и грянуть гром.

1.6.2.   

Над субъектом, который формулирует метапредложения, может стоять дру­гой субъект, для которого уже предложения первого субъекта окажутся объект­ными. Тогда клаузу (1.1) второй субъект или метасубъект запишет для себя сле­дующим логическим выражением:

.

Преобразовав это выражение в дизъюнкт, получим:

.

Отсюда легко находим:

.

Поэтому клауза (1.1) может быть представлена в другой эквивалентной форме:

. (1.2)

В силу коммутативности конъюнкции на месте посылки РЛ может оказаться любая другая, причем не одна. Например, клауза:

может быть преобразована в другую эквивалентную форму:

. (1.3)

Однако клауза (1.1) по сравнению с (1.2) и другими подобными формами, типа (1.3), имеет определенные преимущества и, в частности, используется в языке логического программирования ПРОЛОГ. Ее называют хорновской. Произ­вольную клаузу всегда можно свести путем эквивалентных преобразований к хорновскому виду.

Если символ метаимпликации « => » клаузы (1.2) сместить в крайнее левое по­ложение, то она превратится в тавтологию; если же его сместить в крайнее пра­вое положение, то — в противоречие.

1 => — тавтология,

— противоречие.

R Добавив в клаузу (1.1) слева 1 через «,» и сместив импликацию влево, получим смещением тавтологию.

Добавив в клаузу (1.1) справа через «;» 0 и сместив импликацию вправо, получим противоречие.

R

Ниже мы рассмотрим пять конкретных методов доказательства справедливости логических клауз:

• аксиоматический метод,
• метод таблиц истинности,
• метод резолюций,
• метод Вонга,
• метод натурального исчисления.

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