Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 60
Текст из файла (страница 60)
При построении кратчайших д. н. ф. функции на минимизирующей карте отыскивается минимальная по числу элементов совокупность «прямоугольников», соответствующих простым импликантам функции и покрывающих все единицы в минимизирующей карте. Пример 1. Кратчайшей д.н.ф. функции 1, которая задана табл. 91, ЯвлЯе~сЯ д.н.ф. Р = Узх4Ч жзл4 ЧтзлзУз ЧУ1УгУ4 В этой д.н.ф. все конъюнкции ядровые, как это легко усматривается из минимизируюгцей карты. Отметим, что Р является единственной тупиковой и минимальной д. н.
ф. функции 1. Для построения тупиковых д. н. ф. функции 1 часто используется так называемая таблица Квайна Цу функции 1, строки которой соответствуют простым импликантам функции 1, а столбцы наборам из множества ХР На пересечении строки, соответствующей импликанте 1, и столбца,. соответствующего набору а, стоит 1, если 1(а) = 1, и О, если 1(а) = О. Минимальное (тупиковое) покрытие столбцов таблицы Яу строками соответствует кратчайшей (тупиковой) д. н. ф. функции 1.
Минимальной д.н.ф. отвечает покрытие, обладающее минимальной суммой рангов конъюнкций, соответствующих строкам, вошедшим в покрытие. Пля построения всех тупиковых д. н. ф. функции 1 составим к.н.ф. Х(Д следующим образом: поставим в соответствие столбцу а таблицы Яу элементарную дизъюнкцию вида Р„= Лз Ч Лз м... Ч К„где Л, (г = 1, ..., з) все такис простые импликанты функции 1, что К,(а) = 1. Полагаем Х(~) = Й Рк. Раскрывая скобки подобно тому, как это делалось в методе 11ельсона (см, пример 2 из предыдущего параграфа), и используя правила А.А = А и АГАВ = А, получаем из к.н.ф.
Х(Д д.н.ф. М(у), слагаемые которой соответствуют тупиковым д.н,ф. функции П р и м е р 2. Пусть 1 = (х1 Ч хз Ч жз) (У1 Ч хз 'Ч Уз). Сокращенная д. н. ф. функции 1 имеет вид Ру — жзтз ''Уж~из ЧУ'.хзЧУзх Ч тзлз Ч згкз. Таблица Квайна Цу показана в табл. 9.3. 302 Гл. 1Х. Минцмизвция булевых 1яункццц Таблица 9.3 К. н.
ф. я',(Д имеет вид л4(2) = (Кь Ч Кв)(КЗ Ч К4)(К1 '4КЗ)(КЗ Ч Кь)(КЗ Ч Кь)(КЗ Ч К4). Палее М(1) = КЗК4Кь ц КЗКзКь ч «1КЗКзКЗ ч КЗКЗКЗКЗ 4УКЗК4КЗКЗ. Функция ( имеет две кратчайшие д. н. ф., которые являются в данном случае и минимальными, и три тупиковые д.н.ф., не являющиеся кратчайшими (и минимальными). Кратчайшая д.
н. ф., соответствующая слвгаеМОМу К1К4КЗ Д. н. ф. М(1 ) имеет Вид Х122 1 ХЗХЗ 1 ХЗХ1. Заметим, что слагаемые д. н, ф. М(1) соответствуют тупиковым покрытиям матрицы 4,З 4 и могли быть получены непосредственно из нее. Алгорит и упрвиьвния д.н.ув. состоит в применении двух операций. 1. Операция удаления элементарной конъюнкции. Операция удаления конъюнкции К из д.
н. ф. Р осуществляется лишь в случае, если после удаления К из д.н.ф. Р получается д.н.ф. Р', эквивалентная д. н. ф. Р. 2. Операция удаления буквы. Операция осуществляется, если удаление буквы хв из некоторой конъюнкции К д. н. ф, Р приводит к д. н. ф. Р', которая эквивалентна д, н, ф, Р. При применении алгоритма упрощения д. н. ф. Р рассматривается как слово, в котором задан некоторый порядок следования конъюнкций, а также букв в каждой конъюнкции. Операция 1 (операция 2) применяется к первой конъюнкции (букве), к которой эта, операция применима. Если ни одна иэ операций не применима, то алгоритм заканчивает работу.
Пример 3. Применим алгоритм упрощения к д.н, ф. Р = У1У2ХЗ Ч Х1Х2УЗ Ч Х2ХЗ 44УЗУ1 44Х1ХЗ. На первом этапе исключается первая конъюнкция Р1 — — ХЗХЗХЗЧ ХЗХЗЧ ХЗХ1 ц хзхз. В .01 нет конъюнкций, которые можно удалить, но можно удалить букву х1 в первой конъюнкции.
Имеем Р2 = '42хз '4 х2хз 4ххзх1 Ч х1хз 363 З" Х Методы построении д. н. ф. Эта д. н. ф. является тупиковой. Алгоритм заканчивает работу. Заметим, что если на этом этапе Удалить из конъюнкции г:1Угхз не бУкву х1, как этого требует алгоритм упрощения, а букву тз, то процесс упрощения можно продолжить путем удаления конъюнкции хгхз. В результате была бы получена д. н.
ф. Рз = хгх2 хгхз Ч гзх1, являя>щаяся кратчайшей и минимальной. 3.1. Выяснить, является ли д.н.ф. Р а) тупиковой, б) кратчай- шей, в) минимальной: 1)Р=хгхгухг, .2)Р=хгхгцхг, 3)Р=х1Чхг, 4) Р = хЗУЗ У хгхг, 5) Р = хгхгхз Ч хгхз У хгхз, 6) Р = хгтг Ч хсхзх1 У хгхзх4', 7) Р = хгхгхиЧ УгхзУЗЧ хгхзУ4: 8) Р х142хз У х1х2 с4 ' х1хзс4 У х2хзУ4 3.2. Применить алгоритм упрощения к д. н. фо 1) Р = хгхг У зе; 2) Р = хгхг Ч хгхг', 3) Р = х,хгхз Ч хгУз Ч х2хз, 4) Р = хгх2 У хгхг У хгхз, 5) Р = хгхг У хгхз У х1УЗ'У Угхг У Угхз,' 6) Р = х,хгхгх4 У хгхзх4 У хгхз Ч х,тз; 7) Р = хзхиЧ хгхзхи У х.
хгх4 Ч хсхгхз Ч хсхгхз У хгхгх4,. 8) Р = Угхз Ч хгхз У хгхг Ч х1 хгх4 У хгхзх4 Ч хгхзх4. 3.3. По заданной сокращенной д. н. ф. Р построить д. н. ф. Рцт, состоящую из конъюнкций, входящих хотя бы в одну тупиковую д. н. фл 1) Р=хуУхгЧуг; 2) Р = У юЧ узш У хуш Ч х уз У ху г У туйц 3) Р = хугЧ хуггоЧ хуй1 У хуй1 Ч ууи1; 4) Р = Зи1 УхуюЧУуУЧ хуг Чхую; 5) Р =Уш У уи1 У хш Ч угшЧ хуг; 6) Р = хугЧ хугЧ хуг У Уш У уюУ хш: 7) Р = хз У уз Уху Ч хуш Ч узш У хгш: 8) Р = Уг У у юЧ ху Ч уг У хш Ч зш. 3.4. По заданной сокращенной д. н.
ф, Р построить д. н. ф..Рвм, состоящую из конъюнкций, входящих хотя бы в одну минимальную д. н. фл 1) Р = хуУхУУ уг; 2) Р = хуУУ хуг У туюУ хгй1У узиб 3) Р = хш У уюЧ ги1 У хг У уг; 4) Р =УгЧугЧ хушцхуЧугшЧхгш: 5) Р = уг У хгш У хуг У хзюУ хуу 6) Р = УуйгЧ хуй1Ч угшЧ угш УУуг; 7) Р =УгЧхУУхугУхгш; 8) Р = угЛУ уийЧ хуИУхугш. 304 Гл. 1Х. Мцццциэвцив булевых функццй 3.5. Лля д.н.ф. из предыдущей задачи построить минимальные д. н.
ф. 3.6. С помощью таблицы Квайна построить все тупиковые д. н. ф. функции 7, заданной вектором своих значений: 1) ау = (01111100); 2) ау = (01111110); 3) ау = (00011111); 4) ау = (1111100001001100); 5) ау = (111010000П01000); б) ау = (1110011000010101); 7) ау = (0001011110101110); 8) Йу = (0001101111100111). 3.7. Найти число тЦ) тупиковых д, н, ф. и число р(7') минимальных д. н. ф. функции 7: 1) т' (хи) = хз ~В хз йЗ... Ф х„ве 1; 2) ~(х") = (х1 Чхз Чхе)(х1 Мхя Чхз) ее хе ев...
озхп; 3) 7(х и) = (хз Ч хз М хз) (х, ~хе Ч хз) (х, ез... 01 хп); 4) у(х") = (0111111111111110); 5) У(х ) = (хз ц хе ц хз ц хл ч хз ч ... ~ хп) йе х1 ч х че,,л хп); б) 1(хп) = (х Е " .Е х.)(х „ Е ... Е х.). 3.8. Показать,что число тупиковых д.н. ф.произвольной булевой функции ((хп) не превосходит ( „ ) . 3.9. Пусть Ь(Д число букв в минимальной д.н.ф, функции г", а 1(Д число слагаемых в кратчайшей д. н. ф. функции 7. Показать, что: шах 1(1(хп)) 2п — и 2) п1ах 7(У(хп)) и 2п — 1 Лх '0 Ли") 3.10.
Показать, что число тупиковых д. н. ф. любой функции 7" (хо), имеющей 2п ' ядровых импликант, равно 1. 3.11. Лля скольких функций 7"(хп) справедливы соотношения: 1) Ь(Дх")) = и 2п ~; 2) Ь(Дх")) = п(2п ~ — 1)7 3.12. Функция Д(хп) называется цепной, если множество 1Цу можно расположить в последовательность аН аз, ..., а1 такую, что р(а„апы) = 1 при всех 1 < г < 1 и р(а„а ) > 1 при ~г — у~ > 1. Пусть ц(1) число тупиковых д.н.ф. цепной функции ( такой, что ~%7~ = 5 Показать,. что: 1) ц(1) = ц(2) = ц(3) = ц(4) = 1; 2) п(1) = ц(1 — 2) + ц(1 — 3) при 1 > 5. 3) Найти асимптотическое поведение в1(1) при 1 з оо. 3.13. Пусть Г(7") минимально возможное число элементарных дизъюнкций в конъюнктивной нормальной форме функции 1, а Л® = 1(()/1*(Д. Найти Л(7) для (х1 Ч хз)(тз Н хв)...
(хзп--1 Ч хзп) ° 3.14. Пусть Во = Ро(хп) и Вз = Рз(хп) д.н.ф. такие, что Ро ве Рз = О, Ро Ч Рз = 1, а д. н. ф. В(у ) не содержит общих букв с д.н.ф. Ро и Рз. Бесповторцой суперпозиццей д.н.ф. Р, Ро, Рз по д о. Методы построения д. и. ф. 305 переменной у, называется д.н.ф. Е, полученная из д.н.ф. Й подстановкой вместо каждого вхождения буквы уе д.н.ф.
11о, .а вместо дг — — д. н. ф. Р, с последующим раскрытием скобок. Ц Доказать, что бесповторная суперпозиция тупиковых д.н.ф. является тупиковой д. н. ф. 2) Доказать, что бссповторная суперпозиция сокращенных д. н. ф. является сокращенной д.н. ф. 3.15. Пусть функция т(х4) такова, что аг = (0101 11000011 1010). Доказать, что выполнены свойства 1) — 3): 1) ш(ты хг, хз, хе) = ш(х ); 2) минимальными д.н.ф. функции и)(хха) являются гог = хгхзх4 Ч хгхзхеЧ хгхзхо Ч хгхзхы Вг = хгхгхз Ч хгхгх4 Ч хгхгхз Ч хгхгхо', 3) число тупиковых д. н.
ф, равно 10. 4) Доказать, что если Л(х ) = хг еехг ю... юг:, и четно и ) (хо) = в(хы х, Л(хз, ..., х„~ге.,), Л(хоугег, ..., хи)), то существуют тупиковые д.н.ф. Е и Е функции 1" такие, что 1(Е)ЯЕ) = 2и(г — г 5) Показать, что число тупиковых д. н. ф. функции 6(х") = го(х') Ех, Е...Ех равно 10г, а число минимальных д. н. ф.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
