Using FOL: Knowledge Engineering

Writing FOL Sentences

Facts (Ground Atoms)

Brother(Richard, John)
OnHead(Crown1, John)
King(John)

Rules (Universally Quantified Implications)

∀x,y Brother(x,y) → BrotherOf(y,x)              -- symmetry
∀x King(x) ∧ GreedyPerson(x) → Evil(x)           -- greedy kings are evil
∀x Person(x) → ∃y Heart(y) ∧ Has(x,y)            -- every person has a heart

Unique Names Assumption (UNA)

Different constants refer to different objects: Richard ≠ John

Without UNA, Richard and John might refer to the same person.

Closed World Assumption (CWA)

Anything not known to be true is false.

Under CWA: if Brother(John, Bill) is not in the KB, infer ¬Brother(John, Bill).

Open World Assumption (OWA): absence of information ≠ falsity. Used in description logics / ontologies (Web Ontology Language OWL).

Wumpus World in FOL

-- Percept axioms
∀t,s At(Agent,s,t) ∧ Breezy(s) → ∃s2 Adjacent(s,s2) ∧ Pit(s2)

-- Spatial axioms
∀s Adjacent(s, [1,1]) ↔ s=[1,2] ∨ s=[2,1]
...

-- Agent knowledge
∀t,s1,s2 At(Agent,s1,t) ∧ GoTo(s2,t) → At(Agent,s2,Succ(t))

The time argument t tracks state across timesteps — handles change in FOL.

The Electronic Circuit Domain

Knowledge engineering example:

-- Component type hierarchy
∀c XOR-gate(c) → Gate(c)
∀c Gate(c) → Component(c)

-- Functional specifications
∀c,t XOR-gate(c) ∧ Signal(In1(c),t)=0 ∧ Signal(In2(c),t)=1 → Signal(Out(c),t)=1
∀c,t XOR-gate(c) ∧ Signal(In1(c),t)=1 ∧ Signal(In2(c),t)=0 → Signal(Out(c),t)=1
∀c,t XOR-gate(c) ∧ Signal(In1(c),t)=Signal(In2(c),t) → Signal(Out(c),t)=0

Knowledge Engineering Process

  1. Identify the task — what questions will the KB answer?
  2. Assemble relevant knowledge — domain expert interviews, texts
  3. Decide vocabulary — predicates, functions, constants
  4. Encode the domain knowledge — write axioms and facts
  5. Encode the specific problem — ground facts about this instance
  6. Pose queries — ask the inference engine
  7. Debug — fix incorrect or missing axioms

Common pitfalls: - Wrong quantifier pairing (∀ with ∧, ∃ with →) - Forgetting the closed/open world distinction - Circularity in function definitions - Conflating objects with their names (use quoted strings for names)

Categories and Objects

FOL naturally expresses taxonomies:

∀x GoldenRetriever(x) → Dog(x)
∀x Dog(x) → Animal(x)
∀x Animal(x) → LivingThing(x)

This is the basis for Description Logic and OWL (Web Ontology Language), which restricts FOL to gain decidable inference.

Summary

FOL provides: - Expressivity: one rule captures what many propositional symbols require - Object-level reasoning: reasoning about individuals, not just propositions - Reusability: axioms generalize across instances

The price: undecidable inference (can always run forever) vs. propositional logic’s decidable (but exponential) inference.