Hi everyone, I'm writing a LISP program to solve a certain
types of systems of boolean equastions. Does anyone
know a lot about boolean algebra? It would be nice to
talk to someone about my ideas. The algorithms are not
specific to lisp but the implementation is.
What I need are some identities envolving several
boolean variables with the operations of XOR and AND.
Notation: !A represents (not a)
and AB represents (and a b)
and !AB represents (and (not a) b)
and + represents XOR -- A + B <=> (xor a b)
I have the following three identies and have generalized them
to several variables.
t = A + !A
t = A + !AB + !A!B
t = AB + !AB + A!B + !A!B
Are there other identies envolving XOR and AND and NOT?
All others that i can think of are derivable from these
three.
For example: AB => A ( => implies)
is equivalent to : t = !(AB) + A + A!(AB)
which apparently simplifies to: t = A + !AB + !A!B
I'll be very happy to share the lisp code with anyone interested.
-jim
In article <···············@individual.net>,
Jim Newton <·····@rdrop.com> wrote:
> Are there other identies envolving XOR and AND and NOT?
Isn't this the kind of thing you should have learned in Logic 101
(although, IIRC we tended to use OR much more than XOR)? If you didn't
take it, surely you can find the textbook?
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
Jim Newton wrote:
> Hi everyone, I'm writing a LISP program to solve a certain
> types of systems of boolean equastions. Does anyone
> know a lot about boolean algebra? It would be nice to
> talk to someone about my ideas. The algorithms are not
> specific to lisp but the implementation is.
>
> What I need are some identities envolving several
> boolean variables with the operations of XOR and AND.
>
> Notation: !A represents (not a)
> and AB represents (and a b)
> and !AB represents (and (not a) b)
> and + represents XOR -- A + B <=> (xor a b)
>
> I have the following three identies and have generalized them
> to several variables.
>
> t = A + !A
> t = A + !AB + !A!B
> t = AB + !AB + A!B + !A!B
>
>
> Are there other identies envolving XOR and AND and NOT?
> All others that i can think of are derivable from these
> three.
>
> For example: AB => A ( => implies)
> is equivalent to : t = !(AB) + A + A!(AB)
> which apparently simplifies to: t = A + !AB + !A!B
>
> I'll be very happy to share the lisp code with anyone interested.
>
> -jim
Jim,
Strictly speaking you are not working with 'Boolean algebra' but rather
the algebra of propositions, which is a Boolean algebra. Boolean
algebras categorize a class of mathematical systems including, for
example, the algebra of sets (union, intersection, ...).
Notations vary, but typically when AB is used to represent conjunction
(logical AND) the symbol + is used for disjunction (logical OR, i.e.,
inclusive OR not XOR). Usually, XOR is denoted using a modification of
the symbol for OR, such as the plus/minus sign (a line under the +).
Java uses ^ for its bitwise XOR operator, but this symbol is also
frequently used to represent AND (with v used for OR).
Are you familiar with the use of truth tables? What about DeMorgan's
Laws (+ is OR here):
!(A+B) == !A!B
!(AB) == !A + !B
I would suggest reading a book on elementary mathematical logic to
explore some of the identities you're looking for. In particular, are
you familiar with the idea that all of these operations can be expressed
simply using NOT and AND, i.e., NAND:
AB = !(!(AB)!(AB))
A+B = !(!(AA)!(BB))
In other words,
(defun logical-and (a b) (nand (nand a b) (nand a b)))
(defun logical-or (a b) (nand (nand a a) (nand b b)))
David Sletten
+ Jim Newton <·····@rdrop.com>:
| Does anyone know a lot about boolean algebra?
No. There isn't a whole lot to know about it.
| What I need are some identities envolving several
| boolean variables with the operations of XOR and AND.
|
| Notation: !A represents (not a)
| and AB represents (and a b)
| and !AB represents (and (not a) b)
| and + represents XOR -- A + B <=> (xor a b)
Calculating with truth values using these operations is equivalent to
doing arithmetic modulo 2, where + corresponds to _xor_, and
multiplication corresponds to _and_. And finally, negation (not a)
corresponds to adding 1.
In particular, all the standard rules of arithmetic apply.
In fact, one often talks about boolean rings to be rings with identity
in which every element satisfies xx=x:
http://en.wikipedia.org/wiki/Boolean_ring
There are other ways to axiomatize propositional logic:
http://en.wikipedia.org/wiki/Propositional_logic
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- Debating gives most of us much more psychological satisfaction
than thinking does: but it deprives us of whatever chance there is
of getting closer to the truth. -- C.P. Snow
Harald Hanche-Olsen <······@math.ntnu.no> writes:
> + Jim Newton <·····@rdrop.com>:
>
> | Does anyone know a lot about boolean algebra?
>
> No. There isn't a whole lot to know about it.
There is, actually. Have a look at Paul Halmos' nice little book, or
the three volume Handbook of Boolean Algebras (ed. J.D. Monk) for a
more complete picture.
The equational theory ("arithmetic") of BAs is not that exciting,
for sure. But see http://www-unix.mcs.anl.gov/~mccune/papers/robbins/
where a (computer aided) solution to a 60 years old problem is
reported.
Andras
There's quite a bit to say about boolean algebra. It is algebraic
geometry over the field Z/2. Hence it should be compared to algebraic
geometry over Z (a.k.a. number theory, including Fermat's last theorem,
elliptic curve cryptography...) The areas are not equally rich, but,
like I say, should be compared.
An example: write down a random boolean polynomial equation like
ABC + BCD + CDE + DEA + EAB + ABDE + CD = false
and try to solve it without just grinding out the truth table. Now do
the same for
ABC + BCD + 17*CDE + DEA + 3*EAB + ABDE + 5*CD = 0
over the integers, looking for integer solutions. They're the same
kind of beast, though the latter is harder.
To put the same thing into practical language, converting a random
boolean polynomial into the smallest "normal form" is a serious
problem. It's like factoring in ordinary algebra:
x^3 + 15*x^2 + 75*x + 125 is a lot more compact if you discover it
equals (x+5)^3.
Chip designers have to address the boolean-algebra version of this
problem.
To the OP: are any parts of this post related to what you're aiming at?
Jim Newton wrote:
> Are there other identies envolving XOR and AND and NOT?
> All others that i can think of are derivable from these
> three.
<http://www.cs.rochester.edu/u/leblanc/csc173/proplogic/laws.html>
<http://www.cs.rochester.edu/u/leblanc/csc173/proplogic/expressions.html>
--
Jens Axel Søgaard
Jim Newton <·····@rdrop.com> writes:
> Hi everyone, I'm writing a LISP program to solve a certain
> types of systems of boolean equastions. Does anyone
> know a lot about boolean algebra? It would be nice to
> talk to someone about my ideas. The algorithms are not
> specific to lisp but the implementation is.
>
> What I need are some identities envolving several
> boolean variables with the operations of XOR and AND.
>
> Notation: !A represents (not a)
> and AB represents (and a b)
> and !AB represents (and (not a) b)
> and + represents XOR -- A + B <=> (xor a b)
>
> I have the following three identies and have generalized them
> to several variables.
>
> t = A + !A
> t = A + !AB + !A!B
> t = AB + !AB + A!B + !A!B
>
>
> Are there other identies envolving XOR and AND and NOT?
> All others that i can think of are derivable from these
> three.
>
> For example: AB => A ( => implies)
> is equivalent to : t = !(AB) + A + A!(AB)
> which apparently simplifies to: t = A + !AB + !A!B
>
> I'll be very happy to share the lisp code with anyone interested.
>
> -jim
What makes:
t = AB + !AB + A!B + !A!B
so special and not, for example:
T = (NOT (XOR
(NOT
(AND (XOR (NOT A) T)
(NOT (XOR (NOT A) (XOR (AND B T) (NOT B))))))
(NOT (AND C (NOT (XOR (NOT C) T))))))
(and an infinity of other tautologies)?
--
__Pascal Bourguignon__ http://www.informatimago.com/
-----BEGIN GEEK CODE BLOCK-----
Version: 3.12
GCS d? s++:++ a+ C+++ UL++++ P--- L+++ E+++ W++ N+++ o-- K- w---
O- M++ V PS PE++ Y++ PGP t+ 5+ X++ R !tv b+++ DI++++ D++
G e+++ h+ r-- z?
------END GEEK CODE BLOCK------