Hintikka's Lemma

If we take φ and ψ to range over the set of propositional formulas, then the set H of propositional formulas is called a propositional Hintikka set if and only if

Hintikka's lemma states that every Hintikka set is satisfiable. The proof involves constructing a truth assignment, γ, where for each occurrence of the propositional variable X in the set we assign γ(X) = t, and for each occurrence of ¬X in the set, we assign γ(X) = f. It is easy to demonstrate that such an assignment can be constructed and that it satisfies the Hantikka set.


Fitting, Melvin. First-Order Logic and Automated Theorem Proving. Springer, 1990.