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

. . · 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, . . . , 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 , .