OK_metodichka_part_1 (1132796), страница 5
Текст из файла (страница 5)
Достаточно убедиться в том, что неприводимая ДНФ A, не имеющая строгих расширений, содержит все простые импликанты реализуемой ею ФАЛ f . ПустьX (n) = {x1 , . . . , xn } — множество БП ДНФ A, а K — простая импликанта f , которая не входит в A. Рассмотрим множество K, состоящее из всех тех элементарных конъюнкцийот БП X (n), которые являются импликантами f , но не являются импликантами ни одной ЭК из A. Заметим, что множество K не пусто, так как содержит ЭК K в силу ее свойств,и что K не может содержать ЭК ранга n, поскольку любаяЭК вида xα1 1 · · · xαnn , где α = (α1 , . .
. , αn ) ∈ Nf , является импликантой той ЭК из A, которая обращается в 1 на наборе α.Пусть, далее, k — ЭК максимального ранга в K, причем,как было отмечено, R (k) < n, и пусть буквы некоторой БПxi , 1 6 i 6 n, не входят в k. Тогда, в силу выбора ЭК k исвойств ДНФ A, ЭК вида xi · k (вида xi · k) должна быть импликантой некоторой ЭК вида xi ·K 0 (соответственно xi ·K 00 )32Глава 1. Дизъюнктивные нормальные формыиз A, где ЭК K 0 и K 00 состоят из букв ЭК k.
Следовательe равной K 0 · K 00 , а ЭКно, ЭК k является импликантой ЭК KeK, в свою очередь, является импликантой некоторой ЭК изA. Действительно, ДНФ A не имеет строгих расширений иe попоэтому содержит ЭК, которая имплицируется ЭК K,000лучающейся из подформулы xi K ∨ xi K в результате эквивалентного преобразования (3.2). Таким образом, ЭК 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. Тупиковые и минимальные ДНФ§433ДНФ Квайна и ДНФ сумма тупиковых. Критерий вхождения простых импликант в тупиковые ДНФ, его локальность.Теорема Ю. И. Журавлева о ДНФ суммаминимальныхИсходя из «геометрических» соображений можно находитьвсе или некоторые тупиковые ДНФ для ФАЛ от небольшогочисла БП. Так, например, сокращенная ДНФ (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)а у ФАЛ 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 наряду с ДНФпересечение тупиковых (см. §2) полезно знать ДНФ сумматупиковых (ДНФ ΣT ) ФАЛ f , то есть дизъюнкцию всех техразличных простых импликант этой ФАЛ, которые входятв хотя бы в одну тупиковую ДНФ ФАЛ f .
Заметим, чтоДНФ ∩T ФАЛ f в общем случае не реализует саму ФАЛ f ,а в некоторых случаях и, в частности, в случае ФАЛ g (см.выше), может быть пустой. В то же время ДНФ ΣT ФАЛ fвсегда реализует эту ФАЛ, содержится в ее сокращенной иможет с ней совпадать, как это имеет место в случае ФАЛ34Глава 1. Дизъюнктивные нормальные формыg или в случае ФАЛ «голосования». Аналогичным образомопределяется ДНФ сумма минимальных (ДНФ ΣM ) ФАЛ fи т. п. Очевидно, что ДНФ ΣM ФАЛ f реализует эту ФАЛи содержится в ее ДНФ ΣT , а для всех приведенных вышеФАЛ ДНФ ΣM совпадает с ДНФ ΣT .Будем называть ФАЛ ядровой, если все ее максимальные грани являются ядровыми.
Из леммы 2.1 следует, чтосокращенная ДНФ ядровой ФАЛ является ее единственнойтупиковой ДНФ. Примером ядровой ФАЛ является ФАЛголосования (3.3) (см. также §6).(111)`@@@`c`c`@@@@@c``@c`@ x2x@1@I `6 x3@(000)Рис. 4.1: «геометрия» сокращенной ДНФ ФАЛ g 00Дизъюнктивная нормальная форма, получающаяся изсокращенной ДНФ ФАЛ 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 . Вто же время для ФАЛ g 0 , показанной на рис. 3.1, ДНФ Квайна совпадает с сокращенной ДНФ этой ФАЛ и отличается§4. Тупиковые и минимальные ДНФ35от ее ДНФ Σ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, являются ее регулярными точками. Кроме того, в силу включения Πβ0 (g 0 ) ⊂ Πα0 (g 0 ), точкаα0 тоже является регулярной точкой этой ФАЛ.Грань NK ФАЛ f называется регулярной гранью этойФАЛ, если все точки NK регулярны. Заметим, что грань,которая не входит в ядро, но покрывается им, является регулярной. Заметим также, что для ФАЛ g 0 , показанной нарис.
3.1, грани N60 и N70 , которые не входят в ДНФ ΣT , являются регулярными, так как состоят из регулярных точек.Теорема 4.1 (ср. [27, 6, 22, 10]). Простая импликанта KФАЛ f входит в ДНФ ΣT тогда и только тогда, когдагрань NK не является регулярной гранью этой ФАЛ.Доказательство. Пусть α1 , . . . , αs — все регулярные точкиФАЛ f . Тогда для каждого j, j = 1, . . . , s, в силу регулярности точки αj , найдется нерегулярная точка βj ФАЛ f ,36Глава 1.
Дизъюнктивные нормальные формыобладающая тем свойством, что любая максимальная граньФАЛ 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 ). Кроме того, равенство Πβj (f ) == Πα (f ) тоже невозможно, так как NK ∈ Πα (f ) \ Πβj (f ),и поэтому в Πβj (f ) найдется грань NKj , которая проходитчерез точку βj , но не проходит через точку α. Следовательно, из покрытия множества Nf максимальными гранямиNK , NK1 , . . . , NKq нельзя удалить грань NK , так как только она покрывает в нем точку α.
Таким образом, любое тупиковое покрытие множества Nf , являющееся подпокрытием указанного покрытия, будет соответствовать тупиковойДНФ, содержащей ЭК K.Теорема доказана.Коснемся, далее, вопроса о локальном характере рассмотренных выше критериев вхождения простых импликантФАЛ f в ее ДНФ ∩T и ДНФ ΣT (см.
[27, 21, 22, 16]). Длякаждой максимальной грани N ФАЛ f (x1 , . . . , xn ) положимS0 (N, f ) = {N}, а затем индукцией по r, r = 1, 2, . . ., определим множество Sr (N, f ) как множество всех тех максимальных граней ФАЛ f , которые имеют непустое пересечениехотя бы с одной гранью из Sr−1 (N, f ). При этом множествоSr (N, f ) будем называть окрестностью порядка r грани Nфункции f .§4. Тупиковые и минимальные ДНФ37Докажем, что вопрос о вхождении простой импликанты K ФАЛ f в ДНФ ∩T (ДНФ ΣT ) этой ФАЛ можно решить, рассматривая окрестность S1 (NK , f ) (соответственноS2 (NK , f )). Действительно, грань NK является ядровой гранью ФАЛ f тогда и только тогда, когда она не покрываетсявсеми остальными максимальными гранями этой ФАЛ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
