OK_metodichka_part_1 (1132796), страница 6
Текст из файла (страница 6)
Поскольку грани, не входящие в S1 (NK , f ), не имеют общихточек с NK , грань NK является ядровой тогда и только тогда, когда она не покрывается всеми остальными гранямииз S1 (NK , f ). Из теоремы 4.1 следует, что ЭК K не входит в ДНФ ΣT ФАЛ f тогда и только тогда, когда для любой точки α из NK найдется точка β, β ∈ Nf , для которойΠβ (f ) ⊂ Πα (f ). Заметим, что все грани пучка Πα (f ) входятв S1 (NK , f ), а все грани пучка Πβ (f ), если Πα (f )∩Πβ (f ) 6=∅, — в S2 (NK , f ). Следовательно, проверку грани NK на регулярность можно осуществить на основе анализа ее окрестности порядка 2. Легко показать, что рассмотрение окрестности порядка 2 достаточно для проверки грани NK на еевхождение в ДНФ Квайна ФАЛ f .
Если же все ядровые грани ФАЛ f выделены и «помечены» (для этого, как уже говорилось, достаточно рассмотреть их окрестности порядка1), то невхождение ЭК K в ДНФ Квайна ФАЛ f равносильно покрытию грани NK отличными от нее «помеченными»гранями из окрестности S1 (NK , f ). Функция f (x1 , . . .
, xn )называется цепной (циклической) функцией длины t, если еесокращенная ДНФ с «геометрической» точки зрения представляет собой цепь (соответственно цикл) из t последовательно соединенных ребер N1 , N2 , . . . , Nt куба B n (см. рис.4.2a и 4.2b). Заметим, что циклическая ФАЛ длины t существует тогда и только тогда, когда t > 6 — четное число, ацепная ФАЛ длины t — при любом t > 1. Пример цепнойФАЛ длины 3 дает ФАЛ g 00 , показанная на рис. 4.1, а ФАЛg (см. рис. 2.1a) является циклической ФАЛ длины 6.Из теоремы 4.1 следует, в частности, что для любой цеп-38Глава 1.
Дизъюнктивные нормальные формыN1α` 2N1N2α1 `` α3α` 2N2α1 `` α3Ntαt+1 `Nta)`αt `Nt−1`b)Рис. 4.2: множество Nf для цепной и циклической ФАЛ fной ФАЛ длины не меньше 4 и любой циклической ФАЛДНФ ΣT совпадает с сокращенной ДНФ. При этом цепнаяФАЛ f нечетной длины t = 2k − 1 > 3 имеет единственнуюминимальную ДНФ, которая совпадает с ее ДНФ ΣM и соответствует покрытию (см. рис.
4.2a) N1 ∪N3 ∪. . .∪Nt длиныk. Действительно, множество Nf в данном случае состоит из2k наборов и не может быть покрыто (k − 1) ребром. Кроме того, покрытие множества Nf , состоящее из k ребер, неможет включать в себя ребра с общими вершинами и должно содержать ядровые ребра N1 и Nt ФАЛ f . Легко видеть,что только покрытие N1 ∪ N3 ∪ . . .
∪ Nt обладает всеми этими свойствами. Таким образом, для цепной ФАЛ нечетнойдлины t, t > 5, ДНФ ΣT не совпадает с ДНФ ΣM .Теорема 4.2 (ср. [6, 22, 10]). При любом n ∈ N, n > 3, вP2 (n) существуют ФАЛ f 0 и f 00 , имеющие общую простуюимпликанту K, которая входит в ДНФ ΣM одной, но невходит в ДНФ ΣM другой из этих ФАЛ и для которойSn−3 (NK , f 0 ) = Sn−3 (NK , f 00 ).Доказательство. Достаточно построить в P2 (n) цепную функцию f четной длины t = 2k > 2n − 2 > 4. Действительно,§4. Тупиковые и минимальные ДНФNn−1αn `= e1αn−1`α2Nn`αn+1`N139```α1α2n−2N2n−2α2n−1`e0Рис.
4.3: цепная ФАЛ длины (2n − 2) в кубе B nесли указанная ФАЛ f найдена, а ее множество Nf соответствует рис. 4.2a, то, полагаяNf 0 = Nf \ {α1 }и Nf 00 = Nf \ {αt+1 } ,получим цепные ФАЛ f 0 и f 00 нечетной длины 2k − 1 такие,что каждое ребро Ni , где i = 2, . . . , t−1, входит в ДНФ ΣMодной из них, но не входит в ДНФ ΣM другой. При этом,очевидно, Sk−2 (Nk , f 0 ) = Sk−2 (Nk , f 00 ) и, следовательно, искомая ЭК K соответствует ребру Nk .Для завершения доказательства возьмем в качестве fцепную ФАЛ длины (2n − 2), у которой множество Nf состоит из всех наборов αi = (1, .
. . , 1, 0, . . . , 0), где i ∈ [1, n],| {z } | {z }in−iи наборов αn+i = αi , i ∈ [1, n), а ребро с номером j, j ∈[1, 2n − 2], имеет вид Nj = {αj , αj+1 } (см. рис. 4.3) и приме-40Глава 1. Дизъюнктивные нормальные формыним к ней описанные выше построения.Теорема доказана.Замечание 1. Из теоремы следует, что критерий вхождения ЭК в ДНФ ΣM не имеет такого локального характера,как критерий вхождения ЭК в ДНФ ΣT (сравните с теоремой 4.1).Замечание 2. Известно [7], что при n > 14 в P2 (n) имеетсяцепная ФАЛ четной длины t, t > 2n−11 − 4, на основе которой справедливость теоремыможно установить для окрестности порядка 2t − 2 (см.
доказательство).§5Особенности ДНФ монотонных функций. Функция покрытия, таблица Квайна и построениевсех тупиковых ДНФРассмотрим класс монотонных ФАЛ и некоторые связанные с ним другие классы функций. Напомним, что ФАЛf (x1 , . . . , xn ) называется монотонной, если f (α) 6 f (β) длялюбых наборов α и β куба B n таких, что α 6 β. Будем говорить, что ФАЛ f (x1 , .
. . , xn ) монотонно зависит от БП xi ,или, иначе, БП xi является монотонной БП ФАЛ f , еслинеравенство f (α) 6 f (β) выполняется для любых соседнихпо БП xi наборов α и β куба B n таких, что α 6 β. Легко видеть, что монотонная ФАЛ монотонно зависит от всех своихБП и обратно.Докажем, что если ФАЛ f (x1 , . . . , xn ) монотонно зависит от БП xi , то ни одна из ее простых импликант не может содержать букву xi . Действительно, пусть импликантаK 0 ФАЛ f содержит букву xi и, следовательно, для граниNK 0 = Γγ 0 , где γ 0 ∈ ([0, 2])n и γ 0 hii = 0, имеет место включение NK 0 ⊆ Nf . Тогда, в силу монотонной зависимости ФАЛ§5.
Построение всех тупиковых ДНФ41f от БП xi , имеют место включенияNK 00 = Γγ 00 ⊆ Nfи NK = Γγ = NK 0 ∪ NK 00 ⊆ Nf ,где набор γ 00 (набор γ) получается из набора γ 0 заменой 0 в iом разряде на 1 (соответственно 2). Последнее из этих включений означает, что ЭК не является простой импликантойФАЛ f , то есть простая импликанта монотонной по БП xiФАЛ не может содержать буквы xi .
Отсюда следует, что любая простая импликанта отличной от 0 монотонной ФАЛ является монотонной ЭК, то есть не содержит отрицаний БП.Частным случаем монотонной зависимости ФАЛ f отБП xi является конъюнктивная (дизъюнктивная) зависимость f от xi , когда f = xi · g (соответственно f = xi ∨ g),где ФАЛ g получается из f подстановкой константы 1 (соответственно 0) вместо БП xi . При этом в случае конъюнктивной зависимости буква xi входит в любую импликантуФАЛ f , а в случае дизъюнктивной зависимости буква xiне входит ни в одну простую импликанту ФАЛ f отличнуюот xi .
Будем говорить, что ФАЛ f (x1 , . . . , xn ) инмонотонно(инконъюнктивно, индизъюнктивно) зависит от БП xi , еслиФАЛ f (x1 , . . . , xi−1 , xi , xi+1 , . . . , xn ) зависит от xi монотонно(соответственно конъюнктивно, дизъюнктивно). Очевидно,что все особенности ДНФ, характерные для ФАЛ с той илииной монотонной зависимостью от БП распространяются наФАЛ с аналогичной инмонотонной зависимостью после инвертирования соответствующих БП.Сопоставим каждому набору β из B n , монотонную ЭК+Kβ от БП X (n), состоящую из тех и только тех букв xj ,j ∈ [1, n], для которых β hji = 1, и заметим, что каждая монотонная ЭК от БП X (n) может быть представлена в указанном виде. Легко видеть также, что грань, соответствующая ЭК Kβ+ , где β = (β1 , .
. . , βn ) ∈ B n , имеет вид Γγ , гдеγ = (2 − β1 , . . . , 2 − βn ). Набор α, α ∈ B n , называется нижней единицей монотонной ФАЛ f , f ∈ P2 (n), если α ∈ Nf42Глава 1. Дизъюнктивные нормальные формыи f (β) = 0 для любого отличного от α набора β такого, чтоβ 6 α. Множество всех нижних единиц монотонной ФАЛ fбудем обозначать через Nf+ .В силу введенных определений, Kβ+ (α) = 1 тогда и только тогда, когда α > β, откуда следует, что набор β являетсяединственной нижней единицей ЭК Kβ+ и что ЭК Kβ+0 имплицирует ЭК Kβ+00 тогда и только тогда, когда β 0 > β 00 .Отсюда вытекает также, что ЭК Kβ+ является простой импликантой монотонной ФАЛ f тогда и только тогда, когдаβ ∈ Nf+ , и что набор β является при этом ядровой точкойФАЛ f .
Таким образом, доказано следующее утверждение.Лемма 5.1. Сокращенная ДНФ A монотонной ФАЛ f , f ∈ P2 (n),является единственной тупиковой ДНФ этой ФАЛ и имеет вид:_A (x1 , . . . , xn ) =Kβ+ (x1 , . . . , xn ) .β∈Nf+При этом все наборы из Nf+ являются ядровыми точкамиФАЛ f .Следствие. Монотонная ФАЛ является ядровой ФАЛ.Напомним, что с «геометрической» точки зрения, сокращенная ДНФ ФАЛ f из P2 (n) представляет собой покрытиемножества Nf всеми максимальными гранями, а тупиковаяДНФ соответствует тупиковому подпокрытию, выделяемому из этого покрытия.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
