Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 60
Текст из файла (страница 60)
Построить сокращенную д. н. ф. по заданной к. н. фз Ц (х1 Ч тг Ч хз)(хгЧ хг Ч хз)(хг Ч Уз); 2) (хг Ч Уг)(хг Ч хг Ч Уз); 3) (хг Ч хг Ч хз) х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) ое = (11100100); 5) ое = (000110111101101Ц:, 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) ау = (1110111Ц; 5) ау = (000110111101111Ц; 6) Оу = (00111101111111ОЦ; 7) Ну = (0011110111011110),: 8) оу = (0010 10111101 111Ц. 2.7. С помощью минимизирующих карт построить сокращенную д.н. ф.
для частичной функции у, заданной векторно (прочерки соответствук~т не определенным значениям): Ц ау = (01 01 Ц; 2) ау = (1 01 10); 3)ау=(1- - 0 10); 4)Ну=(0- — 10 1 ); 5)ау=(10- 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) У(х ) = ухг Ч хг ' хз)(хг Ч хг ЧУз)(х4 9... 9 хи); 4) ~(х") = Уху Ч .. Ч хь)(хьв г Ч .. Ч х„); 5) Дх") = (хг Е ...Е хь)Ухе ы й ... й хи), 6) у (х ) = (х1 Ч ° Чх )(хг Ч ° ° Ч хе ЧУьв-1 Ч ° ЧУ )~ 7) У(х ) = (хг — е хг)(хг — в хз) .
Ухи — г -+ хи)(хн — в хз); 8) У'(х") = Ухг Ч.,. ЧхиЦУг Ч... Ч т,) 9) У(х ") = (хг Ч хг)(хз Ч хв) ..1хгв — г Ч хгв). 2.10. Пусть Як, (хи) такова, что гЧз„= та Е Вн: Й < йаз < < и + иг). Ц ЛлЯ данного набоРа а Е Вге найти число максимальных интеР- валов функции Яь,„,, содержащих набор Й. 2) Лля й < 1 < Уе+ го и а Е Ви найти число максимальных интервалов функции Яя,„, содержащих набор Й. 3) Показать, что число максимальных интервалов 1'-1оь (х~)) функции Яя „, равно (~) ( ). и! 4) Показать, что щах 1'(Як,„УУе")) = 2.11. Пусть 1е(у") длина сокращенной д. н. ф.
функции 7. Показать, что 1еЯ < — ~уЧу~(~уЧу~ + Ц. 2.12. Найти числа ядровых импликант у функций У из задачи 2.9. 2.13. Показать, что число ядровых импликант функций Дхв) не превосходит 2и 2.14. Ц Показать, что всякая простая импликанта функции у'(х") ранга и является ядровой. ЗО1 1' Я. Мешоды построения д.
н. ф. 2) Показать, что всякая простая импликанта функции ДУ") ранга меньше 2 является ядровой. 2.15. 1) Показать, что простая импликанта монотонной функции не содержит отрицаний переменных. 2) Показать, что каждая простая импликанта монотонной функции является ядровой. 2.16. Показать,что сокращенная д.н.ф. функции 1 реализует 1. 9 3. Методы построения тупиковых, минимальных и кратчайших д. н. ф. При построении тупиковых д. н. ф, функций, зависящих не более чем от четырех переменных, удобно пользоваться минимизирующими картами. При построении кратчайших д. н. ф. функции на минимизирующей карте отыскивается минимальная по числу элементов совокупность «прямоугольников», соответствующих простым импликантам функции и покрывающих все единицы в минимизирующей карте.
Пример 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. По заданной сокращенной д. н.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
