Google Groups Home
Help | Sign in
help with boolean algebra
There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic.
There was an error processing your request. Please try again.
flag
  8 messages - Collapse all
The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.
Your reply message has not been sent.
Your post was successful
Jim Newton  
View profile
 More options Jan 30 2005, 6:20 am
Newsgroups: comp.lang.lisp
From: Jim Newton <ji...@rdrop.com>
Date: Sun, 30 Jan 2005 12:20:07 +0100
Local: Sun, Jan 30 2005 6:20 am
Subject: help with boolean algebra
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


    Reply to author    Forward  
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
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

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  
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Barry Margolin  
View profile
 More options Jan 30 2005, 9:01 am
Newsgroups: comp.lang.lisp
From: Barry Margolin <bar...@alum.mit.edu>
Date: Sun, 30 Jan 2005 09:01:14 -0500
Local: Sun, Jan 30 2005 9:01 am
Subject: Re: help with boolean algebra
In article <363ub6F4rb37...@individual.net>,
 Jim Newton <ji...@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, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***


    Reply to author    Forward  
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Harald Hanche-Olsen  
View profile
 More options Jan 30 2005, 8:19 am
Newsgroups: comp.lang.lisp
From: Harald Hanche-Olsen <han...@math.ntnu.no>
Date: 30 Jan 2005 14:19:09 +0100
Local: Sun, Jan 30 2005 8:19 am
Subject: Re: help with boolean algebra
+ Jim Newton <ji...@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


    Reply to author    Forward  
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Jens Axel Søgaard  
View profile
 More options Jan 30 2005, 9:38 am
Newsgroups: comp.lang.lisp
From: Jens Axel Søgaard <use...@soegaard.net>
Date: Sun, 30 Jan 2005 15:38:15 +0100
Local: Sun, Jan 30 2005 9:38 am
Subject: Re: help with boolean algebra

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


    Reply to author    Forward  
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Andras Simon  
View profile
 More options Jan 31 2005, 11:44 am
Newsgroups: comp.lang.lisp
From: Andras Simon <asi...@math.bme.hu>
Date: 31 Jan 2005 17:44:21 +0100
Local: Mon, Jan 31 2005 11:44 am
Subject: Re: help with boolean algebra

Harald Hanche-Olsen <han...@math.ntnu.no> writes:
> + Jim Newton <ji...@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


    Reply to author    Forward  
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Pascal Bourguignon  
View profile
 More options Jan 31 2005, 12:07 pm
Newsgroups: comp.lang.lisp
From: Pascal Bourguignon <s...@mouse-potato.com>
Date: 31 Jan 2005 18:07:43 +0100
Local: Mon, Jan 31 2005 12:07 pm
Subject: Re: help with boolean algebra

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------


    Reply to author    Forward  
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
mmcconnell17...@yahoo.com  
View profile
 More options Feb 1 2005, 1:21 pm
Newsgroups: comp.lang.lisp
From: mmcconnell17...@yahoo.com
Date: 1 Feb 2005 10:21:09 -0800
Local: Tues, Feb 1 2005 1:21 pm
Subject: Re: help with boolean algebra
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?


    Reply to author    Forward  
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
End of messages
« Back to Discussions « Newer topic     Older topic »

Create a group - Google Groups - Google Home - Terms of Service - Privacy Policy
©2008 Google