Представление логических функций от большого числа переменных (стр. 1 из 3)
Содержание
Введение. Функции алгебры логики.
Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма.
Выводы по первым двум темам. СКНФ.
Разрешим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 – стрелка Пирса.
Таким образом, при возрастании числа переменных, число строк значительно увеличивается, поэтому чаще используют задание в виде логической функции – такая запись называется аналитической.
Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма.
Введем обозначение 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. Полученные конъюнкции объединяем знаком дизъюнкции.
| x | y | Z | f | |
| 0 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 0 | |
| 0 | 1 | 0 | 0 | |
| 0 | 1 | 1 | 1 | Ø xyz |
| 1 | 0 | 0 | 0 | |
| 1 | 0 | 1 | 1 | x Ø yz |
| 1 | 1 | 0 | 1 | xy Ø z |
| 1 | 1 | 1 | 1 | xyz |
В результате получаем следующую СДНФ:
f(x, y, z) = (Ø xyz) È (x Ø yz) È (xy Ø z) È (xyz)
Выводы по первым двум темам.
Логическая переменная может принимать два значения, тогда из n-переменных можно составить N= 2n комбинаций из “0” и “1”, которые принято называть наборами переменных, и говорят, что функция f определена на множестве наборов. Поскольку функция принимает два значения, то на N наборов можно построить M= mNразличных функций. Становится очевидно, что чем больше переменных содержит функция, тем более громоздкой становится таблица истинности. Поэтому чаще используют аналитическую форму записи. Но машинам (тем же ЭВМ) непонятна такая форма записи и всё равно необходимо строить таблицы истинности, что порою может отнимать значительно времени. Об этом речь пойдет чуть ниже.
Так же бывает проблематично, а порою даже и невозможно построить СДНФ не использую таблицы истинности.
Так же существует СКНФ – Совершенная Конъюнктивная Нормальная Формула. Я не стал останавливаться на ней более подробно, так как она очень похожа на СДНФ, с той лишь разницей, что состоит из конъюнктивных элементов дизъюнкции. Соответствующие изменения будут и при получении СКНФ из таблицы истинности.
| x | Y | Z | f | |
| 0 | 0 | 0 | 0 | хÈyÈz |
| 0 | 0 | 1 | 0 | xÈyÈØz |
| 0 | 1 | 0 | 0 | xÈØyÈz |
| 0 | 1 | 1 | 1 | |
| 1 | 0 | 0 | 0 | ØxÈ yÈ z |
| 1 | 0 | 1 | 1 | |
| 1 | 1 | 0 | 1 | |
| 1 | 1 | 1 | 1 |
Таким образом получаем следующую СКНФ:
f(x,y,z)=(хÈyÈz)^(xÈyÈØz)^(xÈØyÈz)^(ØxÈyÈz)
Разрешимoсть задач в классической теории алгоритмов
В классической теории алгоритмов задача считается разрешимой, если существует решающий ее алгоритм. Однако для реализации некоторых алгоритмов при любых разумных с точки зрения физики предположениях о скорости выполнения элементарных шагов может потребоваться больше времени, чем по современным воззрениям существует вселенная. Поэтому возникает потребность конкретизировать понятие разрешимости и придать ему оценочный, количественный характер, введя такие характеристики алгоритмов, которые позволяли бы судить о возможности и целесообразности их практического применения.
Среди различных возможных характеристик алгоритмов наиболее важными с прикладной точки зрения являются две: время и память, расходуемые при вычислении. Физическое время вычисления алгоритма характеризуется произведением tt, где t - число действий (шагов) вычисления, а t - среднее физическое время реализации одного шага. Число шагов t определяется описанием алгоритма в данной алгоритмической модели, это - величина математическая, не зависящая от особенностей физической реализации модели. Напротив, t зависит от реализации и определяется скоростью обработки сигналов в элементах, записи и считывания информации и т. д. Поэтому число действий t можно считать математическим временем вычисления алгоритма, определяющим физическое время вычисления с точностью до константы t, зависящей от реализации.
Память как количественная характеристика алгоритма
Память как количественная характеристика алгоритма определяется количеством S единиц памяти (ячеек ленты машины Тьюринга или машинных слов в современных ЭВМ), используемых в процессе вычисления алгоритма. Ясно, что эта величина по порядку не может превосходить числа шагов вычисления: mt³s, где m - максимальное число единиц памяти, используемых в данной машине на одном шаге. Напротив, t может существенно превосходить s, например, возможно соотношение t ³ s^c. С этой точки зрения время более тонко отражает сложность алгоритма, чем память; и это - одна из причин, по которой исследованию временных характеристик алгоритма уделяется большее внимание. Существуют и другие, прикладные причины (в частности, то, что, грубо говоря, память дешевле времени), которые здесь обсуждаться не будут. Так или иначе, здесь будет идти речь о трудоемкости алгоритмов и задач, решаемых алгоритмами.