Основы кибернетики - Теормин (часть 3) 2008 (1133255)
Текст из файла
Теормин по Основам Кибернетики (3 часть)created by Кунцьо Степан aka StepLg (321 группа)created with TEX/ Kiledate: 03.05.08version: 0.3mailto: StepLg@GMail.comЗадача синтеза — построение по заданной системе функций реализующей еесхемы, которая принадлежит к заданному классу и на которой достигается минимальное значение заданного функционала сложности.U — полный класс схем в том смысле, что каждую систему ФАЛ можно реализовать некоторой его схемой Σ.Ψ — некоторый функционал сложности схем класса U, то есть отображение Uна множество неотрицательных действительных чисел.Функционал сложности Ψ обладает свойством монотонности, если Ψ(Σ) ≥Ψ(Σ0 ) , Σ, Σ0 ∈ U, и Σ0 получается из Σ путем удаления вершин или ребер.Сложность Ψ(F ) системы ФАЛ F в классе U — минимальное значение величины Ψ(Σ) на множестве тех схем Σ ∈ U, которые реализуют FМинимальная схема для ФАЛ F в классе U относительно функционала Ψ —такая схема Σ, реализующая F , для которой Ψ(Σ) = Ψ(F ).Функция Шеннона для класса U относительно функционала сложности Ψ —Ψ(n) = max Ψ(f )f ∈P2 (n)Для сложности L(F ) ФАЛ F = F (f1 , .
. . , fm ) в любом изPрассматриваемыхклассов схем выполняются неравенства max (L(fi )) ≤ L(F ) ≤ mi=1 L(f )i0≤i≤mЛемма Для любой функции алгебры логики f (x1 , . . . , xn ) , f 6= 0 существуетформула Ff , Ff ∈ UΦ , и π -схема Σf , которые реализуют f и для которых справедливы неравенства: L(Ff ) ≤ 2n · |Nf | − 1 , L(Σf ) ≤ n · |Nf | (1.1)Следствие В соответствии с леммой из 2.3 параграфа 2 главы 2 (книги) формулу Ff можно выбрать так, что T (Ff ) ≤ dlog n + log |Nf |e + 1Следствие В силу неравенств (1.1) и с учетом того, что ФАЛ 0 можно реализовать π -схемой сложности 2, а так же формулой из UΦ , имеющей сложность 2,выполняются неравенстваLC (n) ≤ LΦ (n) ≤ n · 2n+1 − 1D(n) ≤ n + dlog ne + 1LK (n) ≤ Lπ (n) ≤ n · 2nЛемма Для любой ФАЛ f, f ∈ P2 (n) и f = 0, существуют π -схема Σf и формулаFf , Ff ∈ UΦ , которые реализуют f и для которых, наряду с (1.1), справедливытакже неравенства: L(Σf ) ≤ 2n + |Nf | − 2 , L(Ff ) ≤ 2n+1 + |Nf | − 4.πn+1Следствие L (n) ≤ 2− 2 (1.2)ΦnСледствие L (n) ≤ 3 · 2 − 4 (1.3)Задача синтеза часто возникает для следующих ФАЛ и систем ФАЛ:• линейной ФАЛ порядка n, то есть ФАЛ l(n) или l(n)• мультиплексорной ФАЛ µ(n) порядка n~~ ) порядка n• дешифратора Q(n)(дизъюнктивного дешифратора J(n)1• универсальной системы P~2 (n) порядка n, состоящей из всех различных ФАЛмножества P2 (n), упорядоченных в соответствии с номерами их столбцовзначений.Для любого натурально n выполняются неравенства:~ n ) ≤ 2n+1 − 2~ n ) ≤ 2n + O(n · 2 n2 )(1.4)LK (QLC (QΦn+2πn(1.5)L (µn ) ≤ 2−3L (µn ) ≤ 3 · 2 − 21CC(1.6)L (ln ) ≤ 4n − 4L (ln ) ≤ 4n − 4 + b n cЛемма Если ФАЛ f (x1 , .
. . , xn ) существенно зависит от всех своих БП, тоLC (f ) ≥ n − 1 , LK (f ) ≥ n (1.7). Если при этом ФАЛ f не является монотонной ФАЛ (каждая переменная xi , i ∈ [1 . . . k] не является ни монотнонной, ниинмонотонной БП ФАЛ f ), то LC (f ) ≥ n , LK (f ) ≥ n + k (1.8)LC (ln ) ≥ nLK (ln ) ≥ 2nСледствиеLC (µn ) ≥ 2n + nLK (µn ) ≥ 2n + 2nЛемма Для системы F = F (f1 , . . . , fm ), состоящей из попарно различных ФАЛ,отличных от констант (от переменных), справедливо неравенство: LK (F ) ≥ m(соответственно LCБ (F ) ≥ m)~ n ) ≥ 2n~ n ) ≥ 2nLK (QLC (QСледствиеLK (J~n ) ≥ 2nLC (J~n ) ≥ 2nn2n~LK (P~2 (n)) ≥ 22 − 2LCБ (P2 (n)) ≥ 2 − nCЛемма Для каждого натурального n в UБ существует универсальная СФЭ Unnпорядка n, сложность которой равна 22 − n.Лемма Если разделительная по выходам (1, m)-КС Σ реализует m различныхФАЛ отличных от 0, то L(Σ) ≥ 2m − 2.Следствие Контактное дерево порядка n является минимальной разделительной (1, 2n )-КС, реализующей систему ФАЛ Qn .Лемма Если система ФАЛ F = (f1 , .
. . , fm ) состоит из попарно различныхmPФАЛ от БП X(n), отличных от 0 и 1, то LK (F ) ≥ 21−n|Nfj |j=1Kn+1L (Jn ) ≥ 2−2Пусть вершина w СФЭ Σ не достижима из ее вершины v , а СФЭ Σ0 получаетсяиз СФЭ Σ в результате удаления вершины v , объявления вершины w начальнойвершиной всех исходивших из v дуг и переноса в вершину w всех выходных БП,приписанных вершине v . Тогда СФЭ Σ0 считается результатом применения к СФЭΣ операции присоединения вершины v к вершине w.Две вершины СФЭ называются эквивалентными, если в них реализуютсяравные ФАЛ.Приведенная схема называется строго приведенной, если в ней нет эквивалентных и висячих вершин.CЛемма Для каждого натурального n в UБ существует универсальная СФЭ Un2nпорядка n, сложность которой равна 2 − nМетод каскадов позволяет по произвольной системе функций алгебры логики F = (f1 , . . . , fm ) , F ∈ P2m (n) строить (1, m)-КС Σf , Σf ∈ UK и СФЭUF , U ∈ UC , которые реализуют F .Будем считать, что все f1 , . .
. , fm системы F различны, отличны от констант и длякаждой БП xi , 1 ≤ i ≤ n, среди них есть ФАЛ, существенно зависящая от xi .Разложим ФАЛ f1 , . . . , fm сначала по БП x1 , потом по БП x2 и т.д. При этомпостроим последовательности множеств Gi и Ĝi , состоящих из ФАЛ от БПxi , xi+1 , .
. . , xn , где i = 1, . . . , n такие, чтоСледствие21. Gi состоит из всех различных ФАЛ g(xi , . . . , xn ) видаfj (σ1 , . . . , σi−1 , xi , xi+1 , . . . , xn ) , 1 ≤ j ≤ m , (σ1 , . . . , σi−1 ∈ B i−1 )g=2. Ĝi состоит из всех различных функций g, g ∈ Gi , которые существеннозависят от xi .Следовательно G1 = f1 , . . . , fm , Ĝn ⊆ {xn , xn }, а множества Ĝ1 , .
. . , Ĝn не пустыи попарно не пересекаются.Далее, любую ФАЛ g, g ∈ Ĝi , 1 ≤ i ≤ n, можно представить в виде g =µ(xi , g0 , g1 ) = xi g0 ∨ xi g1 , где gσ = g(σ, xi + 1, . . . , xn ), и, следовательно, gσ ∈Ǧi+1 ∪ {0, 1} для всех σ, σ ∈ B . Если при этом для некоторого σ, σ ∈ B , ФАЛgσ равна 0, то вместо этого неравенства будем использовать разложение g = xσi gσ ,где gσ ∈ Ǧi+1 ∪ {1}.Пусть (1, 1)-КС Σ̌n+1 представляет собой изолированный вход, который одновременно является выходом и реализует константу 1. Пусть, далее, для некоторого i , 1 ≤ i ≤ n, уже построена (1, m̌i+1 )-КС Σ̌i+1 , реализующая систему ФАЛǦi+1 ∪{1}.
Построим тогда (1, m̌i )-КС Σ̌i , которая реализует систему ФАЛ Ǧi ∪{1}следующим образом:1. КС Σ̌i содержит КС Σ̌i+1 в качестве подсхемы, на выходах которой (ониодновременно являются выходами Σ̌i ) реализуются ФАЛ из множества Ǧi+1 ∪{1}2.а здесь большой пункт про то, как это реализуется на схеме. с картинками. стр.20 “Лекции Ложкина (3 часть)“и здесь еще целый абзац заключения о том, как и что. Короче если кому попадется этот вопрос на тесте — неудачнег :(Каскадная КС – приведенная КС без изолированных полюсов, которая может быть получена из системы тождественных вершин в результате ряда операцийприсоединения 1 или 2 противоположных контактов и операций переименованиявыходов.Каскадная КС считается полной, если она была построена без использования операции присоединения 1 контакта. Вершина ККС, введенная с помощьюоперации присоединения 1 контакта, называется неполной вершиной.Будем говорить, что ККС Σ00 является дополнением неполной ККС Σ0 , если онаполучается в результате соединения всех неполных вершин Σ0 отсутствующими вних контактами с новым входом, удаления всех «старых» входов и перехода ксоответствующей приведенной КС.
При этом L(Σ00 ) ≤ 2L(Σ0 )Лемма Для любого натурального n и σ ∈ B выполняются неравенства:nK σL (ln ) ≤ 4n − 4 + b n1 c , LK (P~2 (n)) ≤ 2 · 22KCТеорема Для функций Шеннона L (n) и L (n) выполнены соотношения:2n2nKCL (n) . 4( n ), L (n) . 8( n ), которые вытекают из мощностных соотношений4·2n2nKΣf ∈ UL(Σf ) ≤ n−2 log n + O n2n .8·2nCΣf ∈ UL(Σf ) ≤ n−2+ O 2n2log nПусть U — некий класс схем, Φ — функционал сложности, а Φ(n) — функцияШеннона для класса U относительно Φ. U(Φ, n) — мн-во тех схем Σ , Σ ∈ U,которые реализуют одну ФАЛ из P2 (n) и для которых Φ(Σ) ≤ Φ.nМощностное неравенство вытекает из определений: kU(Φ(n), n)k = 22Если для некоторого натурально n и действительных Φ̂, δ , 0 < δ < 1 выполняется3nnнеравенство kU(Φ̂, n)k ≤ δ · 22 , то Φ(f ) ≥ Φ̂ для не менее, чем (1 − δ) · 22 ФАЛf ∈ P2 (n).Для любых натуральных n и L справедливы неравенства:C|U (L, n)| ≤ (8 · (L + n))L+1|UΦ (L, n)| ≤ (8n)L+1|UK (L, n)| ≤ (8nL)L|Uπ (L, n)| ≤ (16n)L .Лемма Для положительных действительных чисел a, y, q из неравенствlog a log qlog qy, где e –a log q > 1 , (ay) ≥ q следует неравенство y ≥ log a log q 1 + loglog ae log qоснование натуральных логарифмов, а из неравенств a > 1, ay ≥ q – неравенствоlog qy ≥ logaТеорема Для некоторой последовательности ε = ε(n) , n = 1, 2, .
. . ,такой, чтоε(n) ≥ 0 при n ≥ n0 и lim ε(n) → 0, выполняются неравенства:x→∞nn(1 + ε(n)) 2nLC (n) & 2nn22n(1 − ε(n)) logLΦ (n) & lognnn2nK(1 − ε(n)) 2nСледствие L (n) &nn2n2π(1 − ε(n)) logL(n)&nlog nn − log log n − ε(n)T (n) ≥ n − log log n − o(1)Следствие Нижние оценки из теоремы при указанных в доказательстве значениях ε(n) справедливы для сложности (глубины) почти всех ФАЛ f, f ∈ P2 (n),при их реализации в соответствующих классах схем.LC (n) ε = log nn−6LΦ (n) ε = log6 nLK (n) ε = n4Лемма Для класса ФАЛ Q такого, что log n = o(log log |Q(n)|), выполняютсяLK (Q(n) & logloglogQ(n)Q(n)следующие асимптотические неравенстваLC (Q(n) & logloglogQ(n)Q(n)Множество ФАЛ G, G∈P2 (m), называется дизъюнктивноуниверсальным множеством (ДУМ) порядка m и ранга p, если любая ФАЛg, g ∈ P2 (m), может быть представлена в виде g = g1 ∨· · ·∨gp , gi ∈ G ∀i = 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}
