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

Каждый контакт исходной контактной схемы заменяем на двухполюсную подсхему в соответствии с тождеством TIV .2. Рассматриваем произвольную вершину исходной контактной схемы,не являющуюся полюсом.1) Применяя тождество TV III для каждой звезды с центром в этойвершине добиваемся того, чтобы из рассматриваемой вершины исходилитолько различные цепочки контактов.2) По тождеству TIII рассматриваемую вершину вместе со всеми цепочками контактов, исходящими из нее, удаляем.Повторяя пп.

1) и 2) для каждой вершины, не являющейся полюсом, получим контактную схему, в которой цепочки контактов соединяюттолько полюса.3. В случае, если контактная схема имеет более двух полюсов, выполняем транзитивное замыкание по тождеству TIX .4. Повторяющиеся цепочки контактов, соединяющие одну и ту же паруполюсов, вычеркиваем по тождеству TV I .4.3. Привести к каноническому виду следующие контактные схемы:x•y1)z•z̄•x̄•1y•zx2•xzy2)1ȳ•x̄•x2z2yy3)1xȳ•34.4. 1) Выяснить, эквивалентны ли данные контактные схемы, приводя каждую из них к каноническому виду:yx1)•12zxy•1x2)2z1 zy•yx•y21 xz•z•y24.5. 1) Пусть Σ — контактная схема, зависящая от переменныхx1 , . .

. , xn , и α = (a1 , . . . , an ) — вектор из 0 и 1. Пусть R(Σ, α) — число простых циклов (без повторения вершин) в контактной схеме Σ,состоящихиз некоторых контактов вида xa11 , . . . , xann , и пусть R(Σ) =Pα∈B n R(Σ, α).Доказать, что если контактная схема Σ0 от переменных x1 , . .

. , xn получена из контактной схемы Σ от переменных x1 , . . . , xn в результатеприменения любого из тождеств t1 − t5 , то R(Σ) = R(Σ0 ), а если в ре(m)зультате применения тождества t6 , m ≤ n, то R(Σ) − R(Σ0 ) делится на2n−m .2) Основываясь на утверждении п. 1) доказать, что контактную схемуx1 x••yz2нельзя преобразовать в контактную схемуyx1•z2(1)(2)при помощи тождеств t1 − t5 , t6 , t6 .(m+1)3) Основываясь на утверждении п.

1) доказать, что тождество t6(1)(m)не выводится из тождеств t1 − t5 , t6 , . . . , t6 .(m)4) Доказать, что из множества тождеств t1 −t5 , t6 (m = 1, 2, . . .) нельзя выделить конечной полной системы тождеств для контактных схем.5) Доказать, что в классе всех контактных схем не существует конечной полной системы тождеств.Часть 3.

Надежность и контроль управляющих системДля управляющей системы (схемы) без памяти, функционированиекоторой описывается дискретной функцией или, в общем случае, векторфункцией, может быть сформулирована следующая модель (см. [6, 12]), врамках которой обычно рассматриваются вопросы ее надежности. Предполагается, что имеется некоторый “внешний” источник неисправностей(источник помех) И, под действием которого рассматриваемая схемаΣ может переходить в одно из своих “неисправных состояний” (схем),определяемых этим источником.

Пусть схеме Σ = Σ(1) , реализующей(1)(1)(вектор-) функцию F = F (1) = (f1 , . . . , fm ) от входных переменныхx = (x1 , . . . , xn ), и источнику неисправностей И соответствуют “неисправные” состояния (схемы) Σ(2) , . . . , Σ(t) , где схема Σ(i) , i = 2, . . . , t,(i)(i)реализует функцию F (i) = (f1 , . . . , fm ) от переменных x. При этом всесостояния (как исправное Σ = Σ(1) , так и неисправные Σ(2) , . . . , Σ(t) ) разбиваются на классы (функционально) неотличимых состояний, то естьклассы эквивалентности по отношению равенства реализуемых функций, и рассматриваются далее с точностью до неотличимости.

В дальнейшем, говоря о ненадежной схеме Σ, будем иметь в виду указаннуювыше модель M = (Σ, И) и (или) соответствующее ей множество схемвместе с теми функциями, которые они реализуют.§ 5. Задача контроля управляющих систем. Тесты для таблицРассмотрим математическую модель задачи контроля управляющихсистем, связанную с понятием теста для таблицы.Для целых чисел a и b, где a ≤ b, через ba, be будем обозначать множество целых чисел отрезка [a, b], то есть множество целых i таких, чтоa ≤ i ≤ b.

Для множества A и натуральных n, m через An,m будем обозначать множество матриц с n строками, m столбцами и элементами из A.При этом будем считать, что Am , то есть m-я декартова степень множества A, совпадает с A1,m . Для матрицы M из множества An,m ее подматрицу, расположенную в строках с номерами из множества I и в столбцахс номерами из множества J, где I ⊆ b1, ne и J ⊆ b1, me, будем обозначать через M < I, J >.

При этом подматрицу вида 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) (определение см.