Propositional Logic — Syntax and Semantics — Beginner-Friendly Notes

1. What It Is

Propositional logic: logic of true/false statements (propositions) combined with connectives. Each proposition is atomic — no internal structure (e.g., $P$ = "it rains").

2. Syntax — How to Write Sentences

• Atomic propositions: symbols $P, Q, R$ (each true or false).
• Connectives: $
  eg$(NOT),$\land$(AND),$\lor$(OR),$\Rightarrow$(IMPLIES),$\Leftrightarrow$ (IFF).
• Formation: if $P,Q$ are sentences, so are $
  eg P$,$P \land Q$,$P \lor Q$,$P \Rightarrow Q$,$P \Leftrightarrow Q$, and$(P \land Q) \Rightarrow R$.

Precedence: $
eg$>$\land$>$\lor$>$\Rightarrow$>$\Leftrightarrow$; use parentheses for clarity.

Examples:

• "If it rains then ground wet": $P \Rightarrow Q$
• "Ground not wet and it rains": $P \land
  eg Q$

3. Semantics — What Sentences Mean (truth tables)

An interpretation assigns each atomic proposition true/false. Sentence truth is computed compositionally:

| $P$ | $Q$ | $

eg P$|$P \land Q$|$P \lor Q$|$P \Rightarrow Q$|$P \Leftrightarrow Q$ |
|---|---|---|---|---|---|---|
| T | T | F | T | T | T | T |
| T | F | F | F | T | F | F |
| F | T | T | F | T | T | F |
| F | F | T | F | F | T | T |

Key: $P \Rightarrow Q$ is false only when $P$ true and $Q$ false; otherwise true.

4. Core Semantic Concepts

• Model: an assignment that makes sentence true.
• Satisfiable: has at least one model.
• Valid (tautology): true in all models (e.g., $P \lor
  eg P$).
• Unsatisfiable (contradiction): true in no model (e.g., $P \land
  eg P$).
• Entailment: $KB \models α$ iff every model of $KB$ makes $α$ true — $α$ logically follows.

5. Why It Matters for AI

• Basis for knowledge base reasoning: $KB$ (set of sentences) + inference rules → new facts.
• Limit: cannot say "for all $x$, if $x$ is bird then $x$ flies" without enumerating each bird → needs first-order logic (next).

6. One-Line Summary

Propositional logic builds sentences from atoms with $
eg, \land, \lor, \Rightarrow, \Leftrightarrow$, whose semantics is given by truth tables, defining models, satisfiability, validity and entailment$KB \models α$.

7. Quick Self-Check

1. When is $P \Rightarrow Q$ false?
2. Is $P \land
   eg P$ satisfiable?