Основы кибернетики - Теормин (часть 3) 2010 (1133257)
Текст из файла
Теормин по Основам Кибернетики (3 часть)версия: 0.31 (08.06.10)автор:перекомилировал в XeLatex:Кунцьо Степан (StepLg)Борисенко Олег (al-indigo)mailto:stepLg@gmail.comal@somestuff.ruЗадача синтеза — построение по заданнои системе функции реализующеиее схемы, которая принадлежит к заданному классу и на которои достигаетсяминимальное значение заданного функционала сложности.U — полныи класс схем в том смысле, что каждую систему ФАЛ можно реализовать некоторои его схемои Σ.Ψ — некоторыи функционал сложности схем класса U, то есть отображениеU на множество неотрицательных деиствительных чисел.Функционал сложности Ψ обладает своиством монотонности, если Ψ(Σ) ≥Ψ(Σ′ ) , Σ, Σ′ ∈ U, и Σ′ получается из Σ путем удаления вершин или ребер.Сложность Ψ(F) системы ФАЛ F в классе U — минимальное значение величины Ψ(Σ) на множестве тех схем Σ ∈ U, которые реализуют FМинимальная схема для ФАЛ F в классе U относительно функционала Ψ —такая схема Σ, реализующая F, для которои Ψ(Σ) = Ψ(F).Функция Шеннона для класса U относительно функционала сложностиΨ — Ψ(n) = max Ψ(f )f ∈P2 (n)Для сложности L(F ) ФАЛ F = F (f1 , .
. . , fm ) в любом из рассматриваемых∑классов схем выполняются неравенства max (L(fi )) ≤ L(F ) ≤ mi=1 L(f )i0≤i≤mЛемма Для любои функции алгебры логики f (x1 , . . . , xn ) , f ̸= 0 существуетформула Ff , Ff ∈ UΦ , и π-схема Σf , которые реализуют f и для которых справедливы неравенства: L(Ff ) ≤ 2n · |Nf | − 1 , L(Σf ) ≤ n · |Nf | (1.1)Следствие В соответствии с леммои из 2.3 параграфа 2 главы 2 (книги) формулу Ff можно выбрать так, что T (Ff ) ≤ ⌈log n + log |Nf |⌉ + 1Следствие В силу неравенств (1.1) и с учетом того, что ФАЛ 0 можно реализовать π-схемои сложности 2, а так же формулои из UΦ , имеющеи сложность 2,выполняются неравенстваLC (n) ≤ LΦ (n) ≤ n · 2n+1 − 1D(n) ≤ n + ⌈log n⌉ + 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.2Следствие Lπ (n) ≤ 2n+1 − 2 (1.2)Следствие LΦ (n) ≤ 3 · 2n − 4 (1.3)Задача синтеза часто возникает для следующих ФАЛ и систем ФАЛ:• линеинои ФАЛ порядка n, то есть ФАЛ l(n) или l(n)• мультиплексорнои ФАЛ µ(n) порядка n⃗⃗• дешифратора Q(n)(дизъюнктивного дешифратора J(n))порядка n• универсальнои системы P⃗2 (n) порядка n, состоящеи из всех различныхФАЛ множества P2 (n), упорядоченных в соответствии с номерами ихстолбцов значении.Для любого натурально n выполняются неравенства:⃗ n ) ≤ 2n + O(n · 2 n2 ) LK (Q⃗ n ) ≤ 2n+1 − 2LC (Q(1.4)Lπ (µn ) ≤ 3 · 2n − 2LΦ (µn ) ≤ 2n+2 − 3(1.5)LC (ln ) ≤ 4n − 4LC (ln ) ≤ 4n − 4 + ⌊ n1 ⌋ (1.6)Лемма Если ФАЛ 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 ) ≥ 2nLC (µn ) ≥ 2n + n LK (µ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 ) ≥ 2nnnLCБ (P⃗2 (n)) ≥ 22 − n LK (P⃗2 (n)) ≥ 22 − 2Лемма Для каждого натурального n в UCБ существует универсальная СФЭ Unnпорядка n, сложность которои равна 22 − n.Лемма Если разделительная по выходам (1, m)-КС Σ реализует m различных ФАЛ отличных от 0, то L(Σ) ≥ 2m − 2.Следствие Контактное дерево порядка n является минимальнои разделительнои (1, 2n )-КС, реализующеи систему ФАЛ Qn .3Лемма Если система ФАЛ F = (f1 , .
. . , fm ) состоит из попарно различныхm∑ФАЛ от БП X(n), отличных от 0 и 1, то LK (F ) ≥ 21−n|Nfj |j=1Следствие L (Jn ) ≥ 2Kn+1−2Пусть вершина w СФЭ Σ не достижима из ее вершины v, а СФЭ Σ′ получаетсяиз СФЭ Σ в результате удаления вершины v, объявления вершины w начальноивершинои всех исходивших из v дуг и переноса в вершину w всех выходных БП,приписанных вершине v. Тогда СФЭ Σ′ считается результатом применения кСФЭ Σ операции присоединения вершины v к вершине w.Две вершины СФЭ называются эквивалентными, если в них реализуютсяравные ФАЛ.Приведенная схема называется строго приведенной, если в неи нет эквивалентных и висячих вершин.Лемма Для каждого натурального n в UCБ существует универсальная СФЭnUn порядка n, сложность которои равна 22 − 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 такие, что1. Gi состоит из всех различных ФАЛ g(xi , . . . , xn ) вида g=fj (σ1 , . . . , σi−1 , xi , xi+1 , . . . , xn ) , 1 ≤ j ≤ m , (σ1 , .
. . , σi−1 ∈ B i−1 )2. Ĝi состоит из всех различных функции g, g ∈ Gi , которые существеннозависят от xi .Следовательно G1 = f1 , . . . , fm , Ĝn ⊆ {xn , xn }, а множества Ĝ1 , . . . , Ĝn не пусты и попарно не пересекаются.Далее, любую ФАЛ g, g ∈ Ĝi , 1 ≤ i ≤ n, можно представить в виде g =4µ(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 контакта, называется неполной вершиной.Будем говорить, что ККС Σ′′ является дополнением неполнои ККС Σ′ , еслиона получается в результате соединения всех неполных вершин Σ′ отсутствующими в них контактами с новым входом, удаления всех «старых» входов иперехода к соответствующеи приведеннои КС. При этом L(Σ′′ ) ≤ 2L(Σ′ )Лемма Для любого натурального n и σ ∈ B выполняются неравенства:nLK (lnσ ) ≤ 4n − 4 + ⌊ n1 ⌋ , LK (P⃗2 (n)) ≤ 2 · 22Теорема Для функции Шеннона LK (n) и LC (n) выполнены соотношения:nnLK (n) . 4( 2n ), LC (n) .
8( 2n ), которые вытекают из мощностных соотноше5нииΣf ∈ UK L(Σf ) ≤4·2nn−2 log n8·2nn−2 log n+O( 2n )2n( 2n ) .Σf ∈ UC L(Σf ) ≤+ O n2Пусть U — некии класс схем, Φ — функционал сложности, а Φ(n) — функция Шеннона для класса U относительно Φ. U(Φ, n) — мн-во тех схем Σ , Σ ∈ U,которые реализуют одну ФАЛ из P2 (n) и для которых Φ(Σ) ≤ Φ.nМощностное неравенство вытекает из определении: ∥U(Φ(n), n)∥ = 22Если для некоторого натурально n и деиствительных Φ̂, δ , 0 < δ < 1 выполnняется неравенство ∥U(Φ̂, n)∥ ≤ δ · 22 , то Φ(f ) ≥ Φ̂ для не менее, чем (1 − δ) · 22nФАЛ f ∈ P2 (n).Для любых натуральных n и L справедливы неравенства:|UC (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 qlog log a log qya log q > 1 , (ay) ≥ q следует неравенство y ≥ log a log q 1 + log ae log q , где e– основание натуральных логарифмов, а из неравенств a > 1, ay ≥ q – неравенство y ≥log qlog aТеорема Для некоторои последовательности ε = ε(n) , n = 1, 2, .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
