От логики до ИИ/Дискретная математика

	Факультет логики
	На пути от человеческого разума, через логику к искусственному интеллекту
	Формальная логика; Математическая логика; Дискретная математика; Теория алгоритмов; Криптография; Вычислительная техника; Программирование; Когнитивная психология; Искусственный интеллект;
	Дополнительные материалы:

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

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

Основные направления

Дискретная математика включает средства, которые применяются над объектами, способными принимать только отдельные, не непрерывные значения.

$\forall x(P(x)\Rightarrow P(x'))$
Математическая логика	Теория вычислимости^[1]	Математическая криптография^[2]	Теория графов^[3]

Комбинаторика ^[4] — Теория множеств^[5] — Теория решёток^[6] — Теория дискретных функций — Теория алгоритмов^[7]

Понятия из теории чисел

В частности, нам будет интересно применение понятия p-адического числа из алгебраической теории чисел к обобщению булевой функции, в результате чего образуются математическое представление битовых (и более размерные) операции, которые затем будут реализованы в вычислительной технике, а часть из них будет представлена в программировании.

Булева функция

В теории функциональных систем (раздел дискретной математики) булевой функцией называют функцию типа Bⁿ → B, где B = {0,1} — булево множество, а n — неотрицательное целое число, которое называют арностью или местностью функции. Элементы 1 (единица) и 0 (ноль) стандартно интерпретируют как истину и ложь, хотя в общем случае их смысл может быть любым. Элементы Bⁿ называют булевыми векторами. В случае n = 0 булева функция превращается в булеву константу.

Каждая булева функция арности n полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины n. Число таких векторов равно 2ⁿ. Поскольку на каждом векторе булева функция может принимать значение либо 0, либо 1, то количество всех n-арных булевых функций равно 2^2ⁿ. Поэтому в этом разделе рассматриваются только простейшие и важнейшие булевы функции. То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц. Такие таблицы носят название таблиц истинности.

0-арные функции

При n = 0 количество булевых функций сводится к двум 2^2⁰ = 2¹ = 2, первая из них тождественно равна 0, а вторая 1. Их называют булевыми константами — тождественный нуль и тождественная единица.

Унарные функции

При n = 1 число булевых функций равно 2^2¹ = 2² = 4.

Названия булевых функций от одной переменной:

Обозначение	Название
0	тождественный ноль, тождественная ложь, тождественное "НЕТ"
x̅, ¬x, x'	отрицание, логическое "НЕТ", "НЕ", "НИ", "NOT"(англ.), "NO"(англ.)
x	тождественная функция, логическое "ДА", "YES"(англ.)
1	тождественная единица, тождественная истина, тождественное "ДА", тавтология

Бинарные функции

При n = 2 число булевых функций равно 2^2² = 2⁴ = 16.

Названия булевых функций от двух переменных:

Обозначение	Название
0	тождественный ноль, тождественная ложь, тождественное "НЕТ"
x ↓ y, x ИЛИ-НЕ y, ИЛИ-НЕ(x,y), x NOR y, NOR(x,y)	НЕ- 2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Да́ггера, функция Ве́бба, стрелка Пи́рса
x < y, x ← y, x LT y, LT(x,y)	меньше, инверсия обратной импликации
x̅, НЕ1(x,y), NOT1(x,y), x', ¬x	отрицание (негация, инверсия) первого операнда
x > y, x → y, x GT y, GT(x,y)	больше, инверсия прямой импликации
y̅, НЕ2(x,y), NOT2(x,y), y', ¬y	отрицание (негация, инверсия) второго операнда
x ⊕ y, x +₂ y, x ≠ y, x >< y, x <> y, x XOR y, XOR(x,y)	сложение по модулю 2, не равно, измена, исключающее «или»
x \| y, x NAND y, NAND(x,y), x И-НЕ y, И-НЕ(x,y)	НЕ-2И, 2И-НЕ, антиконъюнкция, штрих Ше́ффера
x & y, x · y, xy, x ∧ y, x AND y, AND(x,y), x И y, И(x,y), min(x,y)	2И, конъюнкция
x ≡ y, x = y, x EQV y, EQV(x,y), x ~ y, x ↔ y	равенство, эквивалентность
y, ДА2(x,y), YES2(x,y)	второй операнд
x → y, x ≤ y, x ⊃ y, x LE y, LE(x,y)	меньше или равно, прямая (материальная) импликация (от первого аргумента ко второму)
x, ДА1(x,y), YES1(x,y)	первый операнд
x ← y, x ≥ y, x ⊂ y, x GE y, GE(x,y)	больше или равно, обратная импликация (от второго аргумента к первому)
x ∨ y, x + y, x ИЛИ y, ИЛИ(x,y), x OR y, OR(x,y), max(x,y)	2ИЛИ, дизъюнкция
1	тождественная единица, тождественная истина, тождественное "ДА", тавтология

Тернарные функции

При n = 3 число булевых функций равно 2^2³ = 2⁸ = 256.

Названия булевых функций трех переменных:

Обозначения	Названия
x $\downarrow$ y $\downarrow$ z = $\downarrow$ (x,y,z) = Webb₂(x,y,z)	3ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса
$\neg (>=2(x,y,z))$	Переключатель по большинству с инверсией, 3ППБ-НЕ, мажоритарный клапан с инверсией
x≠y≠z = [≠(x,y,z)] = NE(x,y,z,v)	Неравенство
x $\mid$ y $\mid$ z = $\mid$ (x,y,z)	3И-НЕ, штрих Шеффера
x&y&z = &(x,y,z) = (x AND y AND z) = AND(x,y,z) = (x И y И z) = И(x,y,z) = min(x,y,z)	3И, минимум
(x=y=z) = [=(x,y,z)] = EQV(x,y,z,v)	Равенство
x⊕₂y⊕₂z = x+₂y+₂z = ⊕₂(x,y,z) = +₂(x,y,z)	Тернарное сложение по модулю 2
[>=2(x,y,z)] = (x И y) ИЛИ (y И z) ИЛИ (z И x)	переключатель по большинству, 3ППБ, мажоритарный клапан
f₁	Разряд займа при тернарном вычитании
f₂	Разряд переноса при тернарном сложении
(x+y+z) = +(x,y,z) = max(x,y,z) = (x OR y OR z) = OR(x,y,z) = (x ИЛИ y ИЛИ z) = ИЛИ(x,y,z)	3ИЛИ, максимум

Примечания

↑ Теория вычислимости берёт свое начало от диссертации Тьюринга (1936), в которой он ввел понятие абстрактной вычислительной машины, получившей впоследствии его имя, и доказал фундаментальную теорему о неразрешимости задачи о её остановке. Знаменитая теорема Гёделя о неполноте (1931) была доказана в терминах примитивно рекурсивных функций, класс которых в 1934 году Гёдель расширил до класса общерекурсивных функций. Формализм, развитый Гёделем оказался эквивалентным тьюринговскому (а также многим другим). Вместе с Тезисом Чёрча — Тьюринга этот факт явно продемонстрировал содержательность новой теории, и сейчас эти определения общеприняты в качестве формального аналога алгоритмически вычислимых функций.
↑ Началом математической криптографии является труд Клода Шеннона «Теория связи в секретных системах», представленным автором в 1945 году. В этой работе, был впервые показан подход к криптографии в целом как к математической науке.
↑ Годом рождения теории можно считать 1736 г. Л.Эйлер решил задачу о кенигсбергских мостах, которая привела к нахождению критерия существования в графе специального маршрута. Термин «граф» был предложен в 1936 г. венгерским математиком Д.Кенигом.
↑ Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».
↑ Создатель теории множеств — Георг Кантор. Разработал свою программу стандартизации математики, в рамках которой любой математический объект должен был оказываться тем или иным «множеством».
↑ Понятия «решётка» чётко сформулировал Р. Дедекинд в работах 1894 и 1897 годов. Как самостоятельное направление алгебры эта теория сформировалась в 30-х годах XX века. Наиболее важные классы решёток, кроме дедекиндовых, — это полные решётки, дистрибутивные решётки и булевы алгебры.
↑ Развитие теории алгоритмов начинается с доказательства К. Гёделем теорем о неполноте формальных систем, включающих арифметику, первая из которых была доказана в 1931 г. Возникшее в связи с этими теоремами предположение о невозможности алгоритмического разрешения многих математических проблем (в частности, проблемы выводимости в исчислении предикатов) вызвало необходимость стандартизации понятия алгоритма. Первые стандартизованные варианты этого понятия были разработаны в 30-х годах XX века в работах А. Тьюринга, А. Чёрча и Э. Поста. Предложенные ими машина Тьюринга, машина Поста и лямбда-исчисление Чёрча оказались эквивалентными друг другу.

[1] Теория вычислимости берёт свое начало от диссертации Тьюринга (1936), в которой он ввел понятие абстрактной вычислительной машины, получившей впоследствии его имя, и доказал фундаментальную теорему о неразрешимости задачи о её остановке. Знаменитая теорема Гёделя о неполноте (1931) была доказана в терминах примитивно рекурсивных функций, класс которых в 1934 году Гёдель расширил до класса общерекурсивных функций. Формализм, развитый Гёделем оказался эквивалентным тьюринговскому (а также многим другим). Вместе с Тезисом Чёрча — Тьюринга этот факт явно продемонстрировал содержательность новой теории, и сейчас эти определения общеприняты в качестве формального аналога алгоритмически вычислимых функций.

[2] Началом математической криптографии является труд Клода Шеннона «Теория связи в секретных системах», представленным автором в 1945 году. В этой работе, был впервые показан подход к криптографии в целом как к математической науке.

[3] Годом рождения теории можно считать 1736 г. Л.Эйлер решил задачу о кенигсбергских мостах, которая привела к нахождению критерия существования в графе специального маршрута. Термин «граф» был предложен в 1936 г. венгерским математиком Д.Кенигом.

[4] Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».

[5] Создатель теории множеств — Георг Кантор. Разработал свою программу стандартизации математики, в рамках которой любой математический объект должен был оказываться тем или иным «множеством».

[6] Понятия «решётка» чётко сформулировал Р. Дедекинд в работах 1894 и 1897 годов. Как самостоятельное направление алгебры эта теория сформировалась в 30-х годах XX века. Наиболее важные классы решёток, кроме дедекиндовых, — это полные решётки, дистрибутивные решётки и булевы алгебры.

[7] Развитие теории алгоритмов начинается с доказательства К. Гёделем теорем о неполноте формальных систем, включающих арифметику, первая из которых была доказана в 1931 г. Возникшее в связи с этими теоремами предположение о невозможности алгоритмического разрешения многих математических проблем (в частности, проблемы выводимости в исчислении предикатов) вызвало необходимость стандартизации понятия алгоритма. Первые стандартизованные варианты этого понятия были разработаны в 30-х годах XX века в работах А. Тьюринга, А. Чёрча и Э. Поста. Предложенные ими машина Тьюринга, машина Поста и лямбда-исчисление Чёрча оказались эквивалентными друг другу.

[1]

[2]

[3]

[4]

[5]

[6]

[7]