Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 84
Текст из файла (страница 84)
В силу утверждения задачи 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) Число самодвойственных функций 11х" ) равно 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. Холл М. Комбинаторика. Мл Мир, 1970. (Ъ71, ЪГП1) 32. Ширяев А.В. Вероятность.
Мл Физматлнт, 1989. (Ч1, ЧП1) ЗЗ. Яблонскии С. В. Функциональные построения в Ь-злачной логике,1/ Труды МИАН СССР. 1958. Т. 51. С. 5 — 142. (1 — П1, У1, 1Х, Х) 34. Яблонский С.В. Введение в дискретную математику. — — Мл Наука,. 1986. (1 — Х) 35.
Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. Мл Наука, 1966. (1, .П) 36. А1оп Ко Брепсег д. ТЬе РгоЬаЬ111всю МеХЬос1. Л. ЪУ11еу Зс Вопя, 2000. (Ъг1, У111) 37. Войобав В. Напбот СгарЬв. — ИХл Асабеш1с Ргевв, 1985. (Ъг1, Ъ'П1) Предметный указатель Автомат без входа 147 выхода 146 Алгоритм Квайна 297 Алфавит входной 103 --. выходной 103 — кодирующий 230 — — машины Тьюринга внешний 182 — -- — внутренний 182 Арность функционального символа 10 Базис замкнутого класса 60 схемы 311 Буква (символ) алфавита 102 Вектор значений булевой функции 11 коэффициентов полинома 53 Вершины графа смежные 203 Вес набора 9 — о.-д, функции 103 Глубина формулы 30 Грань булева куба 290 ---плоского графа 216 Граф 203 двудольный 205 кубический 205 направленный 210 однородный (регулярный) 205 ориентированный 210 планарный 215 полный 205 пустой (вполне несвязный) 205 связный 204 ..
й-связный 206 Графы гомеоморфные 205 изоморфные 204 Дерево 205 — бесконечное информативное 104 корневое 219 растущее 212 Леревья одинаковые 220 Диаметр графа 204 Лизъюнкция 12 над множеством переменных 47 -- элементарная 47 Ллина д.н.ф. 47 к.н. ф. 47 Длина маршрута 204, 211 — слова 102 теста 291 Лополнение графа 205 Замыкание множества функций 60 Знак условного равенства 181 Зона работы мапзины Тьюринга 181 Избыточность кода 235 Импликанта 296 --простая 78, 296 ядровая 296 Имплнкация 12, 89 Интервал функдин максимальный 296 ядровый 296 Инцидентность вершины и ребра 203 Источник орграфа 212 Итерация машины Тьюринга 186 Класс вычислнмых функций 196 общерекурсивных функций 196 .
— предполный 60 — примитивно рскуреивных функций 196 ". функционально замкнутый 60 частично рекурсивных функций 196 Код алфавитный 230 — дерева 220 набора основной машинный 190 решетчатый 191 префиксный 231 Композиция машин Тьюринга 186 Предметный указатель 415 Компонента снязности графа 204 Конденсация орграфа 212 Контакт замыкающий 312 размыкаюший 312 Контур в орграфе 211 Конфигурация машины Тьюринга 179 Конъюнкция 11 над множеством переменных 47 -- элементарная 47 монотонная 52 Критерий планарности 216 Саломаа 97 Слупецкого 97 Яблонского 97 Лемма Бернсайда 274 о нелинейной функции 68 — — немонотонной функции 75 несамодвойственной функции 64 Лес 205 Максимум в и у 89 Маршрут в графе 204 орграфе 211 Метод Блейка 296 минимизирующих карт 298 Нельсона 297 неопределенных коэффициентов 53, 94 Хэмминга 245 Минимум х и у 89 Мультиграф 203 -- ориентированный 210 планарный 215 Набор булев (двоичный) 9 , предшествующий набору 10 Наборы булевы противоположные 9 соседние 9 сравнимые 10 Неравенство Чебышева 279 Объединение графов 205 Оператор, порожденный функциями 120 Операция введения обратной связи 146 — минимизация 196 объединения д.
функций 147 отождествления переменных 33, 146 Операция примитинной рекурсии 195 —. разветвления выхода 149 -- суперпозиции 147 удаления выходной переменной 146 Орграф 203 транзитивный 215 Отрицание Лукасевича 88 Поста 88 еж 11 Отросток в сети 223 Ошибка в канале связи 245 Паросочетание 205 Переменная существенная ЗЗ вЂ” фиктивная 33 Подграф 204 останный 204 порожденный подмножеством вершин 204 Подразбиение графа 205 Подфункция 39 Покрытие матрицы 290 Полинам 7Кегалкина (по модулю 2) 52 Полинам по модулю к 93 Полустепень захода 211 -- исхода 211 Профикс (начало) слова 103, 230 Принцип двойственности 31 Произведение по модулю й 89 Псевдограф 203 — ориентированный 210 Путь н орграфе 211 Разветнление машин Тьюринга 186 Разность по модулю й 89 -- усеченная 89 Ранг элементарной конъюнкции 47 Расстояние Хэмминга 9 Ребра кратные (параллельные) 203, 210 Связка логическэл 12 Сеть 219 — разложимая 223 - к-полюсная 219 Система Поста 97 Россера — Туркетта 97 функционально полная 60 Слово бесконечное 102 -- квазипериодическое 102 416 Прееметнььй указатель Слово пустое 102, 180 Сложность д.
н. ф. 47 Слой булева куба 9, 247 Соединение слов 102 Степень вершины графа 203 Сток орграфа 212 Стрелка Пирса 12 Сумма по модулю 2 12 ---к 89 Суперпозиция сетей 224 функции 14, 195 Сфера в булевом кубе 241 Схема, реализующая функцию 145 Таблица каноническая 130 критериальнэя 81 Теорема Визинга 217 †.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
