• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Глава

Оценки на число булевых функций, реализуемых инициальным константным булевым автоматом с тремя состояниями

С. 74-78.

В данной работе, построен пример инициального булевого автомата с тремя константными состояниями реализующего 2^{2^n} − 2^2^{n−1} − 1 различных булевых функций от n фиксированных переменных. Таким образом, в отличие от случая инициальных автоматов с двумя состояниями, среди инициальных булевых автоматов с тремя константными состояниями существуют автоматы, доля функций f(x1,x2,...,xn), реализуемых которыми, стремится к 1 с ростом n. Также получена верхняя оценка числа булевых функций от n фиксированных переменных, реализуемых инициальным булевым автоматом с тремя константными состояниями.