Зміст
Введення. Функції алгебри логіки.
Розкладання функцій за змінними. Досконала діз'юнктівная нормальна форма.
Висновки по першим двом темам. СКНФ.
Разрешімoсть завдань в класичній теорії алгоритмів.
Трудомісткість алгоритмів.
Пам'ять і час як кількісна характеристика алгоритму. (Стосовно до машини Тьюринга і сучасним ЕОМ).
Трудомісткість алгоритму на прикладі RSA, квантові комп'ютери.
Висновок.
Введення. Функції алгебри логіки
Будь формула алгебри логіки залежить від змінних висловлювань x 1 , x 2 ... x n , Повністю визначають значення вхідних в неї простих висловлень, отже, її можна розглядати як функцію цих висловлювань. Такі функції, які як і їх змінні приймають значення "0" або "1", називають функціями алгебри логіки або логічними функціями. Ці функції позначаються f (x 1 ... x n ).
Логічна змінна може приймати два значення, тоді з n-змінних можна скласти N = 2 n комбінацій з "0" і "1", які прийнято називати наборами змінних, і кажуть, що функція f визначена на безлічі наборів. Посколько функція приймає два значення, то на N наборів можна побудувати M = m N різних функцій.
Приклад. Якщо n = 1, то наборів N = 2, а функцій M = 4
n = 2 N = 4 M = 16
n = 4 N = 8 M = 256
Елементарні функції - логічні функції однієї або двох змінних.
Постороім при n = 1 функцію f (x).
X
f 1
f 2
f 3
f 4
0
0
1
0
1
1
0
1
1
0
Тут f 1 (x) = 0 - Константа "0";
f 2 (x) = 1 - константа "1";
f 3 (x) = x - функція x
f 5 (x) = Г?x - заперечення.
Аналогічно, при n = 2 отримуємо:
f 5 (x, y) = xГ€y
f 6 (x, y) = x Г— y
f 7 (x, y) = x В® y
f 8 (x, y) = y В® x
f 10 (x, y) = Г? f 9 (x, y) = xГ…y - сума по модулю "два".
f 11 (x, y) = Г?f 10 (x, y) = x ВЅ y - Штрих Шеффера.f 9 (x, y) = x ~ yf 12 (x, y) = Г?f 5 (x, y) = x ВЇ y - стрілка Пірса.
Таким чином, при зростанні числа змінних, число рядків значно збільшується, тому частіше використовують завдання у вигляді логічної функції - такий запис називається аналітичною.
Розкладання функцій по змінним. Досконала діз'юнктівная нормальна форма.
Введемо позначення x 0 = Г?x, x 1 = x. Нехай а - параметр, рівний 0 або 1. Тоді x A = 1, якщо x = а, і x A = 0, якщо х В№ а.
Теорема. Всяка логічна функція f (x 1 , ..., x n ) мо-жет бути представлена ​​в наступному вигляді:
де n Ві m, а диз'юнкція береться по всіх 2 m наборам значень змінних х 1 , ..., х m .
Це рівність називається розкладанням по змінним х 1 , ..., х т . Наприклад, при n = 4, m = 2 розкладання має вигляд:
f (x 1 , x 2 , x 3 , x 4 ) = Г?x 1 Г?x 2 f (0, 0, x 3 , x 4 ) Г€ Г?x 1 x 2 f & (0,1, x 3 , x 4 ) Г€ x 1 Г?x 2 f (1,0, x 3 , x < sub> 4 ) Г€ x 1 x 2 f (1,1, x 3 , x 4 )
Теорема доводиться підстановкою в обидві частини рівності довільного набору всіх п змінних.
При m = 1 з одержуємо розкладання функції по однієї змінної
Ясно, що аналогічне розкладання справедливо для будь-якої з п змінних. Інший важливий випадок - розкладання по всьому п змінним (т = п). При цьому всі змінні в правій частині (3.4) отримують фіксовані значення та функції в кон'юнкції правій частині стають рівними 0 або 1, що дає:
де диз'юнкція береться за всіх наборів на яких f = 1. Таке розкладання називається досконалої диз'юнктивної нормальною формою (СДНФ) функції f. СДНФ функції f містить рівно стільки кон'юнкція, скільки одиниць у таблиці f; кожному одиничному набору відповідає кон'юнкція всіх змінних, в якій Xi взято з запереченням, якщо s i = 0, і без заперечення, якщо s i = l. Таким чином, існує взаємно однозначна відповідність між таблицею функції f (x 1 , ..., х п ) і її СДНФ, і, отже, СДНФ для всякої логічної функції єдина (точніше, єдина з точністю до порядку букв і кон'юнкція: це означає, що зважаючи комутативності диз'юнкції і кон'юнкції формули, одержувані з попередньої формули перестановкою кон'юнкція і букв в кон'юнкції, не розрізняються і вважаються однією і тією ж СДНФ). Єдина функція, яка не має СДНФ - це константа 0.
Формули, що містять, крім змінних (і, зрозуміло, дужок), тільки знаки функцій диз'юнкції, кон'юнкції і заперечення, будемо називати булевими формулами (нагадаємо, що знак кон'юнкції, як правило, опускається). Попередня формула призводить до важливої теоремі.
Теорема. Всяка логічна функція може бути представлена ​​булевої формулою, тобто як суперпозиція кон'юнкції, диз'юнкції і заперечення.
Дійсно, для всякої функції, крім константи 0, таким поданням може служити її СДНФ. Константу 0 можна представити булевої формулою Г? xx.
А чому ж формула називається "досконалої"? Досконалої називається тому, що вона має 4 властивості досконалості.
1. У формулі всі кон'юнкції різні.
2. У кон'юнкції всі змінні різні.
3. В одній кон'юнкції не зустрічаються змінні разом з їх запереченням.
4. У кон'юнкції стільки змінних, скільки в вихідної функції f, тобто n. (Число змінних у функції є ранг цієї функції).
У таблиці істинності визначають одиничні набори. З змінних утворюють кон'юнкції наступним чином: якщо змінна = 1, то пишемо x, якщо В№ 1, то пишемо Г? x. Отримані кон'юнкції об'єднуємо знаком диз'юнкції.
x
y
Z
f
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
Г? xyz
1
0
0
|
