Синтез легкотестируемых схем в базисе $\{\&,\vee,\bar{\vphantom{x}}\,\}$ для систем булевых функций

Предложены методы синтеза легкотестируемых схем из функциональных элементов в базисе $\{\&,\vee,\bar{\vphantom{x}}\,\}$ для систем из $m$ булевых функций, отличных от констант. В качестве неисправностей предполагаются константные неисправности типа $1$ на выходах элементов. Доказано, что для таких схем полный проверяющий тест имеет длину не более $1+q$, где $q\le m$ есть число функций из системы, сохраняющих единицу. Значение $1+q$ в этой оценке длины теста в общем случае нельзя заменить ни на какое число, меньшее $q$. Для систем функций, каждая из которой монотонна по каждой из $l$ переменных $x_2,x_3,\dots,x_{l+1}$, $0\le l\le n-1$, и антимонотонна по каждой из $n-l-1$ переменных $x_{l+2},\dots,x_n$, строятся схемы с полным проверяющим тестом длины $1$.
Работа выполнена при финансовой поддержке РФФИ, проект 08–01–00863, и Программы фундаментальных исследований Отделения математических наук РАН “Алгебраические и комбинаторные методы математической кибернетики и информационные системы нового поколения”, проект “Задачи оптимального синтеза управляющих систем”.