Logic 2 - Propositional Logic Syntax | Stanford CS221: AI (Autumn 2021)

Main ideas and concepts

• Purpose of the course module

  • The focus is on the syntax of propositional logic, and more broadly on how to think about:
    • Syntax (the formal structure of logical expressions)
    • Semantics (the meaning of those expressions—covered later)
    • Inference rules (how to manipulate logic and derive conclusions)
  • The emphasis is on algorithmic reasoning in AI, not manual “proof tinkering.”

• Algorithmic perspective on logic (AI goal)

  • In other classes, you may have practiced manually manipulating formulas.
  • Here, the goal is to build algorithms that can:
    • Manipulate logical formulas
    • Perform inference rules
  • Analogy given:
    • In Bayesian networks, even if you can compute or transform probabilities for a specific example, the real lesson is designing an algorithmic method (e.g., sampling) that works generally for any Bayesian network.
    • Similarly, here the goal is an algorithmic framework for logic.

• What “syntax” means in propositional logic

  • Syntax defines the rules for what counts as a well-formed formula (WFF) in the language.
  • Atomic / propositional symbols
    • Examples: a, b, c
    • These are also called atomic formulas.
  • Formulas are built recursively using logical connectives:
    • Negation (¬)
    • Conjunction / AND (∧, “and”)
    • Disjunction / OR (∨, “or”)
    • Implication (→)
    • Biconditional (↔, “if and only if” / “bi-directional implication”)

Methodology / construction rules

• Start with atomic formulas

  • Any propositional symbol (e.g., a, b, c) is a formula.

• Use recursive formation rules with connectives

  • If f and g are formulas, then each of the following is a formula:
    • Negation rule: ¬f
    • Binary AND rule: f ∧ g
    • Binary OR rule: f ∨ g
    • Implication rule: f → g
    • Biconditional rule: f ↔ g (described as “f is equivalent to g”)

• Examples of valid formulas

  • a (atomic)
  • ¬a
  • b → c
  • ¬b → c
  • ¬b ∨ d
  • ¬(¬a) (double negation is still a well-formed formula)

• Examples of invalid strings

  • a + b is not a formula because + has no defined meaning/syntax in this logic language.
  • ab (or “a followed immediately by b”) is not a formula because there is no logical connective/operator connecting them in the formal syntax.

Key lesson about syntax vs. semantics

• Syntax

  • Specifies symbol structure and which expressions are well-formed.
  • Assigns no meaning.

• Semantics (coming in the next module)

  • Will assign meaning to connectives (e.g., what negation or implication means).

• Important point

  • You could choose different symbols and define them as part of the syntax; the syntax is structural/formal and does not inherently carry meaning.

Speakers / sources featured

• Instructor / lecturer (unnamed speaker from Stanford CS221: AI (Autumn 2021))