This article is cited in 2 papers

On the problem of implementation of Boolean functions by generalized $\alpha$-formulas

L. N. Sysoeva

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Moscow, Russia

Abstract: In this paper, we consider the problem of implementation of Boolean functions by generalized $\alpha$-formulas. The notion of a generalized $\alpha$-formula is introduced. For a given set of Boolean functions, we define the notion of a universal set of generalized $\alpha$-formulas. We also propose the notion of dual generalized $\alpha$-formulas and formulate the principle of duality for generalized $\alpha$-formulas. The presence of universal sets of generalized $\alpha$-formulas is proved for every $n\geq2$ for the sets $T_0(n)$ and $T_1(n)$ of $0$-preserving and $1$-preserving Boolean functions of the variables $x_1,x_2,\dots,x_n$.

Keywords: Boolean function, formula, implementation of functions by formulas.

UDC: 519.95

Received: 06.08.2014