CSE 4355 · W2 C2 · Logic, inference and expert systems

01 Cold open 0–4 min

Minesweeper is a logic exam

Minesweeper is model checking Click a hidden cell. The tool enumerates every mine layout consistent with the numbers.

1 2

1

2

3

1

4

1

5

1

ABCDEF

Pick any hidden cell next to a number. Predict first: safe, mine, or can't tell?

Frontier cells9

Models checked2⁹ = 512

Consistent2

Provable now6

Pop culture

Every Windows PC shipped with a logic tutor for decades. Good players never guess: they prove a cell is safe from the numbers. Sherlock calls it deduction; we call it entailment.

Each number is a sentence about its hidden neighbours. A cell is safe if it is safe in every world that agrees with all the numbers.

By the end of today you'll know exactly what the tool on the left is doing, and why it doesn't scale.

02 Concept 4–8 min

A knowledge-based agent: TELL, ASK, repeat

A knowledge base (KB) is a set of sentences in a formal language. The agent TELLs it what it perceives and ASKs it what to do; an inference engine works out answers that were never stored explicitly.

function KB-AGENT(percept):          ; t = time step
   TELL(KB, MAKE-PERCEPT-SENTENCE(percept, t))
   action = ASK(KB, MAKE-ACTION-QUERY(t))
   TELL(KB, MAKE-ACTION-SENTENCE(action, t))
   t = t + 1
   return action

Fact

One specific truth. $\text{Fever}(\text{Rahim})$

Rule

A general truth that makes new facts. $\text{Fever}(x) \land \text{LowPlt}(x) \Rightarrow \text{Suspect}(x)$

Representation	Good at
Propositional logic	Small, fixed worlds (a Minesweeper corner)
First-order logic	Objects and relations: “every patient…”
IF–THEN rules	Expert know-how, easy to explain
Semantic nets, frames	Categories, inheritance, defaults
Probabilities	Uncertainty (Week 8: Bayes)

Pro tip

Declarative: say what is true and let the engine decide how to use it. Procedural: hard-code how. A KB can be updated without rewriting the program.

03 Concept 8–12 min

Propositional logic in five symbols

Atoms (P, Q, Dengue) are true or false. Connectives build sentences, tightest first: ¬, ∧, ∨, ⇒, ⇔. A model is one assignment of T/F to every atom: one possible world.

P	Q	¬P	P ∧ Q	P ∨ Q	P ⇒ Q	P ⇔ Q
F	F	T	F	F	T	T
F	T	T	F	T	T	F
T	F	F	F	T	F	F
T	T	F	T	T	T	T

Gotcha

⇒ is not causation. “If Messi is from Bogura, then 2 + 2 = 5” is true: a false premise makes P ⇒ Q true (the highlighted rows). P ⇒ Q only promises: never P true with Q false.

P \Rightarrow Q \;\equiv\; \lnot P \lor Q

Entailment, α follows from the KB: $\text{KB} \models \alpha \iff M(\text{KB}) \subseteq M(\alpha)$ , where M(·) is the set of models that make a sentence true.

Precedence: $\lnot A \land B \lor C \Rightarrow D$ means $((\lnot A \land B) \lor C) \Rightarrow D$ . When in doubt, bracket.

04 Live lab 12–18 min

Entailment: check every possible world

Entailment by model checking KB ⊨ α when α is true in every row where the KB is true.

R: Red is the impostor · B: Blue is the impostor · V: someone saw Blue vent

Knowledge base

KB1

R \lor B

KB2

B \Rightarrow V

KB3

\lnot V

Ask α =

R	B	V	KB1	KB2	KB3	KB	α
F	F	F	·	·	·	·	·
F	F	T	·	·	·	·	·
F	T	F	·	·	·	·	·
F	T	T	·	·	·	·	·
T	F	F	·	·	·	·	·
T	F	T	·	·	·	·	·
T	T	F	·	·	·	·	·
T	T	T	·	·	·	·	·

3 symbols → 2³ = 8 models · KB true in ? so far

05 Worked example 18–22 min

Worked example: who is the impostor?

Given

An Among Us meeting. (1) “It's Red or Blue.” (2) “If Blue is the impostor, someone saw Blue vent.” (3) “Nobody saw Blue vent.” Symbols: R, B, V.

Find

Prove by truth table that the KB entails R. Then prove it again with inference rules.

R	F	F	F	F	T	T	T	T
B	F	F	T	T	F	F	T	T
V	F	T	F	T	F	T	F	T
KB	F	F	F	F	T	F	F	F

Method: truth-table entailment, Russell & Norvig “Logical Agents”

Solution

Predict the answer first. Then reveal one step at a time.

06 Concept 22–26 min

Valid, satisfiable, and proofs you can trust

Valid true in every model (a tautology). $L \lor \lnot L$

Satisfiable true in some model. $D \Rightarrow L$

Unsatisfiable true in no model. $D \land \lnot D$

Two bridges that power every prover:

\begin{aligned} \text{KB} \models \alpha &\iff (\text{KB} \Rightarrow \alpha)\ \text{is valid} \\ &\iff \text{KB} \land \lnot\alpha\ \text{is unsatisfiable} \end{aligned}

The last one is proof by contradiction: the idea behind resolution.

Modus ponens

\dfrac{\alpha \Rightarrow \beta,\quad \alpha}{\beta}

And-elimination

\dfrac{\alpha \land \beta}{\alpha}

Unit resolution

\dfrac{\alpha \lor \beta,\quad \lnot\beta}{\alpha}

Resolution

\dfrac{\alpha \lor \beta,\quad \lnot\beta \lor \gamma}{\alpha \lor \gamma}

Sound: derives only entailed sentences (no lies). Complete: can derive every entailed sentence (no blind spots).

07 Your turn 26–29 min

Your turn · 1: entailed or not?

03:00

1 Exam CQ

Let D = “the patient has dengue”, L = “platelets are low”.

(a) Does {D ⇒ L, ¬L} entail ¬D?

(b) Does {D ⇒ L, L} entail D?

(c) Classify as valid, satisfiable or unsatisfiable: $L \lor \lnot L,\quad D \land \lnot D,\quad D \Rightarrow L$

Work it out first.
Press Solve when the class has an answer.

08 Concept 29–32 min

Horn clauses: logic's fast lane

A definite clause is a disjunction with exactly one positive literal. It reads as a rule:

\lnot A \lor \lnot B \lor C \;\equiv\; A \land B \Rightarrow C

A fact is a definite clause with an empty body (just C). A Horn clause has at most one positive literal, so it also allows goal clauses like $\lnot A \lor \lnot B$ (i.e. $A \land B \Rightarrow \text{False}$ ).

Pro tip

With Horn KBs, modus ponens alone is complete, and entailment takes linear time in the KB size. That is why Prolog, CLIPS and most expert systems live here.

	Forward chaining	Backward chaining
Starts from	Known facts	The query (goal)
Style	Data-driven	Goal-driven
Does	Fire every rule whose premises hold	Find rules that conclude the goal; prove their premises
Risk	Derives lots of irrelevant facts	Loops; repeated sub-goals
Used in	ICU alarms, monitoring, CLIPS	Diagnosis, MYCIN, Prolog

09 Live lab 32–39 min

Forward vs backward chaining, live

Chaining engine Rules are AND-joins (circles). Click a bottom node to toggle it as a known fact.

Goal

Step0 / 8

Rules fired0

Agenda (queue) →

FeverEye painPlt < 100kAbdo pain

Agenda starts with the known facts: Fever, EyePain, LowPlt, AbdoPain.

10 Worked example 39–43 min

Worked example: forward chaining with an agenda

Given

Rules: R1: P ⇒ Q, R2: L ∧ M ⇒ P, R3: B ∧ L ⇒ M, R4: A ∧ P ⇒ L, R5: A ∧ B ⇒ L. Facts: A, B.

Find

Is Q entailed? Trace the agenda and the premise counts of every rule.

Pro tip

Draw it as an AND-OR graph first (the sim's textbook rule base). Arcs across the edges into a rule mean AND; two rules into the same node mean OR.

Method: PL-FC-ENTAILS, Russell & Norvig “Logical Agents”

Solution

Predict the answer first. Then reveal one step at a time.

11 Your turn 43–46 min

Your turn · 2: Feluda chains backward

2 Exam CQ

Feluda's rule book:

R1: Motive ∧ Opportunity ⇒ Suspect
R2: AtScene ⇒ Opportunity
R3: NoAlibi ⇒ Opportunity
R4: Inherits ⇒ Motive
R5: Suspect ∧ Fingerprints ⇒ Arrest

Facts: Inherits, NoAlibi, Fingerprints. Backward-chain the query Arrest. Show the goal stack, where it backtracks, and count rules tried and fired.

Work it out first.
Press Solve when the class has an answer.

12 Concept 46–50 min

First-order logic: objects, relations, “for all”

Propositional logic needs a new symbol for every patient: Dengue_Rahim, Dengue_Karim… FOL talks about objects and their relations.

Constants	Rahim, Dhaka, AedesAegypti
Predicates	$\text{Patient}(x),\ \text{Lives}(x, \text{Dhaka})$
Functions	$\text{Mother}(x),\ \text{Platelets}(x)$ (return an object)
Quantifiers	$\forall x$ for all, $\exists x$ there exists

✓ $\forall x\ \text{Dengue}(x) \Rightarrow \text{Fever}(x)$

∀ goes with ⇒. “For everything: if it has dengue, then fever.”

✓ $\exists x\ \text{Patient}(x) \land \text{Malaria}(x)$

∃ goes with ∧. “Something is a patient and has malaria.”

≠ $\forall x\,\exists y\ \text{Treats}(y,x) \;\;\text{vs}\;\; \exists y\,\forall x\ \text{Treats}(y,x)$

Order matters: “everyone has a doctor” vs “one doctor treats everyone”.

\lnot\forall x\,P(x) \equiv \exists x\,\lnot P(x)

13 Think deeper 50–52 min

Critical thinking · the smart-student trap

3 Trap

A student translates “All students are smart” and “Some student is smart” as:

\text{(a)}\ \ \forall x\ \text{Student}(x) \land \text{Smart}(x)

\text{(b)}\ \ \exists x\ \text{Student}(x) \Rightarrow \text{Smart}(x)

What does each sentence actually say? Fix both.

Work it out first.
Press Solve when the class has an answer.

14 Your turn 52–56 min

Your turn · 3: English to FOL

4 Exam CQ

Translate into first-order logic:

Every dengue patient has a fever.
Some patient in Dhaka has malaria.
No mosquito that carries the dengue virus is harmless.
Every patient is treated by some doctor.

Work it out first.
Press Solve when the class has an answer.

15 Concept 56–58 min

Unification: making a rule fit a fact

Generalized modus ponens lifts modus ponens to FOL: find a substitution θ that makes the rule's premises match the facts.

Rule $\forall x\ \text{Mosquito}(x) \land \text{Infected}(x) \Rightarrow \text{Risky}(x)$

Facts $\text{Mosquito}(M_7),\ \ \text{Infected}(M_7)$

Unify $\theta = \{x/M_7\}$

Conclude $\text{SUBST}(\theta, \text{Risky}(x)) = \text{Risky}(M_7)$

UNIFY returns the most general unifier (MGU): the substitution that commits to as little as possible.

p	q	UNIFY(p, q)
Treats(Rahman, x)	Treats(Rahman, Karim)	$\{x/\text{Karim}\}$
Treats(Rahman, x)	Treats(y, Mother(y))	$\{y/\text{Rahman},\ x/\text{Mother}(\text{Rahman})\}$
Treats(Rahman, x)	Treats(x, Karim)	fail: x can't be both. Rename apart (x → z) and it works: $\{z/\text{Rahman},\ x/\text{Karim}\}$
Treats(y, y)	Treats(Rahman, Karim)	fail

16 Concept 58–61 min

Anatomy of an expert system

Inference engine. The reasoning part: matches rules against facts and decides which to fire next (forward or backward chaining, conflict resolution, certainty-factor arithmetic). Domain-independent.

An expert system captures a specialist's know-how as rules so non-specialists get expert-level advice, with reasons.

Domain expert: knows the field. Knowledge engineer: turns that into rules and tests them.

Click a block to see what it does.

17 Concept 61–63 min

Inside the shell: CLIPS, semantic nets, frames

(deftemplate patient              ; the shape of a fact
   (slot name)
   (slot fever (default no))
   (slot platelets (type NUMBER)))

(defrule dengue-suspect                ; IF ... THEN
   (patient (name ?n) (fever yes)
            (platelets ?p&:(< ?p 100000)))
   =>
   (assert (suspect ?n dengue))
   (printout t ?n ": suspect dengue, order NS1" crlf))

(assert (patient (name Rahim) (fever yes) (platelets 85000)))
(run)
; output → Rahim: suspect dengue, order NS1

Facts live in working memory; rules pattern-match them; => separates IF from THEN. CLIPS chains forward.

Frame: Dengue

is-aViral fever

vectorAedes aegypti

incubation4–10 days

plateletslow (default)

18 Live lab 63–68 min

MYCIN in miniature: certainty factors

Rule firing

CF = CF_{\text{rule}} \times \min(CF_{\text{premises}})

Two positive CFs, same conclusion

CF = CF_1 + CF_2\,(1 - CF_1)

Threshold

A premise counts only if its CF > 0.2

Mini-MYCIN: fever consult Answer yes / no / unknown with a confidence. Ask it WHY and HOW.

⚠ Teaching toy with made-up rule strengths. Not medical advice; real triage follows national guidelines and a clinician.

Question 1

Fever of 38.5 °C or more?

How sure is the answer? 1.0

Conclusions (certainty factor)

Dengue

0.00

Malaria

0.00

Typhoid

0.00

Reasoning trace

Nothing yet. Answer the first question.

19 Worked example 68–71 min

Worked example: combining certainty

Given

Evidence CFs: fever 0.9, eye pain 0.7, platelets < 100k 0.8, rash 0.5, monsoon 1.0. Rules: D1: fever ∧ eye pain ⇒ dengue (0.4); D2: fever ∧ low platelets ⇒ dengue (0.6); D3: rash ∧ monsoon ⇒ dengue (0.3).

Find

The certainty factor for dengue after all three rules fire.

Method: MYCIN / EMYCIN certainty factors, Patterson's chapter on uncertainty in expert systems

Solution

Predict the answer first. Then reveal one step at a time.

20 Think deeper 71–74 min

Critical thinking · brittle experts, fluent LLMs

Think deeper

Expert systems boomed in the 1980s and then faded. Why did they become brittle?

Argue it in pairs for two minutes. There may be more than one defensible answer.

Think deeper

Why might an LLM plus explicit rules or probabilities be safer in medicine than an LLM alone?

Argue it in pairs for two minutes. There may be more than one defensible answer.

21 Real world 74–77 min

From MYCIN to dengue season in Dhaka

MYCIN (Stanford, 1970s) recommended antibiotics for blood infections using a few hundred backward-chaining rules with certainty factors. In blinded evaluations its advice was rated about as good as infectious-disease specialists'. It was never used on real patients: typing in every answer took too long, and nobody knew who would be liable.

Today its descendants are clinical decision support inside hospital record systems: drug-interaction alerts, sepsis warnings, dosing checks. Their big problem is alert fatigue: too many rules firing, so clinicians click “ignore”.

BME corner

Bangladesh's 2023 dengue season was its worst on record, with over 300,000 hospital admissions. Triage rules like today's (fever + warning signs ⇒ admit) are what a clinic app or a hospital's intake form encodes, so a junior doctor at 3 am applies the same logic as the national guideline.

From our lab

mHealth Lab angle: explicit rules and probabilities give you something you can check against local data. That is the design idea behind combining Bayesian reasoning with an LLM in mLabLLM.

22 Pop quiz 77–79 min

Pop quiz

Score 0

Question 1 / 5

KB ⊨ α means…

23 Recap 79–80 min

Three things to remember

01

KB ⊨ α: α holds in every model of the KB. Check models (2ⁿ) or prove with sound rules; Horn KBs let forward/backward chaining do it in linear time.

02

FOL adds objects, predicates, functions and quantifiers. ∀ with ⇒, ∃ with ∧. Unification lets one rule serve every patient.

03

Expert system = knowledge base + inference engine + explanation. MYCIN's CFs: × min for AND, CF₁ + CF₂(1 − CF₁) to combine.

HW Before next class

Evidence: fever 1.0, cyclic chills 0.6, recent Bandarban trip 0.9. Rules M1: fever ∧ chills ⇒ malaria (0.4); M2: chills ∧ hill trip ⇒ malaria (0.7). Find CF(malaria), and say which piece of evidence to firm up first.

Work it out first.
Press Solve when the class has an answer.

R	B	V	KB1	KB2	KB3	KB	α
F	F	F	·	·	·	·	·
F	F	T	·	·	·	·	·
F	T	F	·	·	·	·	·
F	T	T	·	·	·	·	·
T	F	F	·	·	·	·	·
T	F	T	·	·	·	·	·
T	T	F	·	·	·	·	·
T	T	T	·	·	·	·	·

R	B	V	KB1	KB2	KB3	KB	α
F	F	F	·	·	·	·	·
F	F	T	·	·	·	·	·
F	T	F	·	·	·	·	·
F	T	T	·	·	·	·	·
T	F	F	·	·	·	·	·
T	F	T	·	·	·	·	·
T	T	F	·	·	·	·	·
T	T	T	·	·	·	·	·

R	B	V	KB1	KB2	KB3	KB	α
F	F	F	·	·	·	·	·
F	F	T	·	·	·	·	·
F	T	F	·	·	·	·	·
F	T	T	·	·	·	·	·
T	F	F	·	·	·	·	·
T	F	T	·	·	·	·	·
T	T	F	·	·	·	·	·
T	T	T	·	·	·	·	·