Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 59
Текст из файла (страница 59)
Методы настроенья сонратенной д, н, ф. 297 Пример 1. Построить сокращенную д.н.ф. по д.н.ф. Р функции Х, где Р = хзхз 1ХхзхзЧ Узхз. После первого этапа получаем Р, = хгхз Ч х1хз 1Ххзхз Ч хзхз ~ехгхз Ч хз. После второго этапа получаем сокращенную д. н. ф. Р2 г1х2 " хз. ЛХетод ХХель сана позволяет строить сокращенную д. н, ф.
по к. н. ф. Сначала в заданной к.н.ф. раскрываются скобки с использованием закона дистрибутивности. На втором этапе вычеркиваются буквы и конъюнкции с использованием правил ххК = О, ххК = хК, К1 'ч' К1К2 = К1. Пример 2. Построить сокращенную д.н.ф. по заданной к.н.ф. (х1 Ч хз)1х1 Ч У2 Ч хз). После раскрытия скобок имеем Р, = х1 х1 Ч х,х Ч х,хз1ухзх, Ч хзхз Ч хзхз. После второго этапа получаем сокращеннук1 д. н. ф. РХ вЂ” Р2 — х1хз М х2 ° Алгоритм Квайна строит сокращенную д.н.ф.
по совершенной д. н. ф. На первом этапе к совершенной д. н. ф. применяется операция неполного склеивания (хКЧ хК = К 'д хХ1 1~ хХ1 ). После того как такая операция применена к каждой паре конъюнкций из совершенной д.н.ф., к которой она применима, с помощью операции поглощения (КЧ х К = К) удаляются те коньюнкции ранга п, которые можно удалить таким образом. В результате получается некоторая д.
н. ф. Р1. Если проведено Й > 1 этапов, то на (Й+ 1)-м этапе операции неполного склеивания и поглощения применяются к конъюнкциям ранга и — к д.н.ф. Рю В результате получается д.н.ф. Рге ы Алгоритм заканчивает работу, если Рге 1 = Рю П р и м е р 3. Пусть функция Х(хз) задана своей совершенной д. н. ф. Ро = хгхзхз Ч х1хзхз 1Х хгхзхз 1ух1хзхз 1ухгхзхз. После первого этапа имеем Р1 = хзхз и хзхз и хгхз Ч х хз Ч х1хз. После второго этапа получаем сокращенную д.
н. ф. Р'=Р =* 12ххз. Для небольших значений и сокращенную д.н.ф. функции Х'(хн) можно найти, исходя из геометрического изображения множества 11'Х в кубе В". С этой целью в кубе В" отыскиваются грани максимальной размерности, целиком содержащиеся в множестве 11'Р а затем составляется д. н.
ф. из конъюнкпий, соответствующих этим граням. П р и м е р 4. Пусть функция Х(хз) задана вектором од = = (00011111). Требуется найти ее сокращенную д. н. ф. 298 Гл. 1Х. Минимизации булевых функций 001 Таблица 9.1 Таблица 9.2 Простая импликанта 1 функции ф называется здравой, если существует набор Д такой, что 11Н) = О, и в то же время к1Н) = 0 для любой простой импликанты К функции 1, отличной от 1. Такой Решение. Вершины множества 1з'1 = (111, 110, 101, 100, 01Ц отмечены в кубе Вз (рис.
9.1) светлыми кружками. Максимальны- зц з,з.з 111 ми являются грани В ' и В ' ' . Коды этих граней суть (1 ) и ( 11). Соответствующие конъкзнкции имеют вид хы хзхз, а сокращенная 110 д.н.ф. есть Р1~ — — хз 'и'хзхз. Другой способ построения сокращенных д.н.ф. для функций, зависящих от небопьшо- 010 100 го числа (не более 4) переменных, состоит в исцоцьзовании минимизирующих карт (называемых картами Карно или диаграммами Вейна). 000 При этом функция задается прямоугольной табРис. 9.1 лицей, в которой наборы значений переменных на каждой из сторон прямоугольника расположены в коде Грея, Нахождение простых импликант сводится к выделению максимальных по включению прямоугольников, состоящих из единиц.
Считается, что каждая клетка таблицы, примыкающая к одной из сторон, является соседней к клетке, примыкающей к противоположной стороне и расположенной на той же горизонтали или вертикали. Метод применйм также и дця не всюду определенных функций. В этом случае выделяются максимальные прямоугольники, содержащие хотя бы одну единицу и не содержащие нулей.
П р и м е р 5. Таблица 9.1 представляет собой минимизирующую карту дпя функции 11хл) с вектором значений Д1 = = 11110010101001101). Коды максимальных интервалов имеют вид (00 0)., (000 ), ( 01), ( 1 1), (11 0). Сокращеннаяд.н.ф. имеет вид Р1 — — хзхзхл Ч хзхзхз 'г хзхл и хзхл Ч хзхзхз. П р и м е р 6. Таблица 9.2 представляет собой минимизирующую карту для частичной функции 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 Ч Хг) (хг " хг " хз); 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. Методы построения тупиковых, минимальных и кратчайших д. н. ф. При построении тупиковых д. н. ф, функций, зависящих не более чем от четырех переменных, удобно пользоваться минимизирующими картами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
