Knowledge Representation & Logic: Facts, Rules & Reasoning

TAKEAWAYS:

• Knowledge representation is the bridge between raw data and AI reasoning, using structures like predicates, frames, and semantic networks to model facts and relationships.
• Propositional logic uses truth tables and Boolean operators to reason about simple statements, while predicate logic extends this to quantify over objects (e.g., "All humans are mortal").
• Inference rules (modus ponens, resolution) let AI systems deduce new facts from existing ones—forward chaining starts with facts, backward chaining starts with goals.
• Frame-based systems (slots, facets) and semantic networks (nodes/arcs) handle complex, hierarchical knowledge like family trees or medical diagnoses.
• Uncertainty in logic is addressed via fuzzy logic (degrees of truth) or probabilistic logic, but pure logic assumes binary truth values.
• Applications span from eSewa’s transaction validation (rule-based logic) to medical diagnosis systems (frame-based reasoning).

Core Concepts: Representing Knowledge

1. Propositional Logic: Statements and Truth

Propositional logic deals with propositional variables (e.g., P: "It is raining") and logical operators (¬, ∧, ∨, →, ↔). A well-formed formula (WFF) combines these to express complex statements.

How it works:

• Assign truth values (True/False) to propositions.
• Use truth tables to evaluate compound statements.
• Example: If P: "The bus is late" and Q: "I will be late for class", then P → Q ("If the bus is late, then I will be late") is only False when P is True and Q is False.

graph TD
    A["P: Bus is late"] -->|"True"| B["Q: I'm late"]
    A -->|"False"| C["Q: I'm late"]
    B["Q: True"] --> D["P→Q: True"]
    C["Q: False"] --> E["P→Q: False"]

Worked Example: eSewa Transaction Rules eSewa uses propositional logic to validate transactions. Suppose:

• P: "User has sufficient balance."
• Q: "Transaction amount ≤ daily limit."
• R: "OTP verified." The rule P ∧ Q ∧ R → Approve must hold for a transaction to succeed. Trace:

  P (Balance)	Q (Limit)	R (OTP)	P∧Q∧R	Approve?
  True	True	True	True	Yes
  True	False	True	False	No

Limitations:

• Cannot express relationships between objects (e.g., "John owns a car").
• Scales poorly for complex domains.

2. Predicate Logic: Quantifiers and Relationships

Predicate logic extends propositional logic by introducing:

• Predicates: Properties or relations (e.g., Owns(X, Y): "X owns Y").
• Terms: Constants (john), variables (X), and functions (Parent(X)).
• Quantifiers:
  • Universal (∀): "For all X, P(X) holds."
  • Existential (∃): "There exists an X such that P(X) holds."

Syntax:

• ∀x (Human(x) → Mortal(x)) ("All humans are mortal.")
• ∃y (Owns(john, y) ∧ Car(y)) ("John owns a car.")

Worked Example: Family Tree (Nepali Context) Model a family with predicates:

• Parent(X, Y): "X is a parent of Y."
• Male(X), Female(X). Facts:

1. Parent(ram, shyam)
2. Parent(ram, gita)
3. Male(ram)
4. Female(gita) Query: Is there a male child of ram? Answer: Use ∃x (Parent(ram, x) ∧ Male(x)). Here, x = shyam satisfies this.

Advantages over Propositional Logic:

• Handles objects and relationships (e.g., "X is taller than Y").
• More expressive for real-world domains.

3. Inference Rules: Deriving New Knowledge

Inference rules let AI systems derive conclusions from existing facts. Two key approaches:

A. Forward Chaining (Data-Driven)

Start with facts and apply rules to infer new facts until no more can be added. Example: Medical Diagnosis Facts:

• Fever(patient1)
• Cough(patient1) Rules:

1. Fever(X) ∧ Cough(X) → Possible(Flu(X))
2. Possible(Flu(X)) ∧ Age(X, >65) → Severe(Flu(X)) Steps:
3. Apply Rule 1: Possible(Flu(patient1)) is inferred.
4. If Age(patient1, 70) is known, apply Rule 2: Severe(Flu(patient1)).

B. Backward Chaining (Goal-Driven)

Start with a hypothesis and work backward to verify it. Example: Loan Approval (Bank Scenario) Goal: Approve(Loan(X)) Rules:

1. Approve(Loan(X)) ← Income(X, ≥25000) ∧ CreditScore(X, ≥650)
2. Income(john, 30000)
3. CreditScore(john, 700) Steps:
4. To prove Approve(Loan(john)), check Income(john, ≥25000) and CreditScore(john, ≥650).
5. Both conditions are satisfied → Goal achieved.

Comparison Table:

4. Frame-Based Representation

Frames model stereotypical situations (e.g., "Restaurant") with:

• Slots: Attributes (e.g., Menu, Location).
• Facets: Slot properties (e.g., Default, AllowedValues).
• Default Values: Pre-filled assumptions.

Example: Nepali Restaurant Frame

classDiagram
    class Restaurant {
        +Name: String
        +Menu: List[Dish]
        +Location: String
        +OpeningHours: TimeRange
        +Specialty: String
    }
    class Dish {
        +Name: String
        +Price: Number
        +Ingredients: List[String]
    }
    Restaurant "1" --> "many" Dish

Worked Example: Pathao Driver App Pathao uses frame-based logic to represent:

• Driver Frame:
  • Slot: CurrentLocation, Facets: Default = "Home", AllowedValues = [GPS_coordinates].
  • Slot: VehicleType, Facets: Default = "Motorcycle", AllowedValues = ["Bike", "Car"].
• Rule: If VehicleType = "Car" and PassengerCount > 4, then RejectTrip().

Advantages:

• Handles default assumptions (e.g., "Restaurants serve food").
• Hierarchical inheritance: A "Thakali Restaurant" inherits from "Restaurant" but adds Specialty = "Dhindo".
• Used in expert systems (e.g., medical diagnosis, legal advice).

5. Semantic Networks

A graph-based knowledge representation where:

• Nodes = Objects/concepts (e.g., "Person", "Car").
• Arcs = Relationships (e.g., IS-A, HAS-PART, OWNED-BY).

Example: Nepali Family Tree

Worked Example: NTC Traffic Route Planning NTC uses semantic networks to model:

• Nodes: Intersection, Road, TrafficLight.
• Arcs: CONNECTS, REGULATES. Query: Find all roads from Thapathali to Kathmandu Durbar Square. Solution: Traverse arcs labeled CONNECTS between nodes.

Advantages:

• Intuitive for hierarchical relationships (e.g., "Animal → Mammal → Dog").
• Efficient for inheritance (e.g., "Dog" inherits Barks() from "Animal").
• Used in NLP (wordnet), question answering, and ontologies.

6. Logic Programming: Prolog Basics

Prolog (Programming in Logic) is a language for declarative logic programming. It uses:

• Facts: parent(ram, shyam).
• Rules: grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
• Queries: ?- grandparent(ram, Z). → Returns Z = gita.

Worked Example: Khalti Transaction Validation Model Khalti’s transaction rules in Prolog:

% Facts
balance(khalti_user1, 5000).
transaction_amount(1000).
daily_limit(5000).
otp_verified(true).

% Rules
valid_transaction(User) :-
    balance(User, Amount),
    transaction_amount(Amount),
    Amount =< daily_limit,
    otp_verified(true).

% Query
?- valid_transaction(khalti_user1).  % Returns true

Key Features:

• Pattern matching replaces loops.
• Backtracking explores all possible solutions.
• Used in symbolic AI, expert systems, and NLP.

7. Handling Uncertainty: Fuzzy Logic

Pure logic assumes binary truth values, but real-world data is often uncertain. Fuzzy logic assigns degrees of truth (e.g., 0.7 for "likely").

Example: Traffic Congestion Prediction

• Rule: IF Speed < 20 km/h THEN Congestion = High (0.9).
• Fuzzy Sets:
  • Speed: {Low: 0-10, Medium: 10-30, High: 30-50}.
  • Congestion: {Low: 0-0.3, Medium: 0.3-0.7, High: 0.7-1.0}.

Worked Example: Ncell Network Signal Strength Ncell uses fuzzy logic to classify signal strength:

• Input: SignalStrength = 45%.
• Membership Functions:
  • Weak: 0-30% (membership = 0.5 at 45%).
  • Medium: 30-70% (membership = 0.75 at 45%).
  • Strong: 70-100% (membership = 0).
• Output: "Medium signal (0.75)".

Advantages:

• Handles vague concepts (e.g., "tall", "expensive").
• Used in control systems (e.g., washing machines, anti-lock brakes).

In the Real World

1. eSewa Transaction Validation

   • Idea: Propositional logic + rule-based inference.
   • How: Transactions are approved only if P ∧ Q ∧ R holds (balance, limit, OTP). If any condition fails, the transaction is rejected.
   • Example: A user with Balance = 4500, DailyLimit = 5000, and InvalidOTP will see: P ∧ Q ∧ ¬R → Reject.

2. Pathao Driver Matching

   • Idea: Frame-based representation + semantic networks.
   • How: Driver frames include VehicleType, Location, and Availability. The system matches passengers to drivers using CONNECTS arcs in a road network graph.
   • Example: A passenger at Thapathali requests a car. Pathao queries the semantic network for all Car nodes CONNECTED to Thapathali with Availability = True.

3. Nepal Stock Exchange (NEPSE) Risk Assessment

   • Idea: Predicate logic + fuzzy logic.
   • How: NEPSE uses rules like: ∀x (Price(x) > 1.5 × AvgPrice(x) → Risk(x, High)). Fuzzy logic adjusts "High" risk based on volatility (e.g., Risk = 0.8 if volatility is 0.7).
   • Example: If StockA price = 2000 and AvgPrice = 1200, then Risk(StockA, High) is triggered. If volatility is 0.6, the fuzzy system might classify it as Risk = 0.75.

Exam Tip

This unit is heavily tested on:

1. Definitions and Comparisons:

   • Distinguish between propositional and predicate logic (objects vs. no objects).
   • Compare forward vs. backward chaining (data-driven vs. goal-driven).
   • Explain frames vs. semantic networks (slots vs. arcs).

2. Worked Examples:

   • Propositional Logic: Given a truth table, evaluate a compound statement (e.g., (P ∨ Q) → ¬R).
   • Predicate Logic: Write predicates for a scenario (e.g., "A student passes if they attend ≥75% classes and score ≥40%").
   • Inference: Show step-by-step forward/backward chaining for a mini-domain (e.g., "If it rains, roads are slippery. If roads are slippery, accidents increase.").

3. Applications:

   • Link frames to real systems (e.g., "How would you model a bank loan application?").
   • Describe semantic networks for a given use case (e.g., "Design a network for a university course catalog").

4. Prolog Queries:

   • Given a set of facts/rules, write a query and predict the output (e.g., "Is grandparent(ram, X) true?").

Common Pitfalls:

• Forgetting to negate in backward chaining (e.g., ¬Goal).
• Misapplying quantifiers (e.g., confusing ∀ and ∃).
• Overlooking default values in frames (e.g., assuming all slots are filled).

High-Score Strategy:

• Draw diagrams for semantic networks/frames (label nodes/arcs clearly).
• Show traces for inference steps (number each rule application).
• Relate to Nepal: Use examples from eSewa, NTC, or local businesses to explain abstract concepts.