С.В. Яблонский - Введение в дискретную математику (1060464), страница 53
Текст из файла (страница 53)
Тогда ~24[ рФ Ь (Е) н, й2" + я2" ' + 2"+'+ —, причем й2" о~ — ), п2™ о (-„), 2"+' о (-), хв зв з в' Поэтому )~в' В силу произвольности функции ~(хь ..., Е.) отсюда следует, что йв Ь(л) н,, —. Соединяя полученные соотношения с теоремой 2, мы за- вершаем доказательство. $7. Синтез сумматора Общая теория синтеза схем из Ф, Э. приводит к важному выводу о том, что большинство булевых функций (при и- ~) имеет сложные минимальные схемы. Это означает, что практическую ценность с точки зрения синтеза представляет весьма узкий класс булевых функций. Позтому наряду с универсальными методами синтеза необходимо иметь методы синтеза, приспособлеп- гл. з. синтиз схим из фиткциональных элкмкнтов Зсз ные к отдельным классам булевых функций, полнее учитывающие свойства отдельных функций.
В етом параграфе мы поанакомимся с одним из подходов к реализации достаточно узкого класса функций. Речь пойдет о построении многополюсной схемы из функциональных элементов, реализующей сложение двух чиФг д, сел, заданных в двоичной системе счисления Л Лг,1...Х„ У У»У»-1 ° ° ° У1 ° Для этого рассмотрим хорошо известный алгоритм сложения чисел я и у «столбиком» (дл+1дл" д1) Ил ° » ° К1 + У» * ° У1 Зл+1З» ° » ° З1 Здесь числа д +1, ..., д~ обозна. «ул ЭЛ У« д)м гг Рве. 18 чают результаты переносов из предыдущих разрядов (да 0). Очевидно, з~ х1+ у~+ д,(шоб 2), д,+, х,у< Ч л,д, Ч у,дь Основываясь на тождестве »и»д -Т»»Лают»»)»( Ч» ~»)'~ »».
легко получить схему, реализующую соответствующее 368 ч у нккотогые пР<тлох<ен<!я к клввннктикн преобразование величин хь уь д< в г<, д«.< (см. рис. 28). Обозначим данную схему через В,(1 <1< и). Тогда искомая схема Մ— сумматор для двух и-разрядных двоичных чисел — получается путем последовательного соединения блоков В< (см.
рис. 29). Здесь г„„= д.+„и блок В, осуществляет преобразование г, = х, + у, х<у,(х< Ч у ), у< х<у<. Очевидно, Т (В<) 4 и Е(В,) - 9 при 1 < 1 < и, Такам образом, Ь(Х„) й 9(п — 1)+ 4 — 9п — 5 < 9п.
$8. Синтез схем ив Ф.Э., реализующих симметрические функции Другим. интересным классом двоичных преобразований является класс так называемых симметрических функций. Определение. Булеза функция В(х„..., х„) называется симметрической, если она является симметрической относительно всех переменных х„..., х., т. е. если для любого набора (а„..., а„) н любой полста- (1...н ') нонки ~. имеет место 'ч(г ° . (« l о (а;,, ..., а,„) Ю (а„..., а„). Классу симметрических функций, очевидно, принад- лежат константы 0 и 1, функции х„х< б< х,, х, ~/ т„х, + + х<, х<хг Ч х<х< Ч х<хг и т.
д. Легко видеть, что если для набора (а„..., а.) Я(а„..., а.) 1, и (а„..., а„) содержит ровно 1 единиц, то для любого набора (ам ...> а„), содержащего также ровно 1 еди- ниц, В(а„..., а„) ° 1. В таком случае симметрическая функция Я(хь ..., х.) характеризуется списком своих рабочих чисел ..., 1,(0 < 1, «... 0 < и), обозначавших число единиц в наборах (а„ ..., а„), для которых В(а„..., а ) 1.
гл. х синтяз схим из фтнкционлльных злхмвнтов 331 Поэтому можно писать Я(ха, ..., х„) Яви...,а„(ха, ...,х„), где индексы $„..., 1, — рабочие числа функции Я(х„.. э ..., х„). Например, хэна аэ хвхв аз каха = 8а, а(хээ ха, хв) ° Рассмотрим вспомогательное преобразование (савв ° ° ° э иа) ~ 1(аа,...,аа)э где Е<„,...,,а„> — число единиц в наборе (цо ..., и ). Это преобразование будет реализо- э вано многополвсником Е„нз е,— е, функциональных элементов (см. рис. 80), в котором на ~багга! в выходах г„,, г,„„+, по- Рнс.
30 является двоичная запись числа 1 „ „ когда на вход поступает набор (а„ ..., и„). Пусть и = 2 . Тогда (1ойа н) + 1 па + 1. Л е и и а 5. Можно построить многополюсник Х„, осуществляющий в вышеуказанном смысле преобразование (ага, . ° °, иа) э Е(аа„.„,аа)э и С(Хээ)(18п — 9 1оя и — 18. Доказательство проводится индукцией по па. ва вав мв Рнс.
32 а) Базис индукции па О. Здесь п 1 и искомая схема Ев имеет внд (см. рнс. 31), Ь(Еэ') О. С другой стороны, 18п — 9 1ойа п — 18 О при и 1. 333 ч. у. некотОРые пРиложения к кинеРнетикн Следовательно, неравенство Ь (Е ) ~ 18п — 9 1о9 и — 18 справедливо для и 1. б) Индуктивный переход от пд — 1 к т(пд— 1 > 0) осуществляется прн помощи схемы Х (см, 7 (д«3 в]+Ф ттг Рве. 33 рис. 82). Эта схема «делит» набор (а„„., а ) на две части (а„..., а д) н (а»я-д«о „.,а,„,), в каждой ча- 1 сти под схемамн 2» -д вт вычисляется число единиц Ф в и 1", аатем сумматор «1 в]+! Х+ «складывает» 1' и 1", «1 в]т и на выходе вычисляется Рве. 34 число единиц исходного набора.
Мы имеем д (Х .) = 2Ь(2, -д ) + Ь(Х+), или Ь(Х„) 2Ь(2„~») + Ь(Е+)~2(18 —" — 91об — — 18) + + 9 1об»п ( 18п — 9 )ой и — 18. Лемма докааана. Следствие. б(Х»н)(18 2', т. е. при и ° 2" Х (Х„)(18п. Лемма б.,ддля любоео и мол«но построить лногополюснин Х„, осуществляющий преоброеовоние (ад. ..., а„)-» 1( д„,,,вв)д и Ь(Х„)~Збп, Гл.
3. синтез схем пз Функц110ЕАлъных злементов $66 Доказательство. Очевидно, существует такое п1, что в~ 2 с2п. Искомый многополюсник 2 может быть реализован так, как зто показано на рис. ЗЗ. У многополюсника 2., берутся первые (1о61 п1+ 1 выходов: Ь(2'„) Ь(2р)+ 2«„18 2"'+ 2а ,'18(2п — 1) + 2а,',Збп. Утверждение доказано.
Теорема 8. Суи1естеует константа С, такая, что любая симметрическая у1унк11ия 811 „,«„(х„..., т„) может быть реалиеоеана схемой Ез(„„„„„„) такой, что ~(21(*„..., *„))~ Свп. Доказательство. Искомая схема о 1,1,...,е,) может быть построена так, как зто показано на рис. 31. Здесь схема Х„преобразует набор (сг„..., и„) в двоичный код 1(о„..„пер Схема 2,', реализует булеву функцию от (1ойзв)+ 1 переменной, и зта функция на енаборахэ1(и„...д„), совпадающих с 1„..., 1„равна 1, а в остальных случаях равна нулю. Мы имеем (см. теорему 7) ~ 1оз,п)+1 16п ЦЕз~(, „.„,„))~ Збп + ~ Збп + 1 откуда следует существование константы С„о которой говорилось в теореме.
Теорема доказана. СПИСОК ЛИТЕРАТУРЫ 1. Васильев Ф.П. Численные методы решения акстремальиых задач.— Мс Наука, 1980. 2. Васильев Ю. Л. О сравнении сложности тупиковых и мявимальвых диаъюиктивкых нормальных форм.— В кил Проблемы кибернетики. Вып. 10.— Мс Фвавгатгиз, И63, с. 5 — 61. 3 Г а в р и л о в Г. П., С а п о ж е и к о А. А.
Сборник вадач по дискретной математике.— Мл Наука, 19?7. 4. Дяслретиая математика и математические вопросы ииберветики/Под ред. С. В. Яблоневого и О. Б. Лупанова. — Мл Йаука, 1974. 5. Журавлев Ю. И, Об отделимости подмножеств вершин ямерпого единичного куба.— В кяа Труды МИАН СССР. Т. 51.— Мс Изд-во АН СССР, 1958, с. 143 — 157. 6. Журя вл ее Ю. И. Об алгоритмах упрощения дпаъюиктиввых нормальных форм.— ДАН СССР, 1960, 132, № 2, с. 260 — 263. 7.
Зыков А. А. Гиперграфы.— УМН, 1974, 2в9, № 6, с. 89 — 154. 8. Плыл в В. А., Садовничий В. А., Сеидов Б. Х. Математический анализ. — Мс Наука, 1979. 9. Кратко М. И. Алгоритмическая веразрешиввость одной еадачи иа теории конечных автоматов.— В киа Дискретный анализ, Вып. 2.— Новосибирск, 1964, с. 37 — 41. 10. Кратко М. И, О существовайви иерекурсиввых базисов конечных автоматов.— Алгебра и логика, 1964, 3, № 2, с. 33 — 44. М.
Кудрявцев В, Б. Теорема полноты для одного класса ав; томатов без ооратных связей.— В кпс Проблемы киберветиья. Вып. 8.— Мс Фиаматгиэ, 1962, с. 91 — 115. 12. К уд р я в це в В. Б. О мощностях множеств иредполиых множеств некоторых функциональных систем, свяаапяых с автоматами.— В квл Проблемы кибернетики. Вып. 13. Мл Наука, 1965, а 45 — 74. 13. Кудрявцев В.
Б., Алешив С. В., Подколаии А. С. Введевие в теорию автоматов.— Мс Наука, 1986. 14. Кудрявцев Л. Д. Курс математического ввалила. Т. 1 — 2.— Мс Высш. шк., 1981. 15. Куэвецов А. В. О проблемах тождества и фуякциовальяой полноты алгебраических светам.— В кна 'Груды 3-го Всесоюаного мат. съезда. Т. 2.— Мс Ивд-во АН СССР, 1956, о. 145-146. 16. К у а не цо в А. В. О бесповторяых ковтактвых схемах и бесповторных суперпоавциях фувкций алгебры логики.-В ки.: Труды МИАН СССР. Т. 51.— Мс Иад-во АН СССР, 1958, с. 1М- 225. СПИСОК ЛИТЕРАТУРЫ 37! 17. Лупан он О. Б.
О возможностях синтеза схем из провзвольных алементов.— В кнл Труды МИЛН СССР. Т. 51.— Мл Издво АН СССР, 1958, с. 158 — 173. 18. Луп а нов О. Б. О синтезе некоторых классов управляющих систем.— В кнл Проблемы кибернетики. Выл. 10.— Мл Физивтгиз, 1963, с. 63 — 97. 19.
Луп апов О. Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования.— В кнл Проблемы квбернетики. Вып. 14.— Мл Наука, 1965, с. 3! — !Ю. 20. Л уланов О. Б. Аснмптотические оценки сложности управля>ощих систеы.— Мл Пзд-во МГУ, 1984. 2!. Ляпунов А. А. О логических схемах программ.— В кнл Проблемы кибернетики. Вып.
1.— Мл Физматгив, 1958, с. 46 — 74. 22. Ма рк он Ал. А. Об алфавитном кодировании. 1.-ДАН СССР, 1960. 132, № 3, с. 521 — 523. 23. Марков Ал. А. Об алфавитном кодировании. П.— ДАН СССР, 1961. 139, № 3, с. 560 — 56!. 24. Марков Ал. А. Перекуррентпое кодирование.— В кнл Проблемы кибернетики. Вып. 8.— Мл Фкзматгив, 1962, с. 169 — 186. 25. Марков А. А. Введение в теорию кодировании.— Мл Наука, 1982. 26. Н и к о л ь с к и й С. М. Курс математического анализ>ь Т. 1 — 2.— Мл Наука, 1983. 27.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
