В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (2011), страница 8

Найти p.2) Пусть распределения режимов работы конъюнктора u1 &u2 и дизъu1 &u2 1юнктора u1 ∨ u2 в СФЭ Σ на рис. 23 а) имеют види1−p pu1 ∨ u2 x, соответственно. Известно, что вероятность такого функ1233ционирования схемы, при котором на выходе Σ реализуется тождественная единица, равна 83 . Найти p.7.4.

Пусть базис Б состоит из ФЭ, реализующего функцию голосования, который работает абсолютно надежно, и конъюнктораu1 &u2 , расu1 &u2 1.пределение режимов работы которого имеет вид12331) Достаточно ли 40 функциональных элементов, чтобы реализоватьфункцию u1 &u2 c ненадежностью не более 0.1?2) Достаточно ли 400 функциональных элементов, чтобы реализоватьфункцию u1 &u2 c ненадежностью не более 0.002?7.5.∗ Ниже приведены распределения режимов работы ФЭ Ei , i =1, ..., b, ненадежного базиса Б.

Покажите, что в данном базисе возможнасколь угодно надежнаяреализация произвольной функции.u1 ⊕ u2 u1 ∨ u21) b = 1, E1 :;1−ppu1 ∨ u2 1u1 ⊕ u2 1u1 &u22) b = 3, E1 :, E2 :, E3 :.1−p p1−p p1Другой (так называемый логико-комбинаторный [12]) подход к определению уровня надежности схемы связан с понятием самокорректируемости. Схема Σ называется самокорректирующейся относительноисточника неисправностей И, если в модели (Σ, И) все состояния эквивалентны.

Естественно считать, что чем больше неисправностей корректирует схема Σ, тем выше уровень ее надежности. Задача синтезасамокорректирующихся схем является важным частным случаем общейзадачи синтеза.Рассмотрим задачу синтеза контактных схем, которые являются самокорректирующимися относительно источника неисправностей Иr,s (см. §5).

Простейший способ решения этой задачи связан с последовательными (или) параллельным дублированием двухполюсной КС. Легко видеть,что если при этом взять l экземпляров самокорректирующейся относительно Иr,s КС Σ и соединить их последовательно (параллельно), то получим эквивалентную Σ КС Σ0 , которая является самокорректирующейся относительно ИR,S , где R = r, S = (s + 1) · l − 1 (соответственноR = (r + 1) · l − 1, S = s).

Аналогичный результат дает указанное выше дублирование, если его применять к каждому контакту схемы (этотспособом можно строить многополюсные самокорректирующиеся КС).Другой способ перехода от (многополюсной) КС Σ к эквивалентной ейКС Σ0 , которая является самокорректирующейся относительно Иσ,1−σ ,где σ ∈ {0, 1}, заключается в следующем. Разобьем КС Σ на непересекающиеся связные (многополюсные) подсхемы Σ1 , . . . , Σl , каждая изкоторых состоит из контактов одного типа, а затем заменим КС Σi ,i = 1, . . .

, l, на КС Σ0i , состоящую из контактов того же типа, которая(i)(i)представляет собой цикл, проходящий через все вершины v1 , . . . , vai КСΣi , если σ = 1 (см. рис. 27 а)) и звезду с центром в новой вершине, соеди(i)(i)ненной со всеми вершинами v1 , . . . , vai КС Σi , если σ = 0 (см. рис. 27 б)).(i)xδv2(i)v2xδ(i)v1(i)v3xδ(i)v1xδ•xδ ....(i)xδxδ..(i)v3(i)vaivaiа)б)Рис. 277.6. 1) Доказать, что если функция xσi , где 1 ≤ i ≤ n и σ ∈ {0, 1}может быть получена из функции f (x1 , ..., xn ) в результате некоторойподстановки констант вместо БП x1 , ..., xi−1 , xi+1 , ..., xn , то в любой КС,реализующий f и корректирующей r обрывов (r замыканий), содержитсяне менее (r + 1) контактов xσi .2) Построить для функции x1 ⊕x2 минимальную КС, корректирующуюа) одно размыкание,б) одно замыкание.7.7.

По контактной схеме Σ построить эквивалентную схему, корректирующую замыкание m контактов и содержащую не более l контактов.1) m = 1, l = 6Σ:2) m = 1, l = 7Σ:3) m = 1, l = 10Σ:4) m = 1, l = 4Σ:5) m = 1, l = 10Σ:6) m = 1, l = 6Σ:7) m = 1, l = 9Σ:8) m = 1, l = 4Σ:7.8. По контактной схеме Σ построить эквивалентную схему, корректирующую размыкание (обрыв) m контактов и содержащую не более lконтактов.1) m = 1, l = 10Σ:2) m = 1, l = 4Σ:3) m = 1, l = 9Σ:4) m = 1, l = 8Σ:5) m = 1, l = 4Σ:6) m = 1, l = 9Σ:7) m = 1, l = 10Σ:8) m = 1, l = 4Σ:7.9.

Построить по КС Σ эквивалентную ей КС Σ0 , корректирующую1) одно размыкание2) одно замыканиеи такую, чтоа) L(Σ0 ) ≤ 30, если Σ — КС на рис. 28,б) L(Σ0 ) ≤ 25, если Σ — КС на рис. 29,в) L(Σ0 ) ≤ 28, если Σ — КС на рис. 30.•x̄3ax2 x̄3••x1•x4 x̄3x̄4 x3x3x3•x̄2•x4x̄2 x̄1b1x2 x1•ax̄4•b2x̄2 • x̄1Рис. 28.x̄3•••x3x̄3•x2•x̄2x2•x1bx̄1x̄3 • x̄2Рис. 29.x̄3•x̄3x̄3•ax̄4x3x4•x2x3x̄3x1•••x̄2x̄2•Рис. 30.x̄1x1b1•x̄1b2a•x2x4x1 • x3bx̄2x̄4x2•Рис. 31.7.10.

Рассматривается КС на рис. 31.1) Построить по этой схеме КС не более чем из 13 контактов, корректирующуюа) одно размыкание,б) одно замыкание.2) Построить для функции, реализуемой этой схемой, минимальнуюКС, корректирующуюа) одно размыкание,б) одно замыкание.7.11.∗ Для функции m(x1 , x2 , x3 ) = x1 x2 ∨ x1 x3 ∨ x2 x3 построить КСсложности 8, корректирующуюа) одно размыкание,б) одно замыкание.Указание.

Каркасы этих схем представлены на рис. 32 и 33 (соответственно).••ab••ab•••Рис. 33.Рис. 32.•x2a•x2••x̄2x1x̄1bx4x3x2x̄2 •Рис. 34.x̄4••a••b•••x̄3Рис. 35.7.12.∗ Доказать, что минимальная корректирующая одно размыканиеКС для линейной булевой функции, существенно зависящей от всех своих n переменных, имеет сложность 4n (КС, реализующая эту функцию,представлена на рис.

21).7.13. Рассматривается КС на рис. 34. Построить по этой схеме КС,корректирующую одно размыкание и имеющую сложность не более 18.7.14.∗ Для элементарной симметрической функции трех переменныхс рабочим числом два S32 (x1 , x2 , x3 ) = x̄1 x2 x3 ∨ x1 x̄2 x3 ∨ x1 x2 x̄3 построитьминимальную корректирующую одно размыкание КС. Указание. Каркасэтой схемы представлен на рис. 35.7.15. Обозначим через Lp (f ), p ≥ 0, сложность минимальной КС,реализующей функцию f и корректирующей p обрывов (p замыканий)контактов.

Докажите, что если для натурального s и целых неотрицательных k, k1 , . . . , ks имеет место равенство k1 + · · · + ks + s = k + 1, тоLk (f ) ≤ Lk1 (f ) + · · · + Lks (f ).7.16.∗ Покажите, что в случае размыкания для величин, введенных взадаче 7.15, справедливы неравенства:а) 6(p + 1) ≤ Lp (x1 ⊕ x2 ⊕ x3 ) ≤ 6(p + 1) + 2((p + 1) mod 2),б) 6(p + 1) ≤ Lp (S32 (x1 , x2 , x3 )) ≤ 6(p + 1) + ((p + 1) mod 2), гдеS32 (x1 , x2 , x3 ) = x̄1 x2 x3 ∨ x1 x̄2 x3 ∨ x1 x2 x̄3 .7.17.∗ Пусть Σ — корректирующая один обрыв КС, в которой можновыделить s пар вершин (все вершины различны) таких, что по анализупроводимостей между этими парами вершин можно обнаружить любойединичный обрыв контакта. Показать, что схему Σ можно преобразоватьв корректирующую один обрыв КС Σ0 такую, что любой единичный обрыв контакта в ней может быть обнаружен по анализу проводимостеймежду двумя вершинами схемы.Ответы, указания и решенияК параграфу 1.1.1.

1) Да; 2) да; 3) нет; 4) нет.1.2. 1) Нет. Пример: {x}. 2) Нет. Пример: {0, 1, x̄}.1.3. Да.1.4. 6) Нет, так как, например, функция f (x, y) = x ∨ y являетсясимметрической, но при добавлении в нее фиктивной переменной z получается несимметрическая функция g(x, y, z) = x ∨ y.7) Да.1.6. Пусть n ≥ 0 и f (x1 , . . . , xn , xn+1 ) — произвольная функция изQ(n + 1). Из разложенияf (x1 , .

. . , xn , xn+1 ) = xn+1 f (x1 , . . . , xn , 1) ∨ x̄n+1 f (x1 , . . . , xn , 0)следует, что функция f полностью определяется парой своих подфункций f (x1 , . . . , xn , 1) и f (x1 , . . . , xn , 0). Поскольку последние также принадлежат классу Q, имеем|Q(n + 1)| ≤ |Q(n)|2 .Отсюда2n+1ppn|Q(n + 1)| ≤ 2 |Q(n)|.(4)pnИз (4) вытекает невозрастание последовательности 2 |Q(n)|. Покажем,что она ограничена. Если Q не пусто, то√pp√nn2n2n1 = 1 ≤ 2 |Q(n)| ≤ 2 |P2 (n)| = 22n = 2.(5)pnСледовательно, предел последовательности 2 |Q(n)| существует и заключен в сегменте [1, 2].1.7. В самом деле, при некотором фиксированном m pсуществует2n|Q(n)| нефункция g(x1 , .

. . , xm ) ∈/ Q. Так как последовательностьвозрастает, тоppm−mnmlim 2 |Q(n)| ≤ 2 |Q(m)| ≤ (22 − 1)2 < 2.n→∞1.8. 2) Воспользоваться тем, что число монотонных функций, зависяnщих от переменных x1 , x2 , . . . , xn , не превосходит n(dn/2e) .3) 1/2. Нижняя оценка |Q(n)|. Выберем линейную функцию l в (3)равной x1 ⊕ . . . ⊕ xn . Пусть B n,1 — множество двоичных наборов длиныn с нечетным числом координат, равных 1. Через Nf обозначим множество наборов, обращающих функцию f в единицу. Ясно, что Nl = B n,1и |B n,1 | = 2n−1 .

Среди функций g(x1 , . . . , xn ) ∈ P2 найдется множествоn−1G из 22функций попарно отличающихся друг от друга на множеn,1стве B . Ясно, что число функций вида (3) с l = x1 ⊕ . . . ⊕ xn и g ∈ Gn−1n−1равно 22 . Отсюда 22 ≤ |Q(n)|.Верхняя оценка |Q(n)|. При фиксированной функции l = xi1 ⊕ . . . ⊕r−1n−1xir имеется не более 22 ≤ 22 различных функций f ∈ Q(n).

Числолинейных функций, зависящих от переменных x1 , . . . , xn , равно 2n+1 .n−1Поэтому |Q(n)| ≤ 2n+1 22 . Таким образомn−122≤ |Q(n)| ≤ 2n+1 22n−1.Отсюдаlimn→∞2np|Q(n)| = 21/2 .Тем самым построен инвариантный класс Q с характеристикой σ = 1/2.1.12.1. а) U (M ) = {x̄}. Указание. Воспользуйтесь доказательством леммы о немонотонной функции. б) U (L) есть множество всех попарнонеконгруэнтных нелинейных функций переменных x, y.

Указание. Воспользуйтесь доказательством леммы о нелинейной функции. в) U (Q)есть множество всех функций, существенно зависящих ровно от k + 1переменных. г) U (Q) = {xy, x ∨ y, x̄}.2. Класс квазисимметрических функций. Указание. Каждая функцияgn (x1 , x2 , . . . , xn ) = x1 x2 · · · xn ∨ x̄2 · · · x̄n является порождающим элементом данного класса (есть и другие).4. Верхняя оценка очевидна. Получим нижнюю. Пусть Qn — минимальный инвариантный класс, содержащий функцию gn (x1 , x2 , . .

. , xn ) =x1 x2 · · · xn ∨ x̄1 x̄2 · · · x̄n . Все классы Qn попарно различные. Пусть,Sдалее,α = 0, a1 a2 . . . — бесконечная двоичная дробь. Положим Qα =Qn .n: an =1Легко видеть, что Qα есть инвариантный класс и при α1 6= α2 имеем:Qα1 6= Qα2 . Нижняя оценка доказана.К параграфу 2.2.11. 1) K 0 = (x1 ∨x2 ∨t1 )(t̄1 ∨x3 ∨x4 )(x̄1 ∨x2 ∨t2 )(t̄2 ∨x̄3 ∨x̄4 )(x̄2 ∨x̄3 ∨x4 ).−1 −1 0−12.12.

1) A =, b=;−1 0 −1−10 −1 004) A =, b=.−1 0 −1−12.19. 1), 3), 5), 7) – полиномиально решаемые, 2), 4), 6), 8) – N P полные.2.20. 1) а), г), д), 2) а), г), д), 3) а), г), д), 4) а) – полиномиальнорешаемые, 1) б), в), 2 б), в), 3) б), в), 4 б) – N P -полные.К параграфу 3.3.1. 4)(x1 ·(x2 ·x3 ))·(x4 ·x5 ) = ((x1 ·x2 )·x3 )·(x4 ·x5 ) = (((x1 ·x2 )·x3 )·x4 )·x5 .3.2. Указание. Докажите индукцией по n, что выражение x1 ·x2 ·. . . xnс любой правильной расстановкой скобок можно с помощью тождества(6) преобразовать в выражение (. . . ((x1 · x2 ) · x3 ) · .