Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 60
Текст из файла (страница 60)
1.22. Две матрицы М и В с одинаковым числом строк называются Т-экоиоалентныни, если множество строк с номерами гы ..., 1ь является тестом тогда и только тогда, когда множество строк матрицы В с томи жс номерами является тестом матрицы В. Выяснить, являются ли Т-зквивалентными матрицы М и Ь, если: 295 у' П Сгарукпеура граней п-мерного куба Пример. Рассмотрим матрицу М. Для построения всех тупиковых тестов этой матрицы построим сначала матрицу МОО 101 !~1] По матрице МОО построим к.н.ф. ®)М), переменными которой являются номера строк матрицы М~~~, а элементарные дизъюнкции соответствуют ее столбцам н включак~т в себя номера строк, имеющих единицы на пересечении с данным столбцом. Таким образом, к.н.ф.
имеет вид еЗМ) = (1 о' 2 Ч 3) (2 Н 4) (1 Ч 3 Ч 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Х. Минимизации булевых функций Решение. Вершины множества 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
