Is it more probable that random propositional formula, as defined

in previous blogpost using true, nil and traditional connectives or,

and, not and -> is true or false? One would expect that it is equally

probable. Let us test this hypothesis.

(set 'random-formula (lambda(x) (if (= x 1) (amb true nil) (letn ((a (div (add (mul x 3) 4) (mul 2 (sub x 1)))) (r (random 0 (add 4 (mul 2 a))))) (cond ((<= 0 r 1) (list 'not (random-formula x))) ((<= 1 r 2) (list 'and (random-formula x) (random-formula x))) ((<= 2 r 3) (list 'or (random-formula x) (random-formula x))) ((<= 3 r 4) (list '-> (random-formula x) (random-formula x))) ((<= 4 r (add 4 a)) true) ; if a=2 then ((<= (add 4 a) r (add 4 a a)) nil)))))) (set '-> (lambda(x y)(or (not x) y))) (for (j 1 50) (set 'sum 0) (dotimes(i 100000) (if (eval (random-formula j)) ; power of eval (inc sum))) (println "Random formula of a length " j ". is true in " (div (mul 100 sum) 100000) "% of cases"))

Results:

Random formula of a length 1. is true in 49.855% of cases Random formula of a length 2. is true in 52.099% of cases Random formula of a length 3. is true in 52.636% of cases Random formula of a length 4. is true in 53.104% of cases Random formula of a length 5. is true in 53.224% of cases Random formula of a length 6. is true in 53.577% of cases Random formula of a length 7. is true in 53.339% of cases Random formula of a length 8. is true in 53.484% of cases Random formula of a length 9. is true in 53.513% of cases Random formula of a length 10. is true in 53.87% of cases Random formula of a length 11. is true in 53.889% of cases Random formula of a length 12. is true in 53.571% of cases Random formula of a length 13. is true in 53.917% of cases Random formula of a length 14. is true in 53.837% of cases Random formula of a length 15. is true in 54.14% of cases Random formula of a length 16. is true in 53.973% of cases Random formula of a length 17. is true in 53.811% of cases Random formula of a length 18. is true in 54.059% of cases Random formula of a length 19. is true in 53.929% of cases Random formula of a length 20. is true in 53.98% of cases Random formula of a length 21. is true in 53.818% of cases Random formula of a length 22. is true in 54.109% of cases Random formula of a length 23. is true in 53.999% of cases Random formula of a length 24. is true in 54.001% of cases Random formula of a length 25. is true in 54.095% of cases Random formula of a length 26. is true in 54.03% of cases Random formula of a length 27. is true in 54.215% of cases Random formula of a length 28. is true in 54.048% of cases Random formula of a length 29. is true in 54.12% of cases Random formula of a length 30. is true in 53.972% of cases Random formula of a length 31. is true in 53.752% of cases Random formula of a length 32. is true in 54.154% of cases Random formula of a length 33. is true in 54.229% of cases Random formula of a length 34. is true in 54.159% of cases Random formula of a length 35. is true in 53.972% of cases Random formula of a length 36. is true in 54.063% of cases Random formula of a length 37. is true in 53.926% of cases Random formula of a length 38. is true in 53.899% of cases Random formula of a length 39. is true in 54.078% of cases Random formula of a length 40. is true in 54.247% of cases Random formula of a length 41. is true in 54.14% of cases Random formula of a length 42. is true in 54.036% of cases Random formula of a length 43. is true in 54.05% of cases Random formula of a length 44. is true in 54.16% of cases Random formula of a length 45. is true in 53.964% of cases Random formula of a length 46. is true in 53.988% of cases Random formula of a length 47. is true in 54.075% of cases Random formula of a length 48. is true in 54% of cases Random formula of a length 49. is true in 53.975% of cases Random formula of a length 50. is true in 53.954% of cases

Why probability that random formula is true is consistently greater

than 50%? Because of asymmetry of traditionally basic logical connectives

and, or and ->. These are the truth tables (0 = nil, 1 = true):

x y (or x y) x y (and x y) x y (-> x y) ------------ ------------- ------------ 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 0 1 0 0 1 1 1 1 1 1 1 1 1

Look at the last column in each of these definitions - there are

total seven 1's and five 0's.

If formula of a given length, say l has connective or, and or

-> on a top level, the probability that it is true should be greater

than probability that it is false.

On the other side, if formula of the same length l has connective not

on the top level, then it is more probable that formula is false -

because not is applied on a random formula of a length l-1 which

is, supposedly more probable to be true. However, there is less of

formulas of length l-1 than formulas of a length l, so formulas

starting with not cannot compensate for formulas starting with

and, or and ->.

We proved that random formula of the length l is probably true -

if formula of the length l-1 is probably true. To complete the proof,

we must prove that random formula is probably true for some base

case:

1: true, false => 1 true, 1 false

2: (not true), (not false) => 1 true, 1 false

3: (or false false), (or false true), (or true false), (or true true),

(and false false), (and false true), (and true false), (and true true),

(-> false false), (-> false true), (-> true false), (-> true true)

(not (not true)), (not (not false)) => 8 true, 6 false.

If formula of a length 3 is probably true, then formula of the

length 4 is probably true and so on ...

Note that our random formulas have no fixed length - but they have

fixed average length, and it is enough that this asymmetry breaks

through.

Related posts: Propositional Variables and Formulas, 2009. |

Random Propositional Formulas of a Given Length |

---

## No comments:

## Post a Comment