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

Факультет логики
| ||||

На пути от человеческого разума, через логику к искусственному интеллекту | ||||

| ||||

| ||||

Дополнительные материалы:
|


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



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

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

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

Файл:DFAexample.svg | Файл:Caesar3.svg | Файл:6n-graf.png | |

Математическая логика | Теория вычислимости[1] |
Математическая криптография[2] |
Теория графов[3]
|


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

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

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

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

В теории функциональных систем (раздел дискретной математики) **булевой функцией** называют функцию типа *B* n →

*B*, где

*B*= {0,1} —

*булево множество*, а

*n*— неотрицательное целое число, которое называют арностью или местностью функции. Элементы 1 (единица) и 0 (ноль) стандартно интерпретируют как истину и ложь, хотя в общем случае их смысл может быть любым. Элементы

*B*

называют

*n**булевыми векторами*. В случае

*n*= 0 булева функция превращается в

*булеву константу*.

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

*n*-арных булевых функций равно 2

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

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

При *n* = 0 количество булевых функций сводится к двум 22 0 = 2

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

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

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

2= 4.

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

Обозначение | Название |
---|---|

0 | тождественный ноль, тождественная ложь, тождественное "НЕТ" |

x̅, ¬x, x'
|
отрицание, логическое "НЕТ", "НЕ", "НИ", "NOT"(англ.), "NO"(англ.) |

x
|
тождественная функция, логическое "ДА", "YES"(англ.) |

1 | тождественная единица, тождественная истина, тождественное "ДА", тавтология |


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

При *n* = 2 число булевых функций равно 22 2 = 2

4= 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 +2 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 число булевых функций равно 22 3 = 2

8= 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ППБ, мажоритарный клапан |

f
1 |
Разряд займа при тернарном вычитании |

f
2 |
Разряд переноса при тернарном сложении |

(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 века в работах А. Тьюринга, А. Чёрча и Э. Поста. Предложенные ими машина Тьюринга, машина Поста и лямбда-исчисление Чёрча оказались эквивалентными друг другу.