Equivalence of boolean expressions

I think the competing approach to exhaustive (and possibly exhausting) creation of truth tables would be to reduce all your expressions to a canonical form and compare those. For example, rewrite everything into conjunctive normal form with some rule about the ordering of symbols (eg alphabetical order within terms) and terms (eg alphabetical by first symbol in term). This of course, requires that symbol A in one expression is the same as symbol A in another.

How easy it is to write (or grab from the net) a C or C++ function for rewriting your expressions into CNF I don't know. However, there's been a lot of AI work done in C and C++ so you'll probably find something when you Google.

I'm also a little unsure about the comparative computational complexity of this approach and the truth-table approach. I strongly suspect that it's the same.

Whether you use truth tables or a canonical representation you can of course keep down the work to be done by splitting your input forms into groups based on the number of different symbols that they contain.

EDIT: On reading the other answers, in particular the suggestion to generate all truth tables and compare them, I think that @Iulian has severely underestimated the number of possible truth tables.

Suppose that we settle on RPN to write the expressions, this will avoid having to deal with brackets, and that there are 10 symbols, which means 9 (binary) operators. There will be 10! different orderings of the symbols, and 2^9 different orderings of the operators. There will therefore be 10! x 2^9 == 1,857,945,600 rows in the truth table for this expression. This does include some duplicates, any expression containing only 'and' and 'or' for instance will be the same regardless of the order of symbols. But I'm not sure I can figure this any further ...

Or am I making a big mistake ?

Can this be achieved without evaluating for all the possibilities? In our case we're talking about expressions containing even 20 boolean elements, which would mean 2^20 computations. The expressions are sometimes pretty complex. I would not rule out your solution by all means, but I hope to be able to do something different - less complex.

Iulian Şerbănoiu 2010-06-03 11:49:55

+1 That's probably the only reliable way to do it

qrdl 2010-06-03 11:50:04

@Iulian Şerbănoiu: You could look at Disjunctive Normal Form - http://en.wikipedia.org/wiki/Disjunctive_normal_form - perhaps you can sort the terms and then compare.

Mark Byers 2010-06-03 11:56:39

1 048 576 calculations are not _that_ much.

Daniel Daranas 2010-06-03 12:09:54

@Iulian: in general you probably wouldn't need to test all 2^20 solutions, as soon as you generate a different line for the same T/F inputs the expressions are different and you can go on to the next one.

High Performance Mark 2010-06-03 12:45:17

@Iulian: what do you mean by 'boolean element' ? An expression such as A+B (2 symbols, 1 function) or A (1 symbol, 0 functions) ?

High Performance Mark 2010-06-03 12:53:19

I meant symbol- boolean element is a symbol

Iulian Şerbănoiu 2010-06-03 13:02:38

@All, see my edit below, too much for a comment.

High Performance Mark 2010-06-03 13:08:45

I think this method may have better results in my particular case.

Iulian Şerbănoiu 2010-06-03 12:42:45

A truth table is a table with one row for each possible combination of input values, containing the value of the evaluated expression. There are two possible states for each input value, and the input values are independent - so there are `2**N` rows in the truth table where `N` is the number of different input values.

caf 2010-06-04 05:05:47

@caf: what you write is right, but @Iulian's problem would require the construction of multiple truth tables to resolve the question of whether multiple expressions are the same. I didn't make it terribly clear in my post or edit that this is what I was trying to count -- the number of rows in all the truth tables that would have to be constructed. And I'm still not sure that my figuring is correct.

High Performance Mark 2010-06-04 08:11:30

Well, if you want to compare two expressions, you don't actually need to construct an actual truth table at all. Just iterate over all the `2**N` combinations, for each combination calculate the value of expression 1 and expression 2, if they're unequal then the expressions are not equivalent. ie, it appears that the OP has two specific boolean expressions and wishes to compare those.

caf 2010-06-05 01:36:40

ansaurus

tags:

views:

answers:

Equivalence of boolean expressions

related questions