оки1 (1155744), страница 9
Текст из файла (страница 9)
. . ∪ Nt обладает всеми этими свойствами. Таким образом, для цепной ФАЛ нечетнойдлины t, t > 5, ДНФ ΣT не совпадает с ДНФ ΣM .Теорема 8.1 (ср. [6, 23, 10]). При любом n ∈ N, n > 3, вP2 (n) существуют ФАЛ f 0 и f 00 , имеющие общую простуюимпликанту K, которая входит в ДНФ ΣM одной, но невходит в ДНФ ΣM другой из этих ФАЛ и для которойSn−3 (NK , f 0 ) = Sn−3 (NK , f 00 ).Доказательство. Достаточно построить в P2 (n) цепную функцию f четной длины t = 2k > 2n − 2 > 4. Действительно,если указанная ФАЛ f найдена, а ее множество Nf соответ-58Глава 1. Дизъюнктивные нормальные формыствует рис. 8.1a, то, полагаяNf 0 = Nf \ {α1 }и Nf 00 = Nf \ {αt+1 } ,получим цепные ФАЛ f 0 и f 00 нечетной длины 2k − 1 такие,что каждое ребро Ni , где i = 2, .
. . , t−1, входит в ДНФ ΣMодной из них, но не входит в ДНФ ΣM другой. При этом,очевидно, Sk−2 (Nk , f 0 ) = Sk−2 (Nk , f 00 ) и, следовательно, искомая ЭК K соответствует ребру Nk .Для завершения доказательства возьмем в качестве fцепную ФАЛ длины (2n − 2), у которой множество Nf состоит из всех наборов αi = (1, . . . , 1, 0, . . . , 0), где i ∈ [1, n],| {z } | {z }in−iи наборов αn+i = αi , i ∈ [1, n), а ребро с номером j, j ∈[1, 2n − 2], имеет вид Nj = {αj , αj+1 } (см. рис. 8.2) и применим к ней описанные выше построения.Теорема доказана.Замечание 1. Из теоремы следует, что критерий вхождения ЭК в ДНФ ΣM не имеет такого локального характера,как критерий вхождения ЭК в ДНФ ΣT (сравните с теоремой 4.1).Замечание 2.
Известно [7], что при n > 14 в P2 (n) имеетсяцепная ФАЛ четной длины t, t > 2n−11 − 4, на основе которой справедливость теоремыможно установить для окрестtности порядка 2 − 2 (см. доказательство).Литература[1] Алексеев В. Б.
Введение в теорию сложности алгоритмов. М.: Издательский отдел ф-та ВМиК МГУ, 2002.[2] Алексеев В. Б., Вороненко А. А., Ложкин С. А.,Романов Д. С., Сапоженко А. А., Селезнева С. Н.Задачи по курсу «Основы кибернетики». Издательский отдел ф-та ВМиК МГУ, 2002.[3] Алексеев В. Б., Ложкин С. А. Элементы теории графов, схем и автоматов. М.: Издательский отдел ф-таВМиК МГУ, 2000.[4] Боровков А. А. Курс теории вероятностей. М.: Наука,1976.[5] Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике. 3-е изд., перераб.М.: ФИЗМАТЛИТ, 2004.[6] Дискретная математика и математические вопросы кибернетики, под редакцией С. В.
Яблонского иО. Б. Лупанова. Т. 1. М.: Наука, 1974.[7] Евдокимов А. А. О максимальной длине цепи в единичном n-мерном кубе // Матем. заметки. 1969. 6. №3.С. 309–319.[8] Емеличев В. А., Мельников О. И., Сарванов В. И.,Тышкевич Р. И. Лекции по теории графов. М.: Наука,1977.5960Литература[9] Журавлев Ю. И. Локальные алгоритмы вычисленияинформации // Кибернетика. №1. 1965.
С. 12–19.[10] Журавлев Ю. И. Теоретико-множественные методы валгебре логики // Проблемы кибернетики. Вып. 8.М.: Физматгиз, 1962. С. 5-44.[11] Кузьмин В. А. Оценки сложности реализации функций алгебры логики простейшими видами бинарныхпрограмм // Сб. «Методы дискретного анализа втеории кодов и схем». Новосибирск, 1976. Вып. 29.С. 11–39[12] Ложкин С.
А. Оценки высокой степени точности длясложности управляющих систем из некоторых классов // Математические вопросы кибернетики. Вып. 6.М.: Наука, 1996. С. 189–214.[13] Ложкин С. А. Структурное моделирование и декомпозиция для некоторых классов схем. М.: Издательский отдел ф-та ВМиК МГУ, 2001.[14] Лупанов О. Б. Асимптотические оценки сложностиуправляющих систем. М.: Изд-во МГУ, 1984.[15] Лупанов О. Б. О сложности реализации функцийалгебры логики релейно-контактными схемами //Проблемы кибернетики. Вып. 11. М.: Наука, 1964.С. 25–48.[16] Лупанов О. Б.
О сложности реализации функций алгебры логики формулами // Проблемы кибернетики.Вып. 3. М.: Физматгиз, 1960. С. 61–80.[17] Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования.Литература61// Проблемы кибернетики. Вып. 14. М.: Наука, 1965.С. 31–110.[18] Мурога С. Системы проектирования сверхбольшихинтегральных схем. М.: Мир, 1985.[19] Нечипорук Э.
И. О топологических принципах самокорректирования // Проблемы кибернетики. Вып. 21.М.: Наука, 1969. С. 5–102.[20] Нигматуллин Р. Г. Сложность булевых функций.М.: Наука, 1991.[21] Поваров Г. Н. Метод синтеза вычислительных и управляющих контактных схем // Автоматика и телемеханика. 1957. Т. 18. №2. С. 145–162.[22] Сапоженко А.
А. Дизъюнктивные нормальные формы. М.: Изд-во МГУ, 1975.[23] Сапоженко А. А. Некоторые вопросы сложности алгоритмов. Издательский отдел ф-та ВМиК МГУ, 2001.[24] Сапоженко А. А., Ложкин С. А. Методы логического проектирования и оценки сложности схем на дополняющих МОП-транзисторах // Микроэлектроника. 1983. Т. 12. №1.
С. 42–47.[25] Фихтенгольц Г. М. Основы математического анализа,том 1. М.: Наука, 1968.[26] Фихтенгольц Г. М. Основы математического анализа,том 2. М.: Наука, 1964.[27] Чегис И. А., Яблонский С. В. Логические способыконтроля работы электрических схем // Труды МИАН СССР. Т. 51. М.: Изд-во АН СССР, 1958. С. 270–360.62Литература[28] Яблонский С. В. Введение в дискретную математику.2-е изд., перераб. и доп. М.: Наука, 1986.[29] Яблонский С. В.
Надежность управляющих систем.М.: Изд-во МГУ, 1991.[30] Яблонский С. В. Некоторые вопросы надежности иконтроля управляющих систем // Математические вопросы кибернетики. Вып. 1. М.: Наука, 1988. С. 5–25.[31] Яблонский С. В. Элементы математической кибернетики. М.: Высшая школа, 2007.[32] Cardot C. Quelques resultats sur l’application de l’algèbrede Boole à la synthèse des circuits a relais //Ann. Telecommunications.
1952. V.7. №2. P. 75–84.[33] Shannon C. E. The syntesis of two-terminal switchingcircuits // Bell Syst. Techn. J. 1949. V. 28. №1.P. 59–98 (Русский перевод: Шеннон К. Работы потеории информации и кибернетике. М.: ИЛ, 1963.С. 59–101).[34] Wegener I. Branching programs and binary decisiondiagrams. SIAM Publishers, 2000..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
