<aside> 🎯

Tutorial covering semantic entailment, recursive semantic evaluation, equivalence relations, tautologies, satisfiability, and logical equivalence proofs using truth tables.

</aside>

Topics covered:

• Semantic entailment using truth tables
• Recursive semantic function evaluation ([φ]_σ notation)
• Proving logical equivalence is an equivalence relation
• Counting logical equivalence classes
• Tautologies and satisfiability
• Proving logical equivalence with truth tables

Semantic Entailment

What is Semantic Entailment?

Semantic entailment (written as ⊨) requires that for all values where the premise is true, the conclusion is also true.

Notation:

• Premise ⊨ Conclusion
• Also written with double arrow ⇒ (common in logic texts)
• Single arrow → is the same as double arrow in this context

Understanding the Premise

Think of the premise as an environment or context:

• It's something we know to be necessarily true
• If the premise is true, semantic entailment requires the conclusion to also be true