Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 58
Текст из файла (страница 58)
3) Пусть Е(А) множество робер куба В", целиком содержащихся в подмножестве А С В". Показать, что для любого целого т такого, что 0 ( т ( 2о з, и любого А С В" такого, что ~А~ = 2" ~ -~- т, выполнено неравенство ~Е(А)~ > тп. 1.4. Пусть пы пз,...,п„ -- целые неотрицательные числа такие, что ~ 2"' = 2". Тогда в В" существуют попарно непересекающиеся грани Сы Сз, ..., С, размерностей, соответственно раве ных пы пз, ..., п„такие, что О Се С Всч ~.—.-1 1.5. Грани С и Н куба В" называются несравнимь ми, если не выполняется ни одно из включений С С Н, Н С С.
1) Показать, что существует множество граней куба В", состоящее из ~ ) ~ ! попарно несравнимых граней. 2) Показать, что мощность всякого множества попарно несравнимых граней куба В" не превосходит . 2" ~"1з1. ЯЦ3)/ 1.6. Найти глубину матрицы М: у 1. Сгарукгаура граней и-мерного куба 293 1.7. Найти минимальные мощности градиентных покрытий матриц М из задачи 1.6. 1.8. Найти числа кратчайших покрытий матриц М из задачи 1.6. 1.9. Найти числа тупиковых 1юкрытий матриц М из задачи 1.6. 1.10. Пусть М матрица с п ненулевыми столбцами, а в каждой ее строке не менее й единиц.
1) Показать, что с(М) < п — й+!. 2) Показать, что оценка достижима. 1.11. Пусть М матрица линейного (и, й)-кода, Показать, что ~(М) < 1з 1.12*. Пусть матрица М размерности т х и имеет не менее з единиц в каждом столбце. Доказать, что: 1) ~(М) < 1+ — [п —; 2) Ьг(М) ( 1+ — [п * е т е т 1.13а. Пусть в матрице М с и, ненулевыми столбцами существует подматрнца М' с т строками такая, что число столбцов подматрицы М', содержащих менее е вдиниц, не превосходит г„. Доказать, что максимальная мощность Ег(М) градиентного покрытия матрицы М удовлетворяет неравенству Ег (М) ~ ~1 + га + е т. 1.14.
Пусть матрица т имеет и, ненулевых столбцов, а ее глубина равна р. Дока. зать, что Ег(М) ( 1 + 9+ ([п — ) /[п (1 — — ). 1.15. Пусть двоичная матрица М имеет п = 2(2" — 1) столбцов и д+ 2 строк, причем множество Е, номеров единичных координат ртй строки матрицы М имеет вид Е,=(2' ~,2' "+1,...,2' — 1,п — 2' ~+1,п — 2' ~,...,п — 2'+2) при 1 ( 1 ( У, Еа з —— (1, 2,..., 2" — Ц, Е„ з — †(2а, 2а + 1,...,п). Найти отношение мощности градиентного покрытия к мощности кратчайшего покрытия.
1.16. Множество Я С В" называется (по к)-протеакаю1аим, если в каждой а-мерной грани куба В" находится хотя бы одна вершина множества Ле. Пусть Е(п, а) = пцп [Х[, гдв минимум берется по всем (по й)-протыкающим множествам. Доказать, что: 1) Ци, 1) = 2а з; 2) Ь(п, и — 1) = 2; 3) 1(п, .2) < [2а,13); 4) т < Ь(п, п — 2) < т, + 2, где т — наименьшее целое, для ко- т торого [ ) ) п; [т,/ 2) [и/ь[ 5)цп,й)< ~ ~( п,); е=о 294 Гл. 1Х. Минимизации булевых функций 6)Ь1п,к)>2" "Цг,к) 1к<г<п); 7) Л(п, й) < 1+ 2" ь 1п ( ) + 2" "'.
1.17*. Пусть 1 < 1 < к ( и и М„ие -- матрица, строки которой соответствуют наборам из В",, а столбцы наборам из В,", и пусть 1 на пересечении строки и столбца, стоит тогда и только тогда, когда набор, соответствующий столбцу, содержит все единицы набора, соответствующего строке.
1) Найти ~(Ми и г ~). 2) Показать, что ЯМи ь ~) > ~ — ~ — 1...~ [... [[[. 3) Показать, что ДМ„„ь е) = 1+ 1 при и. > 11+ 1)й. 4) Показать, что (~) ( ) < ~(М„ь р) < 1+ ( ) (1+ 1и ( )) ( ). 5) Показать, что <1Ми,л г,и е) ~ (г) ) + (1 — 1 ч-г)(2), где г остаток от деления и на 1 — 1, а д = 1п — г)/0 — 1). 1.18.
Пусть М вЂ” матрица размерности т х и, уг — положительное число. Показать, что в М можно найти множество строк А мощности, не превышающей и/р, такое, что после вычеркивания всех столбцов, покрываемых строками из А, получается подматрица, в каждой строке которой менее уг единиц. 1.19. Найти длину минимального теста матриц М из задачи 1.6. 1.20. Найти длины минимальных тестов для матрицы М, если: 1) множество столбцов матрицы М есть В"; 2) множество столбцов матрицы М есть В~",, 3) множество столбцов матрицы М есть О В" 4 о<ь<игг 4) множество столбцов матрицы М есть В„" еэ' В", (й > 0). 1.21. Через М~г~ будем обозначить матрицу, составленную нз сумм по модулю 2 всевозможных неупорядоченных пар столбцов ~по~ Гопы матрицы М. Например, если М = [ОП~, то Моо = '[ПО~.
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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
