1 (С.А. Ложкин - Лекции по основам кибернетики (2017)), страница 9

. , Ntкуба B n (см. рис. 8.1a и 8.1b). Заметим, что циклическаяФАЛ длины t существует тогда и только тогда, когда t > 6 —четное число, а цепная ФАЛ длины t — при любом t > 1.Пример цепной ФАЛ длины 3 дает ФАЛ g 00 , показанная нарис.

4.1, а ФАЛ g (см. рис. 2.1a) является циклической ФАЛдлины 6.Из теоремы 4.1 следует, в частности, что для любой цепной ФАЛ длины не меньше 4 и любой циклической ФАЛДНФ ΣT совпадает с сокращенной ДНФ. При этом цепнаяФАЛ f нечетной длины t = 2k − 1 > 3 имеет единственнуюминимальную ДНФ, которая совпадает с ее ДНФ ΣM и соответствует покрытию (см. рис. 8.1a) N1 ∪N3 ∪. . .∪Nt длиныk. Действительно, множество Nf в данном случае состоит из2k наборов и не может быть покрыто (k − 1) ребром. Кро-Введение57Nn−1αn `= e1αn−1`α2Nn`αn+1`N1```α1α2n−2N2n−2α2n−1`e0Рис.

8.2: цепная ФАЛ длины (2n − 2) в кубе B nме того, покрытие множества Nf , состоящее из k ребер, неможет включать в себя ребра с общими вершинами и должно содержать ядровые ребра N1 и Nt ФАЛ f . Легко видеть,что только покрытие N1 ∪ N3 ∪ . . . ∪ 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Введениествует рис. 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] Яблонский С. В. Эквивалентные преобразования управляющих систем. М.: Изд-во МГУ, 1986.[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..