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

Построить по КС Σ эквивалентную ей КС Σ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 ) · . . . · xn−1 ) · xn (см.4.1).3.3. Указание. 2) и 4) приведите к виду xx̄, остальные к совершеннойдизъюнктивной нормальной форме.(1)(5,4)(5,8)(14,13)2) x ∨ y · (xz̄ ∨ y) = x̄ȳ · (xz̄ ∨ y) = x̄ȳxz̄ ∨ x̄ȳy) = xx̄ ∨ y ȳ = xx̄.(11)(4)(5)5) xy ∨ yz = (z ∨ z̄)xy ∨ (x ∨ x̄)yz = zxy ∨ z̄xy ∨ xyz ∨ x̄yz = xyz ∨(10,12)(13)xyz̄ ∨ xyz ∨ x̄yz = (xyz ∨ xyz) ∨ xyz̄ ∨ x̄yz = xyz ∨ xyz̄ ∨ x̄yz.3.5.

См. задачу 4.4.(3)(3)(2)¯ 1 ∨ x̄¯ 2 = x̄1 &x̄2 =3.6. Выведем (1), используя (2)-(9): x1 · x2 = x̄x̄1 &x̄2 .(3)(5)(2)(2)¯ 1 ∨ x̄¯ 2 = x̄1 · x̄2 = x̄2 · x̄1 =Выведем (10), используя (2)-(9): x1 ∨ x2 = x̄(3)¯ 2 ∨ x̄¯ 1 = x2 ∨ x1 .x̄Указание. Для вывода (11), (12) и (13) сводите, используя (2)-(3),дизъюнкцию к конъюнкции и обратно и используйте (9), (6) или (7),соответственно. Для вывода (14) используйте (8) и (5).3.7.

Указание: при помощи тождеств (1)-(14) приведите обе формулык совершенной д.н.ф. Ответ: 1), 3), 6)-11) — да; 2), 4), 5) — нет.3.8. Указание: при помощи тождеств (1)-(14) обе формулы можнопривести к совершенной д.н.ф.3.9. 1) Указание: постройте систему тождеств, позволяющую любуюформулу над базисом B = {xy, x ⊕ y, 1} переводить в полином Жегалкина.2) Например: тождества (4)-(7), (10), (12), (13) вместе с тождествами0&0 = 0, 1&1 = 1, x&0 = 0, x&1 = x, 0 ∨ 0 = 0, 1 ∨ 1 = 1, x ∨ 0 = x,x ∨ 1 = 1.3.10.

2) Указание. Докажите индукцией по n, что выражение x1 ·x2 · . . . xn с любой правильной расстановкой скобок можно с помощьютождеств A1 , Bm , Cm преобразовать в выражение (. . . ((x1 · x2 ) · x3 ) · . . . ·xn−1 ) · xn (см.4.1).К параграфу 4.4.2. Указание. TII : используйте тождество t2 . Многократно используйте тождества t5 и t2 . 3) Многократно используйте тождества t5 и t2 иmзатем tm6 . 4) Используйте тождества t6 и t5 .4.4.

1) Нет; 2) да.К параграфу 5.5.1. 1) 2; 2) 3; 3) 2; 4) 3; 5) 2; 6) 3.5.2. 1) n; 2) n − 1; 3) n − 1; 4) n.5.3. Указание. Два столбца матрицы M различаются в j-й строкетогда и только тогда, когда j-я строка матрицы M (2) покрывает суммупо модулю 2 этих столбцов.5.5. 1), 4), 5), 7) — Да. 2), 3), 6), 8), 9) — Вообще говоря, нет.5.6.

Пусть A и B — тупиковые тесты матрицы M с m строками. Тогдани одно из включений A ⊂ B, B ⊂ A не имеет места. Отсюда вытекает,что число тупиковых тестов не превосходит максимального числа попарнонесравнимых наборов в B m , а значит, не превосходит величиныmb m2 c .5.7. Число матриц размерности k×n с попарно различными столбцамиравно 2k (2k − 1) · . . .

· (2k − n + 1). Число матриц размерности m × n, укоторых k строк с фиксированными номерами заданы, равно 2n(m−k) .5.8. 1) {1, 2}, {1, 4}, {2, 3}, {3, 4}; 2) {1, 2, 3}, {1, 2, 4}, {1, 3, 4}; 5){1, 2, 3}, {1, 2, 5}, {2, 3, 4}, {1, 4, 5}, {3, 4, 5}; 6) {1, 2, 3}, {2, 3, 5}, {3, 4, 5}.5.9. Указание. Нижняя оценка доказывается от противного из предположения о существовании теста длины меньшей, чем dlog2 ne. Для доказательства верхней оценки изучите число классов эквивалентности, накоторые все n столбцов матрицы тупикового теста разбиваются ее первыми l строками (l ∈ {1, . . .