Теормин (все билеты, кроме 12-14) (Мадорский) (1133375), страница 2
Текст из файла (страница 2)
. , αs }, заключается в нахождении такого подмножества множества N , в которомЭта задача сводится к задаче о∀i ∈ [1, p] имеется хотя бы один элемент из Ni .выделении подпокрытия из покрытия отрезка [1, p] его подмножества-ми I1, . . . , Is,где Ii = {j : αi ∈ Nj } при всех i, i ∈ [1, s]. Заметим, что матрица построенной такимобразом системы подмножеств отрезка [1, p] получается из матрицы системы (N, N)в результате транспонирования.Лемма. ∀m, n ∈ N, m 6 n в кубе B n всегда найдётся подмножество мощности не болеечем n · 2m , протыкающее все грани ранга m.
Док-во: часть 1, стр. 476Задача минимизации ДНФ. Поведение функциитипичных значений для ранга и длины ДНФ.ШеннонаиоценкиНа множестве ДНФ задаётся неотрицательный функционал сложности ψ , обладающийсвойством монотонности, т. е. ∀ДНФ A ∃ψ(A) > 0 : ψ(A0) > ψ(A00), если ДНФ A00 получаетсяиз ДНФ A0 удалением букв или ЭК.Примеры: длина λ(A), ранг R(A), «формульная» сложность L(A).Задача минимизации ДНФ относительно функционала сложности ψ состоит в нахождении для заданной ФАЛ f ДНФ A, такую что ψ(A) = min ψ(A0 ), где минимум берётся повсем ДНФ A0 ФАЛ f .При этом ДНФ A называется минимальной относительно функционала ψ или ψминимальной ДНФ. Значение ψ(A) называется сложностью ФАЛ f относительнофункционала ψ или ψ-сложностью ФАЛ f в классе ДНФ.λ-минимальную (по длине) ДНФ будем называть кратчайшей, а R-минимальную (порангу) — просто минимальной.Функция Шеннона для класса ДНФ относительно функционала ψ: ψ(n) = max ψ(f ).f ∈P2 (n)n−1n−1, R(n) = n · 2.Лемма.
∀n ∈ N имеют место соотношения λ(n) = 2Рассмотрим отрезок [ψ 0 (n), ψ 00 (n)], в который попадают значения ψ(n) для почти всехФАЛ f ∈ P2 (n). Если границы ψ 0 (n) и ψ 00 (n) асимптотически равны ψ(n), то говорят, чтодля параметра ψ имеет место эффект Шеннона.Для параметров λ и R эффект Шеннона отсутствует.Лемма 7.2. Для почти всех ФАЛ f, f ∈ P2(n), выполняются неравенства:33λ(f ) 6 n · 2n−1 1 + O n · 2−n/2λ(f ) 6 2n−1 1 + O n · 2−n/2 ,447АлгоритмическиетрудностиминимизацииДНФи оценкимаксимальных значений некоторых связанных с ней параметров.Теорема Ю. И.
Журавлёва о ДНФ сумма минимальных.Функция Шеннона для параметра ψ в классе ДНФ: ψ(n) = max ψ(f ).f ∈P2 (n)Обозначим значение функции Шеннона для следующих параметров: число тупиковыхДНФ — τ (n), число минимальных ДНФ — µ(n) и длина сокращённой ДНФ у ФАЛ из P2 (n)— λсокр. (n) (ДНФ рассматриваются с точностью до перестановки ЭК и букв в них).Лемма. Для ФАЛ f из P2 (n), n > 4, вида f (x1 , .
. . , xn ) = g(x1 , x2 , x3 ) · (x4 ⊕ · · · ⊕ xn ), гдеn−4N g = {(000), (111)}, число тупиковых (минимальных) ДНФ равно 52(соответственноn−4n−4n−4Док-во: часть 1, стр. 5322 ).Следствие. τ (n) > 52 , µ(n) > 22 .Выберем множество номеров I ⊆ [0, n], зафиксируем объединение всех слоёв куба B n сномерами из I, обозначим характеристичесую функцию этого объединения как sIn. Числа изI назовём рабочими числами ФАЛ sIn.ФАЛ sIn является симметрической, т. е. не изменяет своё значение при любой перестановке аргументов. Наоборот тоже верно: любая симметрическая ФАЛ совпадает с однойиз ФАЛ вида sIn .Симметрическая ФАЛ является поясковой, еслиобразуют отрезок.
Вид_её рабочие числаσn+r−p[r,p]xσi11 · · · xin+r−p.её сокращённой ДНФ: sn (x1 , . . . , xn ) =16i1 <···<in+r−p 6nσ1 +···+σn+r−p =rПоясковой ФАЛ является, в частности, ФАЛ голосования H (x1 , x2 , x3 ) = s[2,3]3а также ФАЛ g = s3[1,2], показанная на рис.x10x1x110010110011nЛемма. λсокр. (n) > e1 3n , где e1 — некоторая константа.Функция f (x1 , .
. . , xn ) называется цепной (циклической) функцией длины t, если её сокращённая ДНФ с «геометрической» т. з. представляет собой цепь (соответственно цикл)из t последовательно соединённых рёбер N1 , . . . , Nt куба B n .Теорема. ∀n ∈ N, n > 3, в P2 (n) существуют ФАЛ f 0 и f 00 , имеющие общую простуюимпликанту K, которая входит в ДНФ ΣM одной, но не входит в ДНФ ΣM другой изэтих ФАЛ и для которой Sn−3 (NK , f 0 ) = Sn−3 (NK , f 00 ).Формулы, их структура, эквивалентность и способы задания.8 Оптимизацияподобных формул по глубинеПусть X = {x1, x2, . . .
, xn, . . . } — счетный упорядоченный алфавит входных БПи пусть Б = {ϕ1, ϕ2, . . . , ϕb} — базис, где ФАЛ ϕi, i = 1, . . . , b, зависит от ki, ki > 1,БП и является существенной ФАЛ, если ki > 2. Предполагается, что Б — полныйбазис и допускается, в общем случае, наличие в нем равных ФАЛ. Чаще всего мыбудем иметь дело с базисом Б0 = {&, ∨, ¬}.Любая переменная xj из X считается формулой глубины 0 или, иначе,тривиальной формулой над базисом Б, которая реализует функцию xj . Если i ∈[1, b] и для каждого j, j ∈ [1, ki], определена формула Fj глубины qj над Б, котораяреализует ФАЛ fj , то запись F вида F = ϕi (F1 , . .
. , Fki ) является формулой глубиныq над Б, где q = max {q1 , . . . , qki } + 1, кот. реализует ф-цию f вида f = ϕi (f1, . . . , fki ).Все записи, полученные в результате указанного индуктивного построения, итолько они считаются формулами над базисом Б. При этом формулы, полученные впроцессе индуктивного построения формулы F, называются ее подформулами, а теподформулы F1, . . . , Fki , из которых на последнем шаге индуктивного построениястроится формула F (см. выше), считаются ее главными подформулами.Под сложностью (рангом) формулы F понимается число вхождений в неефункциональных символов (соответственно символов переменных), котороеобозначается через L (F) (соответственно R (F)).Графически совпадающие формулы считаются изоморфными, а формулы F′ и F′′,реализующие равные функции f′ и f′′, называются равными или, иначе, эквивалентными. При этом равенство вида t : F′ = F′′ считается тождеством.Лемма 2.1. Для формулы F, F ∈ UΦ, выполняются неравенстваR (F) = L&,∨ (F) + 1 6 L (F) + 1 6 2D(F) , где L&,∨ (F) -число ФС & и ∨ в формуле F.Док-во: часть 2, стр.
19 Следствие. D (F) > ⌈log (L (F) + 1)⌉ .лентпреобразоваФормулы из UΦ, получающиеся друг из друга эквивалентнымиAAKKниями на основе тождеств t & и t ∨ , а также тождеств t & и t ∨ , называютсяподобными.Формула, в которой все ФС ¬ встречаются только над БП, называетсяформулой с поднятыми отрицаниями.
Преобразования подобия и эквивалентныепреобразования формул на основе тождеств де Моргана не изменяют ранг этихформул и, следовательно, число ФС {&, ∨} в них.Альтернирование Alt (F) формулы F с поднятыми отрицаниями максимальное число изменений типов ФС & и ∨ в цепях дерева,соответствующего формуле F. Заметим, что альтернирование ЭК или ЭД равнонулю, а альтернирование любой (отличной от ЭК и ЭД) ДНФ или КНФ равно 1.Теорема 2.1.
Для любой формулы F с поднятыми отриДок-во: часть 2,цаниями из UΦ существует подобная ей формула F̌ тастр. 21-23.кая,что D F̌ 6 ⌈log (L (F) + 1)⌉ + Alt (F) .Следствие 1. Длялюбой ЭК или ЭД Kсуществует подобная формула Ǩтакая, что D Ǩ = ⌈log (L(K) + 1)⌉ , которая, минимальна по глубине.Следствие 2. Для любой ДНФ или КНФ A существуетподобная ей формула Ǎ такая, что D Ǎ 6 ⌈log (L (A) + 1)⌉ + 1.Задание формул графами, схемы из функциональных элементов.9 Оценкачисла формул и схем в базисе {&, ∨, ¬}Схемой из функциональных элементов над базисом Б называетсяориентированная ациклическая упорядоченная сеть Σ, входная выборка которойсостоит из всех истоков Σ, а вершины помечены следующим образом:1. каждому входу (выходу) Σ сопоставлена БП из X (со-ответственно Z), являющаяся пометкой связанной с ним вершины, причем различным входам (выходам) сопоставлены различные БП, а упорядоченность вер-шинво входной и выходной выборках Σ определяется упорядоченностьюсопоставленных им БП;+(v).2.
каждая отличная от истока вершина v схемы Σ помечена ФС ϕi, где ki = dΣДве СФЭ считаются изоморфными, если они изоморфны как помеченныеграфы, и эквивалентными, если они реализуют равные системы ФАЛ. Всоответствующих друг другу вершинах изоморфных (квазиизоморфных) СФЭреализуются одинаковые (соответственно подобные) формулы, а значит, иодинаковые ФАЛ. Следовательно, две изоморфные (квазиизоморфные) СФЭэквивалентны.Также как и для формул, для каждой СФЭ Σ, Σ ∈ UCБ, определим следующиепараметры (функционалы сложности):1. L (Σ) — сложность Σ, то есть число всех ее ФЭ;2. D (Σ) — глубина Σ, то есть максимальная глубина ее вершин.3.
R (Σ) — ранг Σ, то есть число дуг,исходящих из ее входов.Лемма 3.1. Для приведенной СФЭ Σ, Σ ∈ UC , с одним выходом, выполн. нер-ваR (Σ) 6 L&,∨ (Σ) + 1 6 L (Σ) + 1 6 2D(Σ) , где L&,∨ - число ФЭ & и ∨ в Σ.Имеет место включение UΦ [D, n] ⊆ UΦ 2D − 1, n .Лемма 3.2. Для любых натуральных n, L, D выполняются неравенства: ΦU (L, n) 6 (10n)L+1 , Док-во: часть 2, стр. 30-31 ΦСледствие 1.
Число попарно не квазиизоморфныхU (L, n) 6 (8n)L+1 ,формул с поднятыми отрицаниями от БП X (n) ΦU [D, n] 6 (8n)2D .ранга не больше, чем R, не превосходит (12n)R.Лемма 3.3. Для любых натуральных n и L выполняется неравенство CU (L, n) 6 (8 (L + n))L+1 . Док-во: часть 2, стр. 31-32Контактные схемы и π-схемы, оценка их числа. Особенности10 функционированиямногополюсных схемРассмотрим класс контактных схем, в которых реализация ФАЛосуществляется не с помощью преобразования входных значений в выходные,как это происходит, например, в схемах из функциональных элементов, а врезультате передачи значений по ребрам графа, проводимостью которого«управляют» входные БП.
Ребро или дуга графа с пометкой xi (xi) называетсязамыкающим (соответственно размыкающим) контактом БП xi.Сеть Σ с входами a′1, . . . , a′p и выходами a′′1, . . . , a′′q, в которой все ребра(дуги) помечены переменными x1, . . . , xn или их отрицаниями x1, . .
. , xn,называется (p, q)-контактной схемой (КС) от БП x1, ... , xn и обозначается Σ == Σ (x1, . . . , xn) или Σ = Σ (x1, . . . , xn; a′1, . . . , a′p; a′′1, . . . , a′′q ). При этом числоконтактов называется сложностью КС Σ и обозначается через L (Σ).Рассмотрим теперь некоторые оценки числа контактных схем различныхтипов. Пусть UK и Uπ — множество всех КС из неориентированных контактов имножество всех π-схем соответственно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
