OK_metodichka_part_1 (1132796), страница 4
Текст из файла (страница 4)
. ∪ N6 , где Ni = NKiпри всех i = 1, . . . , 6 (см. рис. 2.1a). Заметим, что совершенные ДНФ и КНФ ФАЛ f из (2.4) задают покрытие множеств Nf и N f соответственно гранями размерности 0. Принимая во внимание указанную выше геометрическую интерпретацию, мы не будем в дальнейшем делать существенныхразличий между ЭК Ki и соответствующей ей гранью NKi ,а также между ДНФ вида (2.6) и соответствующим ей покрытием (2.7).Рассмотрим теперь некоторые специальные виды ДНФ иих «геометрическую» интерпретацию.
Будем говорить, чтоФАЛ f 0 имплицирует ФАЛ f 00 , или, иначе, ФАЛ f 00 поглощает ФАЛ f 0 , если Nf 0 ⊆ Nf 00 , то есть импликация(f 0 → f 00 ) тождественно равна 1. Элементарная конъюнкция, которая имплицирует ФАЛ f , называется импликантой этой ФАЛ. Заметим, что отношение имплицируемостиявляется отношением частичного порядка и что f 0 имплицирует f 00 тогда и только тогда, когда f 00 = f 0 ∨ f 00 илиf 0 = f 0 · f 00 . Отсюда следует, в частности, что ЭК K 0 имплицирует ЭК K 00 тогда и только тогда, когда множество буквK 00 содержится во множестве букв K 0 , то есть K 0 = K 00 · Kдля некоторой ЭК K, не имеющей общих букв с ЭК K 00 . Этоозначает, что в данном случае ЭК K 0 может быть «устранена» из ДНФ K 00 ∨ K 0 с помощью тождества поглощения(2.3).Дизъюнктивную нормальную форму A вида (2.6) будемназывать неприводимой, если соответствующее ей покрытиеявляется неприводимым (см.
§1), то есть ни одна из гранейNK1 , . . . , NKs не содержится ни в одной из других гранейпокрытия (2.8). На «языке имплицируемости» это означает,что ни одна из ЭК Ki , i ∈ [1, s], не является импликантойЭК Kj , где j ∈ [1, s] и i 6= j. Заметим, что с помощью тождества поглощения (2.3) из любой ДНФ A можно получитьbнеприводимую ДНФ A.§2. Представление ФАЛ с помощью ДНФ25Импликанта K ФАЛ f называется простой импликантой этой ФАЛ, если она не поглощается никакой другойотличной от нее импликантой ФАЛ f . Из определений и отмеченных выше фактов следует, что в простую импликантуФАЛ f не входят буквы несущественных БП этой ФАЛ и чтоиз любой импликанты ФАЛ f можно получить ее простуюимпликанту удалением некоторых букв.
Последнее означает, что любая импликанта ФАЛ f имплицирует некоторуюпростую импликанту f . С «геометрической» точки зренияпростые импликанты ФАЛ f соответствуют максимальнымпо включению граням множества Nf .Будем говорить, что ДНФ A, реализующая ФАЛ f , является тупиковой ДНФ, если f 6= A0 для любой ДНФ A0 ,полученной из A в результате удаления некоторых букв илицелых ЭК.
Из определения вытекает, что в тупиковую ДНФA ФАЛ f могут входить только простые импликанты этойФАЛ, и что A является неприводимой ДНФ. С «геометрической» точки зрения тупиковая ДНФ A ФАЛ f задает тупиковое (см. §1) покрытие множества Nf максимальнымигранями ФАЛ f и обратно.Построение всех или некоторых тупиковых ДНФ для заданной ФАЛ f является, обычно, промежуточным этапомпри построении минимальной (кратчайшей) ДНФ ФАЛ f ,то есть ДНФ, которая имеет минимальный ранг (соответственно длину) среди всех ДНФ, реализующих f . Это связано с тем, что минимальная ДНФ обязательно являетсятупиковой, а среди кратчайших ДНФ всегда есть тупиковая.При построении тупиковых ДНФ ФАЛ f бывает полезнознать ДНФ пересечение тупиковых (ДНФ ∩T ) ФАЛ f , тоесть дизъюнкцию всех тех различных простых импликантэтой ФАЛ, которые входят в любую тупиковую ДНФ ФАЛf.Набор α, α ∈ B n , называется ядровой точкой ФАЛ f (x1 , .
. . , xn ),26Глава 1. Дизъюнктивные нормальные формыесли α ∈ Nf и α входит только в одну максимальную граньФАЛ f . При этом грань NK , являющаяся максимальнойгранью ФАЛ f и содержащая точку α, считается ядровойгранью ФАЛ f , а совокупность всех различных ядровых граней ФАЛ f называется ядром ФАЛ f .Лемма 2.1. Дизъюнктивная нормальная форма ∩T ФАЛf состоит из тех простых импликант ФАЛ f , которыесоответствуют ядровым граням этой ФАЛ.Доказательство.
Пусть тупиковая ДНФ A ФАЛ f (x1 , . . . , xn )не включает в себя простую импликанту K, которая соответствует ядровой грани NK ФАЛ f , содержащей ядровуюточку α этой ФАЛ. Поскольку все отличные от K простыеимпликанты ФАЛ f обращаются в 0 на наборе α, то ДНФA также будет равна 0 на этом наборе и, следовательно,f (α) = 0. Полученное противоречие с тем, что α ∈ Nf , доказывает необходимость включения ЭК K в любую тупиковую ДНФ ФАЛ f .Пусть теперь простая импликанта K ФАЛ f соответствует грани NK , которая не входит в ядро ФАЛ f . При этомкаждая точка грани NK покрывается хотя бы одной отличной от NK максимальной гранью ФАЛ f . Следовательно,все отличные от NK максимальные грани ФАЛ f образуют покрытие множества Nf , из которого можно выделитьтупиковое подпокрытие, соответствующее тупиковой ДНФФАЛ f , не содержащей ЭК K.Лемма доказана.§3Сокращенная ДНФ и способы ее построенияДизъюнкция всех простых импликант ФАЛ f называется еесокращенной ДНФ.
Заметим, что сокращенная ДНФ ФАЛf является неприводимой ДНФ и что ей соответствует покрытие множества Nf всеми максимальными по включению§3. Сокращенная ДНФ и способы ее построения27гранями множества Nf этой ФАЛ. Указанное соответствиепозволяет строить сокращенную ДНФ на основе «геометрических» соображений. Так, в соответствии с рис. 2.1 праваячасть (2.10) является сокращенной ДНФ ФАЛ g, а из рис.3.1a вытекает, что сокращенная ДНФ ФАЛ g 0 (x1 , x2 , x3 , x4 ),для которой αeg0 = (1111 1011 1101 1010), имеет видg 0 = K10 ∨ . . .
∨ K70 ,(3.1)где K10 = x3 x4 , K20 = x2 x3 , K30 = x2 x4 , K40 = x1 x3 , K50 == x2 x4 , K60 = x1 x4 , K70 = x1 x2 , причем ЭК Ki0 , i = 1, . . . , 7,соответствует грани Ni0 = NKi0 на рис. 3.1a. На рис. 3.1bприведена для наглядности «развертка» множества Ng0 исоставляющих его максимальных граней указанной ФАЛ g 0 .Легко видеть, что сокращенная ДНФ ЭК или ЭД совпадаетс ней самой.Чтобы сделать построение сокращенной ДНФ для ФАЛf, f ∈ P2 (n), более наглядным, часто используют ее представление в виде карты Карно, то есть в виде таблицы Π2,2 (f ),в которой наборы (10) и (11) переставлены, а противоположные стороны отождествлены по типу «тора». Заметим, чтолюбое ребро куба B 4 соответствует двум соседним клеткамуказанной таблицы, а любой квадрат в B 4 — либо квадрату,составленному из четырех соседних клеток таблицы, либоее строке или столбцу. На рис.
3.2 приведена карта Карно ФАЛ g 0 (x1 , x2 , x3 , x4 ) и указаны все максимальные граниэтой ФАЛ.Теорема 3.1. Пусть A0 и A00 — сокращенные ДНФ ФАЛf 0 и f 00 соответственно, а неприводимая ДНФ A получается из формулы A0 · A00 в результате раскрытия скобоки приведения подобных. Тогда A — сокращенная ДНФ ФАЛf = f 0 · f 00 .Доказательство.
Достаточно доказать, что в A входит любая простая импликанта ФАЛ f . Пусть ЭК K является про-28Глава 1. Дизъюнктивные нормальные формы1`@@e@@ β4β0β53 `c N@`c3`cN50 ` @ @@@ @ N40@ @@@@0 α6N@α1`c `@@`cN70 @2 `c α2`c`N60@α7@@@@@ @ N10 @@@ @@α@5@`c@`c`c @`cα4β0@ α3@@ x x2 3 x4 x@11@I 6@`c e0a)β` 3 = (1011)N30α3 ` = (0001)α2 = (1001) `N70N20β0 = (1000) ``N10α1 = (1100) `α0 = e0`α7 = (0011)N40` α4 = (0010) `β4 = (0111)N60`α5 = (0100)N50`β5 = (1110)` α6 = (0110)b)Рис. 3.1: «геометрия» сокращенной ДНФ ФАЛ g 0§3.
Сокращенная ДНФ и способы ее построенияРис. 3.2: карта Карно ФАЛ g 02930Глава 1. Дизъюнктивные нормальные формыстой импликантой ФАЛ f и, следовательно, является импликантой как ФАЛ f 0 , так и ФАЛ f 00 . Из свойств сокращенных ДНФ вытекает, что в A0 и A00 найдутся ЭК K 0 и K 00соответственно, которые имплицируются ЭК K. Таким обeразом, в ДНФ A войдет имплицируемая ФАЛ K 0 · K 00 ЭК K,которая получится в результате раскрытия скобок и приведения подобных в формуле A0 · A00 .
Заметим, что при этомЭК K имплицирует ФАЛ K 0 ·K 00 и, следовательно, имплициe Поскольку ЭК Ke является импликантой ФАЛ fрует ЭК K.e = K, так каки, одновременно, имплицируется ЭК K, то KK — простая импликанта ФАЛ f .Теорема доказана.Следствие. Если неприводимая ДНФ A получается из КНФB ФАЛ f в результате раскрытия скобок и приведения подобных, то A — сокращенная ДНФ ФАЛ f .Применяя следствие из теоремы 3.1 к ФАЛ g 0 , показанной на рис. 3.1-3.2, получим (сравните с (3.1))D = (x1 ∨ x2 ∨ x4 )·(x1 ∨ x2 ∨ x3 ∨ x4 )·(x1 ∨ x2 ∨ x3 ∨ x4 ) == (x2 ∨ x4 ∨ x1 x3 ) · (x1 ∨ x2 ∨ x3 ∨ x4 ) == x3 x4 ∨ x1 x4 ∨ x1 x2 ∨ x2 x3 ∨ x2 x4 ∨ x1 x3 ∨ x2 x4 .Следующий метод (метод Блейка [6]) позволяет получать сокращенную ДНФ ФАЛ f из произвольной ДНФ этойФАЛ с помощью эквивалентных преобразований на основетождества обобщенного склеивания:x1 x2 ∨ x1 x3 = x1 x2 ∨ x1 x3 ∨ x2 x3 .Любая ДНФ A0 , которую можно получить из ДНФ Aпутем формирования в ней с помощью тождеств ассоциативности и коммутативности подформул вида xi K 0 ∨ xi K 00 ,§3.
Сокращенная ДНФ и способы ее построения31применения к этим подформулам тождества обобщенногосклеиванияxi K 0 ∨ xi K 00 = xi K 0 ∨ xi K 00 ∨ K 0 K 00(3.2)и последующего приведения подобных, называется расширением ДНФ A. Расширение A0 ДНФ A считается строгим, если A0 содержит ЭК, не являющуюся импликантой ни однойЭК из A. Заметим, что сокращенная ДНФ не имеет строгихрасширений и что в результате построения последовательных строгих расширений и приведения подобных из любойДНФ можно получить неприводимую ДНФ, которая не имеет строгих расширений.Теорема 3.2. Неприводимая ДНФ является сокращеннойДНФ тогда и только тогда, когда она не имеет строгихрасширений.Доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
