А.А. Сапоженко - Некоторые вопросы сложности алгоритмов (PDF) (1132758), страница 3
Текст из файла (страница 3)
Другие используемые, но неопределяемые здесь понятия можно найти в [2] или [3].Лемма 3.1 Пусть f — произвольная булева функция. Тогда1. ДНФ Dfсок р реализует функцию f .2. Всякая тупиковая, а, значит, и всякая минимальная ДНФ функцииf может быть получена из Dfсок р путем отбрасывания некоторых слагаемых.Конъюнкция K ∈ Dfсок р называется ядровой, если существует α̃ ∈ NKтакая, что L(α̃) = 0 для любой конъюнкции L ∈ Dfсок р \ K. Множество всехядровых конъюнкций функции f называется ее ядром.Теорема 3.1 (W.V.Quine) Конъюнкция K ∈ Dfсок р содержится во всех тупиковых ДНФ функции f тогда и только тогда, когда она входит в ядроэтой функции.Доказательство.Необходимость.
Пусть конъюнкция K входит во все тупиковые ДНФ функции f , но не входит в ее ядро. Тогда для каждой вершины α̃i ∈ NK существует конъюнкция Ki ∈ Dfсок р такая, что Ki (α̃i ) = 1. Поэтому удаление K из12Dfсок р приводит к эквивалентной ДНФ. Продолжив удаление слагаемых изDfсок р с сохранением эквивалентности, придем к некоторой тупиковой ДНФфункции f , не содержащей K. Получаем противоречие.Достаточность.
Из определения ядра следует, что удаление ядровой конъюнкции K из Dfсок р приводит к ДНФ, которая не эквивалентна Dfсок р , а,значит, не реализует f . Утверждение следует теперь из леммы 3.1.2Следствие 3.1 Свойство вхождения K во все тупиковые ДНФ функции fможно установить по S1 (K, Dfсок р ).Доказательство.В силу теоремы Квайна достаточно доказать, что свойство конъюнкции K“входить в ядро” можно установить по ее окрестности S1 (K, Dfсок р ). В самом деле, достаточно выяснить, поглощается ли конъюнкция K дизъюнкциейконъюнкций, содержащихся в S1 (K, Dfсок р ) и отличных от K.2Пучком с центром в α̃ относительно ДНФ D называется множествоΠ(α̃, D) = {K ∈ D : K(α̃) = 1}.Пусть D — ДНФ, а K — слагаемое этой ДНФ.
Точка α̃ ∈ ND называетсярегулярной относительно (K, D), если1. K(α̃) = 1,2. Существует β̃ ∈ ND такая, что K(β̃) = 0 и Π(β̃, D) ⊂ Π(α̃, D).Пусть 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 не может быть отброшена, ибо только она покрывает точку α̃.13Следовательно, существует тупиковая ДНФ функции f , содержащая конъюнкцию K.Достаточность. Пусть конъюнкция K регулярна относительно Dfсок р . Удалим K из Dfсок р . ДНФ D = Dfсок р \ K эквивалентна Dfсок р , ибо, в силу регулярности K, для всякой точки α̃ ∈ NK существует β̃ ∈ ND такая, чтоβ̃ 6∈ NK и Π(β̃, Dfсок р ) ⊂ Π(α̃, Dfсок р ). Последнее означает, что всякая точка α̃ ∈ NK покрыта некоторой конъюнкцией из D. Продолжая отбрасываниеслагаемых из ДНФ D с сохранением эквивалентности, придем к тупиковойДНФ, не содержащей K.2Следствие 3.2 Свойство конъюнкции K “быть регулярной относительноДНФ Dfсок р ”, а тем самым, и свойства “входить хотя бы в одну тупиковуюДНФ функции f ”, можно установить по ее окрестности S2 (K, Dfсок р ).Доказательство.В самом деле, требуется установить для каждой точки α̃ из NK , является лиэта точка регулярной.
Для этого надо сравнить пучки с центрами в точках изNK с пучками, центры которых находятся во множествах вида NL , где L —ррконъюнкция из S1 (K, D)сок. Но Π(β̃, Dfсок р ) ⊆ S2 (K, D)сокдля любой точкиffсок рβ ∈ NL , где L — конъюнкция из S1 (K, D)f . В то же время, Π(α̃, Dfсок р ) ⊆рS1 (K, D)сокдля любой точки α ∈ NK . Таким образом, все конъюнкции,fрсодержащиеся в рассматриваемых пучках принадлежат S2 (K, D)сок.2f14Вхождение конъюнкции хотя бы в одну минимальную ДНФe = (α1 , . . . , αn ) и βe = (β1 , . . . , βn )Расстоянием между двоичными наборами αназывается числоne =e β)ρ(α,X| α i − βi | .i=1e1, .
. . , αe m ∈ B n называется цепью, если выПоследовательность вершин αполнены условия:ei, αe i+1 ) = 1, для всех i = 1, . . . , m − 1,1. ρ(αei, αe j ) > 1, для всех i, j таких, что | i − j |> 1.2. ρ(αФункция f (xe) называется цепной, если можно упорядочить наборы из Nfтак, что образуется цепь.Лемма 3.2 Пусть f - цепная функция и | Nf |= m > 1. Тогда1. Все максимальные грани f являются ребрами.e1, . . . , αe m множества Nf в указанном порядке образу2. Пусть наборы αei, αe i+1 }, i = 1, . .
. , m−1, и пусть Ki —конъюнкция,ют цепь. Положим Ni = {αсоответствующая ребру Ni . Тогда Dfсок р = K1 ∨ K2 ∨ . . . ∨ Km−1 .3. Пусть m четно, тогда D = K1 ∨ K3 . . . ∨ Km−1 — единственная минимальная ДНФ функции f .Доказательство.Утверждение 1 следует из того, что, с одной стороны, каждая вершина содержится хотя бы в одном ребре, а с другой стороны, в силу свойства 2определения цепи, грани размерности 2 отсутствуют.Утверждение 2 следует из утверждения 1.Минимальность ДНФ D следует из того, что все максимальные грани цепной функции являются ребрами, каждое из которых содержит две вершины,а для покрытия 2m вершин цепи требуется не менее m ребер.Единственность минимальной ДНФ D, состоящей из конъюнкций с нечетными номерами, докажем от противного. Если бы существовала еще одна минимальная ДНФ D0 6= D, то в ней нашлась бы конъюнкция вида K2ie 2i , αe 2i+1 }. Пусть i — наименьшее целое, такое что конътакая, что NK2i = {αюнкция K2i является слагаемым ДНФ D0 .
Конъюнкция K1 входит в ДНФD0 как ядровая. Объединение множества ребер N1 , . . . , N2i−1 , N2i содержит2i − 1 вершин из Nf . Для покрытия оставшихся 2m − 2i + 1 вершин требуется еще по меньшей мере m − i + 1 ребер. Следовательно, ДНФ D0 имеет неменее m + 1 слагаемых. Отсюда и из пункта 1 вытекает, что D0 не являетсяминимальной.215Замечание 3.1 В дальнейшем подразумевается, что вершины множества Nf , а также конъюнкции в Dfсок р цепной функции f пронумерованы всоответствии с пунктом 2 леммы 3.2.Следствие 3.3 Если функция f цепная, то при “естественной” нумерацииконъюнкций из Dfсок р ни одна конъюнкция с четным номером не входит вее единственную минимальную ДНФ.e1, .
. . , αe 2m ∈ B n , m > 2 называется циклом,Последовательность вершин αесли выполнены условия:ei, αe i+1 ) = 1, для всех i = 1, . . . , 2m − 1;1. ρ(αee j ) > 1, для всех i, j таких, что | i − j |> 1 (mod 2m),2. ρ(αi , αe 2m , αe 1 ) = 1.3. ρ(αЛемма 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 (xe) называется циклической, если можно упорядочить наборыиз Nf так, что образуется цикл. Обозначим через DfΣM ДНФ, состоящую извсех конъюнкций, входящих хотя бы в одну минимальную ДНФ функции f .Лемма 3.4 Пусть f - циклическая.Тогда1. Все максимальные грани f являются ребрами;e1, . .
. , αe 2s множества Nf в указанном порядке обра2. Пусть точки αei, αe i+1 }, i = 1, . . . , 2s − 1, и N2s = {αe 2s , αe 1 }, —зуют цикл. Пусть Ni = {αребра этого цикла. Обозначим через Ki конъюнкцию, соответствующуюребру Ni . Тогда Dfсок р = K1 ∨ K2 , ∨ . . . ∨ K2s .3. Существует ровно две минимальные ДНФ:D1 = K1 ∨ K3 ∨ . . .
∨ K2s−1иD2 = K2 ∨ K4 ∨ . . . ∨ K2s .4. Df∪M = Dfсок р .Доказательство.Утверждения 1 и 2 доказываются аналогично соответствующим пунктамлеммы 3.2.16Минимальность ДНФ D1 и D2 также вытекает по соображениям, аналогичным тем, что использовались в лемме 3.2. То, что других минимальныхДНФ нет, вытекает из того, что если в ДНФ входят конъюнкции с номерамиразной четности, то, как и в лемме 3.2, такая ДНФ содержит не менее m + 1конъюнкций. Утверждение 4 вытекает из пунктов 2 и 3.2Теорема 3.3 (Ю.И.Журавлев).
Для любого r существует n и f (xen ) такие, что1. Df∪M = Dfсок р ;2. Для любой конъюнкции K ∈ Dfсок р существует функция hK такая,чторSr (K, Dfсок р ) = Sr (K, Dhсок)(13)KиK∈/ Dh∪M.KДоказательство.Зафиксируем r. Пусть n > r + 3. Пусть f = f (x1 , . . . , xn ) — циклическаяфункция такая, что множество Nf состоит из вершин цикла Sn , определенного в лемме 3.3. Тогда Df∪M = Dfсок р в силу леммы 3.4.Пусть K ∈ Dfсок р и m есть нечетное число из пары (r, r + 1). Определимфункцию hK следующим образом. ПоложимNhK = ∪L∈Sm (K,Dfсокр ) NL .рЯсно, что hK — цепная функция и |NhK | = 4m.
Кроме того, K ∈ DhсоквKсок рестественной нумерации слагаемых в DhK конъюнкция K имеет номер 2m,а, значит, в силу cледствия 3.3, она не входит в единственную минимальнуюДНФ функции hK .2Следствие 3.4 Для любого r существуют число n и функция f (xen ) такие,что никакой локальный алгоритм A индекса r с произвольной функциейвычисления пометок ϕ, удовлетворяющей условию локальности (12) и имеющей вид:ϕ(K, Sr (K, Dfсок р )) 1,если K ∈ D∪Mf ,∪M/ Df ,= 0, если K ∈−, если значение ϕ неизвестно,не может изменить отметку ни над одной конъюнкцией из Dfсок р .17Доказательство.В самом деле, алгоритм A индекса r принимает решение о вхождении и илиневхождении конъюнкции K в ДНФ Df∪M только по окрестности конъюнкции K порядка r.
На первом шаге алгоритма все пометки над конъюнкциямиравны“-”. Поэтому в силу равенства (13) свойство локальности (12) выполнено для определенной выше функции ϕ, любой конъюнкции K из Dfсок р ирпары ДНФ (D, D0 ), где D = Dfсок р и D0 = Dhсок. Поэтому значение функKции ϕ не может быть определенным. В самом деле, значение пометки “0”противоречит тому, что K ∈ Df∪M , а значение “1” — тому, что K ∈/ Dh∪M.KОтсюда вытекает утверждение.2Список литературы[1] Ю.И.Журавлев, Теоретико-множественные методы в алгебре логики// Всб.
Проблемы кибернетики, М.: Наука, Вып. 8, 1962г., С.5-44.[2] Ю.И.Журавлев, Избранные научные труды, М. 1998г., 417 с.[3] А.А.Сапоженко, Дизюнктивные нормальные формы, Издательство МГУ,1975, 90 с.184Теорема КукаВведение. В параграфе доказывается теорема Ст. Кука. Центральными понятиями являются (полиномиальная) сводимость языков, детерминированные и недетерминированные машины Тьюринга, классы P и N P , N P -полнота.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
