Об асимптотических оценках числа решений систем булевых уравнений с зависимыми переменными

Abstract

Известно, что многие вопросы функционирования дискретных управляющих систем сводятся к решению систем булевых уравнений, либо к определению числа их решений. Таковы, например, некоторые задачи синтеза цифровых автоматов, нахождения внутренне и внешне устойчивых множеств в графе, вопросы теории тестов и др. Естественно предполагать, что множество решений системы будет сужаться с ростом числа уравнений и при достаточно большом количестве последних будет пустым. В работах [1,2] обосновывается это предположение для “типичного” случая, а также приводятся оценки числа решений “почти всех” систем из l неэквивалентных уравнений как с n независимыми, так и с m зависимыми ( и n независимыми ) переменными. В настоящей работе исследуется класс уравнений с “ неявными” m зависимыми переменными.