On Expected Truth Value of a Random Propositional Formula (2)

; Random propositional formula - is it true or false?

; Another function for definition of the random propositional formula
; is implemented. This time not the probability that graph edge is 
; leaf (true or nil) is given, instead, the size of the formula is
; exactly controlled. For example, if (random-formula 5) is called,
; then, first, logical connective is randomly chosen, and then,
; if that logical connective is not then
;
;   (list 'not (random-formula 4)) 
;
; is returned. If binary logical connective is chosen, the pair 
; (n1, n2) is also randomly chosen so n1+n2=4, and
;
;   (list connective (random-formula n1) (random-formula n2))
;
; is returned. There are also few simple special cases. 
          
(set 'random-formula2
  (lambda(x)
    (cond ((= x 1) (amb true nil))
          ((= x 2) (list 'not (random-formula2 1)))
          
          (true (let ((connective (amb 'not 'or 'and '->)))
                     
                     (cons connective
                     
                           (if (= connective 'not)
                               (list (random-formula2 (- x 1)))
                                       
                               (let ((r (apply amb (sequence 1 (- x 2)))))
                                     (list (random-formula2 r)
                                           (random-formula2 (- x 1 r)))))))))))
                                           
; I'll use debug-wrap from my library to demonstrate how function
; calls itself:

(load "http://www.instprog.com/Instprog.default-library.lsp") 

(debug-wrap random-formula2)
(random-formula2 7)

; 
; (random-formula2 (in 7)
;                  (random-formula2 (in 5)
;                                   (random-formula2 (in 4)
;                                                    (random-formula2 (in 1)
;                                                                     (out true))
;                                                    (random-formula2 (in 2)
;                                                                     (random-formula2 (in 1)
;                                                                                      (out true))
;                                                                     (out (not true))); m=2
;                                                    (out (or true (not true)))); t=31; m=5
;                                   (out (not (or true (not true))))); t=31; m=7
;                  (random-formula2 (in 1)
;                                   (out true))
;                  (out (-> (not (or true (not true))) true))); t=46; m=10
;

(debug-unwrap random-formula2)

; Let us look once again whether propositional formulas are really
; more probably true than false ... 


(for (x 0 10)
  (set 'j (pow 10 x))
  (set 'sum 0)
  (dotimes(i 1000)
    (if (eval (random-formula2 j)) ; power of eval
        (inc sum)))
  (println "Random formula of a length " j " is true in " 
           (div (mul 100 sum) 1000) "% of cases"))

; Random formula of a length 1 is true in 49.2% of cases
; Random formula of a length 10 is true in 55.2% of cases
; Random formula of a length 100 is true in 57.9% of cases
; Random formula of a length 1000 is true in 56.6% of cases
; Random formula of a length 10000 is true in 60% of cases
; Random formula of a length 100000 is true in 59.5% of cases

;

---