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.