Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleEnumerating the Propositions Equivalent to a Boolean Function
Author(s) Nachum Dershowitz, Mitchell A. Harris
TypeTechnical Report, Misc
AbstractA 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 non-linear 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.
Translation No
Refereed No