ON FREE BOOLEAN VECTORS

Zarko Mijajlovi\'c

Abstract: 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,\ldots,b_n)=1, \enskip \text{\it then}\enskip f(x_1,x_2,\ldots,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.

Classification (MSC2000): 03G05, 06E30, 94C10

Full text of the article:

• Compressed DVI file (17 kilobytes)
• PostScript file (159 kilobytes)
• Compressed PostScript file (65 kilobytes)
• PDF file (166 kilobytes)