Часть 2 (1132844)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Общефакультетский курс«Основы кибернетики»Осенний семестр 2017–2018 уч. г.группы 311–319лектор — профессор С. А. Ложкин(lozhkin@cs.msu.su)Информационная поддержка курса:http://mk.cs.msu.ru/index.php/Основы_кибернетики_(2-й_поток,_3_курс)II. Основные классыдискретных управляющихсистем, структурныепредставления схем и оценкаих числа. Эквивалентныепреобразования управляющихсистем8 Формулы алгебры логики,их эквивалентныепреобразования с помощьютождеств. Полнота системыосновных тождеств дляэквивалентныхпреобразований формулбазиса {&, ∨, ¬}DΠKΠKτ осн = t&M, t¬M, t&A, t&K, t&OΠ, t&,∨, t1,&, t0,&,τ A = t&A, t∨A ,τ K = t&K, t∨K , OΠ OΠOΠτ = t& , t∨ , DDτ D = t&,∨, t∨,&,ΠKΠKΠKΠKΠKτ = t0,& , t1,& , t0,∨ , t1,∨ ,τeосн = τ M, τ A, τ K, τ OΠ, τ D, τ ΠK, t Π .Утверждение 8.1 Система τeосн выводимаиз системы τ осн.Утверждение 8.2 Любую формулуF (x1, .

. . , xn ), реализующую ФАЛ f , спомощью ЭП на основе системы тождествτ осн можно преобразовать в совершеннуюОДНФ ФАЛ f от БП X (n).Утверждение 8.3 Система τ осн — полнаясистема тождеств.9. Задание формул спомощью деревьев,функционалы их сложности исоотношения между ними.Оптимизация подобныхформул по глубинеУтверждение 9.1 Для формулы F,F ∈ UΦ, вида F = F1 ◦ . . . ◦ Fk , где◦ ∈ {&, ∨}, выполняются неравенстваR (F) = L&,∨(F) + 1 6 L(F) + 1 66 2D (F1) + .

. . + 2D (Fk ) 6 2D (F),где L&,∨(F) — число ФС & и ∨ в формуле F.СледствиеD (F1 )D (Fk )D (F) > log 2+ ... + 2>> dlog(L(F) + 1)e.Утверждение 9.2 Для любой формулы Fс поднятыми отрицаниями из UΦ существуетподобная ей формула F̌ такая,чтоD F̌ 6 dlog (L (F) + 1)e + Alt (F) .Следствие 1. Для любой ЭК или ЭДK существует подобная ей формула Ǩ такая,чтоD (Ǩ ) = dlog(L(K ) + 1)e,которая, минимальна по глубине.Следствие 2. Для любой ДНФ или КНФA существует подобная ей формула Ǎ такая,чтоD (Ǎ) 6 dlog(L(A) + 1)e + 1.10. Схемы изфункциональных элементов.Изоморфизм иэквивалентность схем,функционалы их сложности,операции приведения.Верхние оценки числаформул и схем в базисе{&, ∨, ¬}Утверждение 10.1 Для приведеннойСФЭ Σ, Σ ∈ UC , с одним выходом,выполняются неравенстваR (Σ) 6 L&,∨ (Σ) + 1 6 L (Σ) + 1 6 2D (Σ),где L&,∨ — число ФЭ & и ∨ в Σ.Утверждение 10.2 Для любыхнатуральных n, L, D выполняютсянеравенства ΦU (L, n) 6 (10n)L+1 , ΦU (L, n) 6 (8n)L+1 , ΦU [D , n] 6 (8n)2D .Следствие Число попарно некоммутативно подобных формул споднятыми отрицаниями ранга R отБП x1, .

. . , xn не больше, чем (12n)R .Утверждение 10.3 Для любыхнатуральных n и L выполняется неравенство CU (L, n) 6 (8 (L + n))L+1 .11. Контактные схемы (КС) иπ-схемы, их изоморфизм,эквивалентность, сложность,операции приведения.Структурное моделированиеформул и π-схем. Оценкичисла КС и числа π-схем.Особенностифункционированиямногополюсных схемv s xia)u vs x ib)ssσu v s x-i suc)Рис.

1: типы контактовxq ivqqq?a)xq iquvqq 6qqub)Рис. 2: физическая интерпретация контактовvr3x1rx2ra1 v1x1 v4rx1v2 rb1x2ra1 v1 x1x1 C2C1x2 v2 rb1x 3 C3ra)b)a1 r x 1 r x 2 r x 3 r b2x1x2x3x1x2x3a2 r x 1 r x 2 r x 3 r b1c)Рис. 3: некоторые КС от БП x1 , x2 , x3Утверждение 11.1 Любой π-схеме Σможно сопоставить эквивалентную ейформулу F из UΦ с поднятыми отрицаниямитакую, что R (F) = L (Σ) и обратно.Утверждение 11.2 При любыхнатуральных L и n выполняется неравенствоkUπ (L, n)k 6 (12n)L .Утверждение 11.3 При любыхнатуральных L и n выполняется неравенство KU (L, n) 6 (8nL)L .12. Эквивалентныепреобразования схем изфункциональных элементов имоделирование с их помощьюформульных преобразований.Моделированиеэквивалентныхпреобразований формул исхем в различных базисах,теорема переходаУтверждение 12.1 Если τ — конечнаяполная система тождествдля ЭП формул изΦCBUБ , то τ , τ , τ — конечная полнаясистема тождеств для ЭП СФЭ из UCБСледствиетождеств осн B CСистема— КПСТ для ЭП СФЭ из UC.τ , τ , τУтверждение 12.2 Пусть τ — КПСТ дляЭП формул из UΦБ , а Π0 и Π — системытождеств для перехода от базиса Б к базисуБ0 и от базиса Б0 к базису Б соответственно.Тогда система тождеств {Π0 (τ ) , Π0 (Π)}является КПСТ для ЭП формул из UΦБ .Следствие Из системы тождеств τ осн дляЭП формул из UΦ указанным в утвержденииспособом можно получить КПСТ для ЭПформул в любом базисе Б.13.

Эквивалентныепреобразования контактныхсхем. Основные тождества,вывод вспомогательных иобобщённых тождествУтверждение 13.1 Имеет место(1) (2)выводимость {t1—t5, t6 , t6 } |⇒ {t7—t11}.Утверждение 13.2 При n > 2 имеетместо выводимость τn |⇒ τ (n).14. Полнота системыосновных тождеств иотсутствие конечной полнойсистемы тождеств в классеконтактных схемУтверждение 14.1 Для любой КС Σ, гдеΣ = Σ (x1, .

. . , xn ; a1, . . . , am ) ∈ UK, илюбой эквивалентной Σ КСb (x1, . . . , xn ; a1, . . . , am ) каноническогоΣbвида существует ЭП Σ ⇒ Σ.τnУтверждение 14.2 Для любых двухэквивалентных КС Σ0 и Σ00 от БП x1, . . . , xnсуществует ЭП вида Σ0 ⇒ Σ00.τnСледствие Система τn является КПСТ дляЭП КС из UK от БП x1, . .

. , xn .Следствие Система τ∞ является ПСТ дляЭП КС из UK.Утверждение 14.3 ЕслиΣ0 (x1, . . . , xn ) ⇒ Σ00 (x1, . . . , xn ), то{t1 −t5 }000Θ (Σ ) = Θ (Σ ), а если Σ0 ⇒ Σ00, где k < n,τk000то Θ (Σ ) − Θ (Σ ) делится на 2n−k .Утверждение 14.4 В классе UK несуществует конечной полной системытождеств..

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций