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