оки1 (1155744), страница 3
Текст из файла (страница 3)
. , αn ) куба B n , для которых αi = γi при всех i ∈16Глава 1. Дизъюнктивные нормальные формыx1010 x1 x1 10 1 0 10 0 1 1a)x1 x20 00 11 01 1&0001∨ ⊕ ∼ → | ↓0 0 1 1 1 11 1 0 1 1 01 1 0 0 1 01 0 1 1 0 0b)αef(00)(11)(01)(10)(0001)(0111)(0110)(1001)(1101)(1110)(1000)название функции f— ”0” (константа нуль)— ”1” (константа единица)— тождественная функция— отрицание— конъюнкция (умножение)— дизъюнкция— сумма по модулю 2— эквивалентность— импликация— штрих Шеффера— стрелка Пирсаc)Рис. 2.2: P2 (1) и «основные» ФАЛ из P2 (2)§2. Представление ФАЛ с помощью ДНФ17[1, n] таких, что γi 6= 2.
Множество Γγ называется граньюкуба B n , число (n − r), равное числу ”2” в наборе γ, считается размерностью этой грани, а число r — ее рангом. Заметим, что указанная грань Γγ представляет собой подкубразмерности (n − r) куба B n и состоит из 2n−r наборов, отличающихся друг от друга только в тех разрядах, в которыхрасположены символы ”2” набора γ. В частности, грань размерности 0 представляет собой вершину куба, грань размерности 1 — его ребро, грань размерности 2 — квадрат, и такдалее. Так, на рис.
2.1 в кубе B 3 выделены ребра N1 , . . . , N6 ,а в кубе B 4 выделены грани Γ(0010) , Γ(0200) , Γ(0221) и Γ(1222)размерностей 0, 1, 2 и 3 соответственно. Легко видеть, чтогрань Γγ ранга (n − r) в кубе B n , где γ = (α, 2, . . . , 2) иα ∈ B n−r , соответствует отрезку куба длины 2r , а множество всех граней указанного вида образует разбиение B n напоследовательные отрезки.Будем, как обычно, предполагать, что у нас имеется счетный упорядоченный алфавит булевых переменных (БП) X ={x1 , x2 , . . . , xn , . . . }, и будем рассматривать функции алгебры логики (ФАЛ), или, иначе, булевы функции от переменных из X, а множество всех таких функций будем обозначать через P2 (X), или P2 . Будем предполагать также, чтокаждый рассматриваемый n-мерный куб имеет вид B n == B n (X), где множество переменных X = {xj1 , . .
. , xjn } ⊂ Xи j1 < · · · < jn , причем переменная xji для всех i ∈ [1, n] связана с i-м разрядом куба B n (X). Множество всех функцийалгебры логики f (xj1 , . . . , xjn ), отображающих куб B n (X) вB, будем обозначать через P2 (X), а его m-ю декартову степень, то есть множество систем вида F = (f1 , . . . , fm ), состоящих из m таких функций, — через P2m (X). Как правило,мы будем выделять из X множество БП X(n) = {x1 , . . . , xn },где n ∈ N, будем сопоставлять ему набор БП x(n) == (x1 , .
. . , xn ) и будем рассматривать множество ФАЛ P2 (n) =P2 (X(n)), а также его степени P2m (n) = P2m (X(n)).18Глава 1. Дизъюнктивные нормальные формыДля задания ФАЛ f из P2 (n) можно использовать ееnтаблицу значений, то есть матрицу M из множества B 2 ,n+1 ,i-я строка, i ∈ [1, 2n ], которой имеет видM hi, [1, n + 1]i = (α, f (α)) ,где ν (α) = i − 1. При этом столбец M h[1, 2n ] , n + 1i, однозначно задающий ФАЛ f , считается ее столбцом значенийи обычно записывается в виде транспонированной строки,обозначаемой через αef .
Отсюда следует, в частности, чтоn2|P2 (n)| = 2 . На рис. 2.2a (2.2b) приведены таблицы всех(соответственно «основных») ФАЛ от БП x1 (соответственно x1 , x2 ), а на рис. 2.2c перечислены столбцы значений αef иназвания для всех указанных ФАЛ. Столбец значений ФАЛf из P2 (n) при любом k ∈ [1, n) можно записать в виде прямоугольной таблицы (матрицы)длины 2k и высоты 2n−k , i-яn−kстрока которой, i ∈ 1, 2, имеет видDiE(i − 1) 2k , i2k .αefКроме того, ФАЛ f однозначно определяется своим характеристическим множеством, которое состоит из всех наборов α ∈ B n таких, что f (α) = 1, и обозначается через Nf ,а также его дополнением N f = Nf = B n \ Nf . Заметим, чтоФАЛ f является характеристической функцией множестваNf .На рис.
2.3a показана таблица значений ФАЛ трех переменных H (x1 , x2 , x3 ), которая называется функцией голосования, на рис. 2.3b приведены прямоугольные таблицы еезначений, а на рис. 2.3c выписаны наборы множеств NH иNH.Нетрудно убедиться в том, что бинарные операции &, ∨,⊕ удовлетворяют обычным «алгебраическим» тождествамассоциативности и коммутативности, а операция &, крометого, — тождествам дистрибутивности относительно ∨ и ⊕,§2. Представление ФАЛ с помощью ДНФx1 x2 x30 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1H00010111a)x1001l x3x2l0110001x2l x3x1l0110110 0 1 10 1 0 10 0 0 10 1 1 1b)NH = {(011) , (101) , (110) , (111)}N H = {(000) , (001) , (010) , (100)}c)Рис. 2.3: функция голосования1920Глава 1.
Дизъюнктивные нормальные формыс помощью которых можно раскрывать скобки1 . Заметим,также, что имеют место следующие тождества приведенияподобныхx · 0 = x · x = x ⊕ x = 0,x ∨ 1 = x ∨ x = x ⊕ x = 1, (2.1)x · x = x ∨ x = x ∨ 0 = x ⊕ 0 = x · 1 = x,(2.2)x1 ∨ x1 x2 = x1 ,(2.3)последнее из которых называется «тождеством поглощения».Напомним, что ФАЛ видаf (x1 , . .
. , xn ) = α1 x1 ⊕ · · · ⊕ αn xn ⊕ α0из P2 (n), где α0 , . . . , αn — булевы константы, называется линейной ФАЛ и заметим, что существенными БП этой ФАЛявляются те и только те БП xi из множества X (n), для которых «коэффициент» αi равен 1. Заметим также, что ФАЛ`n = x1 ⊕ · · · ⊕ xn и `n = x1 ⊕ · · · ⊕ xn ⊕ 1 являются единственными существенными линейными ФАЛ в P2 (n).Рассмотрим некоторые формулы «алгебраического» типа над множествомБ0 = {x1 · x2 , x1 ∨ x2 , x1 } .Функции xi и xi будем называть буквами БП xi и, как обычно, будем считать, что x0i = xi , x1i = xi . Конъюнкция (дизъюнкция) r, 1 6 r 6 n, букв различных БП из множества X (n) называется элементарной конъюнкцией (соответственно элементарной дизъюнкцией) ранга r от булевых переменных X (n). Из (2.1), (2.2) следует, что элементарная1При записи формул над P2 (2) будем применять обычные соглашения о «силе» операций, в соответствии с которыми ФАЛ ¬ сильнееФАЛ &, а ФАЛ & сильнее всех остальных ФАЛ от двух БП.
Кроме того, внешние скобки и скобки, задающие порядок многократного выполнения одной и той же бинарной ассоциативной операции &, ∨, ∼, ⊕,будем, как правило, опускать.§2. Представление ФАЛ с помощью ДНФ21конъюнкция (ЭК) K = xαi11 · · · xαirr и элементарная дизъюнкция (ЭД) J = xαi11 ∨ . . . ∨ xαirr , где 1 6 i1 < · · · < ir 6 n,являются характеристическими ФАЛ грани NK = Γβ и еедополнения NJ = B n \ Γβ , где набор β из ([0, 2])n обладает тем свойством, что β hip i = αp при всех p ∈ [1, r] иβ hii = 2 в остальных случаях.
Так, элементарные конъюнкции x1 x2 x3 x4 , x1 x3 x4 , x1 x4 и x1 ранга 4, 3, 2 и 1 соответственно от БП x1 , x2 , x3 , x4 являются характеристическимиФАЛ граней куба B 4 , показанных на рис. 2.1b. Будем считать, что константа 1 (константа 0) является элементарнойконъюнкцией (соответственно элементарной дизъюнкцией)ранга 0. Заметим, что любая отличная от x1 ⊕ x2 и x1 ∼ x2существенная ФАЛ от БП x1 , x2 является либо ЭК, либоЭД ранга 2.Дизъюнкция различных элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ), а конъюнкция различных элементарных дизъюнкций — конъюнктивной нормальной формой (КНФ). При этом ДНФ (КНФ)считается совершенной, если все ее ЭК (соответственно ЭД)существенно зависят от одних и тех же БП, а их ранг равен числу этих БП. Число ЭК (ЭД) в ДНФ (соответственноКНФ) A называется ее длиной и обозначается через λ (A).Любую ФАЛ f (x1 , . .
. , xn ), отличную от константы, можнопредставить в виде ее совершенных ДНФ и КНФ следующим образом:f (x1 , . . . , xn ) =_xα1 1 . . . xαnn =(α1 ,...,αn )∈Nf=^ββx1 1 ∨ . . . ∨ xnn . (2.4)(β1 ,...,βn )∈N fТак, совершенная ДНФ ФАЛ g (x1 , x2 , x3 ), для которой N g =22Глава 1. Дизъюнктивные нормальные формы{(000) , (111)}, (см. рис. 2.1a) имеет видg (x1 , x2 , x3 ) == x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 .Заметим, что любую ФАЛ f из P2 (n), отличную от константы 0, можно представить ее совершенной ДНФ вида(2.4), а ФАЛ f ≡ 0 — формулой x1 · x1 .
Следовательно, любая ФАЛ из P2 может быть реализована формулой над Б0 ,и поэтому множество Б0 является базисом P2 .Cовершенную ДНФ (2.4) обобщает следующее представление, которое называют обычно разложением Шеннона:_σq+1f x0 , x00=xq+1· · · xσnn fσ00 x0 , (2.5)σ 00 =(σq+1 ,...,σn )где q ∈ [0, n], x0 = (x1 , . . . , xq ), x00 = (xq+1 , .
. . , xn ) и fσ00 (x0 ) =f (x0 , σ 00 ). Заметим, что при q = 0 все «остаточные» ФАЛfσ00 (x0 ) являются константами.Представление ФАЛ в виде ДНФ или КНФ имеет простую геометрическую интерпретацию. Пустьf (x1 , . . . , xn ) = K1 ∨ . . . ∨ Ks = A,(2.6)f (x1 , . .
. , xn ) = J1 · · · Jt = B,(2.7)где K1 , . . . , Ks (J1 , . . . , Jt ) — различные ЭК (соответственно ЭД) от БП x1 , . . . , xn . Из (2.1), (2.2) следует, что представления (2.6) и (2.7) эквивалентны следующим покрытияммножеств Nf и N f гранями куба B nNf = NK1 ∪ . . . ∪ NKs ;(2.8)N f = N J1 ∪ . . . ∪ N Jt .(2.9)Так, представлениеg (x1 , x2 , x3 ) = K1 ∨ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
