Введем несколько определений.
Допустим, существует два примитива
-ый и j –ый примитивы типа
Не трудно показать, что две КАМСИ-композиции, каждая из которых состоит из одинаковых примитивов
В общем виде, m-позиционные кортежи у которых одинаковый набор типов КАМСИ-композиции можно записать в виде:
Форм. 16
где:
q - один из множества
Общее число m-позиционных кортежей, которые имеют одни и те же примитивы и отличаются только порядком их расположения равно ([45]):
Форм. 17
где:
Приступим к определению мощности множества примитивов.
Введем определение.
Два состояния А и В таблицы переходов, которые имеют вид
где C и D – любые состояния таблицы переходов,
будем называть взаимообратимыми. Взаимообратимые состояния имеют одинаковое заполнение в тестирующей таблице.
Предварительно сформулируем несколько утверждений.
Утверждение 4: Таблица переходов КАМСИ не содержит взаимообратимых состояний.
Это утверждение вытекает из Theorem 14-1 цитированной выше книги Zvi Kohavi (стр. 510).
Утверждение 5: «Перестановка переходов в любой строке таблицы переходов КАМСИ сохраняет свойство КАМСИ и его тип (величину µ-задержки)».
Доказательство.
Первая часть Утверждения вытекает из способа построения тестирующей таблицы (см. «Switching and Finite Automata Theory», Zvi Kohavi), в которой каждой строке верхней половины тестирующей таблицы ставится упорядоченное сочетание названий состояний переходов в соответствующей строке таблицы переходов. Из этого следует, что перестановка переходов сохраняет свойство КАМСИ.