PUBLICATIONS DE L'INSTITUT MATHÉMATIQUE (BEOGRAD) (N.S.) Vol. 64(78), pp. 28 (1998) 

ON FREE BOOLEAN VECTORSZarko Mijajlovi\'cMatemati\v ki fakultet, Beograd, YugoslaviaAbstract: 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 kbit 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^{nk}$, to be compared with the number of $2^n$ computing steps in the usual tablechecking 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:
Electronic fulltext finalized on: 6 Apr 2000. This page was last modified: 16 Nov 2001.
© 2000 Mathematical Institute of the Serbian Academy of Science and Arts
