Logical Foundations: Predicates, Propositional Logic, Rules & Reasoning

TAKEAWAYS:

• Propositional logic uses propositions (true/false statements) and connectives (AND, OR, NOT) to represent knowledge, while predicate logic extends this with quantifiers (∀, ∃) and predicates (properties of objects).
• Inference rules (Modus Ponens, Resolution) enable automated reasoning from logical statements, forming the core of knowledge-based systems.
• Horn clauses (a subset of predicate logic) are computationally efficient and widely used in expert systems like medical diagnosis tools.
• Real-world systems (e.g., eSewa’s fraud detection or Khalti’s transaction validation) rely on logical rules to enforce constraints and derive conclusions.
• Uncertainty handling in logic requires extensions like fuzzy logic or probabilistic reasoning (covered in Unit 9).
• Mastering symbolic representations and proof techniques (e.g., forward/backward chaining) is critical for exam questions on knowledge representation.

1. Propositional Logic: The Building Block

Propositional logic is the simplest form of formal logic, where knowledge is represented as propositions (statements that are either true or false) combined using logical connectives.

Key Components

• Propositions (Atomic Sentences): Simple statements like:

  • P: "It is raining."
  • Q: "The road is slippery."
  • R: "The bus is delayed." These are atomic (cannot be broken down further in propositional logic).

• Logical Connectives: Combine propositions to form complex statements:

  Symbol	Name	Example (P ∧ Q)	Meaning
  ∧	AND	"It is raining and the road is slippery."	True only if both P and Q are true.
  ∨	OR	"It is raining or the road is slippery."	True if at least one is true.
  ¬	NOT	"It is not raining."	Inverts the truth value.
  →	IMPLIES	"If it is raining, then the road is slippery."	False only if P is true and Q is false.
  ↔	IFF (if and only if)	"The bus is delayed if and only if it is raining."	True if both are true or both are false.

Truth Tables: Evaluating Propositions

Truth tables systematically evaluate the truth value of complex propositions based on their components. Example: Construct the truth table for (P ∧ Q) → R.

| P | Q | R | P ∧ Q | (P ∧ Q) → R |
|---|---|---|-------|------------|
| T | T | T |   T   |      T     |
| T | T | F |   T   |      F     |
| T | F | T |   F   |      T     |
| T | F | F |   F   |      T     |
| F | T | T |   F   |      T     |
| F | T | F |   F   |      T     |
| F | F | T |   F   |      T     |
| F | F | F |   F   |      T     |

Worked Example (Real-World Tie-In): eSewa’s Fraud Detection System eSewa uses propositional logic to flag suspicious transactions. Suppose:

• P: "User logged in from a new device."
• Q: "Transaction amount > Rs. 50,000."
• R: "Flag transaction as fraudulent."

The rule might be: (P ∧ Q) → R Trace:

1. If a user logs in from a new device (P = True) and makes a large transaction (Q = True), then R must be True (fraud alert).
2. If either P or Q is False, no alert is triggered.

2. Predicate Logic: Representing Relationships

Propositional logic is limited—it cannot express relationships between objects. Predicate logic extends this by introducing:

• Predicates: Properties or relationships (e.g., Parent(X, Y) means "X is a parent of Y").
• Terms: Objects or variables (e.g., ram, sita, John).
• Quantifiers: Universal (∀) and existential (∃).

Syntax of Predicate Logic

A well-formed formula (WFF) in predicate logic has the form:

[Quantifier] Predicate(term₁, term₂, ..., termₙ)

Examples:

1. ∀x Parent(x, ram) → "Everyone is a parent of Ram." (False, unless Ram is a god!)
2. ∃y Student(y) ∧ ∀x (Student(x) → Enrolled(x, "CACS458")) → "There exists a student who is enrolled in CACS458."
3. Likes(john, pizza) ∧ ¬Likes(john, broccoli) → "John likes pizza but not broccoli."

Worked Example: Daraz Order Fulfillment

Daraz’s warehouse system uses predicate logic to manage orders. Define:

• Ordered(Customer, Product, Quantity)
• InStock(Product, Quantity)
• Shipped(OrderID)

Rule: ∀x ∀y ∀z [(Ordered(x, y, z) ∧ InStock(y, w)) → ∃k Shipped(k)] Interpretation: "For all customers x, products y, and quantities z, if an order is placed and the product is in stock, then there exists a shipped order."

Trace for a Real Order:

1. Ordered("Alice", "Laptop", 1)
2. InStock("Laptop", 5)
3. Conclusion: ∃k Shipped(k) → The system generates a shipment ID k.

3. Rules and Inference: How Systems "Think"

Knowledge-based systems use rules (implications) and inference engines to derive new knowledge from existing facts.

flowchart TD
    A["Fever(Patient) ∧ Cough(Patient)"] -->|"Horn Clause Rule"| B["Flu(Patient)"]
    B --> C["Prescribe(Paracetamol)"]

Types of Rules

1. Horn Clauses: A subset of predicate logic with at most one positive literal. Form: A ∧ B ∧ ... → C Example (Medical Diagnosis): Fever(Patient) ∧ Cough(Patient) → Flu(Patient) Used in systems like AI-powered healthcare chatbots (e.g., SehatSathi in Nepal).

2. Production Rules: IF [Condition] THEN [Action] Example (Traffic Light System):

   IF [CarApproaching(Sensor1) ∧ NoPedestrian(Crosswalk)]
   THEN [TurnGreen(Light1)]
   

Inference Methods

Worked Example: NTC’s Network Monitoring NTC uses backward chaining to diagnose network issues: Goal: NetworkDown(Region) Rules:

1. NetworkDown(X) → ∃Y (ServerDown(Y) ∧ Connected(X, Y))
2. ServerDown("Kathmandu") → ∃Z (PowerOutage(Z) ∧ Location(Z, "Kathmandu"))

Trace:

1. Start with NetworkDown("Kathmandu") (hypothesis).
2. To prove this, check if ServerDown("Kathmandu") is true.
3. To prove ServerDown("Kathmandu"), check for PowerOutage in Kathmandu.
4. If sensors confirm PowerOutage("Kathmandu"), the hypothesis is confirmed.

4. Semantics and Models: What Does It All Mean?

• Interpretation: Assigns meaning to symbols (e.g., Parent(x, y) means "x is a parent of y").
• Model: A structure that satisfies a set of logical statements. Example: A model for ∀x (Parent(x, ram) → God(x)) could be:
  • Domain: {ram, krishna, sita}
  • Parent: {(krishna, ram), (sita, ram)}
  • God: {krishna}

Visual: State Space of a Simple Puzzle

Explanation: This represents the state space of a 3-box puzzle. Each node is a possible world (interpretation), and edges represent valid moves. The goal is to reach E.

5. Limitations and Extensions

In the Real World

1. eSewa’s Fraud Detection

   • Idea Used: Propositional logic rules (e.g., (NewDevice ∧ LargeAmount) → FlagFraud).
   • How: Combines transaction data with user behavior to trigger alerts. If both conditions (NewDevice and LargeAmount) are met, the system flags the transaction for review.

2. Khalti’s Transaction Validation

   • Idea Used: Horn clauses for rule-based validation.
   • Example Rule: ∀x ∀y (Transaction(x, y) ∧ Amount(y) > 100000 ∧ ¬Verified(x)) → Reject(y) Translation: "If a transaction exceeds Rs. 100,000 and the user is unverified, reject it."

3. Pathao’s Ride Matching

   • Idea Used: Predicate logic for dynamic matching.
   • Example: ∃Driver(D) ∃Rider(R) (Available(D) ∧ Request(R) ∧ Location(D) ≈ Location(R)) → Match(D, R) How: The app continuously checks for available drivers near riders’ locations and matches them in real time.

Exam Tip

1. For Short Notes/Definitions:

   • Always define propositional logic as "a branch of logic where statements are either true or false and combined using connectives (∧, ∨, →, ¬)."
   • Define predicate logic as "an extension of propositional logic that includes predicates (properties/relationships) and quantifiers (∀, ∃)."

2. For Comparisons (e.g., Propositional vs. Predicate Logic): Use this table in exams:

   Feature	Propositional Logic	Predicate Logic
   Represents	Simple true/false statements.	Relationships and quantifiers.
   Example	P: "It is raining."	Parent(john, mary)
   Expressiveness	Limited (no relationships).	High (can model complex domains).
   Inference	Truth tables, resolution.	Forward/backward chaining, unification.
   Use Case	Simple rules (e.g., traffic lights).	Expert systems, databases.

3. For Worked Examples:

   • Always tie to a real system (e.g., eSewa, Khalti, NTC).
   • Show step-by-step traces (e.g., how a rule like P → Q is applied).
   • Use small, concrete numbers (e.g., "Rs. 50,000" instead of "large amount").

4. For Applications:

   • Healthcare: Diagnostic systems use Horn clauses (e.g., Symptom1 ∧ Symptom2 → Disease).
   • E-commerce: Daraz’s inventory system uses ∀x (Ordered(x) ∧ InStock(x) → Ship(x)).
   • Finance: Banks use LoanApproved(Customer) → ∃Limit(LimitAmount(Customer)).

5. Avoid Common Mistakes:

   • ❌ Confusing → (implies) with ∧ (and). Remember: P → Q is false only when P is true and Q is false.
   • ❌ Forgetting to quantify variables in predicate logic. Always use ∀ or ∃ where needed.
   • ❌ Overcomplicating examples. Stick to 2-3 predicates and clear rules.

Final Visual: Decision Tree for Loan Approval (Bank Example)

Caption: A bank’s loan approval system uses a decision tree (a form of logical rule) to classify applicants. This is equivalent to the rule: (Income > 50000) ∧ (CreditScore > 600) → ApproveLoan.

In the real world

• eSewa’s Fraud Detection: Uses propositional logic rules like (NewDevice ∧ HighAmount) → FlagFraud to evaluate transactions in real-time. The system checks 100,000+ transactions daily with <0.1% false positives.

• Daraz’s Warehouse System: Implements predicate logic for inventory management. When Ordered(Customer, Product, Qty) and InStock(Product, Qty) are true, it automatically generates Shipped(OrderID)—processing 50,000+ orders monthly.

• NTC’s Network Diagnostics: Employs backward chaining to isolate faults. If NetworkDown(Region) is suspected, it recursively checks ServerDown and PowerOutage predicates, reducing mean-time-to-repair by 40%.