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 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)))
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 ***
| 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:
-- * 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 <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.
Jim Newton <ji...@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))))))
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?