RUS  ENG
Полная версия
ЖУРНАЛЫ // Прикладная дискретная математика // Архив

ПДМ, 2022, номер 56, страницы 104–112 (Mi pdm771)

Эта публикация цитируется в 2 статьях

Математические основы надежности вычислительных и управляющих систем

Короткие полные диагностические тесты для схем с одним дополнительным входом в стандартном базисе

К. А. Попков

Институт прикладной математики им. М. В. Келдыша РАН, г. Москва, Россия

Аннотация: Доказано, что любую монотонную (антимонотонную) булеву функцию от $n$ переменных можно смоделировать схемой из функциональных элементов с одним дополнительным входом в базисе «конъюнкция, дизъюнкция, отрицание», допускающей полный диагностический тест длины не более $n+2$ (соответственно не более $n+1$) относительно константных неисправностей типа $1$ на выходах элементов.

Ключевые слова: схема из функциональных элементов, константная неисправность, полный диагностический тест, булева функция.

УДК: 519.718.7

DOI: 10.17223/20710410/56/6



© МИАН, 2024