Дипломная работа: Представление логических функций от большого числа переменных
Содержание
Введение. Функции алгебры логики.
Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма.
Выводы по первым двум темам. СКНФ.
Разрешимoсть задач в классической теории алгоритмов.
Трудоемкость алгоритмов.
Память и время как количественная характеристика алгоритма. (применительно к машине Тьюринга и современным ЭВМ).
Трудоемкость алгоритма на примере RSA, квантовые компьютеры.
Вывод.
Введение. Функции алгебры логики
Любая формула алгебры логики зависит от переменных высказываний x1 , x2 ... xn , полностью определяющих значение входящих в неё простых высказываний, следовательно, её можно рассматривать как функцию этих высказываний. Такие функции, которые как и их переменные принимают значение “0” или “1”, называют функциями алгебры логики или логическими функциями. Эти функции обозначаются f(x1 ... xn ).
Логическая переменная может принимать два значения, тогда из n-переменных можно составить N= 2n комбинаций из “0” и “1”, которые принято называть наборами переменных, и говорят, что функция f определена на множестве наборов. Посколько функция принимает два значения, то на N наборов можно построить M= mN различных функций.
Пример. Если n=1, то наборов N=2, а функций M=4
n=2 N=4 M=16
n=4 N=8 M=256
Элементарные функции - логические функции одной или двух переменных.
Постороим при n=1 функцию f(x).
| X | f1 | f2 | f3 | f4 |
| 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
Здесь f1 (x)=0 – константа “0”;
f2 (x)= 1 – константа “1”;
f3 (x)= x – функция x
f5 (x)= Øx – отрицание.
Аналогично, при n=2 получаем:
f5 (x,y)=xÈy
f6 (x,y)=x×y
f7 (x,y)=x®y
f8 (x,y)=y®x
f10 (x,y)= Ø f9 (x,y)=xÅy – сумма по модулю “два”.
f11 (x,y)=Øf10 (x,y)=x½y – Штрих Шеффера.f9 (x,y)=x~yf12 (x,y)=Øf5 (x,y)=x¯y – стрелка Пирса.
Таким образом, при возрастании числа переменных, число строк значительно увеличивается, поэтому чаще используют задание в виде логической функции – такая запись называется аналитической.
Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма.
--> ЧИТАТЬ ПОЛНОСТЬЮ <--