Knowledge Representation Using Scripts

What is a Script?

A script is a structured representation of knowledge about a stereotyped sequence of events in a particular context. Scripts were introduced by Roger Schank and Robert Abelson (1977) to represent common, everyday situations that follow a predictable pattern.

A script describes a causally ordered sequence of events that are expected to occur in a specific situation. It allows an AI system to make inferences about what happened even when information is incomplete.

Components of a Script

A script consists of the following components:

Example: Restaurant Script

Script:    RESTAURANT
Track:     Coffee Shop
Entry Conditions:
           - Customer is hungry
           - Customer has money
Roles:
           - Customer (C)
           - Waiter (W)
           - Cook (K)
           - Cashier (Ca)
Props:
           - Tables, Menu, Food, Bill, Money

Scene 1: ENTERING
    - Customer enters restaurant
    - Customer looks for a table
    - Customer sits down

Scene 2: ORDERING
    - Waiter brings menu
    - Customer reads menu
    - Customer orders food
    - Waiter takes order to cook

Scene 3: EATING
    - Cook prepares food
    - Waiter brings food to customer
    - Customer eats food

Scene 4: LEAVING
    - Waiter brings bill
    - Customer pays bill
    - Customer leaves restaurant

Results:
    - Customer is no longer hungry
    - Customer has less money
    - Restaurant has more money

How Scripts Help in Inference

Consider the following story:

"John went to a restaurant. He ordered a burger. He left a tip."

Using the restaurant script, the AI system can infer the following facts that were never explicitly stated:

• John sat at a table
• A waiter brought him a menu
• John paid the bill before leaving
• John was hungry when he entered

This ability to fill in missing information is called script-based inference.

Advantages of Scripts

1. Allows inference about unstated events
2. Handles incomplete information effectively
3. Represents real-world common sense knowledge
4. Useful in natural language understanding systems

Limitations

1. Scripts are rigid and do not handle unexpected events well
2. Requires a large number of scripts to cover real-world situations
3. Difficult to handle novel situations not covered by existing scripts

Note: Scripts are a form of frame-based knowledge representation where knowledge is organized around a central concept or situation, making them suitable for AI systems dealing with natural language processing and story understanding.

Issues in Knowledge Representation & Resolution

Part 1: Issues in Knowledge Representation (4 marks)

Knowledge representation deals with how knowledge about the world can be represented so that a computer system can use it to solve complex problems. The major issues are:

1. Representational Adequacy

The knowledge representation scheme must be able to represent all kinds of knowledge needed for the domain. It should handle facts, rules, relationships, and exceptions without loss of information.

2. Inferential Adequacy

The system must be able to derive new knowledge from existing knowledge. The representation must support valid inferences and reasoning mechanisms.

3. Inferential Efficiency

The system should be able to draw inferences quickly and efficiently. The representation should allow the inference engine to focus on relevant knowledge and avoid unnecessary search.

4. Acquisitional Efficiency

It should be easy to add new knowledge to the system without reorganizing the entire knowledge base. The representation should support incremental knowledge acquisition.

5. Expressiveness

The representation language must be expressive enough to capture complex relationships, uncertainty, time, and context in the real world.

6. Consistency and Completeness

The knowledge base should be free from contradictions (consistent) and should contain all necessary facts (complete) to answer queries correctly.

7. Handling Uncertainty

Real-world knowledge is often incomplete or uncertain. The representation must handle probabilistic or fuzzy information.

Part 2: Resolution Proof (6 marks)

Knowledge Base (Given Facts)

Let us define the predicates:

• Fruit(x) : x is a fruit
• Likes(x, y) : x likes y
• Eats(x, y) : x eats y
• Loves(x, y) : x loves y

Given Knowledge Base (Axioms)

Convert to Conjunctive Normal Form (CNF) / Clausal Form

F5: ∀x ∀y [Eats(x,y) ∧ Loves(x,y) → Fruit(y)] = ∀x ∀y [¬Eats(x,y) ∨ ¬Loves(x,y) ∨ Fruit(y)] Clause C5: {¬Eats(x,y), ¬Loves(x,y), Fruit(y)}

F6: ∀x ∀y [Eats(x,y) ∧ Loves(x,y) → Likes(x,y)] = ∀x ∀y [¬Eats(x,y) ∨ ¬Loves(x,y) ∨ Likes(x,y)] Clause C6: {¬Eats(x,y), ¬Loves(x,y), Likes(x,y)}

All Clauses:

a.) Prove: Ava likes watermelon → Likes(Ava, Watermelon)

Negate the goal: ¬Likes(Ava, Watermelon) → Clause C7

Resolution Steps:

Step 1: Resolve C6 and C3
         C6: ¬Eats(x,y) ∨ ¬Loves(x,y) ∨ Likes(x,y)
         C3: Eats(Ava, Watermelon)
         Unifier: {x=Ava, y=Watermelon}
         Result C8: ¬Loves(Ava, Watermelon) ∨ Likes(Ava, Watermelon)

Step 2: Resolve C8 and C4
         C8: ¬Loves(Ava, Watermelon) ∨ Likes(Ava, Watermelon)
         C4: Loves(Ava, Watermelon)
         Result C9: Likes(Ava, Watermelon)

Step 3: Resolve C9 and C7
         C9: Likes(Ava, Watermelon)
         C7: ¬Likes(Ava, Watermelon)
         Result: □ (Empty Clause - Contradiction)

Proved: Ava likes watermelon ✓

b.) Prove: Apple and Watermelon are fruits

For Apple: Fruit(Apple) is already given as clause C1, so the proof is immediate.

Negate the goal: C7': ¬Fruit(Apple)

Step 1: Resolve C7' and C1
         C1 : Fruit(Apple)
         C7': ¬Fruit(Apple)
         Result: □ (Empty Clause - Contradiction)

For Watermelon: Fruit(Watermelon) is given as C2, but it can also be derived from the rule C5, which is the more informative proof.

Negate the goal: C7'': ¬Fruit(Watermelon)

Step 1: Resolve C5 and C3
         C5: ¬Eats(x,y) ∨ ¬Loves(x,y) ∨ Fruit(y)
         C3: Eats(Ava, Watermelon)
         Unifier: {x=Ava, y=Watermelon}
         Result C10: ¬Loves(Ava, Watermelon) ∨ Fruit(Watermelon)

Step 2: Resolve C10 and C4
         C4: Loves(Ava, Watermelon)
         Result C11: Fruit(Watermelon)

Step 3: Resolve C11 and C7''
         Result: □ (Empty Clause - Contradiction)

Proved: Apple and Watermelon are fruits ✓

c.) Prove: Ava eats watermelon and loves it so much

The goal is the conjunction Eats(Ava, Watermelon) ∧ Loves(Ava, Watermelon). Negating a conjunction gives a single disjunctive clause.

Negate the goal: C12: ¬Eats(Ava, Watermelon) ∨ ¬Loves(Ava, Watermelon)

Step 1: Resolve C12 and C3
         C3: Eats(Ava, Watermelon)
         Result C13: ¬Loves(Ava, Watermelon)

Step 2: Resolve C13 and C4
         C4: Loves(Ava, Watermelon)
         Result: □ (Empty Clause - Contradiction)

Proved: Ava eats watermelon and loves it so much ✓

d.) Prove: Anything eaten by anybody and loved so much is a fruit

The goal is the universally quantified rule ∀x ∀y [Eats(x,y) ∧ Loves(x,y) → Fruit(y)]. Its negation is existential, so the two existential variables are replaced by Skolem constants a and b, giving three unit clauses.

Negate the goal:
   ¬∀x ∀y [¬Eats(x,y) ∨ ¬Loves(x,y) ∨ Fruit(y)]
 = ∃x ∃y [Eats(x,y) ∧ Loves(x,y) ∧ ¬Fruit(y)]

Skolemize with constants a and b:
   C14: Eats(a, b)
   C15: Loves(a, b)
   C16: ¬Fruit(b)

Step 1: Resolve C5 and C14
         C5 : ¬Eats(x,y) ∨ ¬Loves(x,y) ∨ Fruit(y)
         Unifier: {x=a, y=b}
         Result C17: ¬Loves(a, b) ∨ Fruit(b)

Step 2: Resolve C17 and C15
         Result C18: Fruit(b)

Step 3: Resolve C18 and C16
         Result: □ (Empty Clause - Contradiction)

Proved: anything eaten by somebody and loved so much is a fruit ✓

Conclusion

Resolution refutation works the same way in all four parts: the knowledge base is converted to clausal form, the statement to be proved is negated and added to the clause set, and clauses are resolved with the most general unifier until the empty clause appears. Reaching the empty clause shows that the negated goal is inconsistent with the knowledge base, which means the original goal follows from it. Parts b and c resolve directly against the given facts, while parts a and d need the implication clauses C6 and C5 with the substitution {x = Ava, y = Watermelon} and the Skolem constants respectively.

Hill Climbing is a local search algorithm that continuously moves in the direction of increasing value (uphill) to find the peak (optimal solution). It is an iterative algorithm that starts with an arbitrary solution and attempts to find...

A Genetic Algorithm (GA) is a search and optimization technique inspired by the process of natural selection and biological evolution. It works by evolving a population of candidate solutions over successive generations to find an optima...

a. All animals and plants are living things. b. Rose is a plant. c. All plants prepare food using photosynthesis process. d. Carnivorous animals don't eat plants. e. Tiger is carnivorous. --- --- Node 1 (Subject) Relationship / Arc Node ...

Knowledge Representation Using Scripts

What is a Script?

A script is a structured representation of knowledge about a stereotyped sequence of events in a particular context. Scripts were introduced by Roger Schank and Robert Abelson (1977) to represent common, everyday situations that follow a predictable pattern.

A script describes a causally ordered sequence of events that are expected to occur in a specific situation. It allows an AI system to make inferences about what happened even when information is incomplete.

Components of a Script

A script consists of the following components:

Example: Restaurant Script

Script:    RESTAURANT
Track:     Coffee Shop
Entry Conditions:
           - Customer is hungry
           - Customer has money
Roles:
           - Customer (C)
           - Waiter (W)
           - Cook (K)
           - Cashier (Ca)
Props:
           - Tables, Menu, Food, Bill, Money

Scene 1: ENTERING
    - Customer enters restaurant
    - Customer looks for a table
    - Customer sits down

Scene 2: ORDERING
    - Waiter brings menu
    - Customer reads menu
    - Customer orders food
    - Waiter takes order to cook

Scene 3: EATING
    - Cook prepares food
    - Waiter brings food to customer
    - Customer eats food

Scene 4: LEAVING
    - Waiter brings bill
    - Customer pays bill
    - Customer leaves restaurant

Results:
    - Customer is no longer hungry
    - Customer has less money
    - Restaurant has more money

How Scripts Help in Inference

Consider the following story:

"John went to a restaurant. He ordered a burger. He left a tip."

Using the restaurant script, the AI system can infer the following facts that were never explicitly stated:

• John sat at a table
• A waiter brought him a menu
• John paid the bill before leaving
• John was hungry when he entered

This ability to fill in missing information is called script-based inference.

Advantages of Scripts

1. Allows inference about unstated events
2. Handles incomplete information effectively
3. Represents real-world common sense knowledge
4. Useful in natural language understanding systems

Limitations

1. Scripts are rigid and do not handle unexpected events well
2. Requires a large number of scripts to cover real-world situations
3. Difficult to handle novel situations not covered by existing scripts

Note: Scripts are a form of frame-based knowledge representation where knowledge is organized around a central concept or situation, making them suitable for AI systems dealing with natural language processing and story understanding.

Intelligent Agent and PEAS Framework for a Particle Picking Robot

What is an Intelligent Agent? [1 mark]

An intelligent agent is anything that can perceive its environment through sensors and act upon that environment through actuators in order to achieve its goals. An intelligent agent takes the best possible action based on its percepts, built-in knowledge, and past experience to maximize its performance measure.

PEAS Framework [4 marks]

PEAS stands for:

• P - Performance Measure
• E - Environment
• A - Actuators
• S - Sensors

PEAS is used to describe the task environment of an intelligent agent.

PEAS Framework for a Particle Picking Robot

Summary Table

Agent:  Particle Picking Robot
+------------------+------------------------------------------+
| P (Performance)  | Particles picked, surface cleanliness,   |
|                  | energy efficiency, time efficiency        |
+------------------+------------------------------------------+
| E (Environment)  | Factory floor, scattered particles,       |
|                  | obstacles, varying lighting               |
+------------------+------------------------------------------+
| A (Actuators)    | Robotic arm, gripper, wheels, suction,    |
|                  | deposit container                         |
+------------------+------------------------------------------+
| S (Sensors)      | Camera, proximity sensor, touch sensor,   |
|                  | position sensor, particle detector        |
+------------------+------------------------------------------+

Key Points to Remember

• The Performance Measure evaluates how well the agent is doing its job.
• The Environment defines where the agent operates.
• Actuators are the means by which the agent affects the environment.
• Sensors are the means by which the agent perceives the environment.

Artificial Intelligence (AI) is the branch of computer science that deals with the design and development of computer systems capable of performing tasks that normally require human intelligence. These tasks include: - Reasoning and prob...

Issues in Knowledge Representation & Resolution

Part 1: Issues in Knowledge Representation (4 marks)

Knowledge representation deals with how knowledge about the world can be represented so that a computer system can use it to solve complex problems. The major issues are:

1. Representational Adequacy

The knowledge representation scheme must be able to represent all kinds of knowledge needed for the domain. It should handle facts, rules, relationships, and exceptions without loss of information.

2. Inferential Adequacy

The system must be able to derive new knowledge from existing knowledge. The representation must support valid inferences and reasoning mechanisms.

3. Inferential Efficiency

The system should be able to draw inferences quickly and efficiently. The representation should allow the inference engine to focus on relevant knowledge and avoid unnecessary search.

4. Acquisitional Efficiency

It should be easy to add new knowledge to the system without reorganizing the entire knowledge base. The representation should support incremental knowledge acquisition.

5. Expressiveness

The representation language must be expressive enough to capture complex relationships, uncertainty, time, and context in the real world.

6. Consistency and Completeness

The knowledge base should be free from contradictions (consistent) and should contain all necessary facts (complete) to answer queries correctly.

7. Handling Uncertainty

Real-world knowledge is often incomplete or uncertain. The representation must handle probabilistic or fuzzy information.

Part 2: Resolution Proof (6 marks)

Knowledge Base (Given Facts)

Let us define the predicates:

• Fruit(x) : x is a fruit
• Likes(x, y) : x likes y
• Eats(x, y) : x eats y
• Loves(x, y) : x loves y

Given Knowledge Base (Axioms)

Convert to Conjunctive Normal Form (CNF) / Clausal Form

F5: ∀x ∀y [Eats(x,y) ∧ Loves(x,y) → Fruit(y)] = ∀x ∀y [¬Eats(x,y) ∨ ¬Loves(x,y) ∨ Fruit(y)] Clause C5: {¬Eats(x,y), ¬Loves(x,y), Fruit(y)}

F6: ∀x ∀y [Eats(x,y) ∧ Loves(x,y) → Likes(x,y)] = ∀x ∀y [¬Eats(x,y) ∨ ¬Loves(x,y) ∨ Likes(x,y)] Clause C6: {¬Eats(x,y), ¬Loves(x,y), Likes(x,y)}

All Clauses:

a.) Prove: Ava likes watermelon → Likes(Ava, Watermelon)

Negate the goal: ¬Likes(Ava, Watermelon) → Clause C7

Resolution Steps:

Step 1: Resolve C6 and C3
         C6: ¬Eats(x,y) ∨ ¬Loves(x,y) ∨ Likes(x,y)
         C3: Eats(Ava, Watermelon)
         Unifier: {x=Ava, y=Watermelon}
         Result C8: ¬Loves(Ava, Watermelon) ∨ Likes(Ava, Watermelon)

Step 2: Resolve C8 and C4
         C8: ¬Loves(Ava, Watermelon) ∨ Likes(Ava, Watermelon)
         C4: Loves(Ava, Watermelon)
         Result C9: Likes(Ava, Watermelon)

Step 3: Resolve C9 and C7
         C9: Likes(Ava, Watermelon)
         C7: ¬Likes(Ava, Watermelon)
         Result: □ (Empty Clause - Contradiction)

Proved: Ava likes watermelon ✓

b.) Prove: Apple and Watermelon are fruits

For Apple: Fruit(Apple) is already given as clause C1, so the proof is immediate.

Negate the goal: C7': ¬Fruit(Apple)

Step 1: Resolve C7' and C1
         C1 : Fruit(Apple)
         C7': ¬Fruit(Apple)
         Result: □ (Empty Clause - Contradiction)

For Watermelon: Fruit(Watermelon) is given as C2, but it can also be derived from the rule C5, which is the more informative proof.

Negate the goal: C7'': ¬Fruit(Watermelon)

Step 1: Resolve C5 and C3
         C5: ¬Eats(x,y) ∨ ¬Loves(x,y) ∨ Fruit(y)
         C3: Eats(Ava, Watermelon)
         Unifier: {x=Ava, y=Watermelon}
         Result C10: ¬Loves(Ava, Watermelon) ∨ Fruit(Watermelon)

Step 2: Resolve C10 and C4
         C4: Loves(Ava, Watermelon)
         Result C11: Fruit(Watermelon)

Step 3: Resolve C11 and C7''
         Result: □ (Empty Clause - Contradiction)

Proved: Apple and Watermelon are fruits ✓

c.) Prove: Ava eats watermelon and loves it so much

The goal is the conjunction Eats(Ava, Watermelon) ∧ Loves(Ava, Watermelon). Negating a conjunction gives a single disjunctive clause.

Negate the goal: C12: ¬Eats(Ava, Watermelon) ∨ ¬Loves(Ava, Watermelon)

Step 1: Resolve C12 and C3
         C3: Eats(Ava, Watermelon)
         Result C13: ¬Loves(Ava, Watermelon)

Step 2: Resolve C13 and C4
         C4: Loves(Ava, Watermelon)
         Result: □ (Empty Clause - Contradiction)

Proved: Ava eats watermelon and loves it so much ✓

d.) Prove: Anything eaten by anybody and loved so much is a fruit

The goal is the universally quantified rule ∀x ∀y [Eats(x,y) ∧ Loves(x,y) → Fruit(y)]. Its negation is existential, so the two existential variables are replaced by Skolem constants a and b, giving three unit clauses.

Negate the goal:
   ¬∀x ∀y [¬Eats(x,y) ∨ ¬Loves(x,y) ∨ Fruit(y)]
 = ∃x ∃y [Eats(x,y) ∧ Loves(x,y) ∧ ¬Fruit(y)]

Skolemize with constants a and b:
   C14: Eats(a, b)
   C15: Loves(a, b)
   C16: ¬Fruit(b)

Step 1: Resolve C5 and C14
         C5 : ¬Eats(x,y) ∨ ¬Loves(x,y) ∨ Fruit(y)
         Unifier: {x=a, y=b}
         Result C17: ¬Loves(a, b) ∨ Fruit(b)

Step 2: Resolve C17 and C15
         Result C18: Fruit(b)

Step 3: Resolve C18 and C16
         Result: □ (Empty Clause - Contradiction)

Proved: anything eaten by somebody and loved so much is a fruit ✓

Conclusion

Resolution refutation works the same way in all four parts: the knowledge base is converted to clausal form, the statement to be proved is negated and added to the clause set, and clauses are resolved with the most general unifier until the empty clause appears. Reaching the empty clause shows that the negated goal is inconsistent with the knowledge base, which means the original goal follows from it. Parts b and c resolve directly against the given facts, while parts a and d need the implication clauses C6 and C5 with the substitution {x = Ava, y = Watermelon} and the Skolem constants respectively.

Hill Climbing is a local search algorithm that continuously moves in the direction of increasing value (uphill) to find the peak (optimal solution). It is an iterative algorithm that starts with an arbitrary solution and attempts to find...

A Genetic Algorithm (GA) is a search and optimization technique inspired by the process of natural selection and biological evolution. It works by evolving a population of candidate solutions over successive generations to find an optima...

a. All animals and plants are living things. b. Rose is a plant. c. All plants prepare food using photosynthesis process. d. Carnivorous animals don't eat plants. e. Tiger is carnivorous. --- --- Node 1 (Subject) Relationship / Arc Node ...

--- A simple reflex agent selects actions based only on the current percept, ignoring the entire percept history. It works on a simple condition-action rule: If condition then action - It has no memory of past states. - It assumes the en...

Note: Reference notes were not available for this topic. The following answer is based on standard, correct Computer Science knowledge appropriate for TU BSc CSIT curriculum. --- DFS explores a graph by going as deep as possible along ea...

Ambiguity is one of the fundamental challenges in NLP. It occurs when a word, phrase, or sentence can be interpreted in more than one way. Since human language is inherently ambiguous, NLP systems must be designed to resolve these ambigu...

Learning Rule and Backpropagation in ANN

Part 1: What is a Learning Rule? [2 marks]

A learning rule is a method or procedure that modifies the weights and biases of a neural network in order to improve its performance on a given task. It defines how the network learns from training data by updating connection weights based on the error between the actual output and the desired output.

Common types of learning rules include:

• Hebbian Learning Rule - weights are updated based on the correlation of input and output activations
• Perceptron Learning Rule - weights are updated when the output is incorrect
• Delta (Widrow-Hoff) Rule - weights are updated proportional to the error
• Backpropagation Rule - generalized delta rule for multilayer networks

General form: $$\Delta w_{ij} = \eta \cdot \delta_j \cdot x_i$$ where $\eta$ is the learning rate, $\delta_j$ is the error signal, and $x_i$ is the input.

Part 2: Learning Using Backpropagation Algorithm [8 marks]

Overview

Backpropagation (BP) is a supervised learning algorithm used to train multilayer feedforward neural networks. It works by:

1. Forward pass - computing the output
2. Backward pass - propagating the error backward and updating weights

Network Architecture

Consider a three-layer network:

• Input layer - nodes indexed $i$
• Hidden layer - nodes indexed $j$
• Output layer - nodes indexed $k$

Step-by-Step Backpropagation Algorithm

Step 1: Initialize Weights

Set all weights $w_{ij}$ and $w_{jk}$ to small random values (typically between -0.5 and 0.5).

Step 2: Forward Pass (Feed Forward)

At the hidden layer, compute the net input and activation for each hidden neuron $j$:

$$net_j = \sum_i w_{ij} \cdot x_i + b_j$$

$$y_j = f(net_j) = \frac{1}{1 + e^{-net_j}} \quad \text{(sigmoid activation)}$$

At the output layer, compute the net input and activation for each output neuron $k$:

$$net_k = \sum_j w_{jk} \cdot y_j + b_k$$

$$o_k = f(net_k) = \frac{1}{1 + e^{-net_k}}$$

Step 3: Compute Output Error

For each output neuron $k$, compute the error signal $\delta_k$:

$$E = \frac{1}{2} \sum_k (t_k - o_k)^2$$

where $t_k$ is the target (desired) output and $o_k$ is the actual output.

The error gradient at the output layer:

$$\delta_k = (t_k - o_k) \cdot f'(net_k)$$

For sigmoid activation: $f'(net_k) = o_k(1 - o_k)$

$$\boxed{\delta_k = (t_k - o_k) \cdot o_k(1 - o_k)}$$

Step 4: Backpropagate Error to Hidden Layer

Compute the error signal $\delta_j$ for each hidden neuron $j$:

$$\delta_j = \left(\sum_k \delta_k \cdot w_{jk}\right) \cdot f'(net_j)$$

$$\boxed{\delta_j = \left(\sum_k \delta_k \cdot w_{jk}\right) \cdot y_j(1 - y_j)}$$

The error is propagated backward from output to hidden layer using the weights.

Step 5: Update Weights

Update weights between hidden and output layer:

$$\Delta w_{jk} = \eta \cdot \delta_k \cdot y_j$$

$$w_{jk}^{new} = w_{jk}^{old} + \Delta w_{jk}$$

Update weights between input and hidden layer:

$$\Delta w_{ij} = \eta \cdot \delta_j \cdot x_i$$

$$w_{ij}^{new} = w_{ij}^{old} + \Delta w_{ij}$$

where $\eta$ is the learning rate (typically 0.01 to 0.9).

Step 6: Repeat

Repeat Steps 2 to 5 for all training patterns until the total error $E$ is minimized below a threshold or the maximum number of epochs is reached.

Summary Diagram

Input Layer      Hidden Layer      Output Layer
   x_i  ---w_ij---> y_j ---w_jk---> o_k
                                      |
                              Error = (t_k - o_k)
                                      |
              <--- delta_j <--- delta_k (backpropagated)
              Weight update          Weight update

Key Points

Advantages and Limitations

Advantages:

• Can learn complex nonlinear mappings
• Works for multilayer networks

Limitations:

• May get stuck in local minima
• Slow convergence for large networks
• Requires labeled training data
• Sensitive to learning rate choice

This is a conceptual/constructive question. No numeric matrices, burst times, or reference strings are supplied. The student is required to: - Define state space problem formulation [2] - Construct a state space with start/goal, heuristi...

Unification, Lifting in Predicate Logic & Knowledge Base Construction

Part 1: Unification and Lifting [4 Marks]

Unification

Unification is the process of finding a substitution (called a unifier) that makes two or more logical expressions identical.

• A substitution θ is a set of bindings of the form {x/term, y/term, ...}
• The Most General Unifier (MGU) is the most general substitution that unifies two expressions

Unification Algorithm Steps:

1. If both expressions are constants or the same variable, they unify (empty substitution)
2. If one is a variable, substitute it with the other term (occurs check: variable must not appear in the term)
3. If both are compound expressions, unify functor/predicate names and then unify arguments recursively
4. If none of the above, unification fails

Example:

Lifting

Lifting refers to the process of generalizing inference rules from propositional logic to first-order predicate logic by incorporating unification.

The key idea: instead of applying rules to ground (fully instantiated) sentences only, we lift them to work with variables using unification.

Example - Lifted Modus Ponens (Generalized Modus Ponens):

If we have:

• P(x) → Q(x) (for all x)
• P(John)

Then by unification {x/John}, we derive: Q(John)

Lifted Resolution:

Standard resolution in propositional logic:

From (A ∨ B) and (¬B ∨ C), derive (A ∨ C)

Lifted resolution in FOL:

From (P(x) ∨ Q(x)) and (¬P(John) ∨ R(y)), unify P(x) with P(John) using {x/John}, derive (Q(John) ∨ R(y))

Benefits of Lifting:

• Avoids instantiating all possible ground instances
• Makes inference efficient and general
• Enables working directly with universally quantified statements

Part 2: Knowledge Base in FOL and CNF Conversion [6 Marks]

Step 1: Represent Statements in FOL

Let:

• S(x) = x is a student
• Smart(x) = x is a smart person
• I(x) = x is intelligent
• H(x) = x is hardworking

Step 2: Convert Each Statement to CNF

CNF Conversion Steps:

1. Eliminate implications (A → B becomes ¬A ∨ B)
2. Move negations inward (De Morgan's laws)
3. Standardize variables apart
4. Skolemize (eliminate existential quantifiers)
5. Drop universal quantifiers
6. Distribute ∨ over ∧

Statement 1: ∀x [S(x) → Smart(x)]

• Eliminate implication: ∀x [¬S(x) ∨ Smart(x)]
• Drop universal quantifier:

CNF: ¬S(x) ∨ Smart(x)

Statement 2: ∀x [Smart(x) → ¬I(x)]

• Eliminate implication: ∀x [¬Smart(x) ∨ ¬I(x)]
• Drop universal quantifier:

CNF: ¬Smart(x) ∨ ¬I(x)

Statement 3: ∃x [I(x)]

• Skolemize: Replace ∃x with a Skolem constant c (since no universal quantifier wraps it)
• Result: I(c)

CNF: I(c)

Statement 4: [∀x (S(x) → I(x))] ∨ [∀x (S(x) → H(x))]

This is the most complex. First, standardize variables apart:

[∀x (S(x) → I(x))] ∨ [∀y (S(y) → H(y))]

• Eliminate implications:

[∀x (¬S(x) ∨ I(x))] ∨ [∀y (¬S(y) ∨ H(y))]

• Move quantifiers outward (prenex normal form):

∀x ∀y [(¬S(x) ∨ I(x)) ∨ (¬S(y) ∨ H(y))]

• Drop universal quantifiers:

(¬S(x) ∨ I(x) ∨ ¬S(y) ∨ H(y))

CNF: ¬S(x) ∨ I(x) ∨ ¬S(y) ∨ H(y)

Summary of CNF Clauses

Conclusion

Unification finds the substitution that makes two literals identical, and lifting is what allows the propositional inference rules to be applied directly to quantified first order sentences by using that substitution. Once every sentence of the knowledge base has been reduced to the four clauses above, resolution can be applied mechanically to them, since every clause is now a disjunction of literals with all quantifiers removed.

--- An Artificial Neural Network (ANN) is inspired by biological neurons. The mathematical model of a single artificial neuron consists of the following components: 1. Inputs and Weights: Each neuron receives n inputs x₁, x₂, ..., xₙ wit...

Dempster-Shafer Theory

Note: The reference notes did not contain this topic. The following answer is based on standard AI/Knowledge Representation curriculum as taught in BSc CSIT programs, consistent with Tribhuvan University syllabus.

(a) Dempster-Shafer Theory

Dempster-Shafer Theory (DST), also known as the Theory of Evidence or Belief Function Theory, was developed by Arthur Dempster and later extended by Glenn Shafer. It is a mathematical framework for reasoning under uncertainty that generalizes Bayesian probability theory by allowing degrees of belief to be assigned to sets of possibilities rather than individual outcomes.

Key Concepts

1. Frame of Discernment (Θ) A finite set of mutually exclusive and exhaustive hypotheses (possible answers to a question).

Example: Θ = {Disease A, Disease B, Disease C}

2. Basic Probability Assignment (BPA) / Mass Function m(·) A function m: 2^Θ → [0, 1] such that:

• m(∅) = 0
• Σ m(A) = 1, for all A ⊆ Θ

Here, m(A) represents the degree of belief (evidence mass) assigned directly to subset A, not distributed to its subsets.

3. Belief Function (Bel) The total belief committed to a hypothesis A, including all subsets of A:

Bel(A) = Σ m(B),  for all B ⊆ A, B ≠ ∅

4. Plausibility Function (Pl) The maximum possible support for A (belief that does not contradict A):

Pl(A) = Σ m(B),  for all B ∩ A ≠ ∅

The interval [Bel(A), Pl(A)] represents the uncertainty interval for hypothesis A.

5. Dempster's Rule of Combination When two independent sources of evidence provide mass functions m₁ and m₂, they are combined as:

m(A) = [ Σ m₁(B) · m₂(C) ] / (1 - K)
         B ∩ C = A

Where K is the conflict factor:

K = Σ m₁(B) · m₂(C),  for all B ∩ C = ∅

K measures the degree of conflict between the two sources.

(b) Use in Statistical Reasoning

Dempster-Shafer Theory is used in statistical reasoning in the following ways:

Example (Brief)

Suppose a doctor has two tests for a disease:

• Test 1 gives: m({Disease}) = 0.6, m({Healthy, Disease}) = 0.4
• Test 2 gives: m({Healthy}) = 0.7, m({Healthy, Disease}) = 0.3

Using Dempster's rule, these two pieces of evidence are combined to get a final belief, resolving the conflict statistically.

Summary

DST extends classical probability by allowing partial belief over subsets of hypotheses. It is particularly useful in statistical reasoning when evidence is incomplete, uncertain, or comes from multiple conflicting sources, making it a powerful tool in AI, expert systems, and decision making.