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

• For every variable X it is not the case that both X ∈ H and ¬X ∈ H;
• neither f∈ H nor ¬t∈ H;
• if ¬¬φ∈ H then φ∈ H;
• if φ∧ψ∈ H then φ∈ H and ψ∈ H;
• if φ∨ψ∈ H then φ∈ H or ψ∈ H;
• if φ⇒ψ∈ H then ¬φ∈ H or ψ∈ H;
• if φ⇔ψ∈ H then both φ⇒ψ∈ H, and, ψ⇒φ∈ H.

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.

References

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