Содержание

Введение. Функции алгебры логики.

Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма.

Выводы по первым двум темам. СКНФ.

Разрешим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).

Здесь 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~y f12(x,y)=Øf5(x,y)=x¯y – стрелка Пирса.

Таким образом, при возрастании числа переменных, число строк значительно увеличивается, поэтому чаще используют задание в виде логической функции – такая запись называется аналитической.

Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма.

Введем обозначение x0=Øx, x1=x. Пусть а - параметр, равный 0 или 1. Тогда xA=1, если x=а, и xA=0, если х¹а.

Теорема. Всякая логическая функция f(x1, ... , xn) мо-жет быть представлена в следующем виде:

где n ³ m, а дизъюнкция берется по всем 2m наборам значений переменных х1, ..., хm.

Это равенство называется разложением по переменным х1, ..., хт. Например, при n=4, m=2 разложение имеет вид:

f(x1, x2, x3, x4)= Øx1 Øx2 f(0, 0, x3, x4) È Øx1 x2 f & (0,1,x3,x4)È x1 Øx2 f(1,0,x3,x4)È x1 x2 f(1,1,x3,x4)

Теорема доказывается подстановкой в обе части равенства произвольного набора всех п переменных.

При m=1 из получаем разложение функции по одной переменной

Ясно, что аналогичное разложение справедливо для любой из п переменных. Другой важный случай — разложение по всем п переменным (т=п). При этом все переменные в правой части (3.4) получают фиксированные значения и функции в конъюнкциях правой части становятся равными 0 или 1, что дает:

где дизъюнкция берется по всем наборам  на которых f=1. Такое разложение называется совершенной дизъюнктивной нормальной формой (СДНФ) функции f. СДНФ функции f содержит ровно столько конъюнкций, сколько единиц в таблице f ; каждому единичному набору  соответствует конъюнкция всех переменных, в которой Xi взято с отрицанием, если si = 0, и без отрицания, если si = l. ............