On Free Boolean Vectors

Žarko Mijajlović

Publications de l'Institut Mathématique, _N_S_64 (1998) no. 78, p. 2 .

Résumé

Let $f(x_1,x_2,\ldots,x_n)$ be a Boolean expression in $n$ variables $x_1,x_2,\ldots,x_n$. A method for checking if the identity $f(x_1,x_2,\ldots,x_n)=1$ is valid for all boolean values of $x_1,x_2,\ldots,x_n$ is proposed, based on the parallel structure of a computer k-bit processor. We give a construction of $n$ boolean vectors $(b_1,b_2,\ldots,b_n)$ of the size $2^n$ with the following property: $ \text{\it If}\enskip f(b_1,b_2,łdots,b_n)=1, \enskip \text{\it then}\enskip f(x_1,x_2,łdots,x_n)\enskip \text{\it is identically equal to one}. $ In this case, the necessary number of computing steps for checking the identity $f(b_1,b_2,\ldots,b_n)=1$ is $2^{n-k}$, to be compared with the number of $2^n$ computing steps in the usual table-checking procedure. The complete characterization of vectors $(b_1,b_2,\ldots,b_n)$ is given.

Détail

Classification : 03G05 06E30 94C10