В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин и др. - Задачи по курсу Основы кибернетики (2011) (1124117), страница 9
Текст из файла (страница 9)
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, .
. . , 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 00M = 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 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
