О.Б. Лупанов - Элементы математической кибернетики (1161667), страница 2
Текст из файла (страница 2)
. . , αn ) = 1, поскольку K ◦ > Ki ,i = 1, n по свойству 3 множества M. А значит найдется такая конъюнкция Kj , j ∈ 1, n, что Kj (α1 , . . . , αn ) = 1, и так как она заведомо небольшей длины, чем K ◦ , то K ◦ 6 Kj . Это противоречит свойству 3множества M. Итак, K ◦ не содержит xl .Конъюнкция K ◦ xl из–за большей длины не принадлежит множеству M, однако свойства 1 и 2 выполнены, поскольку K ◦ xl 6 K ◦ 6 K.Следовательно, не должно выполняться свойство 3, то есть K ◦ xl 6 Kiдля некоторой Ki ∈ M. Покажем, что Ki содержит xl . Если допустить, что это не так, то K ◦ будет поглощаться конъюнкцией Ki , ведьK ◦ xl 6 Ki . Выходит, что Ki = K ′ xl .Аналогично, K ◦ xl 6∈ M, и K ◦ xl 6 Kj для некоторой Kj ∈ M.
Затемтак же приходим к Kj = K ′′ xl .6Применим теперь операцию обобщенного склеивания к Ki и Kj :K K ′′ 6 Kh для некоторого Kh ∈ F в силу замкнутости F . А так какK ◦ 6 K ′ и K ◦ 6 K ′′ , то K ◦ 6 K ′ K ′′ 6 Kh , то есть K ◦ поглощается некоторой Kh из F . Противоречие с построением множества M. Утверждение доказано.На основе следующей теоремы можно построить алгоритм поискасокращенной ДНФ.′Теорема 2. Замкнутая ДНФ F функции f содержит все минимальные конъюнкции функции f .Доказательство. Пусть F = K1 ∨ · · · ∨ Ks cостоит из минимальныхконъюнкций и допустим, K — минимальная конъюнкция функции f ,не входящая в F . Согласно основной лемме о замкнутой ДНФ K поглощается некоторой Ki из F .
В силу минимальности Ki получим, чтоK = Ki . Теорема доказана.Аналогично ДНФ определяется и КНФ — конъюнктивная нормальная форма: D1 & · · · &Ds , где дизъюнкции Di = xσi1i1 ∨ · · · ∨ xσikik .Утверждение 3. При раскрытии скобок в произвольной КНФ получается обобщенная замкнутая ДНФ.Схема доказательства. Рассмотрим типичную ситуацию при перемножении скобок: выражение вида K ′ xi ∨ K ′′ xi , где K ′ = xσj K̃ иK ′′ = xτh K̂, может быть получено из (xi ∨ xτh · · · )&(xi ∨ xσj · · · ).
Результат обобщенного склеивания xσj K̃xτh K̂ будет полгощаться, например,конъюнкцией xσj xτh K̃. Так получим замкнутую ДНФ.Обратимся снова к терминологии. Будем говорить, что минимальная конъюнкция K функции f входит в ядро функции f , если существует набор α̃ из Nf такой, что K — единственная минимальная конъюнкция функции f , обращающаяся в 1 на наборе α̃.Определим так называемый тип суммы тупиковых (ΣT ). ΣT —дизъюнкция минимальных конъюнкций, входящих хотя бы в одну тупиковую ДНФ данной функции.Пусть K — минимальная конъюнкция функции f (x1 , . . . , xn ), наборα̃ таков, что K(α̃) = 1.
Будем называть α̃ регулярным относительноK, если существует набор β̃α ∈ Nf , но K(β̃α ) = 0, что Pα ⊆ Pβα . Минимальная конъюнкция K называется регулярной, если любой набор α̃для которого K(α̃) = 1, регулярен относительно K.Теорема 3. Конъюнкция K не входит в ДНФ типа ΣT тогда и только тогда, когда K регулярна.7Доказательство.
1. Пусть K регулярна. Это означает, что для любого набора α̃ ∈ NK , существует такой набор β̃α ∈ Nf , β̃α 6∈ NK , чтоPα ⊆ Pβα . Допустим, что K входит в ДНФ типа ΣT . Пусть эта тупиковая ДНФ такова: K ∨ K (1) ∨ · · · ∨ K (l) . Из связи между пучками наборов α̃ и β̃α следует, что среди K, K (1) , . . . , K (l) обязана существоватьтакая конъюнкция K(α) , что K(α) (α̃) = 1, K(α) (β̃α ) = 1, причем отличная от K, так как K(β̃α ) 6= 1.
Таким образом, каждый набор α̃ будетобслуживаться“, кроме собственно K, еще и некоторой конъюнкцией”из K (1) , . . . , K (l) . Значит, если удалить K, то ДНФ будет по–прежнемуреализовывать ту же функцию. Это противоречит тупиковости ДНФ.Следовательно, K не входит в ДНФ типа ΣT .2. Пусть K нерегулярна. Это означает, что существует такой нерегулярный относительно K набор α̃, что K(α̃) = 1.
Нерегулярность набораα̃ в свою очередь подразумевает, что для любого такого набора β̃ ∈ Nf ,что K(β̃) = 0, можно указать конъюнкцию K(β) ∈ Pβα , которая обращается в нуль на наборе α̃. Построим ДНФ следующим образом: длякаждого такого набора β̃ ∈ Nf , что K(β̃) = 0, образуем такую конъюнкцию K(β) , что K(β) (β̃) = 1, K(β) (α̃) = 0. Затем возьмем дизъюнкциюконъюнкций K(β) и конъюнкции K. Если из полученной ДНФ и можно удалять конъюнкции, сохраняя при этом реализуемую функцию, тотолько отличные от K, так как это единственная конъюнкция, принимающая единичное значение на наборе α̃. В итоге получится ДНФтипа ΣT . Теорема доказана.Рассмотрим конъюнкцию K функции f и множество всех таких минимальных конъюнкций K ′ функции f , для которых существует наборβ̃K ′ такой, что K(β̃K ′ ) = 1 и K ′ (β̃K ′ ) = 1. Это множество конъюнкцийназывается окрестностью ранга 1 конъюнкции K.
Будем обозначать(1)эту 1–окрестность через UK .К примеру, для функции f = K1 ∨ K2 ∨ K3 , где K1 = x1 x2 ,K2 = x1 x3 , K3 = x2 x3 , K3 входит в 1–окрестность K1 , а в 1–окрестностьK3 входят K1 и K2 .Окрестность ранга r определим по индукции: допустим, определе(r−1)на UK , тогда[(r)(1)UK =UK ′ .(r−1)K ′ ∈UK(1)Так, если в последнем примере UK1 = {K1 , K3 }, то уже(2)UK1 = {K1 , K3 , K2 }.Возможна ситуация, когда на каждом новом шаге новых конъюнкций не появляется.
Для выяснения регулярности конъюнкции необхо8димо знать ее окрестность ранга 2 — это локальная процедура. А вотзадача о вхождении произвольной конъюнкции в сумму минимальныхконъюнкций нелокальна.Рассмотрим, например, функцию f (x1 , . . . , xn ) с множеством Nf вида цепиα̃0 = (0, 0, 0, . . . , 0, 0),α̃1 = (1, 0, 0, . . . , 0, 0),α̃2 = (1, 1, 0, . . . , 0, 0),···α̃n−1 = (1, 1, 1, . . . , 1, 0),α̃n = (1, 1, 1, .
. . , 1, 1).Тогда K1 = x2 x3 · · · xn , K2 = x1 x3 · · · xn , . . . , Kn = x1 x2 · · · xn−1 . Геометрическая интерпретация ДНФ представлена на рис. 2. Существует двевозможности в зависимости от четности n. Пусть n = 2m − 1. В этомслучае имеется только одна минимальная ДНФ, обслуживающая все2m наборов: она состоит из конъюнкций с нечетными номерами. Покажем, что любая ДНФ, содержащая конъюнкцию с четным номером,не будет минимальной.r K1 r K2 rα̃0α̃1···α̃2Рис. 2r Kn rα̃n−1 α̃nДопустим, что это не так, и конъюнкция K2t входит в минимальную ДНФ. Конъюнкция K2t обслуживает наборы α̃2t−1 и α̃2t .
Наборыα̃0 , . . . , α̃2t−2 , располагающиеся до них, обслуживаются2t − 1=t2конъюнкциями, а наборы α̃2t+1 , . . . , α̃2m−1 , располагающиеся после, обслуживаются2m − 2t − 1=m−t2конъюнкциями. Следовательно, всего конъюнкций в ДНФ будет покрайней мере t + (m − 1) + 1 = m + 1. А минимальная ДНФ содержитих ровно m. Противоречие.Но для выяснения вопроса четности n необходимо дойти до ближайшего конца ДНФ. Даже если рассматривать окрестности фиксированного ранга r, то n > 2r + 2, и так установить четность нельзя.Этим объясняется нелокальность данной задачи.9r(1, 0, 1, 0)(1, 1, 1, 0) ✟✟(0, 1, 0, 0) rr(0, 1, 1, 1)✟r✟❍✟✟ ❍❍❍❍✟✟kr✟❍E❍✟r(1, 1, 1, 1)(1, 1, 0, 0) ❍2✟❍✟❍❍ ✟✟❍r✟❍(1, 1, 0, 1) ❍❍r(1, 0, 0, 1)Рис.
3§ 1.3. Градиентный алгоритм построенияминимальной ДНФПусть Nf = {α̃0 , . . . , α̃s } и K1 , . . . , Kt — минимальные конъюнкции. Требуется минимизировать их количество. Построим матрицуA = (aij ) с t строками и s столбцами так, что aij = Ki (α̃j ). Выберемстроку матрицы A, которая содержит наибольшее число единиц. Пустьее номер i0 . Теперь вычеркнем из матрицы i0 –ю строку и столбцы, соответствующие наборам, обслуживающимся конъюнкцией Ki0 . К полученной матрице будем применять те же рассуждения пока возможно.Это один из так называемых жадных алгоритмов.Рассмотрим случай нерациональности градиентного алгоритма.
Нарис. 3 изображена ситуация, когда множество Nf представлено целиком k–мерным подкубом и еще несколькими наборами, ему не принадлежащими. Жадный градиентный алгоритм в первую очередь начнетобрабатывать подкуб, хотя понятно, что можно сразу включить в минимальную ДНФ конъюнкции, которые обслуживают наборы, не принадлежащие подкубу.§ 1.4. Монотонные функцииУстановим отношение порядка следующим образом:(α0 , . . .
, αn ) = α̃ 6 β̃ = (β1 , . . . , βn ),если αi 6 βi для каждого i = 1, n. Для любого набора α̃ справедливо0̃ 6 α̃ 6 1̃. Функция f (x1 , . . . , xn ) монотонна, если для всех таких наборов α̃ и β̃, что α̃ 6 β̃, выполнено f (α̃) 6 f (β̃). Будем рассматриватьмонотонные функции отличные от константы.10Утверждение 4. Всякая минимальная конъюнкция не содержитотрицаний переменных.Схема доказательства. Предположим, что xik входит в минимальную конъюнкцию xσi11 · · · xik · · · xσiss функции f . Тогда еслиα̃ = (σ1 , . .
. , 0, . . . , σs ), то f (α̃) = 1. Но α̃ 6 α̃′ = (σ1 , . . . , 1, . . . , σs ), значит f (α̃′ ) = 1, и конъюнкция xσi11 · · · xik · · · xσiss тоже допустима. Операσk−1 σk+1ция склеивания даст в результате xσi11 · · · xik−1xik+1 · · · xσiss . Если отрицания в конъюнкции еще остались, удалим их таким же образом.Утверждение 5. Всякая минимальная конъюнкция входит в ядрофункции.Доказательство. Пусть K = xi1 · · · xik — некоторая минимальнаяконъюнкция. Согласно предыдущему утверждению отрицаний в нейнет. Построим набор, на котором K принимала бы единичное значение,а все остальные минимальные конъюнкции — нулевое. Будем считать,что i1 < · · · < ik .
Пусть двоичный набор α̃ таков, что в нем все позиции, кроме i1 , . . . , ik нулевые. Тогда, естественно, K(α̃) = 1. Возьмемлюбую другую минимальную конъюнкцию K ′ = xj1 · · · xjs . Покажем,что среди переменных xj1 , . . ., xjs обязательно найдется не входящаяв xi1 , . . . , xik .
Это и будет означать, что K ′ (α̃) = 0. Предположим противное: все переменные xj1 , . . . , xjs входят в список xi1 , . . . , xik . Возможны два случая: либо эти наборы переменных просто совпадают,чего не может быть, так как K 6= K ′ , либо включение строгое, что также приводит к противоречию, поскольку в этом случае конъюнкциюK ′ можно получить из K удалением переменной, хотя K минимальна.Утверждение доказано.Таким образом, у монотонной функции сокращенная ДНФ (состоящая из всехминимальных конъюнкций) является единственной минимальной. (У линейнойфункции совершенная ДНФ есть одновременно и сокращенная, и минимальная.)11Глава 2Контактные схемы§ 2.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
