Непейвода Н.Н. Прикладная логика

Подождите немного. Документ загружается.

1.2. ЗАЧЕМ ИЗУЧАТЬ?

бы смоделировать всю систему на машине, нужно привлечь такие-то

программные средства, что для того чтобы специалисты поняли резуль-

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

чальное — нужно быть готовым к тому, что построенная модель окажет-

ся никуда не годной и ее придется переделывать, поскольку, например,

характер нагрева в данном случае известен неточно, а при математиче-

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

которые совсем не обязательно адекватны реальной ситуации.И это еще

простейший случай.

Язык математической логики предоставляет великолепный случай

потренироваться в таких переводах, и сам используется как мощное, но

на сей раз не до конца формальное средство для перевода между дале-

ко отстоящими друг от друга языками. Выразить утверждение на нем

часто означает понять, что же нужно заложить в математическую либо

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

бо программные условия и затем прочитать на естественном языке —

что же было упущено в самой основе формальной модели.

Более того, язык математической логики (или язык логики предика-

тов, как его часто называют) используется либо прямо, либо как основа

и в других логических системах. Поэтому в данной книге этот язык на-

зывается просто логическим языком.

Дополнение

Об истории возникновения логического языка

В середине XIX века в математике самым передовым и бурно раз-

вивающимся разделом была абстрактная алгебра. Впервые математики

стали изучать не те структуры,которые,как казалось, были даны свыше:

числа и геометрические фигуры, а любые структуры, в которых можно

найти порядок и меру

. Были созданы новые числовые системы, новые

геометрии, и возникло большое желание перенести алгебраические ме-

тоды на другие области. Это с успехом проделала английская школа,

родоначальником которой можно считать де Моргана, а наибольшую

Еще в XVII веке выдающийся французский мыслитель Рене Декарт, хорошо знав-

ший и математику (хотя основным своим делом он считал философию и богословие; в

частности, ему в значительной степени западный мир обязан обузданием ордена иезуи-

тов и дискредитацией гибельного для любой страны и любой системы принципа: цель

оправдывает средства), дал определение математики как «Наука о порядке и мере».

Как говорится, здесь ни прибавить, ни убавить...

ГЛАВА 1. НЕОБХОДИМОСТЬ ТОЧНОГО ЯЗЫКА

известность получил Дж. Буль. Они заметили, что простейшие опера-

ции над множествами (правда, тогда еще не было понятия множества в

математике, но в традиционной логике всегда оперировали с понятием

“класса объектов, обладающих данным свойством” и изучались опера-

ции, аналогичные объединению, пересечению и дополнению) подчиня-

ются законам коммутативности, ассоциативности и дистрибутивности.

Естественно,они провели аналогию между объединением и сложением,

пересечением и умножением, пустым классом и нулем, самым большим

классом (универсом) и единицей... Нашлась и операция, очень похожая

на вычитание, а вот аналогию делению никак не удавалось подобрать, и

из-за этого английские алгебраисты-логики чувствовали себя несколь-

ко ущербно: что же за алгебра без деления! Весь остаток XIX века все

квалифицированные математики, занимавшиеся алгеброй классов, пы-

тались изобрести для них деление, но так ничего путного и не приду-

мали. Зато появилась алгебра булевских значений 0 и 1, которую сам

Буль рассматривал как какую-то патологию, хотя и приводил в качестве

примера.

К концу XIX века сразу несколько выдающихся математиков заня-

лись теорией многоместных отношений, и эта теория естественно пре-

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

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

записывали все как алгебру отношений и упустили случай перевода на

новый язык других математических понятий.Впрочем,сами они на пер-

вый план выносили в значительной степени ту же псевдопроблему, свя-

занную с удобными на первых порах, но в дальнейшем все больше и

больше приводившими к путанице, обозначениями логических опера-

ций как сложения и умножения: определить деление. Другие, одновре-

менно в Германии (Г. Фреге)и Италии (Пеано с учениками), попытались

записывать именно математические высказывания.

Фреге подошел к созданию нового языка как ученый,и причем осно-

вательный ученый немецкого стиля времен его расцвета. Он построил

теорию, впервые в математике формализовывавшую незадолго до этого

введенное в математический обиход понятие бесконечного множества

и всю систему теории множеств. Оказалось, что все известные матема-

тические понятия выражаются через понятие множества и отношение

принадлежности «

x является элементом множества X». Это был пер-

вый случай, когда всю математику свели к одному исходному понятию

и к одной исходной операции: образования множества элементов, обла-

1.2. ЗАЧЕМ ИЗУЧАТЬ?

дающих данным свойством.

Позднее (уже в XX веке) выяснилось, что есть еще три исходных

понятия, к которым можно свести всю математику.

• Понятие функции вместе с операциями:

1. определения по выражению

t(x) функции λx. t(x), вычисля-

ющей его значения;

2. применения функции к аргументу

f(x).

• Понятие имени вместе с операцией именования понятия и отно-

шением ‘имя N именует объект x’.

• Понятие системы, которое делает осмысленным, в частности, от-

ношение ‘часть — целое’. Фундаментальное отношение здесь —

отношение связи.

Второе из представлений используется в

λ-исчислении, оно стало од-

ним из главных инструментов, в частности, в современной математи-

ческой теории программирования, последним из них пока что повезло

меньше: логики знают о них, но толком еще использовать не смогли

Перед Пеано и его учениками стояла другая задача. В то время Ита-

лия быстро развивалась и требовались новые учебники для вузов. Тра-

диция практически не давила, поскольку итальянских учебников хоро-

шего уровня в области математики долго (после XVII века) просто не

было, образованные люди пользовались французскими и немецкими.

Чтобы подчеркнуть двойственность функции и аргумента в данном выражении, сей-

час в логике часто пишут просто

(f x).Такое представление функции с аргументами как

единого списка стало одной из основ широко применяемого для моделирования систем

со сложной логикой языка

ЛИСП

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

Фреге получил умственное расстройство (после периода признания и успеха), когда

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

докс Рассела). Шейнфинкеля (российского математика, создавшего

λ-исчисление), на-

оборот, не признали на Родине и не выпустили за рубеж, где его сравнительно быстро

признали. А у нас его заморили голодом в сумасшедшем доме... (Документов, подтвер-

ждающих такой конец Шейнфинкеля, найти не удалось. Если они и были, то сгинули

во время блокады Ленинграда. Но петербургские логики единогласно говорят, что де-

ло было именно так.) Поляки Хвистек и Лесьневский, создатели теории именования,

погибли во время второй мировой войны.

ГЛАВА 1. НЕОБХОДИМОСТЬ ТОЧНОГО ЯЗЫКА

Именно как педагог и подошел Пеано

к созданию символического язы-

ка,и неудивительно, что его система обозначений оказалась самой удач-

ной. Впоследствии ее лишь подправляли.

В частности, в те времена математики очень не любили нагромо-

ждений скобок (сейчас вычислительные машины к этому уже приучи-

ли). Старшее поколение еще помнит, как внимательно следили учителя,

чтобы скобки первого уровня были круглыми, второго — квадратны-

ми, а третьего — фигурными. Пеано избежал психологической опасно-

сти, заменяя скобки точками у логических связок: чем сильнее связыва-

ет связка, тем меньше у нее точек, и, соответственно, чем она главнее,

тем их больше. Он решительно отказался от обозначений операций ‘и’ и

‘или’ как умножения и сложения: раз это — другие операции, то и знач-

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

И после этого проблема ввести деление логических значений как-то са-

ма собой отпала.

Пеано ввел кванторы всеобщности

∀x и существования ∃x

, да и

само слово ‘квантор’. Впрочем, кванторы вводил и Г. Фреге, но его обо-

значения для кванторов были крайне неудобны, так же как и его обозна-

чения для логических формул: он их рисовал в виде двумерного дерева.

Дж. Уайтхед и его ученик Б. Рассел в Англии повторили и углуби-

ли труд Фреге на новом уровне. Они педантично проследили, чтобы все

известные источники противоречий были изгнаны. При этом они вос-

пользовались языком, изобретенным Пеано, и тем самым ввели данный

язык в употребление во всем мире.

Конечно же, бывший в то же время выдающимся и широко образованным матема-

тиком, внимательно следившим за новейшими веяниями. В математике навсегда оста-

нется, в частности, кривая Пеано, полностью заполняющая единичный квадрат.

Так что они происходят не от английских слов, а от тех латинских, от которых эти

английские слова сами произошли...

Глава 2. ПРОСТЕЙШИЕ

ВЫСКАЗЫВАНИЯ

§ 2.1. ЧТО ТАКОЕ ВЫСКАЗЫВАНИЕ?

Высказывание —утверждение об объектах,имеющее однозначный,точ-

но определенный смысл.

Это определение, конечно же, не математическое.С чисто математи-

ческой точки зрения понятия высказывания и объекта являются исход-

ными, но содержательно мы все равно должны описать, что же такое

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

Примерами высказываний служат, в частности, следующие утвер-

ждения:

2 × 2 = 4 (2.1)

2 × 2 = 5 (2.2)

sin π = 0 (2.3)

Волга впадает в Каспийское море.

(2.4)

Волга впадает в Балтийское море.

(2.5)

Кама впадает в Каспийское море.

(2.6)

Для всякого натурального числа найдется пре-

восходящее его простое число.

(2.7)

13 января 1995 г. в 11.35 на перекрестке

улиц Пушкинской и Советской автомобилем

№ CUR2171RUS был сбит гр. Иванов Иван

Иванович.

(2.8)

ГЛАВА 2. ПРОСТЕЙШИЕ ВЫСКАЗЫВАНИЯ

13 января 1995 г. в 11.35 на перекрестке улиц

Пушкинской и Советской автомобилем “Тойота”,

принадлежащим гр. Хасбулатову, находившему-

ся в состоянии опьянения средней степени, был

сбит гр. Иванов Иван Иванович, который полу-

чил тяжкие телесные повреждения.

(2.9)

Не только Иванов, но и Петров прогулял сего-

дняшнюю лекцию.

(2.10)

По словам Сталина, Троцкий был врагом СССР.

(2.11)

Большинство членов собрания проголосовало за

первый вариант решения.

(2.12)

Все волки — млекопитающие.

(2.13)

Простых чисел бесконечно много.

(2.14)

Геракл убил немейского льва.

(2.15)

У русалок зеленые волосы.

(2.16)

У нынешнего российского императора красный

нос.

(2.17)

Рим расположен на реке Тибр, основан, согласно

Титу Ливию, Ромулом и находится под особым по-

кровительством Юпитера.

(2.18)

Некоторые высказывания являются истинными, некоторые — лож-

ными. Например, (2.1), (2.3), (2.7) — безусловно истинные высказыва-

ния, (2.2), (2.5) — безусловно ложные.

Истинность либо ложность высказывания не всегда легко устано-

вить. Например, высказывание (2.7) требует доказательства и называет-

ся теоремой Евклида. Как ни странно, могут возникнуть сомнения даже

по поводу высказывания (2.4), которое традиционно относится к числу

трюизмов, общеизвестных истин. В самом деле, по принятому в геогра-

фии определению при слиянии двух рек притоком считается та, которая

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

в два раза меньше. Так что, возможно, правильней было бы считать ис-

тинным высказывание (2.6). Нигде так долго, прочно и безнаказанно не

могут существовать ошибки, как среди трюизмов. Порой даже кажется,

что общепринятая истина всегда ошибочна.

Зачастую высказывания говорят не о единичном факте, а о целом

множестве утверждений, например, (2.12), (2.13), (2.14). Такие выска-

зывания часто называют общими.

2.1. ЧТО ТАКОЕ ВЫСКАЗЫВАНИЕ?

Далее, порою вопрос об истинности или ложности высказываний

переносится из нашего мира в какой-то другой, т. н. ‘возможный’ мир

Например, все признают истинным утверждение о Геракле, но ведь на

самом деле неизвестно, был ли он и что делал... Просто для нас неко-

торые возможные миры, например, Библии, сказок, греческих мифов,

имеют почти такую же реальность, как и настоящий

2 3

Иногда высказывание относитcя не столько к сообщаемому акту,

сколько к его оценке. Например, утверждение (2.11) не зависит от “ре-

альной” истинности данного факта, но может быть строго доказано ли-

бо опровергнуто анализом исторических документов, касающихся того,

что говорил и делал Сталин.

А в сложном высказывании могут быть перемешаны и реальность,

и возможные миры, и оценки; см., например, (2.18).

В естественном языке можно сделать следующие замечания о вы-

сказываниях.

Атомарными,элементарными высказываниями естественно считать

такие, которые сообщают единичный факт. Атомарные высказывания

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

мер, (2.8), а сложные — достаточно простыми, например, (2.13). Слож-

ные высказывания образуются из атомарных применением трех видов

операций.

• Логические связки применяются к высказываниям и в результате

дают новое высказывание. Например, это “не только ..., но и ...”,

или просто конструкция сложносочиненного предложения, как в

(2.18).

Даже саму математику можно рассматривать как возможный мир, поскольку ее по-

нятия имеют к “действительности” весьма косвенное отношение. А уж физика вообще

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

системы координат, в которой выполнены три закона Ньютона, в природе нет и быть не

может.

А вообще, что такое “настоящий” мир? Реален ли он? Если глубоко разобраться,

то ответы могут быть самыми различными. В частности, Платон и буддисты уверены,

что этот мир нереален, а реален некий “идеальный” мир, бледным слепком с которого

является наш. Те, кто испытывал состояние творческого озарения, зачастую склонны

согласиться с ними.

(АПБ)

Традиционно настоящий мир считается реальным по определению. На мой

взгляд, стоит отличать истинный мир от реального (и оба их отличать от миров нава-

ждений).

ГЛАВА 2. ПРОСТЕЙШИЕ ВЫСКАЗЫВАНИЯ

• Модальности применяются к высказываниям и изменяют наше

отношение к ним. Например, модальностью является “По словам

Сталина...”

• Кванторные конструкции применяются к совокупности однород-

ных (отличающихся лишь значениями некоторых параметров) вы-

сказываний либо выражений и дают единое высказывание либо

выражение, не зависящие от упомянутых выше параметров. На-

пример, таковы “Большинство...”, “Все...” Порою кванторные

конструкции подразумеваются, как, например, в (2.16).

К несчастью, во многих естественных языках (особенно в русском)

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

ря: “и

A, и B”, мы подчеркиваем равноправие двух утверждений, а “не

только A, но и B” — наоборот, предпочтительность одного из них.

Помимо высказываний, в естественном языке имеется множество

предложений такой же грамматической структуры, которые тем не ме-

нее принципиально не могут иметь четкой и однозначной интерпрета-

ции. Их мы назовем квазивысказываниями.

Например, квазивысказываниями являются утверждения о субъек-

тивных чувствах, скажем, “Саша любит Машу”. Беда даже не в том, что

понятие любви неточно. Оно, прежде всего, неформализуемо, то есть

каждая его формализация немедленно вызывает к жизни контрприме-

ры

. Далее, оно принципиально непроверяемо, поскольку относится к

внутреннему миру человека и понимается разными людьми совершен-

но неодинаково.

Тем не менее методы логики, и даже математической логики, разра-

ботанные для высказываний, интенсивно применяются (прежде всего

в современных философии и “искусственном интеллекте”

) к квазивы-

сказываниям. Да и мы будем интенсивно пользоваться квазивысказыва-

Изобретение таких контрпримеров в исторические моменты, когда возникает прак-

тически общепринятое уточнение понятия любви, является одним из излюбленных за-

нятий литераторов и поэтов. Впрочем, т. н. “творческая интеллигенция” во всем мире

очень любит разрушать устоявшиеся системы взглядов, совершенно не задумываясь о

последствиях, почему И. А. Крылов и поместил в аду писателя в худшие условия, чем

разбойника.

Это чисто американское вульгарно-рекламное название стало практически термином

для обозначения целой отрасли в современной информатике. В дальнейшем мы часто

будем пользоваться принятым для него сокращением ИИ.

2.1. ЧТО ТАКОЕ ВЫСКАЗЫВАНИЕ?

ниями в наших примерах и упражнениях

. Возникает вопрос: почему

же мы, прекрасно осознавая неприменимость, вообще говоря, традици-

онной математической логики к этому классу предложений, применяем

ее? На это есть две причины.

Во-первых, если как следует разобраться, практически любое при-

менение строго доказанного математического результата на практи-

ке есть выход за те границы, в которых он был доказан. Скажем, при-

меняя действительные числа, мы опираемся на предположение о непре-

рывности измеряемой величины, а до сих пор неясно, непрерывно ли

наше пространство. В таких случаях стыдливо говорят, что точные ме-

тоды математики применяются на практике приближенно.

Опыт такого “приближенного” применения показал, что на самом

деле наиболее устойчивыми при выходе за рамки своих обоснований

являются преобразования, в особенности эквивалентные, математиче-

ских выражений. В логике мы сможем даже строго обосновать, что мно-

гие из развиваемых в общепринятой, классической, логике преобразо-

ваний высказываний применяются далеко за ее пределами. Поэтому мы

имеем серьезные основания ожидать, что корректно проведенное пре-

образование квазивысказываний не подведет нас.

Во-вторых, квазивысказывания через посредство модальностей за-

вязаны в неразрывный узел с высказываниями. Например, ‘Саша за-

явил, что он любит Машу’ — уже высказывание, а ‘Мне кажется, что

Волга впадает в Каспийское море’ — квазивысказывание.

Упражнения к § 2.1

Выделите высказывания и квазивысказывания.

2.1.1. У меня одна рука.

Есть еще одна область, где никак не удается обойтись без квазивысказываний. Оце-

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

ворят, что данный результат сильный, ценный, красивый... Оценочные высказывания

являются таковыми лишь тогда, когда фиксированы легко проверяемые критерии оцен-

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

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

имелось в виду при содержательной формулировке (например, оценка интеллектуаль-

ности человека по коэффициенту интеллекта IQ, измеряемому стандартной системой

тестов).

По данной причине необходимо четко понимать, что встречающиеся в данной кни-

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

комментариев по поводу субъективности (такие комментарии могут быть даже вред-

ны, поскольку создают иллюзию объективности большинства оценок).

ГЛАВА 2. ПРОСТЕЙШИЕ ВЫСКАЗЫВАНИЯ

2.1.2. У меня расстройство желудка.

2.1.3. У меня повышенное давление.

2.1.4. У меня болит спина.

2.1.5. У меня нет денег.

В нижеприведенных предложениях выделите логические связки,

модальности и кванторы.

2.1.6. (ШБ1) Каждая программа содержит ошибку.

2.1.7. (ШБ2) Если программа не содержит ошибок, то неверен приме-

ненный метод

7 8

2.1.8. По словам преподавателя, у студента Канторовича в каждой про-

грамме не менее десяти ошибок.

2.1.9. Завтра взойдет Солнце, если только не будет светопреставления.

2.1.10. Как мне сообщила Маша, наш профессор собирается завалить

на экзамене не менее половины группы.

2.1.11. Большинство избирателей проголосовало за Уткина.

2.1.12. Мне кажется, что Иванов думает, что я намерен подложить ему

свинью.

2.1.13. Мне передали, что Иванов думает, что я намерен подложить ему

свинью.

2.1.14. Почему высказывание (2.9) уже сложное, в отличие от (2.8)?

Эти два утверждения известны в русском программистском фольклоре как 1-я и 2-я

аксиомы Шуры-Буры (М. Р. Шура-Бура — профессор МГУ и один из основоположни-

ков русской программистской культуры). Третья аксиома звучит следующим образом:

(ШБ3) Если программа на самом деле полностью и абсолютно пра-

вильна, она никому не нужна.

(АПБ)

М. Р. Шура-Бура,как он сам подтвердил, никогда не употреблял эти три выска-

зывания вместе, пока не услышал их от автора настоящей книги. Более того, он заявил,

что третье высказывание на самом деле — принадлежащее автору следствие из первых

двух его утверждений.