NCB: Probably True?

How many tautologies are there in propositional logic? Yeah yeah, countably many of the critters. Fine. But what happens if I pick a propositional formula at random? What are my chances of lucking out and picking a tautology? This is the question that Alan Woods set out to answer. Alan is the one in the middle.

It turns out that it matters what you mean by random. Let's think about how we would do this asymptotically. Well, for a start, we'll just represent formulae using and, or, not and parentheses. So, we may think of a propositional formula as being a binary tree. Let's focus our attention on such trees with m literals over n variables. Actually, let's fix n throughout. Let T(m) denote the total number of such trees and let True(m) denote the number of such trees that represent tautologies. Then, unsurprisingly, we can say that the probability of a tautology is the limit as m goes to infinity of True(m)/T(m). Let's call this number P(True).

Another way to consider random formulae is to take a random walk to construct a tree and see what formula we end up with. To do this, start by flipping a fair coin. If it is heads, then roll a 2n-sided die to pick a literal. Stop at this stage. If it is tails, then we are goingto make the node a boolean connective. Flip the coin again to decide if it is a conjunction or disjunction. Then, rinse wash and repeat for the two conjuncts/disjuncts. Notice that there is no guarantee that this process even terminates, but it can be shown that it does so with probability 1. Now, what we have is a well defined probability of any particular formula appearing as a result of this process. Define p(True) to be the sum of the probabilities for each tautology.

Now, it turns out that P(True) and p(True) compute different numbers, though they are related. What can be shown is that p(True) < P(True) for every n (remember that n is the number of variables we are working with). Moreover, as n tends to infinity, p(True) is asymptotically 1/(4n) and P(True) is asymptotically 3/(4n). Want precise numbers? Ok, with n=3, we get p(True) = 0.0642 and P(True) = 0.165.

Of course, there is nothing really special about counting tautologies. Why not consider the probability of hitting some other propositional formula? All this and more has been done! For the details, look no further than:

And/or tree probabilities of boolean functions. Daniele Gardy and Alan Woods.

Stay tuned for more NCB fun tomorrow!