1. Основні напрямки [ правити ]
2. Поняття з теорії чисел [ правити ]
3. Булева функція [ правити ]
4. 0-арні функції [ правити ]
5. Унарні функції [ правити ]
6. Бінарні функції [ правити ]
7. Тернарние функції [ правити ]

Існують досить тонкі відмінності в термінології різних наук, що і потрібно спочатку розглянути, щоб чітко розуміти в якому контексті що мається на увазі. Почнемо нашу подорож від формальної логіки до штучного інтелекту, і подивимося як на історичному шляху змінювався сенс деяких загальних термінів.

Дискретна математика утворилася в результаті застосування методів теорії чисел до математичній логіці . Необхідність вирішення різних теоретичних, а потім і практичних завдань, в областях, в яких не придатні розділи математики оперують безперервністю , Привели до створення ряду математичних розділів описаних нижче. У сукупності вони і утворюють дискретну математику.

Основні напрямки [ правити ]

Дискретна математика включає кошти, які застосовуються над об'єктами, здатними приймати тільки окремі, не безупинні значення.

комбінаторика [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 -арної булевих функцій дорівнює 22 n. Тому в цьому розділі розглядаються тільки найпростіші і найважливіші булеві функції. Те, що кожна булева функція задається кінцевим масивом даних, дозволяє представляти їх у вигляді таблиць. Такі таблиці звуться таблиць істинності .

0-арні функції [ правити ]

При n = 0 кількість булевих функцій зводиться до двох 220 = 21 = 2, перша з них тотожно дорівнює 0, а друга 1. Їх називають булевими константами - тотожний нуль і тотожна одиниця.

Унарні функції [ правити ]

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

Назви булевих функцій від однієї змінної:

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

Бінарні функції [ правити ]

При n = 2 число булевих функцій одно 222 = 24 = 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, x y, 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 число булевих функцій одно 223 = 28 = 256.

Назви булевих функцій трьох змінних:

Позначення Назви x ↓ {\ displaystyle \ downarrow} y ↓ {\ displaystyle \ downarrow} z = ↓ {\ displaystyle \ downarrow} (X, y, z) = Webb2 (x, y, z) 3ІЛІ-НЕ, функція Вебба, функція Даггера, стрілка Пірса ¬ (> = 2 (x, y, z)) {\ displaystyle \ neg (> = 2 (x, y, z))} Перемикач по більшості з інверсією, 3ППБ-НЕ, мажоритарний клапан з інверсією x ≠ y ≠ z = [≠ (x, y, z)] = NE (x, y, z, v) Нерівність x | {\ displaystyle \ mid} y | {\ displaystyle \ mid} z = | {\ displaystyle \ 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⊕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 століття в роботах А. Тьюринга, А. Черча і Е. Посту. Запропоновані ними машина Тьюринга, машина Посту і лямбда-числення Черча виявилися еквівалентними один одному.