1 (С.А. Ложкин - Лекции по основам кибернетики (2017)), страница 5
Описание файла
Файл "1" внутри архива находится в папке "С.А. Ложкин - Лекции по основам кибернетики (2017)". PDF-файл из архива "С.А. Ложкин - Лекции по основам кибернетики (2017)", который расположен в категории "". Всё это находится в предмете "основы кибернетики" из 6 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 5 страницы из PDF
§1) покрытие множества Nf максимальнымигранями ФАЛ f и обратно.Построение всех или некоторых тупиковых ДНФ для заданной ФАЛ f является, обычно, промежуточным этапомпри построении минимальной (кратчайшей) ДНФ ФАЛ f ,то есть ДНФ, которая имеет минимальный ранг (соответственно длину) среди всех ДНФ, реализующих f . Это связано с тем, что минимальная ДНФ обязательно являетсятупиковой, а среди кратчайших ДНФ всегда есть тупиковая.При построении тупиковых ДНФ ФАЛ f бывает полезнознать ДНФ пересечение тупиковых (ДНФ ∩T ) ФАЛ f , тоесть дизъюнкцию всех тех различных простых импликантэтой ФАЛ, которые входят в любую тупиковую ДНФ ФАЛf.Набор α, α ∈ B n , называется ядровой точкой ФАЛ f (x1 , . . . , xn ),если α ∈ Nf и α входит только в одну максимальную граньФАЛ f .
При этом грань NK , являющаяся максимальнойгранью ФАЛ f и содержащая точку α, считается ядровойгранью ФАЛ f , а совокупность всех различных ядровых граней ФАЛ f называется ядром ФАЛ f .32ВведениеЛемма 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)Введение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Введение(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, являются ее регулярными точка-Введение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Введениепиковое покрытие множества 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 . Если же все ядровые гра-Введение37ни ФАЛ f выделены и «помечены» (для этого, как уже говорилось, достаточно рассмотреть их окрестности порядка1), то невхождение ЭК K в ДНФ Квайна ФАЛ f равносильно покрытию грани NK отличными от нее «помеченными»гранями из окрестности S1 (NK , f ).§5Особенности ДНФ линейных и монотонныхфункций. Функция покрытия, таблица Квайна и построение всех тупиковых ДНФБудем говорить, что ФАЛ f (x1 , .