1 (С.А. Ложкин - Лекции по основам кибернетики (2017)), страница 8

. . , xn ) =xσ2 2 · · · xσnn · f x1 , σ 00(7.2)σ 00 =(σ2 ,...,σn )Легко видеть, что после замены в разложении (7.2) каждойФАЛ f (x1 , σ 00 ) равной ей ФАЛ из множества {0, 1, x1 , x1 } иприведения подобных мы получим ДНФ Af длины не больше, чем 2n−1 , что доказывает верхние оценки в (7.1).Лемма доказана.При изучении того или иного связанного с ДНФ функционала ψ наряду с его максимальным значением, то естьфункцией Шеннона ψ (n), представляет интерес соответствующий отрезок "типичных" значений, то есть отрезок [ψ 0 (n) , ψ 00 (n)],в который попадают значения ψ (f ) для почти всех ФАЛ fиз P2 (n).

Если при этом границы ψ 0 (n) и ψ 00 (n), где n =1, 2, . . ., асимптотически равны ψ (n), то говорят, что дляпараметра ψ имеет место эффект Шеннона. Выясним некоторые особенности строения ДНФ у почти всех ФАЛ и установим, в частности, отсутствие эффекта Шеннона для параметров λ и R - длины и ранга ДНФ соответственно.50ВведениеВведем дискретную векторную случайную величину ξ (n) =ξe0 , . . . , ξe1 , состоящую из 2n независимых случайных величин ξα , α ∈ B n , принимающих значения 0 и 1 с вероятностью 12 . При этом, очевидно, для любого α, α ∈ B n , выполняются равенства1Eξα = ,21Dξα = ,4(7.3)где Eθ и Dθ - математическое ожидание и дисперсия случайной величины θ (см., например, [25]).Будем считать, что любая ФАЛ f из P2 (n) является реализацией величины ξ, при которой ξα = f (α) для любогоnα, α ∈ B n , и что вероятность такой реализации равна 2−2 .Отсюда следует, что для любого множества Q, Q ⊆ P2 (n),nотношение |Q| /22 , то есть доля тех ФАЛ f из P2 (n), которые принадлежат Q, равна вероятности того, что реализация случайной величины ξ принадлежит Q.Из независимости случайных величин ξα , α ∈ B n , вытеe которая равна мощностикает, что для их суммы ξe(n) = ξ,множества Nf для ФАЛ f , являющейся реализацией случайной величины ξ (n) = ξ, в силу (7.3) справедливы равенства(см., например, [4])Eξe(n) = 2n−1 ,Dξe(n) = 2n−2 ,(7.4)Полагаяlmnt = n · 22 ,I = 2n−1 − t, 2n−1 + tи применяя к случайной величине ξe с учетом (7.4) неравенство Чебышева [4], получим, что вероятность события ξe ∈/ I,то есть доля тех ФАЛ f из P2 (n), для которых |Nf | ∈/ I, небольше, чемDη16 22t4nВведение51и, следовательно, стремится к 0 при n стремящемся к бесконечности.

Это означает, в частности, что для почти всехФАЛ f из P2 (n), выполнено равенство|Nf | = 2n−1 1 ± O n · 2−n/2(7.5)то есть длина совершенной ДНФ у почти всех ФАЛ из P2 (n)асимптотически равна 2n−1 .Лемма 7.2. Для почти всех ФАЛ f , f ∈ P2 (n), выполняются неравенства3λ(f ) 6 2n−1 1 + O n · 2−n/2 ,43λ(f ) 6 n · 2n−1 1 + O n · 2−n/2 ,4(7.6)(7.7)Доказательство. Пусть ФАЛ f , f ∈ P2 (n), является реализацией случайной величины ξ. Для каждого набора β, β ∈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Введениеи проводя на основе (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Все ДНФ рассматриваются с точностью до перестановки ЭК и буквв них.Введение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ВведениеСледствие.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Введение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Введение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 , . .