Microsoft Word - 5.doc


Математические вопросы кибернетики и вычислительной техники 38, 13--14, 2012. 

 
13 

 

 
 
 

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

 
Э. В. Егиазарян 

 
Кафедра дискретной  математики   и теоретической  информатики ЕГУ 

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

Пусть  1)( rrM -такое семейство множеств, что | )(rM  при r  ( M  
обозначает число элементов множества M ), а )(rM E -подмножество тех элементов 
из )(rM , которые обладают заданным свойством E . Говорят, что почти все элементы 
множества )(rM  обладают свойством E , если 1)(/)( rMrM E  при 

n (“типичный” случай).  
Всюду под log  понимается логарифм по основанию 2. 

      Обозначим через lnS , множество всех систем из  l  уравнений вида 
 

  
,...,1

1,,1






l

xxf

i
ni 

 

где    lixxf ni ,...,1,,,1  попарно отличающиеся булевые функции от переменных 
nxxx ,...,, 21  

       Пусть  1,0B ,  niBB inn  1,),,...,,(~/~ 21  . Набор 

n
ni B ),.....,,(

~
21   называется решением системы  (1) , если   ,...,1

1),.....,,( 21






li

nif 
 

      Сопоставим  каждой   системе  S  множества S ln ,     целочисленный параметр   )(S ,   
равный  числу  ее   решений. Справедлива следующая 
       
     Теорема 1 (см [1,2]). 
    1 . Е с л и    nn  , то для почти всех  систем  S  множества S ln ,  имеет место 

lnS 2~)( . 



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

14 

    2. Е с л и    nn  , то почти все  системы  S   множества S ln ,  не имеют 
решений. 
     3. Е с л и  n  ограничено при ln,  ,то для почти всех  систем  S  множества S ln ,  
число решений ограничено сверху произвольной функцией )(n ,         удовлетворяющей 
условию )(n при n . 
      Обозначим через mlnS ,, множество всех систем из l   уравнений вида 

 
,                               
где  xxy njj ,,1   ( mj ,1 ) –неизвестные булевые 

функции ,зависящие от переменных nxxx ,...,, 21 ; ff ji  , при ji  . 
Набор булевых функций     xxxx nmn ,,,,,, 111    называется решением системы  
(4), если при подстановке в  (4) вместо переменных y j  функций  xx nj ,,1    mj ,1  
все уравнения обращаются в тождества. 
     Сопоставим  каждой   системе  S  множества mlnS ,,     целочисленный параметр   )(St ,   
равный числу ее решений. Справедлива следующая 
 
     Теорема 2 (см [2]). 
    1 . Е с л и    mnnlm , , то для почти всех  систем  S  множества mlnS ,,  
имеет место 

nlmSt 2)(2~)(  . 
     2. Е с л и  1]2ln)21([log  lnlm  для достаточно больших m и n , то почти все  
системы  S  множества mlnS ,,  имеют хотя бы одно решение. 

     3. Е с л и  0]2ln)21([log  lnlm  для достаточно больших m и n , то почти все  
системы  S  множества mlnS ,,  не имеют решений. 

     Рассмотрим теперь множество mlnS ,,/  всех систем уравнений вида  

      
 

  
,...,1

1,,1






li

yyf mi 
,  ff ji   при ji  . 

Относительно числа решений )(St  систем из mlnS ,,/ справедлива следующая 
 

     Теорема 3. 
    1 . Е с л и   nmnm ,)log(  ,то для почти всех систем множества mlnS ,,'   

имеет место 
n

lmSt 2)(2~)(  . 
     2. Е с л и    lmlm , , то почти все  системы  S  множества mlnS ,,'  не 
имеют решений. 
 

Список Литературы 
     1.Егиазарян Э.В. Оценки, связанные с числом решений булевых уравнений. Сб. 

вопросы кибернетики, комбинаторный анализ и теория графов, Москва, 1981.      

     2.Егиазарян Э.В. Метрические свойства систем булевых уравнений. ДАН Арм.ССР, т. 

72, N2, 1981. 

 






li

x yynxf mi
,...,1

1,,,,... 11 