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

. . , 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 ). Кроме того, равенство Πβj (f ) == Πα (f ) тоже невозможно, так как NK ∈ Πα (f ) \ Πβj (f ),и поэтому в Πβj (f ) найдется грань NKj , которая проходитчерез точку βj , но не проходит через точку α. Следовательно, из покрытия множества Nf максимальными гранямиNK , NK1 , . .

. , NKq нельзя удалить грань NK , так как только она покрывает в нем точку α. Таким образом, любое ту-36Глава 1. Дизъюнктивные нормальные формыпиковое покрытие множества Nf , являющееся подпокрытием указанного покрытия, будет соответствовать тупиковойДНФ, содержащей ЭК K.Теорема доказана.Коснемся, далее, вопроса о локальном характере рассмотренных выше критериев вхождения простых импликантФАЛ f в ее ДНФ ∩T и ДНФ ΣT (см. [28, 22, 23, 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 .Докажем, что вопрос о вхождении простой импликанты K ФАЛ f в ДНФ ∩T (ДНФ ΣT ) этой ФАЛ можно решить, рассматривая окрестность S1 (NK , f ) (соответственноS2 (NK , f )).

Действительно, грань NK является ядровой гранью ФАЛ f тогда и только тогда, когда она не покрываетсявсеми остальными максимальными гранями этой ФАЛ. Поскольку грани, не входящие в S1 (NK , f ), не имеют общихточек с NK , грань NK является ядровой тогда и только тогда, когда она не покрывается всеми остальными гранямииз S1 (NK , f ). Из теоремы 4.1 следует, что ЭК K не входит в ДНФ ΣT ФАЛ f тогда и только тогда, когда для любой точки α из NK найдется точка β, β ∈ Nf , для которойΠβ (f ) ⊂ Πα (f ).

Заметим, что все грани пучка Πα (f ) входятв S1 (NK , f ), а все грани пучка Πβ (f ), если Πα (f )∩Πβ (f ) 6=∅, — в S2 (NK , f ). Следовательно, проверку грани NK на регулярность можно осуществить на основе анализа ее окрестности порядка 2. Легко показать, что рассмотрение окрестности порядка 2 достаточно для проверки грани NK на еевхождение в ДНФ Квайна ФАЛ f .

Если же все ядровые гра-§5. Построение всех тупиковых ДНФ37ни ФАЛ f выделены и «помечены» (для этого, как уже говорилось, достаточно рассмотреть их окрестности порядка1), то невхождение ЭК K в ДНФ Квайна ФАЛ f равносильно покрытию грани NK отличными от нее «помеченными»гранями из окрестности S1 (NK , f ).§5Особенности ДНФ линейных и монотонныхфункций.

Функция покрытия, таблица Квайна и построение всех тупиковых ДНФБудем говорить, что ФАЛ f (x1 , . . . , 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 , . . .