Proof Systems, Soundness & Completeness

Recap: Semantics

Previously covered:

• Propositional logic and syntax
• Truth tables for evaluating formulas
• Worlds: An allocation of truth values to propositional variables
• Semantic meaning (true or false) depends on the truth assignment

The Martian Analogy: Syntactic Transformations

<aside> 🛸

Imagine a Martian trying to understand translation from English to French. They don't understand meaning — they only see strings of symbols being transformed into other strings. This is a syntactic approach.

</aside>

Key insight: Formal proofs work the same way:

• They are syntactic transformations from one set of formulas to another
• No meaning is considered, just symbol manipulation
• Rules are strict and mathematical, like programs
• This is different from human proofs, which are about convincing and are more sociological constructs

Semantic Entailment

Example: Truth Table Analysis

Consider three formulas:

• φ: P → Q