On free Boolean vectors (Q2774633)

A method for checking if the identity \(f(x_1,\ldots,x_n)=1\) is valid for all Boolean values of \(x_1,\ldots,x_n\) is proposed, where \(f(x_1,\ldots,x_n)\) is a Boolean expression in \(n\) variables \(x_1,\ldots,x_n\). Namely, the author gives a construction of \(n\) Boolean vectors \((b_1,\ldots,b_n)\) of size \(2^n\) with the property: if \(f(x_1,\ldots,x_n)=1\), then \(f(x_1,\ldots,x_n)\) is identically equal to one.NEWLINENEWLINENEWLINEThe necessary number of computing steps for checking the identity \(f(b_1,\ldots,b_n)=1\) is \(2^{n-k}\), where the computation is based on the parallel structure of a \(k\)-bit processor (the number of computing steps in the usual table checking procedure is \(2^n\)). For the case \(2^n\leq 2^k\) one should put \(b_1,\ldots,b_n\) as binary sequence into \(2^k\)-bit registers and compute \(f(x_1,\ldots,x_n)\). In the case \(2^n>2^k\) each vector \(b_i\) should be divided simultaneously into blocks of size \(2^k\) (there are \(2^{n-k}\) such blocks).NEWLINENEWLINENEWLINEThe mathematical background of this paper are free finitely generated Boolean algebras.