ОК_Часть_1_2015 (С.А. Ложкин - Лекции по основам кибернетики (2015)), страница 6

, xn ) монотонно зависит от БП xi , то ни одна из ее простых импликант не может содержать букву xi . Действительно, пусть импликанта38Глава 1. Дизъюнктивные нормальные формыK 0 ФАЛ f содержит букву xi и, следовательно, для граниNK 0 = Γγ 0 , где γ 0 ∈ ([0, 2])n и γ 0 hii = 0, имеет место включение NK 0 ⊆ Nf . Тогда, в силу монотонной зависимости ФАЛf от БП xi , имеют место включенияNK 00 = Γγ 00 ⊆ Nfи NK = Γγ = NK 0 ∪ NK 00 ⊆ Nf ,где набор γ 00 (набор γ) получается из набора γ 0 заменой 0 в iом разряде на 1 (соответственно 2). Последнее из этих включений означает, что ЭК не является простой импликантойФАЛ f , то есть простая импликанта монотонной по БП xiФАЛ не может содержать буквы xi .

Отсюда следует, что любая простая импликанта отличной от 0 монотонной ФАЛ является монотонной ЭК, то есть не содержит отрицаний БП.Частным случаем монотонной зависимости ФАЛ f отБП xi является конъюнктивная (дизъюнктивная) зависимость f от xi , когда f = xi · g (соответственно f = xi ∨ g),где ФАЛ g получается из f подстановкой константы 1 (соответственно 0) вместо БП xi .

При этом в случае конъюнктивной зависимости буква xi входит в любую импликантуФАЛ f , а в случае дизъюнктивной зависимости буква xiне входит ни в одну простую импликанту ФАЛ f отличнуюот xi . Будем говорить, что ФАЛ f (x1 , . . . , xn ) инмонотонно(инконъюнктивно, индизъюнктивно) зависит от БП xi , еслиФАЛ f (x1 , . . . , xi−1 , xi , xi+1 , .

. . , xn ) зависит от xi монотонно(соответственно конъюнктивно, дизъюнктивно). Очевидно,что все особенности ДНФ, характерные для ФАЛ с той илииной монотонной зависимостью от БП распространяются наФАЛ с аналогичной инмонотонной зависимостью после инвертирования соответствующих БП.Сопоставим каждому набору β из B n , монотонную ЭК+Kβ от БП X (n), состоящую из тех и только тех букв xj ,j ∈ [1, n], для которых β hji = 1, и заметим, что каждая монотонная ЭК от БП X (n) может быть представлена в указанном виде. Легко видеть также, что грань, соответствую-§5. Построение всех тупиковых ДНФ39щая ЭК Kβ+ , где β = (β1 , .

. . , βn ) ∈ B n , имеет вид Γγ , гдеγ = (2 − β1 , . . . , 2 − βn ). Набор α, α ∈ B n , называется нижней единицей монотонной ФАЛ f , f ∈ P2 (n), если α ∈ Nfи f (β) = 0 для любого отличного от α набора β такого, чтоβ 6 α. Множество всех нижних единиц монотонной ФАЛ fбудем обозначать через Nf+ .В силу введенных определений, Kβ+ (α) = 1 тогда и только тогда, когда α > β, откуда следует, что набор β являетсяединственной нижней единицей ЭК Kβ+ и что ЭК Kβ+0 имплицирует ЭК Kβ+00 тогда и только тогда, когда β 0 > β 00 .Отсюда вытекает также, что ЭК Kβ+ является простой импликантой монотонной ФАЛ f тогда и только тогда, когдаβ ∈ Nf+ , и что набор β является при этом ядровой точкойФАЛ f . Таким образом, доказано следующее утверждение.Лемма 5.1. Сокращенная ДНФ A монотонной ФАЛ f , f ∈ P2 (n),является единственной тупиковой ДНФ этой ФАЛ и имеет вид:_A (x1 , .

. . , xn ) =Kβ+ (x1 , . . . , xn ) .β∈Nf+При этом все наборы из Nf+ являются ядровыми точкамиФАЛ f .Следствие. Монотонная ФАЛ является ядровой ФАЛ.Напомним, что с «геометрической» точки зрения, сокращенная ДНФ ФАЛ f из P2 (n) представляет собой покрытиемножества Nf всеми максимальными гранями, а тупиковаяДНФ соответствует тупиковому подпокрытию, выделяемому из этого покрытия. Рассмотрим сначала метод выделения из заданного покрытия конечного множества всех еготупиковых подпокрытий, основанный на построении сокращенной ДНФ для специальной монотонной ФАЛ, связаннойс исходным покрытием.40Глава 1. Дизъюнктивные нормальные формыПусть N = {α1 , .

. . , αs } — конечное множество, а N == (N1 , . . . , Np ) — система его подмножеств, образующих покрытие множества N. Сопоставим паре (N, N) матрицу M, M ∈B p,s , для которой M hi, ji = 1 тогда и только тогда, когдаNi 3 αj . Заметим, что матрица M не имеет нулевых столбцов, так как система N образует покрытие множества N.Будем считать, что i-я строка (j-й столбец) матрицы M соответствует подмножеству Ni системы N (элементу αj множества N) и не будем делать между ними существенныхразличий. Так, будем говорить, что i-я строка матрицы Mпокрывает ее j-й столбец, если M hi, ji = 1, то есть Ni 3 αj ,и что система строк с номерами из I, I ⊆ [1, p], образуетпокрытие матрицы M , если каждый ее столбец покрывается хотя бы одной строкой с номером из I, то есть системаподмножеств {Ni }i∈I задает покрытие множества N.

Аналогичным образом понимается покрытие одного множествастрок матрицы M другим множеством ее строк и т. п.Покрытие матрицы M , в котором ни одна строка не покрывается другой строкой, считается неприводимым, а покрытие, не имеющее собственных подпокрытий, называется тупиковым и т. п. Заметим, что задача выделения всехтупиковых подпокрытий из покрытия N множества N эквивалентна задаче построения всех тупиковых покрытий матрицы M , соответствующей паре (N, N). Для решения этойзадачи по аналогии с ДНФ можно ввести понятие ядрового и регулярного столбцов, а также ядровой и регулярнойстроки, для которых будут справедливы утверждения, аналогичные лемме 4.1 и теореме 4.1.Пусть M, M ∈ B p,s — матрица без нулевых столбцов.Сопоставим i-й строке, i ∈ [1, p], матрицы M БП yi , а каждому набору β, β ∈ B p , значений этих переменных y =(y1 , .

. . , yp ), — множество строк матрицы M с номерами измножества I = I (β) ⊆ [1, p], где i ∈ I (β) тогда и толькотогда, когда β hii = 1. Рассмотрим ФАЛ F (y), для которой§5. Построение всех тупиковых ДНФ41F (β) = 1 тогда и только тогда, когда система строк матрицы M с номерами из I (β) образует ее покрытие, и будемназывать эту ФАЛ функцией покрытия матрицы M . Заметим, что ФАЛ покрытия F (y) является монотонной ФАЛ, аее «нижние единицы» соответствуют тупиковым покрытиямматрицы M .

Действительно, из неравенства β 0 6 β 00 вытекает, что I (β 0 ) ⊆ I (β 00 ) и потому F (β 0 ) 6 F (β 00 ), то есть ФАЛF является монотонной. Из определений следует также, чтонабор β, β ∈ B p , являющийся «нижней единицей» ФАЛ F ,соответствует множеству I (β), которое задает тупиковое покрытие матрицы M , и обратно.

Таким образом, в силу леммы 5.1, каждая простая импликанта вида K = yi1 yi2 · · · yir ,где 1 6 i1 < · · · < ir 6 p, ФАЛ покрытия F (y) соответствует тупиковому покрытию матрицы M , состоящему из строкс номерами из множества I = {i1 , . . . , ir }, и обратно.Лемма 5.2. Функция покрытия F (y1 , . . . , yp ) матрицы M, M ∈B p,s , без нулевых столбцов задается КНФ вида:F (y1 , . . . , yp ) =s ^j=1_yi .(5.1)16i6pM hi,ji=1Доказательство. Для каждого j, j ∈ [1, s], положимJj (y) =_yi ,16i6pM hi,ji=1где y = (y1 , .

. . , yp ). Легко видеть, что Jj (β) = 1 для произвольного набора β, β ∈ B p , тогда и только тогда, когдамножество строк с номерами из I (β) покрывает j-й столбецматрицы M, j ∈ [1, s]. Отсюда следует, что КНФ в правой части (5.1) обращается в 1 на наборе β тогда и толькотогда, когда множество строк с номерами из I(β) образует42Глава 1.

Дизъюнктивные нормальные формыпокрытие матрицы M , то есть тогда и только тогда, когдаF (β) = 1.Лемма доказана.Следствие. В результате раскрытия скобок и приведения подобных из КНФ (5.1) можно получить сокращеннуюДНФ ФАЛ F (y), простые импликанты которой взаимнооднозначно соответствуют тупиковым покрытиям матрицы M .Задача построения всех тупиковых ДНФ ФАЛ f из P2 (n)на основе ее сокращенной ДНФ сводится к рассмотреннойвыше задаче о покрытии, если в качестве множества N взятьмножество Nf , а в качестве его покрытия N — систему всехмаксимальных граней ФАЛ f .

Матрица M , соответствующая указанной паре (N, N), называется, обычно, таблицейКвайна ФАЛ f . Заметим, что ядровой столбец (строка) таблицы Квайна связан с ядровой точкой (соответственно гранью) ФАЛ f , что регулярный столбец (строка) этой таблицы задает регулярную точку (соответственно грань) ФАЛ f ,что строка, покрываемая ядровыми строками, соответствует грани, покрываемой ядром и т. п.Рассмотрим, для примера, задачу построения всех тупиковых ДНФ для ФАЛ g (x1 , x2 , x3 ) из ее сокращенной ДНФ,полагая (см. рис. 2.1a, (2.10), (4.1) и (4.2)), чтоNg = {α1 = (100) , α2 = (110) , α3 = (010) ,α4 = (011) , α5 = (001) , α6 = (101)},N = {N1 , . .

. , N6 } ,где Ni = NKi = {αi , αi+1 } для всех i, i ∈ [1, 6], причемα7 = α1 = (100). Паре (Ng , N) указанным выше способом§5. Построение всех тупиковых ДНФсопоставим таблицу Квайна1 10 10 0M =0 00 01 001100000110000011043000,011ФАЛ покрытия которой в соответствии с (5.1) задается следующей КНФ от переменных y = (y1 , . . . , 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 .