оки1 (1155744), страница 5
Текст из файла (страница 5)
Таким образом, ЭК kявляется импликантой некоторой ЭК из A и не может входить в K. Полученное противоречие доказывает, что ЭК Kвходит в A.Теорема доказана.Следствие. Из любой ДНФ A ФАЛ f можно получить сокращенную ДНФ этой ФАЛ в результате построения последовательных строгих расширений и приведения подобных до получения ДНФ без поглощений ЭК, не имеющейстрогих расширений.Возьмем для примера в качестве ДНФ A совершеннуюДНФ ФАЛ голосования H (x1 , x2 , x3 ), которая имеет видA (x1 , x2 , x3 ) = x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 .Применяя к A метод Блейка, получим:A = (x1 x2 x3 ∨ x1 x2 x3 ) ∨ x1 x2 x3 ∨ x1 x2 x3 == x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 = (x2 x3 ∨ x2 x1 x3 ) ∨ x1 x2 x3 == x2 x3 ∨ x1 x3 ∨ x1 x2 x3 = x2 x3 ∨ (x3 x1 ∨ x3 x1 x2 ) == x2 x3 ∨ x1 x3 ∨ x1 x2 . (3.3)§4.
Тупиковые и минимальные ДНФ§431Тупиковые ДНФ, ядро и ДНФ пересечениетупиковых. ДНФ Квайна и ДНФ сумма тупиковых, критерий вхождения простых импликант в тупиковые ДНФ, его локальностьБудем говорить, что ДНФ 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 ),если α ∈ Nf и α входит только в одну максимальную граньФАЛ f . При этом грань NK , являющаяся максимальнойгранью ФАЛ f и содержащая точку α, считается ядровойгранью ФАЛ f , а совокупность всех различных ядровых граней ФАЛ f называется ядром ФАЛ f .32Глава 1. Дизъюнктивные нормальные формыЛемма 4.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.3)для ФАЛ «голосования» H (x1 , x2 , x3 ) является единственной тупиковой ДНФ этой ФАЛ, ФАЛ g (x1 , x2 , x3 ) (см. рис.2.1a и (2.10)) имеет пять тупиковых ДНФ —A1 = K1 ∨ K3 ∨ K5 ,A3 = K1 ∨ K2 ∨K4 ∨ K5 ,A2 = K2 ∨ K4 ∨ K6 ,A4 = K2 ∨ K3 ∨ K5 ∨ K6 ,A5 = K3 ∨ K4 ∨ K6 ∨ K1 ,(4.1)(4.2)§4. Тупиковые и минимальные ДНФ33а у ФАЛ g 0 (x1 , x2 , x3 , x4 ) (см. рис. 3.1-3.2 и (3.1)) имеютсядве тупиковые ДНФ —A01 = K10 ∨ K30 ∨ K40 ∨ K50 ,A02 = K20 ∨ K30 ∨ K40 ∨ K50 . (4.3)При этом ДНФ A1 , A2 в (4.1) и ДНФ A01 , A02 в (4.3) являются минимальными и, одновременно, кратчайшими ДНФФАЛ g и ФАЛ g 0 соответственно.При построении тупиковых ДНФ ФАЛ f наряду с ДНФпересечение тупиковых полезно знать ДНФ сумма тупиковых (ДНФ ΣT ) ФАЛ f , то есть дизъюнкцию всех тех различных простых импликант этой ФАЛ, которые входят вхотя бы в одну тупиковую ДНФ ФАЛ f .
Заметим, что ДНФ∩T ФАЛ f в общем случае не реализует саму ФАЛ f , а внекоторых случаях и, в частности, в случае ФАЛ g (см. выше), может быть пустой. В то же время ДНФ ΣT ФАЛ fвсегда реализует эту ФАЛ, содержится в ее сокращенной иможет с ней совпадать, как это имеет место в случае ФАЛg или в случае ФАЛ «голосования».Будем называть ФАЛ ядровой, если все ее максимальные грани являются ядровыми.
Из леммы 4.1 следует, чтосокращенная ДНФ ядровой ФАЛ является ее единственнойтупиковой ДНФ. Примером ядровой ФАЛ является ФАЛголосования (3.3) (см. также §6).Дизъюнктивная нормальная форма, получающаяся изсокращенной ДНФ ФАЛ f удалением тех ЭК K, для которых грань NK покрывается ядром ФАЛ f , но не входит внего, называется ДНФ Квайна этой ФАЛ. Из определенийследует, что ДНФ Квайна ФАЛ f включает в себя ДНФ ΣTэтой ФАЛ и содержится в ее сокращенной ДНФ. Заметим,что для ФАЛ g 00 (x1 , x2 , x3 ), показанной на рис. 4.1, ее сокращенная ДНФ имеет вид g 00 = x2 x3 ∨ x1 x2 ∨ x1 x3 , то естьотличается от ДНФ Квайна, которая является единственнойтупиковой ДНФ этой ФАЛ и имеет вид g 00 = x2 x3 ∨ x1 x3 .
В34Глава 1. Дизъюнктивные нормальные формы(111)`@@`c`@c`@@@@`@`c@`c@ x2x3x@1@I`@6(000)Рис. 4.1: «геометрия» сокращенной ДНФ ФАЛ g 00то же время для ФАЛ g 0 , показанной на рис. 3.1, ДНФ Квайна совпадает с сокращенной ДНФ этой ФАЛ и отличаетсяот ее ДНФ ΣT , которая (см. выше) равнаK10 ∨ K20 ∨ K30 ∨ K40 ∨ K50 .Для ФАЛ f (x1 , . .
. , xn ) и набора α, α ∈ Nf , обозначимчерез Πα (f ) множество всех проходящих через α максимальных граней ФАЛ f , которое мы будем называть пучкомФАЛ f через точку α. Точку α, α ∈ Nf , будем называть регулярной точкой ФАЛ f , если найдется точка β, β ∈ Nf ,для которой имеет место строгое включение Πβ (f ) ⊂ Πα (f ).Указанное включение означает, что любая максимальнаягрань ФАЛ f , проходящая через точку β, проходит и черезточку α, причем есть такая максимальная грань ФАЛ f , которая проходит через точку α, но не проходит через точкуβ. Легко видеть, что для любой регулярной точки α ФАЛf всегда найдется такая нерегулярная точка β, β ∈ Nf , длякоторой Πβ (f ) ⊂ Πα (f ).Из определений следует, что любая неядровая точка ядровой грани регулярна, и поэтому точки αi , i ∈ [1, 7], ФАЛg 0 , показанной на рис. 3.1, являются ее регулярными точка-§4.
Тупиковые и минимальные ДНФ35ми. Кроме того, в силу включения Πβ0 (g 0 ) ⊂ Πα0 (g 0 ), точкаα0 тоже является регулярной точкой этой ФАЛ.Грань NK ФАЛ f называется регулярной гранью этойФАЛ, если все точки NK регулярны. Заметим, что грань,которая не входит в ядро, но покрывается им, является регулярной. Заметим также, что для ФАЛ g 0 , показанной нарис. 3.1, грани N60 и N70 , которые не входят в ДНФ ΣT , являются регулярными, так как состоят из регулярных точек.Теорема 4.1 (ср. [28, 6, 23, 10]). Простая импликанта KФАЛ f входит в ДНФ ΣT тогда и только тогда, когдагрань NK не является регулярной гранью этой ФАЛ.Доказательство.
Пусть α1 , . . . , αs — все регулярные точкиФАЛ f . Тогда для каждого j, j = 1, . . . , s, в силу регулярности точки αj , найдется нерегулярная точка βj ФАЛ f ,обладающая тем свойством, что любая максимальная граньФАЛ f , проходящая через точку βj , проходит и через точку αj . Следовательно, любая система максимальных граней ФАЛ f , покрывающая точки β1 , . . . , βs , «автоматически» покроет все точки α1 , . . .
, αs . Таким образом, граньNK , состоящая из регулярных точек, не может входить втупиковое покрытие множества Nf максимальными гранями, и поэтому ЭК K не может входить в ДНФ ΣT ФАЛ f .Пусть теперь NK — нерегулярная грань ФАЛ f , которая содержит нерегулярную точку α, и пусть Nf \ NK == {β1 , . . . , βq }. Из нерегулярности точки α следует, что длялюбого j, j = 1, . . . , q, пучок Πβj (f ) не может быть строго вложен в пучок Πα (f ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
