Knowledge Representation & Logic: FOL, Rules, Semantics & Proofs

TAKEAWAYS:

• First-Order Logic (FOL) uses predicates, quantifiers (∀, ∃), and functions to represent complex relationships (e.g., Parent(X,Y) means "X is a parent of Y").
• Semantic networks visualize knowledge as nodes (concepts) and edges (relations), making inheritance and hierarchical reasoning intuitive.
• Production rules (IF-THEN) model conditional logic, used in rule-based systems like loan approvals or medical diagnosis.
• Logical inference (forward/backward chaining) derives new facts from existing ones—backward chaining is goal-driven (e.g., proving "Can I take this loan?").
• Knowledge bases combine FOL, rules, and semantics to enable AI agents to reason under uncertainty (later in Unit 6).
• Frame problems (e.g., "How does an agent know what doesn’t change?") highlight limits of classical logic in dynamic worlds.

1. Why Represent Knowledge?

AI agents need to store, organize, and reason about the world. Poor representation leads to:

• Brittleness: Small changes break the system (e.g., a rule-based chatbot failing on typos).
• Incompleteness: Missing edge cases (e.g., a loan system rejecting valid applicants).
• Inefficiency: Slow reasoning (e.g., a game AI recalculating moves from scratch).

Real-world analogy: Imagine eSewa’s bill payment system. It must represent:

• "User X has account Y with balance Z" (FOL: Balance(X,Y,Z)).
• "If balance ≥ payment, deduct and send receipt" (rule: IF Balance(X,Y,Z) ≥ P THEN Deduct(X,Y,P)).
• "If payment fails, notify user" (exception handling).

2. First-Order Logic (FOL): The Language of AI

FOL extends propositional logic (true/false statements) by adding:

• Predicates: Properties (e.g., Parent(X,Y) = "X is a parent of Y").
• Functions: Named computations (e.g., Salary(EmployeeID)).
• Quantifiers: Universal (∀) and existential (∃) statements.

Syntax Breakdown

Worked Example: Family Tree in FOL

Scenario: Represent relationships in a Nepali family to answer: "Is ‘Raju’ a brother of ‘Sita’?"

1. Define predicates:

   • Parent(X,Y): X is a parent of Y.
   • Male(X): X is male.
   • Female(X): X is female.
   • Sibling(X,Y): X and Y are siblings.

2. Encode facts:

   Parent("Ram", "Raju") ∧ Parent("Sita", "Raju")  // Ram and Sita are Raju’s parents
   Male("Raju") ∧ Female("Sita") ∧ Male("Ram")     // Genders
   ∀x∀y (Parent(x,"Raju") ∧ Parent(y,"Raju") → Sibling(x,y))
   

   Translation: "If X and Y are both parents of Raju, then X and Y are siblings."

3. Query: Is Raju a brother of Sita?

   • FOL query: ∃x (Sibling("Raju",x) ∧ Female(x))
   • Answer: No, because Sibling("Raju","Sita") is false (they are parent-child, not siblings).

Visual: Family Tree as a Semantic Network

Why the red edge? Siblings must share both parents. Here, Raju and Sita share only one parent (Ram), so they are not siblings.

3. Semantic Networks: Visualizing Knowledge

Semantic networks represent knowledge as nodes (concepts) and labeled edges (relations). They solve:

• Hierarchical reasoning (e.g., "All birds can fly" → "Tweety can fly").
• Default inheritance (e.g., "Penguins are birds but cannot fly").

Example: Nepali Traffic Rules

Knowledge Base:

• Vehicle(X) → HasLicense(X)
• Motorcycle(X) → Vehicle(X)
• Bicycle(X) → ¬HasEngine(X)
• DefaultRule: Vehicle(X) → CanDriveOnRoad(X)

Query: Can a bicycle drive on a road?

• Answer: No, because Bicycle(X) → ¬HasEngine(X) overrides the default.

Visual: Traffic Rule Hierarchy

graph TD
    A["Vehicle"] -->|"isa"| B["Motorcycle"]
    A -->|"isa"| C["Bicycle"]
    A -->|"rule"| D["CanDriveOnRoad"]
    C -->|"exception"| E["¬HasEngine"]

Key Idea: Exceptions (like bicycles) are marked explicitly.

4. Production Rules: IF-THEN Logic

Rules are conditional statements used in:

• Expert systems (e.g., medical diagnosis).
• Game AI (e.g., "If enemy is weak, attack").
• Chatbots (e.g., "If user says ‘help’, suggest options").

Syntax

IF <condition> THEN <action>

Example: Loan approval system (like NMB Bank):

IF (Income(X) ≥ 50000 ∧ CreditScore(X) ≥ 650 ∧ LoanAmount ≤ 0.3 * Income(X))
THEN ApproveLoan(X, LoanAmount)
ELSE RejectLoan(X, "Insufficient income or credit")

Forward vs. Backward Chaining

Worked Example: Pathao Driver Eligibility Rules:

1. IF HasLicense(X) ∧ Vehicle(X) ∧ ¬CriminalRecord(X) THEN EligibleDriver(X)
2. IF EligibleDriver(X) ∧ Request(Y) THEN AssignTrip(X,Y)

Facts:

• HasLicense("Sita"), Vehicle("Bike123"), ¬CriminalRecord("Sita")
• Request("Trip456")

Query: Can Sita take Trip456?

• Backward chaining:
  1. Goal: AssignTrip("Sita","Trip456") → Need EligibleDriver("Sita").
  2. Check EligibleDriver("Sita") → Need HasLicense("Sita") ∧ Vehicle("Bike123") ∧ ¬CriminalRecord("Sita").
  3. All true → AssignTrip("Sita","Trip456") succeeds.

5. Logical Inference: Deriving New Facts

Inference engines apply rules to deduce conclusions. Two key methods:

A. Resolution Refutation (Proof by Contradiction)

1. Assume the negation of the goal is true.
2. Use rules to derive a contradiction.
3. If contradiction found, the goal is true.

Example: Prove "All humans are mortal" (∀x (Human(x) → Mortal(x))).

• Goal: Human("Socrates") → Mortal("Socrates")
• Assume ¬Goal: Human("Socrates") ∧ ¬Mortal("Socrates")
• Add rule: Human(x) → Mortal(x)
• Resolve: Contradiction (Mortal("Socrates") vs. ¬Mortal("Socrates")) → Goal is true.

B. Forward Chaining (Data-Driven)

Start with facts, apply rules to generate new facts until no more rules fire.

Example: NTC’s Traffic Fine System Facts:

• Speeding("Car123", 80) (speed limit = 60 km/h)
• Rule: IF Speeding(X, S) ∧ S > Limit THEN IssueFine(X, Amount)

Steps:

1. Apply rule → IssueFine("Car123", 5000)
2. New fact: PaidFine("Car123", 5000) (if user pays).

6. Knowledge Representation Techniques Compared

7. Real-World Applications

A. eSewa’s Bill Payment Logic

• FOL: Paid(X, Y, Amount) = "User X paid bill Y for Amount."
• Rule: IF Balance(X) ≥ Amount ∧ ValidBill(Y) THEN ProcessPayment(X,Y,Amount)
• Semantic Network: Bills → Users → Banks → Payment Status.

B. Daraz’s Order Fulfillment

• Frame Problem: "What stays the same when an order is processed?"
  • FOL: OrderStatus(X) = "Pending" → IF Stock(Y) ≥ Quantity THEN UpdateStatus(X, "Shipped")
  • Issue: What if stock changes mid-processing? (Handled by Unit 6: Uncertainty.)

C. Ncell’s Customer Support Chatbot

• Production Rules:
  • IF UserSays("recharge") THEN Ask("Amount?")
  • IF UserSays("complaint") THEN RouteToAgent()
• Semantic Network: User → Intent → Action → Response.

D. NEPSE Stock Analysis (Hypothetical)

• FOL:
  • Trend(X, "Up") if Price(X,t) > Price(X,t-1).
  • Rule: IF Trend(X, "Up") ∧ Volume(X) > 1000 THEN RecommendBuy(X)
• Visual: Stock price as a time-series graph with rules overlaid.

8. Limitations and Challenges

1. Frame Problem: How does an agent know what doesn’t change?
   • Example: A robot moving a block assumes other blocks stay put unless acted upon.
2. Combinatorial Explosion: Too many rules/facts slow reasoning.
   • Example: A game AI with 10^6 possible moves.
3. Default Reasoning: How to handle exceptions?
   • Example: "Birds fly" but penguins don’t.

9. Exam Tip

What Examiners Look For:

1. Correct Syntax: Use ∀, ∃, →, ∧ properly. Example:
   • ❌ Wrong: Parent(X,Y) = True (predicates are not assignments).
   • ✅ Correct: Parent("Ram", "Sita").
2. Logical Equivalence: Know when to use universal instantiation vs. existential generalization.
   • Example: From ∀x P(x) → P(a) (instantiation), but not the reverse.
3. Rule Applications: Show step-by-step inference. Example:

   Given: ∀x (Student(x) → PaysFee(x))
   Fact:   Student("Raju")
   ⊢       PaysFee("Raju")  // Universal instantiation
   

4. Real-World Mapping: Link FOL to systems like eSewa or bank loans. Example:
   • "How would you represent ‘Khalti users can transfer money if verified’ in FOL?" Answer: IF Verified(X) ∧ User(X) THEN CanTransfer(X, Amount)
5. Diagrams: Draw semantic networks or rule chains for 5+ marks. Example:

6. Common Pitfalls:
   • Confusing ∀ and ∃.
   • Forgetting to negate goals in resolution.
   • Overlooking exceptions in semantic networks.

Sample Exam Question: *"Represent the following in FOL and use backward chaining to prove whether ‘Sita can drive a scooter’:

• Rules: (1) IF License(X, "Scooter") THEN CanDrive(X, "Scooter")
• Facts: License("Sita", "Car")"* Answer:

1. FOL: License(X,Y) → CanDrive(X,Y)
2. Query: CanDrive("Sita", "Scooter")
3. Backward Chaining:
   • Need License("Sita", "Scooter") → But fact is License("Sita", "Car") → False.

10. Practice Problems

1. FOL Translation:
   • "Every employee in TU gets a salary." Answer: ∀x (Employee(x, "TU") → GetsSalary(x))
2. Rule Application:
   • Given:
     • IF Raining THEN BringUmbrella
     • IF Cold THEN WearJacket
     • Facts: Raining ∧ Cold Derive: BringUmbrella ∧ WearJacket (forward chaining).
3. Semantic Network: Draw the hierarchy for: Animal → Bird → Penguin → Flightless.