Proving Tautologies

Several years ago I took a computer science class, where I seem to remember my teacher saying something about there being no easy way to prove tautologies (a tautology is a Boolean equation that is always true). I'm no expert in the field, but looking online it seems like there are two main techniques for proving that an equation is a tautology: using a truth table (brute force method) or doing a proof.

However, it seems to me that you might be able to use a probabilistic technique as well. If you have a Boolean variable named "A" (a Boolean variable can have two values: true and false) then it has a 50% chance of being true, and 50% chance of being false. "A" is therefore not a tautology, because half the time it would be false and a tautology must always be true.

But what about A & B? If A is true and B is true, than A & B is true. If either or both A and B are false, then A & B is also false. Here is the truth table technique:

A B | A&B
---------
F F | F
F T | F
T F | F
T T | T

Note that A & B is always false, except where A and B are both true. Therefore, A & B are not a tautology, because a tautology must always be true.

But here's where the probabilist method comes in. If there's a 50% chance of A being true (note how half the rows have A as True), and there's a 50% chance of B being true (note how half the rows have B as True), then there's a (1/2) * (1/2) chance of A & B being true. That's a 1/4 chance of A & B being true, and we can double check against the right-most column in the truth table above: 1 out of 4 results are true.

So that's & ("and") but there are a lot more logical operations.

• And / conjunction ( & )
  
• Or / disjunction ( | )
  
• Not / negation ( ~ )
  
• Implication / if-then ( --> )
  
• Equivalence / biconditional / xnor / if-and-only-if (<--> )
  
• Not equivalent / exclusive disjunction / xor ( <-/-> )
  

Plus several more, but these are the basic ones.

Since this post is already getting long, I'll just list the probability equations for those logical operations, without explaining how they can be derived (in my case, from the Venn diagrams).

e.g. "Pa" means the Probability of "a".

• And: Pa*Pb
• Or: Pa + Pb - Pa*Pb
• Not: 1 - Pa
• Implies: 1 - Pa + Pa*Pb
• Equivalence: 1 - Pa - Pb + 2*Pa*Pb
• Not Equivalent: Pa + Pb - 2*Pa*Pb

So let's take a look at a sample equation and prove whether it's a tautology or not.

(a & b) | (~a) | (~b)

Truth table:

a b | a&b | ~a | ~b | (~a | ~b) | ((a&B) | (~a | ~b))
-----------------------------------------------------
F F | F | T | T | T | T
F T | F | T | F | T | T
T F | F | F | T | T | T
T T | T | F | F | F | T

All the rows have a True in the right-most column, so that is a tautology. Now let's try the probabilistic method.

(a & b) | (~a) | (~b) =
(Pa*Pb) | (1-Pa) | (1-Pb) =
(Pa*Pb + 1 - Pa + Pa*Pb + Pa*Pb*(1-Pa)) | (1-Pb) =
(Pa*Pb + 1 - Pa) | (1-Pb) = (note that as we distributed Pa over (1-Pa), Pa & Pa simplifies to just Pa, and we can cancel terms out)
Pa*Pb + 1 - Pa + 1 - Pb - (Pa*Pb + 1 - Pa)*(1 - Pb) =
Pa*Pb + 1 - Pa + 1 - Pb - Pa*Pb + Pa*Pb - 1 + Pb + Pa - Pa*Pb =
= 1

"1", or 100% chance of being true, proving it's a tautology.

Is that better than a truth table, or a formal proof? It sure looks longer than a truth table, and a formal proof would probably only have a half-dozen lines at the most.

Well, a formal proof requires you to memorize various laws and rules. This technique just took basic algebra. And a truth table grows very quickly: there's 2^n rows, where "n" is the number of distinct variables. In this example, there were two: "a" and "b", so there were 2^2 or 4 rows. This probabilistic method, on the other hand, grows nicely. Let's look at another simple example:

a & b & c & d & e & f & g & h & i & j

How would this proof play out formally? With 10 different variables, there would be 2^10 or 1024 rows in a truth table. That's a big table (we're ignoring shortcuts that we can sometimes take when making a truth table, since we can only "sometimes" take them and we want a method that is always fast). Using our probabilistic technique, though, the proof is this:

Pa*Pb*Pc*Pd*Pe*Pf*Pg*Ph*Pi*Pj =
(1/2)*(1/2)*(1/2)*(1/2)*(1/2)*(1/2)*(1/2)*(1/2)*(1/2)*(1/2) =
= 1/1024

So this particular proof is only three lines, and it shows that there's a 1/1024 chance of each row being True. We need 1024 / 1024 or "1" or 100% chance of each row being True, so we can see we're a long ways from having a tautology.

With this massively long post written, I have to say that I have no idea if this is really unique, or even helpful. It seems like it might be, but I don't know enough about the problem to know if my insight is really an insight. Come Monday, I'll ask around the lab and see if anyone knows whether this way of proving tautologies has been done before.