Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Рис. 30
но
Я
V-*,—Г~к
: ---------
V • -и.. і
Рис. 31
Риг. 32
а) Базис индукции п = 0. Здесь к ^ - 1 п нсі.н мая схема X] имеет ым (см рис. 31), М -, ) п. С Другой стерини, І»« -Зітудк—18 — 0 при и * 1*
Следовательно, неравенство
L (2^) ^ 18п — 9 log п — 18
справедливо для п— 1.
б) Индуктивный переход от т — 1 к т(т — — 1 5* 0) осуществляется При ПОМОЩИ схемы 2 ™ (см.
т”
п
|1од2л]м Рис. 34
рис. 32). Эта схема «делит» набор (аи ..а т) на две части (а|, а.гт~~1) и (а^-1+1, в каждой ча-
1-------—------- сти под схемами 2гт-1
вычисляется число единиц V и г", затем сумматор
2™ «складывает» V и I”, и на выходе вычисляется число единиц исходного набора.
Мы имеем Ь (2’™) = 2Ь (23т -1) -р Ь (2^)| или
Ь (2^) = 2 I(Х>/а) + ? (2+) < 2 (18 \ 910?-г- - 18) +
4- 9 1о? 2п < 18п — 9 log п — 18.
Лемма доказана.
Следствие. Ь(2'т)^118-2?\ г. е. при п~2т
?(Х)<18гс.
Лем м а 6. Для любого п можно построить многополюсник 2„, осуществляющий преобразование • » 0?п)—>- Ч ^ (2„)^ ^ ЗСя,
ГЛ. 2. СИНТЕЗ СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ
Доказательство. Очевидно, существует такое т,
что
п^2т< 2 п.
Искомый многополюсник 2п может быть реализован так, как это показано на рис. 33. У многополюсника 22-« берутся первые [1о^а п] + 1 выходов:
?(2;) = ?(2;™)+ 2<18.2”'+ 2<18 (2л - 1) + 2<3бл.
Утверждение доказано.
Теорема 8. Существует константа Сй такая, что любая симметрическая функция..................^ (а^, ..., хп) может быть реализована схемой 25^1(<іїі3д х такой, что
С (2$ (х1.. )) ^ С0п.
Доказательство. Искомая схема 2 Хп) может быть построена так, как это показано на рис. 34. Здесь схема 2П преобразует набор (а1у .,а„) в двоичный код ^ апу Схема 2* реализует булеву фупк-
цию от [к^гл] +1 переменной, и эта функция на «наборах» і{аі «^)у совпадающих с і1} ,,іх, равна 1, а в
остальных случаях равна нулю.
Мы имеем (см. теорему 7)
2[]°*а"1+1 ЛП
36л +
откуда следует существование константы С0, о которой говорилось в теореме. Теорема доказана.
24 с. В. Яблонский
СПИСОК ЛИТЕРАТУРЫ
1. В а с и л ь е в Ф. П. Численные методы решения экстремальных задач.— М.: Наука, 1980.
2. Васильев 10. Л. О сравнении сложности тупиковых о минимальных диаъюнктивных нормальных форм,— В кн.: Проблемы кибернетики. Вып. 10.— М.: Физлґатгиз, 1963, с. б—61.
8. Г а в р и л о в Г. П., С а и о ж е н к о А. А. Сборник задач по дискретной математике.— М.: Наука, 1977.
4. Дискретная математика и математические вопросы кибернети-ки/Под ред. С. В. Яблонского и О. Б. Лупанова.— М.: Наука, 1974.
5. Ж у р а в л е в Ю. И. Об отделимости подмножеств вершин п-мерного единичного куба,— В кн.: Труды МИАН СССР. Т. 51.— М.: Ивд-во АН СССР, 1958, с. 143—157.
6. Журавлев Ю, И. Об алгоритмах упрощения дизъюнктивных нормальных форм,— ДАН СССР, 1960, 132, Аа 2, с. 260—263.
7. 3 ы к о в А. А. Гиперграфы.— УМН, 1974, 29, № 6, с. 89—154.
8. И л ь и н В. А., С а д о в н и ч и й В. А., С е н д о в Б. X. Математический анализ.— М.: Наука, 1979.
9. К р а т к о М. И. Алгоритмическая неразрешимость одной задачи из теории конечных автоматов.— В кн.: Дискретный анализ. Вып. 2.— Новосибирск, 1964, с. 37—41.
10. Кратко М. И. О существовании нерекурсивных базисов конечных автоматов,—Алгебра и логика, 1964, 3, № 2, с. 33—44
11. Кудрявцев В. Б. Теорема полноты для одного класса автоматов без обратных связей,— В кн.: Проблемы кибернетики. Вып. 8.— М.: Физматгиз, 1962, с. 91—115.
12. Кудрявцев В. Б. О мощностях множеств предполных множеств некоторых функциональных систем, связанных с автоматами,—В кн.: Проблемы кибернетики. Вып. 13. М.: Наука, 1965, с. 45-74.
13. К у д р я в ц е в В. Б., Алешин С. В., П о д к о л з и н А. С. Введение в теорию автоматов,— М.: Наука, 1986.
14 Кудрявцев Л. Д. Курс математического анализа. Т. 1—2,— М.: Высш. пік., 1981.
15, К у а в е ц о в А. В. О проблемах тождества и функциональной полноты алгебраических систем.— В кн.: Труды 3-го Всесоюзного мат. съезда. Т. 2.— М.: Изд-во АН СССР, 1956, о. 145—146.
16. К у а н е ц о в А. В. О бесловторных контактных схемах и бес-повторных суперпозициях функций алгебры логики.— В кн.: Труды МИАН СССР. Т, 51.— М.: Изд-во АН СССР, 1958, с. 186— 225.
СПИСОК ЛИТЕРАТУРЫ
371
17. Лупанов О. Б. О возможностях синтеза схем из произвольных элементов.—В кн.: Труды МИАН СССР. Т. 51.— М.: Изд-во АН СССР, 1958, с. 158-173.
18. Л у п а н о в О. Б. О синтезе некоторых классов управляющих систем.— В кн.: Проблемы кибернетики. Вьш. 10.— М.: Физмат-гиз, 1963, с. 63—97.
19. Л у о а н о в О. Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования.— В кн.: Проблемы кибернетики. Вып. 14.— М.: Наука, 1965, с. 31—110.
20. Л у п а и о в О. Б. Асимптотические оценки сложности управляющих систем.— М.: Иад-во МГУ, 1984.
21. Ляпунов А. А. О логических схемах программ.— В кн.: Проблемы кибернетики. Выи. 1.— М.: Физматгиз, 1958, с. 46—74.
22. М а р к о в Ал. А. Об алфавитном кодировании. 1.— ДАН СССР,
1960. 132, 3, с. 521-523.
23. Марков Ал. А. Об алфавитном кодировании. II.— ДАН СССР,
