Теормин (все билеты, кроме 12-14) (Мадорский) (1133375), страница 4
Текст из файла (страница 4)
. , fm) влюбом из рассматриваемых классовm схем вы-полняютсяXнеравенства max L (fi ) 6 L (F ) 6L (f ) .16i6mii=1Лемма 1.1. Для любой функции алгебры логики f (x1 , . . . , xn ),f 6= 0, существуют формула Ff , Ff ∈ UΦ , и π-схема Σf ,которые реализуют f и для которых справедливы неравенL (Σf ) 6 n |Nf | .ства: L (Ff ) 6 2n · |Nf | − 1,Следствие 1. В силу (1.1), с учетом того, что ФАЛ 0можно реализовать π-схемой сложности 2, а также формулой из UΦ , имеющей сложность 2, выполняются нераLC (n) 6 LΦ (n) 6 n · 2n+1 − 1,венстваLK (n) 6 Lπ (n) 6 n · 2n .Следствие 2.
В силу следствия 1 и с учётом следствия 2из теоремы 2.1 главы 2 справедливо неравенствоD(n) 6 n + ⌈log n⌉ + 2.Лемма 1.2. Для любой ФАЛ f, f ∈ P2 (n) и f 6= 0, существуют π-схема Σf и формула Ff , Ff ∈ UΦ , которыереализуют f и для которых, наряду с (1.1), справедливыnтакже неравенства: L (Σf ) 6 2 + |Nf | − 2,L (Ff ) 6 2n+1 + |Nf | − 4.Следствие.Lπ (n) 6 2n+1 − 2, LΦ (n) 6 3 · 2n − 4.Пусть вершина w СФЭ Σ не достижима из ее вершины v,а СФЭ Σ′ получается из СФЭ Σ в результате удаления вершины v, объявления вершины w начальной вершиной всехисходивших из v дуг и переноса в вершину w всех выходных БП, приписанных вершине v. Тогда СФЭ Σ′ считаетсярезультатом применения к СФЭ Σ операции присоединениявершины v к вершине w.
Две вершины СФЭ называютсяэквивалентными, если в них реализуются равные ФАЛ.Приведенная схема называется строго приведенной, если в ней нет эквивалентных вершин. Из любой СФЭ можнополучить эквивалентную ей строго приведенную СФЭ с помощью операции присоединения эквивалентных вершин иоперации удаления висячих вершин.−→Для множества ФАЛ G, G ⊆ P2 (n), через G будем обозначать систему, состоящую из всех различных ФАЛ множества G, упорядоченных в соответствии с номерами их столб−→цов значений. При этом систему ФАЛ P 2 (n) будем называть универсальной системой порядка n.Лемма 1.3.
Для каждого натурального n в UCБ существу−→ет СФЭ Un , которая реализует систему ФАЛ P 2 (n) иnсложность которойравна22 − n.→−C2nСледствие. LБ P 2 (n) 6 2 − n.16 Нижние оценки сложности ФАЛ, реализация некоторых ФАЛ и минимальность некоторых схем.Лемма 2.1. Если ФАЛ f (x1 , . . . , xn ) существенно зависитот всех своих БП, то LC (f ) > n − 1, LK (f ) > n.Если при этом ФАЛ f не является монотонной ФАЛ (каждая БП xi , i ∈ [1, k], не является ни монотонной, ни инмонотонной БП ФАЛ f ), то LC (f ) > n (соотв.
LK (f) > n + k).Следствие.LC (ℓn ) > n,LK (ℓn ) > 2n,LC (µn ) > 2n + n,LK (µn ) > 2n + 2n.Лемма 2.2. Для системы F = (f1 , . . . , fm ), состоящей изпопарно различных ФАЛ отличных от констант (от переменных), справедливо неравенство LK (F ) > m(соответственно LБC (F ) > m).→→− − L K Q n > 2n ,Следствие LC ( Q n > 2n ,→→− − L C J n > 2n ,L K J n > 2n ,−→−n2nK →(n)> 22 − 2.(n)>2−n,LPLCP22БЛемма 2.3.
Для любого натурального n выполняются нераnn→−→−венства: LC ( Q n ) 6 2n + O(n · 2 2 ), LC ( J n ) 6 2n + O(n · 2 2 );−→LK ( Q n ) 6 2n+1 − 2;LΦ (µn ) 6 2n+2 − 3; Lπ (µn ) 6 3 · 2n − 2,1CCL (ℓn ) 6 4n − 4 +.L (ℓn ) 6 4n − 4,n→−−→Следствие. LС ( Q n ) ∼ LС ( J n ) ∼ 2n .Лемма 2.4. Если система ФАЛ F = (f1 , . . . , fm ) состоитиз попарно различных ФАЛ от БП X(n), отличных от 0 иmXNf .1, то LK (F ) > 21−njj=1Kn+1− 2.Следствие. L (Jn ) > 2Лемма 2.5.
Если для ФАЛ f , f ∈ P2 (n), и для любого σ,σ ∈ B, ФАЛ fσ (x1 , . . . , xn−1 , σ) 6≡ 0, 1, тоCCLC&,∨ (f ) > min{L&,∨ (f0 ), L&,∨ (f1 )} + 2.След. 1. LC (µn) > 2n+1 + n − 1.След. 2. D(µn) > n + 1.17 Каскадные контактные схемы и схемы из функциональных элементов. Метод каскадов и примеры егоприменения, метод ШеннонаОпределим, далее, каскадную КС как приведенную КСбез изолированных полюсов, которая может быть полученаиз системы тождественных вершин в результате ряда операций присоединения одного или двух противоположных контактов и операций переименования выходов.
Каскадная КС(ККС) считается полной, если она была построена без использования операции присоединения одного контакта.Вершина ККС, введенная в нее с помощью операцииприсоединения одного контакта, называется неполной вершиной этой ККС. Будем говорить, что ККС Σ′′ являетсядополнением неполной ККС Σ′ , если она получается в результате соединения всех неполных вершин Σ′ отсутствующими в них контактами с новым входом, удаления всех«старых» входов и перехода к соответствующей приведеннойКС.а объединениеΣ′ и Σ′′ является полной ККС.
Дополнение Σ′′к полной ККС Σ с 1 входом будем называть инверсной к Σ′ККС. Заметим, что ККС Σ′′, в силу отмеченных выше′свойств полных ККС, реализует систему ФАЛ F , если ККСΣ′ реализует систему ФАЛ F ′ . Таким образом, в силу (3.3)справедливо следующее утверждениеЛемма 3.1. Если (1, m)-ККС Σ′ реализует систему ФАЛ′ ), то существует (1, m)-ККС Σ′′ , котораяF ′ = (f1′ , . . . , fm′′′реализует систему ФАЛ F = f 1 , . . . , f m и для которойL (Σ′′ ) 6 2L (Σ′ ).Лемма 3.2. Для любого натурального n и σ∈ B выполня1K σются неравенства:L (ℓn ) 6 4n − 4 +,n−− →K →2nKn+2L P 2 (n) 6 2 · 2 , L J n 6 2− 6.Теорема 3.1. Для функций Шеннона LK (n) и LC (n) выnnполнены соотношения: LK (n) .
4 2 , LC (n) . 8 2 .nn18 Нижние мощностные оценки функции ШеннонаМощностной метод Шеннона основан на том, что число ФАЛот БП x1, . . . , xn не может быть меньше числа тех попарно неэквивалентных схем, сложность которых не превосходитзначения соответ-ствующей функции Шеннона от аргумента n.Обозначим че-рез U (Ψ, n) множество тех схем Σ, Σ ∈ U,которые реализу-ют одну ФАЛ из P2 (n) и для которых Ψ(Σ) 6 Ψ.
Следую-щее «мощностное» равенство вытекаетnнепосредственно из определений: kU (Ψ (n) , n)k = 22 . CU (L, n) 6 (8 (L + n))L+1 ,Верхние оценки,установленные ранее: UΦ (L, n) 6 (8n)L+1 ,LπkU (L, n)k 6 (12n) , KU (L, n) 6 (8nL)L , ΦD2U [L, n] 6 (8n) .Лемма 4.1. Для положительных действительных чиселya, y, q из неравенств a log q > 1, (ay) > q,log qlog log (a log q)следует неравенствоy>1+,log (a log q)log (ae log q)где e — основание натуральных логарифмов, а из неравенствa > 1, ay > q — неравенство y > log q .log aТеорема 4.1. Для некоторых последовательностей εi =εi (n),где i = 1, . . .
, 5 и n = 1, 2, . . ., таких, что εi (n) > 0 приn > n0 и εi (n) стремится к 0 при n стремящемся к бесконечности, для почти всех ФАЛ f , f ∈ P2 (n), выполняютсяnнеравенства LC (f ) > (1 + ε (n)) 2 ,1n2n2nΦL (f ) > (1 − ε2 (n)), Lπ (f ) > (1 − ε4 (n)),log nlog n2nD (f ) > n − log log n − ε5 (n).LK (f ) > (1 − ε3 (n)) ,n2nСледствие 1. LC (n) &,n2nπ.L (n) &log nLΦ (n) &2n,log nLK (n) &2n,n19Дизъюнктивно-универсальные множествафункций. Асимптотически наилучший методО. Б. Лупанова для синтеза схем изфункциональных элементов в базисе {&, ∨, ¬}Указанное ДУМ G будем называть ДУМ, связанным сразбиением Π.
Компоненты разбиения Π будем при этом называть полосами ДУМ G, а ФАЛ ψ1 = χδ1 , . . . , ψp = χδp — егохарактеристическими ФАЛ.Будем считать стандартным ДУМ порядка m и высоты s, где s 62m ,ДУМ ранга p, p = ⌈2m /s⌉, связанное с разбиением Π =(π1 , . . . , πp ) куба B m на последовательные отрезки, для которого номер любого набора из множества πi меньше номералюбого набора из множества πj , если i < j, и выполнены соотношения s1 = s2 = · · · = sp−1 = s, sp = 2m − (p − 1) s 6 s.Лемма5.1. Для любых натуральных p, m и s, где p = 2m s , существует стандартное ДУМ G порядка m и высоты s, которое является ДУМ ранга p и для которого:1) λ = |G| 6 p2s ;2) система из p характеристических ФАЛ ψ1 , . .
. , ψpДУМ G обладает тем свойством, что для любойФАЛ g, g ∈ P2 (m), и соответствующих ФАЛg1, . . . , gp из G справедливо не только представлениеxg = g1 ∨ . . . ∨ gp , но и представлениеg = ψ1 g 1 ∨ ψ2 g 2 ∨ · · · ∨ ψp g pТеорема 5.1. Для любой ФАЛ f, f ∈ P2 (n), существуетреализующая ее СФЭ Σf , Σf ∈ UC , такая, что2n5 log n + O (1)L (Σf ) 61+.nn2nСледствие. LC (n) ∼.nМетод каскадов позволяет строить КС и СФЭ, многократноиспользующие «промежу-точные результаты».Метод Шеннона позволяет строить КС и СФЭ и установить порядок роста функцийШеннона LС(n) и LК(n).Метод Шеннона основан на разложении Шеннона по q переменным.
При этом мыраскладываем функцию на подфункции от q переменных, которые в разложении домножаσσn· x−ются на функции вида x q+1n q) переменных. Все указанные подфункции отq+1от· ·(nq переменных мы реализуем с помощью универсального многополюсника порядка q (т. е.схемы, которая реализует все функции от q переменных). Потом присоединяем к выходамуниверсального многополюсника, к q информационным входам мультиплексора порядка (n− q), т.
е. у него (n − q) адресных переменных, с помощью которых «адресуются»конкретные функции, реализуемые универсальным многополюсником.Полагаем q = ⌊log2(n − 2 log2 n)⌋.Метод О. Б. Лупанова позволяет строить СФЭ и установать асимптотику функцииШеннона LС(n).Множество ФАЛ G ∈ P2(m) называется дизъюнктивно-универсальным множеством(ДУМ ) порядка m и ранга p, если любая ФАЛ g ∈ P2(m) м.
б. представлена в виде g = g1 ∨ · ·· ∨ gp, где gi ∈ G.Метод О. Б. Лупанова также основан на разложении Шеннона по q переменным и такжеиспользует мультиплексор порядка (n−q). Но подфункции от q переменных из разложенияреализуются не универсальным многополюсником, а как дизъюнкция функций из ДУМпорядка q.-------------------------------------------------------------------17 (начало)19 (начало)20Регулярные разбиения единичного куба и моделирование функций переменными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
