Главная » Просмотр файлов » Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике

Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 33

Файл №1132701 Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике.djvu) 33 страницаГ.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701) страница 332019-05-12СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 33)

Найти вес о.-д. функции, получающейся из о.-д, функции 1 с помощьк> операции отоясдествления входных переменных х, и х, (операция 01): 1) У: а) 1 = 1, у = 2; б) 1 = 2, у = 3; 2) 1: а) 1 = 1, 1 = 2; б) 1 = 2, 1 = 3; 3) ф: 1, 1 = 2; б) 1 = 1, 1 = 3; в) 1 = 2, ф = 3; а) 1= У1(») = х1(») — 1 (хг(»)1» хз(»)) Ч(» — 1), уг(») Ч(» 1) е х1(») хг(»)~ Ч(») = Ч(» — 1) У хг(»). хз(»), Ч(0) = О,. 4) 1 а) 1 = 1,,1 = 2; б) 1 = 1, 1 = 3; в) 1 = 2, г = 3 2.12. Найти все суперпозиции»"1(»"2)., если: 1) ф1.' У1(») = х1(»)'~Ч1(» — 1), Уг(») = хг(»)'Чг(» 1) Ч1(») = х1(») У Ч1(» — Ц, 12: Чг(») = хг(») Чг(» — 1) Ч,(О) =О, Ч,(0) = 1; 3) ф1: у(») = х1(») -+ хг(») Ч1(» — 1), Ч1(») = хг(») — ~ хз(»)' Чг(» — 1) Чг(») = х1(») хг(») У Ч1(» — 1), Ч1(0) = Чг(0) = О, у(») — х1(») 1» хг(») ' Ч1(» 1)", Ч1(») Чг(» 1) + Ч1(» 1)~ Чг(») =* (») У-хз(») УЧ1(»-1) Ч,(0) = Чг(0) = О, У1(») — х1(») ' х2(») е Ч(» 1) уг(») = х1(») .

хз(») — 1 хг(»), Ч(») = хз(») '» Ч(» — 1) Ч(0) = 1, у (») =Ч (» 1) 2) 11. Ч1(») = х1(») Ч1(» — 1), 12 Ч,(О) =1, У1(») = х1(») — + Ч1(» — 1), Ч (») =Ч1(» — 1) Ч1(0) = О, У (»)=Ч (» — Ц, Чг(») = хг(») У Чг(» — 1) Ч,(О) =О; 1" х. Анаграммы, н)абянцы, канонические уравнения, схемы 159 функция уг задается диаграммой Мура, изображенной на рис. 4.53; цб) () 0" цц 1 0 0(0)ц1 0(0) а б Рис. 4.53 Рис. 4.54 0(Ц 0(1) 0(1) цо) Ц1) цц Рис. 4.55 4) функции )"1 и )2 задаются диаграммами Мура, изображенными на рис. 4.54, а, б соответственно; 5) функции 11 и уг задаются диаграммами Мура. изображенными на рис. 4.55, а, б соответственно. 3. Реализации ограниченно-детерминированных функций схемами. Понятие схемы, реализующей о.-д, функцию, и определение соответствующих операций над схемами даны в и.

2. В настоящем пункте представлены некоторые задачи, относящиеся к схемам, реализующим о.-д. функции из множества Рг, . Пример 8. Построить схему, реализующу)о о.-д. функцию у из Рг од над множеством, состоящим из элемента единичной задержки и функций, порожденных дизъюнкцией, конъюнкцией и отрицанием: У1(е) = х1(е)'Ч1(1 1)1) хг(е)'хз(е) Уг(1) Чг(е 1) е х1(1) )) хзФ~ Ч1(х) = Ч1(1 — Ц ей Чг(1 — 1), Чг(2) = х1(2).хг(Г) Ч1(2-1), Ч,(0) = Ч,(0) = 0. Решение. Сначала строим схему из функциональных элементов над множеством, состоящим из дизъюнкции, коныонкции и отрицания, для следующей совокупности булевых функций: у1 = х1 Ч1')) хг хз, Уг=Чгчхзчхз, Ч1 Ч1 'Ч2 ))Ч1'Чг; Ч2 — х1 х2 ' Ч1. 160 Гл.

17. Ограниченно-дегаерлеинирооанные функции (При выписывании этих функций мы воспользовались эквивалентными соотношениями для функций алгебры логики: т -+ у = и 'ч' у и и ~В у = тд Чиу.) Схема из функциональных элементов, реализующая систему функций (*), имеет пять входных каналов (по переменным иы из, хз, дз Рис.

4.56 и уз) и чотыре выходных (по переменным уы дз, у' и у' ). Обозначим эту схему через Е*. Она представлена на рис. 4.56. Светлыми кружочками на ней обозначены входные и выходные полюса, а темными кружочками - внутренние полюса. Функциональныс (логические) элементы, реализующие дизъюнкцию, конъюнкцию и отрицание, изображены в виде треугольников с двумя (для дизъюнкции и конъюнкции) или одним (для отрицания) входными каналами.

У каждого функционального элемента один выходной канал. Около выходных полюсов элементов указаны булсвы функции, реализуемые такими подсхемами схемы Е', у которых входы совпадают с входами схемы Е*, а выходами являются данные выходы элементов. В треугольниках, соответствующих элементам, реализующим конъюнкцию, изображен знак ег; элементы, реализующие отрицание, помечены знаком 1. Лля получения схемы Еу, реализующей о.-д. функцию у, достаточно к выходам д' и а' схемы Е* присоединить последовательно у 2.

11иаераммвь тааблиивь канонические уравнения, схемы 161 элементы единичной задержки (опсрация супсрпозиции) и затем ввести обратную связь по парам каналов уха — е71 и дз — е7з, где да выходной канал элемента единичной задержки, подсоединенного к выходу у,'. схемы Е*.

Схема Ху приведена на рис. 4.57. (Нули около элементов единичной задержки, поставлены нами для того, чтобы лишний раз напом- ! (1 — 1) Рис. 4.57 нить, что в момент времени 1 = 1 выходные символы этих элементов равны О.) Пример 9. По схеме Еу, реализующей функцию 1 (рис. 4.58), построить канонические уравнения, задающие эту функцию. Рис. 4.58 11 Г. П.

Гаврилов, А. А. Свиоженио 162 Гл. 17. Ограниченно-деигерминированные функции Решение. Удаляя из схемы Ху задержки, получаем Еу схему из функциональных злементов, изображеннукв на рис. 4.59, с дополнитвльными выходными (Ч~г и Чг) и входными (Чг и Чг) полюсами. Рис. 4.59 Выписывая функции проводимости для каждого выходного полюса, имеем Уг лг 'хгч'Чы У2 Ч1 ' (Хг Ч Чг)~ Чг — — тг ГЬ'к ч Чг — — лг ~Э лг Чг, Ч. = (Хг хг е9 Чг) хг = (тг Чг) хг Теперь для получения канонических уравнений, описывающих работу схемы Еу, нужно учесть время и начальные условия; Уг(г) = лгй)' иг(г) Чг Чг(е — 1): угу) Чг(1 1)' (иг(1) " Чг(1 1))~ Чг(1) = тгф ЧЗЯ21г) Чг(1 — 1), Ч212) = (иг® Чг(г — 1)) тг(г) Ч,10) = Чг(0) = 0.

Пример 10. Выписать канонические уравнения для функций, реализуемых схемами, изображенными на рис. 4.60. (Схемы, изображенные на рис. 4.60, а и, соответствуют пп, а) к) решения.) Решение. а) Схема реализует функцию Ял) = уи192 (и)), где уи(2) о.-д. функция, порожденная функцией У из Рг. На «языке 2" Я. Анаграммы, епабаииеь канонические ураенения, схемы 163 (е) х(1) х(1) х(1) и)2 (1) у(1) о у(1) о у(1) Рис.

4.60 последовательностей» функция Ях) описывается следующим соот- НОШЕНИЕМ: 11(Хы) = 1Х(1) Х(2)... Х(1)... ИСХОдя ИЗ НЕГО МОЖЕМ СраЗу написать канонические уравнения: у(1) = 0(1 — 1) д(1) = х(1), а(О) = О. 11* 164 Гж 1г'. Ограниченно-детер)нинированные функции Приведем еше одно решенис этой задачи. Ясно, что данная схема является суперпозицией двух схем, одна из которых реализует единичнУю задеРжкУ У),(т), а дРУгаЯ фУнкцию 1и(2). Канонические уравнения этих функций можно записать в следующей форме: дз(1) = Ч~(1 — 1), дз)'г) = г)1), Ч) (х)) Чз(1) = х)1), 1и12)) е12)1) = О, Ч,<О) = О.

Ч,(О) = О. Значит, канонические уравнения суперпозиции 12(т) = 9-,(у)Г(в)) имед(1) = Чз(1 — 1); Чз )1) = х(1) Ч2Я =О, Ч,(О) = Ч,(О) = О. Вес функции 12(х) равен 2 (переменная Чз является «фиктивной»), и поэтому «приведенные» канонические уравнения для нее выглядят У(1) = Чз(1 — 1) ~,(*): Чз(1) = тЮ Чз(О) = О. (Эти уравнения с точностью до обозначения переменных такие же, как и выписанные выше.) б) Очевидно, что данная схема реализует функцию 12(т) = = 12)1 — (и)); где Л(х) о.-д, функция из примера а). Следовательно, 12(х ) =1т — «единичная задержка с начальным выходом, равным 1», и д(1) = Ч(1 — 1), 12)и) ° Ч)1) ~'1): Ч<О) = О.

в) Схема реализует функцию 1"з(х) = )р Я (и)). Значит, 1"2(х' ) = = 01т(1) х(2)... х(1)... Далее, так как функции у)з и ~з задаются следуюшими каноническими уравнениями: У211) = Чз(1 У2 (1) Ч2 )1 1) ~ у)~(и1)) Ч1)1) из(1) 11)кг)' Ч2М х2)1) Ч (О) = О, Ч2(0) = О, то имеем У(1) Чз (1 у ( )), )11(1) = Ч2(1 1) Ч2(1) = х(1), Ч,(0) = Ч2(0) = О. г) Данная схема реализует о.-д. функцию )*) = г )г - е )*) - ) )и) и рвз 2" х.

Анаграммы, хаабяииеь канонические уравнения, схемы 1бб — задержку на и тактов. Очевидно, что уо~ (х ) = 00... Ох". Канон рве нические уравнения этой функции выглядят так: у(1) =у (1 — 1), Ч1 (1) — Чз (е 1) у — (1) = Чн(1 — 1), Чн(1) = хИ), у2(0) = уз(0) = ... = ун(0) = О. д) Обозначим функцию, реализуемую этой схемой, через ув(х). От переменной и она зависит несущественным образом. Для получения ео канонических уравнений возьмем единичную задержку с двумя выходами, у и уы и введем обратную связь по переменным х и уы Канонические уравнения единичной задержки с двумя выходами у и у1 выглядят так у(1) = у(1 — Ц, уз(1) = Ч(1 — 1), Ч(1) =*(), ' д(0) = 0. Вводя обратную связь по каналам и и уы имеем у(1) = д(1 — 1),. А(х): у(1) = Ч(1 — 1) а(0) = 0.

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

Тип файла
DJVU-файл
Размер
3,29 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6367
Авторов
на СтудИзбе
309
Средний доход
с одного платного файла
Обучение Подробнее