Дискретная математика & математическая логика
..pdf
Ноам Хомский (англ. Avram Noam Chomsky, р. 1928) –
рис. 1.39 – лингвист, политический публицист и теоретик, является основателем формальных грамматик как раздела математической логики.
Рис. 1.39. Ноам Хомский
Логикой «высшего пилотажа» занимался Альфред Тарский
(польск. Alfred Tarski, 1901–1983) – рис. 1.40 – выдающийся поль-
ско-американский математик, логик, основатель формальной теории истинности.
Рис. 1.40. Альфред Тарский
31
«Высокая» логика также связана с именем Стивена Кука – рис. 1.41.
Рис. 1.41. Стивен Артур Кук
Стивен Артур Кук (англ. Stephen Arthur Cook, род. 14 декаб-
ря 1939 г.) – американский учёный в области теории вычислительных систем. Знаменит своей работой над теорией сложности вычислений, лауреат премии Тьюринга. В своей работе ’The Complexity of Theorem Proving Procedures’, Кук доказал, что задача выполнимости булевых формул является NP-полной. Тем самым он поднял вопрос о равенстве классов сложности P и NP, один из сложнейших вопросов теории вычислительных систем, на который до сих пор нет ответа.
Отечественные учёные
Мы должны помнить и чтить таких ученых, как Виктор Иванович Шестаков (1907–1987) – рис. 1.42. Виктор Шестаков – советский логик и теоретик-электротехник, который в середине 1930-х годов предложил интерпретацию булевой алгебры логики на релей- но-контактных схемах.
32
Рис. 1.42. Виктор Иванович Шестаков
В.И. Шестаков в 1938–1941 годах (фактически одновременно с американцем К. Шенноном и японцем Накашимой) показал возможность использования аппарата математической логики для синтеза и анализа релейно-контактных переключательных систем. А ведь до Шестакова, работавшего в Москве, в Казани работал И.И. Жегалкин (опередивший лет на тридцать американцев Рида и Миллера) [5]. А еще задолго до Жегалкина в Казани работал П.С. Порецкий, одна из основополагающих работ которого по математической логике датируется 1884 годом. На возможность использования алгебры логики при построении релейных схем впервые указал австрийский и нидерландский физик-теоретик Пауль Эренфест (1910 г.) – рис. 1.43, который в то время работал в Санкт-Петер- бурге, познакомился с А.Ф. Иоффе и другими молодыми русскими физиками, читал лекции в Петербургском политехническом институте, вел на дому теоретический семинар.
Большую роль сыграл Михаил Александрович Гаврилов
(1903–1979) – рис. 1.44. Ключевым моментом в жизни Михаила Александровича стало то, что в 1938 году он случайно оказал на семинаре Московского математического общества, на котором выступал физик из МГУ В.И. Шестаков с докладом о применении
33
алгебры Буля для описания структуры релейных схем. Михаил Александрович работу В.И. Шестакова считал революционной (похоже, что сам автор этого не понимал).
Рис. 1.43. Пауль Эренфест
Рис. 1.44. Михаил Александрович Гаврилов
Мэтром дискретной математики был и Виктор Михайлович Глушков (1923–1982) – рис. 1.45.
34
Рис. 1.45. Виктор Михайлович Глушков
В.М. Глушков – выдающийся советский математик и кибернетик. Решил обобщённую пятую проблему Гильберта. Под его руководством в 1966 году была разработана первая персональная ЭВМ «МИР-1» (машина для инженерных расчётов). Метод синтеза автоматов назван методом Хаффмана – Глушкова. Алгоритмическая логика была им сформулирована ещё до Хоара.
Логические схемы алгоритмов были предложены Алексеем Андреевичем Ляпуновым – рис. 1.46.
Рис. 1.46. Алексей Андреевич Ляпунов
35
Ляпунов Алексей Андреевич (1911–1973) – выдающийся математик, один из основоположников кибернетики, член-корреспондент АН СССР. Специалист в области теории функций вещественного переменного и математических вопросов кибернетики. Основные труды относятся к теории множеств, теоретическим вопросам программирования, математической лингвистике, математической биологии.
Первую в СССР кафедру дискретной математики в МГУ воз-
главил Олег Борисович Лупанов (1932–2006) – рис. 1.47 – совет-
ский, российский математик, академик РАН, декан механикоматематического факультета МГУ (1980–2006).
Рис. 1.47. Олег Борисович Лупанов
О.Б. Лупанов – это проблема самоприменимости в теории алгоритмов, асимптотические оценки сложности булевых функций.
Сергей Всеволодович Яблонский (1924–1998) – рис. 1.48 – со-
ветский и российский математик, один из основателей отечественной школы математической кибернетики. Автор ряда классических работ попроблемам синтеза, надежности и контроляуправляющих систем.
С.В. Яблонский – это теорема о функциональной полноте, сформулированная фактически одновременно с теоремой Поста.
Андрей Николаевич Колмогоров (1903–1987) – рис. 1.49 – со-
ветский математик, один из крупнейших математиков ХХ века.
36
Рис. 1.48. Сергей Всеволодович Яблонский
Рис. 1.49. Андрей Николаевич Колмогоров
В дискретной математике используются уравнения Колмогорова, используемые для анализа так называемых графов марковских цепей.
Виктор Ильич Варшавский – рис. 1.50, известен как созда-
тель научной школы синтеза и анализа апериодических (самосинхронных) автоматов.
Анатолий Абрамович Шалыто (р. 1948) – рис. 1.51 – уче-
ный, преподаватель, лауреат премии Правительства РФ 2008 года в области образования, профессор, доктор технических наук, заведующий кафедрой технологий программирования Санкт-Петер-
37
Рис. 1.50. Виктор Ильич Варшавский
Рис. 1.51. Анатолий Абрамович Шалыто
бургского национального исследовательского университета информационных технологий, механики и оптики, автор технологии автоматного программирования, названной switch-технологией, основатель «Движения за открытую проектную документацию» и движения «Сохраним в университетах лучших!».
38
2. КОМБИНАТОРИКА
Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».
2.1.РАЗБИЕНИЯ И ЧИСЛА СТИРЛИНГА
Висточниках [1–3] рассмотрены только некоторые типовые выборки: размещения, перестановки и сочетания. В комбинаторике же рассматриваются и другие типовые комбинаторные комбинации, например разбиения n-элементного множества на k подмножеств, которые называются блоками разбиения. Получить явную формулу для них не так просто, как для остальных конфигураций. Рассмотрим разбиения [4].
Разбиение множества X, состоящего из m элементов, на n блоков – представление его в виде объединения произвольного количествапопарно непересекающихся подмножеств. Например: Х = {1, 2, 3}.
Блоки разбиения:
1) {1}, {2}, {3} – 3 элемента;
2) {1}, {2, 3} – 2 элемента;
3) {2}, {1, 3} – 2 элемента;
4) {3}, {1, 2} – 2 элемента; 5) {1, 2, 3} – 1 элемент, это исходное множество. Всего 5 блоков.
Число Стирлинга второго рода
Число разбиений m элементного множества на n блоков называется числом Стирлинга второго рода и обозначается S (m, n):
S (m, 0) = 0; S (m, m) = 1; S (0, 0) = 1; S (m, n) = 0 при n > m; S (m, n) = S (m – 1, n – 1) + n ·S (m – 1, n).
39
Пример: S (3, 2) = 3; S (2, 1) = 1; S (2, 2) = 1; S (3, 2) = S (2, 1) +
+ 2 S (2, 2) = 1 + 2·1 = 3.
Число Стирлинга второго рода определяется с помощью сочетаний без повторений:
m−1
S (m, n) = ∑ Ci − S (i −1, n–1).
m 1
i =n−1
Число Стирлинга первого рода
Число Стирлинга первого рода s (m, n) – число размещений m предметов по n ящикам так, что все ящики заняты:
s (m, n) = n! S (m, n).
Число Белла
Число Белла [2] – число всех разбиений m-элементного множества:
m
B(m) = ∑ S (m, n), B(0) =1,
n=0
m
B(m +1) = ∑C(m, i)B(i).
i =0
Беспорядки
Беспорядком [4] называется подстановка, при которой ни один из элементов конфигурации не остается на своем месте. В рассмотренном примере беспорядков только два: β и ε (рис. 2.1).
Рис. 2.1. Беспорядки
40