Все тупиковые тесты для заданной таблицы контроля и цели \(N\) можно получить через специальную функцию теста. Каждой строке таблицы сопоставляют переменную \(y_t\). Для каждой пары столбцов, которую требуется различить, записывают дизъюнкцию тех \(y_t\), чьи строки различают эту пару. Конъюнкция всех таких дизъюнкций равна 1 ровно на наборах строк, образующих
После раскрытия этой КНФ и удаления поглощений получают сокращённую ДНФ функции теста. Каждый её конъюнкт взаимно однозначно соответствует одному тупиковому
Что важно запомнить
- Для каждой требуемой пары столбцов найти строки, в которых значения различаются.
- Записать по этой паре дизъюнкцию соответствующих переменных \(y_t\).
- Перемножить все дизъюнкции и получить функцию теста в КНФ.
- Раскрыть скобки, привести подобные и выполнить поглощения.
- Каждый конъюнкт сокращённой ДНФ перевести в множество выбранных строк — тупиковый
Функция теста
Пусть цель контроля \(N\) содержит пары столбцов \((i,j)\). Переменная \(y_t\) означает, что в тест включена строка \(t\). Тогда функция теста имеет вид
\(F(y_1,\ldots,y_p)=\bigwedge_{(i,j)\in N}\left(\bigvee_{t:\,M_{ti}\ne M_{tj}}y_t\right).\)
Каждая скобка требует выбрать хотя бы одну строку, различающую конкретную пару состояний. Поэтому набор значений \(y\), на котором \(F=1\), задаёт некоторое решение задачи контроля.
Почему простые импликанты дают тупиковые тесты
Функция теста монотонна: если набор строк уже различает все нужные пары, добавление новых строк не разрушает это свойство. Минимальные по включению единичные наборы такой функции соответствуют тупиковым тестам. Алгебраически они задаются простыми импликантами, то есть конъюнктами сокращённой ДНФ
Алгоритм
Сначала функция теста строится непосредственно по таблице и цели контроля. Затем КНФ раскрывают в ДНФ, удаляют повторяющиеся множители и поглощаемые конъюнкции. Если в результате имеется конъюнкт \(y_{t_1}\cdots y_{t_r}\), то множество строк \(\{t_1,\ldots,t_r\}\) является тупиковым тестом. Перебрав все конъюнкты сокращённой ДНФ, получают все тупиковые тесты и только
Если в исходной таблице есть одинаковые строки, их можно сначала объединить в классы эквивалентности по значениям. После решения сокращённой задачи тесты разворачиваются обратно с учётом выбора конкретных представителей классов.
Пример простыми словами
В примере курса сокращённая ДНФ функции теста имеет вид \(y_1y_2\vee y_1y_4\vee y_2y_3\vee y_2y_4\vee y_3y_4\). Значит, существуют пять тупиковых тестов: \(\{1,2\}\), \(\{1,4\}\), \(\{2,3\}\), \(\{2,4\}\) и
Частые ошибки
- Оставлять в раскрытой ДНФ поглощаемые конъюнкты. Они соответствуют тестам, из которых можно удалить строки, поэтому не являются тупиковыми.
- Выбирать только самый короткий конъюнкт. Алгоритм должен перечислить все тупиковые тесты, а не только минимальные по длине.
- Путать переменные \(y_t\) с входными переменными исходной схемы. Они кодируют выбор строк таблицы контроля.
