help with boolean algebra - comp.lang.lisp

Message from discussion help with boolean algebra

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

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

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