help with boolean algebra - comp.lang.lisp

Message from discussion help with boolean algebra

David Sletten

View profile

More options Jan 30 2005, 7:14 am

Newsgroups: comp.lang.lisp

From: David Sletten <da...@slytobias.com>

Date: Sun, 30 Jan 2005 12:14:53 GMT

Local: Sun, Jan 30 2005 7:14 am

Subject: Re: help with boolean algebra

  Reply to author
  |
  Forward
  | Print
  | View thread
  | Show original
  | Report this message
  | Find messages by this author
  

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

Reply to author Forward