Дизъюнктивные и конъюктивные нормальные формы. СДНФ и СКНФ. Теорема о представлении булевой функции в виде СДНФ и СКНФ.

Любая формула х или !х над стандартным базисом, где х – произвольная переменная, называется литералом.

Пусть ~xi – литерал. Ф-ла видa ~x1/\~x2/\…/\~xk наз-ся элементарной конъюкцией

~x1\/~x2\/…\/~xk - элементарной дизъюнкцией

(все переменные, входящие в ЭК и ЭД попарно различны)

ДНФ от переменных х1…хn называется ф-ла вида K1\/K2\/…\/Km, где Ki, i=1,m – ЭК

КНФ от переменных х1…хn называется ф-ла вида D1\/D2\/…\/Dm, где Di, i=1,m - ЭД

Если в каждую ЭК входят все переменные х1…хn или их отрицания, то такая ДНФ называется совершенной ДНФ.

Т-ма: Любая БФ, отличная от константы 0 (1) мб представлена формулой в виде СДНФ (СКНФ)

Д-во (для первого): рассм некоторую БФ f, отличную от константы 0. Сформируем м-во С1f={~L | f(~L)=1}. Каждый набор из С1f называется конституентой единицы ф-ии f. Т.к. по усл ф-я не равно 0, м-воC1f не пусто. Каждому набору поставим в соответствие ЭК: ~L э C1f ->x1^L1…xn^Ln. Эта формула обращается в единицу только на наборе ~L и равно 0 на любом наборе B, отличном от L.

Тогда искомая ф-ла им вид f=\/x1^L1…xn^Ln, L э C1f.

Базис Жегалкина и его полнота. Полином Жегалкина. Теорема о единственности

Полинома Жегалкина для каждой булевой функции

Базис Жегалкина – полное множество БФ {(+), . , 1}

Полином Жегалкина – формула вида a0+a1x1+a2x2+…+anxn+a12x1x2+…+a12…nx1…xn

Т-ма: для каждой БФ полином Жегалкина определён однозначно.

Д-во: Посчитаем кол-во коэф-тов в полиноме Жегалкина от n перем. Заметим, что каждый коэф-т ai1…in<-> {i1…in}=c{1…n} (ставится в соответствие)

ð |2^({1…n})| = 2^n {0,1}

ð Различных БФ от n перем можно задать с помощью полинома Жегалкина 2^((2^n)), что совпадает с кол-вом БФ от n переем

ð Для каждой БФ существует однозначно определённый полином Жегалкина.

Полином жегалккина над x_1….x_n называется выражение вида к₁+к₂…+к_е, е£1 и все к_iразличные монотонные коньюкции над x₁…x_n,либо конст.

Теор Жигалкина:Любую функцию алгебры логики f(x₁…x_n) можно единственным образом выразить полиномом жегалкина над x₁…x_n

До-во:1)Докажем $ полинома, система  полна,Þ" функцию алгебры логики f(x₁…x_n) можно реалиховывать формулой над

А)Пользуясь дистрибутивностью раскрываем все скобки в этой реализации и получаем ,что f(x₁…x_n) = к₁+к₂…+к_i,где к_i–коньюкция переменных и единицу.

Б)преобразуем все полученные коньюкции в элементарные,пользуясь при этом коммутативностью о соотношениями х*х=х, 1*1=1, А*1=А.Очевидно,все коньюкции станут монотонными.

В)преобразуем полученную сумму в полином жегалкина ,пользуясь при этом соотношениями А+а=А и А+0=А в результате получим либо k_i1 + k_i2 +…+ k_inлибо конст 0

2)Докажем единственность представления .Подсчитаем число различных всевозможных монотонных коньюкций от n переменных.Для этого сост табл

 вида,где каждой переменной соотв. 1,если она присутствует в монотонной коньюкции 0 в противном случае.При этом конст.1 поставим в соотв нулевой набор.Очевидно,что построенное отображение биективноÞ,всего тразличных монотонных коньюкций от n переменных 2ⁿ. Построим аналогичное биективное отображение между всевозможными суммами монотонных коньюкций и векторами длинн 2ⁿ-числа коньюкции.Для этого составим

табл вида ,где под соотв. Монотоной коньюкции стоит эдиница если она входит в данную суммму и ноль, если не входит.При этом константе 0 ставится в соотв нулевой набор.Очевидно,отображение биективно.Всего таких различных сумм будет столько сколько $ различных булевых векторов длины 2ⁿ,т.е. 2ⁿ.Мы получим,что число различных полиномов Жегалкина совпадает с числом функций алгебры логиги.Поскольку отображение из мн-ва полиномов во мн-во функций сюрьективно то оно и биективно над n переменными и функций алгебры логиги от n переменных равномощны.Единственность доказанна.