Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 61
Текст из файла (страница 61)
равно 2г Глава Х РЕАЛИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ СХЕМАМИ И ФОРМУЛАМИ й 1. Схемы из функциональных элементов Схемой из функциональных злементаов (СФЭ) называется ориентированнал бесконтурная сеть с помеченными вершинами. Полюса сети делятся на входные (входы) и выходные (выходы). Входные полюса помечаются символами переменных (иногда также символами отрицаний переменных или констант).
Каждая вершина, отличная от входа (внутренняя вершина), помечается функциональным символом 1или символом логической связки). При этом должны выполняться следующие условия: Ц полустепень захода каждого входного полюса равна нулю; 2) полустепень захода каждой вершины, отличной от входного полюса, равна числу мест функционального символа (или логической связки), которым эта вершина помечена. Множество функциональных символов или связок, используемых для пометки внутренних вершин СФЭ, называется базиса,м схемьь Термин «базис» употребляется здесь в смысле, отличном от того, который принят в гл.
П, поскольку в данном случае но предполагается ни полнота системы функций, составляющих базис, ни ее неизбыточность. Например, принято говорить о схемах в базисе ~Ч, ьс, — ) (этот базис будет называться стандартным) или в базисе 1ез, ьс ). На рис. 10.1, а представлено изображение СФЭ. Входы помечаются свотлыми кружками, внутренние вершины темными кружками, а выходы -- двойными кружками.
Лругой способ изображения схем иллюстрируется рис. 10.1, б. Здесь входы, как и ранее, изображаются светлыми кружками, каждая внутренняя вершина заменена треугольником, внутрь которого помещена пометка (функциональный символ). К одной из сторон треугольника присоединены входы элемента, а вершина треугольника, противоположная этой стороне, является выходом элемента. Выходы схемы отделены от функциональных элементов и обозначены, как и прежде, двойными кружками. Выходам иногда будут приписываться символы функций, реализуемых в них.
Понятие функции, реализуемой 307 З' д Схемы иэ фуннционавьных элементов Рис. 10.1 в вершине схемы, определим по индукции следующим образом. Если СФЭ не содержит функциональных элементов, то каждая ее вершина является входом. В этом случае функция, реализуемая в вершине, тождественно равна переменной (или отрицанию переменной), приписанной соответствующему входу. Пусть для СФЭ, содержащих не более т > 0 элементов, для каждой вершины функция, реализуемая в ней, определена. Рассмотрим произвольную СФЭ Б с ха+ 1 элементами.
Поскольку СФЭ является ориентированным бесконтурным графом, то существует вершина с нулевой полустепенью исхода. Удаляя эту вершину, получаем СФЭ с т элементами, в которой по предположению индукции каждой вершине можно однозначно сопоставить функцию, реализуемую в этой вершине. Пусть удаленная вершина и имела полустепень захода, равную и, и вершине был приписан и-местный функциональный символ г. Пусть, кроме того, в Й вершинах, из которых дуги выходили в вершину о, реализуются функции 1з(хы ..., ха), ..., 1~,.(хы ..., х„).
Тогда определим функцию еэе, реализуемую в вершине и, равенством ре(е,....., х„) = 7((,(х„..., .х.)....., Л,(х|, .... х.)). Заметим, что при этом входы функционального элемента считаются упорядоченными. Будем говорить, что функция 1" реалиэуееася схемой, Б, если в Е существует выход, в котором реализуется функция 1. Сложностью СФЭ будем называть число вершин, не являющихся входами (т.е. число функциональных элементов). СФЭ Е называется минимальной, если она имеет наименьшую сложность среди всех СФЭ, реализукещих функции, реализуемые схемой Х.
Сложностью булевой функции 1 (системы функций А = ( (ы ..., 1т)) в классе СФЭ в базисе Б называется сложность минимальной СФЭ в базисе Б, реализующей функцию 1 (систему функций А). Сложность схемы Е (функции 1, системы функций А) в базисе Б обозначается через Бв(Х), (Ьв(Д, Лв(А))). В дальнейшем, если базис СФЭ не указывается, подразумевается, 308 Гл. Х. Реализаиия булевых фуикиий схемами и формулами что это СФЭ в стандартном базисе (дс, й, — ). При этом символ Б в обозначении сложности схемы или функции будем опускать и пи- сать Л(Е) и ь(у). Везде в дальнейшем связки дд, Й,.
бд, ~, 4, -э, являются двухместными. Б=(Й, дс, — ); хдхз) уг = хд хг, Уг = хг ег хз)~ Б= (.Ц: Ч тзхд, хд ддхг ддхз, хдхгхз); Б= (!); а)Б=(бз, Й,-), б) 4) Ф = (уд — — хдтг Ч хгхз а) Б=(й,дд', — ), б) 5) Ф = (Л = хдхг ''хгтз а) Б=(Й.,Ч, — ), б) 1.1. Лля заданной функции 1(хл а) построить СФЭ в стандартном базисе сложности, не превосходящей т: Ц Д(х~) = хд . хг, т = 2; 2) Д(х~) = х, тг, т, = 4; 3) дс(х~) = хдхг дд хгхз и хзхд, т = 4; 4) Д(хз) (0111 1110) т = 6 5) ~(хз) (0001 111Ц, т = 2; 6) д'(х~) = (1000110Ц, т = 4; 7) д" (х~) = (0110100Ц, т = 8. 1.2.
Лля заданной функции 1(х") построить формулу в базисе Б: Ц,д'(хг) = хд бд хг, .а) Б = ($, — ), б) Б = ( — +, — ); 2) У(хб ) = хд †> хг; а) Б = (Ь, -), б) Б = ( Й ., -): 3) Дхг) = хд дУ хг, а) Б = ( — Ц), б) Б = ( , Й ); 4) 1(ххз) = хд ду хг духа, а) Б = ( †, Ц, б) Б = (э, †); 5) 1(х') = х,х, м хгхз'~ хзхд; а) Б= (Й, 9), б) Б = ( — >,.
— ); 6) у(хз) = хдххз дс хдхгхз, а) Б = ( —, /, Ц, б) Б = ( Й, бз, — ); 7) У(хз) = х, Е х х,; а) Б = (4, ~, — ), б) Б = ( +, — ) 1.3. Для функции, заданной вектором своих значений, построить формулу в базисе Б; Ц 1(х~) = (101Ц; а) Б = (дД, — ), б) Б = (/); 2) 1(хг) = (100Ц; а) Б= (Й, -+), б) Б = Щ: 3) 1(хх) = (1000000Ц; а) Б = ( —, Д, б) Б= (Е, Й, Ц; 4) 1(хз) = (11101000), а) Б = (бд, Й, 1), б) Б = ( — д, — ); 5) 1(хз) = (1001 0100); а) Б = (бд, 1), б) Б = ( —, !); 6) 1(хз) = (1010 1110); а) Б = (дй,.
Й, — ), б) Б = ( —, дУ)' 7) 1(хз) = (0110111Ц; а) Б = (ЕВ, Й, — ), б) Б = ( —, Ц. 1.4. По схемам Е, изображенным на рис. 10.2, найти функции, реализуемые ими. 1.5. Построить СФЭ в базисе Б, реализующую систему функций Ф: Ц Ф = (дд = хдхг дс тгтз дс Узтд,,дг = хд ид хг ддд хз); а) Б = (Й, ч, — ), б) Б = (Й, дй), в) Б = (4, $); 2) Ф = (Уд =*д, Л = хдхг,,(з = хдхг*з; Ул = 1); а)Б=(й,— ), б)Б=( —,Ц; 3) Ф = ((д = хд чг хг,,(г = хд дс хг дс хз дУхдхгхз, (з = хдхг М хдхг); 309 у'1.
Схемы нэ функциональных элементов Рис. 10.2 6) Ф = (,Г1(х ) = Х1ХЗХ4 Ч Х1ХЗХ4 э Х2ХЗХ4 Ч Х2ХЗХ4, Ь = Л(Х1, хг, хз У4)); а) Б = ( ое, Ч., — ), б) Б = ( ое, 9, — ); 7) Ф = (Л(х ) = хзхгхз Н УгхгУз Ъ УЗХЗУ3 Ч У12224 Н х1 тгх4, .~2 = 71 9 Х2 ° 33 = Х2 9 ХЗ),~4 = 21 9 Х4); а) Б = ( ве, 17', — ), б) Б = ( 32, 9, — ); 8) Ф = Уо = х1, 'хю хз Л = з,,хгхз, Ь = х,,хгхз, 73 =х,хгхз, 34 = 21.'е2.'33 13 = Х122ХЗ, 13 = Х1Х2ХЗ, 37 = Х1ХЗХЗ)~ а) Б = ( й, — ), б) Б = ЕЧ, 9, Ц.
1.6. Реализовать функцию 7(хн) СФЭ в стандартном базисе, предварительно упростив выражение для 7(х ): 1) 7 (х ) Х122хз 7 21х2ХЗ 17х1хгхз э х1Х2хз 17х1хгхз~ 2) 7(х ) = Х1хгхз 17 хзхгхз 47'езхгхз 17 х1УЗУЗ 47У1хгхз 17 ххУгхз1 3) У(х ) — хзхз 1ухгхз 17 Х1.'ег'~ Хгхз,'. 4) Дх ) = (Х1 М хг М хз)(х1 М Хг Ч Хз)(хз Ч хг Ч Уз)(У1 Ч хг Ч Уз); 5) 7 (х~) = (х1 Ч х2)(х1 Ч х2 М хз) Ч х1х2хз 7 х2хз; 6) 7(х ) = (У1 Ч хг)(УЗ 47хз)(21 47 хг Ч хз)(х1 Ч Хг 47хз); 7) 3 (х ) = хзх2 7 х1хз 1 х1х2хз 7х1х2 гхзхз ° 310 Гл, Х. Реализаиил булевых функиий схемами и формулами Метод синтеза СФЭ, основанный на д. н.
фп состоит из двух эта- пов: 1) представления функции в д.н.фб 2) реализации д.н.ф. с помощью СФЭ. 1.7. Реализовать функцию 1 по методу, основанному на д. н. фл 1) 1 = 101000110);. 2) 1 = (01111110); 3) 1 = (00011111); 4) ~=(00010111); 5) )'=16>хй>гу; 6) У=х>1>уйг. 1.8. Показать, что если Г функция, двойственная к Э", и 1" отлична от константы, то Ь11') = Ц~).
Одноразрядным двоичным сумматором называется СФЭ (в произ- вольном базисе), реализующая систему из двух функций: т1х, у, р) = = ху > > ур Ч рх и 11х, у, р) = х а у 6> р. 1.9. Построить одноразрядный двоичный сумматор в базисе со сложностью, не превышающей А: ЦБ=1Ч,3с,— ), А=9; 2)Б=1еЭ,1с), А=5;. 3) Б=1ь, ~> — ), 1.10. Построить СФЭ в базисе 1й>, й ), реэлизующую такук> сис- ТЕМУ фУНКЦИй 1>Э'>1Хп), Эг(Х~), фХ )), Чта иЦ>1ап), Л(ап), Ь(ап)) Равно числУ единиц в набоРе йл = 1о>, ог> оз, ол).
Таким обРазом, искомая СФЭ дает двоичное разложение числа единиц набора ал. Здесь, как и раньше, о(о» ..., оп) = ~ еп. 2" ><><и Де>аифратпором называется схема 11п, реализующая систему всех конъюнкций ранга и переменных х>, хг, ..., хп. 1.11. 1) Построить Вг в базисе 1 3с, †) с числом элементов, не превосходящим 6. 2) Построить Вп в базисе Б = 1 й, — ) такую, что ЦВ„) ( 2"+' ч- п — 4. 3) Построить Вп в базисе Б = 1 се, — ) такую, что г.сд ) ( 2п, + 2>пп-з)йг 1.12. Мультиплексором от переменных х>, ..., хп, уо, у>, ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
