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

. . , y6 ):F (y) = (y6 ∨ y1 ) (y1 ∨ y2 ) (y2 ∨ y3 ) (y3 ∨ y4 ) (y4 ∨ y5 ) (y5 ∨ y6 ) .Раскрывая в этой КНФ скобки и приводя подобные, получим сокращенную ДНФ ФАЛ F (y) видаF (y) = y1 y3 y5 ∨ y2 y4 y6 ∨ y1 y2 y4 y5 ∨ y2 y3 y5 y6 ∨ y1 y3 y4 y6 ,слагаемые которой взаимно однозначно соответствуют тупиковым ДНФ ФАЛ g (см. (4.1), (4.2)).В общем случае при построении всех тупиковых ДНФФАЛ f , f ∈ P2 (n), с помощью леммы5.2 на основе ее сокращенной ДНФ используют, обычно, следующую модификацию рассмотренного выше подхода, которая позволяет уменьшать размеры матрицы M . Пусть NK1 , .

. . , NKq — все максимальные грани ФАЛ f , причем грани NKp+1 , . . . , NKt , где1 6 p 6 t 6 q, являются ядровыми, а грани NKt+1 , . . .. . . , NKq — регулярными гранями ФАЛ f , и пусть множеb состоит из всех ядровых и регулярных точек ФАЛство Nf . ПоложимbN = Nf \ N,N = {N1 , . . . , Np } ,b при всех i, i ∈ [1, p], и заметим, что задагде Ni = NKi \ Nча построения всех тупиковых ДНФ ФАЛ f эквивалентна44Введениезадаче выделения всех тупиковых подпокрытий из покрытия N множества N. Действительно, если система подмножеств Ni1 , .

. . , Nir , где 1 6 i1 < · · · < ir 6 p, является тупиковым покрытием множества N, то система максимальных граней NKi1 , . . . , NKir , NKp+1 , . . . , NKt задает тупиковоепокрытие множества Nf , то есть соответствует тупиковойДНФ ФАЛ f , и обратно.Так, применяя указанную модификацию к ФАЛ g 0 изP2 (4), показанной на рис. 3.1 (см. также (3.1) и (4.3)), получим тривиальную задачу о покрытии множества N == {(1000)} двумя совпадающими с ним подмножествами N1и N2 .§6Градиентный алгоритм и оценка длины градиентного покрытия.

Использование градиентного алгоритма для построения ДНФВыделение всех тупиковых подпокрытий из заданного покрытия и, в частности, построение всех тупиковых ДНФявляется трудоемкой задачей. В связи с этим, вместо того, чтобы строить все тупиковые ДНФ и выбирать срединих, например, кратчайшую, часто используют эвристические алгоритмы, позволяющие получать не очень «длинные» ДНФ. К числу таких алгоритмов относится и градиентный алгоритм, ориентированный на выделение из заданного покрытия достаточно «коротких» подпокрытий, или,иначе, на построение достаточно «коротких» покрытий длязаданной матрицы. На каждом шаге градиентного алгоритма в матрице выбирается и включается в покрытие такаястрока, которая покрывает наибольшее число еще не покрытых столбцов (если таких строк несколько, из них выбирается строка с наименьшим номером).

Алгоритм заканчиваетсвою работу после того шага, на котором получилось покрытие.Введение45Следующее утверждение дает верхнюю оценку длиныпокрытия, получаемого с помощью градиентного алгоритма для матриц с заданной «густотой».Теорема 6.1 ([6]). Пусть для действительного γ, 0<γ 61,в каждом столбце матрицы M, M ∈ B p,s , имеется неменьше, чем γ · p, единиц. Тогда покрытие матрицы M , получаемое с помощьюl градиентногоалгоритма, имеет длиm+111ну не больше, чем γ ln (γs) + γ .Доказательство. Пусть для построения покрытия матрицы M с помощью градиентного алгоритма потребовалосьсделать q шагов, причем на шаге с номером t, t ∈ [1, q], была выбрана строка с номером it .

Для каждого t, t ∈ [1, q),рассмотрим матрицу Mt , которая получается из матрицы Mв результате удаления строк с номерами {i1 , . . . , it }, а такжепокрываемых ими столбцов, и которая принадлежит множеству B pt ,st , где pt = p − t и st = s · δt , 0 6 δt 6 1. Для определенности будем считать, что M0 = M, p0 = p, s0 = s, δ0 = 1и pq = p−q, sq = δq = 0. Заметим, что при любом t, t ∈ [0, q],справедливо неравенствоq 6 t + δt · s,(6.1)так как после выполнения первых t шагов алгоритма остаются не покрытыми δt · s столбцов матрицы M , а на каждомследующем шаге покрывается не менее одного столбца.Заметим, далее, что в каждом столбце матрицы Mt , t ∈ [0, q),имеется не менее, чем γ · p, единиц и поэтому общее числоединиц в матрице Mt не меньше, чем γpsδt , а значит среднее число единиц в ее строках не меньше, чем γsδt . Отсюдавытекает, что строка матрицы M с номером it+1 , котораявыбирается на (t + 1)-м шаге алгоритма и является строкой матрицы Mt с наибольшим числом единиц, содержит не1Полагаем, что ln+ x = ln x, если x > 1, и ln+ x = 0, если 0 < x < 1.46Введениеменьше, чем γsδt , единиц, то есть покрывает не меньше, чемγsδt , еще не покрытых столбцов матрицы M .

Таким образом, для любого t, t ∈ [0, q), выполняются соотношенияsδt+1 = st+1 6 st − γsδt = sδt (1 − γ) ,из которых, с учетом δ0 = 1, следует, чтоδt 6 (1 − γ)t 6 e−γt(6.2)при любом t, t ∈ [0, q).Выбирая значение параметра t так, что1 +t=ln (γs) ,γподставляя его в (6.2) и учитывая (6.2), получимq6+1 +1 +1ln (γs) + s · e− ln (γs) 6ln (γs) + .γγγТеорема доказана.В качестве примера применения градиентного алгоритмарассмотрим задачу о «протыкании» граней куба его точками. Задача о «протыкании» системы N, состоящей из подмножеств N1 , N2 , .

. . , Np множества N = {α1 , . . . , αs }, заключается в нахождении такого подмножества множестваN, в котором при любом i, i ∈ [1, p], имеется хотя бы одинэлемент из Ni . Эта задача сводится к задаче о выделенииподпокрытия из покрытия отрезка [1, p] его подмножествами I1 , . . . , Is , где Ii = {j : αi ∈ Nj } при всех i, i ∈ [1, s].Заметим, что матрица построенной таким образом системыподмножеств отрезка [1, p] получается из матрицы системы(N, N) в результате транспонирования.Введение47Лемма 6.1 ([19]).

При любых натуральных n и m, m 6 n,в кубе B n всегда найдется подмножество мощности не более, чем n · 2m , протыкающее все грани ранга m.Доказательство. Применяя указанный выше подход, рассмотрим множествосостоящее из всех граней ранга m N,n· 2m , а также систему N = {Nα }α∈B n егокуба B n , |N| = mподмножеств, где Nα — множество тех граней из N, которые проходят через точку α.

Очевидно, что каждая граньиз N содержится в тех 2n−m подмножествах Nα , для которых точка α принадлежит этой грани. Следовательно, матрица M ,связанная с парой (N, N), состоит из p = 2n строкnиs= m· 2m столбцов, в каждом из которых имеется p · γ,−mгде γ = 2 , единиц. Искомое множество наборов получается в результате применения к матрице M теоремы 6.1 ипостроения покрытия длины q, где nnmm+ 2 6 2 log+ 2m 6q 6 2 lnmm6 2m (n − 1) + 2m = n · 2m .m+Лемма доказана.§7Задача минимизации ДНФ. Поведение функций Шеннона и оценки типичных значенийдля ранга и длины ДНФКак уже отмечалось, ДНФ представляет собой удобную инаглядную (с «геометрической» точки зрения) форму задания ФАЛ.

С другой стороны, ДНФ можно рассматриватькак простейшую модель, предназначенную для структурнойреализации ФАЛ (см. гл. 3).Заметим, что различные параметры ДНФ (ранг, длина и т. п) характеризуют различные48Введение«меры» сложности указанного представления или структурной реализации. В связи с этим часто возникает необходимость построения оптимальной в том или ином смысле ДНФдля заданной ФАЛ, то есть необходимость решения соответствующей задачи минимизации ДНФ, которая являетсячастным случаем задачи синтеза управляющих систем (см.гл. 3).В общем виде задача минимизации ДНФ может бытьсформулирована следующим образом. Пусть для каждойДНФ A определена ее «сложность» ψ (A), ψ (A) > 0, длякоторой ψ (A0 ) > ψ (A00 ), если ДНФ A00 получается из ДНФA0 удалением букв или ЭК.

В этом случае будем говорить,что на множестве ДНФ задан неотрицательный функционалсложности ψ, обладающий свойством монотонности. Примерами таких функционалов могут служить длина λ (A),ранг R (A) или «формульная» сложность L (A) ДНФ A, атакже число вхождений БП с отрицаниями и другие параметры ДНФ. Задача минимизации ДНФ относительно функционала сложности ψ состоит в том, чтобы по заданнойФАЛ f построить реализующую ее ДНФ A такую, чтоψ (A) = min ψ A0 ,где минимум берется по всем ДНФ A0 , реализующим ФАЛ f .При этом ДНФ A считается минимальной относительнофункционала ψ, или, иначе, ψ-минимальной ДНФ, а значение ψ (A) называется сложностью ФАЛ f относительнофункционала ψ, или, иначе, ψ-сложностью ФАЛ f в классеДНФ.

В соответствии с введенными ранее определениями,λ-минимальную ДНФ, то есть ДНФ минимальную по длине,будем называть кратчайшей, а R-минимальную ДНФ, тоесть ДНФ минимальную по рангу, — просто минимальной.Функциюψ (n) = max ψ (f ) ,f ∈P2 (n)Введение49которая характеризует максимальное значение ψ-сложностиФАЛ из P2 (n), называют, обычно, функцией Шеннона длякласса ДНФ относительно функционала ψ.Установим поведение функций Шеннона λ(n) и R(n) длядлины и ранга ДНФ ФАЛ из P2 (n) соответственно.Лемма 7.1. Для любого n, n ∈ N, имеют место соотношенияλ(n) = 2n−1 , R(n) = n · 2n−1 .(7.1)Доказательство.

Нижние оценки (7.1) следуют из того,чтоλ(ln ) = 2n−1 и R(ln ) = n · 2n−1 , так как единственной ДНФлинейной ФАЛ ln = x1 ⊕ · · · ⊕ xn является ее совершенная ДНФ. Для получения требуемых в (7.1) верхних оценоквозьмем произвольную ФАЛ f из P2 (n) и, в соответствии с(2.5), разложим ее по БП x2 , . . . , xn следующим образом:_f (x1 , .