This article is cited in 1 paper

Construction of noniterated Boolean functions in the basis $\{\&,\vee,-\}$ and estimation of their number

O. V. Zubkov

Irkutsk State Pedagogical University

Abstract: In this paper we consider noniterated Boolean functions in the basis $\{\&,\vee,-\}$. We obtain the canonical form of the formula for a noniterated function in this basis. We construct the set of such formulas in terms of the variables $x_1,\dots,x_n$ and calculate the number of its elements. Based on these results, we obtain the upper and lower bounds for the number of noniterated Boolean functions of $n$ variables in the basis under consideration.

Keywords: noniterated Boolean function, number of noniterated functions, estimates for the number of noniterated functions.

UDC: 519.714

Received: 03.06.2003
Revised: 02.12.2007

 English version: Russian Mathematics (Izvestiya VUZ. Matematika), 2008, 52:10, 13–19

Bibliographic databases:

• 
•