Generalization of Boole-Shannon expansion, consistency of Boolean equations and elimination by orthonormal expansion

preprint2013arXivOpen access

Abstract

The well known Boole-Shannon expansion of Boolean functions in several variables (with co-efficients in a Boolean algebra BB) is also known in more general form in terms of expansion in a set ΦΦ of orthonormal functions. However, unlike the one variable step of this expansion an analogous elimination theorem and consistency is not well known. This article proves such an elimination theorem for a special class of Boolean functions denoted B(Φ)B(Φ). When the orthonormal set ΦΦ is of polynomial size in number nn of variables, the consistency of a Boolean equation f=0f=0 can be determined in polynomial number of BB-operations. A characterization of B(Φ)B(Φ) is also shown and an elimination based procedure for computing consistency of Boolean equations is proposed.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.