Introduction to Propositional Logic: Syntax

<aside> ⚡

Master the foundations of propositional logic and formal reasoning. Learn the three pillars of logic systems (syntax, semantics, deduction), understand propositional variables, logical operators, BNF derivation rules, syntax trees, and operator precedence conventions. Build syntactically correct formulas and prepare for formal proofs!

</aside>

At-a-glance checklist

• [ ] Understand the three components of a logic system: syntax, semantics, and deduction
• [ ] Recognize propositions (statements that can be true or false, but not both)
• [ ] Master propositional variables (P, Q, R) that represent boolean values
• [ ] Learn the five logical operators: ¬ (negation), ∧ (conjunction/AND), ∨ (disjunction/OR), → (implication), ⊥ (contradiction)
• [ ] Use BNF (Backus-Naur Form) rules to derive syntactically correct formulas
• [ ] Construct syntax trees to represent formula structure
• [ ] Understand one-to-one correspondence: well-bracketed formulas ↔ BNF derivations ↔ syntax trees
• [ ] Apply operator precedence rules: negation > conjunction/disjunction > implication
• [ ] Know associativity: conjunction/disjunction associate left, implication associates right
• [ ] Use Greek letters (φ, ψ, χ) to represent entire formulas

Key takeaways

Three pillars of logic: Every logic system has syntax (symbols and rules), semantics (meaning/truth values), and deduction (proving conclusions from premises). Master all three!

BNF ensures correctness: If you can derive a formula from BNF rules starting with F, the formula is syntactically valid. Can't derive it? It's not a proper formula.

Syntax trees visualize structure: The root shows the top-level operator, children show sub-formulas. P ∧ Q → R has implication as root, conjunction (P ∧ Q) and R as children.

Order matters syntactically: P ∧ Q and Q ∧ P are different formulas even if they have the same meaning. Syntax is about structure, not semantics.