Часть 3. Математические модели

О растущей нижней оценке функции Шеннона длины единичного проверяющего теста при константных неисправностях на выходах элементов в формулах над базисами, близкими к стандартному

Ч. Цуй, Д. С. Романов

Московский государственный университет имени М. В. Ломоносова, факультет вычислительной математики и кибернетики

Аннотация: В статье установлены асимптотически равные числу переменных нижние оценки функций Шеннона длины единичного проверяющего теста при константных неисправностях на выходах элементов в булевых формулах над базисами $ \{x\mathbin{\&}y,\,x\vee y,\,\bar x\}$, $\{x\mathbin{\&}y,\,\bar x\}$, $\{x\vee y,\,\bar x\}$, $\{x\mathbin{\&}{\bar y},\,\bar x\}$, $\{x\vee {\bar y},\,\bar x\}$.

Ключевые слова: проверяющий тест, константные неисправности, булева формула