Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 82
Текст из файла (страница 82)
Лалее, полагая Ге=~ — 1п( — )( в 1 т /овец ГП в вп неравенстве ЛгГМ) < к+ п6»м получаем требуемое утверждение. 1.14. На первом шаге градиентной процедуры в покрытие войдет строка, покрывающая не менее п»»р столбцов, и не более п(1 — 1/р) останутся непокрытыми. Если А» множество непокрытых после к-го шага столбцов и ~А» ~ < пГ1 — 1»р)», то на Г)е -~- Ц-м шаге по крайней море одна из строк 404 Ответы, указания, решения покрывает не менее (Ая(/р столбцов. Отсюда )Агег! < (Аь((1 — 1/р) < < п(1 — 1/р)ььг. Таким образом, )Ая) < гг(1 — 1/р)".
Посколыгу Ьг(Р) < < й. + ~Ая ~ при любом натуральном к, то, полагая ] (1п Р)/З1п(1 ') [ получаем утверждение. 1.15. — = — (1обя ( — + 1)). 1.16. Ц Множество 1г' = (Н б В': ОНО, и четное) является (и, Ц-протыкающим и )Х) = 2" . Остается показать, что б(п, Ц > 2" . В силу задачи 1.2 куб В" разбивается на 2" ' 1-мерных граней одного направления. В каждой из них должна присутствовать вершина (и, Ц-протыкающего множества. 2) Нижняя оценка очевидна. С другой стороны, гу = (О, Ц является (и, п — Ц-протыкающим. 3) (В.В.
Глаголов.) Указание. Рассмотреть гУ = (Н б В": ОЩ = : — О (шог1 3) ) ипи № = (а б Вп: н(Й) = 3 (шог1 4)). 4) (О.Б. Лупанов.) Нижняя оценка. Заметим, что, для того чтобы веригина Н = (пг, ..., гг„) содержалась в (и — 2)-мерной грани с колом у = = ('Уг, ..., '7 ), в котоРом У,, Тз б (О, Ц, нУжно, чтобы щ = У„о = У .
Пусть 1г' С В" —. (и, и — 2)-протыкающее множество и ~гу~ = ти. Рассмотрим матрицу М, строками которой являются векторы из № Из предыдущего следует, что для каждой пары чисел (г, 1), 1 < г < ) < и, и любой пары (а., г), гг, т б (О, Ц, должна найтись строка й = (ог, ..., ег ) такая, что а, = и, о = т. Отсюда вытекает, что любые два столбца матрицы М попарно несравнимы. Число попарно несравнимых двоичных наборов т г гп длины ги не превосходит...). Отсюда вытекает, что (,, )) > и. , (гп/2/) ' (иг/2 В е р х н я я о ц е н к а.
Пусть т наименьшее целое такое, что (= / )) > и. Построим двоичную матрицу М с т строками и п попарно несравнимыми столбцами. Добавим к матрице две строки: 0 и 1. Тогда множество строк полученной матрицы будет (гг, и + 2)-протыкающим. ! гН б) Вытекает из того, что множество 7У = () Вггзгн является (и, й)- =в протыкающим. 6) Если гу является (и, 1)-протыкающим и С вЂ” г-мерная грань куба В", то ггг О С является (г, 1)-протыкакндим.
Отсюда и из задачи 1.2, Ц вытекает требуемое неравенство. 7) Неравенство вытекает из задачи 1.12, если положить ги = 2", в = 2, п ()2 — Я 1.17. Ц 1+ 1. 2) Положим ~(Мтюг) = р„,г...г. Утверждение вытекает из того., что 1 и — 1-~-1 Г йд„ьг. г > пд„г г г г г, р„г. г целое и д„гпг ь г г г = ] 3) Ясно, что 4(М„,„цг) > 1, поскольку при любом выборе 1 векторов Нг, ..., Нг из В,", г можно подобрать вектор /3 б В,", не покрываемый ни одним из выбранных 1 векторов. Это можно сделать, выбрав по одной нулевой координате в каждом из векторов йг,..., Н„и положив их равными 1 в векторе /3.
Если жс выбраны 1+ 1 векторов из В'„' г, так, что 405 Гл. 1Х. Минимизация булевых функций множества нулевых координат попарно не пересекаются, то все векторы из Вт" оказываются покрытыми. 4) Нижняя оценка вытекает из мощностных соображений: число покрыт'и1 Гттз ваемых столбцов равно (! ), а каждая строка покрывает (1) столбцов.
Верхняя оценка вытекает из задачи 1.12. 5) Верхняя оценка. Пусть и =4!! — 1)+г, 0 < г < ! — 2. Разобьем и, кттординат на ! — 1 блоков так, что два любых блока различаются по мощности не большо, чем на 1. Всего имеется г блоков мощности й+ 1, ! — 1 — г блоков мощности т!. Лля каждой пары координат произвольного из этих блоков возьмем вектор из Вл г, имеющий нули в этих координатах. Множество Р получаемых таким образом векторов имеет мощность 4+11 т( ) +1! — 1 — г)( ). Покажем, что для каждого В из В,", т существует т3 из Р такой, что В < т3. В самом деле, поскольку число нулей в В равно 1, а число блоков равно ! — 1, то некоторый блок содержит некоторые дво нулевые координаты. В Р содержится вектор тз, имеющий нули в этих координатах.
Ясно, что а < Д. 1.19. 1) 2. 2) 2. 3) 4. 4) 3. 5) 3. 6) 3. 1.20. 1) и. 2) п — 1. 3) л — 1. 4) и. 1.21. Указание. Два столбца матрицы М различаются в бнй строке тогда и только тогда, когда ф-я строка матрицы Мт ! покрывает сумму по модулю 2 этих столбцов. 1.22. Ц, 4), 5), 7) Ла. 2), 3), 6), 8), 9) Вообще говоря, нет. 1.23. Если матрица составлена менее чем из !об. л строк, то число попарно различных столбцов меньше и. 1.24. Пусть А и В тупиковые тесты матрицы М с тл строками. Тогда ни одно из включений А с В, В с А не имеет места. Отсюда вытекает, что число тестов не превосходит числа попарно несравнимых наборов в В'", а тп значит,не превосходит , , )).
,~ ит!'2 1.25. Число матриц размерности /т х и с попарно различными столбцами равно 2ь12 + 1)...12я — и+ 1). Число матриц размерности тл х п, у которых фиксированные й строк заданы, равно 2"т 1.26. 1) 11, 2), 11, 4), 12, 3), !3, 4). 2) 11, 2, 3), 11, 2, 4), 11, 3, 4). 1.27. !Э.Ш. Коспанов.) Если в матрице М с попарно различными столбцами расстояние между любыми двумя столбцами не меньше т), то в матриде Мтгт каждый столбед содержит не менее т! единиц. Теперь утверждение вытекает из задач 1.21 и 1.12. 2.1. Ц хт,хгхз. 2)хтхг.
3)хгхз, хтхгхт. 4)хт. 2.2. 1) После применения правила обобщенного склеивания имеем Вт = = хтхгЧ хтхгхлЧ хгУзхл Ч хгхт Ч хтхзхл Н хтйзхл Ч хзхл. После применения правила поглощения получаем Вг = хтхг Ч хгхл Н хзхл. 2) хтхгхз Ч хтхгхл ЧУтхгУл Ч УтУЗУт НУгйзхл. 3) хт Н хг Ч хзН хл. 4) хзУ4 Ч Угхзхл Н хтйгхл Н хтхгхз Н хт бгхз Ч УтУгУл. 5) лтНУтхз Ч хзхл '' хгхз Н хтхгхл.
406 Ответы, указания, решенов 2.3. Ц хгхзЧхгхгхз. 2) хг Чхгхз 3) хгхгЧ хгхгхз. 4) хгУг Чхгхг Ч хгхз Ч хгхз Ч хгхз Ч хгхз. 5) хгхгхз Чхгхгхз. 6) хгхгхз ЧхгхгУ4 Ч хгхзхг. 2.4. Ц хгхз Ч хгхг Чхгхз Ч хгУз. 2) хгхз Ч хгхз Ч х~хг ЧхгУз'Ч хгхг Ч хгхз. 3) хг Ч хгхз. 4) хгхг Ч хгхзЧ хгхз. 5) хгхг Ч хгхз Ч хзхг Ч хгУзхз Чхгхгхз Ч х~хгхз. 6) хг:сг Ч Угхг Ч хгУзхг Ч хгУзх4 Ч хгхзУз Ч хгхзУ4 2.5. Ц хг Ч хгхз. 2) Угхз Ч хгхз Ч хгхг.
3) тгхг Ч хгхз Ч х хз Ч хгхг. 4) хгхг Ч хгхз Ч хгхз Ч х~ хз Ч хгхз Ч хгхз. 5) хгхг ЧУгхзхз Ч хгУзхг Ч хгхгхз Ч х~хзхг Ч Угхзхз. 6) хгхг Ч хгхз Ч хгхз Ч х~Уг Ч хгхз Ч вгтрк Ч хгхзхз. 2.6. Ц хзЧ хгхг. 2) УгУг Ч хгхз Ч УгУз Ч хейз Ч хгхг Ч хгхз. 3) хгхз Ч хгхг. 4) хг Ч хг ЧУз. 5) хгУ4 'Ч хгхз Ч хзхз Ч хгхз Ч хгхз Ч хгхг. 6) Угхз Ч хгхз Ч хзхг Ч хгхг Ч хгхз Ч хгхг. 2.7. Ц хг Ч хз. 2) хг Ч хгхз Ч хгхз. 3) хг Ч хгхз.
4) хг Ч хгхз. 5) хзхз г хгхг Ч хгхз Ч хгхзЧ хгхз Чхгхз Ч хзх4. 2.8. Ц хз, хгхг. 2) Ядреных импликант нот. 3) хгУз, Угхг. 4) хг, хг, хз. 5) хгхгЧ хгУз, хзхо 6) хгУз, хгхз. 2.9. Ц 2" '. 2) 2" '. 3) 6 2" ~. 4) к(гг — к). 5) 2" 6) й + (и — й)(п — 1 — Ц. 7) 2. 8) п(п — Ц, 9) 2". 2.10. Ц ( ). 2)( ) ( + ~). 3) Вытекает из задачи Ц. 4) Вытекает из того,что шш (й!)(и — Й вЂ” т)(т! = (Н!) (и — [ — ))!. 2.11. Каждый интервал функции 1 однозначно определяется заданием любой пары противоположных в этом интервале точек. Эти точки, очевидно, принадлежат множеству 1Ч7.
Поэтому число максимальных интервалов не превосходит числа неупорядоченных пар вершин (быть может, совпадающих) из множества йсу. 2.12. Ц 2" '. 2) 2" 'з. 3) О. 4) 1е(п — й). Указание. В любом максимальном интервале монотонной функции нижняя единица является собственной точкой того интервала, которому она принадлежит. 5) 2" г. Указание. Использовать задачу 1.9, 5) и то, что все интервалы имеют размерность О. 6) й. 7) 2. Заметить, что 7' = хг...хв Ч хг...х„. 9) 2в. 2.13.
Выберем для каждого ядрового импликанта функции Д(х") в точности по одной собственной точке. Рассмотрим все ребра куба В некоторого направления. Никакое ребро не может содержать двух выделенных собственных точек. Отсюда и вытекает утверждение. Гл. Х. Реализация булевых функций схемами и формулами 407 83 3.1. Ц а) Нет. 6) Па.
в) Нет. 2) а) Нет. 6) Нет. в) Нет. 3.3. Ц Оьт = туЧ хе. 2) Лвт = В. 3.7. Ц т(Д = р(1) = 1. 2) т(1) = осг, рЩ = 2г 4) т(7) = 58, р(7) = б. 3.8. Указание. Оценка следует из того, что число элементарных конъюнкций над переменными хг, ..., х„равно 3", длина тупиковой д, н, ф. не превосходит 2" и ни одна из конъюнкций в тупиковой д, н, ф.
не поглощает другую. 3.9. Указание. Верхняя оценка устанавливается по индукции. 3.11. Ц 2. 2) 2". 3.12. 3) Указание. См. задачу 5.17 гл. Ч1П. 3.13. 2",/и. Глава Х 1.2. Ц а) ((хг ~ хг) ~ (хг ) хг)) ~ (хг ~ хг). 6) (хг — э хг) э (хг -э хг). 2) а) ((хг 4 хг) 4 хг) 4 ((хг 4 хг) 4 хг). 6) хг 8сх . 3) а) (хг ~ хг)(хг ~ хг). 6) ((хму) х) у. 1.3. Ц а) хг Чхг. 6) хг ) (хг ~ хг). 2) а) (хг — э хг) й (хг — э хг).
6) ((хг 4 хг) 4 хг) 4 ((хг ~ хг) 3 хг). 3) а) ((хг ~ хг) ~ хз) ~ Нхг ) хг) ~ хз). 6) хгхгхз Ю (х1 ев Ц(хг Ю Ц(хз бг Ц. 1.4. Ц 7~ = хгхг., ггг = хг хг. 2) 7г = хгхг 9 хгхз Юхзхг, гтг = хг Ю хе 9 хз. 3) 1г = хг Чхе Ч хз, уг =хгхгхз. 1.6. Указание. Ц 7 = х Ч хгхз. 2) з' = хгхгЧ хгхз Ч ггхг. 3) 7 = хз(хг Ч хг) Чхг(хг Ч хз). 4) 1 = (гг Ч хе)(хг Чйз). 1.7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
