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

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

Часть I

Язык математики

Глава 1. Необходимость точного

языка в математике

§ 1.1. КАК И ПОЧЕМУ ПОЯВИЛСЯ ЯЗЫК

МАТЕМАТИЧЕСКОЙ ЛОГИКИ?

Математика изучает объекты, свойства которых точно сформули-

рованы.

Это описание поля деятельности современной математики не претен-

дует на полноту. Оно, скорее, достаточно широко и отбрасывает лишь

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

. В част-

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

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

генетического кода.

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

ют разъяснения в первую очередь последние слова: «точно сформули-

рованы». Очевидно, что их уточнение влечет за собой уточнение и дру-

гих понятий, в частности ‘объекта’ и ‘свойства’. Какие формулировки

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

Очевидно, что не все то, что сказано на естественном языке, точно.

Иногда эта неточность лежит на поверхности, как, например, в фразах:

«Хочется чего-то, а чего — неясно» или «Оно, конечно, ежели что как...

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

зуя, как остроумно выразился Леви-Стросс, «формулы как узор, украшающий текст».

В частности, таковы многие современные работы по культурологии, философии и т. п.

Критерий распознавания такого наукообразия прост:понятия не уточняются. Далее, ча-

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

в текст. Но порою узоры внутренне непротиворечивы и просто не имеют отношения к

окружающему их тексту: это — высшая ступень надувательства.

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

А ежели что не так?» Иногда смысл фразы явно зависит от контекста,

например: «Сейчас я намылю ему шею». Богатство любого естествен-

ного языка неразрывно связано с его многозначностью. Зависимость от

контекста не всегда отрицательный фактор, лишь бы в любой данной

ситуации предложение уточнялось однозначно.

Но, например, полное и достаточно безобидное на вид предложение

«Он встретил ее на поляне с цветами» (1.1)

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

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

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

ремы на как можно более четком, хотя и бедном, диалекте естественно-

го языка. Хотя словарный запас этого диалекта постоянно расширяет-

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

ски теми же, что были выработаны еще в античные времена. Следует

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

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

чтения классических трудов, в первую очередь «Элементов» Евклида.

Долгое время считалось, что ‘математический диалект’ состоит из

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

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

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

формулировки теорем зачастую становились все длиннее, необозримее

и неудобнее. Соответственно, выкладки становились все более и более

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

«Квадрат первого, сложенный с квадратом вто-

рого и с удвоенным произведением первого на

второе, есть квадрат первого, сложенного со вто-

рым»,

(1.2)

требуется значительное усилие. Таким образом, математическая стро-

гость и удобство начали противоречить друг другу.

Выход был найден, когда заметили, что использованная в (1.2) часть

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

кам, и сейчас (1.2) записывается кратко и ясно:

+ 2xy + y

= (x + y)

. (1.3)

1.1. КАК И ПОЧЕМУ ОН ПОЯВИЛСЯ?

Это стало первым этапом уточнения математического языка: был со-

здан символизм арифметических выражений, их равенств и неравенств.

К XVIII в. математические формулы записывались почти в том же виде,

что и сейчас.

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

записывались на обычном языке с вкраплениями формул. И чем даль-

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

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

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

Рассмотрим один из самых ярких и элементарных примеров.

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

чисел, например:

«Десять в степени десять в степени десять».

(1.4)

«Наименьшее простое число, большее миллио-

на».

(1.5)

В русском языке 33 буквы, и предложений, состоящих не более чем из

ста букв, конечное число (грубо говоря, не более

101

). Натуральных

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

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

есть и наименьшее такое число. Его можно определить как

‘Наименьшее натуральное число, которое нельзя

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

жащим менее ста букв’.

(1.6)

Это предложение содержит 96 букв. Следовательно, определение (1.6)

противоречит самому себе. (Парадокс Берри. 1906 г.)

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

ское. Однако уже в те времена подобные конструкции встречались в те-

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

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

описания математических объектов. В частности, подобная идея лежит

в основе знаменитой теоремы Гёделя

о неполноте любой достаточно

сильной формальной теории.

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

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

Если парадокс Берри возник на границе между математикой и есте-

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

ки — в теории множеств.

Пусть

z — множество тех множеств, которые не

являются собственными элементами. То есть x ∈

z тогда и только тогда, когда неверно, что x ∈ x.

Символически

z = {x | x /∈ x}.

Подставляя z вместо x в определение z, получаем,

что z ∈ z тогда и только тогда, когда z /∈ z.

(1.7)

Появление первых парадоксов ошеломило математический мир и

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

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

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

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

писи формулировок теорем, и в особенности при манипуляциях с эти-

ми формулировками. Например, вот одно из элементарных определений

математического анализа:

Функция f, определенная на множестве M, не-

прерывна на M , если для каждого x из M и для

любого сколь угодно малого положительного ε

найдется такое положительное δ, зависящее от ε,

что,когда x

лежит в M и отличается от x меньше,

чем на δ, f (x

) отличается от f(x) меньше, чем на

ε.

(1.8)

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

вдаваясь в смысл фразы (1.8), не менее трудно, чем преобразовывать

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

символизме «

f непрерывна на M» записывается компактно и изящно:

∀x ∈ M ∀ε > 0 ∃δ > 0 ∀x

∈ M

(|x − x

| < δ ⇒ |f (x) − f(x

)| < ε).

(1.9)

Язык математической логики, ставший символическим языком со-

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

тического языка для нужд математики было окончательно осознано.Так

1.1. КАК И ПОЧЕМУ ОН ПОЯВИЛСЯ?

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

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

простые алгоритмы их осуществления и тем самым освободил головы

математиков для более важных дел.

Вместе с тем впервые появилась возможность строго ответить на

вопрос: а что значит ‘точно сформулированное высказывание’? Это вы-

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

ский язык математики.

Формализация математики привела к более ясному осознанию при-

роды самой математики, к триумфальному применению ее к нечисло-

вым и непространственным объектам, таким как, например, гены, есте-

ственные и искусственные языки, программы для ЭВМ и т. д. Вместе с

тем стало ясно и то, когда мы не должны применять математику. До тех

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

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

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

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

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

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

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

извлечения следствий из этих свойств.

Итак, первой проблемой, которую поставила жизнь перед математи-

ческой логикой, была следующая.

Основная задача языка математики

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

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

творял бы трем требованиям:

1. на него возможно перевести математические

утверждения,

2. он допускал бы сравнительно легкий перевод

на обычный язык,

3. записи на нем были бы компактны и удобны в

обращении.

(1.10)

Первая часть нашего пособия посвящена показу используемого в совре-

менной математике решения этой проблемы. Мы стремимся осветить с

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

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

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

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

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

логический подход к изучаемым понятиям.Сама математическая логика

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

языка математики.

Основная задача логической семантики

Дать четкое и однозначное истолкование суждений

формального языка, одновременно как можно более

простое и как можно более близкое к естественному

математическому пониманию.

(1.11)

Конечно же, мы вынуждены касаться отдельных аспектов этой зада-

чи уже в первой части, но лишь в простейших случаях.

Подытожим

Труднее всего поддается уточнению само понятие точности.

Математическая логика — наука, изучающая саму матема-

тику математическими средствами.

Математическая логика изучает формальную структуру рас-

суждений математическими средствами.

Формальная проверка зачастую сильнее содержательной.

Формальный язык позволяет значительно эффективнее пре-

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

Когда сложность утверждений данной науки превосходит опре-

деленный предел, начинается процесс ее формализации.

Формальный язык должен полностью исключать неоднознач-

ности.

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

го и до конца определен.

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

нению.

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

ного языка.

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

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

1.1.1. (Л. С. Выготский) Сколько различных смыслов имеет предложе-

ние

Предложение рабочих бригад вызвало осуждение

товарища Иванова?

1.1.2. (Х. Б. Карри) Докажите, что из существования множества всех

таких множеств

x, что если x является своим элементом, то вы-

полнено A, следует, что A истинно.

1.1.3. Какое из предложений (1.4),(1.5)неоднозначно?Как его перефор-

мулировать, чтобы оно стало однозначным?

§ 1.2. ЗАЧЕМ ИЗУЧАТЬ ФОРМАЛЬНЫЙ ЯЗЫК МАТЕМАТИКИ?

Ну допустим, мне удалось убедить Вас, что для математики необходи-

мо создавать точный формальный язык. Но остается второй вопрос: а

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

листом именно в области математической логики. Ведь столько лет без

него обходились, почему бы не обойтись и Вам?

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

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

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

но что незнание основ алгебры. Просто грех не пользоваться точными

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

бретать заново велосипед Артамонова

Второй ответ требует апелляции к опыту современных формальных

языков, прежде всего языков программирования.

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

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

ной машиной, Вы не обойдетесь без знакомства (хотя бы шапочного) по

крайней мере с 2–3 искусственными языками. А уж если Вы собирае-

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

Артамонов — мастер-самоучка, в царствование Николая I приехавший с Урала в

Питер на самодельном велосипеде.

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

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

ских языков сейчас не обойтись. Но лишь ими ограничиться нельзя,

если Вы стремитесь подняться выше чисто ремесленного уровня.

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

ленный формальный язык. Он появился в конце XIX века в трудах ита-

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

на ему Расселом и Гильбертом в начале XX века, и этот язык доказал на

практике свою жизнеспособность и устойчивость. Во множестве фор-

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

кусственного интеллекта, сменяющихся каждые десять лет, он является

своего рода скалой среди айсбергов. В нем в гораздо более последова-

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

ренятые в языках программирования и искусственного интеллекта. Так

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

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

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

тематика либо системного аналитика.

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

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

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

ритмов на конкретный язык программирования и обратно. Такая много-

языковость неизбежна: она вызвана необходимостью находить точные

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

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

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

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

ми в частных производных

, что в данном случае граничные условия

имеют такой-то вид, а тогда задача нахождения решений этих уравне-

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

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

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

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

ники этого не знают. Другое дело, что нужно развивать свою внутреннюю “базу знаний”

и включать в нее и то, что сам не знаешь как следует. Тут нужно лишь понимать, к какой

области это относится, к какому специалисту нужно обратиться, если Вы столкнетесь с

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

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

всего даже в одной отдельно взятой отрасли.