100 000100110 000100010
. За булевої матриці записується функція у формі В«диз'юнкція кон'юнкційВ»:
В В
Таким чином, безліч елементарних тестів складається з чотирьох елементів
Т1 = {,,,,,}
Т2 = {,,,,,,}
Т3 = {,,,,,,}
Т4 = {,,,,,,}
Мінімальним є тест Т1 = {,,,,,}
4.2 Побудова досить простих діагностичних тестів за допомогою алгоритму Яблонського-Мак-Класкі
Пропонований алгоритм у загальному випадку призводить до побудови деякого досить простого діагностичного тесту, проте іноді може призводити і до мінімального варіанту. Нехай безліч Е = {еk}, k = є безліч всіх двійкових наборів еk = (), ГЋ {0, 1} довжини m (j =). Для всіх еkГЋЕ , норма еk визна ляется числом одиниць в даному наборі, тобто | | еk | | =. Набори еk і еrГЋЕ називаються порівнянними (обо призначається еk ВЈ еr) якщо для всіх j, j = (наприклад заходів, 10100 ВЈ 10110). p> Вихідна інформація задається у вигляді якоїсь булевої матриці М, яку необхідно спрощувати за такими правилами:
. Правило поглинання рядків. Якщо в матриці М є така пара рядків ai і ar (i, r =), що ai ВЈ ar, то рядок ar викреслюється. p>. Правило поглинання стовпців. Якщо в матриці М є така пара стовпців bj і bt (j, t =), що bt ВЈ bj, то стовпець bt викреслюється. p>. Критерій входження стовпця в усі Непріводімие матриці. Якщо в матриці М є рядок ai, яка містить тільки одну одиницю (тобто | | ai | | = 1), що стоїть на перетині i-го рядка і j-го стовпця, то стовпець bj наголошується, що вхідний у мінімальний діагностичний тест, і викреслюється з М.
4. Якщо в матриці є стовпець, який не містить одиниць (тобто | | bj | | = 0), то цей стовпець викреслюється з М .
Правила перетворення застосовуються до вихідної матриці М доти, поки ці правила призводять до спрощення М . Таке спрощення може призвести до двох результатів.
. Після застосування правил перетворення в матриці М не залишилося жодного стовпчика. У цьому випадку відмічені стовпці утворюють непріводімим матрицю М *, що має мінімальне число стовпців. Отже, підмножина перевірок з П, мають ті ж номери, що і стовпці в М *, утворює мінімальний діагностичний тест.
. З матриці М отримана матриця М0, що не спрощується при подальшому застосуванні правил перетворення. Така матриця називається циклічною. У цьому випадку будь-який тест Т , отриманий за допомогою матриці М, можна представити у вигляді
T = T 1 Г€ < span align = "justify"> T 2
де T 1 - підмножина перевірок з П, номери яких співпадають з номерами...
