Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 84
Текст из файла (страница 84)
Нетрудно видеть, что я Ь(Уг ) = 2 < 2 ° 2 . По предположению индукции сугцествует схема — 1 для 11,"; г сложности, не большей чем 2 2г . Все функции ф(ха), не зависящие сущоственно от х„, реализованы в УЯ г. Если функция ф зависит от т,„существенно, то она представнма в виде У = х„д Ч х Ь, где д и л различные функции переменных хг, ..., х„г. Если одна из этих функций (д или Ь) равна нулю, то отнесем 1 к классу Кг, в противном случае к классу Кг. Набавим к схеме 11„г по одной вершине гу для каждой функции ф из Кг О Лг. Если ф б Кг и имеет вид 1 = х„)г, то соединим вершину ив схемы У„" г контактом х„с новой вершиной ер Если ф В Кг и ( = х„д + х„л, то соединим вершины ив и иь схемы Сг„г с новой вершиной иг соответственно контактами х и х.
Таким образом, добавляется всего [Л г [ + 2[Л г[ контактов. Ясно, что такое добавление контактов к схеме (г',", не вносит каких-либо цепей с ненулевой проводимостью в У„г и, следоваг тельно, не изменяет функций, реализуемых схемой ((,, Ясно также, что я в новых воршинах реализуются соответствующие им функции из Кг О Кг, и, значит, построена схема для У„. Оценим сложность построенной схемы. г Имеем йь(ПЯ) < 1я((У„г) -1- [Кг[-1-2[К [ < 2 2 + 2[Кг[-Ь [Кг[ = 2 2 3) Выбирая щ = [1ояг(п — 21оя гг)[, получаем при достаточно больших и Л,([(х")) < Лг(оя „,)+ Ья(П„'') < 2 2 -""'"-"""'*"'+ г> гг~ -г~ лг ) 2"тг 2" '" г 2" +2 2 +, <4 —. п!одг(п — 21обг и) пг и 2.17.
Ц Схема для Угь может быть получена по методу каскадов. Эта схема имеет сложность, равную 2. Предположим, что схема для с1„. г подул -1 ченная по методу каскадов, содержит не более 2 2г контактов. Построим схему для (~У'. Множество )го ввршин этой схемы соатветствуот мнОжеству всех функций 1(х"). Вершины нз 1'о, соответствующие функциям 1 (х "), не 4)о Отеетьц указания, реюеноя зависящим от переменной х„, содержатся также и в Ъь Пусть Км Кз классы функций, зависящих от и переменных, определенные в решении задачи 2.12, 2). Правило провеления контактов метода каскадов предписывает провести один контакт для каждой вершины, соответствующей функции 1 из Лы и два контакта для вершины, соответствующей функции ) из Кз.
Таким образом, общее количество ребер, соединяющих вершины множеств 1 о и Ъ ц равно )К~ ~ + 2~Кз ~. Дальнейшие рассуждения повторяют решение задачи 2.12, 2). 2.18. Утнерждение вытекает из того, что для реализации всех конъюнкций по методу каскадов ~);~ = 2" ' (з = О, 1, ..., и) и из каждой вершины з-го яруса (О < 1 < л) в следующий ярус выходит ровно одно ребро. 2.19. Доказательство отличается от предыдущего только том, что количество ребер, исходящих из вершины, отличной от полюса Ь, равно 2 при О < г < и — 2.
При 1 = п — 1 из каждой вершины исходит одно ребро. 2.21. Пусть, например, схема Е представляет собой последовательное соединение некоторой двухполюсной схемы А и контакта х. Преобразуем схему Е, отбросив все контакты х и стянув в точку каждый из контактов х в А. 51сно, что функдия проводимости новой схемы Е' совпадает с прежней, а число контактов уменьшилось. 2.22. Если схема Е не является сильно связной, то в ней имеется отросток.
Отбрасывая его, мы не изменяем, очевидно, функцию проводимости. Поэтому Е не может быть минимальной. 2.2б. То, что Лк(л Ю у) < 4, вытекает из того, что существует схома для х 9 у (см. задачу 2.Ц сложности 4. Предположим, что минимальная схема для х чз у солержит менее четырех контактов. В силу утверждения задачи 2.23 эта схема не может иметь ровно три контакта. Каждая минимальная схема с двумя контактами реализует либо функцию вида х" у", либо функцию вида х" Ч у . 2.26.
Пусть х, . буква, встречающаяся в качестве пометки контакта в бесповторной схеме Е. Поскольку Е сильно связная, то существует цепь, соединяющая полюса а и Ь схемы Е и содержащая контакт я, Зафиксируем значения лз,..., о переменных, отличных от хы так что все контакты рассматриваемой цепи, кроме х7, оказшзись замкнутыми, а все контакты, НЕ ВХОДЯЗЦИЕ В ЦЕПЬ, --- РаЗОМХНУтЫМИ. ТОГДа )„Л(им ЛЗ, ..., П„) = Яоз.
Отсюда и следует, что функция проводимости 1, з существенно зависит от яь 2.2Т. Утверждение вытекает из того, что для каждого о существует сильно связная бесповторная схема со контактами. 2.32. Всякая контактная схема с семью ребрами остается планарной после добавления полюсного ребра, так как не существует непланарных графов с восемью ребрами. Посколысу для всякой такой схемы двойственная схема определена и имеет такую же сложность, то отсюда вытекает, что Дя(1) = 1ь(1*). Второе равенство следует из того, что у(яц ...,;с„) = )*(хм ..., л„).
2.33. Утверждение следует из того, что всякая я-схема является планарной и остается таковой после добавления к ней полюсного ребра. 2.34*. Схема Е, указанная на рис. 19.12, имеет среди своих сечений множества (х, 9), (г, ьз), (я, г, г, з) и (я, ю, 1, и). Тогда, если сугцествует бесповторная схема Еы реализующая функцию з'*, то в ней имеются цепи с проводимостями ту, гиб хгиз, яоМи. Без ограничения общности можно считать, что контакт х примыкает к полюсу о сети Еь Тогда к этому Рл. Х. Реализация булевых 4)уикиий схемами и угормуяами 411 полюсу примыкает также и контакт г или контакт ш.
В первом случае в Ег но существует цепи хгиг, а во втором цепи вийи. 2.35. Неверно. Воспользоваться тем, что 1 1хм ..., х„) = 1*1хг, ..., х ), и результатом задачи 2.34. 2.38. Пусть Н)К) число связных двухполюсных сетей с й ребрами. Каждом из рассматриваемых контактных схем может быть получена из некоторой двухполюсной сети в результате приписывания каждому )зебру одного из 2" символов хг, ..., х„, хг, ..., х„, Поскольку НЯ ( 1сй) ' 1см.
задачу),то Кап, т) < ) Н)йн2п) < ~(сй) (2п) < (с тп) о=о ь.=о 2.40. 10. Б. Пупанов.) Каждая формула, содержыцоя й символов переменных, имеет й — 1 символов связок й и О', не более й — 1 левых и не более й — 1 правых скобок. Общее число символов нв превосходит 4й — 3. Таким образом, всякая такая формула есть слово длины, не превышаюгцей 4й — 3, в алфавите 11, ), О, 8с ) О Х", где Х" = 1хм..., х„, хм ...
..., х„), причем число букв из Х' равно й. Число слов длины е, содержатцих й букв из алфавита А и е — й букв алфавита В, не превосходит С~)А(~(В!' ~. Поэтому Ф1п, т) < ) Сго — з12п) 4 < 1сгг) оят 2.42. Ц, 2) С использованием результата предыдущей задачи имеем при п о оо 1У (и, — 2" 11 — е)) -(" '- — ')" ("("'— '- ))- — 2" < и + 11 — е)2" — 2' = и — е 2" о -сю. Отсюда вытекает задача 2), а значит, и задача 1).
г" 2.43. 1) Число самодвойственных функций Д1х" ) равно 2г . С использованием задачи 2.38 имеем при и -о со — 1 1обгЯ (и, (1 — е)) ~ ((1 — е) 1обг(с 2" '(1 — е)) = и и = 2" (1 — е) ) 1+ О Н) < 2" Отсюда вытекает утверждение. 2) С использованием задачи 2.39 имеем при п о оо 2" 2" '11 — е) 1обг Р (пи 11 — е) ~ (1обг)сп) = 1оягп 1ояги =2" (1 — е+О( — )). Список литературы *) 1.
Автоматы / Под рсд. К.а. Шеннона и Пж.Маккарти. Мл ИЛ, 1956 (1Ъ ) 2. Алферова 3. В. Теория алгоритмов. Мл Статистика, 1973. (Ч) 3. Арбиб М. Мозг, машина и математика. Мл Наука, 1968. НЧ, Ъ') 4. Бернс К. Теория графов и ее применения. - Мл ИЛ, 1962, ('г"1) 5. Виленкин Н. Я. Комбинаторика. - - Мл Наука, 1969.
1'ч'П1) 6. Грехем Р,, Кнут Л., Наташник О. Конкретная математика. Мл Мир, 1998. (Ъ'1, УП1) 7. Лискретная математика и математические вопросы кибернетики. Т. 1.. Мл Наука, 1974. (1-П1, Ч1, УП, 1Х, Х) 8. Емелнчеа В. А., Мельников О. И., Сарванов В. И., Тьликввич Р. И. Лекции по теории графов. --. Мл Наука, 1990, ('у1, ЧП1-Х) 9. Зьтов А.А. Теория конечных графов.
Новосибирск: Наука, 1969. (Ъ'1) 10. Кобринский Н.Е., Тр хтвнброт Б.А. Введение в теорию конечных автоматов. Мл Физматгиз, 1962. (1У) 11. Комбинаторный анализ. Задачи и упражнения / Под ред. К. А. Рыбникова Мл Наука, 1982. ( у'1, ЧП1) 12. Кристофидес Н. Теория графов. Алгоритмичоский подход. — Мл Мир, 1978. (У1) 13. Лавров И.А., Максимова Л.Л. Задачи по теории множеств математической логике и теории алгоритмов. -- Мл Физматлит, 2001.
(1, П, Ъ') 14. Леонтьев В.К. Избранные задачи комбинаторного анализа. Мл МГТУ им. Н.Э. Баумана, 2001. ('у'П1) 15. Мальцев А. И. Алгоритмы и рекурсивные функции. Мл Наука, 1986. (У) 16, Марченков С.С. Замкнутые классы булевых функций. Мл Физматлит, 2000. (П) 17. Матросов В.Л., Стеиенко В.Н. Лекции по дискретной математике. Мл МПГУ. 1997. (1, П, Ч1) 18. Минский М.
Вычисления и автоматы.. Мл Мир, 1971. (1Ч, Ъ') 19. Нефедов В.Н., Осиоооа В.А. Курс дискретной математики. Мл МАИ, 1992. (1, П, УП1) 20. Оре О. Теория графов. Мл Наука, 1980. (Ъ'1) в) Римские цифры, стоящие после названия, указывают главы задачника, при работе над которыми эта литература может оказаться полезной. Список литаературы 413 21. Питерсон У., Уэлдон Э. Коды, исправляюпзие оюибки. -- Мл Мир, 1976. (ЪгП) 22.
Риордан Дхс. Введение в комбинаторный анализ. - - Мл ИЛ, 1963. (Ъ'1, Ъ'Ш) 23. Рыбников К. А. Введение в комбинаторный анализ. --. Мл Изд-во МРУ, 1985. (Ъг1, Ъ'П1) 24. Сачков В. Н. Введение в комбинаторные методы дискретной математики. Мл Наука, 1982. (Ч1, ЧШ) 25. Свами М., Тхуласираман К, ! рафы, сети н алгоритмы. Мл Мир, 1984.
(Ъг1) 26. Трахтенброга Б, А. Алгоритмы и вычислительные автоматы. - - Мл Советское радио, 1974. (1Ъ', Ч) 27. Трахтенброт В.А., Барздиоь Я. М. Конечные автоматы. Мл Наука, 1970. (1Ъ') 28. Уилсон Р. Введение в теорию графов. -- Мл Мир, 1977. (Ч1) 29. Феллер В. Введение в теорию вероятностей и ее приложения. Т. 1. -- Мл Мир, 1984. (ЧШ) 30. Харари Ф. Теория графов. -- Мл Мир, 1973. (Ъг1) 31. Холл М.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
