Subject:Some Fundamental Properties of Boolean Rings Jour: 28/11/97 (Vendredi 28 Novembre) http://pauillac.inria.fr/bin/calendar/Seminaires S E M I N A I R E ____ ____ ___ / _ _ / __ __ /_ _ / / | _ __ _ / / \ / \ ___ / / | / /_ / __| / ___ /___/ __| / | __| |___ |_/ |_/ |____ / / __/ |_ |_/ |_ / |_/ / |_/ / / I N R I A - Rocquencourt, Salle de confe'rence du batiment 11 Vendredi 28 Novembre, 11h30 ------------------- Jieh Hsiang ------------------- National Taiwan University ============================================================ Some Fundamental Properties of Boolean Rings ============================================================ Boolean ring is an algebraic structure which uses exclusive-or instead of the usual or. It yields a unique normal form for every Boolean function. Boolean rings were first studied by Zhegalkin in 1927, then by Stone in 1936. However, despite its long history and elegant algebraic properties, Boolean rings have not been utilized in neither computer science nor mathematics. In this talk we present several fundamental properties concerning Boolean rings. We present a simple method for deriving the Boolean ring normal form directly from a truth table. We also describe a notion of normal form of a Boolean function with a don't-care condition, and show an algorithm for generating such a normal form. We then discuss two Boolean ring based theorem proving methods for propositional logic. If time allows we shall also talk about the relationship between Boolean ring normal form and BDD. Finally we give some arguments on why the Boolean ring representation had not been used more extensively, and how it can be used in computing.