On free Boolean vectors
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.
- Representing free Boolean algebras
- On the bit graph of Boolean vectors
- Free skew Boolean algebras
- On some properties of vector functions of Boolean algebra
- scientific article; zbMATH DE number 165484
- scientific article; zbMATH DE number 774018
- Free-Boolean independence for pairs of algebras
- On the complexity of narrow systems of Boolean vectors
- scientific article; zbMATH DE number 1138592
- Freely generated filters in free Boolean algebras
This page was built for publication: On free Boolean vectors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2774633)
