Жар холодных числ и пафос бесстрастной логики [заметки]
*
* Э. Николау. Введение в кибернетику. С добавлениями автора русскому изданию. Перев. с румынского. М., 1967, с. 11.
**
* Материалы XXV съезда КПСС. М., 1976, с. 170.
**
** Там же, с. 214.
1
1. Платон. Сочинения. В 3-х т., т. 1. М., 1968; т. 2. М., 1970;
т 3, ч. 1. М., 1971; т. 3, ч. 2. М., 1972. «Апология Сократа», о которой пойдет речь ниже, помещена в т. 1.
5
2. Платон. Сочинения, т. 1, с. 83—84.
6
3. Гиппократа, персонажа этого диалога Платона, не следует смешивать с его современником — знаменитым древнегреческим врачом Гиппократом Косским (прибл. 460—377 гг. до н. э.).
7
4. Платон. Сочинения, т. 1, с. 191—193.
8
5. См. А. Ф. Лосев. Комментарии.— В кн.: Платон. Сочинения, т. 2. с. 590.
9
6. Платон. Сочинения, т. 2, с. 404—405.
10
7. На эти слова Канта очень часто ссылаются, но очень редко их цитируют. Вот что дословно говорит Кант: «так как во всяком учения о природе имеется науки в собственном смысле лишь столько, сколько имеется в ней априорного познания, то учение о природе будет содержать науку в собственном смысле лишь в той мере, в какой может быть применена в нем математика» (И. Кант. Сочинения. В 6-ти т., т. 6. М., 1966, с. 59). Таким образом, кантовский тезис о «математичности» как мере научности был связан с общей априористской концепцией Канта.
11
8. Платон. Сочинения, т. 2, с. 416.
12
9. В переводе с греческого «органон» означает орудие (метод) исследования; под этим названием комментаторы Аристотеля объединили пять его сочинений по логике и методам научного познания: «Категории» (русск. перев. 1939 г.) «Об истолковании» (русск. дерев. 1891 г.), «Аналитики первая и вторая» (русск. перев. 1952 г.), «Топика» и «Опровержение софистических аргументов».
13
10. Аристотель. Аналитики первая и вторая. [М.], 1952, с. 14—15 (см. также примечения к русскому переводу с. 293).
14
11. Я. Лукасевич. Аристотелевская силлогистика с точки зрения современной формальной логики. Перев. с англ. М, 1959, с. 189, Ян Лукасевич в данной книге (вышедшей на англ. языке в 1951 г.) систематически исследовал силлогистику Аристотеля с позиций современной математической логики.
15
12. Аристотель создал не только силлогистику — в его трудах мы находим исследование дедуктивного метода (о котором речь пойдет в дальнейшем), логических модальностей (им изучалась логика рассуждений, в которых существенную роль играют модальные выражения «необходимо, что...», «возможно, что...», «невозможно» что...» и т. п.), определений, простейших обобщающих (индуктивных) умозаключений, аналогии, логических ошибок и до.
16
13. L. Falmar. Foundations of Mathematics, wether now? - "Problems of the Philosophy of Mathematics" (Proceedings of the International Colloquiumin the Philosophy of Science, London, 1965, vol.1) Amsterdam, 1967, p.188. Из работ А. Сабо, обосновывающих этот тезис, укажем: А. Сабо. О превращении математики в дедуктивную науку и начале ее обоснования.— В кн.: Историко-математические исследования. Вып. XII. М., 1959.
17
14. О влиянии логико-методологических идей Аристотеля на древнегреческую математику см. С. А. Яновская. Из истории аксиоматики.— В кн.: С. А. Яновская. Методологические проблемы науки. М., 1972.
18
1. Дж. Свифт. Сказка бочки. Путешествия Гулливера. М., 1976, с. 293-294.
19
2. См. Ф. Рабле. Гаргантюа и Пантагрюэль. М., 1973, книга вторая, глава VIII (она содержит письмо Гаргантюа, в котором он рекомендует своему сыну Пантагрюэлю оставить без внимания астрологию и искусство Луллия как «науки пустые и лживые»).
20
3. В трактате «О достоинстве и преумножении наук» (1623) Ф. Бэкон сравнивал «искусство Луллия» с лавкой старьевщика, «где можно , найти множество тряпья, но нельзя найти ничего, что имело бы хоть какую-нибудь ценность» (Ф. Бэкон. Сочинения. В 2-х т.. т. 1. М., 1971, с. 349.
21
4. Предупреждаем, впрочем, что «искусство» Луллия было гораздо сложнее, чем может показаться из приведенного выше его краткого описания. Например, в его комбинаторике нашли свое место даже вопросительные предложения (заметим в этой связи, что логика вопросительных форм и по сей день остается мало разработанной). Читателя, желающего подробнее ознакомиться с логикой Луллия и его школы, мы отсылаем к книгам: В. Владиславлев. Логика. Обозрение индуктивных и дедуктивных приемов мышления и исторические очерки: логики Аристотеля, схоластической диалектики, логики формальной и индуктивной. Спб, 1881; Н. И. Стяжкин. Формирование математической логики. М.. 1967; М. Gardner. Logic Machines and Diagrams. New York - Toronto - London, 1958.
22
5. Большинство лейбницевых текстов логического содержания было впервые издано в 1901 и 1903 гг. Луи Кутюра. Впрочем, научное наследство Лейбница еще полностью не опубликовано; как отмечает И. С. Нарский в книге «Западноевропейская философия XVII века» (М., 1974, с. 281), в ганноверском архиве Лейбница хранится около 75 тысяч отдельных его работ.
23
6. По словам Б. Рассела, «есть две системы философии, каждую из которых можно рассматривать как представляющую взгляды Лейбница: одна, которую он открыто провозглашал, была оптимистической, ортодоксальной, фантастической и мелкой; другая, которую постепенно извлекали из его рукописей относительно недавние издатели, была глубокой, ясной, ... удивительно логичной» (Б. Рассел. История западной философии. М., 1959, с. 600).
24
7. О жизни и научном творчестве Лейбница в интересующей нас области см. книгу Н. И. Стяжкина, указанную в примечании 4. Философские взгляды Лейбница подробно освещены в книге И. С. Нарского, упомянутой в примечании 5. Облик Лейбница как ученого и человека обрисован в книге: И. Б. Погребысский. Готфрид Вильгельм Лейбниц. 1646—1716. М., 1971.
25
8. G.W. Leibniz. Fragmente zur Logik. Berlin. 1960, S. 16.
26
9. Там же.
27
10. Н. Винер. Кибернетика, или Управление и связь в животном и машине. Второе издание. М., 1968, с. 57.
28
11. Н. Винер. Кибернетика и общество. М., 1958, с. 32—33.
28
12. И.Слешинский. Логическая машина.— «Вестник опытной физики и элементарной математики». Одесса, 1893, № 175 (7).
29
13. Цитируется по статье: А. И. Берг. Кибернетика и общественные науки.— В кн.: Методологические проблемы науки. Материалы заседания Президиума Академии наук СССР. М., 1964, с. 260. О машине Джевонса в России, усовершенствованной известными физико-химиками П. Д. Хрущевым и А. Н. Щукаревым, см.: В. А. Велигжанин, Г.Н. Поваров. К истории создания логических машин в России.-«Вопросы философии», 1971, № 3.
30
14. Ст. Джевонс. Основы науки. Трактат о логике и научном методе. Спб, 1881, с. 2. В этой книге читатель найдет подробное и очень доступное изложение алгебры логики Джевонса — теории, в которой впервые в логике фактически присутствовало то, что ныне называется булевой алгеброй (см. следующую главу). В нашем изложении мы несколько изменили символику Джевонса, приблизив ее к современной. Примеры, которыми мы оперируем, принадлежат Джевонсу.
31
15. Операция пересечения двух произвольных классов (множеств) — это операция, порождающая такой класс — его обычно обозначают А ∩ В или просто AВ, как в нашей записи, который состоит из элементов, входящих как в класс A, так и в класс В. В дальнейшем будут использоваться также понятия объединения двух классов и дополнения к классу. Операцией объединения произвольных классов A и В называется операция, порождающая такой класс (он обозначается через A ∪ В), который состоит из элементов, входящих хотя бы в один из классов: в A или в В.
Операция взятия дополнения к произвольному классу A (до некоторого объемлющего универсального класса, или универсума, V) есть операция, порождающая класс, состоящий из всех тех и только тех) элементов универсума, которые не входят в класс А; дополнение к А обозначается через A' или -A. Заметим, что операции пересечения и объединения классов обладают свойством коммутативности (перестановочности, симметричности), то есть А ∩ В = В ∪ А, А ∪ В = В ∩ А (это свойство используется ниже в примере 3).
32
16. Действительно, по закону исключенного третьего:
A = AB ∪ AB' = ABC ∪ ABC' ∪ AB'C ∪ AB'C', A' = A'B ∪ A'B' = А'ВС ∪ А'ВС' ∪ AВ'С ∪ А'В'С' но, как очевидно, A ∪ A' = V.
33
1. G. Вооlе. The Mathematical Analysis of Logic. Cambridge and London, 1847; G. Вооlе. An Investigation of the Laws of Thought. London, 1854.
34
2. Е. Т. Веll. Men of Mathematics. New York. 1962, p. 433. О своеобразии английской математики того времени, объясняющем тот факт, что математическая логика возникла в Англии, см.: Б. В. Бирюков, А. А. Коноплянки н. Развитие логико-математических идей как элемент исторической подготовки кибернетики (на примере развития английской науки в 19 и начале 20 вв.).— «Вестник истории мировой культуры», 1961, № 6 (30).
35
3. Формулы вида (а & β) и (а V β) мы будем называть соответственно конъюнктивной и дизъюнктивной формулами (или формами, когда появится понятие формы), иногда же просто «конъюнкциями» и «дизъюнкциями».
36
4. Метазнак (греч. «мета» — за, после) — знак, обозначающий знак или конструкцию из знаков данного алфавита и не принадлежащий к этому алфавиту. В данном случае метазнаки обозначают произвольные формулы.
37
5. Строгое определение цепочки равенств выглядит следующим образом: а) каждое равенство есть (одночленная) цепочка равенств;
б) если Х — цепочка равенств, в которой последней формулой справа является формула φ и φ=χ;, то Х=χ — тоже цепочка равенств:
в) Других цепочек равенств, кроме устанавливаемых на основе пп. а) и б), не имеется.
38
6. Этот список постулатов основан на перечне равносильностей алгебры высказываний, приведенных в кн.: П. С. Новиков. Элементы математической логики. М.» 1973. с. 42.
39
7. Название связано с тем, что в математической логике законы 9 и 10 впервые сформулировал Де Морган. Однако соответствующие правила были известны уже средневековым логикам.
40
8. Вместо этого «общего» правила замены равным в число постулатов можно было бы ввести более «конкретное» правило: если а = β то (γ & а) = (γ & β). (а & γ) = (β & γ); (γ V а) = (γ V β), (а V γ)-(β V γ)» ~а= ~β. «Общее» правило замены равным оказывается в этом случае производным правилом: его можно обосновать с помощью «конкретного» правила замены равным.
41
9. Обращаем внимание на то, что мы не стремимся к независимости постулатов нашего аппарата. Например, свойство рефлексивности отношения равенства оказывается в данном построении производным от свойств симметричности и транзитивности этого отношения и каждой из схем аксиом 7, 8, 11—15. Со свойствами отношения равенства можно подробнее ознакомиться по кн.: А. Тарский. Введение в логику и методологию дедуктивных наук. М., 1948, с. 90 и далее. О философских вопросах, связанных в равенством и отождествлением, см: Д. П. Горский. Вопросы абстракции и образование понятий. М., 1961.
42
10. То есть (а → β) ≝ (~а V β), где ≝ есть знак «равенства выражений по определению» («графического» их совпадения). Мы будем считать, что к равенствам по определению тоже применимы правила [b] (ср. ниже с. 64—65 и 69—70).
43
11. Различного рода исчисления равенств оказываются весьма полезным инструментом во многих разделах логики и оснований математики (ср. кн.: Р. Л. Гудстеин. Рекурсивный математический анализ. М., 1970, в которой исчисление равенств используется для построения и исследования фрагментов конструктивной математики; о конструктивном направлении в математике см. ниже, гл. 5 и далее). Систематическое представление различных логических систем в виде соответствующих исчислений равенств было осуществлено Г. И. Сыркиным в его курсах лекций «Алгебраические методы в логике», читанных на философском факультете МГУ в 1974—1975 гг. 1
44
12. Столбцы для аргументов от остальной части таблицы мы отделяем двойной вертикальной чертой. Обращаем внимание на то, что фигурирующие в таблицах 0 и 1 не следует смешивать с константами 0 и 1.
45
13. С учетом интерпретации констант 0 и 1, которая будет дана ниже.
46
14. Мы не останавливаемся на некоторых деталях определения;
понятия «верные равенства формул», отсылая читателя к книге П. С. Новикова, указанной в примечании 6.
В этой книге говорится, правда, об отношении «равносильности» формул, но это по существу то же, что мы имеем в виду под совпадением функций (точнее, впрочем, то же, что в следующей интерпретации окажется равенством или равносильностью форм высказываний).
47
15. Вместо слов «формула а при данных значениях своих переменных переходит в истинное (или ложное) высказывание» мы будем употреблять и такое выражение: «формула а принимает такое-то (истинностное) значение», а также говорить: «формула а истинна (ложна)».
48
16. В связи с данной интерпретацией заметим, что со знаками → и ≡ можно было с самого начала поступить иначе: не вводить их определениями (как сокращения), а включить в сам язык формальной системы — в ее алфавит (расширив соответствующим образом пункт I в)). Это приведет к расширению понятия формулы и добавлению к системе постулатов схем аксиом для → и ≡. А именно, в пункт II (в) добавляется- «если а и β — формулы, то (а → β) и (а ≡ β) — тоже формулы», а к системе постулатов IV[a] присоединяются: 18. (а → β) = (~а V β) и 19. (а ≡ β) = (~а V β) & (а V ~β)). Пункт V при этом должен быть удален.
49
17. Ср. формулировку этих законов у Джевонса (с. 43). Очевидно, что способ «формульного» представления этих законов зависит от характера рассматриваемого логического аппарата.
рис. 7. Круговые схемы, изображающие пять возможных отношений между двумя произвольными классами а и β.
50
18. Аналогично, в школьной математике не пишут, скажем, ((а+b)+с)+d или (а+b)+(с+d) а записывают просто а+b+с+d.
51
19. Эрнет Шредер (E. Schroder, 1841—1902) является автором трехтомных «Лекций по алгебре логики» (Vorlesungen uber die Logik. Bd. 1-3, Leipzig, 1890—1905), знаменующих собой — вместе с трудами русского логика и астронома П. С. Порецкого (1846—1907) — вершину развития алгебры логики в прошлом столетии. Задача, которая приводится ниже, заимствована из первого тома «Лекций». Эту задачу приводила в своих лекциях по математической логике в Московском университете С. А. Яновская; мы приводим задачу в ее формулировке.
52
20. Впрочем, операции булевой алгебры можно задавать указанием и других наборов их свойств. О булевых алгебрах см., например:
И. М. Яглом. Алгебра Буля.— В сб.: «О некоторых вопросах современной математики и кибернетики». М., 1965.
53
21. Напоминаем, что здесь высказывание понимается «классически», то есть как выражение либо истинное, либо ложное, но не то и другое вместе.
54
22. При другом подходе булевой алгеброй для логической интерпретации нашего аппарата можно считать множество форм высказываний (рассматриваемых с точностью до отождествления равносильных форм) вместе с заданными на них операциями ~, &. V - такая булева алгебра высказываний оказывается алгеброй Линденбаума — Тарского, о которой см.: Е. Расёва, Р. Сикорскии. Математика метаматематики. М., 1972, с. 282 и далее.
55
23. Заметим, что булеву алгебру можно сформулировать и на основе отношения ≤ (или ≥). См: X. Б. Карри. Основания математической логики. М., 1969.
56
24. Для этого имеются и другие причины. Дело в том, что в алгебре логики Буля можно определить операцию дизъюнкции, и тогда все равенства, верные в логике высказываний как булевой алгебре, будут верными и в теории Буля; с другой стороны, в рассмотренной нами теории можно определить строгую дизъюнкцию (например, так:
(А V B)≝((A & ~В) V (~А & В)), и тогда теория Буля может быть пред. ставлена как теория булевой алгебры (в узком смысле).
57
25. Понятие формы класса (классовой формы) следует понимать по аналогии с понятием «форма высказывания».
57
26. Ср. примечание 14.
58
27. Заметим, что при проверке схем аксиом, в каждой из которых фигурирует по две формы классов, следует учитывать возможные отношения между двумя произвольными классами а и β. Таких отношений может быть пять: классы а и β совпадают; класс а полностью входит в класс β, причем в β имеются элементы, не принадлежащие а; то же отношение, но с заменой а на β и наоборот; классы а и β имеют общие элементы, причем в а есть элементы, не принадлежащие классу β, и в β есть элементы, не принадлежащие а; классы а и β не имеют общих элементов. Эти отношения можно передать следующими схемами (рис. 7). Проверяя равенство, нужно убедиться в его справедливости при каждом из этих отношений.
59
28. Абстрактное понятие булевой алгебры есть достижение середины нашего века, в то время как его спецификации — на классах и высказываниях — восходят к логикам прошлого века. Применению аппарата булевой алгебры к исследованию релейно-контактных схем начало положили в 1935—1938 гг. В. И. Шестаков, А. Никасима и К. Шеннон, один из создателей кибернетики (см. его статью «Символический анализ релейных и переключательных схем», в русском переводе опубликованную в кн.: К. Шеннон. Работы по теории информации и кибернетике. М., 1963). «Приоритет в применении аппарата математической логики к вопросам электротехники (связанным с построением релейно-контактных схем), — отмечает С. А. Яновская, принадлежит... В. И. Шестакову, работа которого «Алгебра релейно-контактных схем»... написанная еще в январе 1935г., к сожалению, не была своевременно опубликована, хотя и легла в основу его кандидатской диссертации» (Послесловие редакции в кн: А. Тарекии. Введение в логику и методологию дедуктивных наук. М., 1948. с. 320).
60
1. Эти — и другие — высказывания выдающихся мыслителей о математике см. в кн.: Е. Т. Веll. Men of Mathematics. N. Y. 1962, XV—XVII.
61
2. См. об этом в кн.: В. Н. Молодший. Очерки по философским вопросам математики. М., 1969, ч. II, гл. 2.
62
3. Конечную дробь, то есть (периодическую) дробь с «хвостом» из одних нулей (например, 3,14000...) при этом заменяют бесконечной периодической дробью с девяткой в периоде (в нашем примере— дробью 3,13999...).
63
4. Если действительное число есть рациональное число, то есть если десятичная дробь является периодической, то с бесконечностью можно «справиться» тривиальным способом, рассматривая число как дробь p/q, где p и q — целые числа, а q отлично от нуля.
64
5. E. Т. Веll. Men of Mathematics. N. Y., 1962. p. 431.
65
6. С теорией Дедекинда можно подробнее познакомиться по изложению автора. См.: Р. Дедекинд. Что такое числа и для чего они служат. Казань, 1905.
7. См. Г.М. Фихтенгольц. Основы математического анализа. Т. 1. М., 1960, с. 17.
66
8. Априори возможен еще случай, когда в левом классе есть наибольшее число, а в правом — наименьшее. Однако нетрудно показать, что такой случай противоречит свойствам сечения.
67
9. См. об этом подробнее в кн. В. Н. Молодшего, указанной в примечании 2.
68
10. Б. Рассел. История западной философии. М., 1959, с. 56.
69
11. Цитируется по кн.: Н. Бурбаки. Очерки по истории математики. М., 1963. с. 29.
70
12. См. об этом в кн.: История математики. Т. 1. М., 1970, с. 292 и далее.
71
13. См. статью Л. Кальмара, указанную в примечании 13 к гл.1, е.188,
72
14. С основными идеями Г. Кантора можно ознакомиться по трем его работам, имеющимся в русском переводе (опубликованы в издании:
Новые идеи в математике. Вып. 6. Спб, 1914).
73
15. С. К. Клини. Введение в метаматематику. М., 1957, с. 14.
74
16. Этот результат был в определенном смысле обобщением следующего свойства конечных множеств. Пусть дано, скажем, множество из трех элементов М = {а, b, с}. Помимо пустого множества, по определению входящего во всякое множество, и самого множества M, входящего в самое себя, в нем содержатся следующие подмножества: {а}, {b}, {с} {а, b}, {а, с}, {b, с}; таким образом, множество всех подмножеств множества из трех элементов содержит 8, или 2>3 элементов. Легко доказать, что если исходное множество содержит n элементов, то множество всех его подмножеств будет содержать 2>n элементов. Поэтому в случае конечных множеств количественное превосходство производного множества над исходным очевидно. Но когда речь идет о бесконечных множествах, вопрос становится не таким просты»: Кантор доказал, что и в этом случае производное множество превзойдет исходное; правда, здесь уже нельзя будет сказать, что в нем окажется больше элементов — и там и там их бесконечно много, а следует говорить, что оно обладает большей мощностью. Термин «мощность» Кантор определил математически строго. См. гл. I книги С. К. Клини, указанной в примечании 15.
75
17. G. Frege. Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. Halle, 1879; G. Frege. Grundgesetze der Arithmetik, begriffsschrift lich abgeleitet. Bd. I, Jena, 1893; Bd. II, Jena, 1902:
Общую характеристику вклада Фреге в логику и основания математики см. в статье Б. В. Бирюкова «О работах Фреге по философским вопросам математики», помещенной в сборнике «Философские вопросы естествознания», вып. 2, [М], 1959.
76
18. В рассмотренном нами в гл. 3 исчислении равенств это были знаки → и ≡.
77
19. При этом в интерпретациях этого исчисления — если не иметь в виду интуиционистскую и подобные ей «неклассические» логики, о которых пойдет речь ниже, присутствуют булевы алгебры.
78
20. В построении самого Фреге фигурировали не схемы аксиом, а конкретные аксиомы, в связи с чем в числе постулатов имелось еще одно правило вывода — так называемое правило подстановки. Однако мы следуем его системе лишь в самых общих- чертах. Заметим, что символика Фреге резко отличалась от обычной линейной логической и математической символики. Она носила «рисунчатый» характер и не привилась.
79
21. Используя «родство» эквиваленции (которую без труда можно ввести в исчисление Фреге) с отношением равенства и согласовав выразительные средства этого исчисления со-средствами описанного в гл. 3 исчисления равенств (равносилъноетей) формул, можно показать, что эти исчисления в определенном смысле переводимы друг в друга — имеют одинаковую дедуктивную силу.
80
22. Ниже излагается лишь общая идея фрегевского определения натуральных чисел. Полностью изложить его подход здесь, разумеется, не представляется возможным.
81
23. Об определении натуральных чисел как конечных кардинальных чисел (по Кантору) см., например: Н. Бурбаки. Теория множеств. М., 1965, с. 197 и далее.
81
24. J. van Heienoort. From Frege to Godel. A Source Book in Mathematical Logic. Cambridge (Mass.), 1967, p. 124—125.
82
25. Под идеографией Рассел имеет в виду логическую символику.
83
26. В теории Фреге предикаты рассматривались как частный случай функций, а именно, как функции, принимающие в качестве своих значений значения «истинно» и «ложно». Эта точка зрения на предикаты общепринята и в настоящее время при содержательном исследовании закономерностей «мира свойств и отношений».
84
27. Имеется в виду книга Б; Рассела «Принципы математики», которая вышла два года спустя(В. Russell. The Principles of Mathematics. Cambridge (Engl.), 1993).
85
28. Этими словами начинается послесловие Фреге ко второму тому «Основных законов арифметики» (с. 253).
86
29. X. Б. Карри. Основания математической логики. М., 1969, с. 32.
87
30. См. L. Kreiser. Geschichte und logisch-semantische Probleme des wissenschaftlichen Werkes Fregess. In: G. Frege. Schriften zur Logik. Aus dem Nachlaβ. Berlin. 1973.
88
31. Это стало известно после опубликования первого тома научного наследства Фреге: G. Frege. Nachgelassene Schriften. Bd. I. Hamburg, 1969. В рецензии на эту книгу, написанной Б. В. Бирюковым и Н. Н. Нуцубидзе и помещенной в издании «Новые книги за рубежом по общественным наукам», 1974, 6, читатель найдет рассказ об эволюции взглядов Фреге под конец жизни и о судьбе его научного наследия, в известном смысле разделившего научную трагедию Фреге.
89
32. Это была известная «теория тинов», разработанная Расселом еще до публикации «Principia Mathematica». О теории типов см. книгу С. К. Клини, указанную в примечании 15.
90
33. Следует вместе с тем заметить, что труд А. Н. Уайтхеда и Б. Рассела (A. N. Whitehead, B. Russell. Principia Mathematica. Vol. I, 1910; vol. II, 1912; vol, III, 1913, Cambridge, Engl.) явился важной: вехой в развитии математической логики и оснований математики. От него в знаяительной мере отправляются последующие работы в этой области, в частности исследования К. Гёделя (см. ниже).
91
1. Развертывание своей философско-матемагической платформы Брауэр начал со статьи «Недостоверность логических принципов», опубликованной в 1908 г. на голландском языке. Хорошее представление о взглядах Браузра дает кн.: Г. Веиль. О философии математики. М.-Л. 1934.
92
2. «Всякая наука. - считал Р. Декарт, заключается в достоверном и очевидном познании, которое есть деятельность интеллекта. Возможны только два действия интеллекта, «посредством которых мы можем придти к познанию вещей, не боясь никаких ошибок, это интуиция и дедукция, «поэтому из всех наук только математика чиста «от всего ложного и недостоверного»,; опытное же познание «часто вводит вас в заблуждение» (Р. Декарт. Набранные произведения. [М.]» 1950, с. 81—86). О параллелях между взглядами Декарта и философскими установками Брауэра см. ниже.
93
3. Что обе они не могут -выполняться— это гарантируется законом противоречия. Этот закон Брауэр не ставил под сомнение.
94
4. Но позиция Брауэра позволяет заключать от отвержения альтернативы α, например, путем приведения ее к абсурду, к верности высказывания ~α (этот способ рассуждения признает и конструктивизм, генетически связанный с брауэровской критикой классической математики и логики).
95
5. Цитируется по кн.: E.W. Beth. The Foundations of Mathematics. A Study in the Philosophy of Science. Amsterdam, 1965. p. 618—619.
96
6. Р. Декарт. Избранные произведения, с. 86.
97
7. См., например: Ж. Пиаже. Избранные психологические труды. [М.], 1959.
98
8. А. А. Марков. Комментарии.—В кн.: А. Рейтинг. Интуиционизм. Введение. М., 1965, с. 162.
98
9. При интуиционистской — не связанной с понятием алгоритма — трактовке конструктивности.
99
10. Мы набросали лишь идею доказательства. Точную формулировку теоремы и полное ее доказательство можно найти, скажем, в кн.:
Г.М. Фихтенгольц. Основы математического анализа. Т. I. М.. 1960, с. 105—106.
100
11. См. Д. Гильберт. Основания геометрии. М.— Л., 1948.
101
12. И вступил по этому поводу в полемику с Гильбертом (переписка Фреге и Гильберта по данному вопросу опубликована в «Sitzungsberichte der Heidelberger Akademie der Wissenschaften.». Jahrgang 1940, 6. Abhandlung, Heidelberg, 1940; 1941, 2. Abhandlung, Heidelberg, 1941).
102
13. Гильберт говорит: «с применением метода идеальных элементов связано одно условие, одно единственное, но необходимое, это доказательство непротиворечивости. Именно, расширение посредством пуюбщения идеальных элементов дозволено только в том случае, когда при этом в старой, более узкой области не-возникает никаких противоречий, то есть если соотношения, которые выявляются для старых образов при исключении идеальных образов, всегда остаются справедливыми в этой старой области» (Д. Гильберт. Обоснования математики. Добавление IX в его книге «Основания геометрии», с. 376).
103
14. Д. Гильберт. О бесконечном. Добавление VIII в его книге «Основания геометрии», с. 350.
104
15. См.: Проблемы Гильберта. М., 1969, с. 22.
105
16. Д. Гильберт. О бесконечном. Добавление VIII в его книге «Основания геометрии», с. 351.
106
17. Д. Гильберт. Обоснования математики. Добавление IX в его книге «Основания геометрии», с. 381—382. Под «реальными высказываниями» Гильберт имеет в виду высказывания, не содержащие «идеальных элементов».
107
18. Обращаем внимание на различие между доказательством теорем в формальной системе и доказательством теорем о самой формальной системе. Доказательства последнего рода называются метадоказательствами, а теоремы, в них доказываемые, метатеоремами. Что доказательства в формальной системе финитны — это очевидно, так как они представляют собой знаковые конструкции, то есть материальные объекты. Задача Гильберта состояла в том, чтобы придать финитный характер метадоказательствам.
108
19. Оно, правда, представляет собой сведение к абсурду, но в такой его форме, которая приемлема даже для Брауэра: ни закон исключенного третьего, ни закон снятия двойного отрицания (также отвергаемый интуиционистами) здесь не используется.
109
20. Этот доклад составляет добавление IX в книге «Основания геометрии».
110
21. П. С. Новиков. Элементы математической логики. М.» 1959, с. 36.
111
1. О содержании этой работы Гёделя можно подробнее прочесть в кн.: Э. М. Чудинов. Теория относительности и философия. М.. 1974, с. 232 и далее.
112
2. K. Godel. Uber formal unentscheidbare Satze der Principia Mathematica und vervandter Systeme. -— «Monatchefter fur Mathematik und Physik» Bd 38, 1931.
113
3. Понятие тождественной истинности, которое в гл. 3 было нами разъяснено в применении к формам высказываний, трактуемым на уровне логики высказываний (алгебры логики), естественным образом распространяется на классическую логику предикатов и строящиеся на ее основе логико-математические системы. Поскольку, однако, мы не можем здесь рассказать, как происходит такое распространение, мы будем вместо «тождественной истинности» употреблять более общее (хотя и менее определенное) понятие «содержательной истинности» (истинности по смыслу).
114
4. Заметим, что если из доказуемости (или истинности) некоторой формулы (высказывания) следует ее недоказуемость, то это не означает еще формально-логического противоречия. Таковое будет иметь место, если, кроме этого, из недоказуемости будет следовать доказуемость.
115
5. Отметим, что в своей теореме Гёдель использовал более сильное условие, чем «обычная» непротиворечивость, смысл которой был кратко пояснен в главе 5, с. 120—121. Однако впоследствии было показано, что для его теоремы достаточно и «обычной» непротиворечивости.
116
6. П. С. Новиков. Элементы математической логики. М., 1989, с. 36.
117
7. А. Н. Нагель. Дж. Р. Ньюмен. Теорема Гёделя. М., 1970. с. 58—60.
118
8. Краткий, но достаточно ясный обзор проблематики исследований формальных систем читатель найдет в гл. I кн.: С. Клини. Математическая логика. М., 1973.
9. Одно из таких доказательств приводится в кн.: Э. Мендельсон. Введение в математическую логику. М., 1971, с. 282—295.
119
1. Совокупность этих допущений составляет то, что обычно называют абстракцией потенциальной осуществимости. Представление об этой абстракции в явной форме было введено в логику и основания математики выдающимся советским ученым Андреем Андреевичем Марковым (род. в 1903 г.). См.: А. А. Марков. Теория алгорифмов. Труды Математического института АН СССР. т. ХШ. М.—Л.. 1954. с. 15; А. А. Марков. О логике конструктивной математики. М., 1972.
120
2. Более строго операцию подстановки можно задать следующим образом. По n-местным функциям q1..., gm и m-местной функции h строится n-местная функция f такая, что для любых x1, x2,..., Хn
f(x1, x2,..., Хn) = h(x1, ... Хn),... gm(x1,... Хn)).
121
3. Обращаем внимание на то, что в определениях операторов I—III знак равенства (=) следует понимать как знак так называемого условного равенства (≃). Соединение двух выражений, в которых могут фигурировать знаки частичных функций, знаком условного равенства,-понимается как следующее утверждение: для любого из двух выражений из того, что определено одно из них, вытекает, что определено и другое и их значения совпадают.
122
4. Отметим в этой связи, что приведенное там же определение функции δ подпадает под схему II для случая, когда отсутствуют параметры рекурсии (см. с. 137 — 138). Роль f играет функция δ, в качестве r берется 0, а в качестве h — проектирующая функция I>1>2.
122
5. См. А. И. Мальцев. Алгоритмы и рекурсивные функции. М., 1965, с. 12 и далее.
123
6. Имеется в виду статья: L. Kalmar. An Argument against the Plausibiolitu of Church's Thesis. «Constructivity in Mathematics. Proceedings of the Colloquium held at Amsterdam». Amsteerdam, 1959, p. 72—73.
124
7. Имеется в виду работа : А. Church. An Unsolvable Problem of Elementary Number Theory. «American Journal of Mathematics», vol. LVIII, № 2, 1936.
125
8. Характеристической (представляющей) функцией арифметического предиката P (х1, ..., Хn)называется такая арифметическая функция f, что для любого набора аргументов x1, ..., Хn
f(х1, ..., Хn) = (1, если предикат P выполняется на данном наборе) или (0, если P не выполняется на данном наборе.)
Предикат называется примитивно-, обще- или частично-рекурсивным в соответствии с типом характеристической функции.
126
9. В основополагающей статье А. Тьюринга (А. М. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem. «Proceedings of the London Mathematical Society», Ser. 2, vol. 42, 1936) была не только изложена его «машина», но и дана попытка проанализировать вычислительный процесс вообще. Обширный фрагмент из этой статьи Тьюринга можно в русском переводе найти в кн.: М. Минскии. Вычисления и автоматы. М., 1971, с. 138—142. Там же читатель найдет подробное описание Тьюринговых машин. Обращаем внимание на то, что наше изложение машины Тьюринга в соответствии с традицией, принятой в современных работах, в ряде непринципиальных пунктов отличается от тьюрингова.
127
10. Отметим, что приведенные нами машины Тьюринга, работающие над целыми положительными числами, служат лишь иллюстрацией тьюринговой формализации вычислительного процесса
128
11. Об упомянутых—и других—видах автоматов можно прочесть в интересной книге М. Г. Гаазе-Рапопорта «Автоматы и живые организмы» (М., 1961)
129
12. А. А. Марков. Теория алгорифмов, с. 3 (см. примечание 1)
130
13. С. Я. Яновская. О некоторых чертах развития математической логики и отношении ее к техническим приложениям.— В кн.: Применение логики в науке и технике. М., 1960, с. 10.
131
14. Диофантово уравнение — алгебраическое уравнение с целочисленными коэффициентами, для которого отыскиваются целые решения.
132
15. Проблемы Гильберта. М., 1969, с. 39.
133
16. Ф. П. Варпаховскии. А. Н. Колмогоров. О решении десятой проблемы Гильберта.— «Квант», 1970, № 7 у с. 42.
134
17. Ю. В. Матиясевич. Диофантовость перечислимых множеств.—Доклады АН СССР, 1970, т. !91, № 2.
135
18. А. А. Марков. Теория алгорифмов. См. примечание I.
136
19. Существуют и другие эквивалентные рассмотренным уточнения идеи алгоритма и вычислимой функции и в их числе «финитные комбинаторные процессы» Э. Поста (машина Поста). О машине Поста см. статьи В. А. Успенского в журнале «Математика в школе», 1967, № 1—4.
137
20. А. А. Марков. Теория алгорифмов, с. 92 (см. примечание 1). О философской основе конструктивной математики можно прочесть в кн.: В.Н. Тростников. Конструктивные процессы в математике. (Философский аспект). М., 1975.
138
1. Имеется в виду, что число x представлено в двоичной системе счисления и введено в память ЭВМ. В этом случае проверка условия x = 0 сводится к выяснению того, имеет ли хотя бы один элемент ячейки памяти, отведенной иод данное число, ненулевое значение, что, очевидно, технически нетрудно осуществить. Однако мы не останавливаемся здесь на устройстве ЭВМ и ее памяти, так как нас интересует логико-математическая сторона дела. О техническом аспекте действия ЭВМ и о физической реализации процесса запоминания см., например: Л. Н. Краснухин, П. В. Нестеров. Цифровые вычислительные машины. М. 1974.
139
2. Если функция f частично-рекурсивна, то при некоторых аргументах она может быть не определена, и процесс вычисления никогда не закончится. На первый взгляд рассмотрение в этом месте лишь общерекурсивных функций ограничивает общность рассуждений, однако, как мы увидим несколько ниже, это не так.
140
3. Заметим, что ЭВМ может вычислить или, по крайней мере, пытаться вычислить значение любой частично-рекурсивной функции (заранее не всегда известно, является ли интересующая нас функция общерекурсивной). Ибо, как показал С. К. Клини, каждую частично рекурсивную функцию можно представить в виде суперпозиции двух функций, первая из которых есть результат действия мю-оператора на некоторую примитивно рекурсивную функцию, а вторая — примитивно рекурсивная функция, вообще говоря, не совпадающая с упомянутой ранее.
140
4. И которая, конечно, абсолютно надежна в своем функционировании, то есть не допускает ошибок в переработке данных. Эта идеализация составляет содержание абстракции безошибочности как одного из упрощающих предположений, связанных с идеей эффективной вычислимости и понятием алгоритма. Об этой абстракции см. кн.: Управление, информация, интеллект. Под ред. А. И. Берга и др. М., 1976;
Б. В. Бирюков. Проблема абстракции безошибочности в логике. «Вопросы философии», 1973, №11.
141
5. См, его статьи «Машина для игры в шахматы» и «Составление программ для игры в шахматы на вычислительной машине» в кн.: К. Шеннон. Работы по теории информации и кибернетике. М., 1963. Обе статьи на английском языке впервые были опубликованы в 1950 году.
142
6. В принципе возможен еще и тот случай, что шахматы есть игра, «всегда выигрышная» для черных. Но многовековый опыт игры в шахматы опровергает такую возможность.
143
7. См. М.М. Ботвинник. О кибернетической цели игры. М„ 1975.
144
8. Об эвристических машинных программах и проблемах их разработки см.вкн.:Н.Нильсон. Искусственный интеллект. Методы поиска решений. М., 1973; Дж. Слэйгл. Искусственный интеллект. Подход на основе эвристического программирования М., 1973; Е. А. Александров. Основы теории эвристических решений. Подход к изучению естественного и построению искусственного интеллекта. М. 1975.
145
9. Следует отметить, что другой пионер теории вычислимости (теории алгоритмов)—А.Тьюринг—также был в числе тех, кто создавал первые универсальные цифровые вычислительные машины (этим он занялся еще до второй мировой войны, а после войны участвовал в разработке первого английского «компьютера»).
146
10. Коллега фон Неймана, хорошо его знавший, Е. Вигнер, дает выразительную характеристику этого ума. «Безупречная логика была наиболее характерной чертой его мышления. Он производил впечатление идеальной логической машины... отличительной чертой его ума была замечательная память..., он... свободно говорил на пяти языках и умел читать по-латыни и по-гречески». Трагическими были его последние дни. «Когда фон Нейман понял, что он неизлечимо болен, логика заставила его прийти к выводу, что он перестанет существовать и, следовательно, мыслить. Такое заключение, весь смысл которого непостижим для человеческого рассудка, ужаснуло его. Тяжело было видеть, как ум его, по мере того, как исчезали все надежды, терпел одно поражение за другим в борьбе с судьбой, казавшейся ему хотя и неизбежной, но тем не менее совершенно неприемлемой» (Е. Вигнер. Джон фон Нейман.— В кн.: Е. Вигнер. Этюды о симметрии. М., 1971, с. 207— 208). О фон Неймане см. также статью К. Шеннона «Вклад фон Неймана в теорию автоматов» в кн.: К. Шеннон. Работы по теории информации и кибернетике. М., 1963.
147
11. Дж. фон Нейман. Общая и логическая теория автоматов. В кн.: А. Тьюринг. Может ли машина мыслить? М., 1960, с. 90—91 (разрядка наша.— Лет.).
148
12. См. Б. В. Бирюков. Машина и мышление (три принципа).— В кн.: Художественное и научное творчество. Л., 1972, с. 255— 257.
149
13. Некоторые интересные проблемы сложных систем рассматриваются в кн.: Управление, информация, интеллект (см. примечание 4)
150
14. Читатель может ознакомиться с этим вопросом по работе фон Неймана, цитаты из которой мы приводили выше. На русском языке имеется также перевод труда фон Неймана «Теория самовоспроизводящихся автоматов» (закончено и отредактировано А. Бёрксом.М., 1971)
151
15. Представление о них можно почерпнуть из кн.: Б. А. Трахтенброт. Алгоритмы и вычислительные автоматы. М., 1974.
151
16. М. Бунге. Интуиция и наука. М., 1967, с. 137.
152
17. Мы не говорим здесь о тех гипотетических машинах далекого будущего, возможности которых обсуждает, например, Ст. Лем в книге «Сумма технологии» (М. 1968). И для автоматов, и для разумных существ этого «четвертого эшелона» прогнозов, которым занимается польский писатель, теряют силу нынешние категории ЭВМ и человека. Тем не менее мы рекомендуем читателю познакомиться с этой книгой, учтя послесловие к ней редакторов русского перевода.
153
* Укажем работы, не носящие узкоспециального характера:
Л. А. Заде. Тени нечетких множеств. «Проблемы передачи информации», 1966, т. II. вып. 1; Л. А. Заде. Расплывчатые алгоритмы.—Экспресс-информация «Техническая кибернетика», 1988, № 38; Н. Н.Воробьев. Развитие йауки и теория игр.— В кн.: Исследование операций. Методологические аспекты. М., 1972; В. В. Налимов. Вероятностная модель языка. О соотношении естественных и искусственных языков. М., 1974; Л. А. Заде. Основы нового подхода к анализу сложных систем и процессов принятия решений.— В кн.: Математика сегодня (Сборник переводных статей). М.» 1974; Б. В. Бирюков. Алгоритмический подход в науке и концепция расплывчатых алгоритмов.—В кн :
Кибернетика и современное научное познание. М., 1976; Управление, информация, интеллект. М., 1976(см.ч.1, гл.4; ч. III, гл.4;) Л. Заде. Понятие лингвистической переменной и его применение к принятию приближенных решений. М., 1976.
154
*Цит. по кн.: М. Льоцци. История физики. М., 1970, с. 241. 187
155
* Эта связь раскрывается в работе: Н. А. Шанин. О рекурсивном математическом анализе и исчислении арифметических равенств Р. Л. Гудстейна. Вступительная статья в кн.: Р. Л. Гудстейн. Рекурсивный математический анализ. М., 1970.
156
** См. об этом в ки.: В. Н. Тростников. Конструктивные процессы в математике. (Философский аспект). М.» 1975.
