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 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.
File
Language	English
Year	2005
Edition	0
Translation	No
Refereed	No