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

. . , uj−1 , σ, uj+1 , . . . , uk ) (соответственно σ). Можно рассматривать константные неисправности различных типов, а также константные неисправности как на входах, так и навыходах ФЭ.При описании источника неисправностей в КС или СФЭ Σ часто выделяется множество Σ̆ тех элементов или “узлов” Σ, которые могут выходить из строя, и указываются возможные неисправные состояния каждого из них.

При этом источник, допускающий любую комбинацию любыхнеисправных состояний для любого подмножества (подмножества мощности 1) элементов множества Σ̆, называется полным (соответственно,единичным) источником для множества Σ̆ и заданных неисправных состояний его элементов, а связанный с ним тест — полным (соответственно, единичным) тестом. По умолчанию считается, что Σ̆ = Σ.6.1.

Тесты для контактных схем6.1. Построить все тупиковые диагностические тесты для КС нарис. 10 и источника неисправностей, допускающего обрыв одного из контактов вида x.•z̄xyaȳ•••xȳbayz•Рис. 10.•zxx̄ȳx̄•ybxz̄•Рис. 11.6.2. Построить все тупиковыеа) проверяющиеб) диагностическиетесты для КС на рис. 11 и источника неисправностей, допускающегоразмыкание контактов вида z̄, z, а также замыкание контакта вида y,причем общее число неисправных контактов не может быть больше 1.6.3. Построить все тупиковыеа) проверяющиеб) диагностическиетесты для КС на рис.

12 и источника неисправностей, допускающегообрыв одного контакта переменных x, z.•yxax̄ȳ•••z̄ȳzy•Рис. 12.y•z̄xzb az•ȳ•yz̄b a•Рис. 13.xȳx̄ z••x̄ybx̄Рис. 14.6.4. Построить все тупиковыеа) проверяющиеб) диагностическиетесты для КС на рис. 13 и источника неисправностей, допускающего однуиз следующих неисправностей: обрыв контакта z̄, обрыв выделенногоконтакта z и замыкание выделенного контакта y.6.5. Построить все тупиковыеа) проверяющиеб) диагностическиетесты для КС на рис.

14 с единичным источником неисправностей, допускающим обрыв контактов вида z, z̄ или замыкание контакта вида y.6.6. Построить все тупиковые диагностические тесты для КС нарис. 15 и источника неисправностей, допускающего замыкание одногоиз контактов вида x̄, y, ȳ.••zz̄xx̄yxa••xx̄zb aȳz̄•ȳz̄z̄b ax̄•xzbx̄zyȳxy•••Рис. 15.Рис. 16.Рис. 17.6.7. Построить все тупиковыеа) проверяющиеб) диагностическиетесты для КС на рис.

16 и источника неисправностей, допускающегозамыкание одного контакта переменных y, z.6.8. Построить все тупиковыеа) проверяющиеб) диагностическиетесты для КС на рис. 17 и источника неисправностей, допускающегоразмыкание одного контакта вида x, y или z̄.6.9. Пусть в двухполюсной КС Σ от переменных x1 , . . . , xn для любого набора α = (α1 , . . . , αn ) из Nf найдется единственная не содержащаяконтактов вида xα1¯1 , . . . , xαn¯n цепь Cα , соединяющая полюса. Пусть источник неисправностей И допускает обрыв не более, чем одного из контактовk1 , . .

. , ks−1 КС Σ и порождает при этом s отличимых состояний.1) Доказать, что множество наборов T , T ⊆ B n , образует проверяющий тест для (Σ, И) тогда и только тогда, когда для каждого контактаki , i = 1, . . . , (s − 1), найдется цепь Cα , α ∈ T , проходящая через него.2) Доказать, что множество наборов T , T ⊆ B n , образует диагностический тест для (Σ, И) тогда и только тогда, когда оно образует проверяющий тест и для любых двух контактов ki и kj , где 1 ≤ i < j ≤ (s−1),найдется такой набор α, α ∈ T , что цепь Cα проходит через один из этихконтактов и не проходит через другой.6.10.∗ Рассматривается построенная по методу каскадов КС Snr (см.рис. 18), реализующая элементарную симметрическую функцию от nпеременных с рабочим числом r (т.

е. функцию, принимающую значение1 на всех наборах из Brn и только на них).1) Используя результат задачи 5.12, получить нижнюю оценку вида2r(n−r)для длины единичного диагностического теста размыкания данr+1ной схемы.2) Показать, что для Snr существует единичный диагностический тестразмыкания длины, не превосходящей 2n − 2.6.11. Найти длину минимального единичного проверяющего теста дляразмыкания контактов в КС на рис.

19.6.12. Рассмативается КС на рис. 20.1) Найти длину минимального единичного проверяющего теста дляразмыкания.2) Построить такой единичный тест размыкания для контактов видаx1 , . . . , xn , x̄1 , . . . , x̄n , длина которого не превосходит величины dlog2 ne+2.x̄1 • x̄2 • x̄3 • . . . • x̄n−r−1 • x̄n−r •ax1x2x3x4xn−r−1 xn−rxn−r+1x̄2 • x̄3 • x̄4 • . . . • x̄n−r • x̄n−r+1 ••x2x3x4x5xn−rxn−r+1 xn−r+2x̄x̄x̄x̄x̄n−r+2 •345n−r+1... ••••••........ . ........ x̄. x̄. x̄.. x̄..

. x̄rr+1 •r+2 •n−2 •n−1 •... •••xrxr+1xr+2xr+3xn−2xn−1xnx̄x̄x̄x̄x̄r+1 •r+2 •r+3 •n−1 •n... ••bРис. 18.... •... •••••xixn−1x2xxn1ax̄2x̄1••x1ax̄2x2x̄n+1x̄1•x̄ix̄3x̄2•...•...x̄n+2•...x̄i+1x̄i •Рис. 19.••xi•x̄n+i−1...•...•x̄n+ix̄i •Рис. 20.•x̄n−1...x̄nx̄n−1xn−1•bx̄n•xnbx̄2n−2x̄2n−1•x̄n−1•x̄n•x1ax̄1x2•x̄2x̄2•...x2••xi...x̄i••...•xix̄i •Рис. 21.•...•x̄n−1xxn−1 nbxn−1x̄n−1 • x̄n6.13. На основе контактного дерева построена КС для функцииf (x1 , . . . , xn ) = x1 ⊕ x2 ⊕ .

. . ⊕ xn . Для этой схемы найти длину минимального единичного тестаа) размыкания,б) замыкания,в) как размыкания, так и замыкания.6.14. Единичной сферой с центром в точке α, α ∈ B n , называетсямножество всех наборов куба B n , отличающихся от набора α только водной координате.Докажите, что длина минимального единичного теста размыкания дляпроизвольной КС, реализующей характеристическую функцию единичной сферы куба B n , не меньше n. Покажите, что указанная оценка достижима.6.15.∗ Докажите, что для функции f (x1 , .

. . , xn ) = x1 ⊕ x2 ⊕ . . . ⊕ xn несуществует КС от n переменных, имеющей полный тест длины меньшей,чем 2n .6.16.∗ Рассматривается построенная по методу каскадов КС Σn , реализующая линейную функцию x1 ⊕ x2 ⊕ · · · ⊕ xn ⊕ 1 при n ≥ 3 (см.рис. 21).1) Докажите эквивалентность единичных замыканий одноименныхконтактов.2) Найдите длину минимального единичного проверяющего тестаа) замыкания,б) размыкания,в) как размыкания, так и замыкания.3) Постройте асимптотически минимальный единичный тест замыкания.4) Постройте единичный тест размыкания, длина которого не превосходита) 2 log2 n + 7,б) 23 log2 n + 10.6.17.∗ Доказать, что любую булеву функцию можно реализовать КС,допускающей единственный полный проверяющий тест, состоящий извсех наборов.6.2.

Тесты для схем из функциональных элементов6.18. 1) Построить минимальный единичный диагностический тестотносительно константных неисправностей на выходах ФЭ схемы нарис. 22 а), б)3 и указать число таких тестов.2) Построить минимальный единичный проверяющий тест относительно константных неисправностей на выходах ФЭ схемы на рис. 23 а).3) Построить минимальный единичный проверяющий тест относительно константных неисправностей на выходах ФЭ схемы на рис. 24 а).4) Построить минимальный проверяющий тест относительно константных неисправностей на выходах тех ФЭ схемы на рис.

25, которыесодержат входы схемы.6.19. 1) Показать, что тест, проверяющий константные неисправности на выходах ФЭ, среди входов которых есть либо входы схемы, либоветвящиеся выходы функциональных элементов, является проверяющимтестом для константных неисправностей на выходах всех ФЭ схемы (приэтом предполагается, что базис не содержит ФЭ, реализующих константы).xqΣ1 :yqAQQ QQAAA&A∨AA@@z1 A− A@@ A&A?z2а)xqΣ0 :q 0qyqΣ11A∨ A?z1Σ1?z22б)При изображении схем из функциональных элементов в настоящем пособии действуют правила:1) общими точками проводников могут являться лишь точки выходов функциональных элементов,2) входы каждого функционального элемента упорядочены слева направо.3xq 1 yq1xq 2 xq n yq2 yqn...Σ0Σn :...Σn−1?.

. . . .z10 z2znв)Рис. 22. Схема сумматора Σn??z0z1xq0Σ̂ :yqqqAQQ QQAA A&A∨AAA&AA AAAAA∨ A 00q?a q bq qxСхема Σ̂n :xq 1 yq1...Σ̂n−1?б)anq bnq xq n−1qyn−1A&A0 ? ?0a...Схема Σ̃n :A∨ Aа)xq 2 xq n yq2 yqnΣ̂0yqA&AA∨ A0z0Рис. 23.а)Σ̃2 :?Σ̃2bxn−2xy qq . . . q 1q .

n−2. . y1Σ̃n−1?a1 ?b1б)Рис. 24.2) Показать, что СФЭ на рис. 25 является примером схемы, для которой единичный тест, проверяющий константные неисправности на выходах лишь тех ФЭ, среди входов которых есть входы схемы, не являетсяединичным проверяющим тестом для константных неисправностей навыходах всех ФЭ схемы.6.20.∗ Реализовать линейную функцию x1 ⊕ x2 ⊕ . . . ⊕ xn СФЭ в стандартном базисе, допускающей единичный тест из четырех наборов, проверяющий константные неисправности на выходах ФЭ схемы.6.21.∗ 1) Доказать, что длина минимального единичного теста, диагностирующего константные неисправности на выходах ФЭ схемы сумматора Σn при n ≥ 3 (рис.

22 в)), равна 5.2) Схема Σ̂n на рис. 23 б) имеет сложность 4n−3 и вычисляет старшийразряд z0 суммы z0 z1 . . . zn двоичных чисел x1 . . . xn и y1 . . . yn (схемаΣ̂1 представляет собой конъюнктор). Доказать, что длина минимальногоединичного теста, проверяющего константные неисправности на выходахФЭ схемы Σ̂n , равна 2n.3) Построить единичный тест, проверяюxq 1 xq 2 xq 3 xq 4щий константные неисправности на выхоA−A−A−A−AX AP AXAдах ФЭ схемы Σ̃n на рис.