ОК_Часть_1_2015 (С.А. Ложкин - Лекции по основам кибернетики (2015)), страница 3
Описание файла
Файл "ОК_Часть_1_2015" внутри архива находится в папке "С.А. Ложкин - Лекции по основам кибернетики (2015)". PDF-файл из архива "С.А. Ложкин - Лекции по основам кибернетики (2015)", который расположен в категории "". Всё это находится в предмете "основы кибернетики" из 6 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 3 страницы из PDF
В частности, грань размерности 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 ∨ . . . ∨ K6 ,(2.10)§3. Сокращенная ДНФ и способы ее построения23где N g = {(000) , (111)} иK1 = x1 x3 ,K 2 = x2 x3 ,K 3 = x1 x2 ,K4 = x1 x3 ,K 5 = x2 x3 ,K 6 = x1 x2 ,соответствует покрытию Ng = N1 ∪ .
. . ∪ N6 , где Ni = NKiпри всех i = 1, . . . , 6 (см. рис. 2.1a). Заметим, что совершенные ДНФ и КНФ ФАЛ f из (2.4) задают покрытие множеств Nf и N f соответственно гранями размерности 0. Принимая во внимание указанную выше геометрическую интерпретацию, мы не будем в дальнейшем делать существенныхразличий между ЭК Ki и соответствующей ей гранью NKi ,а также между ДНФ вида (2.6) и соответствующим ей покрытием (2.7).Лемма 2.1. Совершенная ДНФ ФАЛ f , f ∈ P2 (n), является единственной ДНФ от БП X (n), которая реализуетэту ФАЛ, тогда и только тогда, когда во множестве Nfнет соседних наборов.Доказательство. Совершенная ДНФ ФАЛ f является единственной ДНФ от БП X (n), которая реализует эту ФАЛ,тогда и только тогда, когда в множестве Nf нет граней размерности больше 0, что эквивалентно тому, что в множествеNf нет соседних наборов.Следствие.
Совершенные ДНФ ФАЛ `n , `n являются единственными ДНФ этих ФАЛ от БП X (n).§3Сокращенная ДНФ и способы ее построенияРассмотрим теперь некоторые специальные виды ДНФ иих «геометрическую» интерпретацию. Будем говорить, чтоФАЛ f 0 имплицирует ФАЛ f 00 , или, иначе, ФАЛ f 00 поглощает ФАЛ f 0 , если Nf 0 ⊆ Nf 00 , то есть импликация24Глава 1. Дизъюнктивные нормальные формы(f 0 → f 00 ) тождественно равна 1. Элементарная конъюнкция, которая имплицирует ФАЛ f , называется импликантой этой ФАЛ.
Заметим, что отношение имплицируемостиявляется отношением частичного порядка и что f 0 имплицирует f 00 тогда и только тогда, когда f 00 = f 0 ∨ f 00 илиf 0 = f 0 · f 00 . Отсюда следует, в частности, что ЭК K 0 имплицирует ЭК K 00 тогда и только тогда, когда множество буквK 00 содержится во множестве букв K 0 , то есть K 0 = K 00 · Kдля некоторой ЭК K, не имеющей общих букв с ЭК K 00 . Этоозначает, что в данном случае ЭК K 0 может быть «устранена» из ДНФ K 00 ∨ K 0 с помощью тождества поглощения(2.3).Дизъюнктивную нормальную форму A вида (2.6) будемназывать ДНФ без поглощений ЭК, если ни одна из гранейNK1 , .
. . , NKs не содержится ни в одной из других гранейпокрытия (2.8). На «языке имплицируемости» это означает,что ни одна из ЭК Ki , i ∈ [1, s], не является импликантойЭК Kj , где j ∈ [1, s] и i 6= j. Заметим, что с помощью тождества поглощения (2.3) из любой ДНФ A можно получитьb без поглощений ЭК.ДНФ A.Импликанта K ФАЛ f называется простой импликантой этой ФАЛ, если она не поглощается никакой другойотличной от нее импликантой ФАЛ f . Из определений и отмеченных выше фактов следует, что в простую импликантуФАЛ f не входят буквы несущественных БП этой ФАЛ и чтоиз любой импликанты ФАЛ f можно получить ее простуюимпликанту удалением некоторых букв. Последнее означает, что любая импликанта ФАЛ f имплицирует некоторуюпростую импликанту f . С «геометрической» точки зренияпростые импликанты ФАЛ f соответствуют максимальнымпо включению граням множества Nf .Дизъюнкция всех простых импликант ФАЛ f называется ее сокращенной ДНФ.