Теормин (все билеты, кроме 12-14) (Мадорский) (1133375)
Текст из файла
1Представление функций алгебры логики с помощью дизъюнктивных нормальных форм(ДНФ) и его "геометрическая" интерпретация. Совершенная ДНФ, критерийединственция. Совершенная ДНФ, критерий единственности ДНФДля набора γ = (γ1 , . . . , γn ) длины n над множеством [0, 2] через Γγ обозначиммножество всех тех наборов α = (α1, . . .
, αn) куба Bn, для которых αi = γi при всехi ∈ [1, n] таких, что γi 6= 2. Множество Γγ называется гранью куба Bn, число (n − r),равное числу ”2”(т.е. не постоянных БП) в наборе γ, считается размерностью этойграни, а число r — ее рангом.Кроме того, ФАЛ f однозначно определяется своим характеристическим множеством, которое состоит из всех на боров α ∈ Bn таких, что f (α) = 1, и обозначается через Nf .Функции xi и xi будем называть буквами БП xi и, как обычно, будем считать, чтоx0 = xi, x1 = xi. Конъюнкция (дизъюнкция) r, 1 6 r 6 n, букв различных БП измножества X (n) называется элементарной конъюнкцией (соответственноэлементарной дизъюнкцией) ранга r от булевых переменных X (n).Дизъюнкцияразличныхэлементарныхконъюнкцийназываетсядизъюнктивной нормальной формой (ДНФ), а конъюнкция различныхэлементарных дизъюнкций — конъюнктивной нормальной формой (КНФ).
Приэтом ДНФ (КНФ) считается совершенной, если все ее ЭК (соответственно ЭД)существенно зависят от одних и тех же БП, а их ранг ра-вен числу этих БП. ЧислоЭК (ЭД) в ДНФ (соответственно КНФ) A называется ее длиной и обозначаетсячерез λ (A).Лемма 2.1. Совершенная ДНФ ФАЛ f, f ∈ P2 (n), является единственной ДНФот БП X (n), которая реализует эту ФАЛ, тогда и только тогда, когда вомножестве Nf нет соседних наборов.Следствие. Совершенные ДНФ ФАЛ ℓn, ℓn являются единственными ДНФэтих ФАЛ от БП X (n).2Сокращённая ДНФ и способы её построенияФАЛ f0 имплицирует ФАЛ f00 ((f0 → f00) ≡ 1), если Nf0 ⊆ Nf00 .ФАЛ f00 поглощает ФАЛ f0, если Nf0 ⊆ Nf00 .ФАЛ 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, если она получена путём выделения спомощью тождеств ассоциативности и коммутативности подформул вида xiK0 ∨ xiK00, применением к ним тождества обобщённого склеивания (xiK0 ∨ xiK00 = xiK0 ∨ xiK00 ∨ K0K00) ипоследующим приведением подобных.ДНФ A0 называется строгим расширением ДНФ A, если она является расширением A исодержит ЭК, не являющуюся импликантой ни одной ЭК из A.Теорема.
ДНФ без поглощений ЭК является сокращённой ДНФ ⇔ когда она не имеетстрогих расширений.Следствие. Из любой ДНФ A ФАЛ f можно получить сокращённую ДНФ этой ФАЛ врезультате построения последовательных строгих расширений и приведения подобных дополучения ДНФ без поглощений ЭК, не имеющей строгих расширений.ДНФ, ядро и ДНФ пересечение тупиковых. ДНФ3 ТупиковаяКвайна, критерий вхождения простых импликант в тупиковыеДНФ и его локальность.ДНФ A, реализующая ФАЛ f, называется тупиковой ДНФ, если f 6= A0 для любой ДНФ A0,полученной из A в результате удаления некоторых букв или целых ЭК.Минимальная ДНФ — ДНФ, имеющая минимальный ранг среди ДНФ реализующих f.Кратчайшая ДНФ — ДНФ, имеющая минимальную длину среди ДНФ реализующих f.Минимальная ДНФ всегда является тупиковой, среди кратчайших обязательно найдётся тупиковая.ДНФ пересечение тупиковых (ДНФ ∩T ) ФАЛ f - дизъюнкция всех тех различныхпростых импликант этой ФАЛ, которые входят в любую тупиковую ДНФ ФАЛ f.Набор α называется ядровой точкой ФАЛ f, если α ∈ Nf и α входит только в однумаксимальную грань ФАЛ f.
При этом грань NK , являющаяся максимальной гранью ФАЛf и содержащая точку α, называется ядровой гранью ФАЛ f. Совокупность всех различныхядровых граней ФАЛ f называется ядром ФАЛ f.Лемма. ДНФ ∩T ФАЛ f состоит из тех простых импликант ФАЛ f , которые соответствуют ядровым граням этой ФАЛ f .Док-во: часть 1, стр. 32ДНФ сумма тупиковых (ДНФ Σ T ) ФАЛ f - дизъюнкция всех тех различныхпростых импликант этой ФАЛ, которые входят в хотя бы в одну тупиковую ДНФФАЛ f.ФАЛ называется ядровой, если все её максимальные грани являются ядровыми.Следствие.
Сокращённая ДНФ ядровой ФАЛ является её единственной тупиковой ДНФ.ДНФ, получающаяся из сокращённой ДНФ ФАЛ f удалением тех ЭК K, для которыхгрань NK покрывается ядром ФАЛ f, но не входит в него, называется ДНФ Квайна этойФАЛ.ДНФ ∩T ⊆ ДНФ ΣT ⊆ ДНФ Квайна ⊆ сокращённая ДНФ.Для α ∈ Nf обозначим через Πα(f) множество всех проходящих через α максимальныхграней ФАЛ f, будем называть его пучком ФАЛ f через точку α.Точку α будем называть регулярной точкой ФАЛ f, если найдётся точка β ∈ Nf , длякоторой имеет место строгое включение Πβ (f ) ⊂ Πα (f ).Грань NK ФАЛ f называется регулярной гранью этой ФАЛ, если все точки NK регулярны.Теорема.
Простая импликанта K ФАЛ f входит в ДНФ ΣT ⇔ когда грань NK не явДок-во: часть 1, стр. 35-36ляется регулярной гранью этой ФАЛ.ДНФ линейных и монотонных ФАЛ.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 (x1 , .
. . , xn ) зависит от БП xi инмонотонно (инконъюнктивно, индизъюнктивно), если ФАЛ f (x1 , . . . , xi−1 , xi , xi+1 , . . . , xn ) зависит от xi монотонно (соответственноконъюнктивно, дизъюнктивно).Набор α называется нижней единицей монотонной ФАЛ f , если α ∈ Nf и ∀β =6 α, β 6 αвыполняется f (β) = 0. Множество всех нижних единиц монотонной ФАЛ f обозначаетсяNf+ .Лемма. Сокращённая ДНФ A монотонной ФАЛ f является единственной тупиковой_ДНФ этой ФАЛ и имеет видA=K +.ββ∈Nf+При этом все наборы из Nf+ являются ядровыми точками ФАЛ f .Замечание. Можно сказать, что сокращённая ДНФ монотонной ФАЛ состоит из еёпростых импликант, не содержащих отрицаний и соответствующих нижним единицам.Следствие. Монотонная ФАЛ является ядровой ФАЛ.i-я строка M покрывает её j-й столбец, если Mhi, ji = 1.Система строк с номерами из I образует покрытие матрицы M, если каждый её столбецпокрывается хотя бы одной строкой с номером из I.
Аналогично понимается покрытиеодного множества строк M другим множеством строк.Покрытие матрицы M, в котором ни одна строка не покрывается другой строкойназывается неприводимым. Покрытие, не имеющее собственных подпокрытий, называетсятупиковым.ФАЛ F (y) называется функцией покрытия матрицы M без нулевых столбцов, если F (β)= 1 ⇔ когда система строк матрицы M с номерами из I(β) = {i|βhii = 1} образует еёпокрытие.Лемма. Функция покрытия F (y1 , . . .
, yp ) матрицы M ∈ B p,s без нулевых столбцов задаs^_ётся КНФ видаF (y1 , . . . , yp ) =yi .j=116i6pM hi,ji=1Док-во: часть 1, стр. 41-42Следствие. В результате раскрытия скобок и приведения пободных из КНФ для F (см.лемму) можно получить сокращённую ДНФ ФАЛ F (y), простые импликанты которойвзаимно однозначно соответствуют тупиковым покрытиям матрицы M .Градиентный алгоритм и оценка длины градиентного покрытия, лемма о«протыкающих» наборах.
Исполь-зование градиентного алгоритма дляпостроения ДНФ.Градиентный алгоритм ориентирован на выделение из заданного покрытия достаточно«коротких» подпокрытий или, иначе, на построение достаточно «коротких» покрытий длязаданной матрицы.Шаг: в матрице выбирается и включается в покрытие такая строка, которая покрываетнаибольшее число ещё не покрытых столбцов (если таких строк несколько, из них выбирается строка с наименьшим номером).Останов: после того шага, на котором получилось покрытие.5Теорема. Пусть для действительного γ, 0 < γ 6 1, в каждом столбце матрицыM ∈ M p,s имеется не меньше чем γ · p единиц.
Тогда покрытие матрицы M , получаемое с помощью градиентного алгоритма, имеет длину не больше чем d γ1 ln+ (γs)e + γ1 , гдеln+ (x) = 0 при 0 < x < 1 и ln+ (x) = ln(x) при x > 1.Задача о «протыкании» системы N, состоящей из подмножеств N1 , . . . , Np множестваN = {α1 , . .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
