Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 61
Текст из файла (страница 61)
Таблица 9.2 представляет собой минимизирующую карту для частичной функции 1, зависящей от трех переменных. Сокращенная д. н. ф. имеет вид Р1 — — Х~хз Ч хгхз Ч хзхз Ч хзхз. 001 Таблица 9.1 Таблица 9.2 Простая импликанта 1 функции ф называется здравой, если существует набор Д такой, что 11Н) = О, и в то же время к1Н) = 0 для любой простой импликанты К функции 1, отличной от 1.
Такой у" е. Методы носнгроення сокращенной д, н, ф. 299 набор Н называется собспгвенньме набором ядровой импликанты 1 (или соответствукгшего интервала). 2.1. Из заданного множества А элементарных конъюнкций вьще- лить простые импликанты функции г: Ц А = (хг, тз, хгхг; х2хз) 1(хз) = (0010 111Ц; 2) А = (тгтг, хгхз, хгхгхз), ге(хз) = (01111110); 3) "4 = (х1 'г4 хгхэ хзУгх4)., Дх~) = (101011100101 1110)' 4) .4 = (х1, хг, х1У2), Х(х~) = (101Ц:, 5) А = (21хз, хгхз, хг), ((х') = (0011101Ц; 6) А = (:гггю хгУз, х2),,((х~) = (0010111Ц.
2.2. По заданной д. н. ф. Р с помощькг метода Блейка построить сокращенную д. н. ф.: Ц Р = хгхг Ч хгхгхеЧхгхзт4, 2) Р = хгхгхз ЧУ1хгУ4 ЧУгхзх4,' 3) Р = хг Ч хгхг 'Ч хзхгхз Ч хзхгхзхе,' 4) Р = хз хгха Ч хгхгхз Ч УзУ4! 5) Р = хзх4 Ч хгхе Ч хгх4 Ч хгхзх4; 6) Р = хг.'егтз Ч хзх4'Ч хгт4 '' хгт4,' 7) Р = хзхе Ч хгхг Ч тзУ4 Ч хгхз', 8) Р = х1'с2хз Ч т!х2х4 Ч х2хза4 Ч х2хзх4 Ч х2хзт1 ° 2.3. Построить сокращенную д. н.
ф. по заданной к. н. фз Ц (х1 Ч тг Ч хз)(хгЧ хг Ч хз)(хг Ч Уз); 2) (хг Ч Уг)(хг Ч хг Ч Уз); 3) (хг Ч хг Ч хз) х1 Ч Хг) (х1 " хг " хз); 4) (х1 Ч хг Ч хз) хг Чхг ЧУ3) 5) х1 Ч тг)(хг Ч хз)(хз Ч х1); 6) (х, Чхг)(хг Чхз)(хзЧх4)(х, Чх,); 7) (хг Ч хг Ч хз)(хг Ч хг Ч х4)(х1 Ч хг Ч У4) ~ 8) (хг Ч хг)(т1 Ч хз Ч х4)(У1 Ч Уг Ч хз)(хз Ч У4).
2.4. С помощью алгоритма Кввйна построить сокращенную д. н. ф. для функции 7, заданной вектором своих значений; Ц оу = (01110110); 2) ау = (1011 110Ц; 3) оу = (0010111Ц: 4) о е = (1110 0100); 5) о! = (0001 1011 1101 101 Ц:, 6) ое = (00001!1111110110); 7) ау = (1111111101111110), 8) оу = (0000 1111 0111 111 Ц. 2.5. Изобразив множество 2Чу функции Дхн) в В", найти коды максимальных интервалов и построить сокращенную д. н. фз Ц ЙХ = (11110100): 2) Йу = (0101 001Ц; 3) оу = (1101 001Ц:. 4) оу = (1110011Ц; 5) ау = (1111100001001100); 6) од = (0001 0111 1110 111 Ц; 7) од = (1110 0110 0000 011 Ц; 8) Ну = (1111 1111 1111 1000).
2.6. Найти сокращенную д. н. ф. функции 7' с помощью минимизи- рующей карты: Ц оу = (0101011Ц; 2) оу = (1101 101Ц; 3) ау = (10110000), 300 Гл. 1Х. Миниииэвиив булев х фунниий 4) ау = 11110 111Ц; 5) ау = 10001 10111101111Ц; 6) ау = 10011 1101 1111 110 Ц; 7) ау = 10011 1101 1101 1110),: 8) ау = 10010 10111101 111Ц. 2.7. С помощью минимизирующих карт построить сокращенную д.н. ф. для частичной функции У, заданной векторно 1прочерки соответствук~т не определенным значениям): Ц ау =101 01 Ц; 2) ау = (1 01 10); 3)ау=(1- - 0 10); 4)ау=(0- — 10 1 ); 5)ау=110- 1- 011 0 - - 1- ОЦ; 6)ау=(0 1 0 1 1 ОЦ,: 7)ау=( .- 01 .1-.00....
1 0); 8)ау=( 10 1 11 01 0— 2.8. Найти все ядровые импликанты для функций 7' из задачи 2.6. 2.9. Найти длину сокращенной д.н.ф. функции уе: Ц У 1х и) = х, Е х, Е... Е х„;. 2) ул Ухи) = (хг Ч хг Ч хз)(хУг Ч Уг Ч хз) Ю хл Е... Ю х„; 3) У(х ) = ухг Ч хг ' хз)(хг Ч хг ЧУз)1х4 9... 9 хи); 4) ~(х") = Уху Ч ..Л хь)1хьв г Ч ..Л х„); 5) Дх") = (хг Е ...Е хь)Ухе ы й ... й хи), 6) у1Х ) = Ухг Ч ° Лх )1хг Ч ° ° Ч хе ЧУьв-1 Ч ° ЛУ )~ 7) У1х ) = 1хг — е хг)1хг — в хз) .
Ухи — г -+ хи)1хи — в хз); 8) У'(х") = Ухг Ч., ЛхлЦУг Ч...Ч.т,) 9) УУх") = 1хг Ч хг)1хз Ч хл) .. 1хгл — г Ч хгв). 2.10. Пусть Як, (хи) такова, что гЧз„= 1а Е Вн: й ( ))а() ( ( и + иг). Ц ЛлЯ данного набоРа а Е Вге найти число максимальных интеР- валов функции Яь,„,, содержащих набор Й. 2) Лля й < 1 < Уе+ го и а Е Ви найти число максимальных интервалов функции Яя,„, содержащих набор Й. 3) Показать, что число максимальных интервалов 1'-1оь 1х~)) функции Яя „, равно (~) ( ). и! 4) Показать, что щах 1'18к,„УУе")) = 2.11. Пусть 1е11") длина сокращенной д. н. ф.
функции 7. Показать, что 1еЯ < — ~уЧу~(~уЧу~ + Ц. 2.12. Найти числа ядровых импликант у функций У из задачи 2.9. 2.13. Показать, что число ядровых импликант функций Дхл) не превосходит 2и 2.14. Ц Показать, что всякая простая импликанта функции у'1х") ранга и является ядровой. ЗО1 1' Я. Мешоды построения д. н. ф. 2) Показать, что всякая простая импликанта функции Дх") ранга меньше 2 является ядровой. 2.15. 1) Показать, что простая импликанта монотонной функции не содержит отрицаний переменных. 2) Показать, что каждая простая импликанта монотонной функции является ядровой. 2.16. Показать,что сокращенная д.н.ф.
функции 1 реализует 1. 9 3. Методы построения тупиковых, минимальных и кратчайших д. н. ф. При построении тупиковых д. н. ф, функций, зависящих не более чем от четырех переменных, удобно пользоваться минимизирующими картами. При построении кратчайших д. н. ф. функции на минимизирующей карте отыскивается минимальная по числу элементов совокупность «прямоугольников», соответствующих простым импликантам функции и покрывающих все единицы в минимизирующей карте. Пример 1. Кратчайшей д.н.ф. функции 1, которая задана табл. 9 1, являешься д н ф. Р = Узх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 Мх, Чхз) еехл ев...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
