Теормин по методичке 2013

Теоретический минимум по «основамкибернетики», 3 курс, 6 семестрЧасть IМинимизация дизъюнктивныхнормальных форм и связанные с нейзадачи1. Представление функций алгебры логики (ФАЛ) дизъюнктивными нормальными формами (ДНФ) и его«геометрическая» интерпретация.

Совершенная ДНФи критерий единственности ДНФ.См. §2 методички, он почти целиком состоит из определений. Список:• единичный куб (гиперкуб) размерности n;• i-й слой куба B n ;• отношение лексикографического линейного порядка на множестве B n ;• отрезок куба B n ;• расстояние Хэмминга;• противоположные, соседние (соседние по i-й переменной) наборы;• сфера и шар радиуса t с центром α;• отношение частичного порядка 6 на B n ;• сравнимые и несравнимые наборы;• грань куба B n , её размерность и ранг;• обозначения X, P2 (X) или P2 , X ⊂ X, P2 (X), P2m (X), X(n), P2 (n), P2m (n);• таблица значений и столбец значений ФАЛ;• характеристическое множество ФАЛ f и характеристическая функция множества Nf ;• P2 (1) и «основные» ФАЛ из P2 (2), функция голосования;• ассоциативность, коммутативность, дистрибутивность (в т. ч.

& относительно ∨ и ⊕);• тождества приведения подобных (в т. ч. тождество поглощения);• линейная функция;• множество Б0 , буквы, ЭК и ЭД ранга r от БП X(n);• ДНФ, КНФ, совершенные ДНФ и КНФ;• длина ДНФ или КНФ A (λ(A));• разложение Шеннона;• геометрическая интерпретация ДНФ и КНФ, а также совершенных ДНФ и КНФ.Лемма. Совершенная ДНФ ФАЛ f ∈ P2 (n) является единственной ДНФ от БП X(n),которая реализует эту ФАЛ ⇔ когда во множестве Nf нет соседних наборов.Следствие.

Совершенные ДНФ ФАЛ `n , `n являются единственными ДНФ этих ФАЛот БП X(n).12. Сокращённая ДНФ и способы её построенияФАЛ f 0 имплицирует ФАЛ f 00 ((f 0 → f 00 ) ≡ 1), если Nf 0 ⊆ Nf 00 .ФАЛ f 00 поглощает ФАЛ f 0 , если Nf 0 ⊆ Nf 00 .ФАЛ f 0 имплицирует ФАЛ f 00 ⇔ f 00 = f 0 ∨ f 00 или f 0 = f 0 · f 00 .ЭК K 0 имплицирует ЭК K 00 ⇔ K 0 = K 00 · K, где K не имеет общих букв с K 00 .ЭК K является импликантой ФАЛ f , если K имплицирует f .ДНФ A называется ДНФ без поглощений ЭК, если ни одна из граней NK1 , .

. . , NKs несодержится ни в одной из других граней покрытия Nf = NK1 ∪ . . . ∪ NKs . Или, другимисловами, ни одна ЭК не является импликантой другой ЭК.Импликанта K ФАЛ f называется простой импликантой f , если она не поглощаетсяникакой другой отличной от неё импликантой f (т. е. не имплицирует никакую другуюимпликанту f ). С «геометрической» т. з. простые импликанты f соответствуют максимальным по включению граням множества Nf .Дизъюнкция всех простых импликант ФАЛ f называется её сокращённой ДНФ.Сокращённая ДНФ является ДНФ без поглощений.Теорема.

Пусть A0 и A00 — сокращённые ДНФ ФАЛ f 0 и f 00 соответственно, а ДНФ A безпоглощений получается из формулы A0 · A00 в результате раскрытия скобок и приведенияподобных. Тогда A — сокращённая ДНФ ФАЛ f = f 0 · f 00 .Следствие. Если ДНФ A без поглощений получается из КНФ B ФАЛ f в результатераскрытия скобок и приведения подобных, то A — сокращённая ДНФ ФАЛ f .Метод Блейка позволяет получить сокращённую ДНФ ФАЛ f из произвольной ДНФ f .ДНФ A0 называется расширением ДНФ A, если она получена путём выделения спомощью тождеств ассоциативности и коммутативности подформул вида xi K 0 ∨ xi K 00 , применением к ним тождества обобщённого склеивания (xi K 0 ∨ xi K 00 = xi K 0 ∨ xi K 00 ∨ K 0 K 00 )и последующим приведением подобных.ДНФ A0 называется строгим расширением ДНФ A, если она является расширением Aи содержит ЭК, не являющуюся импликантой ни одной ЭК из A.Теорема. ДНФ без поглощений ЭК является сокращённой ДНФ ⇔ когда она не имеетстрогих расширений.Следствие.

Из любой ДНФ A ФАЛ f можно получить сокращённую ДНФ этой ФАЛ врезультате построения последовательных строгих расширений и приведения подобных дополучения ДНФ без поглощений ЭК, не имеющей строгих расширений.23. Тупиковая ДНФ, ядро и ДНФ пересечение тупиковых.ДНФ Квайна, критерий вхождения простых импликантв тупиковые ДНФ и его локальность.ДНФ A, реализующая ФАЛ f , называется тупиковой ДНФ, если f 6= A0 для любойДНФ A0 , полученной из A в результате удаления некоторых букв или целых ЭК.В тупиковую ДНФ ФАЛ f могут входить только простые импликанты f .

Она являетсяДНФ без поглощений ЭК. С «геометрической» т. з. тупиковая ДНФ ФАЛ f задаёттупиковое покрытие множества Nf максимальными гранями f и обратно.Минимальная ДНФ — ДНФ, имеющая минимальный ранг среди ДНФ реализующих f .Кратчайшая ДНФ — ДНФ, имеющая минимальную длину среди ДНФ реализующих f .Минимальная ДНФ всегда является тупиковой, среди кратчайших обязательно найдётся тупиковая.Набор α называется ядровой точкой ФАЛ f , если α ∈ Nf и α входит только в однумаксимальную грань ФАЛ f . При этом грань NK , являющаяся максимальной гранью ФАЛf и содержащая точку α, называется ядровой гранью ФАЛ f .

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

Грань, которая не входит в ядро, нопокрывается им, регулярна.3Теорема. Простая импликанта K ФАЛ f входит в ДНФ ΣT ⇔ когда грань NK не является регулярной гранью этой ФАЛ.Для каждой максимальной грани N ФАЛ f положим S0 (N , f ) = {N }, затем индукциейпо r определим окрестность порядка r грани N функции f Sr (N , f ) как множество всехтех максимальных граней ФАЛ f , которые имеют непустое пересечение хотя бы с однойгранью из Sr−1 (N , f ).Вопрос о вхождении простой импликанты K в ДНФ ∩T (ДНФ ΣT ) этой ФАЛ можнорешить, рассматривая окрестность S1 (NK , f ) (соответственно S2 (NK , f )).4. Особенности ДНФ линейных и монотонных ФАЛ.Функция покрытия, таблица Квайна и построение всехтупиковых ДНФ.ФАЛ f линейно зависит от БП xi (xi является линейной БП f ), если f (α) 6= f (β) длялюбых соседних по xi наборов α и β.Равенство f (x1 , . .

. , xn ) = xi ⊕ f (x1 , . . . , xi−1 , 0, xi+1 , . . . , xn ) равносильно линейности поБП xi ФАЛ f .ФАЛ f является линейной ⇔ когда она линейно зависит от всех своих существенных БП.Если ФАЛ f линейно зависит от БП xi , то в любую импликанту этой ФАЛ входит однаиз букв xi , xi .ФАЛ f называется монотонной, если f (α) 6 f (β) для любых наборов α и β таких, чтоα 6 β.ФАЛ f монотонно зависит от БП xi (xi является монотонной БП ФАЛ f ), еслиf (α) 6 f (β) для любых соседних по xi наборов α и β таких, что α 6 β.ФАЛ является монотонной ⇔ когда она монотонно зависит от всех своих БП.Если ФАЛ f монотонно зависит от БП xi , то ни одна из её простых импликант несодержит букву xi .Частные случаи монотонной зависимости f от xi : конъюнктивная (f = xi · g) идизъюнктивная (f = xi ∨ g), где ФАЛ g получается подстановкой вместо xi константы 1или 0 соответственно.При конъюнктивной зависимости буква xi входит в любую простую импликанту ФАЛf , в случае дизъюнктивной зависимости буква xi не входит ни в одну простую импликантуf , отличную от xi .ФАЛ f (x1 , .

. . , xn ) зависит от БП xi инмонотонно (инконъюнктивно, индизъюнктивно), если ФАЛ f (x1 , . . . , xi−1 , xi , xi+1 , . . . , xn ) зависит от xi монотонно (соответственно4конъюнктивно, дизъюнктивно).Сопоставим каждому набору β ∈ B n монотонную ЭК Kβ+ , состоящую только из техбукв xj , для которых βhji = 1. Любая монотонная ЭК может быть представлена в такомвиде.Набор α называется нижней единицей монотонной ФАЛ f , если α ∈ Nf и ∀β 6= α, β 6 αвыполняется f (β) = 0. Множество всех нижних единиц монотонной ФАЛ f обозначаетсяNf+ .Лемма. Сокращённая ДНФ A монотонной ФАЛ f является единственной тупиковойДНФ этой ФАЛ и имеет вид_A=Kβ+ .β∈Nf+При этом все наборы из Nf+ являются ядровыми точками ФАЛ f .Замечание.

Можно сказать, что сокращённая ДНФ монотонной ФАЛ состоит из еёпростых импликант, не содержащих отрицаний и соответствующих нижним единицам.Следствие. Монотонная ФАЛ является ядровой ФАЛ.Пусть N = {α1 , . . . , αs } — конечное множество, а N = {N1 , . . . , Np } — система егоподмножеств, образующих покрытие N . Сопоставим паре (N , N) матрицу M ∈ M p,s , длякоторой M hi, ji = 1 ⇔ αj ∈ Ni .Считаем, что i-я строка соответствует подмножеству Ni системы N, а j-й столбец —элементу αi множества N .i-я строка M покрывает её j-й столбец, если M hi, ji = 1.Система строк с номерами из I образует покрытие матрицы M , если каждый еёстолбец покрывается хотя бы одной строкой с номером из I.