Logic 3 - Propositional Logic Semantics | Stanford CS221: AI (Autumn 2021)

Main ideas and concepts (semantics in propositional logic)

Goal of the module: move from syntax to semantics

• Syntax: formulas are built from propositional symbols and logical connectives, with no meaning assigned yet (pure symbol manipulation).
• Semantics: assign meaning to these syntactic formulas by connecting them to truth assignments.

Model (in propositional logic)

In this logic lecture, a model means:

• Definition: a model (w) is an assignment of truth values to propositional symbols.
• If there are 3 symbols (a,b,c), there are (2^3 = 8) possible models (worlds).

Interpretation function

• Definition: an interpretation function (i) maps:
  • inputs: a formula (f) and a model (w)
  • output: a Boolean value (true/false, represented as 1/0) indicating whether (w) makes (f) hold
• Type: (i(f,w) \rightarrow {0,1})

Recursive definition of interpretation

• Base case (propositional symbol): For a propositional symbol (p), [ i(p,w) = \text{truth value assigned to } p \text{ by } w \quad (\text{i.e., } w(p)). ]

• Inductive/recursive step (composite formulas): (i(f,w)) is computed recursively based on the logical connectives:

  • Negation: (i(\neg f, w)) is the logical negation of (i(f,w))
  • Binary connectives (e.g., conjunction, disjunction, implication, equivalence): evaluated by computing truth-table-style combinations from (i(f,w)) and (i(g,w))

Models of a formula

• Definition: [ \text{models}(f) = {\, w \mid i(f,w)=1 \,} ]

• Intuition: (\text{models}(f)) is the set of exactly the worlds/assignments where the formula is true.

• Example idea: a compact formula like “rain or red” can correspond to a large set of satisfying assignments.

---

Knowledge bases and how adding information changes meaning

Knowledge base (KB)

• Definition: a knowledge base (KB) is a set of formulas the agent already knows.
• In the semantics view:
  • (\text{models}(KB)) corresponds to an intersection of models
  • If (KB) contains (f_1, f_2), then: [ \text{models}(KB)=\text{models}(f_1)\cap \text{models}(f_2). ]

Effect of adding a new formula

• Adding a formula to the KB shrinks the set of models:
  • more constraints ⇒ fewer satisfying assignments ⇒ smaller (\text{models}(KB))

---

Three cases: entailment, contradiction, contingency

When someone tells the agent a new formula (f), exactly one of these holds (defined via sets of models):

1. Entailment

   • Condition: [ KB \models f \iff \text{models}(KB)\subseteq \text{models}(f) ] (Equivalently: the worlds consistent with KB already satisfy (f).)

   • Meaning: (f) was already true in all worlds consistent with KB.

2. Contradiction

   • Condition: [ \text{models}(KB)\cap \text{models}(f)=\emptyset ]

   • Key relationship:

     • Contradiction with (f) is equivalent to entailment of the negation: [ KB \text{ contradicts } f \iff KB \models \neg f ]

3. Contingency (unknown / partial information)

   • Condition: [ \text{models}(KB)\cap \text{models}(f)\neq \emptyset ] but not equal to all of (\text{models}(KB))

   • Meaning: the KB allows some consistent worlds where (f) is true and some where it is not—so (f) is not determined.

---

Using this for virtual assistant behavior (tell/ask)

The lecture maps these logical cases to operations in a virtual assistant with a KB.

Tell operation: add a new formula (f) to the KB

• Start with current (KB), receive a new formula (f).

• Check which case applies, then respond:

• If entailment ((KB \models f)):

  • Response: “I already knew that.”
  • KB update: no change (adds no new constraints)

• If contradiction ((KB \models \neg f)):

  • Response: “I don’t believe that.”
  • KB update: no change (conflicts with existing knowledge)

• If contingency:

  • Response: “I learned something new.”
  • KB update: update the KB to include (f)

Ask operation: query a formula (f)

• Decide an answer based on the case:

• If entailment ((KB \models f)): answer Yes

• If contradiction ((KB \models \neg f)): answer No
• If contingency: answer “I don’t know”

---

Probabilistic connection (Bayesian networks intuition)

The lecture briefly generalizes from truth values to probabilities:

• Instead of only true/false (0/1), assign probabilities:
  • conceptually, (P(f \mid KB)) relates to the probability mass of worlds satisfying both (KB) and (f).
• Interpretation of outcomes:
  • probability 0 ⇒ contradiction
  • probability 1 ⇒ entailment
  • otherwise (between 0 and 1) ⇒ contingency

---

Satisfiability and reducing entailment/contradiction/contingency to SAT

Satisfiability (SAT)

• Definition: a knowledge base (KB) is satisfiable iff: [ \text{models}(KB)\neq \emptyset ]

• This corresponds to existence of at least one satisfying assignment (a model).

Using two SAT checks to classify the relationship between (KB) and (f)

The lecture describes determining the relationship via two calls to satisfiability:

1. First SAT call: check satisfiability of (KB \cup \neg f)

   • If unsatisfiable ⇒ (KB \models f) (entailment)
   • If satisfiable ⇒ not enough yet to conclude entailment (could be contingency or contradiction)

2. Second SAT call: check satisfiability of (KB \cup f)

   • If unsatisfiable ⇒ (KB \models \neg f) (contradiction)
   • If satisfiable ⇒ contingency

Model checking / CSP analogy

• Satisfiability checking is a form of model checking: does there exist an assignment/world satisfying the constraints?
• Mapping to CSP (constraint satisfaction problem):
  • propositional symbols ⇒ CSP variables
  • formulas ⇒ constraints
  • satisfying assignment/model ⇒ CSP solution

Solvers mentioned

• Backtracking-based SAT solvers (example: DPLL)
• Randomized local search (example: WalkSAT, likened to Gibbs sampling)
• Z3 (well-known SAT/SMT solver)

---

Overall takeaway

• Semantics connects formulas to truth assignments (models).
• A KB corresponds to the intersection of satisfying worlds.
• Any new formula falls into one of: entailment, contradiction, or contingency.
• These can be implemented for agent actions (tell/ask) and computed using SAT/model checking.

---

Speakers / sources featured

• Stanford CS221 course lecture (Autumn 2021) — no individual instructor name appears in the provided subtitles; the speaker is not explicitly identified.