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

Содержание

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

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

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

Разрешимoсть задач в классической теории алгоритмов.

Трудоемкость алгоритмов.

Память и время как количественная характеристика алгоритма. (применительно к машине Тьюринга и современным ЭВМ).

Трудоемкость алгоритма на примере RSA, квантовые компьютеры.

Вывод.

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

Любая формула алгебры логики зависит от переменных высказываний x₁ , x₂ ... x_n , полностью определяющих значение входящих в неё простых высказываний, следовательно, её можно рассматривать как функцию этих высказываний. Такие функции, которые как и их переменные принимают значение “0” или “1”, называют функциями алгебры логики или логическими функциями. Эти функции обозначаются f(x₁ ... x_n ).

Логическая переменная может принимать два значения, тогда из 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

Здесь f₁ (x)=0 – константа “0”;

f₂ (x)= 1 – константа “1”;

f₃ (x)= x – функция x

f₅ (x)= Øx – отрицание.

Аналогично, при n=2 получаем:

f₅ (x,y)=xÈy

f₆ (x,y)=x×y

f₇ (x,y)=x®y

f₈ (x,y)=y®x

f₁₀ (x,y)= Ø f₉ (x,y)=xÅy – сумма по модулю “два”.

f₁₁ (x,y)=Øf₁₀ (x,y)=x½y – Штрих Шеффера.f₉ (x,y)=x~yf₁₂ (x,y)=Øf₅ (x,y)=x¯y – стрелка Пирса.

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

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

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

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

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

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

f(x₁ , x₂ , x₃ , x₄ )= Øx₁ Øx₂ f(0, 0, x₃ , x₄ ) ÈØx₁ x₂ f & (0,1,x₃ ,x₄ )È x₁ Øx₂ f(1,0,x₃ ,x₄ )È x₁ x₂ f(1,1,x₃ ,x₄ )

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

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

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

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

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

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать