А.А. Сапоженко - Некоторые вопросы сложности алгоритмов (1158759), страница 3
Текст из файла (страница 3)
Пусть конъюнкция K входит во все тупиковые ДНФ функции f , но не входит в ее ядро. Тогда для каждойвершины α̃i ∈ NK существует конъюнкция Ki ∈ Dfсокр такая, что Ki (α̃i ) = 1. Поэтому удаление K из Dfсокр приводит кэквивалентной ДНФ. Продолжив удаление слагаемых из Dfсокр с сохранением эквивалентности, придем к некоторой тупиковойДНФ функции f , не содержащей K. Получаем противоречие.Достаточность.
Из определения ядра следует, что удаление ядровой конъюнкции K из Dfсокр приводит к ДНФ, которая неэквивалентна Dfсокр , а, значит, не реализует f . Утверждение следует теперь из леммы 3.1.27Следствие 3.1 Свойство вхождения K во все тупиковые ДНФ функции f можно установить по S1 (K, Dfсокр ).Доказательство.В силу теоремы Квайна достаточно доказать, что свойство конъюнкции K “входить в ядро" можно установить по ееокрестности S1 (K, Dfсокр ). В самом деле, достаточно выяснить, поглощается ли конъюнкция K дизъюнкцией конъюнкций,содержащихся в S1 (K, Dfсокр ) и отличных от K.2Определение 3.3 Пучком с центром в α̃ относительно ДНФ D называется множествоΠ(α̃, D) = {K ∈ D : K(α̃) = 1}.Определение 3.4 Пусть D — ДНФ, а K — слагаемое этой ДНФ.
Точка α̃ ∈ ND называется регулярной относительно(K, D), если1. K(α̃) = 1,2. Существует β̃ ∈ ND такая, что K(β̃) = 0 и Π(β̃, D) ⊂ Π(α̃, D).Определение 3.5 Пусть D — ДНФ, а K — слагаемое этой ДНФ. Конъюнкция K называется регулярной относительноD, если всякая точка α̃ ∈ NK является регулярной относительно (K, D).Теорема 3.2 ( Ю.И.Журавлев). Конъюнкция K ∈ Dfсокр не содержится ни в одной тупиковой ДНФ функции f тогда итолько тогда, когда она регулярна относительно Dfсокр .Доказательство.Необходимость.
Пусть существует точка α̃ ∈ NK , не являющаяся регулярной относительно (K, Dfсокр ). Удалим из Dfсокр всеконъюнкции пучка Π(α̃, Dfсокр ) за исключением K. Полученная ДНФ D все еще реализует функцию f , ибо в противномслучае нашлась бы точка β̃ ∈ Nf такая, что K(β̃) = 0 и Π(β̃, Dfсокр ) ⊂ Π(α̃, Dfсокр ), что противоречило бы предположению отом, что точка α̃ ∈ NK , не является регулярной. Отбрасывая, если понадобится, некоторые слагаемые из ДНФ D, получимтупиковую ДНФ. При этом конъюнкция K не может быть отброшена, ибо только она покрывает точку α̃.
Следовательно,существует тупиковая ДНФ функции f , содержащая конъюнкцию K.Достаточность. Пусть конъюнкция K регулярна относительно Dfсокр . Предположим, что некоторая тупиковая ДНФ Dфункции f содержит слагаемое K. В силу регулярности K для любого α̃ ∈ NK существует β̃ ∈ ND \ NK такое, чтоΠ(β̃, Dfсокр ) ⊂ Π(α̃, Dfсокр ).(13)Поскоьку β̃ ∈ ND , в D существует слагаемое K(β̃) из Π(β̃, Dfсокр ). Но в силу (13) имеем α̃ ∈ NK(β̃) . Это означает, что каждаяточка α̃ ∈ NK обращает в единицу некоторое слагаемое ДНФ D, отличное от K. Следовательно, удаление K из D приводитк ДНФ, реализующей f , что противоречит предположению о тупиковости ДНФ D.2Следствие 3.2 Свойство конъюнкции K “быть регулярной относительно ДНФ Dfсокр ", а тем самым, и свойства “входитьхотя бы в одну тупиковую ДНФ функции f ", можно установить по ее окрестности S2 (K, Dfсокр ).8Доказательство.В самом деле, требуется установить для каждой точки α̃ из NK , является ли эта точка регулярной.
Для этого надо сравнитьпучки с центрами в точках из NK с пучками, центры которых находятся во множествах вида NL , где L — конъюнкцияиз S1 (K, Dfсокр ). Но Π(α̃, Dfсокр ) ⊆ S1 (K, Dfсокр ) для любой точки α̃ ∈ NK . В то же время, Π(β̃, Dfсокр ) ⊆ S2 (K, Dfсокр ) для любойточки β̃ ∈ NL , где L — конъюнкция из S1 (K, Dfсокр ). Таким образом, все конъюнкции, содержащиеся в рассматриваемыхпучках, принадлежат S2 (K, Dfсокр ).2Вхождение конъюнкции хотя бы в одну минимальную ДНФРасстоянием между двоичными наборами αe = (α1 , .
. . , αn ) и βe = (β1 , . . . , βn ) называется числоe =ρ(eα, β)nX| αi − βi | .i=1Последовательность вершин αe1 , . . . , αem ∈ B n называется цепью, если выполнены условия:1. ρ(eαi , αei+1 ) = 1, для всех i = 1, . . . , m − 1,2. ρ(eαi , αej ) > 1, для всех i, j таких, что | i − j |> 1.Функция f (ex) называется цепной, если можно упорядочить наборы из Nf так, что образуется цепь.Лемма 3.2 Пусть f - цепная функция и | Nf |= m > 1. Тогда1. Все максимальные грани f являются ребрами.2. Пусть наборы αe1 , . . .
, αem множества Nf в указанном порядке образуют цепь. Положим Ni = {eαi , αei+1 }, i =1, . . . , m − 1, и пусть Ki —конъюнкция, соответствующая ребру Ni . Тогда Dfсокр = K1 ∨ K2 ∨ . . . ∨ Km−1 .3. Пусть m = 2s, тогда D = K1 ∨ K3 . . . ∨ K2s−1 — единственная минимальная ДНФ функции f .Доказательство.Утверждение 1 следует из того, что, с одной стороны, каждая вершина содержится хотя бы в одном ребре, а с другойстороны, в силу свойства 2 определения цепи грани размерности 2 отсутствуют.Утверждение 2 следует из утверждения 1.Минимальность ДНФ D следует из того, что все максимальные грани цепной функции являются ребрами, каждое изкоторых содержит две вершины, а для покрытия 2s вершин цепи требуется не менее s ребер.Единственность минимальной ДНФ D, состоящей из конъюнкций с нечетными номерами, докажем от противного.Если бы существовала еще одна минимальная ДНФ D0 6= D, то в ней нашлась бы конъюнкция вида K2i такая, чтоNK2i = {eα2i , αe2i+1 }.
Пусть i — наименьшее целое такое, что конъюнкция K2i является слагаемым ДНФ D0 . КонъюнкцияK1 входит в ДНФ D0 как ядровая. Объединение множества ребер N1 , . . . , N2i−1 , N2i содержит 2i + 1 вершин из Nf . Дляпокрытия оставшихся 2m − 2i − 1 вершин требуется еще по меньшей мере m − i ребер.
Следовательно, ДНФ D0 имеет неменее m + 1 слагаемых. Отсюда и из пункта 1 вытекает, что D0 не является минимальной.2Замечание 3.1 В дальнейшем подразумевается, что вершины множества Nf , а также конъюнкции в Dfсокр цепнойфункции f пронумерованы в соответствии с пунктом 2 леммы 3.2.Следствие 3.3 Если функция f цепная и Nf четно, то при “естественной"нумерации конъюнкций из Dfсокр ни однаконъюнкция с четным номером не входит в ее единственную минимальную ДНФ.9Последовательность вершин αe1 , .
. . , αe2m ∈ B n , m > 2 называется циклом, если выполнены условия:1. ρ(eαi , αei+1 ) = 1 для всех i = 1, . . . , 2m − 1;2. ρ(eαi , αej ) > 1 для всех i, j таких, что |i − j| > 1 (mod 2m);3. ρ(eα2m , αe1 ) = 1.Лемма 3.3 Для любого n ≥ 3 в B n существует цикл с 2n вершинами.Доказательство.Примером такого цикла в B n является последовательностьSn = (00 . . . 00), (00 . . . 01), . . . , (11 . .
. 11), (11 . . . 10), . . . , (10 . . . 00),в которой число единиц в очередном наборе сначала увеличивается на 1, а затем, достигнув n, последовательно уменьшаетсяна 1.2Функция f (ex) называется циклической, если можно упорядочить наборы из Nf так, что образуется цикл. Обозначимчерез Df∪M ДНФ, состоящую из всех конъюнкций, входящих хотя бы в одну минимальную ДНФ функции f .Лемма 3.4 Пусть f — циклическая функция. Тогда1. Все максимальные грани f являются ребрами.2. Пусть точки αe1 , . . . , αe2sмножества Nf в указанном порядке образуют цикл.
Пусть Ni = {eαi , αei+1 }, i =1, . . . , 2s − 1, и N2s = {eα2s , αe1 } — ребра этого цикла. Обозначим через Ki конъюнкцию, соответствующую ребру Ni .Тогда Dfсокр = K1 ∨ K2 ∨ . . . ∨ K2s .3. Существуют ровно две минимальные ДНФ:D1 = K1 ∨ K3 ∨ . . . ∨ K2s−1иD2 = K2 ∨ K4 ∨ . . . ∨ K2s .4. Df∪M = Dfсокр .Доказательство.Утверждения 1 и 2 доказываются аналогично соответствующим пунктам леммы 3.2.Минимальность ДНФ D1 и D2 также вытекает по соображениям, аналогичным тем, что использовались в лемме 3.2.То, что других минимальных ДНФ нет, вытекает из того, что если в ДНФ входят конъюнкции с номерами разной четности,то, как и в лемме 3.2, такая ДНФ содержит не менее s конъюнкций. Утверждение 4 вытекает из пунктов 2 и 3.2Теорема 3.3 (Ю.И.Журавлев). Для любого r существуют n и f (exn ) такие, что1. Df∪M = Dfсокр ;2.
Для любой конъюнкции K ∈ Dfсокр существует функция hK такая, чтоSr (K, Dfсокр ) = Sr (K, Dhсокр)KиK∈/ Dh∪M.K10(14)Доказательство.Зафиксируем r. Пусть n > r + 3. Пусть f = f (x1 , . . . , xn ) — циклическая функция такая, что множество Nf состоит извершин цикла Sn , определенного в лемме 3.3. Тогда Df∪M = Dfсокр в силу леммы 3.4.Пусть K S∈ Dfсокр и m есть нечетное число из пары (r, r + 1). Определим функцию hK следующим образом. ПоложимNhK =NL .
Ясно, что hK — цепная функция и |NhK | = 4m. Кроме того, K ∈ Dhсокр, и при этом в естественнойKсокрL∈Sm (K,Df)нумерации слагаемых в Dhсокрконъюнкция K имеет номер 2m, а значит, в силу cледствия 3.3, она не входит в единственнуюKминимальную ДНФ функции hK .2Следствие 3.4 Для любого r существуют число n и функция f (exn ) такие, что никакой локальный алгоритм A индексаr с произвольной функцией вычисления пометок ϕ, удовлетворяющей условию локальности (12) и имеющей вид:1, если K ∈ Df∪M ,ϕ(K, Sr (K, Dfсокр )) =0, если K ∈/ Df∪M , −, если значение ϕ неизвестно,не может изменить отметку ни над одной конъюнкцией из Dfсокр .Доказательство.В самом деле, алгоритм A индекса r принимает решение о вхождении или невхождении конъюнкции K в ДНФ Df∪M толькопо окрестности конъюнкции K порядка r.
На первом шаге алгоритма все пометки над конъюнкциями равны“-". Поэтомув силу равенства (14) свойство локальности (12) выполнено для определенной выше функции ϕ, любой конъюнкции K изDfсокр и пары ДНФ (D, D0 ), где D = Dfсокр и D0 = Dhсокр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
