Представление логических функций от большого числа переменных

Содержание

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

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

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

Разрешим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. Таким образом, существует взаимно од­нозначное соответствие между таблицей функции f (x1, ., хп) и ее СДНФ, и, следовательно, СДНФ для всякой логической функции единственна (точнее, единственна с точностью до порядка букв и конъюнкций: это означает, что ввиду коммутативности дизъюнкции и конъюнкции формулы, получаемые из предыдущей формулы перестановкой конъюнкций и букв в конъюнкции, не различаются и считаются одной и той же СДНФ). Единственная функция, не имеющая СДНФ – это константа 0.

Формулы, содержащие, кроме переменных (и, разумеется, скобок), только знаки функций дизъюнкции, конъюнкции и отрицания, будем называть булевыми формулами (напомним, что знак конъюнкции, как правило, опускается). Предыдущая формула приводит к важной теореме.

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

Действительно, для всякой функции, кроме константы 0, таким представлением может служить её СДНФ. Константу 0 можно представить булевой формулой Ø xx.

А почему же формула называется “совершенной”? Совершенной называется потому, что она имеет 4 свойства совершенства.

1. В формуле все конъюнкции разные.

2. В конъюнкции все переменные разные.

3. В одной конъюнкции не встречаются переменные вместе с их отрицанием.

4. В конъюнкции столько переменных, сколько в исходной функции f , то есть n. (Число переменных в функции есть ранг этой функции).

В таблице истинности определяют единичные наборы. Из переменных образуют конъюнкции следующим образом: если переменная = 1, то пишем x, если ¹ 1, то пишем Ø x. Полученные конъюнкции объединяем знаком дизъюнкции.

 Скачать реферат