От логики формальной до логики символической

Логика, прежде чем стать математической, прошла долгий путь: от логики формальной до логики математической. Рассмотрим этапы становления математической логики.

Формальная логика и Аристотель

А ристотель

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

Логика учит другие науки доказательству всех следствий, вытекающих из заданных посылок.

Лейбниц

Аристотель родился во фракийском городе Стагира, греческой колонии, расположенной неподалеку от Афона [7, с. 34], поэтому Аристотеля называли часто "Стагирит".

Аристотеля уважительно именовали "князем мудрости". Его популярность была столь велика, что его произведения из века в век переписывались (пока не было изобретено книгопечатание), комментировались, переводились на латинский, армянский, арабский и другие языки, поэтому они стали известны нам. Дошедшие до нас труды Аристотеля по логике и научному познанию комментаторы объединили под общим названием "Органон" (термин "органон" представляет собой транслитерацию соответствующего греческого слова, означающего "орудие" (метод) исследования). Сам Аристотель свои логические труды называл "Аналитиками" [1].

Разрабатывая теорию логики Аристотель поставил перед собой задачу выяснить, "на чём же покоится принудительная сила речей, какими средствами должна обладать речь, чтобы убеждать людей, заставлять их с чем-нибудь соглашаться или признавать что-либо истинным?"

Он показал, что правильные рассуждения подчиняются небольшому числу законов, не зависимых от частной природы объектов, о которых идет речь. Аристотель открыл и точно сформулировал первые три закона традиционной логики. Первый закон – закон про- тиворечия, который на языке современной математической логики можно записать в виде Vx(x • x) (для всякого х не может быть одновременно истинно утверждение х и отрицание того же х ). Второй – закон исключенного третьего Vx(x v x) (для всякого х истинно либо х , либо x , вместе они ложны). Третий – закон тождества Vx(x ^ x) (для любого х истинно, что если х , то х ; х влечет х ).

Вклад Аристотеля в науку заключался прежде всего в том, что он отделил логические принципы и схемы рассуждения от содержания рассуждений и систематически их исследовал. В "Первой аналитике" – важнейшем логическом сочинении – была изложена силлогистика (система силлогических заключений, или силлогизмов) – главное достижение Аристотеля в логике, стоящее у истоков логики как науки. Чтобы оценить значимость этого достижения Аристотеля, обратимся к традиционному развитию всех наук. При формировании наук функционирует множество разных идей, из которых многие оказываются ошибочными. Рождаются и умирают десятки, а то и сотни теорий. Силлогистика представляет собой парадоксальное исключение. Она построена одним человеком и практически сразу. Ее никто не пытался критиковать или опровергать. Ее лишь уточняли и модернизировали. Со времени создания силлогистики прошло более двух тысяч лет, но она по-прежнему занимает почетное место в науке. "В средние века Аристотель пользовался такой популярностью, что его наверняка бы причислили к святым, если бы он не родился за четыреста лет до рождения основателя этой религии. На протяжении многих столетий силлогистика была единственной моделью дедуктивных рассуждений. В этом смысле она сыграла исключительную роль в становлении всех наук вообще, ибо стала для них методологией научного мышления" [6]. Силлогистика Аристотеля удовлетворяет, по существу, критериям логико-математической строгости, предъявляемым к современным формализованным системам. Ян Лукасевич заметил, что аристотелевская силлогистика по своей строгости превосходила даже строгость математических теорий того времени, и в этом состоит ее непреходящее значение. Логическое учение Аристотеля получило название традиционной логики. К ней добавляют эпитет "формальная", подчеркивая значимость формы рассуждений.

Заметим, что термин "логика" Аристотель не использовал. Впервые этот термин появился в трудах стóиков. Представители стоической школы (Зенон, ок. 336–264 до н.э. и др.) ввели термин "логика" для обозначения науки, исследующей законы мыслительной деятельности. Они рассматривали логику как первую часть философии, которая включает в себя также физику и этику. Цель логики – оградить ум человека от заблуждений и найти пути и критерий истины . Логика нужна, чтобы "охранять" этику, пищу для которой поставляет физика.

Термин " формальная логика" ввел Иммануил Кант.

Символическая логика и Лейбниц

Г.В. Лейбниц

Г.В. Лейбниц (1646–1716) понимал логику не только как искусство рассуждения и доказательства, но и как искусство изобретения и открытия новых истин. На него произвела сильное впечатление силлогистика Аристотеля. Его также вдохновляла идея, восходящая к Декарту, о "всеобщей математике" ( mathesis universalis ), исследующей порядок и меру. Он писал: "Изобретение силлогической формы – одно из прекраснейших и даже важнейших открытий человеческого духа. Это своего рода универсальная математика, все значение которой еще не достаточно понято" [14, с. 7– 9]. Размышляя о математизации логики, об использовании в ней символического языка, он задумал грандиозный проект усовершенствования логики, включающий создание "универсальной характеристики" – средства, с помощью которого все человеческое познание должно подвергнуться коренному преобразованию. Впервые соответствующие идеи Лейбниц высказал в своей (магистерской)

"Диссертации о комбинаторном искусстве" (Dissertatio de arte combinatoria), изданной в 1666 г. По замыслу Лейбница, новый метод должен включать два теоретических инструмента: искусственный язык ( characteristica universalis ) и исчисление умозаключений ( calculus rationator ). Искусственный язык, должен служить средством выражения любых мыслей, по его мнению, устранять барьеры разноязычной речи, способствовать распространению научных идей. Выражения естественного языка должны быть заменены компактными, наглядными и однозначно понимаемыми знаками – " характерами ". Все понятия следует свести к некоторым элементарным понятиям, образующим как бы алфавит, азбуку человеческих мыслей. После этого станет возможной замена обычных рассуждений оперированием со знаками.

Правила такого оперирования должны быть заданы во второй части "всеобщей науки" – в исчислении умозаключений. Они должны однозначным образом определять последовательности выполнения действий над знаками и сами эти действия, так что при правильном их применении не останется места для разногласий. Сокровенная цель описанной программы Лейбница четко выражена в словах о том, что единственное средство улучшения умозаключений состоит в уподоблении их математическим, т.е. в придании такой наглядности, что их "ошибочность можно было бы увидеть глазами, и, если между людьми возникают разногласия, достаточно только сказать "Вычислим!", чтобы стало ясно, кто прав" [14, с. 16]. Свой грандиозный замысел Лейбниц не реализовал, но, несомненно, идея математизации логики оказала влияние на ученых XVIII в., стимулируя, в свою очередь, использование символических обозначений.

Заслуги Лейбница в формировании математической логики высоко оценил Норберт Винер, создатель кибернетики: "Если бы мне в анналах истории наук пришлось выбирать святого – покровителя кибернетики, то я бы выбрал Лейбница, философия которого концентрировалась вокруг двух основных идей: идеи универсальной символики и идеи логического исчисления. Из них возникли современный математический анализ и современная символическая логика". Винер считает, что подобно тому, как в арифметическом исчислении заложена возможность развития его механизации от абака и арифмометра до сверхбыстрых вычислительных машин, так и в calculus rationator Лейбница в зародыше содержится mashina rationatrix – "думающая машина" [3, с. 57].

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

Математическая логика. XIX век

Джордж Буль

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

Создателем современной символической логики следует считать Джорджа Буля (1815–1864) [2, с. 17]. Буль для превращения логики в точную науку стал использовать математические обозначения. Он писал: "...необходимо связать логику не с философией, а с математикой". В 1847 г. он опубликовал свою первую работу по логике "Математический анализ логики как эссе к исчислению дедуктивного рассуждения" [9], в которой подчеркивал: "те, кто знаком с настоящим состоянием символической алгебры, отдает себе отчет в том, что обоснованность процессов анализа зависит не от интерпретации используемых символов, а только от законов их комбинирования" [9, с. 3]. Именно в ясном понимании абстрактности исчисления, понимании того, что исчисление определяется законами заданных в нем операций, состоит принципиальная новизна взглядов Буля на логическое учение. Через 8 лет Буль публикует свою вторую книгу "Исследование законов мышления, на которых основаны математические теории логики и вероятности" [10]. Замысел "Законов логики" Буль формулирует так: "Цель настоящего исследования состоит в том, чтобы изучить основные законы тех операций ума, посредством которых осуществляются рассуждения" [10, с. 1–2]. В этих работах Буль строит алгебру высказываний (алгебру логики) как алгебру классов, в которой классы множеств соответствуют объемам понятий. Буль обозначает универсальное множество символом 1, пустое множество – символом 0, для обозначения классов использует переменные x, y,   На множестве классов вводит двухместные операции x + у (сложение, соответствующее объединению множеств с исключением их общей части) и х • у (умножение, соответствующее пересечению множеств), одноместную операцию 1 — х (дополнение до универсума). В булевой алгебре для сложения и умножения выполняется коммутативный и ассоциативный закон, умножение дистрибутивно относительно сложения. Если использовать современные обозначения для дополнения, то следующие свойства операций в алгебре Буля можно записать в виде x • x = 0, x + x = 1. Буль отмечает, что логика отличается от алгебры тем, что в логике выполняется равенство x • x = x, тогда как в алгебре равенство x2 = x выполняется только тогда, когда x = 1 или x = 0.

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

Кванторы в логику ввел немецкий математик, логик и философ Фреге Фридрих Людвиг Готтлоб (Friedrich Ludwig Gottlob Frege, 1848–1925).

Готтлоб Фреге

С именем Фреге связано возникновение нового этапа в развитии математической логики, который характеризуется аксиоматической трактовкой пропозиционального исчисления, формированием основ математического доказательства. Фреге построил логику в виде формализованного языка, именуемого им "исчислением понятий" (Begriffsschrift) в работе 1879 г. [12]. Его формализованная логика стала впоследствии основным орудием математики.

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

Фреге ввел кванторы, но использовал обозначения только для квантора всеобщности, квантор существования он выразил через общность и отрицание.

От современников Фреге не получил признания. "Исчисление понятий" в целом прошло незамеченным и философами, и математиками. Философов отпугивал сложный математический аппарат, математиков – постоянное использование таких терминов, как "суждение", "отношение", "понятие", которые специалисты считали "типично метафизическими". Дополнительные трудности были связаны со сложной символикой.

Более удобная символика была предложена Джузеппе Пеано. С 1845 г. Пеано и его сотрудники приступили к изданию " Формуляра математики " (Formulario mathematico), в котором математические дисциплины излагались в специальном логическом исчислении. Достоинства символики Пеано отлично понял Бертран Рассел, собственный язык которого в "Principia Mathematica" (1910–1913) сочетал строгость языка Фреге и удобство языка Пеано.

Влияние Фреге в краткосрочной перспективе проявилось в работах Пеано, Витгенштейна, Карнапа и Рассела, в долгосрочной перспективе Фреге оказал большое влияние на развитие философии логики. Если современники его в значительной степени игнорировали, то во второй половине XX в. и в XXI в. его с увлечением читают и высоко чтят философы, особенно после перевода его работ на английский язык. Так, американские философы A. George и R. Heck пишут: "С чрезвычайной ясностью, строгостью и техническим блеском, он впервые представил свою концепцию рационального обоснования. По сути, это, пожалуй, самый большой единственный вклад в логику, когда-либо сделанный, и это было самым важным достижением, начиная с Аристотеля. Впервые был проведен глубокий анализ дедуктивных выводов, включающих предложения, содержащие многократные вложенные выражения общности. Кроме того, он представил логическую систему, в которой такие аргументы можно было бы четко представить: это было самым значительным событием в нашем понимании аксиоматических систем с Евклида" [13]. Joan Weiner многие годы посвятила исследованию трудов Фреге. Она пишет: "Сочинения Готтлоба Фреге оказали глубокое влияние на современную мысль. Его революционная новая логика была зарождением современной математической логики – области, к которой сводится не только абстрактная математика, но и компьютерная наука и философия" [19].

В России первые лекции по математической логике читал Порецкий Платон Сергеевич (1846–1907) в 1887–1888 гг. в Казанском университете. Порецкий разрабатывал алгебру логики. Для этой теории он нашел оригинальные и простые методы решения задачи об отыскании множества следствий, вытекающих из данной системы посылок, и множества гипотез, из которых выводимы данные следствия ("О способах решения логических равенств и об обратном способе математической логики", 1884).

Математическая логика. XX век

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

Ян Лукасевич

До 1920 г. в математической логике использовались лишь два значения истинности: "истина" и "ложь". Известный польский логик, один из лидеров Львовско-Варшавской философской школы, Ян Лукасевич (1878– 1956) в 1920 г. построил [15] первую трехзначную логику, в которой значения истинности принадлежат множеству {"ложь", "возможно", "истина"} или множеству { о,^, 1 } , в ней не верен закон исключенного третьего, но выполняется закон исключенного четвертого

A v A v A . Трехзначная логика Лукасевича была построена в связи с анализом проблемы логического статуса высказываний о будущих случайных событиях и связанной с ней проблемой логического фатализма. Лукасевич известен как знаток работ Аристотеля. В девятой главе трактата "Об истолковании" Аристотель ставит следующую проблему: верно ли, что относительно единичного и вместе с тем будущего события всякое утверждение или отрицание истинно или ложно? Верно ли, например, что относительно завтрашнего морского сражения истинно или ложно утверждение "завтра морское сражение произойдет" или отрицание – "завтра морское сражение не произойдет?" Эта проблема оказалась весьма продуктивной для развития логики: распространенным является мнение, что именно многочисленные попытки логической реконструкции подхода Аристотеля к решению проблемы будущей случайности привели к появлению многозначных логик. Лукасевич, комментируя высказывания Аристотеля о будущих случайных событиях, приходит к выводу, что Стагирит сомневался в универсальности принципа исключенного среднего, тогда как решительным сторонником двузначности были стоики во главе с Хрисиппом. Поэтому Лукасевич называет новую, трехзначную логику не неаристотелевской, а нехри-сипповой.

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

В 1922 г. Лукасевич обобщил трехзначную логику до логики, имеющей произвольное конечное число истинностных значений.

В 1930-е гг. Лукасевич оценивал свое изобретение многозначных логик так: "Я сразу осознал, что среди всех многозначных систем только две могут претендовать на философскую значимость: трехзначная система и система бесконечнозначная. Считаю, что именно этой последней системе принадлежит первенство среди прочих" [16]. И далее: "Все же мне кажется, что философское значение представленных здесь систем логики может быть по меньшей мере так же велико, как и значение неэвклидовых систем геометрии".

Известный американский логик Е.Т. Белл считал, что открытие Лукасевичем многозначных логик является одним из четырех важнейших открытий в последние 6000 лет [8].

Позже, в 1953 г., Лукасевич изменил свой взгляд на философскую значимость трех- и бесконечнозначной систем логики. Он предполагал, что многозначные системы исчисления высказываний и предикатов послужат основанием для исследований в арифметике и теории множеств.

Польский исследователь львовско-варшавской философской школы Я. Волень-ский в 1985 г. писал, что "в настоящий момент ожидания Лукасевича несомненно не исполнились. Многозначные логики не совершили революции ни в логике, ни в математике, ни в философии" [4]. Мы, однако, заметим, что идея многозначности оказалась весьма продуктивной, получила развитие и многочисленные применения, как и иные достижения логики.

Нечеткая логика Лотфи Заде

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

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

Основы нечеткой логики были заложены в конце 1960-х гг. в работах известного американского математика (выходца из советского Азербайджана) Лотфи Заде.

Лотфи Заде

Его исследования были вызваны возрастающей потребностью построения таких интеллектуальных систем, которые были бы способны адекватно взаимодействовать с человеком. Для таких систем был необходим новый математический аппарат, который способен переводить неоднозначные утверждения естественного языка на язык четких ма- тематических формул. Первым серьезным шагом в этом направлении стала теория нечетких множеств, разработанная Заде. Его работа "Fuzzy Sets", опубликованная в 1965 г. [20], заложила основы моделирования интеллектуальной деятельности человека и стала начальным толчком к развитию новой математической теории. Он же дал и название для новой области науки – "fuzzy logic" (fuzzy – нечеткий, размытый, мягкий) [21]. Дальнейшие работы профессора Лотфи Заде и его последователей заложили фундамент новой теории и создали предпосылки для внедрения методов нечеткого управления в инженерную практику.

Теория алгоритмов

В 1930-х гг. XX в. в рамках математической логики усилиями А.Чёрча, А.Тьюринга и Э. Поста были заложены основы теории алгоритмов, которая буквально преобразила математическую логику и многократно увеличила ее прикладное значение.

Алонзо Чёрч

В течение долгих лет математическая логика оставалась глубинной областью математики и логики, обслуживающей внутренние потребности этих наук. Казалось, что математическая логика не может иметь никаких конкретных приложений. Однако во второй половине XX в. стали устанавливаться новые связи между науками, открылись новые приложения наук. Этот процесс сопровождался проникновением математических методов в разные области знания и затронул математическую логику.

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

Потребность в строгом определении понятия алгоритма и вычислимой функции возникла еще во второй половине XIX в. и обострилась к 1930-м гг. XX столетия. Ряд внутриматематических обстоятельств, таких как кризис оснований математики, логические парадоксы, крах программы Гильберта тотальной формализации математики, привели к созданию течения математического конструктивизма. Конструктивисты признавали только такие доказательства теорем существования, для которых удается указать алгоритм построения. Это требование "активизировало" термин "алгоритм" и способствовало возникновению теории алгоритмов.

С другой стороны, к 1930-м гг. в математике накопились задачи, которые специалисты склонны были считать алгоритмически неразрешимыми. Для строгого доказательства алгоритмической неразрешимости требовалось строгое определение алгоритма, попытки которого были предприняты почти одновременно в 1936 г. несколькими математиками: Алонзо Чёрчем [11], Эмилем Постом [17] и Аланом Тьюрингом [18]. Чёрч аксиоматически определил класс рекурсивных функций, отождествив понятия рекурсивной и вычислимой функции. Тьюринг и Пост определили алгоритмический процесс, реализуемый на некоторой вычислительной машине, называемой, соответственно, "машиной Тьюринга" и "машиной Поста". Третий подход к определению алгоритма предложил А.А. Марков [5], который под алгоритмом понимал процесс преобразования слов, записанных в некотором алфавите. Марков назвал свои алгоритмы нормальными (в авторской транскрипции – "алгорифмы"). Перечисленные подходы привели к построению одного и того же класса алгоритмически вычислимых функций.

Строгое определение алгоритма позволило доказать ряд фундаментальных результатов. Среди них – доказательство П.С. Новикова алгоритмической неразрешимости классической проблемы тождества в конечно определенных группах (1952 г.), доказательство Ю.В. Матиясевича неразрешимости 10-й проблемы Гильберта о разрешимости диофантова уравнения с произвольными неизвестными и целыми рациональными числовыми коэффициентами (1970 г.).

Теория алгоритмов оказала существенное влияние на развитие ЭВМ и практику программирования. В теории алгоритмов были предугаданы основные концепции проектирования вычислительной аппаратуры и языки программирования. Упоминаемые выше три способа определения алгоритма спо- собствовали развитию разных направлений в программировании:

– микропрограммирование восходит к идеям построения машин Тьюринга;

– структурное программирование заимствует идеи из теории рекурсивных функций;

– языки символьной обработки информации берут свое начало от нормальных алгоритмов Маркова и систем Поста.