1 (С.А. Ложкин - Лекции по основам кибернетики (2017)), страница 6
Описание файла
Файл "1" внутри архива находится в папке "С.А. Ложкин - Лекции по основам кибернетики (2017)". PDF-файл из архива "С.А. Ложкин - Лекции по основам кибернетики (2017)", который расположен в категории "". Всё это находится в предмете "основы кибернетики" из 6 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 6 страницы из PDF
. . , xn ) линейно зависит отБП xi , или, иначе, что БП xi является линейной БП ФАЛf , если f (α) 6= f (β) для любых соседних по БП xi наборовα и β куба B n . При этом для ФАЛ f имеет место равенствоf (x1 , . . . , xn ) = xi ⊕ f (x1 , . . . , xi−1 , 0, xi+1 , .
. . , xn ) ,которое равносильно линейности БП xi ФАЛ f , а значитФАЛ является линейной тогда и только тогда, когда оналинейно зависит от всех своих существенных БП.Заметим, что если ФАЛ f линейно зависит от БП xi , тов любую импликанту этой ФАЛ входит одна из букв xi , xi .Рассмотрим далее класс монотонных ФАЛ и некоторыесвязанные с ним другие классы функций. Напомним, чтоФАЛ f (x1 , . . . , xn ) называется монотонной, если f (α) 6 f (β)для любых наборов α и β куба B n таких, что α 6 β. Будемговорить, что ФАЛ f (x1 , . . .
, xn ) монотонно зависит отБП xi , или, иначе, БП xi является монотонной БП ФАЛf , если неравенство f (α) 6 f (β) выполняется для любыхсоседних по БП xi наборов α и β куба B n таких, что α 6 β.Легко видеть, что монотонная ФАЛ монотонно зависит отвсех своих БП и обратно.Докажем, что если ФАЛ f (x1 , . . . , xn ) монотонно зависит от БП xi , то ни одна из ее простых импликант не может содержать букву xi . Действительно, пусть импликанта38Введение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) может быть представлена в указанном виде. Легко видеть также, что грань, соответствую-Введение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ВведениеПусть 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), для которойВведение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Введениепокрытие матрицы 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) указанным выше способомВведение43сопоставим таблицу Квайна1 10 10 0M =0 00 01 0011000001100000110000,011ФАЛ покрытия которой в соответствии с (5.1) задается следующей КНФ от переменных y = (y1 , .