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

Материал из Викиверситета
Перейти к навигации Перейти к поиску
Факультет логики
На пути от человеческого разума, через логику к искусственному интеллекту
Lateral sulcus.gif
Venn diagram cmyk.svg
Spiral arrows wiggly.png
Дополнительные материалы:

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


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

Основные направления[править]

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

DFAexample.svg Caesar3.svg 6n-graf.png
Математическая логика Теория вычислимости[1] Математическая криптография[2] Теория графов[3]

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

Понятия из теории чисел[править]

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

Булева функция[править]

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

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

0-арные функции[править]

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

Унарные функции[править]

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

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

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

Бинарные функции[править]

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

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

Обозначение Название
0 тождественный ноль, тождественная ложь, тождественное "НЕТ"
xy, x ИЛИ-НЕ y, ИЛИ-НЕ(x,y), x NOR y, NOR(x,y) НЕ- 2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Да́ггера, функция Ве́бба, стрелка Пи́рса
x < y, xy, x LT y, LT(x,y) меньше, инверсия обратной импликации
, НЕ1(x,y), NOT1(x,y), x', ¬x отрицание (негация, инверсия) первого операнда
x > y, xy, x GT y, GT(x,y) больше, инверсия прямой импликации
, НЕ2(x,y), NOT2(x,y), y', ¬y отрицание (негация, инверсия) второго операнда
xy, x +2 y, xy, 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, xy, x AND y, AND(x,y), x И y, И(x,y), min(x,y) 2И, конъюнкция
xy, x = y, x EQV y, EQV(x,y), x ~ y, xy равенство, эквивалентность
y, ДА2(x,y), YES2(x,y) второй операнд
xy, xy, xy, x LE y, LE(x,y) меньше или равно, прямая (материальная) импликация (от первого аргумента ко второму)
x, ДА1(x,y), YES1(x,y) первый операнд
xy, xy, xy, x GE y, GE(x,y) больше или равно, обратная импликация (от второго аргумента к первому)
xy, x + y, x ИЛИ y, ИЛИ(x,y), x OR y, OR(x,y), max(x,y) 2ИЛИ, дизъюнкция
1 тождественная единица, тождественная истина, тождественное "ДА", тавтология

Тернарные функции[править]

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

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

Обозначения Названия
xyz = (x,y,z) = Webb2(x,y,z) 3ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса
Переключатель по большинству с инверсией, 3ППБ-НЕ, мажоритарный клапан с инверсией
x≠y≠z = [≠(x,y,z)] = NE(x,y,z,v) Неравенство
xyz = (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⊕2y⊕2z = x+2y+2z = ⊕2(x,y,z) = +2(x,y,z) Тернарное сложение по модулю 2
[>=2(x,y,z)] = (x И y) ИЛИ (y И z) ИЛИ (z И x) переключатель по большинству, 3ППБ, мажоритарный клапан
f1 Разряд займа при тернарном вычитании
f2 Разряд переноса при тернарном сложении
(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ИЛИ, максимум

Примечания[править]

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