OK_metodichka_part_1 (1132796), страница 9
Текст из файла (страница 9)
Поясковой ФАЛ является, в[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) отрицаний БП, то есть имеет§8. Минимизация ДНФ57видs[r,p](x1 , . . . , xn ) =n_σn+r−p.xσi11 · · · xin+r−p(8.1)16i1 <···<in+r−p 6nσ1 +···+σn+r−p =rИз (8.1) sn следует, что длина сокращенной ДНФ ФАЛnn−pnравна r · n−r , и поэтому при r = n − p = 3 она всоответствии с формулой Стирлинга (1.3) не меньше, чемne1 3n , где e1 — некоторая константа.Рассмотренные примеры показывают, что с алгоритмической точки зрения задача минимизации ДНФ являетсяочень трудоемкой задачей. В теории сложности вычислений,где трудоемкость алгоритма определяется, обычно, числомбитовых операций, необходимых для его выполнения в «худшем» случае, выделен целый класс так называемых NPполных проблем, которые считаются алгоритмически трудными (см., например, [1, 22]).
К NP-полным проблемам относится, в частности, проблема выполнимости КНФ, которая состоит в том, чтобы по заданной КНФ выяснить, равнатождественно нулю реализуемая ею ФАЛ или нет. Таким образом, даже построение сокращенной ДНФ из КНФ (см. ??)является алгоритмически трудной задачей.С другой стороны, Ю.И. Журавлев [9, 6] предложил применительно к ДНФ модель так называемых локальных илиокрестностных алгоритмов, когда преобразование рассматриваемой грани однозначно определяется «состоянием» ее«окрестности» заданного порядка (см. §4). Он же (см. теорему 4.2) доказал, что при построении минимальной ДНФдля ФАЛ из P2 (n) , n > 3, приходится, в общем случае, рассматривать окрестности порядка (n − 3) ее максимальныхграней.
Следовательно, задача минимизации ДНФ являетсятрудной и с точки зрения уровня локальности используемыхалгоритмов.[r,p]58Глава 1. Дизъюнктивные нормальные формыРешение задач минимизации ДНФ для заданной ФАЛхарактеризуется различными параметрами этой ФАЛ и, впервую очередь, значениями исследуемых функционалов еесложности (см. §7). Кроме того, как отмечалось выше, рядпараметров (длина сокращенной ДНФ, число тупиковых илиминимальных ДНФ и др.) характеризуют трудоемкость задачи минимизации ДНФ для рассматриваемой ФАЛ. В связи с этим представляет интерес поведение при n = 1, 2, .
. .,максимального значения того или иного подобного параметра ψ для ФАЛ из P2 (n):ψ(n) = max ψ(f ),f ∈P2 (n)которое,как и в случае функционалов сложности, называют,обычно, функцией Шеннона для параметра ψ в классе ДНФ.Будем обозначать значение функции Шеннона для параметров, равных числу тупиковых ДНФ и длине сокращенной ДНФ у ФАЛ из P2 (n), через τ (n) и λсокр. (n) соответственно. Из приведенных выше примеров ФАЛ следует, чтоτ (n) > 52n−4и(8.2)3n(8.3)nгде e1 — некоторая положительная константа.Получим теперь некоторые верхние оценки функций Шеннона τ (n) и λсокр. (n).Для частично упорядоченного множества (A, τ ) множество, состоящее из попарно сравнимых (несравнимых) элементов множества A, называется цепью (соответственно антицепью) этого частично упорядоченного множества.
Заметим, что цепь C ⊆ A в частично упорядоченном множестве (A, τ ) представляет собой линейно упорядоченное множество вида (C, τ ). Максимальная мощность цепей (антицепей) частично упорядоченного множества называется егоλсокр. (n) > e1§8. Минимизация ДНФ59Рис. 8.1: неуплотняемая цепь в B nдлиной (соответственно шириной). Цепь или антицепь частично упорядоченного множества называется неуплотняемой, если она представляет собой максимальное по включению множество соответствующего типа.Частично упорядоченное множество (A, τ ) длины t называется ранжированным множеством, если все его неуплотняемые цепи имеют мощность t. При этом каждый элементA имеет, очевидно, один и тот же номер в любой содержащейего неуплотняемой цепи, а все элементы из A, для которыхуказанный номер равен i, i ∈ [0, t), образуют i-й ярус данного ранжированного множества (A, τ ).
Заметим, что каждыйярус ранжированного множества является его неуплотняемой антицепью.Примером ранжированного множества длины (n + 1) является частично упорядоченное множество (B n , 6). Действительно, любая неуплотняемая цепь данного множества состоит из (n + 1) наборов α0 , α1 , . . .
, αn таких, что 0̃ = α0 <60Глава 1. Дизъюнктивные нормальные формыα1 < . . . < αn = 1̃ (см. рис. 8.1). При этом αk ∈ Bkn для всехk, k ∈ [0, n], наборы αi−1 и αi , i ∈ [1, n], отличаются только в разряде с номером ji , где (j1 , . . .
, jn ) — перестановкачисел 1, 2, . . . , n, а указанное соответствие между неуплотняемыми цепями и перестановками является взаимно однозначным. Отсюда следует, что i-й слой Bin , i ∈ [0, n], является i-м ярусом ранжированного множества (B n , 6) и чточерез каждый набор этого множества проходит (i!) · (n − i)!его неуплотняемых цепей, а общее число всех таких цепейравно n!.Лемма 8.2. Если в ранжированном множестве через каждые два элемента одного и того же яруса проходит одинаковое число неуплотняемых цепей, то ширина данногочастично упорядоченного множества равна максимальноймощности его ярусов.Доказательство. Пусть длина ранжированного множества(A, τ ) равна t, T — множество его неуплотняемых цепей, аAi , где i ∈ [0, t), — i-й ярус этого ранжированного множества, каждый элемент которого содержится в di цепях из T .Заметим, что|Ai | · di = |T |для любого i ∈ [0, t), и поэтомуmax |Ai | = |Aj |,06i<tгде j ∈ [0, t), тогда и только тогда, когдаmin di = dj .06i<tПусть, далее, A0 ⊆ A — неуплотняемая антицепь частичноупорядоченного множества (A, τ ) и пусть A0i = Ai ∩ A0 длявсех i ∈ [0, t).
Заметим, что каждая неуплотняемая цепь частично упорядоченного множества (A, τ ) содержит не более§8. Минимизация ДНФ61одного элемента множества A0 и поэтому, с учетом приведенных выше соотношений|Aj | · dj = |T | >t−1X|A0i | · di > |A0 | · dj ,i=0откуда следует, что|A0 | 6 |Aj |.Лемма доказана.Следствие 1. Ширина частично упорядоченного множества (B n , 6) равна d nn e .2Доказательство. Действительно, нетрудно убедиться в том,что неравенства nn<и 2i + 1 < nii+1равносильны, если i изменяется на отрезке [0, n].Таким обnразом, максимальное по i значениеi на отрезn n−1 величиныn =иравноке [0, n] достигается при i =22b n2 c , амножество B n n является максимальной по числу элеменb2cтов антицепью множества (B n , 6).Лемма 8.3.
Для любого натурального n справедливы неравенства: n n 2 n33n−2526 τ (n) 66 3·.(8.4)2n2Доказательство. Нижняя оценка (8.4) для τ (n) вытекаетиз (8.2). Чтобы получить верхние оценки (8.4) для τ (n),установим между множеством всех ДНФ от БП X (n) и куnбом B 3 изоморфизм, отображающий ДНФ A в набор β, для62Глава 1. Дизъюнктивные нормальные формыРис. 8.2: неуплотняемая цепь в Γ(n)которого β hii = 1 тогда и только тогда, когда грань куба B nс номером i, i ∈ [1, 3n ], входит в покрытие, связанное с A.При этом любая тупиковая ДНФ соответствует набору с неболее, чем 2n , единицами, а две различные тупиковые ДНФодной и той же ФАЛ — попарно не сравнимым наборам.Следовательно, число тупиковых ДНФ у одной и той жеФАЛ из P2 (n) не больше ширины частично упорядоченного множества (A, 6), где множество A состоит из всех слоевnкуба B 3 с номерами 0, 1, .
. . , 2n , которая,в свою очередь, вnсилу леммы 8.2, не больше, чем 32n . Оценивая указанныйбиномиальный коэффициент с помощью неравенства (1.4),получим последнюю из верхних оценок (8.4).Лемма доказана.Лемма 8.4. Для некоторых положительных констант e1 , e2§8. Минимизация ДНФ63и любого натурального n справедливы неравенстваe13n3n6 λсокр. (n) 6 e2 √ .nn(8.5)Доказательство. Нижняя оценка (8.5) следует из (8.3).Для получения верхней оценки (8.5) рассмотрим частично упорядоченное множество (Γ(n) , ⊆), которое задается отношением вложения на множестве Γ(n) , состоящем из всехграней куба B n , и является ранжированным множествомдлины (n + 1).
Действительно, любая неуплотняемая цепьэтого множества состоит из (n + 1) вложенных граней Γγ0 ⊆Γγ1 ⊆ . . . ⊆ Γγn размерности 0, 1, . . . , n соответственно (см.§2). При этом (см. рис. 8.2) γ0 ∈ B n , то есть Γγ0 = {γ0 },γn = (2, . . . , 2), то есть Γγn = B n , и набор γi , i ∈ [1, n], получается из набора γi−1 заменой в разряде с номером ji значения 0 или 1 на значение 2, где π = (j1 , . . . , jn ) — перестановка чисел 1, 2, . . .
, n, а указанное соответствие междурассматриваемыми цепями и парами (π, γ0 ) является, очевидно, взаимно однозначным.Отсюда следует, что i-й ярус, i ∈ [0, n), ранжированногомножества (Γ(n) , ⊆) состоитиз всех граней размерности i,n n−iчисло которых равно i 2 , и что через каждую такуюгрань проходит (n − i)!i!2i его неуплотняемых цепей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
