ОК_Часть_1_2015 (С.А. Ложкин - Лекции по основам кибернетики (2015)), страница 8

Для каждого набора β, β ∈B n−1 , рассмотрим случайную величину ηβ = ξ(0,β) ∨ ξ(1,β) .Заметим, что случайные величины ηβ , β ∈ B n−1 , независимы, а математическое ожидание и дисперсия любой из них3равны 34 и 16соответственно. Заметим также, что равенствоηβ = 1 выполняется тогда и только тогда, когда в ДНФ Af ,построенной по лемме 7.1 для ФАЛ f , входит слагаемое, соответствующее набору β. Из независимости случайных величин ηβ , β ∈ B n−1 , следует, что для их суммы ηe = ηe(n)выполняются соотношения3Eeη (n) = 2n−1 ,4Deη (n) =3 n−12.16Полагаяlt= n·2n2m,I=3 n−13 n−12− t, 2+t44(7.8)52Глава 1.

Дизъюнктивные нормальные формыи проводя на основе (7.8) рассуждения аналогичные тем, спомощью которых из соотношений (7.4) выводилось равен-nство (7.5), получим, что λ(Af ) ∈ I у не менее, чем 22 1 − n12ФАЛ f из P2 (n). Это означает, что для почти всех ФАЛ f ,f ∈ P2 (n), длина и ранг её ДНФ Af , построенной в соответствии с леммой 7.1, удовлетворяет (7.6), (7.7).Лемма доказана.§8Алгоритмические трудности минимизацииДНФ и оценки максимальных значений некоторых связанных с ней параметров. ТеоремаЮ. И.

Журавлева о ДНФ сумма минимальныхРешение задач минимизации ДНФ для заданной ФАЛ характеризуется различными параметрами этой ФАЛ и, впервую очередь, значениями исследуемых функционалов еесложности (см. §7). Кроме того, как отмечалось выше, рядпараметров (длина сокращенной ДНФ, число тупиковых илиминимальных ДНФ и др.) характеризуют трудоемкость задачи минимизации ДНФ для рассматриваемой ФАЛ.

В связи с этим представляет интерес поведение при n = 1, 2, . . .,максимального значения того или иного подобного параметра ψ для ФАЛ из P2 (n):ψ(n) = max ψ(f ),f ∈P2 (n)которое,как и в случае функционалов сложности, называют,обычно, функцией Шеннона для параметра ψ в классе ДНФ.Будем обозначать значение функции Шеннона для параметров, равных числу1 тупиковых ДНФ, числу минималь1Все ДНФ рассматриваются с точностью до перестановки ЭК и буквв них.§8. Минимизация ДНФ53ных ДНФ и длине сокращенной ДНФ у ФАЛ из P2 (n), черезτ (n), µ (n) и λсокр.

(n) соответственно.Из монотонности функционала ψ для сложности ДНФ(см. §7) следует, что ψ-минимальную ДНФ всегда можно выбрать среди тупиковых ДНФ, алгоритм построения которыхописан в §6. Однако, как показывает следующее утверждение, ФАЛ могут иметь очень много различных тупиковыхДНФ, и даже число различных минимальных ДНФ у нихможет быть очень велико.Лемма 8.1. Число тупиковых (минимальных) ДНФ у ФАЛf из P2 (n) , n > 4, видаf (x1 , . .

. , xn ) = g(x1 , x2 , x3 ) · (x4 ⊕ · · · ⊕ xn ),n−4где N g = {(000), (111)}, равно 52(соответственно 22n−4).Доказательство. Из свойств линейной ФАЛ и свойств ФАЛg вытекает, что (см. §1 и §4) любая простая импликанта KФАЛ f имеет видK = Ki (x1 , x2 , x3 ) · xβ4 4 · · · xβnn ,где Ki , i = 1, . . . , 6, — простая импликанта ФАЛ g (см. рис.2.2a и (2.10)) и β4 ⊕ · · · ⊕ βn = 1. Таким образом, сокращенная ДНФ ФАЛ f с «геометрической» точки зрения состоитиз 2n−4 циклов длины 6 (см. §4).

Следовательно, любая тупиковая (минимальная) ДНФ ФАЛ f включает в себя одноиз пяти (соответственно двух) реберных покрытий, связанных с тупиковыми (соответственно минимальными) ДНФФАЛ g, приведенными в (4.1)–(4.2) (соответственно (4.1)),для каждого из 2n−4 указанных циклов. Поэтому число туn−4пиковых (минимальных) ДНФ ФАЛ f равно 52(соответn−4ственно 22 ).Лемма доказана.54Глава 1. Дизъюнктивные нормальные формыСледствие.n−4τ (n) > 52n−4, µn (n) > 22.Важным параметром, влияющим на размер таблицы Квайна и, следовательно, на трудоемкость задачи минимизации,является длина сокращенной ДНФ. Установим некоторыенижние оценки длины сокращенной ДНФ у ФАЛ от n БП,показывающие, в частности, что длина сокращенной ДНФможет быть существенно больше длины совершенной ДНФтой же ФАЛ.Для I ⊆ [0, n] через sIn (x1 , . .

. , xn ) обозначим ФАЛ изP2 (n), которая является характеристической ФАЛ объединения всех слоев куба B n с номерами из I. При этом числа из I считаются рабочими числами ФАЛ sIn . Заметим, чтоФАЛ sIn является симметрической, то есть не изменяет своезначение при любой перестановке аргументов, и наоборот,любая симметрическая функция алгебры логики совпадает с одной из ФАЛ вида sIn . Заметим также, что отличнаяот константы симметрическая ФАЛ является существеннойФАЛ.

Легко видеть, что рабочими числами симметрическихФАЛ `n и `n являются все нечетные и все четные числа отрезка [0, n] соответственно.Симметрическая ФАЛ называется поясковой, если ее рабочие числа образуют отрезок. Поясковой ФАЛ является, в[2,3]частности, ФАЛ голосования H (x1 , x2 , x3 ) = s3 , а так[1,2]же ФАЛ g = s3 , показанная на рис. 2.2a. Легко видеть,[r,p]что сокращенная ДНФ поясковой ФАЛ sn (x1 , . . . , xn ), где0 6 r 6 p 6 n, состоит из всех ЭК ранга (n + r − p), которые содержат r БП и (n − p) отрицаний БП, то есть имеетвид_σn+r−ps[r,p](x1 , .

. . , xn ) =xσi11 · · · xin+r−p.(8.1)n16i1 <···<in+r−p 6nσ1 +···+σn+r−p =r§8. Минимизация ДНФ55Из (8.1)что длина сокращенной ДНФ следует, n ФАЛ snnn−pравна r · n−r , и поэтому при r = n − p = 3 она в соотnветствии с формулой Стирлинга (1.3) не меньше, чем e1 3n ,где e1 — некоторая константа. Таким образом, доказано следующее утверждение:[r,p]Лемма 8.2.λсокр. (n) > e13n,nгде e1 — некоторая константа.Рассмотренные примеры показывают, что с алгоритмической точки зрения задача минимизации ДНФ являетсяочень трудоемкой задачей. В теории сложности вычислений,где трудоемкость алгоритма определяется, обычно, числомбитовых операций, необходимых для его выполнения в «худшем» случае, выделен целый класс так называемых NPполных проблем, которые считаются алгоритмически трудными (см., например, [1, 23]).

К NP-полным проблемам относится, в частности, проблема выполнимости КНФ, которая состоит в том, чтобы по заданной КНФ выяснить, равнатождественно нулю реализуемая ею ФАЛ или нет. Таким образом, даже построение сокращенной ДНФ из КНФ (см. §3)является алгоритмически трудной задачей.С другой стороны, Ю.И. Журавлев [9, 6] предложил применительно к ДНФ модель так называемых локальных илиокрестностных алгоритмов, когда преобразование рассматриваемой грани однозначно определяется «состоянием» ее«окрестности» заданного порядка (см. §4). Он же (см. теорему 8.1) доказал, что при построении минимальной ДНФдля ФАЛ из P2 (n) , n > 3, приходится, в общем случае, рассматривать окрестности порядка (n − 3) ее максимальныхграней. Следовательно, задача минимизации ДНФ являетсятрудной и с точки зрения уровня локальности используемыхалгоритмов.56Глава 1.

Дизъюнктивные нормальные формыN1α` 2N2α1 `N1` α3α` 2N2α1 `` α3Ntαt+1 `Nta)`αt `Nt−1`b)Рис. 8.1: множество Nf для цепной и циклической ФАЛ fОпределим ДНФ сумма минимальных ФАЛ f (ДНФ ΣMФАЛ f ) как дизъюнкцию всех тех её простых импликант,которые входят хотя бы в одну минимальную ДНФ ФАЛ f .Функция f (x1 , . . .

, xn ) называется цепной (циклической)функцией длины t, если ее сокращенная ДНФ с «геометрической» точки зрения представляет собой цепь (соответственно цикл) из t последовательно соединенных ребер N1 , N2 , . . . , Ntкуба B n (см. рис. 8.1a и 8.1b). Заметим, что циклическаяФАЛ длины t существует тогда и только тогда, когда t > 6 —четное число, а цепная ФАЛ длины t — при любом t > 1.Пример цепной ФАЛ длины 3 дает ФАЛ g 00 , показанная нарис. 4.1, а ФАЛ g (см. рис.

2.1a) является циклической ФАЛдлины 6.Из теоремы 4.1 следует, в частности, что для любой цепной ФАЛ длины не меньше 4 и любой циклической ФАЛДНФ ΣT совпадает с сокращенной ДНФ. При этом цепнаяФАЛ f нечетной длины t = 2k − 1 > 3 имеет единственнуюминимальную ДНФ, которая совпадает с ее ДНФ ΣM и соответствует покрытию (см. рис. 8.1a) N1 ∪N3 ∪. . .∪Nt длиныk. Действительно, множество Nf в данном случае состоит из2k наборов и не может быть покрыто (k − 1) ребром. Кро-§8.

Минимизация ДНФNn−157αn `= e1αn−1`α2Nn`αn+1`N1```α1α2n−2N2n−2α2n−1`e0Рис. 8.2: цепная ФАЛ длины (2n − 2) в кубе B nме того, покрытие множества Nf , состоящее из k ребер, неможет включать в себя ребра с общими вершинами и должно содержать ядровые ребра N1 и Nt ФАЛ f . Легко видеть,что только покрытие N1 ∪ N3 ∪ . .

. ∪ Nt обладает всеми этими свойствами. Таким образом, для цепной ФАЛ нечетнойдлины t, t > 5, ДНФ ΣT не совпадает с ДНФ ΣM .Теорема 8.1 (ср. [6, 23, 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.

Действительно,если указанная ФАЛ f найдена, а ее множество Nf соответ-58Глава 1. Дизъюнктивные нормальные формыствует рис. 8.1a, то, полагая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 } (см. рис. 8.2) и применим к ней описанные выше построения.Теорема доказана.Замечание 1. Из теоремы следует, что критерий вхождения ЭК в ДНФ ΣM не имеет такого локального характера,как критерий вхождения ЭК в ДНФ ΣT (сравните с теоремой 4.1).Замечание 2. Известно [7], что при n > 14 в P2 (n) имеетсяцепная ФАЛ четной длины t, t > 2n−11 − 4, на основе которой справедливость теоремыможно установить для окрестtности порядка 2 − 2 (см.

доказательство).Литература[1] Алексеев В. Б. Введение в теорию сложности алгоритмов. М.: Издательский отдел ф-та ВМиК МГУ, 2002.[2] Алексеев В. Б., Вороненко А. А., Ложкин С. А.,Романов Д. С., Сапоженко А. А., Селезнева С. Н.Задачи по курсу «Основы кибернетики». Издательский отдел ф-та ВМиК МГУ, 2002.[3] Алексеев В. Б., Ложкин С. А. Элементы теории графов, схем и автоматов. М.: Издательский отдел ф-таВМиК МГУ, 2000.[4] Боровков А. А. Курс теории вероятностей. М.: Наука,1976.[5] Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике.

3-е изд., перераб.М.: ФИЗМАТЛИТ, 2004.[6] Дискретная математика и математические вопросы кибернетики, под редакцией С. В. Яблонского иО. Б. Лупанова. Т. 1. М.: Наука, 1974.[7] Евдокимов А. А. О максимальной длине цепи в единичном n-мерном кубе // Матем. заметки. 1969. 6. №3.С.