On 12/3/2016 6:28 AM, Henry Baker wrote:
I'm a little rusty on my propositional logic, so I can't remember (if I ever knew) the answer to the following questions:
1. Is there an easy way to enumerate/generate (all and only) *tautologies* in more-or-less increasing complexity fashion? By complexity, I mean more-or-less increasing fashion wrt the number of distinct variables and the size of the expression.
Wouldn't that be equivalent to enumerating all and only all proofs, which is impossible by Godel's theorem for axiom systems that allow induction. Brent
2. What % of prop logic expressions (of a particular complexity) are tautologies?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun