Asymptotics of the number of repetition-free Boolean functions in the elementary basis
| Autor: | O. V. Zubkov |
|---|---|
| Rok vydání: | 2007 |
| Předmět: | |
| Zdroj: | Mathematical Notes. 82:741-747 |
| ISSN: | 1573-8876 0001-4346 |
| DOI: | 10.1134/s0001434607110181 |
| Popis: | In this paper, we obtain an asymptotic approximation of the number K n of repetition-free Boolean functions of n variables in the elementary basis {&, ∨, −} as n → ∞ with relative error O(1/√n). As a consequence, we verify conjectures on the existence of constants δ and α such that $$K_n \sim \delta \cdot \alpha ^{n - 1} \cdot (2n - 3)!!$$ , and obtain these constants. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|