Материал из eSyr's wiki.

Предыдущая лекция | Следующая лекция

[править] Единичный n-мерный куб. Функция алгебры логики (ФАЛ). Дизъюнктивная нормальная форма (ДНФ), Конъюктивная нормальная форма (КНФ), связанные с ними представления и разложения

Пусть есть конечное множество A. Чаще всего мы будем рассматривать декартово произведение или декартову степень данного множества a(1 + e² / 2)

[править] Примеры граней и способов их задания (записи)

N = B3;31 = Г(2,2,1) – грань размерности 2 N1 = B3;1,31,0 = Г(1,2,0) – грань размерности 1 N2 = B3;2,31,0 = Г(2,1,0) N‘ = B3;1,2,30,0,0 = Г(0,0,0) //нарисовать картинки с кубиками

С этими гранями связано понятие КНФ и ДНФ.

Что такое функция алгебры логики, как мы их будем задавать. Рассмотрим представления и разложения других функций.

Функцция от н переменных -отображение единичного n-мерного куба в одномерный куб: ФАЛ f(x1...xn): Bn -f-> B Чаще всего будем задавать ФАЛ таблицей (линейной таблицей T(f)): x1 ... xn f 0

0 alpha0 0

1 alpha1

1

1 alpha2n-1 alphaf = (alpha0 ... alpha2n-1) – столбец значений ФАЛ Прямоугольная таблица:

xk+1 0 1

1

0 0

1

x1

xn / xk 0 0

1 0

0 alpha0

alpha2n-k-1

1

1

alpha2n-1 P2(n) – все ФАЛ от н переменных |P2(n)| = 2^2^n Все функции от 1 переменной: x1 x1 ~x1 0 1 0 0 1 0 1 1 1 0 0 1 Функции от 2 переменных: x1 x2 & v + ~ -> | | V 0 0 0 0 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 1 1 0 1 1 0 0 Существенно зависят от 2 переменных 10 функций.

//приведена функция голосования - H

Другие варианты табличного задания: характеристическое множество. Обозн множество всех тех наборов, на которых функция равна единице (либо его дополнение – множество тех наборов, на которых функция равна 0) Nf = {alpha in Bn: f(alpha)=1} NH = {(011), (101), (110), (111)}

delta in Bn xidelta(xi1 ... xin) – характеристическая функция множества наборов delta Nxi(delta) = delta

Чаще функции будем задавать формулами.

Из функций конъюнкции, отрицания, дизъюнкции и других можно строить формулы. Причём эти функции обладают алгебраическими свойствами: коммутативность, ассоциативность, дистрибутивность.

о – коммутативная операция тогда и только тогда, когда х1 о х2 = х2 о х1, о in {&, v, +, ~} ассоциативность: (x1 o x2) o x3 = x1 o (x2 o x3), o in {&, v, +, ~} дистрибутивность: о []: x1 o (x2 [] x3) = (x1 o x2) [] (x1 o x3) – операция о дистрибутивна по отношению к операции [] это верно для (&, v), (v, &), (&, +)

Сила операций: отрицание, конъюнкция, остальные.

Тождества приведения подобных: отождествление двух переменных либо подстановка весто них константы: x & x = x v x = x & 1 = x v 0 = x x & ~x = x & 0 = 0 x v 1= x v ~x = 1 x +1 = ~x x + ~x = 1

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

x, ~x – буква x0 = ~x, x1 = x

Элементарная конъюнкция (ЭК): конъюнкция букв различных булдевских переменных, K = xσ1i1…xσrir 1 <= i1 < i2 < … ir <= n

Элементарная дизъюнкция I = xσ1i1 v … v xσrir

xσ = 1 <=> x = σ xσ = 0 <=> x = ~σ

Nk = Bn;i1…irσ1…σr ~NI = Bn;i1…ir~σ1…~σr

Дизьюнкция ЭК – ДНФ, Конъюнкция ЭД – КНФ K1 v ... v Kt – ДНФ I1 & ... & Is – КНФ

Совершенная ДНФ <=> ранг каждой (любой) конъюнкции Ki = n. Совершенная КНФ <=> ранг каждой (любой) дизъюнкции Ij = n.

Представление функции – представление в виде объединённых точек.

f(x1...xn) = V σ=&sigma1...σn in Nt xσ11 ... xσnn - совершенная ДНФ f(x1...xn) = & σ=&sigma1...σn in Nt x~σ11 v ... v x~σnn - совершенная КНФ

Разложение функции по части переменных: берём только часть переменных, и по этим переменных разлагаем функцию. f(x1...xq, xq+1 ... xn) = V σ‘ = (σ1 ... σq) xσ11 ... xσqq f(σ‘, x‘‘)

     x‘             x‘‘

Что такое совершенная ДНФ: x1 x2 x3 g 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 Совершенная ДНФ: ~x1~x2x3 v ~x1x2~x3 v ~x1x2x2 v x1~x2~x3 V x1~x2x3 v x1x2~x3 – объект 6 граней размерности 0 Совершенная КНФ: (x1 v x2 v x3)(~x1 v ~x2 v ~x3)

Сокращённая ДНФ и способы её построения

Ng = N1 объединение N2 объединение N3 g = K1 v K2 v K3

K1 = x1~x3 NK1 = N1 K3 = ~x1x2 NK3 = N3 K5 = ~x2x3 NK5 = N5

g = x1~x3 v ~x1x2 v ~x2x3

f = a = K1 v ... v Kt Nf = NK1 объединение NK2 ... объединение NKt f = d = I1 & ... & Is ~Nf = ~NI1 объединение ... объединение ~Nis

K‘ : NK‘ >= Nk <+< K‘ получается из K удалением буква Nk <= Nf Nk – максимальная грань, если любое её расширение выводит за Nf Сокр ДНФ f <=> Тл1 ююю Тле – все максимальные грани ФАЛ f

Nk <= Nf – К-импликанта f

(k -> f) == 1 K <= f

Nk - максимальная грань, тогда K – простая импликанта f

У функции g 6 граней N1..N6, которые являются максимальными, и 6 простых импликантов a = K1 v K2 v K3 v K4 v K5 v K6

   x1~x3 x2~x3 ~x1x2 ~x1x3  ~x2x3  x1~x2

Геометрия помогает при небольшом количестве переменных. Нужно иметь надёжный аппарат для построения сокращённых ДНФ.

Сов КНФ g = (~x1 v ~x2 v ~x3)(x1 v x2 v x3) = ~x1x2 v `x1x3 v x1~x2 v ~x2x3 v x1~x3 v x2~x3 x1~x1 = 0 0 v x1 = x1

a = K1 v .... v Kt – нетривиальная ДНФ <=> любой 1 <= i != j <=t Kki не принадлежит Nkj

Утверждение 2.1. Пусть a‘ - сокращённая ДНФ f‘, a‘‘ - сокращённая ДНФ f‘‘ и пусть неприводимая ДНФ a получается в результате раскрытия скобок и приведения подобных в a‘a‘‘ => a – сокр ДНФ f=f‘f‘‘

Следствие. b = I1 & ... & Is – КНФ ФАЛ f и a – неприводимая ДНФ, полученная из b в результате раскрытия скобок и приведения подобных => a – сокращенная ДНФ

Доказательство. Тождества приведения подобных: x&~x = x&0 = 0, x v 0 = x x1 v x1x2 = x1 – тождество поглощения

K <= K‘ <=> K = K‘K‘‘ K v K‘ = K‘ v K‘K‘‘ = K‘‘

1. Достаточно доказать, что все простые импликанты f получатся при раскрытии скобок в нашем произведении a‘a‘‘.=> a – сокращённая ДНФ 2. Пусть K – простая импликанта f=f‘f‘‘ => K – импликанта f‘, f‘‘. => существет простая импликанта K‘ ФАЛ f‘, существет простая импликанта K‘‘ ФАЛ f‘‘ | K‘ >=K, K‘‘ >= K a‘ = K‘ v ... = f‘ a‘‘ = K‘‘ v ... = f‘‘

       K‘K‘‘ v ... = K v ... = f

раз K‘ больше K, то чтобы перейти от K к K‘, нужно вычеркнуть какие-нибудь буквы в коньюнкции K.

Если K‘K‘‘ = 1, то K‘K‘‘ v... = f = 1 => K‘K‘‘ - импликанта f, состоит из тех же букв, что и K, а это простая импликация. Отсюда K = K‘K‘‘ так как если бы какая-то буква K не содержалась бы в K‘K‘‘, то K не была бы простой импликантой. ч. т. д.

tП: x1 v x1x2 = x1 tOE: ~x11x2 v x1x3 = ~x1x2 v x1x3 v x2x3 ~x1K2 v xK3 = ~x1K2 v x1K3 v K2K3

a |=tOE=>> a‘ - строгое расширение ДНФ a тогда и только тогда, когда в ДНФ a‘ есть ЭК, которые не содержатся ни в одной из элементарных конъюнкций a, то есть нельзя получить из ДНФ a‘ a только поглощениями.

Утверждение 2.2. ДНФ a сокращённая тогда и только тогда, когда она неприводимая и не имеет строгих расширений.

Следствие. a‘ - ДНФ f и a – неприводимая ДНФ, которая получается из a‘ всевозможными расширениями и последующим приведением подобных. Тогда a – сокращённая ДНФ.

Доказательство. Любую простую импликанту можно получить из любой ДНФ путём расширения. Если мы получим все простые импликанты таким способом, тогда все непростые импликанты поглотим. 1. Достаточно доказать, чот любая неприводимая ДНФ a, не имеющая строгих расширений, действительно является строгой ДНФ. a содержит все простые импликанты. Пусть a (x1...xn) реализует f, пусть K – простая импликанта f, которая не вошла в a. K – множество тех ЭК от x1...xn, ЭК является импликантой f, но не является импликантой ни одной элементарной конъюнкцией из ДНФ a. // нет ЭК ранга n

K принадлежит K => K != пустое

k – ЭК из K, имеющая максимальный ранг. rank(k) < n

=> существует переменная xi, которая не входит в k

k&~xi не принадлежит К => K‘ принадлежит a : K‘ >= ~xi&k и K‘ !>= k => K‘=~xi&k‘ и k‘>=k k&xi не принадлежит К => K‘‘ принадлежит a : K‘‘ >= xi&k и K‘‘ !>= k => K‘=~xi&k‘‘ и k‘‘>=k применяя tOE получим, K‘ v K‘‘ v k‘k‘‘ >= k – должна входить в K ?!

|=tП=>> a‘‘ - неприводимая ДНФ a != a‘‘