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

в задаче 5.3).5.6. Доказать, что число тупиковых тестов матрицы M с m строкамине превосходит2 bmmc .25.7. Доказать, что число матриц из B m,n с попарно различными строками, у которых фиксированное множество номеров строк мощности kявляется тестом, равно 2k (2k − 1) . .

. (2k − n + 1)2n(m−k) .5.8. Пользуясь универсальным алгоритмом, построить все тупиковыетесты для матриц 1), 2), 5), 6) задачи 5.1.5.9. Доказать, что длина тупикового теста для приведенной матрицыс n столбцами лежит в пределах от dlog2 ne до (n−1) и что обе указанныеграницы достигаются.5.10. Могут ли строки некоторого тупикового теста для матрицы Mбыть линейно зависимы?5.11.∗ Пусть матрица M из B m,n имеет в каждой своей строке не болееp, p > 0, единиц.

Доказать, что длина минимального теста для матрицыne.M не менее d 2p5.12.∗ Пусть первый столбец приведенной матрицы M , M ∈ B m,n+1 ,состоит из одних нулей (в соответствии с задачей 5.5.5 любая матрицаT -эквивалентна матрице с таким же числом столбцов, у которой первыйстолбец состоит только из нулей), а ее остальные столбцы можно разбитьна s групп так, что подматрица матрицы M , порождаемая любой из этихгрупп, имеет в каждой своей строке не более одной единицы. Показать,что длина теста матрицы M не меньше, чем 2n/(s + 1).§ 6. Тесты для контактных схем и схем из функциональныхэлементовЧерез dae (соответственно bac) обозначается ближайшее к a сверху (соответственно, снизу) целое число.2Рассмотрим общую модель ненадежных схем применительно к контактным схемам (КС) и схемам из функциональных элементов (СФЭ).Будем считать, что любое неисправное состояние КС связано с размыканием (обрывом) одной части и замыканием другой части контактовКС.

При этом предполагается, что функция проводимости замкнутого(разомкнутого) контакта тождественно равна единице (соответственнонулю). В частности, через Иr,s , где r и s — целые неотрицательные числа, будем обозначать источник неисправностей, допускающий не более,чем r, обрывов и не более, чем s, замыканий контактов КС одновременно. Тест для источника неисправностей И0,1 (И1,0 ) называют единичнымтестом замыкания (соответственно, размыкания).При изучении ненадежности СФЭ, в свою очередь, будем считать,что каждое их неисправное состояние связано с возможным изменениемфункционирования функциональных элементов (ФЭ) или входов схемыпри сохранениии местности реализуемых ими булевых функций.

Предполагается также, что все соединения между входами, ФЭ и выходамиСФЭ не нарушаются и передают информацию без искажений. Пусть, вчастности, СФЭ Σ0 является неисправным состоянием СФЭ Σ, xi — входсхемы Σ, а E — ее ФЭ, реализующий булеву функцию ϕ(u1 , . . . , uk ). Будем говорить, что в состоянии Σ0 на входе xi имеет место константнаянеисправность типа σ, σ ∈ {0, 1}, если в соответствующей xi входнойвершине Σ0 реализуется булева функция σ. Будем говорить также, чтов состоянии Σ0 на j-м входе, 1 ≤ j ≤ k, (выходе) ФЭ E схемы Σ имеет место константная неисправность типа σ, σ ∈ {0, 1}, если ФЭ Eреализует в Σ0 булеву функцию ϕ(u1 , .

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