Stanford CS221 | Autumn 2025 | Lecture 15: Logic I

Key Concepts

• Propositional Logic: The simplest form of logic using atomic symbols (variables) and logical connectives.
• Syntax: The set of rules defining valid formulas (e.g., $P \land Q$, $P \implies Q$).
• Semantics: The meaning of formulas, defined by truth values in specific "models" (possible worlds).
• Model ($W$): An assignment of truth values (True/False) to all propositional symbols.
• Interpretation Function ($I$): A recursive function that determines if a formula is true in a given model.
• Knowledge Base (KB): A set of formulas representing known facts about the world.
• Entailment ($\models$): When a KB implies a formula $F$ in all possible worlds.
• Satisfiability (SAT): Determining if there exists at least one model where a formula or KB is true.
• Inference Rules: Syntactic operations (e.g., Modus Ponens) to derive new facts from existing ones.
• Soundness vs. Completeness: Soundness ensures derived facts are true; Completeness ensures all true facts can be derived.

1. The Framework of Logic

Logic is presented as a formal language for knowledge representation and reasoning. Unlike search or probabilistic reasoning, logic is deterministic and symbolic.

• Syntax: Defines valid expressions. It is recursive; formulas are built from atomic symbols and connectives ($\neg, \land, \lor, \implies, \iff$).
• Semantics: Connects syntax to the real world. A formula is viewed as a set of models ($M(f)$)—the collection of all possible worlds where the formula holds true.
• Knowledge Base (KB): A collection of formulas. The semantics of a KB is the intersection of the models of all its individual formulas. As more facts are added, the set of possible models shrinks, representing increased certainty.

2. Logical Relationships

The relationship between a KB and a new formula $F$ is categorized into three states:

1. Entailment ($KB \models F$): The set of models does not shrink. $F$ is true in every world where the KB is true.
2. Contradiction ($KB \text{ contradicts } F$): The intersection of models is empty. $F$ is incompatible with the KB.
3. Contingency: The set of models shrinks but is not empty. $F$ provides new, non-contradictory information.

3. Operationalizing Logic: Ask and Tell

• Ask: Queries the KB. Returns "Yes" (if entailed), "No" (if contradicted), or "I don't know" (if contingent).
• Tell: Adds information to the KB. Returns "Already knew that" (entailment), "I don't buy that" (contradiction), or "I learned something new" (contingency).

4. Computational Efficiency: Satisfiability (SAT)

While model enumeration is exponentially expensive ($2^n$ models for $n$ symbols), logical operations can be reduced to Satisfiability (SAT) checking:

• Entailment: $KB \models F$ is equivalent to checking if $KB \land \neg F$ is unsatisfiable.
• Contradiction: $KB \land F$ is unsatisfiable.
• Tools: Modern SMT solvers (like Z3) are used to perform these checks efficiently, even for problems with hundreds of thousands of variables, despite SAT being NP-complete.

5. Inference Rules and Human Reasoning

Unlike model checking (which is semantic), inference rules are syntactic.

• Modus Ponens: A fundamental rule: Given $P$ and $P \implies Q$, one can derive $Q$.
• Soundness: A system is sound if it only derives true facts (it never produces a false conclusion from true premises).
• Completeness: A system is complete if it can derive every fact that is logically entailed.
• Analogy: The instructor uses a "glass of water" analogy: Truth is the glass; Soundness ensures you don't pour water outside the glass; Completeness ensures you fill the glass entirely.

6. Connection to Probabilistic Reasoning

The lecture highlights that Bayesian Networks are a probabilistic generalization of propositional logic:

• Evidence: Analogous to the Knowledge Base.
• Query: Analogous to the formula $F$.
• Difference: Logic uses binary truth (0 or 1), whereas Bayesian Networks use probabilities (0 to 1). Logic allows for more expressive queries (e.g., "Rain or Snow") that are not native to standard Bayesian variable-assignment structures.

Synthesis

Logic provides a compact, expressive way to represent knowledge. By defining syntax, semantics, and inference rules, we create a system capable of rigorous reasoning. While model checking is the theoretical foundation, practical AI applications rely on SAT solvers to handle complexity. The transition from propositional logic to first-order logic (the next topic) will further expand the ability to represent complex relationships in the world.