В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (скан) (1132786), страница 5
Текст из файла (страница 5)
Пусть, далее, задана цель контроля, то есть указано множества Лг, состоящее из тех неупорядоченных пар различных чисел отрезка 11, (), для которых пары состояний (столбцов матрицы М) с соответствующими номерами необходимо отличать друг от друга, сранниввя значения, расположенные в тех или иных строках данной пары столбцов. В частности, если Х состоит из всех пар указанного вида, то целью контроля является диагностика схемьи а если Лг = ((1, 2),..., (1, З)), то — проверка испраеиосгаи схемы, Множество Т, Т С (1, р), называется гпестом длл матрицы Л1 относирлглъио мноаюества Л', или, иначе, тестом длл (М, Лг), ЕСЛИ дпя ЛЮбОй ПарЫ (г,й) ИЗ Лг СущЕСтВуЕт Э, г Е Т, таКОЕ, Чта М < г.
г >ф М < г,,1 >. Мощность теста называется также его длиной, Заметим, что множество (1, р) всегда образует тест, Тест, который перестает быть тестом при удалении любого своего элемента, называется тупиковым, а тест, который имеет минимальную мощность, — минималыгым. В том случае, когда целью контроля является диагностика схемы (проверка исправности схемы), тест называется диагностическим (соответственно проверяющим) . Для приведенной матрицы М, М е Ар', и цели контроля Ж определим булеву функцию теста ) (уь..., ур) следующим образом: 1(«зь, «зр) = зз 1 тогда и только тогда, когда множество Т, состоящее из тех чисел з, з ~ 11, Р), длн котоРых д, = 1, обРазУет тест длЯ матРицы М относительно ьЧ. Теорема.
Функция теста,)(уь,...,Рр) длл мояьрццм М, М е Агг, и цели яоноьраьл Х мозьсеьп бмньь задана КНФ (4,1) (Ь41ен ~З~ЗР м< °,~)г н 4 юо > причем юьэьсдое аиыоемое вида у„.... У,, сокращенной дНФ фунхцио у(уь ~ ° ~ Уг) соопьееоьсьлеую74 оьуйпкоеаму ньесшу T = (Зь,..., з,) и об реьььно, На данной теореме основан следующий универсальный алгоритм построения всех тупиковых тестов для матрицы йд относительно цели контроля Х: 1) выписываем для функции теста КНФ вида (4.1); 2) раскрывая в ней скобки, приводя "подобные" слагаемые (см. 3 3) и применяя правило поглощения ль Ч яляз = зм получаем сокрещснную ДНФ функции теста; 3) сопоставляем каждой элементарной конъюнкции сокращенной ДНФ тупиковый тест.
Пример, 010 011 Пусть М 110 Для построения всех тупиковых диагностических тестов матрицы М построим КНФ вида (4.1): (Уь Ч Рз Ч Рз) ' (Уз Ч У4) (Уь Ч Уз Ч Уг)' Раскрывая в этой КНФ скобки, приводя подобные слагнельые и применяя правило поглощения, получим сокращенную ДНФ для функции теста: Уьуз Ч Уьрг Ч Узуз Ч Узуг Ч улуг. Тупиковыми диагностическими тестами матрицы М являются множества (1,2), (1,4), (2,3), (2,4), (3,4).
В дальнейшем по умолчанию будем считать, что матрица — это матрице из нулей и единиц, в тест — диагностический тест. Множество номеров строк матрицы М, которое соответствует подматрице без нулевых столбцов, называется ее покрытием. Покрытие считается ьлуликоемм (крапьчайшим), если удаление из него любого номера строки приводит к множеству номеров строк, не являющемуся покрытием (содержит минимзльное чисььо номеров строк). Мощность минимального покрытия называется глубиной матрицы, 3.1. Найти глубину матрицы М: 0110 0011 1001 1100 1)М= 111000 100100 010010 001001 2) М= 1 1 1 1 0 0 О О 0 О 1 1 1 1 0 0 1 1 1 1 0 О 1 1 1 1 0 0 1 1 0 0 0 1 1 1 1 О О 1 1 0 1 1 1 1 1 1 1 0 0 0 0 О О 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 11000 01100 00110 00011 00001 10000 4) М= 11100 01110 00111 10011 11001 5) М= 1010010 1001001 0101010 0010110 0100101 5.2.
Найти длину минимального теста для матрицы М, множество столбцов которой естьг 1) В"; 2)В~,Л>0; 3) () ВУ;, обе<нуг 4) В» Ц В„"„, /с > О. 5.3. Через ЛФг) будем обозначать матрицу, составленную из сумм по модушю 2 всевозможных пар столбцов матрицы М, выписанных в порядке возрастания номеров этих пар в соответствии с их лексико- 110 графической упорядоченностью. Например, если М = 0 1 1, то 001 ЛХ~г) = 1 1 0 Доказать, что множество номеров строк матрицы Л4 является тестом (минимальным, тупиковым тестом) тогда и только тогда, когда оно является покрытием (кратчайшим, тупиковым покрытием) матрицы М~г). 5.4.
Обобщить результат задачи 5.3 на случай произвольной цели контроля )в'. 5.5. Дне матрицы М и Ь с одинаковым числом строк называются Т- эхеиваленглнмлеи, если множество номеров строк матрицы М является тестом тогда и только тогда, когда оно является тестом матрицы Ь. Выяснить, являются ли Т-эквивалентными матрицы М и Ь, если 1) Л1 получена из Ь перестановкой столбцов; 2) М получена из Е перестановкой строк; 3) М получена из Ь удалением всех столбцов, сплошь состоящих из 0 (1); 'Через В„", где 0 < Л к н, обозначмтсн множество всех наборов куба В", содерж~' ших ровно й единиц.
4) М получена из Ь вычеркиванием lс — 1 столбцов из Л одинаковых; 5) М получена сложением по модулю 2 каждого столбца матрицы Ь с заданным столбцом а; 6) М получена из Ь сложением по модулю 2 каждой строки матрицы Ь с заданной сгрокой б; 7) М получена из Ь заменой всех 0 на 1 и всех 1 на 0; 8) М состоит из всех линейных комбинаций столбцов матрицы Ь; 9) М = 1Р (определение см.
в задаче 5.3). 5.6, Доказать, что число тупиковых тестов матрицы М с т строками не превосходите (я)). 5.7. Доказать, что число матриц из В"'" с попарно различными стро- ками, у которых фиксированное множество номеров строк мощности й является тестом, равно 2~(2е — 1)... (2" — и + 1)2в~"' а). 5.6. Пользуясь универсальным алгоритмом, построить все тупиковые тесты для матриц 1), 2), 5), 6) задачи 5.1. 5.9. Доказать, что длина тупикового теста для приведенной матрицы с п столбцами лежит в пределах от (1ояг и) до (п-1) и что обе укаэанные границы достигаются, 5.10. Могут лп строки некоторого тупикового теста для матрицы М быть линейно зависимы? 5.11.' Пусть матрица М из В "имеет в каждой своей строке не более р, р > О, единиц.
Доказать, что длина минимального теста для матрицы М не менее ($). 5.12. Пусть первый столбец приведенной матрицы М, М Е В "+', состоит из одних нулей (в соответствии с задачей 5.5.5 любая матрица Т-эквивалентна матрице с таким же числом столбцов, у которой первый столбец состоит только иэ нулей), а ее остальные столбцы можно разбить на в групп так, что подматрица матрицы Лу, порождаемая любой из этих групп, имеет в каждой своей строке не более одной единицы. Показать, что длина теста матрицы М не меньше, чем 2пу(в+ 1). 3 6.
Тесты для контактных схем и схем из функциональных элементов 'Через (а) (еоотвегетвенно (а) ) обозначаегои ближайшее к а сверху (соответственно, снизу) целое число, Рассмотрим общучо модель ненадежных схем применительно к контмгтным схемам (КС) и схемам из функциональных элементов (СФЭ). Будем считать, что любое неисправное состояние КС связано с разммканиаи (обрывам) одной части н замыканием другой части контактов КС.
Прп этом предполагается, что функция проводимости замкнутого (разомкнутого) контакта тождественно равна единице (соответственно нллтю) В частности, через И,„где г и в — целые неотрицательные числа, будем обозначать источник неисправностей, допускающий не более, чем г, обрывов и нс более, чем в, замыканий контактов КС одновременно. Тест лля источника неисправностей Иоз (Ике) называют единичным тестам замыкания (соответственно, раэммхаиия). При изучении ненадежности СФЭ, в свою очередь, будем считать, что каждое нх неисправное состояние связано с возможным изменением функционирования функциональных элементов (ФЭ) или входов схемы при сохраненнии местности реализуемых нми булевых функций.
Предполагаегся также, что все соединения между входами, ФЭ и выходами СФЭ не нарушаются и передают информацию без искажений. Пусть, в частности, СФЭ Е' является неисправным состоянием СФЭ Е, х, — вход схемы Е, а Š— ее ФЭ, реализующий булеву функцию у(иь..., иь). Будем говорить, что н состоянии Е' на входе х, имеет место константная неисправность типа а, а 6 (О. Ц, если в соответствующей х, входной вершине Е' реализуется булева функция а. Будем говорить также, что в состоянии Е' на у-м входе, 1 < у < Ь, (вьлходе) ФЭ Е схемы Е имеет меппо константная нвисправиостпь типа а, в 6 (О, 1), если ФЭ Е реализует в Е' булеву функцию р(иь..., и.
ив, и ем..., иь) (соответственно а), Можно рассматривать константные неисправности различных типов, а также константные неисправности как на входах, таи и на выходах ФЭ. При описании источника неисправностей в КС или СФЭ Е часто выделяется множество Е тех элементов или "узлов" Е, которые могут выходить из строя, и указываются возможные неисправные состояния каждого из них. При этом источник, допускающий любую комбинацию любых неисправных состояний для любого подмножества (подмножества мощности 1) элементов множества Е, называется полним (соответственно, единичным) источником для множества Й и заданных неисправных состояний его элементов, а связанный с ним тест — полным (соответственно, единичным) тестом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
