О.Б. Лупанов - Элементы математической кибернетики (1161667), страница 3
Текст из файла (страница 3)
Основные понятияГраф, в котором выделены некоторые вершины и ребрам которогоприписана нагрузка, будем называть контактной схемой, выделенныевершины — полюсами контактной схемы, а ребра — ее контактами.Пусть a и b — полюсы контактной схемы. Определим функцию проводимости fa,b контактной схемы следующим образом: fa,b = 1, еслиa = b; fa,b = 0, если a 6= b, но нет цепей, соединяющих полюсы a и b; востальных случаях fa,b есть дизъюнкция по всем цепям, соединяющимa и b, конъюнкций символов, приписанных ребрам цепей.Рассмотрим произвольную булеву функцию f (x1 , . . . , xn ).
Еслиf ≡ 0, то сопоставим ей контактную схему, состоящую только из отличных друг от друга полюсов a и b и не содержащую контактов. Еслиf 6≡ 0, то представим f в виде совершенной ДНФ_xσ1 1 · · · xσnn .(σ1 ,...,σn ),f (σ1 ,...,σn )=1Каждому слагаемому вида xσ1 1 · · · xσnn поставим в соответствие цепь (см.рис. 4),a ❡xσ1 1r···rxσnn❡bРис. 4а затем объединим все полученные цепи по полюсам a и b. При этомфункция проводимости fa,b будет реализовывать функцию f . Следовательно, любая функция f ∈ P2 реализуема контактной схемой.12Введем понятие сложности контактной схемы S.
СложностьюLK (S) будем считать число контактов в S. Затем LK (f ) = min LK (S)S(f )(здесь минимум берется по всем контактным схемам, реализующимфункцию f ), и LK (n) = max LK (f ) — функция Шеннона, оцениваf (x1 ,...,xn )ющая наименьшее число контактов, с помощью которых можно реализовать контактную схему для любой f .§ 2.2. Оценки сложности контактных схемСовершенная ДНФ функции f (x1 , . .
. , xn ) содержит не более 2n слагаемых. Поэтому в контактной схеме, реализующей функцию f , будетне более n22 контактов, т. е. справедлива оценкаLK (n) 6 n2n .(1)Обозначим через Qn систему конъюнкций вида{xσ1 1 · · · xσnn |(σ1 , . . . , σn ) ∈ E2N }.Всего конъюнкций будет |Qn | = 2n . Построим контактную схему, реализующую Qn , и покажем, что LK (Qn ) 6 2n+1 − 2.Пусть n = 1: x1 и x1 реализуются контактной схемой (см.
рис. 5)x✟1 ❡b1✟✟❡a ❍❍❍ ❡x1b2Рис. 5сложности 2. Предположим, что Qk реализованы до k = n − 1 включительно. Так, конъюнкция xσ2 2 · · · xσnn реализована схемой S1 сложностине более 2n − 2. Построим теперь схему S, реализующую Qn , следующим образом. Возьмем два экземпляра схем S1 . Занумеруем полюсыb одной схемы как b1 , . . . , b2n−1 , а другой — как b′1 , .
. . , b′2n−1 . Вершины, бывшие ранее полюсами a, соединим контактами x1 и x1 с новымполюсом a (см. рис. 6). Оценим сложность:LK (S) = 2LK (S1 ) + 2 6 2(2n − 2) + 2 = 2n+1 − 2.Значит, LK (Qn ) 6 2n+1 − 2.13a ❡✂❇✟✟✟✟✟r✟S1❍✂✂ ❍❍❍❍✂ x1❍✂...❡ b1❡b2n−1S❇✟✟❇ x1 ✟✟❇❇ r✟✟S1❍❍❍❍❍❍...❡ b′1❡ b′ n−12Рис. 6Построенная схема S носит название разделительного контактногодерева.
Функция проводимости между его любыми двумя полюсами–выходами тождественно равна нулю.Отметим в схеме S те цепи, которые соответствуют конъюнкциям,содержащимся в совершенной ДНФ функции f (x1 , . . . , xn ), их полюсы–выходы отождествим и обозначим через b. Тогда между полюсами a иb будет реализована функция f . ПоэтомуLK (n) 6 2n+1 − 2.(2)§ 2.3. Метод ШеннонаТеорема 4.
Справедлива более точная оценка:LK (n) .2n+2.n(3)nДоказательство. Пусть Vn = {f (x1 , . . . , xn )|f ∈ P2 }. Тогда |Vn | = 22 .Лемма 2.nLK (Vn ) 6 2 · 22 .(4)Доказательство леммы. Рассмотрим две контактные схемы: (1, k)–полюсную A и (l, 1)–полюсную B. Пусть A реализует функциюgi (x1 , . . . , xn ) между полюсами a и bi , а B реализует функциюfj (x1 , . . . , xn ) между полюсами dj и b.
Предполагаем также, что схема A обладает свойством разделительности, т. е. gb′ ,b′′ ≡ 0 для любыхразличных b′ и b′′ . Объединим схемы A и B следующим образом: i–й14✟✟✟✟✟✟✟✟✟a ❡❍❍❍❍A❍❍❍❍❍❍❍❍❍d1 ❡❍❍...❍❍❡b1...S❍❡b✟✟✟✟✟✟✟✟✟B❡❡dj(i)❡bkdl ❡bi......Рис. 7полюс–выход A соединим с j(i)–м полюсом–входом B (см. рис. 7). Покажем, что в полученной таким образом контактной схеме S функцияk_проводимости будет fa,b (x1 , . . . , xn ) =gi &fj(i) .i=1Поскольку схема B свойством разделительности, вообще говоря, необладает, возможны случаи, когда в B от dj(i) к b ведет не одна цепь,когда есть возвраты в схему A и т.
д. Но так как схема A являетсяразделительной, то функция проводимости всей такой длинной“ це”пи в итоге занулится. Однако можно разбить длинную“ цепь на пары”отрезков, целиком лежащих в A и B, поэтому в логической сумме останутся только слагаемые вида gi &fj(i) .Вернемся к доказательству леммы.
Докажем (4) по индукции.Пусть n = 1, и V1 = {0, 1, x, x}. Все функции из V1 реализуемы контактной схемой, изображенной на рис. 8,0❡1❡xx❡❡x✁ ✑✑❆ ✁✑x❯❡❆✁✑Рис. 8сложности 2 (здесь между входом 1 и полюсом–выходом нет контакта),значит (4) выполнено. Предположим, что (4) справедливо для всех размерностей, которые меньше n, и функции от n−1 переменной реализуетn−1контактная схема Sn−1 с 22входами и одним выходом. Рассмотримпредставлениеf (x1 , . .
. , xn ) = xn f (x1 , . . . , xn−1 , 1) ∨ xn f (x1 , . . . , xn−1 , 0).Добавим к Sn−1 еще один полюс и соединим его контактами xn иxn со входами, отвечающими функциям f (x̃, 1) = f (x1 , . . . , xn−1 , 1) и15❍❡ ❍❍❍... f (x̃, 1) ❍❍❍xn✏✏r❍✏.❡P✏Sn−1 ❍ ❡..PPf (x̃, 0)✟✟xn Pr .✟✟..✟✟❡✟✟✟Рис. 9f (x̃, 0) = f (x1 , . .
. , xn−1 , 0) соответственно. Полученная контактная схема S (см. рис. 9) будет реализовывать функцию f (x1 , . . . , xn ). Оценимее сложность. Добавленных контактов — по два на каждую функциюиз Vn . Если f (x̃, 1) ≡ 0, то контакт xn можно не добавлять в схему.n−1Всего таких возможностей 22(количество функций от n − 1 переn−1менной).
Аналогично для f (x̃, 0). Итого удастся сэкономить 2 · 22контактов. Итак, верхняя оценка сложности схемы S складывается изоценки сложности Sn−1 и числа добавленных контактов за исключением сэкономленных:n−1LK (S) 6 2 · 22nn−1+ 2 · 22 − 2 · 22n= 2 · 22 .Лемма доказана.Вернемся к доказательству теоремы. Рассмотрим функциюf (x1 , . . . , xn ). Зафиксируем произвольное k. Разложим функцию f погруппе переменных набора (x1 , . . . , xn−k , xn−k+1 , .
. . , xn ):_σn−kf (σ1 , . . . , σn−k , xn−k+1 , . . . , xn ).f=xσ1 1 · · · xn−k(σ1 ,...,σn−k )По переменным (x1 , . . . , xn−k ) построим (1, 2n−k )–полюсное разделительное контактное дерево S1 , а по (xn−k+1 , . . . , xn ) построимk(22 , 1)–полюсную контактную схему S2 , реализующую Vk . Соединим,полюсы–выходы S1 с полюсами–входами S2 так, чтобы цепь, реалиσn−kзующая xσ1 1 · · · xn−k, оказалась соединенной с цепью, реализующейf (σ1 , . . . , σn−k , xn−k+1, . . . , xn ). Согласно установленному выше, функцией проводимости полученной схемы Ŝ будет функция f (x1 , . . . , xn ).Из оценок (2) и (4) получим:kLK (Ŝ) 6 2n−k+1 − 2 + 2 · 22 .В качестве k выберем ⌊log2 (n − 2 log2 n)⌋. Тогдаk2n−k+1 − 2 + 2 · 22 <2n+22n+1−2+ 2 .n − 2 log2 nn16При n → ∞ правая часть мажорируется величинойказана.2n+2.
Теорема доn§ 2.4. Случай неразделительных схемВведем понятие расстояния между наборами. Если α̃ = (α1 , . . . , αq )и β̃ = (β1 , . . . , βq ), то ρ(α̃, β̃) — число разрядов, по которым отличаются α̃ и β̃. Единичный шар с центром в α̃0 — это множество всех такихнаборов α̃, что ρ(α̃, α̃0 ) 6 1, т. е. единичный шар содержит ровно q + 1наборов. Единичная сфера с центром в α̃0 — это соответственно множество всех таких наборов α̃, что ρ(α̃, α̃0 ) = 1. Из теории кодированияизвестно, что множество всех наборов длины 2t − 1 можно разбить напопарно не пересекающиеся единичные шары.Лемма 3.
Если r = 2t , то множество всех наборов длины r можноразбить на попарно не пересекающиеся единичные сферы.Доказательство. Разобьем множество наборов длины r − 1 на попарно не пересекающиеся единичные шары. Пусть α̃′ = (α1 , . . . , αr−1 ) —центр одного из шаров. Образуем центры сфер α̃0′ = (α1 , . . . , αr−1 , 0) иα̃1′ = (α1 , . . . , αr−1 , 1). Если центров шаров было 2r−1/r, то центров сфербудет вдвое больше: 2r /r. Покажем, что единичные сферы с центрамив α̃0′ и α̃1′ , во–первых, попарно не пересекаются, а во-вторых, каждыйнабор длины r попадает в какую–либо сферу.1) Существует две возможности: а) центры сфер образованы изцентров различных шаров и б) центры сфер образованы из центраодного и того же шара.
Рассмотрим случай а). Пусть центры шаровα̃′ = (α1 , . . . , αr−1 ) и β̃ ′ = (β1 , . . . , βr−1 ), α̃′ 6= β̃ ′ . Тогда ρ(α̃′ , β̃ ′) > 3, поскольку единичные шары по условию не пересекаются. И если α̃′′ , β̃ ′′ —центры сфер, совпадающие с α̃′ и β̃ ′ по первым r − 1 компонентам, тои подавно ρ(α̃′′ , β̃ ′′ ) > 3, откуда следует, что сферы не пересекаются.Рассмотрим случай б). Пусть центры сфер (α1 , . .
. , αr−1 , 0) и(α1 , . . . , αr−1 , 1). Перечислим все наборы, которые попадут в эти сферы:(α1 , α2 , . . . , αr−1 , 0),(α1 , α2 , . . . , αr−1 , 1),(α1 , α2 , . . . , αr−1 , 0),(α1 , α2 , . . . , αr−1 , 1),······(α1 , α2 , . . . , αr−1 , 0),(α1 , α2 , . . . , αr−1 , 1),(α1 , α2 , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
