Knowledge Representation & Logic: Facts, Rules & Reasoning

TAKEAWAYS:

• Knowledge representation is the bridge between raw data and AI decision-making, using structures like predicates, frames, and semantic networks to model facts and relationships.
• Logical inference (forward/backward chaining) lets AI "reason" by applying rules to known facts, but requires careful handling of contradictions and incomplete data.
• Predicate calculus (first-order logic) is the most expressive formalism for representing complex relationships (e.g., "X is a parent of Y"), but computationally expensive for large domains.
• Semantic networks and frames excel at hierarchical knowledge (e.g., "a car is-a vehicle has-parts engine"), while production rules (IF-THEN) are ideal for expert systems like medical diagnosis.
• Resolution refutation is the core algorithm for proving logical contradictions, but only works in clausal form (CNF).
• Real-world AI (e.g., eSewa’s fraud detection, Ncell’s customer service bots) relies on these techniques to interpret user inputs, infer intentions, and generate responses.

1. Why Represent Knowledge?

AI systems need to store and manipulate knowledge about the world. Without proper representation:

• They cannot understand user queries (e.g., "Find me a red car under $50,000").
• They cannot make decisions (e.g., "Should this loan be approved?").
• They cannot learn from data (e.g., "This transaction looks like fraud").

Real-world analogy: When you use Khalti’s "Pay Anyone" feature, the app must represent:

• Your account balance (fact: balance(KhaltiUser123, 4500)).
• The recipient’s details (fact: has_account(Recipient456, "John Doe")).
• Transaction rules (rule: IF (balance(Sender, Amount) ≥ Amount) THEN deduct(Amount, Sender)). Without these representations, Khalti couldn’t process your request.

2. Knowledge Representation Formalisms

Different problems need different structures. Here’s how to choose:

A. Propositional Logic (PL)

• What it is: Statements that are either true or false (no variables). Example: RainingToday, LaptopPrice > 50000, Not(ExamPassed).
• How it works:
  • Connectives: ¬ (NOT), ∧ (AND), ∨ (OR), → (IMPLIES), ↔ (IFF).
  • Truth tables: Determine validity of compound statements.
• Limitations:
  • Cannot express relationships (e.g., "X is taller than Y").
  • Exponential blowup: For n propositions, you need $2^n$ possible worlds.

Worked Example: Traffic Light Control Assume a simple intersection with:

• Green(NorthSouth), Green(EastWest)
• Rules:
  1. Green(NorthSouth) → ¬Green(EastWest)
  2. ¬Green(NorthSouth) → Green(EastWest)

Question: Is Green(NorthSouth) ∧ Green(EastWest) possible? Solution: Use a truth table to check all combinations. The answer is false—they cannot both be true.

graph TD
    A["Green(NorthSouth)"] -->|"True"| B["Green(EastWest) = False"]
    A -->|"False"| C["Green(EastWest) = True"]
    B --> D["Valid"]
    C --> D

B. First-Order Predicate Logic (FOL)

• What it is: Extends PL with variables, predicates, and quantifiers.
  • Predicates: Parent(X, Y) ("X is a parent of Y").
  • Functions: Salary(EmployeeID).
  • Quantifiers: ∀ (for all), ∃ (there exists).
• Example: ∀x (Person(x) → ∃y (Parent(y, x))) ("Every person has at least one parent.")

Real-world use in Nepal: NEPSE’s stock trading system uses FOL to represent:

• Holds(Trader123, StockNTC) ("Trader123 owns NTC shares").
• ∀x (Holds(x, StockY) ∧ Price(StockY) > 1000 → CanSell(x, StockY)) ("If you own a stock priced > Rs. 1000, you can sell it.")

Worked Example: Family Tree Given:

1. Parent(Alice, Bob)
2. Parent(Bob, Charlie)
3. ∀x ∀y (Parent(x, y) → Older(x, y))

Question: Is Older(Alice, Charlie) true? Solution: By universal instantiation (∀ rule applies to all), we substitute x = Alice, y = Charlie:

• From rule 3: Parent(Alice, Charlie) → Older(Alice, Charlie).
• From rule 1 and 2: Parent(Alice, Bob) ∧ Parent(Bob, Charlie) does not directly imply Parent(Alice, Charlie). Answer: No, unless we add a transitive closure rule: ∀x ∀y ∀z (Parent(x, y) ∧ Parent(y, z) → Parent(x, z)).

C. Production Rules (IF-THEN)

• What it is: A set of conditional statements (like expert system rules). Example: IF (Symptom(Fever) ∧ Symptom(Cough)) THEN Possible(Disease, Flu)
• How it works:
  • Forward chaining: Start with facts, apply rules to derive new facts.
  • Backward chaining: Start with a hypothesis, work backward to verify.

Real-world example: eSewa Fraud Detection eSewa uses rules like:

IF (TransactionAmount > 50000
    ∧ Location(Sender) ≠ Location(Recipient)
    ∧ TimeOfDay(Night)
    ∧ ¬Verified(Sender))
THEN FlagAsFraud(TransactionID)

Worked Example: Loan Approval Rules:

1. IF (Income(Applicant) > 50000 ∧ CreditScore(Applicant) > 650) THEN ApproveLoan(Applicant)
2. IF (LoanAmount > 2000000) THEN RequiresCollateral(Applicant)

Question: Can Applicant X (income = 60000, score = 600, loan = 1500000) get a loan? Solution:

• Apply backward chaining:
  1. Goal: ApproveLoan(X) → Check rule 1: Income(X) > 50000 (True), but CreditScore(X) = 600 < 650 → False.
  2. Alternative path: Maybe RequiresCollateral(X) → Check rule 2: LoanAmount(X) = 1500000 ≤ 2000000 → False. Answer: Rejected.

D. Frames and Semantic Networks

• Frames: Structured templates for objects with slots and default values. Example:

  Frame: Vehicle
    Slots: color, max_speed, fuel_type
    Defaults: color = "unknown", max_speed = 120
  

• Semantic Networks: Nodes = concepts, edges = relationships. Example:

  Animal ---(is-a)---> Mammal ---(has-part)---> Heart
  

Real-world use: Pathao’s Route Planning Pathao’s AI represents:

• Frame for "Route":
  • Slots: distance, traffic, estimated_time, tolls.
  • Default: traffic = "normal".
• Semantic network:

  Kathmandu ---(connected-by)---> Lalitpur ---(connected-by)---> Bhaktapur
  

Visual: Semantic Network for a Car

E. Comparison Table: When to Use Which

3. Logical Inference: How AI "Reasons"

Inference = deriving new facts from existing ones using rules.

stateDiagram-v2
  [*] --> Resolve
  Resolve --> Check: Clause 1
  Check --> Resolve: Subgoal
  Resolve --> Check: Clause 2
  Check --> Resolve: Subgoal
  Resolve --> [*]: Contradiction
  Resolve --> [*]: No Contradiction

A. Forward Chaining

• Process: Start with known facts, apply rules to generate new facts.
• Example: Medical diagnosis.
  • Facts: Fever(Patient1), Cough(Patient1)
  • Rule: IF Fever(X) ∧ Cough(X) THEN Possible(Flu, X)
  • New fact: Possible(Flu, Patient1)

Mermaid: Forward Chaining Pipeline

flowchart LR
    A["Facts: Fever, Cough"] --> B["Apply Rule 1"]
    B --> C["New Fact: Possible(Flu)"] --> D["Apply Rule 2"]
    D --> E["Conclusion: Prescribe Rest"]

B. Backward Chaining

• Process: Start with a hypothesis, verify preconditions.
• Example: Loan approval (as above).

C. Resolution Refutation

• What it is: A method to prove contradictions (i.e., "is this unsolvable?").
• Steps:
  1. Convert all statements to clausal form (CNF).
  2. Add the negation of the goal.
  3. Apply resolution to derive the empty clause (⊥).

Worked Example: Proving a Contradiction Given:

1. ∀x (Bird(x) → Flies(x)) ("All birds fly.")
2. Bird(Tweety)
3. ¬Flies(Tweety) ("Tweety does not fly.")

Question: Is this a contradiction? Solution:

1. Convert to CNF:
   • Rule 1: ¬Bird(x) ∨ Flies(x)
   • Rule 2: Bird(Tweety)
   • Rule 3: ¬Flies(Tweety)
2. Negate the goal (we want to prove inconsistency): Bird(Tweety) ∧ ¬Flies(Tweety)
3. Apply resolution:
   • Resolve Bird(Tweety) (from rule 2) with ¬Bird(x) ∨ Flies(x) → Flies(Tweety).
   • Now we have Flies(Tweety) and ¬Flies(Tweety) → Empty clause (⊥). Conclusion: Contradiction exists (Tweety cannot both fly and not fly under these rules).

4. Handling Uncertainty: Default Logic

Real-world knowledge is incomplete and uncertain. Solutions:

• Default rules: Assume something is true unless proven otherwise. Example: IF Bird(X) THEN Flies(X) [default] (But we know penguins are exceptions.)
• Certainty factors: Assign probabilities to rules (used in expert systems).

Real-world example: Daraz’s Order Fulfillment Daraz uses default logic for shipping:

DEFAULT: IF OrderStatus(Confirmed) THEN ShippingStatus(Processing)
EXCEPTION: IF OrderWeight > 10kg THEN ShippingStatus(ManualReview)

5. Real-World Applications in Nepal

6. Common Pitfalls and How to Avoid Them

1. Overloading a single formalism:
   • ❌ Using only propositional logic for a family tree.
   • ✅ Use predicate logic for relationships + frames for attributes.
2. Ignoring computational cost:
   • ❌ Using pure FOL for a large knowledge base (e.g., medical diagnosis).
   • ✅ Use production rules or semantic networks for efficiency.
3. Not handling exceptions:
   • ❌ Default rule: "All birds fly."
   • ✅ Add exceptions: IF Bird(X) ∧ Penguin(X) THEN ¬Flies(X).

7. Exam Tip: How to Score Full Marks

1. For definitions:

   • Always include examples and limitations.
   • Example:

     "Predicate logic extends propositional logic by adding variables and quantifiers (∀, ∃), allowing statements like Parent(X, Y). However, it suffers from the frame problem (how to represent what doesn’t change)."

2. For worked examples:

   • Show every step of inference (e.g., resolution refutation).
   • Use real-world analogies (e.g., "like eSewa’s fraud rules").

3. For comparisons:

   • Use tables (as above) to contrast formalisms.
   • Highlight trade-offs (e.g., expressiveness vs. computational cost).

4. For diagrams:

   • Semantic networks: Label edges clearly (e.g., "is-a", "has-part").
   • Resolution refutation: Show each resolution step leading to ⊥.
   • Frames: Draw slots and defaults explicitly.

5. Common exam questions:

   • "Convert the following to CNF: ∀x (P(x) → Q(x))." Answer: Original: ¬P(x) ∨ Q(x) (already in CNF).
   • "Use backward chaining to verify if Grandparent(Alice, Bob) is true given the rules." Answer:
     1. Goal: Grandparent(Alice, Bob).
     2. Rule: ∀x ∀y ∀z (Parent(x, y) ∧ Parent(y, z) → Grandparent(x, z)).
     3. Subgoals: Parent(Alice, ?), Parent(?, Bob).
     4. From facts: Parent(Alice, Carol), Parent(Carol, Bob) → True.

8. Practice Problems (Exam-Style)

1. Convert to CNF: ∃x (P(x) ∧ (Q(x) → R(x))) Hint: Use Skolemization and distribute implications.

2. Inference: Given:

   • ∀x (Student(x) → PaysFees(x))
   • Student(Ram) Prove: PaysFees(Ram) using universal instantiation.

3. Semantic Network: Draw a network for:

   • Dog (is-a Animal, has-part Tail, makes-sound Bark).
   • Puppy (is-a Dog, has-attribute Age < 1).

4. Resolution: Prove that ¬Q follows from:

   • P → Q
   • ¬P ∨ R
   • ¬R