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

При этом подматрицу вида M < I, b1, me >(M < b1, ne, J >) будем обозначать через M < I > (соответственноM (J)). Матрица M называется приведенной, если все ее столбцы различны.Пусть M = (Σ, И) — указанная выше модель ненадежной схемы Σ ссостояниями Σ = Σ(1) , Σ(2) , . . . , Σ(t) и функциями F = F (1) , F (2) , .

. . , F (t)от переменных x = (x1 , . . . , xn ). Пусть, далее, функции F (1) , F (2) , . . . , F (t)определены на множестве наборов N = {β1 , . . . , βp } и принимают значения из множества (наборов) A = {α1 , . . . , αa }.Сопоставим рассматриваемой задаче контроля матрицу M , M ∈ Ap,t ,где M < s, j >= F (j) (αs ) для всех s, s ∈ b1, pe, и j, j ∈ b1, te. Заметим, что если M (i) = M (j), то состояния с номерами i и j невозможноотличить друг от друга на основе данных наборов.

В таких случаях всесостояния, как правило, разбиваются на классы эквивалентности по отношению неотличимости, а задача контроля ставится и решается дляэтих классов. Заметим также, что каждому классу неотличимости состояний соответствует группа одинаковых столбцов матрицы M , а задаче контроля для этих классов — приведенная матрица M 0 , множествостолбцов которой совпадает с множеством различных столбцов матрицыM.Пусть, далее, задана цель контроля, то есть указано множества N ,состоящее из тех неупорядоченных пар различных чисел отрезка b1, te,для которых пары состояний (столбцов матрицы M ) с соответствующими номерами необходимо отличать друг от друга, сравнивая значения,расположенные в тех или иных строках данной пары столбцов.

В частности, если N состоит из всех пар указанного вида, то целью контроляявляется диагностика схемы, а если N = {(1, 2), . . . , (1, t)}, то — проверка исправности схемы. Множество T , T ⊆ b1, pe, называется тестомдля матрицы M относительно множества N , или, иначе, тестом для(M, N ), если для любой пары (i, j) из N существует s, s ∈ T , такое, чтоM < s, i >6= M < s, j >. Мощность теста называется также его длиной.Заметим, что множество b1, pe всегда образует тест. Тест, который перестает быть тестом при удалении любого своего элемента, называетсятупиковым, а тест, который имеет минимальную мощность, — минимальным.

В том случае, когда целью контроля является диагностикасхемы (проверка исправности схемы), тест называется диагностическим(соответственно проверяющим).Для приведенной матрицы M , M ∈ Ap,t , и цели контроля N определимбулеву функцию теста f (y1 , . . . , yp ) следующим образом: f (β1 , . .

. , βp ) =1 тогда и только тогда, когда множество T , состоящее из тех чисел s, s ∈b1, pe, для которых βs = 1, образует тест для матрицы M относительноN.Теорема. Функция теста f (y1 , . . . , yp ) для матрицы M , M ∈ Ap,t , ицели контроля N может быть задана КНФ^_f (y1 , . . . , yp ) =(ys ),(4.1)(i,j)∈N1≤s≤pM < s, i >6=M < s, j >причем каждое слагаемое вида ys1 · . . . · ysr сокращенной ДНФ функцииf (y1 , . . .

, yp ) соответствует тупиковому тесту T = {s1 , . . . , sr } и обратно.На данной теореме основан следующий универсальный алгоритм построения всех тупиковых тестов для матрицы M относительно цели контроля N :1) выписываем для функции теста КНФ вида (4.1);2) раскрывая в ней скобки, приводя “подобные” слагаемые (см. § 3)и применяя правило поглощения x1 ∨ x1 x2 = x1 , получаем сокращеннуюДНФ функции теста;3) сопоставляем каждой элементарной конъюнкции сокращеннойДНФ тупиковый тест.Пример.0 1 00 1 1Пусть M =  1 0 1 .1 1 0Для построения всех тупиковых диагностических тестов матрицы Mпостроим КНФ вида (4.1):(y1 ∨ y2 ∨ y3 ) · (y2 ∨ y4 ) · (y1 ∨ y3 ∨ y4 ).Раскрывая в этой КНФ скобки, приводя подобные слагаемые и применяяправило поглощения, получим сокращенную ДНФ для функции теста:y1 y 2 ∨ y 1 y4 ∨ y2 y3 ∨ y 2 y4 ∨ y3 y4 .Тупиковыми диагностическими тестами матрицы M являются множества{1, 2}, {1, 4}, {2, 3}, {2, 4}, {3, 4}.В дальнейшем по умолчанию будем считать, что матрица — это матрица из нулей и единиц, а тест — диагностический тест.

Множество номеров строк матрицы M , которое соответствует подматрице без нулевыхстолбцов, называется ее покрытием. Покрытие считается тупиковым(кратчайшим), если удаление из него любого номера строки приводит кмножеству номеров строк, не являющемуся покрытием (содержит минимальное число номеров строк). Мощность минимального покрытия называется глубиной матрицы.5.1. Найти глубину матрицы0 1 1 00 0 1 11) M = 1 0 0 11 1 0 01 1 1 0 0 01 0 0 1 0 02) M = 0 1 0 0 1 00 0 1 0 0 11 1 1 1 0 0 00 0 1 1 1 1 03) M = 1 1 0 0 0 1 11 1 1 1 1 1 10 0 0 0 0 0 01 1 0 0 0 00 1 1 0 0 00 0 1 1 0 04) M = 0 0 0 1 1 00 0 0 0 1 11 0 0 0 0 11 1 1 0 00 1 1 1 05) M = 001111 0 0 1 11 1 0 0 1M:001010110101001110011110110101100016) M = 110000010110010011000001110110010015.2.

Найти длину минимального теста для матрицы M , множествостолбцов которой есть11) B n ;2) BknS, k > 0;n3)B2k;0≤k≤n/2S n4) Bkn Bk+1, k ≥ 0.5.3. Через M (2) будем обозначать матрицу, составленную из суммпо модулю 2 всевозможных пар столбцов матрицы M , выписанных впорядке возрастания номеров этих пар в соответствиис их лексико1 1 0графической упорядоченностью. Например, если M =  0 1 1  , то0 0 10 1 1(2)M = 1 1 0 .0 1 1Доказать, что множество номеров строк матрицы M является тестом(минимальным, тупиковым тестом) тогда и только тогда, когда оно является покрытием (кратчайшим, тупиковым покрытием) матрицы M (2) .5.4.

Обобщить результат задачи 5.3 на случай произвольной цели контроля N .5.5. Две матрицы M и L с одинаковым числом строк называются T эквивалентными, если множество номеров строк матрицы M являетсятестом тогда и только тогда, когда оно является тестом матрицы L.Выяснить, являются ли T -эквивалентными матрицы M и L, если1) M получена из L перестановкой столбцов;2) M получена из L перестановкой строк;3) M получена из L удалением всех столбцов, сплошь состоящих из 0(1);Через Bkn , где 0 ≤ k ≤ n, обозначается множество всех наборов куба B n , содержащих ровно k единиц.14) M получена из L вычеркиванием k − 1 столбцов из k одинаковых;5) M получена сложением по модулю 2 каждого столбца матрицы L сзаданным столбцом α̃;6) M получена из L сложением по модулю 2 каждой строки матрицыL с заданной строкой α̃;7) M получена из L заменой всех 0 на 1 и всех 1 на 0;8) M состоит из всех линейных комбинаций столбцов матрицы L;9) M = L(2) (определение см.

в задаче 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 , .