Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 59
Текст из файла (страница 59)
001 011 Показать, что множество строк матрицы М с номерами гы ..., гь тогда и только тогда является тестом (минимальным., тупиковым тестом), когда множество строк матрицы М~г~ с теми же номерами является ее покрытием (кратчайшим, тупиковым покрытием). 1.22. Две матрицы М и В с одинаковым числом строк называются Т-экоиоалентныни, если множество строк с номерами гы ..., 1ь является тестом тогда и только тогда, когда множество строк матрицы В с томи жс номерами является тестом матрицы В. Выяснить, являются ли Т-зквивалентными матрицы М и Ь, если: 295 у' П Сгарукпеура граней п-мерного куба Пример. Рассмотрим матрицу М. Для построения всех тупиковых тестов этой матрицы построим сначала матрицу МОО 101 !~1] По матрице МОО построим к.н.ф.
®)М), переменными которой являются номера строк матрицы М~~~, а элементарные дизъюнкции соответствуют ее столбцам н включак~т в себя номера строк, имеющих единицы на пересечении с данным столбцом. Таким образом, к.н.ф. имеет вид ФМ) = (1 у 2 Ч 3) (2 у 4) (1 зуз Ч 4) . Раскрывая скобки в к.н.ф. Я(М) и используя правило поглощения (АГАВ = А),получаемд.н.ф. Р(М) = 1. 2 Ч 1 4Ч 2 4 уЗ. 4 у' У 2 - 3. Тупиковыми тестами являются следующие множества строк: 11, 2), 11, 4), 12, 4), (3, 4), 12, 3).
1.26. Пользуясь универсальным алгоритмом, построить все тупиковые тесты для матриц из пп. Ц, 2), 5), 6) задачи 1.6. 1) М получена из В перестановкой столбцов; 2) М получена из Л перестановкой строк; 3) М получена из В удалением всех столбцов, сплошь состоящих из 0 (из 1): 4) М получена из Ь вычеркиванием к — 1 столбцов из к одинаковых; 5) М получена сложением по модулю 2 каждого столбца матрицы В с заданным столбцом Д; 6) М получена из Ь сложением по модулю 2 каждой строки матрицы Ь с заданной строкой ей; 7) М получена из В заменой всех 0 на.
1 и всех 1 на 0; 8) М состоит из всех линейных комбинаций столбцов матрицы Ь; 9) М = Ь~г~ (определение см. в задаче 1.21). 1.23. Доказать, что если М имеет и попарно различных столбцов, то длина минимального теста не меньше 1обг п,. 1.24. Доказать, что число тупиковых тестов матрицы М с т строками не превосходит ( ) . 1.25.
Доказать, что число матриц размерности т х п с попарно различными строками, у которых совокупность строк с номерами рм ..., ея является тестом., равна 2ь(2У + 1)... (2" — и+ 1)2ой~ ь~. Универсальный алгоритм построения тестов состоит в построении по заданной матрице М некоторой к.н.ф. и последующем преобразовании ее в д.н.ф., слагаемые которой соответствуют тупиковым тестам. 296 Гл.
1Х. Минимизации булевых функций 1.27. Локазать, что если в матрице М размерности т х и расстояние между двумя строками не меньше д, то длина минимального т 2едт теста не превосходит 1+ — 1п п1п — 1) 9 2. Методы построения сокращенной д. н. ф. Имплакантой функции 11х") невывается такая элементарная конъюнкция й над множеством переменных (хм хз, ..., х„), что й Ч 11х") = 11х").
Импликанта к функции 1 называется простой им ликантой, если после отбрасывания любой буквы из к получается конъюнкция, не являющаяся импликантой функции 1. Лизъюнкция всех простых импликант функции 1' называется сокращенной д. и, ф. функции 1. Лизъюнктивная нормальная форма называется: минимальной, если она содержит наименьшее число букв среди всех д.
н. ф., эквивалентных ей; кратчайшей, если она имеет наименыпую длину 1число элементарных конъюнкций) сроди всех д. н. ф., эквивалентных ей; тупиковой, если отбрасывание любой элементарной конъюнкции или буквы приводит к д.н.ф., которая не эквивалентна исходной д. н. фй д. и. ф. функции 1, если она реализует функцию 1. Конъюнкции, входящие в д. н. ф., называются ее слагаемыми, число слагаемых длиной д.н.ф., а сумма рангов слагаемых сложностью д. н.
ф. Говорят, что функция 1 поглощает функцию д 1обозначение: д ( 1), если д Ч 1" = 1" 1или, что то же самое, д ах 1" = = д). Простая импликанта к функции 1 называется ядровой, если д.н.ф., составленная из всех простых импликант функции 1, отличных от Й, не поглощает 1з Лизъюнкция всех ядровых импликант функции Е называется ядром функции 1. Если элементарная конъюнкция к является импликантой функции 21х л), то множество з1'ь всех наборов Н из В" таких, что ~(о) = = 1, образует грань, содержащуюся в множестве 1УБ Эта грань называется интервалом функции 1, соответствуюи1им импликанте й.
Интервал функции 1, но содержащийся ни в каком другом интервале функции 1, называется максимальным интервалом. Максимальные интервалы функции 1 соответствуют ее простым импликантам. Интервалы, соответствующие ядровым импликантам функции 1, называются здравыми интервалами. Метод Блейка для построения сокращенной д.н.ф. из произвольной д. н. ф. состоит в применении правил обобщенного склеива- ниЯ хК1 '2хКз = хКз Ч хКз'У КхКз и поглощениЯ Кз Ч КьКз — — Кы Подразумевается, что правила применяются слева направо. На первом этапе производится операция обобщенного склеивания до тех пор, пока это возможно. На втором производится операция поглощения. у" 2. Методы астроенья сонратенной д, н, ф. 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
