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

, n − 1}). Достижимость нижней (верхней)границы доказывает матрица из задачи 5.2.1 (соответственно 5.2.2 приk = 0).5.10. Нет. Указание. Рассмотрите матрицу M (2) , доказывайте от противного.5.11. Указание. Рассмотрите матрицу M (2) и оцените сверху числоединиц в тех ее строках, которые связаны с тестом.5.12. Пусть T , T ⊆ b1, me — тест матрицы M , а Ji , Ji ⊆ b2, n + 1e —множество номеров тех столбцов матрицы M , которые образуют группус номером i, i = 1, ..., s, из условия задачи. Пусть, далее, Ji0 , i = 1, ..., s,— множество тех чисел j, j ∈ Ji , для которых столбец M hT, ji содержитровно одну единицу. Так как в каждой строке подматрицы M hT, Ji i имеется не более одной единицы, то |Ji0 |+2(|Ji |−|Ji0 |) ≤ |T |, и, следовательно,|Ji0 | ≥ 2|Ji | − |T |.

Суммируя последние неравенства по всем i, i = 1, ..., s,и учитывая, что в подматрице M hT i число столбцов, содержащих однуединицу, не больше, чем |T |, получим: |T | ≥ 2n − s · |T |.К параграфу 6.6.1. {(100), (101)}, {(100), (111)}, {(101), (110)}, {(101), (111)},{(110), (111)}.6.2. Ответы пунктов а) и б) совпадают: {(000), (001), (010)}, {(000),(001), (100)}, {(000), (010), (111)}, {(000), (100), (111)}, {(001), (010),(101)}, {(001), (100), (101)}, {(010), (101), (111)}, {(100), (101), (111)}.6.3. а) {(101)}, {(011), (110)}; б) {(011), (101)}, {(101), (110)}, {(011),(110)}.6.4. Ответы пунктов а) и б) совпадают: {(000), (001), (101)}, {(001),(101), (110)}, {(000), (001), (111)}, {(001), (110), (111)}.6.5.

Ответы пунктов а) и б) совпадают: {(000), (100), (111)}, {(000),(101), (111)}, {(010), (100), (111)}, {(010), (101), (111)}.6.6. {(100), (111)}, {(001), (010), (111)}, {(001), (010), (100)}.6.7. Ответы пунктов а) и б) совпадают: {(000)}.6.8. а) {(010), (101)}, {(100), (110)}, {(010), (100), (111)}; б) {(010),(100), (101)}, {(010), (100), (110)}, {(010), (100), (111)}, {(010), (101),(110)}, {(100), (101), (110)}.6.9.

Указание. Доказательства проводятся от противного.6.10. 1) Указание. Найдите r групп по (n − r) контактов в каждой,единичные обрывы которых дают матрицу, удовлетворяющую (после инвертирования) условиям задачи 5.12; 2) (Р. Н. Тоноян [19]). Рассмотрите при n ≥ 2r множество наборов, порождаемых следующими словами длины n в алфавите {0, 1}: 0s1 1r 0n−s1 −r , 1s2 0n 1r−s2 , 1s3 [01]r−s3 0n−2r+s3 ,0s4 [01]s4 0n−2r−s4 , 0n−2r+s5 [01]r−s5 1s5 (s1 = 0; n − r, s2 = 1; r − 1, s3 =0; r − 1, s4 = 1; n − 2r, s5 = 1; r − 2).6.11.

n + 1.6.12. 1) 2. 2) Указание. Используйте метод дихотомии, т. е. делениясхемы на две части.6.13. а) 2n−1 , б) 2n−1 , в) 2n .6.14. Указание. Рассмотрите наборы единичной сферы и ее центр.Достижимость оценки проиллюстрируйте на схеме, построенной по методу каскадов.6.15. (Х. А. Мадатян [14]). Указание. Докажите, что среди неисправных схем найдутся схемы, реализующие обе константы, а также схемы,реализующие или xσ1 1 xσ2 2 · · · xσnn , или xσ1¯1 ∨xσ2¯2 ∨· · ·∨xσn¯n для любого набора(σ1 , σ2 , . .

. , σn ).6.16. 1) Указание. Рассмотрите изолированный блок этой схемы. 2)а) 2 при четных n, 3 при нечетных n; б) 4; в) 6 при четных n, 7 при нечетных n. 3) (Р. Н. Тоноян [18]). Указание. Используйте метод дихотомии.Длина теста не более, чем на константу, отличается от log2 n. 4) а) (Р.Н. Тоноян [18]). Указание. Используйте метод дихотомии. б) Указание.Используйте метод деления схемы на 4 части.6.17. (Н. П. Редькин [6]). Указание. Рассмотрите КС, реализующуюфункцию f (x1 , . .

. , xn ) и построенную по формуле (Kf (x1 ∨ x̄1 ))·(Df (x1 ∨x̄1 )), где Kf и Df — конъюнктивная и дизъюнктивная совершенные нормальные формы функции f .6.18. 1) а) {(00), (01), (11)}, число тестов — 2; б) {(001), (010), (011),(110), (111)} (порядок переменных — x, y, q 0 ), число тестов — 12. 2){(001), (011), (110)} (порядок переменных — x, y, q 0 ). 3) {(1000), (0001),(0110)} (порядок переменных — a, b, x, y). 4) {(0000), (0111), (1111)}.6.19. 2) Указание. Рассмотрите схему на рис. 25 и заметьте, что неисправность типа 0 на выходе третьего слева инвертора в нижнем рядуинверторов обнаруживается лишь на наборе (0001), не входящем в тестиз задачи 6.18.4.6.20. (Н. П.

Редькин [6]). Указание. Искомая схема строится по индукции из блоков, каждый блок подобен схеме на рис. 22 а) без выходаz1 . Тест из четырех наборов: (0, 0, 0, . . . , 0), (1, 0, 0, . . . , 0), (0, 1, 1, . . . , 1),(1, 1, 1, . . . , 1).6.21. 1) Введем обозначение:01 11 11 01 11 11 01 00M = 11 01 00 01 01 00 01 1100 01 11 110001111101,N =1111110100.Матрица теста T размером 5 × 2n при этом будет иметь вид T =(M 0 M M . . . M N ), где матрица M 0 получается из матрицы M выбрасыванием нужного количества первых столбцов (порядок переменных —x1 , y1 , x2 , y2 , . .

. , xn , yn ). Указание. Для построения теста используютсятаблицы неисправностей из задачи 6.18.1. При этом существенны следующие факты. Любая неисправность блока с номером n вида Σ1 схемы Σnобнаруживается по анализу функции неисправности на его втором выходе (т.

е. на выходе схемы zn ). Если неисправность в блоке с номером i,1 < i < n, не обнаруживается на его втором выходе (т. е. на выходе схемыzi ), то на наборах теста функция неисправности, реализуемая на выходесхемы zi−1 , отличима от всех функций неисправности, возникающих наэтом выходе при всевозможных неисправностях в блоке с номером i − 1.Все неисправности в i-м блоке (1 ≤ i ≤ n), не отличимые по анализуфункции неисправности на его втором выходе (т. е. на выходе схемы zi ),отличаются на наборах теста по анализу функции неисправности на выходе схемы zi−1 . Нижняя оценка длины теста следует из задачи 6.18.1для блока, вычисляющего два старших разряда суммы.2) Наборы теста порождаются словами длины 2n следующего вида: [00]i−1 11[01]n−i , [11]i−1 00[01]n−i (i = 1; n), порядок переменных —xn , yn , .

. . , x2 , y2 , x1 , y1 . Указание. Для построения теста используетсятаблица неисправностей из задачи 6.18.2. Нижняя оценка следует из конструктивных соображений.3) Наборы теста порождаются словами длины 2n следующеговида: [01]n , 10[01]n−1 , 00[10]n−1 , 01[10]n−1 , порядок переменных —an , bn , xn−1 , yn−1 , xn−2 , yn−2 , . . .

, x2 , y2 , x1 , y1 . Указание. Для построениятеста используется таблица неисправностей из задачи 6.18.3.6.22. (S. M. Reddy [21]). Указание. Рассмотрите разложение булевойфункции в полином Жегалкина.6.23. (В. Н. Носков [15]). Указание. Верхняя оценка очевидна. Длядоказательства нижней рассмотрите функцию x1 x2 . . . xn ∨ x̄1 x̄2 . . . x̄n .6.24.

(И. А. Чегис, С. В. Яблонский [20]). Указание. Используйтеасимптотически наилучший метод синтеза схем.6.25. Указание. Доказательства проводятся от противного.К параграфу 7.7.1. 1) Следует из (6.1)–(6.3). 2) Достаточно использовать (6.5). 3)Достаточно выразить ξ(Σ) через вероятности ξ(Ei , β).77.2. 1) ξ(M) = η(M) = 41 . 2) ξ(M) = η(M) = 16. 3) ξ(M) =5η(M) = 9 .7.3. 1) p = 13 . 2) p = 14 .7.4. 1) Да. 2) Да.7.5. Указания. 1) Реализуйте сколь угодно надежно функцию x|y. 2)Реализуйте сколь угодно надежно функции x ⊕ y и 1.7.6. 1) Доказательство проводится от противного.

2) Используйте КС,построенную по совершенной ДНФ функции x1 ⊕ x2 , а также результатзадачи 7.6.1.7.9. Указание. Используйте описанное в предисловии эквивалентноепреобразование связных многополюсных подсхем, состоящих из контактов одного вида.7.10. 1) Указание. Аналогично 7.9. 2) Воспользуйтесь тем, что схемареализует функцию x1 (x̄4 ∨ x3 ) ∨ x2 , а также результатом задачи 7.6.1.7.11. Схемы представлены на рис. 36 и 37 соответственно.7.12. (В. М. Рабинович [16]). Указание. К схеме на рис.

21 надо добавить 4 контакта x1 , x̄1 , xn , x̄n так, чтобы первые два были бы инцидентны полюсу b (но не полюсу a), вторые два — полюсу a (но не полюсуb) схемы, и при этом каждый из новых контактов должен быть смеженс имеющимся в схеме противоположным контактом той же переменной.7.13. Указание. Используйте результат задачи 7.12.•x1ax2x2x3•x3x1b ax1x2x3x2x2x3••x3x2x3x1•x1•ab•x̄3x2 •x3 x̄1 x̄3••x̄2x̄2 •x̄1•x3x2bx1•Рис.

36.Рис. 37.Рис. 38.7.14. Схема представлена на рис. 38. Указание. Нижняя оценкасложности следует из задачи 7.6.1.7.15. Указание. Используйте параллельное (последовательное) соединение схем, на которых достигаются Lk1 (f ), . . . , Lks (f ).7.16. (Е. В.

Валентинов [13]). Указание. а) Верхняя оценка. Используйте при n = 3 схемы на рис. 21 и из решения задачи 7.12, далее воспользуйтесь результатом задачи 7.15. б) Верхняя оценка. Используйте схемуна рис. 17 (при n = 3 и r = 2) и схему на рис. 36, далее воспользуйтесьрезультатом задачи 7.15. Нижние оценки следуют из задачи 7.6.1.7.17. (А. И. Рыбко [17]). Указание.