Details:
Title  Enumerating the Propositions Equivalent to a Boolean Function  Author(s)  Nachum Dershowitz, Mitchell A. Harris  Type  Technical Report, Misc  Abstract  A general method is presented for counting the propositional formulas of a given size that are equal to an arbitrary boolean function. The number of formulas equivalent to each boolean function on v variables is calculated using a system of nonlinear recurrence relations. For particular boolean functions are and for small values of v, simplification for exact computation is feasible. As a corollary, it is shown that the probability that a formula over one variable is satisfiable is asymptotically 1  1/2 3^(1/3) = 0,711325. 
File 
 Language  English  Year  2005  Edition  0  Translation 
No  Refereed 
No 
