Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 28
Текст из файла (страница 28)
3.33. Верно ли утвериленне: если булеза функция сушественно зависит более чем от одного аргумента и оиа монотонна, то оив несвмолвойстзенна? 3.34. Верно ли утверивенне: если булеза функция сушестаенно зависит более чем от одного аргумента и оиа линейна, то она иемонотонна? 3.35. Найти все булевы функции, уковлсгворяюшие системе уравнений М(х) -з= р(к), р(х) р(х) = О, З.йб. Довэавть слепуюшую теорему: при суперпозиции линейных функций колстаиовке функций в функшпо вместо ее аргументов) получаются линейные гик пни.
153 Гл. 2. Магпемашичсскад логика 152 22.11. Задачи и упражнения 3.37. Доказать теорему: при суперпоаицпи самодаойстаенпых функций вновь получаются семолзойствепные фуикпни. 3.28. Доказать теорему". при суперповицнимонатонных функпий вновь получаются монотонные функции. 2.26. Функция называется сасранлющей канстоангар г (г = О, 1), если на наборе аргументов аида (г, г, ..., г) ана принимает значение г. Доказаттч что суперпозиция функций, сохраияюптих понстаиту г, вновь является функцией, сохраняющей зту константу.
2.30. Если функции ут н ут самодзойственны, то самодзойстзенны ли функции атт Чи„астр,? 2.21. Если функции аат н аат линейны, то линейны ли тат Чтет, 7тат и тат -а атт? 3.32. Булеза функция называется симметричной, если она не изменяется при любом перензюноаонпи аргументов. Фундаментальной симметричной булевой ааднкиией индекса та нзаывается такая спмметричнзя булеза функпия, у которой асе ваиъюнкпии, входящие в совершенную ДЙФ юсй функции, имеют ровно ат букв без отрицания. Докааать следующую теорему: любая симметричная булеза функция есть дтюъюикпия фундаментальпыд булевых функций, индексы которых однозначна определякяся представляемой симметричной функкией.
2.33. Определить число самадаайственных функций, аависяших от п аргументов. 3.34. Докааать полноту системы булевой фуиапни, состоящей нз дизъюнкппи, константы 0 и эквивалентности. Образует ли зта система базис? 2.35. Образует ли бзаис системз булевых функций, состоящая из импликакии и константы О? 2.26. Установить, является ли полной система, состоящая нз дизъюнкпии, пмпликапни и аонъюнкпни. 3.37. Образуют ли полнута систему функция стст ЧстсаЧ хтзз и отрицание? 3.36. Доказать, что если некоторая булеза фуикдня не сохраняет константы и несамодаойствениа, то оно немонотаниа и нелинейна. З.ЗЭ.
Сравнить связности мографов, определяющих вонъюнкцню и днзьюнкцию з 3-значной логике до и после минимизации. 2.40. Выяснить, возмоина лн реализапия любой булевой функции на элементах УСЗППА (универсальной системы промышленной пневмо-автоматики), являющихся пневмореле, описываемым функцией а(Ь Ч с) Ч Ьсд. 2.41. Синтезировать логическую схему, реалнзуюшую булеву функшпа /(ст, ст, сз, са, са, са)~т =Ч(О, 1, 2, 5, 7, 11, 13, 15, 19, 20, 32, 57, 61, 62) в базисе Вебба.
2.42. Синтезировать логическую схему, реалнвуюшую булеау функцию /(с„сз, ..., са)(т = Ч(0, 3, 5, 8, 10, 12, 14, 15, 17, 25, 27, 31) в базисе (-+, О). 2.43. Определить слояность одноразрядного сумматора в базисе Шеффера. 3.44. Показать, что д/(ст, ст, ..., с„..., с„) д/(ст, ст, ..., с„..., с„) дс, дс; ЗАВ. Установить, справедливо ли равенство д/( ...,..., .) д/(с„с„..., „) дс; дса 3.46. Синтезировать логическую схему, реализуюшуто булеву функцию /(с„ст, сз, са, са)1т = Ч(0, 3, 5, 8, 10, 12, 14, 15, 17, 25, 27, 31) в бааисе Вебба. ЗА7.
Определить слоиность однораарялного сумматора а базисе (~а, 1). ЗАВ. Синтезировать логяческую схему, реалпзуюшую булеву функцию /(ст, ст, са,са,ха,са)(т = Ч(0, 1, 2, 5, 7, 11, 13, 15, 19, 20, 32, 57, 61, 62) в базисе (-а, ). ЗАЭ. Синтезировать логическую схему, реалнзуюшую булеву фунвцюа /(ст, хт, са, са, са)(т = Ч(0, 1, 2, 5, 6, 7, 11, 12, 15, 16, 18, 25, 30) в базисе (ат Ч Вт Ч аз) 2.50. Сннтеаирозвть логическую схему, реализуюшую булеву функцию /(ст, лт, ..., хт)1т = Ч(0, 2, 4, 5, 6, 7, 11, 12, ..., 81„ 101) в бааисе (-а, О). 2.51.
Определить порядок исключения переменных при ревлпаапии булевой ,функции /(ст, ст, ст, са)(т = Ч(0, 1, 2, 4, 7, 8, 11, 15), если имеется каталог реализации всех 'функций от двух кеременныд. 2.52. Установить, что больше: аес производной д//дсз или вес производной д//дсз от булевой функции /(ст, зг, сз, са))т = Ч(1 3, 7, 8, 12, 14, 15)- ЗЛЗ. Преклонить алгоритм подсчета веса производной от булевой функции с использованием лзоичных матрид. 2.54. Установить, что выгоднее с точки арения уменьшения аппоратурных вотрет в бавнсе имплккапнн и константы 0: исключение по одной переменной или исключение ио двум переменным.
3.55. Найти все остаточные функции при оптимальном порядке исктачеиип переменных булевой функции /(ст, хт, сз, са)(т = Ч(0, 4, 6, 8, 10, 13, 14, 15), 2.56. Сколько входоа имеет блок исключения ?а переменных? 2.5Т. Найти реализацию блока исюпачепия одной переменной з базисе Вебба. 3.58.
Кокова слоииость блока исключения одной переменной а базисе Шеф- фера? 2.56. Найти вес цроиаводной д//дст от булевой функаии /(ст, ст, сз)(т = - Ч(О, 1, 5, 6, 7). 2.60. Показать, что д/(хт, ст, °, к;, ..., сч) д/(хт, сг, ..., са, ..., са) 3.61. Найти производную первого порядка для функции веки переноса в полном одноразрядном сумматоре. 2.63. Определить проиаводиую второго царапка от функции суммы в пол- ном одиорварядиом сумматоре, определяющую условия переключения функции суммы при переключении каналов, соответствующих слагаемым.
2.63. Доказать, что любая булеза функаия олнозиачио оаределяется значе- нием функции и всех произвоцных в точке 00...0. 2.64. Спроектировать счетчик нечетиости в конмпликвтивном базисе. 2.65. Спроектировать одноразрядный сумматор в ималиквтиаиом базисе. 3.66. Синтезировать схему, реализуюшую функпшо, принимающую вначе- ипе 1 на тех наборах своих пяти аргументов, з воторых есть не менее четырех цднинц. При сннтеае испальаоаать злемеиты зккивалентиосгп, дизъюнкдии и езушц апик. З.ВТ. Синтезировать дешифратор иа три входа и восемь выходов, используя вцеыепты ч, Ва, З.ВВ. Реалнаовать функцию имеликацни иа элементах, реалиауюших отри- тшпие н фупкюпо р = ст ст Ч гт сз Ч Стза 2.66.
Реализовать импликакню иа элементах, реалнвуюших функцию Вебба. 155 3 2.11. Задачи и унралснемил Гл. 2. Машгматоичгскал лагика 154 3.70. Реалиаоввть сумму по модулю 2 на элементах Шеффера. 2.71. Реализовать одиоразрялную суммирующую схему на элементах Вс, Ч, 3.73. Реалиаозвть одноразрядную суммируюшую схему с учетом совместной минимизации фуивцнн суммы и переноса на элементах Ч, Вс, З.ТЗ. Доказать, по полный дешифратор на н входов макет быть построен нз двух полных дешифраторов на ш и и — ш входов и 2" элементов типа И. З.Т4.
Реализовать иа маиоритарных элементах и элементах НЕ функцию у = хейг Ч У1Узхз. З.ТВ. Реализовать функцию у = хг -э (хз -э хз) иа элементах у = х,38 ффхз4фхз и НЕ. 3.76. Реализовать на макоритарных элементах и элементах НЕ схему про. верки вола на четносгь, т.
е. схему, на выходе которой при четном числе единиц на входе схемы воэвзшап единичный сигнал. Число входов равно 3. 2.77. Доваэать, что дЯХ) Вс у(Х)) = Х ду(Х) Х дДХ~ д~~Х) дЮ~Х) З.ТВ. Доказать, 1по дЯХ> ч р(х>) — о~<х) — ~а1 х) а1(х> д (х> дх; дх; дх, дх„.
дх; З.ТВ. Раалоиить булеву функцию у(хн хз, хэ, хэ) = х1хзхэ ЧУэхзхэ Ч х1хзхэ в ряд, аналогичный ряду Тейлора, в тачках 2, 11. Сравнить количество первич- ных термов а полученных рвалаиевиях. 2.80. Записать основные законы алгебры Буля при арифметической интер- претации слелующих логических операций: хВсу=х ° у, хчу=х+у — х у, У=1 — х, где, +, — — арифметические операдии умноиение, слоненке и вычитание со- ответственно. 3.81. 1) Список термов исчисления; 11, +, =). Правила абрэаовання формул следующие: 1 — формула; если у — формула, то ~р1 — такие формула; если у и ф — формулы, то у + ф и 1э = ф — такие формулы. Заданы единственная аксиома 1+ 1 = П и два правила вывода: еслк чч + +1 = 1эз — выводимая формула, то Ээ11+! = уз1 — такие выводимая формула; если 1э1+1эз = 1эз — выводимаяформула, то 1э1+1эз1 ю уз1 — такие выводимая форм ла, оказать, 1по: а) формула 11+ 111 = 11111 зызоднма в данном исчислении; б) формула 1+ 1 = 1 невыводима в данном исчислении.
2 Мноиество термов состоит нз бесконечного числа букв и знавав ч и -+. разила образования формул следующие: любая буква есть формула; если я и 13 — формулы, то а ч д и я -+ д — такие формулы. Система аксиом такова: А Ч А -э А; А -э А ч В; А Ч В э В ч А; (А -э -+ В) -+ ((С -э А) -э (С -+ В)).
Правила вывода таковы. Правило ладсаэакозкю если я — выводимая формула н вместо любой пере- менной в этой формуле всюду произвести подстановку любой формулы, то новая формула такие выводимая. 11разила эаключекиз: если а -Ф р и я — выводимые формулы, то р такие выводимая формула. В данном исчислении (исчислении Гильберта) цоказать, что: 1) выводима формула А -+ А; 2) если А -+ (В -+ С), А и В выводямы, то выводима и формула С. 3.63. Используя результаты предыдущей задачи, доказать чта в исчислении Гильберта имеет место следующее утвериленне: если сг -+ (13 -+ 7) выводимо, цо >3 -+ (а -э у) — такие выводимая формула.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
