The Probability That Random Propositional Formula is Tautology

; In last few posts we have shown that radnom propositional formula ; using classical connectives or, and and ->, and without variables ; is more probably true than false. In this post, we'll show that ; probability that propositional formula with variables is tautology ; is surprisingly high. (load "http://www.instprog.com/Instprog.default-library.lsp") ; The function rnd-pf returns random propositional formula. For ; example, (rnd-pf 10 '(true nil x y z) '(not) '(or and ->)) will ; return radnom formula of the size 10, with leafs true, nil, x, y ; and z; unary connective not and binary connectives or, and and ->. (set 'element find) (set 'rnd-pf   (lambda(len leafs unary binary)     (let ((connectives (append unary binary)))       (cond ((= len  1)                (apply amb leafs))             ((= len  2)                (list (apply amb unary)                  (rnd-pf 1 leafs unary binary)))             ((> len  2)                (let ((connective (apply amb connectives)))                  (cons connective                        (if (element connective unary)                            (list (rnd-pf (- len  1) leafs unary binary))                            (let ((r (apply amb (sequence 1 (- len  2)))))                                  (list (rnd-pf r leafs unary binary)                                        (rnd-pf (- len 1 r) leafs unary binary))))))))))) ; In following part of the program, 1000 random propositional formulas ; of the size 1000 (that means, 1000 nodes in graph) are constructed, ; and probability that random formula is tautology is calculated. It ; is done for various number of variables, from no variables at all ; to 17 variables. (set 'vars '(a b c d e f g h i j k l m n o p q r s t u v w x y z)) (dotimes(j 20)   (set 'tautologies 0)    (dotimes(i 1000)      (set 'rf (rnd-pf 1000 (append '(true nil) (slice vars 0 j)) '(not) '(and or ->)))   (when (tautology? rf)         (inc tautologies)))    (println "Formulas with " j " variables: " (/ tautologies 10) "% tautologies.")) ; The results are: ; ; Formulas with 0 variables: 58% tautologies. ; Formulas with 1 variables: 51% tautologies. ; Formulas with 2 variables: 42% tautologies. ; Formulas with 3 variables: 42% tautologies. ; Formulas with 4 variables: 34% tautologies. ; Formulas with 5 variables: 31% tautologies. ; Formulas with 6 variables: 31% tautologies. ; Formulas with 7 variables: 30% tautologies. ; Formulas with 8 variables: 27% tautologies. ; Formulas with 9 variables: 22% tautologies. ; Formulas with 10 variables: 22% tautologies. ; Formulas with 11 variables: 21% tautologies. ; Formulas with 12 variables: 22% tautologies. ; Formulas with 13 variables: 16% tautologies. ; Formulas with 14 variables: 18% tautologies. ; Formulas with 15 variables: 19% tautologies. ; Formulas with 16 variables: 16% tautologies. ; Formulas with 17 variables: 16% tautologies. ;