Introduction to AI and Applications (25CS1ETIAA)

MODULE – 2

2.1 Heuristic Search

AI deals with solving complex problems that are too intricate to be handled using simple or direct techniques. Many AI
problems require exploring multiple possible solutions before reaching an optimal one. Therefore, AI systems often rely
on search-based problem-solving methods, which use algorithms to explore different paths or states in order to find the
best solution.

A search method is a structured process that defines how an AI system navigates through the problem space — that is,
how it moves from an initial state to a goal state. These search strategies are typically categorized as heuristic search
methods, which rely on rules of thumb or approximate knowledge to guide the search process efficiently. Search
methods can be described independently of the problem domain, making them general-purpose techniques. However,
when applied to specific problems, their success depends largely on how well they incorporate domain-specific
knowledge. Without this knowledge, AI systems can face the combinatorial explosion problem — an exponential
growth in the number of possible states to explore, making computation infeasible.

Because these search strategies operate based on limited knowledge and rely on general rules rather than detailed
information, they are often termed weak methods. Despite their limitations, such methods form the core of most AI
systems as they provide the foundation into which specialized, domain-specific intelligence can be integrated either
manually or through automatic learning.

2.1.1 Types of Basic Search Strategies

Two of the most fundamental search techniques in AI are:

● Depth-First Search (DFS): Explores as far as possible along one branch before backtracking.

● Breadth-First Search (BFS): Explores all nodes at one level before moving to the next level.

These methods form the foundation of search algorithms and are essential for understanding more advanced strategies.

Other Important Search Strategies

Apart from DFS and BFS, the following search techniques are also commonly studied in AI:

● Generate-and-Test: Generates possible solutions and tests each for goal satisfaction.

● Hill Climbing: An iterative algorithm that moves towards a solution by selecting the best neighboring state.

● Constraint Satisfaction: Finds solutions that meet a set of constraints or conditions.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 1
 Introduction to AI and Applications (25CS1ETIAA)

● Means–Ends Analysis: Reduces the difference between the current state and the goal state by applying suitable
operators.

Each of these techniques is designed to handle specific problem scenarios efficiently and form the building blocks of
intelligent problem-solving systems.

2.2 Generate-and-Test

The Generate-and-Test strategy is one of the simplest and most fundamental problem-solving methods in Artificial
Intelligence. It is a trial-and-error approach where possible solutions are generated and tested until a satisfactory solution is
found. Despite its simplicity, it forms the foundation for more advanced AI techniques such as heuristic and evolutionary
algorithms.

2.2.1. Algorithm: Generate-and-Test

Step 1: Generate a Possible Solution

A potential solution is generated for the problem. In some cases, this may mean creating a specific configuration in the
problem space. In others, it could mean finding a path from a start state to a goal state.

Step 2: Test the Solution

The generated solution is tested by comparing it to the set of acceptable goal states. If the current state or path satisfies
the goal condition, the problem is solved.

Step 3: Stop or Continue

If the generated solution satisfies the goal condition, stop the search. Otherwise, return to Step 1 and generate a new
possible solution.

2.2.2. Working Principle

The generate-and-test algorithm functions as a depth-first search process because complete solutions must be generated
before testing them. If solutions are generated systematically, the algorithm guarantees finding a solution — provided one
exists — though it may take a long time for large search spaces. In its most exhaustive form, the algorithm explores every
possible state, similar to the British Museum Algorithm, where one searches through an entire museum randomly to find an
object. However, this exhaustive approach is inefficient and time-consuming. Hence, heuristics are often applied to make
the process smarter and faster.

2.2.3. Advantages

● Simple to understand and implement.

● Useful for small or well-defined problems.

● Forms the foundation for other AI problem-solving techniques.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 2
 Introduction to AI and Applications (25CS1ETIAA)

● Can be effective when combined with heuristic or constraint-based methods.

2.2.4. Limitations

● Extremely inefficient for large search spaces.

● May take a long time to find a solution, or may never find one if the space is infinite.

● Lacks feedback and optimization unless heuristics are added.

● Not suitable for complex real-world problems by itself.

2.2.5. Applications

1. Puzzle Solving: Example – Arranging colored cubes in a row so that no two adjacent cubes share the same color.
o Randomly generate arrangements and test until one satisfies the condition.
2. Scientific Discovery:
o Example – The AI system DENDRAL used a plan-generate-test approach to identify molecular structures
based on chemical data (mass spectrometry and NMR).

2.2.6. Heuristic Generate-and-Test

In practice, many AI systems combine the generate-and-test approach with heuristics.

● Heuristics guide the generation process by preferring solutions that are more likely to succeed.

● This reduces unnecessary exploration and improves efficiency.

● Example: Instead of trying all possible cube arrangements in the puzzle, a heuristic may prioritize placing blocks
with more matching faces first.

Variations

● Systematic Generate-and-Test: Exhaustively explores all options (guarantees a solution).

● Random Generate-and-Test: Randomly samples the solution space (less guaranteed but faster).

● Heuristic Generate-and-Test: Uses rules to prioritize promising solutions.

2.2.7. Example

Consider solving a simple equation: 𝑥 2 − 4 = 0

1. Generate possible values for x (e.g., -3, -2, -1, 0, 1, 2, 3).

2. Test each value by substituting it into the equation.
3. When x = ±2, the condition is satisfied → stop.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 3
 Introduction to AI and Applications (25CS1ETIAA)

This demonstrates how generate-and-test systematically searches through potential solutions until a goal is met.

Example 1: Finding a Number Whose Square Equals 49

Scenario:
We need to find a number between 1 and 100 that, when squared, gives 49.

Steps:

1. Generate: Start from 1 and sequentially generate possible numbers: 1 → 2 → 3 → 4 → 5 → 6 → 7

2. Test: For each number, calculate its square and check if it equals 49.
o 1² = 1
o 2² = 4
o 3² = 9
o 4² = 16
o 5² = 25
o 6² = 36
o 7² = 49 ✅
3. Stop: The correct solution is found when 7² = 49.

Explanation:
This example illustrates the basic essence of generate-and-test. The algorithm generates candidate solutions (numbers) and
tests each one until the goal condition (square = 49) is met. This process is simple but systematic — it guarantees a solution,
though it may not be efficient for larger problem spaces.

Example 2: Password Recovery (Brute Force Search)

Scenario:
Imagine you forgot your 4-digit phone password but remember that it contains only numbers (0000–9999).

Steps:

1. Generate: All possible combinations from 0000 to 9999 are generated.

2. Test: Each password is tested by attempting to unlock the phone.
3. Stop: The process stops when the phone unlocks successfully.

Explanation:
This is a real-world example of a brute force search — a direct application of the generate-and-test method. It does not use
any shortcuts or heuristics; instead, it systematically tests all possible combinations until the correct one is found.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 4
 Introduction to AI and Applications (25CS1ETIAA)

Note: Even though generate-and-test alone is limited, when used with other methods (like constraint satisfaction or
planning), it becomes a powerful part of AI systems. For instance, plan-generate-test combines planning and search — it
first plans a structure for solutions, generates possible ones, and tests them to identify feasible results.

Example 3: Maze Solving (Robot Example)

Scenario:
A robot is placed inside a maze and must find the correct path to the exit.

Steps:

1. Generate: The robot generates a possible path by moving forward.

2. Test: It checks whether the path leads to the goal (the exit).
3. Backtrack: If it encounters a dead end, it returns (backtracks) and generates another path.
4. Repeat: The generate-test cycle continues until the robot reaches the exit.

Explanation:
This is an example of a search-based problem-solving task. Early AI systems like the General Problem Solver (GPS)
used similar logic to explore problem spaces. The robot evaluates paths one by one until it finds the correct sequence of
moves leading to the goal.

Example 4: Travelling Salesman Problem (TSP)

Scenario:
A salesman must visit multiple cities exactly once and return to the starting city while minimizing the total travel distance
as shown in Fig. 2.1.

Fig. 2.1. Travelling salesman problem graph

Steps:

1. Generate: List all possible routes (permutations of cities).

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 5
 Introduction to AI and Applications (25CS1ETIAA)

2. Test: Calculate the total travel distance for each route.

3. Select: Choose the route with the minimum cost or distance.

Explanation:
This is a classic optimization problem where the goal is not just to find a solution, but the best solution (least cost or
shortest distance). Using generate-and-test, the algorithm systematically explores possible routes, evaluates each one, and
identifies the optimal path.

Step 1 – Generate All Possible Tours Starting at A

We have 3 remaining cities (B, C, D).

All possible permutations = 3! = 6 tours.

Tour No. Tour Path Calculation Total Distance

1 A → B → C → D → A A–B = 6, B–C = 3, C–D = 4, D–A = 5 6 + 3 + 4 + 5 = 18
2 A → B → D → C → A A–B = 6, B–D = 1, D–C = 4, C–A = 2 6 + 1 + 4 + 2 = 13
3 A → C → B → D → A A–C = 2, C–B = 3, B–D = 1, D–A = 5 2 + 3 + 1 + 5 = 11
4 A → C → D → B → A A–C = 2, C–D = 4, D–B = 1, B–A = 6 2 + 4 + 1 + 6 = 13
5 A → D → B → C → A A–D = 5, D–B = 1, B–C = 3, C–A = 2 5 + 1 + 3 + 2 = 11
6 A → D → C → B → A A–D = 5, D–C = 4, C–B = 3, B–A = 6 5 + 4 + 3 + 6 = 18

Step 2 – Choose Minimum Distance Tour

Minimum distance = 11

Two tours have the same minimum distance:

1. A → C → B → D → A
2. A → D → B → C → A

Final Answer

Best Route(s) Total Distance

A→C→B→D→A 11
A→D→B→C→A 11

2.3. Hill Climbing

Hill Climbing is a variant of the Generate-and-Test strategy where feedback from the test procedure is used to decide
which direction to move in the search space. Unlike the pure Generate-and-Test approach—which only checks whether a

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 6
 Introduction to AI and Applications (25CS1ETIAA)

generated solution is correct or not—Hill Climbing improves the process by using a heuristic function. A heuristic
function (h) gives an estimate of how close a particular state is to the goal state. This allows the algorithm to “climb”
towards better states step-by-step. Essentially, instead of generating random solutions, the algorithm uses the heuristic to
guide its search toward more promising directions.

Hill Climbing is particularly efficient because the heuristic can often be computed at almost no extra cost during the process
of testing a solution. It is widely used when a good heuristic function is available to evaluate the quality of different states,
even when no other problem-specific knowledge is known. For example, imagine you are lost in an unfamiliar city without
a map, but you can see the tops of tall buildings in the distance. If your goal is to reach downtown, you might simply move
toward those buildings. Here, the heuristic function could be the distance between your current location and the tall
buildings—and your objective is to minimize this distance.

Hill Climbing continues moving toward states that appear to bring it closer to the goal (or maximize some objective). The
process stops when:

1. The goal state is reached, or

2. There are no better (neighboring) states to move to — meaning a local maximum or plateau has been reached.

This method is particularly suitable for optimization problems, where we want to find the maximum or minimum of a
function, such as in the Travelling Salesman Problem. However, unlike some other algorithms, Hill Climbing does not
maintain a memory of previous states, so it can sometimes get “stuck” on local maxima or plateaus.

2.3.1. Key Characteristics of Hill Climbing

● Uses heuristic evaluation to choose the best next move.

● Works by iteratively improving the current state.

● Stops when there is no better move or the goal is reached.

● Effective for problems where absolute solutions exist and can be recognized easily (e.g., reaching a specific goal).

● Used in relative optimization problems such as route finding, scheduling, and parameter tuning in AI models.

2.3.2. Example

If the objective is to minimize the cost (e.g., distance, time, or error), Hill Climbing repeatedly selects the next state that
has the lowest heuristic value. If the objective is to maximize a score (e.g., profit or efficiency), it selects the highest
heuristic value instead.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 7
 Introduction to AI and Applications (25CS1ETIAA)

Fig.2.2. Hill climbing search graph

[image source: [Link]

The Hill Climbing Search Graph as shown in Fig. 2.2 visually represents how the algorithm progresses through the search
space. The graph usually shows the evaluation function (or fitness) on the y-axis and the possible states or solutions on the
x-axis.

● Global Maximum: The highest peak on the graph. It represents the best possible solution among all states.

● Local Maximum: A smaller peak where the algorithm may get stuck because all nearby moves lead to lower
values, even though it’s not the best overall solution.

● Plateau: A flat region where many neighboring states have the same value, making it hard for the algorithm to
decide which direction to move.

● Shoulder: A flat region followed by an uphill climb, which might confuse the search process initially but
eventually leads to improvement.

● Ridge: It is another particular type of local maximum, that is located between a better maximum and a minimum
of the state space diagram.

In practice, Hill Climbing is simple but can face problems such as getting trapped in local maxima, wandering aimlessly
on plateaus, or oscillating between similar states. Variants like Stochastic Hill Climbing, Random-Restart Hill Climbing,
and Simulated Annealing are used to overcome these limitations.

2.3.3. Limitations

● Can get trapped in local maxima or minima.

● May stop early at a plateau (flat region) where neighboring states have equal heuristic values.

● Does not guarantee the global optimum.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 8
 Introduction to AI and Applications (25CS1ETIAA)

2.3.4 Simple Hill Climbing

Simple Hill Climbing is the most basic form of the hill-climbing algorithm used in Artificial Intelligence. It works on a
local and greedy search approach and does not use backtracking. It is a heuristic search method that continually moves in
the direction of increasing value (or decreasing cost) to find a better solution. The algorithm compares the current state with
its neighboring states and moves to the neighbor that improves the evaluation function. If no better neighbor exists, the
search stops.

Algorithm: Simple Hill Climbing

1. Evaluate the initial state.

If it is already a goal state, stop and return it as the solution. Otherwise, mark it as the current state.
2. Repeat until a solution is found or no more operators are available to apply:
a. Select an operator that has not yet been tried on the current state to generate a new state.
b. Evaluate this new state:
o If it is a goal state → stop and return it.
o If it is better than the current state (i.e. higher heuristic for maximization, or lower cost for minimization)
→ make it the new current state.
o If it is not better → discard it and continue searching.

3. If no operator can improve the current state further, terminate (failure or local optimum).

The main difference between Simple Hill Climbing and Generate-and-Test is the use of a heuristic function. The heuristic
function provides guidance on which direction to move in the search space by estimating how close a given state is to the
goal. The algorithm asks the question: “Is one state better than another?” and uses the heuristic function to decide. The
definition of “better” can vary: in some cases, a higher heuristic value is better, while in others (such as cost-based
problems), a lower value is preferred.

Example: Four-Colored Blocks Puzzle

To understand hill climbing, consider a puzzle with four colored blocks.

● A heuristic function can be defined as the number of different colors on each of the four sides.

● The goal is to make all sides the same color, so a perfect solution would have a heuristic value of 16.

● The rules of transformation involve choosing a block and changing its color until the heuristic value improves.

This example illustrates how the algorithm evaluates each state and chooses the next one that seems closer to the goal,
making decisions step by step based on heuristic feedback.

Example:

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 9
 Introduction to AI and Applications (25CS1ETIAA)

1. Blocks World Example: Consider the blocks world problem with the block arrangement with the initial state and
the desired goal state as shown in Fig 2.3.

Fig. 2.3 Blocks World

Solution: This problem can be solved using 2 approaches:

1. Local heuristic function approach

2. Global heuristic function approach

1. Local heuristic function approach

- works on local information - i.e it considers only the adjacent/immediate blocks.

- As shown in Fig 2.4 it uses the local heuristic rules. After applying the local heuristic rules h(n) for initial state =
0 and h(n) = 4 for the goal state.
-

Fig 2.3 Simple Hill Climbing with Local Heuristic Rules

Step 1. To move towards the goal state, we need to apply the move operator to rearrange the blocks as shown by applying
the rules. As a result, the block arrangement is as shown. in Fig. 2.4. where h(n) = 0 for initial state and after placing block
A on ground the h(n) = 2 (new state) which is closer to the goal. So h(n) = 2 becomes the next current state.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 10
 Introduction to AI and Applications (25CS1ETIAA)

Fig 2.4. Rearranging the blocks h(n) = 0 and h(n) = 2- new state

Step 2. Continuing the algorithm, and rearranging the the blocks from the new current state h(n) = 2, we have 2 possible
new states

i. block D can be placed on block A or

ii. block D can be placed on ground

Fig 2.5. Rearranging the blocks h(n) = 2 and h(n) = 0- new possible states

In either case, h(n) evaluates to 0 ⇒ both the new states are not better than the current state with h(n) = 2 whereas the goal
state has h(n) = 4. The algorithm terminates here with a local optimum of h(n) = 2.

2: Global Heuristic Approach - uses global information i.e. considers all the blocks in the structure.

Fig 2.6. Global Heuristic Rules

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 11
 Introduction to AI and Applications (25CS1ETIAA)

Applying the global heuristic rules as shown in Fig 2.5 h(n) = -6 and h(n) = +6 for initial and goal state is calculated. Fig
2.6 shows the sequence of move operators which after applied results in the goal state.

Fig 2.7 Sequence of move operators after applying the global heuristic rules results in reaching towards the goal state.

[Link]. Advantages:

● Simple to implement.

● Requires less memory compared to other search methods.

● Works well for problems where the evaluation function gives clear direction.

[Link]. Limitations:

● Can get stuck at local maxima, plateaus, or ridges where no improvement appears possible.

● Lacks backtracking capability to recover from poor decisions.

2.4. Constraint Satisfaction

Constraint Satisfaction Problems (CSPs) form an important class of problems in Artificial Intelligence (AI), where the goal
is to find a solution that satisfies a given set of constraints. In such problems, a state is defined by assigning values to
variables while ensuring all constraints are met. Typical examples include cryptarithmetic puzzles, scheduling problems,
and design optimization tasks where constraints like time, cost, or materials are fixed.

A CSP can be visualized as a search problem that operates in a space of constraint sets. Initially, only the problem
constraints are known. As the solution progresses, additional constraints are discovered and propagated. The search
continues until either a consistent solution is found or an inconsistency is detected. For instance, in a cryptarithmetic puzzle
such as SEND + MORE = MONEY, each letter must represent a unique digit, and the sums of digits must match the
arithmetic rules.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 12
 Introduction to AI and Applications (25CS1ETIAA)

Examples of CSPs include:

● Cryptarithmetic puzzles (e.g., SEND + MORE = MONEY)

● Scheduling tasks (e.g., assigning time slots for classes)

● Map coloring (e.g., coloring countries so no two neighboring countries have the same color)

● Sudoku

● Many computer vision and resource allocation problems

CSPs are very important in AI because they represent a wide range of real-world problems that require reasoning,
planning, and optimization. Constraint satisfaction is preferred because it reduces unnecessary computation and allows
intelligent problem-solving. Instead of testing every possible combination, constraints narrow down the possible
solutions.

Advantages of using constraints:

● They reduce the search space drastically.

● They allow solving problems systematically and efficiently.

● They break large problems into smaller, manageable subproblems.

For example, in the cryptarithmetic problem SEND + MORE = MONEY,

each letter (S, E, N, D, M, O, R, Y) represents a digit from 0–9.
The constraints are:

● No two letters can have the same digit.

● The arithmetic sum must be correct (SEND + MORE = MONEY).

By applying these constraints, we rule out many invalid digit combinations.

2.4.1. Structure of a CSP

A Constraint Satisfaction Problem consists of three key components:

1. Variables – The unknowns we need to find values for.

Example: In SEND + MORE = MONEY, the variables are the letters S, E, N, D, M, O, R, Y.
2. Domains – The possible values that each variable can take.
Example: Each letter can take a digit value between 0–9.
3. Constraints – The conditions or rules that must be satisfied.
Example:

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 13
 Introduction to AI and Applications (25CS1ETIAA)

o All letters must have different digits.

o The arithmetic addition must hold true.

Goal:
Find a value for each variable from its domain such that all constraints are satisfied simultaneously.

Search in CSPs

To find a solution, a CSP search algorithm systematically explores combinations of variable assignments.
The process can be described as follows:

1. Select a variable that has not yet been assigned a value.

2. Choose a value from its domain.
3. Check if the assignment satisfies all constraints with the already assigned variables.
4. If it violates any constraint, backtrack and try another value.

This process continues until:

● All variables are assigned values that satisfy all constraints (success), or

● All combinations have been tried and none satisfy the constraints.

2.4.2. Backtracking Search Algorithm

The Backtracking Search is the most fundamental and widely used algorithm for solving CSPs. It is a depth-first
search that assigns values to variables one by one.

Steps in Backtracking Search:

1. Start with an empty assignment.

2. Select an unassigned variable.
3. Assign a value that does not violate any constraint.
4. If no valid value exists, backtrack to the previous variable and try another value.
5. Continue until either:
o A complete and valid assignment is found (solution), or
o All options are exhausted (no solution).

Example:
In Sudoku, you start filling the grid cell by cell:

● If a number violates Sudoku rules, remove it and backtrack.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 14
 Introduction to AI and Applications (25CS1ETIAA)

● Continue until the puzzle is solved.

2.4.3. General Constraint Satisfaction Algorithm

This algorithm generalizes the process of solving CSPs through constraint propagation and guessing:

1. Propagate Available Constraints:

o Begin with all variables in an OPEN list.
o Repeatedly apply constraints to reduce domains.
o If any domain becomes empty, a contradiction is found → backtrack.
2. Check for Solution:
o If all variables have exactly one possible value and constraints are satisfied, we have a solution.
3. Check for Contradiction:
o If constraints contradict (no possible assignment left), backtrack or return failure.
4. Guessing (Search):
o If still unresolved, make an informed guess.
o Choose a variable with multiple possible values.
o Assign a value and reapply constraint propagation recursively.

Note:
The stronger the constraint propagation, the fewer guesses are required.

Real-Life Analogy: Sudoku Example

In Sudoku:

● Propagation: Fill all obvious numbers using known rules.

● Guessing: When stuck, make a tentative assignment.

● Backtracking: If it leads to a contradiction, erase and try another number.

This is exactly how the CSP algorithm works — it combines logical deduction with trial and error.

CSP Summary

Concept Description
Variables Elements we must assign values to (e.g., letters, time slots, cells)
Domains Possible values for each variable (e.g., digits 0–9, colors)
Constraints Rules that limit valid assignments
Backtracking Systematically tries assignments, undoing invalid ones

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 15
 Introduction to AI and Applications (25CS1ETIAA)

Concept Description
Heuristics Smart strategies for variable/value selection
Inference Logical deduction to reduce possibilities
Goal Find an assignment that satisfies all constraints

2.4.4. Advantages of Constraint Satisfaction:

● Reduces the number of possible states compared to random search.

● Efficiently identifies invalid paths early, saving computation time.

● Flexible and applicable to many AI problems like Sudoku, map coloring, and logic puzzles.

2.4.5. Cryptarithmetic puzzle: SEND + MORE = MONEY

Problem statement (brief): Each letter stands for a distinct decimal digit (0–9). Leading letters (S and M) cannot be 0.
Find digits for S,E,N,D,M,O,R,Y so that:

SEND

+MORE

-----------

MONEY

Key idea: model columns (right → left) with carry variables C1..C4 (each 0 or 1). Use arithmetic column constraints plus
the AllDifferent constraint to deduce values, propagate constraints, then finish by inference/backtracking if needed.

Step-by-step deduction

Step-1: Introduce carries and equations (set up):

Let C1 be carry from units→tens, C2 from tens→hundreds, C3 from hundreds→thousands, C4 from thousands→ten-
thousands. Each Ci ∈ {0,1}. Column equations (right to left):

● Units: D + E = Y + 10·C1.

● Tens: N + R + C1 = E + 10·C2.

● Hundreds: E + O + C2 = N + 10·C3.

● Thousands: S + M + C3 = O + 10·C4.

● Leftmost: result has leading digit M, so C4 = M (but C4 ∈ {0,1} ⇒ M = 1).

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 16
 Introduction to AI and Applications (25CS1ETIAA)

Therefore: M = 1 and C4 = 1. (Important immediate deduction.)

Step-2: Use thousands column with M = 1:

From S + 1 + C3 = O + 10 (since C4 = 1), rearrange: O = S + C3 − 9. Because O must be a digit (0–9) and S ∈ {1..9}, test
C3 possibilities:

● If C3 = 0 → O = S − 9 ⇒ only possible if S = 9 ⇒ O = 0.

● If C3 = 1 → O = S − 8 ⇒ possible when S = 8 ⇒ O = 0, or S = 9 ⇒ O = 1 (but M = 1 so O ≠ 1).

Thus both valid subcases give O = 0, and either (S = 9, C3 = 0) or (S = 8, C3 = 1).

Step-3: Analyze hundreds column to decide C3:

Hundreds equation: E + O + C2 = N + 10·C3. With O = 0 this is E + C2 = N + 10·C3.

● If C3 = 1 → E + C2 = N + 10 ⇒ left side ≤ 9 + 1 = 10 so only possibility is E = 9 and C2 = 1 giving N = 0 — but

O = 0 already, conflict.

● Therefore, C3 = 0 must hold. From step 2, C3 = 0 ⇒ S = 9. Also hundreds reduce to E + C2 = N.

Step-4: Infer C2 and relation between N and E:

Since all letters are distinct, N ≠ E. From E + C2 = N we cannot have C2 = 0 (would give N = E). So C2 = 1 and N = E +
1. (Important relation.)

Step-5: Use tens column to find R and C1:

Tens: N + R + C1 = E + 10·C2. Substitute N = E + 1 and C2 = 1:
(E + 1) + R + C1 = E + 10 → R + C1 + 1 = 10 → R + C1 = 9.

Since digits are distinct and S = 9, R cannot be 9 ⇒ C1 cannot be 0. So C1 = 1 and R = 8.

Step-6: Use unit’s column to determine D, E, Y:

Units: D + E = Y + 10·C1. With C1 = 1, D + E = Y + 10 ⇒ Y = D + E − 10.
The remaining unused digits (after assigning M=1, O=0, S=9, R=8) are {2,3,4,5,6,7} for letters {E,N,D,Y}.

Also N = E + 1, so possible (E,N) pairs from the remaining set are (2,3),(3,4),(4,5),(5,6),(6,7). Try each:

● (2,3): D + 2 = Y + 10 ⇒ D = Y + 8 → D ≥ 8 impossible (8,9 used). Reject.

● (3,4): D = Y + 7 → D ≥ 7; remaining digits don't yield distinct valid pair. Reject.

● (4,5): D = Y + 6 → no valid distinct pair. Reject.

● (5,6): D = Y + 5 → possible if Y = 2 ⇒ D = 7 (both unused). Accept.

● (6,7): D = Y + 4 → no valid distinct pair. Reject.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 17
 Introduction to AI and Applications (25CS1ETIAA)

Therefore, only consistent choice: E = 5, N = 6, Y = 2, D = 7.

Step-7: Collect final assignments:

S = 9, E = 5, N = 6, D = 7,

M = 1, O = 0, R = 8, Y = 2

Step-8: Final verification (add up):

SEND = 9567

MORE = 1085

MONEY = 10652

Check: 9567 + 1085 = 10652 → correct. All letters distinct; leading digits nonzero.

2.5. Means–Ends Analysis (MEA)

Means–Ends Analysis (MEA) is a problem-solving strategy that helps an agent move from the current state to a goal
state by identifying and reducing the differences between the two. This approach is a combination of forward and
backward reasoning, where the system works on bridging the gap (means) between the current situation and the desired
outcome (ends). The term “means–ends” implies that every action (means) is chosen to reduce some difference that prevents
reaching the goal (end). The core idea of MEA is to:

1. Detect the differences between the current state and the goal state.
2. Identify an operator (action) that can reduce one or more of these differences.
3. If the operator cannot be applied immediately, a subgoal is created to satisfy its preconditions.
4. Continue this process until the current state matches the goal state.

This technique uses operator subgoaling, where subproblems are formed for each difference to make progress toward the
goal. Differences are prioritized — major differences are handled before smaller ones — making the search more efficient.

Example: Consider an example where we know the starting state and the desired state. In this issue, we must detect
differences between the beginning state and the goal state and apply operators to obtain the goal state.

To solve the problem, we will first identify the differences between starting and goal states, then construct a new state and
apply the operators to each difference. For this problem, we have the following operators:

 Move

 Delete

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 18
 Introduction to AI and Applications (25CS1ETIAA)

 Expand

1. Evaluating the initial state: In the first step, evaluate the initial state and compare it to the Goal state to
see what are the differences.

2. Applying the Delete operator: As observed, the first difference is that there's no dot symbol in the Goal
state, whereas there is in the initial state, so we'll use the Delete operator to remove it.

3. Applying the Move Operator: After using the Delete operator, a new state appears, which we will
compare to the objective state again. After comparing these states, we notice that the square is outside the
circle, so we'll use the Move Operator to fix it.

4. Applying the Expand Operator: In the third phase, a new state is created, and we will compare it to the desired state.
There is still one difference between the states, which is the size of the square, so we will use the Expand operator to
construct the desired state.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 19
 Introduction to AI and Applications (25CS1ETIAA)

Steps in Means–Ends Analysis

1. Compare the current state with the goal state.

o If there are no differences, the process stops — the goal is reached.
2. Select the most significant difference.
3. Choose an operator that can reduce or eliminate that difference.
4. Check whether the operator’s preconditions are satisfied.
o If not, create subgoals to achieve those preconditions.
5. Apply the operator to move toward the goal.
6. Repeat this process until all differences are removed.

To understand this concept practically, let us consider the Household Robot Problem, a classic example often used to
illustrate how MEA can be applied in a robotic domain. This example demonstrates how a robot can plan and execute a
series of actions to achieve a specific goal using logical reasoning.

2.5.1. Example: Simple Household Robot Problem

Consider a robot that needs to organize a room to achieve the goal:

"The cup is on the shelf, and the floor is clean."

Initial State:

 Cup is on the table.

 Floor is dirty.

Goal State:

 Cup on the shelf.

 Floor clean.

Operators:

 PickUp(Object)

 PutDown(Object, Location)

 Clean(Floor)

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 20
 Introduction to AI and Applications (25CS1ETIAA)

MEA Process:

1. Compare states → identify differences (cup misplaced, floor dirty).

2. Select difference “floor dirty.”

o Apply Clean(Floor) → new subgoal achieved.

3. Select next difference “cup on table.”

o Apply PickUp(Cup) followed by PutDown(Cup, Shelf).

4. Repeat until current state matches goal.

2.5.2. Example: Household Robot Domain Problem

Problem Statement

A robot is placed in a house and is given a set of tasks to perform. In this example, the robot’s task is to move a desk from
one room to another and place some objects on the desk. The robot must perform this task efficiently by reasoning about its
actions, understanding what prevents it from achieving the goal, and applying operators that can reduce these differences.

The goal state is that the desk should be placed at the desired location, and the required objects must be correctly positioned
on it. The current state is that the desk and objects are in their original locations, and the robot’s arm may or may not be
empty. The robot has a limited number of operators (actions) that it can perform, and each operator has certain preconditions
and results.

Goal:
Move a desk from one room to another.

Operators and Preconditions:

Operator Preconditions Result

PUSH(obj, loc) at(robot, obj), large(obj), clear(obj), arm empty at(obj, loc), at(robot, loc)
CARRY(obj, loc) at(robot, obj), small(obj) at(obj, loc), at(robot, loc)
WALK(loc) none at(robot, loc)
PICKUP(obj) at(robot, obj) holding(obj)
PUTDOWN(obj) holding(obj) not(holding(obj))
PLACE(obj1, obj2) at(robot, obj2), holding(obj1) on(obj1, obj2), not(holding(obj1))

Available Operators in the Robot’s Domain

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 21
 Introduction to AI and Applications (25CS1ETIAA)

The robot can perform six basic actions (operators):

1. PUSH(object, location) – To push large objects to a new location.

Preconditions: The robot and object must be at the same place, the object must be large and clear, and the robot’s
arm must be empty.
Result: Both the robot and object are moved to the new location.
2. CARRY(object, location) – To carry small objects from one place to another.
Preconditions: The robot and object must be at the same location, and the object must be small.
Result: The robot and the object are moved to the target location.
3. WALK(location) – To move the robot itself to another location.
Preconditions: None.
Result: The robot is now at the new location.
4. PICKUP(object) – To pick up an object from a surface.
Preconditions: The robot and object must be at the same location.
Result: The robot is holding the object.
5. PUTDOWN(object) – To put down an object being held.
Preconditions: The robot must be holding the object.
Result: The robot is no longer holding the object.
6. PLACE(object1, object2) – To place one object on top of another.
Preconditions: The robot must be at the location of the second object and must be holding the first object.
Result: The first object is placed on the second, and the robot’s arm becomes empty.

Applying Means–Ends Analysis

In Means–Ends Analysis, the robot begins by comparing the current state and the goal state to identify differences.
In this problem:

● The goal is to have the desk at its destination location and the objects placed on the desk.

● The current state is that the desk and robot are in different rooms, and the objects are not yet on the desk.

The key differences identified are:

1. The desk is not in the target room.

2. The objects are not on the desk.
3. The robot is not positioned near the desk.

The robot then chooses an operator that can reduce one of these differences.

The Difference Table is a vital component of the Means–Ends Analysis approach. It allows an intelligent system, such as
the household robot, to make informed decisions by linking specific differences in the problem state to relevant actions that

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 22
 Introduction to AI and Applications (25CS1ETIAA)

can resolve them. In the Household Robot Problem, this table enables the robot to plan its sequence of operations — from
walking to the desk, picking up objects, pushing the desk, and placing items — all while ensuring that each step
meaningfully reduces the difference toward achieving the goal state. Thus, the Difference Table is both a knowledge
representation tool and a decision-making aid, essential for efficient goal-directed problem solving in Artificial Intelligence.

When the robot encounters a difference, for example, “the object is not at the goal location”, it looks at the Difference
Table to identify which operators can handle that difference. The table indicates that both PUSH and CARRY can be used
to move an object. If the object is large, the robot applies the PUSH operator; if it is small, it uses CARRY. Similarly, when
the difference is “the robot is not near the object”, the table shows that WALK can resolve it by moving the robot to the
correct location. If the robot’s arm is not empty, PUTDOWN is the operator that reduces that difference. If the robot is not
holding an object that must be placed, PICKUP is selected.

Thus, the Difference Table provides a direct mapping between problems (differences) and solutions (operators). It
effectively guides the problem solver to select the most relevant and efficient action at each stage.

Difference Table

Action Push Carry Walk Pickup Putdown Place

Move object * *
Move robot *
Clear object *
Get object on object * *
Get arm empty *
Be holding object * *

From this table, the robot can easily identify which operator to apply based on the current difference.
For example:

● To move the object, use either PUSH or CARRY.

● To move itself, use WALK.

● To clear the object, use PICKUP.

● To get the arm empty, use PUTDOWN.

● To place an object, use PLACE.

This organization of knowledge eliminates confusion and helps the system make decisions that are both goal-directed and
efficient.

Solution

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 23
 Introduction to AI and Applications (25CS1ETIAA)

Current State: Desk and objects are in their original positions. Robot’s arm may not be empty

Goal State: Desk is in the destination room. Objects are correctly placed on the desk

Process using MEA:

Difference 1: The desk is not in the goal location.

The operator PUSH can move the desk. However, PUSH requires certain preconditions:

The robot must be at the desk.

The desk must be clear.

Since these preconditions are not yet satisfied, subgoals are created.

Subgoal 1: Move robot to the desk.

The operator WALK can satisfy this subgoal.

After applying WALK, the robot and desk are at the same location.

Subgoal 2: Clear the desk surface.

If there are objects on the desk, the operator PICKUP is used to remove them.

After applying PICKUP, the robot’s arm holds an object.

To make the arm empty again, PUTDOWN can be applied.

Now that preconditions are met, apply PUSH.

The robot pushes the desk to the target location, reducing the difference between the current and goal states.

Difference 2: Objects are not on the desk.

The operator PLACE can be used to put the objects on the desk.

However, the robot must be holding the object and be near the desk.

If it is not, PICKUP is used again to pick up the object, and WALK moves the robot to the desk’s new position.

Final Step: Apply PLACE.

The object is placed on the desk, and the robot’s arm becomes empty.

Now, the desk and objects are in their correct positions.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 24
 Introduction to AI and Applications (25CS1ETIAA)

Final Solution Sequence

1. PUSH → Pick up → Put down → Pick up → Put down → PUSH → PLACE.

This sequence achieves the goal step-by-step by reducing one difference at a time.

The progress of MEA method is shown in Fig. 2.8 and 2.9.

Fig. 2.8. The progress of MEA method

Fig. 2.9. More progress of MEA method

The Household Robot Problem effectively demonstrates how Means–Ends Analysis helps solve complex problems by
systematically reducing the differences between the current and goal states.
Instead of applying random actions, the robot uses a goal-directed reasoning process:

● It identifies what prevents it from reaching the goal.

● It creates subgoals when necessary.

● It uses appropriate operators to progress step-by-step toward the goal.

This method of problem solving mirrors how humans approach tasks — by first identifying obstacles and then planning
steps to remove them.

2.5.3. Advantages of MEA

● Reduces the complexity of problem-solving by focusing on differences.

● Works well for goal-directed reasoning.

● Helps in planning and robotic applications.

● Uses recursive decomposition — solving smaller subproblems efficiently.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 25
 Introduction to AI and Applications (25CS1ETIAA)

2.5.4. Limitations

● May become inefficient for very complex problems with many interrelated subgoals.

● Performance depends heavily on the quality of the difference table and operator definitions.

● Not suitable when subgoals interfere with each other.

2.6. When to Adopt a Heuristic Function – Comparison with Exhaustive Search

A heuristic function is adopted when a problem’s search space is very large and it becomes computationally expensive or
impractical to explore every possible solution. In Artificial Intelligence, many real-world problems such as route finding,
scheduling, and game playing involve an enormous number of possible states or paths. Searching through every state using
an exhaustive method would take excessive time and memory. To overcome this limitation, heuristics are used as intelligent
estimators or guiding functions that evaluate which paths or actions are likely to lead closer to the goal. The heuristic
function, usually denoted as h(n), estimates the “cost” or “distance” from a given state n to the goal state. It does not compute
the exact cost but provides an approximate measure to guide the search efficiently.

Heuristic functions are most suitable when:

1. The problem space is large or complex, making it infeasible to explore all possible states.

2. There is some domain knowledge or prior experience available that can guide the search toward the goal.

3. The goal state is well-defined, and there exists a meaningful way to estimate “how far” a current state is from the
goal.

4. The problem demands a good (near-optimal) solution quickly, even if it is not guaranteed to be the absolute best.

For instance, in pathfinding problems like Google Maps navigation, heuristics such as the straight-line distance to the
destination help find efficient routes faster. In contrast, an exhaustive search approach—such as Breadth-First Search (BFS),
Depth-First Search (DFS), or Uniform Cost Search—explores every possible path or state systematically until it finds the
goal. While exhaustive methods guarantee an optimal solution, they are often computationally infeasible for large or
dynamic problems due to combinatorial explosion (the rapid growth of possibilities). Therefore, exhaustive search is best
used when:

 The search space is small and well-defined,

 The computation time is not a concern, and

 An exact or optimal solution is required.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 26
 Introduction to AI and Applications (25CS1ETIAA)

Heuristic search, on the other hand, sacrifices completeness and optimality in favor of efficiency and practicality. It is
particularly useful when the environment is partially observable, complex, or when timely decisions are critical — such as
in robotics, game AI, and expert systems.

Thus, the decision to adopt a heuristic function depends on the trade-off between accuracy and efficiency. When the goal is
to achieve a good, near-optimal result quickly using limited computational resources, heuristic search is preferred. When
the goal demands the absolute best solution and the search space is small, exhaustive search may still be suitable.

Comparison of Heuristic Techniques

Technique Main Idea When to Use Advantages Limitations

Generate & Try all possible solutions Small, finite Simple; easy to Inefficient for large
Test and test each. problems. code. problems.

Move toward better state Faster, directed Stuck in local maxima or

Hill Climbing Optimization tasks.
using evaluation. search. plateaus.

Constraint Assign values to satisfy all Scheduling, map Prunes invalid Complex with many
Satisfaction constraints. coloring, Sudoku. states early. interdependent constraints.

Reduce difference
Means–Ends Focused, goal- Needs defined operators
between current and goal Planning, robotics.
Analysis driven reasoning. and subgoals.
states.

2.7. Knowledge Representation (KR)

Knowledge Representation (KR) is one of the fundamental areas of Artificial Intelligence concerned with how knowledge
about the world can be formally expressed, stored, and used by intelligent systems. It focuses on designing methods to
encode real-world information—facts, concepts, relationships, and processes—into a structured and symbolic format that
an AI system can interpret and reason with. Simply put, KR gives data meaning and context, allowing computers to
“understand” and manipulate information rather than just storing it.

The goal of KR is to move from raw, unorganized data to structured knowledge, much like converting a random string of
letters into a meaningful word. To achieve this, a formal representation language such as Propositional Logic (PL) or First-
Order Logic (FOL) is used to define facts, rules, and relationships about objects and events in the world. These languages
provide a clear syntax (structure) and semantics (meaning), enabling machines to represent knowledge in a precise, machine-
readable manner. Knowledge Representation, therefore, forms the foundation for reasoning and intelligent decision-making
in AI. Without a well-defined structure to represent what an AI “knows,” it cannot reason, plan, or act effectively.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 27
 Introduction to AI and Applications (25CS1ETIAA)

2.7.1. Importance of Knowledge Representation in AI

Knowledge Representation is the cornerstone of intelligent behavior in AI systems. Just as human intelligence relies on
memory, logic, and understanding, an AI agent requires an explicit and organized representation of knowledge to simulate
human-like reasoning. The importance of KR can be summarized as follows:

 Enables Reasoning and Inference: KR provides both the content (facts) and rules (logic) needed for automated
reasoning. Using logical inference methods such as deduction, an AI system can derive new facts from existing
ones. Example: If the system knows “All cats are mammals” and “Garfield is a cat,” it can logically infer “Garfield
is a mammal.” This demonstrates how knowledge representation supports intelligent reasoning.
 Facilitates Problem Solving: Many AI applications—such as medical diagnosis, robotic navigation, and expert
systems—require the ability to relate objects, actions, and outcomes. KR structures this information, enabling the
system to analyze situations and choose appropriate actions. For instance, a robot that knows “if the floor is wet,
avoid moving fast” can apply this rule to prevent accidents.
 Enhances Communication and Interpretation: In Natural Language Processing (NLP), AI systems must interpret
human language accurately. KR helps bridge the gap between ambiguous natural language and the precise internal
representations that computers require. It allows systems like chatbots and virtual assistants to map human questions
into logical structures and respond intelligently.

Supports Learning and Adaptation: A well-organized knowledge base allows AI systems to update and refine their
understanding as new information is received. This promotes incremental learning, where old knowledge is modified or
expanded instead of being replaced entirely. As a result, the AI becomes more adaptive and capable of handling dynamic
environments.

2.8. Knowledge-Based Agents

Humans possess intelligence not merely because they can react reflexively to stimuli, but because they have the ability to
store, represent, and reason with knowledge. What humans know helps them to understand situations, draw conclusions,
and make informed decisions. This concept forms the foundation of knowledge-based systems in AI. A knowledge-based
agent is an intelligent system that acts by reasoning over an internal representation of knowledge about the world. Instead
of responding blindly to inputs, such an agent uses stored information and logical inference to decide the most appropriate
action in a given situation.

A knowledge-based agent consists of two key components — a knowledge base (KB) and an inference mechanism. The
knowledge base is a collection of facts, rules, and representations about the world, stored in a structured form. The inference
mechanism is responsible for applying logical reasoning to the knowledge base to derive new information or to decide on
actions. These agents work in a cycle of perceive–infer–act: they perceive the environment, use inference to deduce what is
true or what should be done, and then act accordingly. Over time, they can also learn by updating their knowledge base with
new facts.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 28
 Introduction to AI and Applications (25CS1ETIAA)

In the chapter, the concept of knowledge-based agents is introduced using a simple example called the Wumpus World.
This environment illustrates how an intelligent agent can survive by reasoning logically about what it perceives, even when
it lacks complete information. The Wumpus World helps to understand how an agent can use logical reasoning to infer
hidden aspects of the environment, such as the presence of danger or treasure, from indirect sensory evidence.

To formally describe and reason about such environments, AI uses logic as the mathematical foundation for knowledge
representation. Propositional logic, though less expressive than first-order logic, provides a clear and structured way to
illustrate the basic principles of logical reasoning. It allows agents to represent knowledge using propositions (statements
that can be true or false) and apply inference rules to deduce new information. More advanced agents use first-order logic,
which can represent relationships between objects and handle more complex forms of reasoning.

By integrating logical reasoning with knowledge representation, knowledge-based agents are capable of planning, learning,
and decision-making. They form the basis for intelligent systems in various domains, such as expert systems, natural
language understanding, and autonomous robotics. Understanding how these agents work provides a strong foundation for
students to explore advanced AI topics like reasoning under uncertainty, learning-based decision systems, and automated
[Link].

2.8.1. Knowledge Base and Knowledge-Based Agent

The knowledge base (KB) is the central component of a knowledge-based agent. It acts as the “brain” of the agent — a
structured repository of information about the world. A knowledge base consists of a set of sentences, each representing
some fact, rule, or relationship about the environment. These sentences are not in natural language (like English) but are
expressed in a Knowledge Representation Language (KRL), which allows precise and unambiguous reasoning. Each
sentence or statement in the KB is an assertion about the world, and when a sentence is assumed to be true without proof, it
is called an axiom.

A knowledge-based agent interacts with its environment by adding new knowledge and querying existing knowledge. Two
main operations are used to manage this process:

 TELL: Adds new sentences (information) to the knowledge base. It represents the agent’s ability to learn or update
its understanding of the world based on its perceptions.

 ASK: Queries the knowledge base to derive conclusions or make decisions. It enables the agent to reason about
what action should be taken next based on what it already knows.

Both TELL and ASK operations rely on inference, which is the process of deriving new sentences (knowledge) from existing
ones using logical rules. A valid inference ensures that whatever the system concludes must logically follow from what it
already knows; the agent must not “make things up.” This logical soundness is what distinguishes intelligent reasoning from
guesswork.

In simple terms, the knowledge-based agent works in a continuous Perceive–Think–Act cycle:

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 29
 Introduction to AI and Applications (25CS1ETIAA)

 The agent perceives the environment through sensors and TELLs this information to the knowledge base.

 It then ASKs the knowledge base to determine the best action based on the current state and accumulated
knowledge.

 Finally, it TELLs the knowledge base which action was performed so that this new information becomes part of its
experience for future reasoning.

This continuous interaction allows the agent to function intelligently, making decisions not just from current perceptions
but also from previously acquired knowledge and logical deductions. Over time, the KB grows richer, enabling the agent to
handle more complex problems.

The overall design of a knowledge-based agent demonstrates the integration of knowledge representation and reasoning —
two key pillars of Artificial Intelligence. It serves as the foundation for intelligent systems such as expert systems, diagnostic
systems, and decision-making agents used in robotics and data-driven automation.

2.9. The Wumpus World

The Wumpus World is a classic example used in Artificial Intelligence to illustrate how a knowledge-based agent can make
intelligent decisions in a partially observable and uncertain environment as shown in Fig. 2.10. It is a grid-based environment
consisting of interconnected rooms or cells, representing a cave system. The world contains various elements—some
helpful, others dangerous—that the agent must detect, reason about, and act upon using its knowledge and percepts.

Fig. 2.10. A typical wumpus world. The agent is in the bottom left corner, facing right

2.9.1. Description of the Environment

The Wumpus World is designed as a 4×4 grid of rooms, each of which may contain one of the following:

 The Wumpus – a deadly monster that eats any agent entering its room.

 Bottomless pits – traps that cause instant death if the agent falls in.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 30
 Introduction to AI and Applications (25CS1ETIAA)

 Gold – the desirable goal that the agent must find and bring back to the starting point.

 Empty rooms – safe spaces where the agent can move.

The agent starts in the lower-left corner, represented as [1,1], facing east (right). The goal of the agent is to find the gold
and return safely to the starting square while avoiding the Wumpus and pits. The agent has limited abilities and
information and must use reasoning to infer the safest actions.

2.9.2. PEAS Description of the Wumpus World

In AI, environments are defined using the PEAS framework — Performance measure, Environment, Actuators, and
Sensors.

For the Wumpus World, the PEAS components are as follows:

1. Performance Measure

The agent’s success is evaluated based on a scoring system:

 +1000 for climbing out of the cave with the gold.

 –1000 for dying (by falling into a pit or being eaten by the Wumpus).

 –1 for each action taken (to discourage random exploration).

 –10 for shooting the arrow (since it’s a limited resource).

The game ends when the agent dies or climbs out of the cave.

2. Environment

 A 4×4 grid of rooms. The Wumpus and gold are placed randomly in squares other than the starting square. Each
non-starting room can independently contain a pit with 20% probability (0.2).

 The world is static — the Wumpus and pits don’t move.

 The world is partially observable, as the agent can sense but not directly see hazards.

3. Actuators (Actions)

The agent can perform the following actions:

 Move Forward – moves ahead one square unless blocked by a wall.

 Turn Left / Turn Right – rotates the agent’s facing direction by 90°.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 31
 Introduction to AI and Applications (25CS1ETIAA)

 Grab – picks up the gold if it is in the current room.

 Shoot – fires an arrow straight in the current direction; it can kill the Wumpus if hit. The agent has only one
arrow.

 Climb – exits the cave (only from the start position [1,1]).

If the agent enters a square with a pit or live Wumpus, it dies immediately. However, entering a square with a dead
Wumpus is safe, though smelly.

4. Sensors (Percepts)

The agent receives sensory information as a list of five percepts, each represented by a symbol:

 Stench – perceived in the room containing the Wumpus or adjacent rooms.

 Breeze – perceived in rooms adjacent to a pit.

 Glitter – perceived in the room containing the gold.

 Bump – perceived when the agent walks into a wall.

 Scream – heard everywhere in the cave when the Wumpus is killed.

Each percept provides one bit of information, helping the agent infer what might exist in nearby rooms.

Example: [Stench, Breeze, None, None, None] means the agent senses both a stench and a breeze, suggesting a nearby
Wumpus and pit.

2.9.3. Significance of the Wumpus World

The Wumpus World is a foundational problem in AI because it demonstrates how logical reasoning and knowledge
representation help agents make intelligent decisions under uncertainty. It helps to understand:

 How an agent perceives its environment using limited sensors?

 How knowledge-based reasoning (using propositional logic) can help deduce safe moves.

 How intelligent behavior emerges through systematic inference rather than random guessing.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 32
 Introduction to AI and Applications (25CS1ETIAA)

2.10. Propositional Logic – A Very Simple Logic

Propositional Logic, also known as Sentential Logic or Propositional Calculus, is one of the most fundamental and simplest
forms of logic used in Artificial Intelligence (AI). It provides a formal way to represent and reason about knowledge through
statements (propositions) that can be either true or false. Propositional logic is widely used in knowledge-based agents and
reasoning systems, particularly within environments like the Wumpus World, where agents must draw conclusions based
on limited and uncertain information.

Introduction to Propositional Logic

Humans make intelligent decisions by reasoning about facts, and propositional logic captures this process through
propositions—statements that describe something about the world. For example, in the Wumpus World:

“There is a pit in square [1,3]” can be represented as P₁,₃.

“The Wumpus is in square [2,2]” can be written as W₂,₂.

Each proposition can only have two possible truth values—True (T) or False (F).

Hence, propositional logic forms the foundation for representing knowledge in AI and performing logical inference
(deriving new truths from known facts).

2.10.1. Syntax of Propositional Logic

The syntax of propositional logic defines how valid sentences are formed. These sentences are constructed using:

 Atomic sentences, which are the simplest statements (basic propositions).

 Complex sentences, which are formed by combining atomic sentences using logical connectives.
1. Atomic Sentences

An atomic sentence consists of a single propositional symbol, such as: P, Q, R, W₁,₃, North, etc.

Each symbol represents a distinct fact or statement that can be either true or false.

For instance:

W₁,₃ means “The Wumpus is in room [1,3].”

Here, W₁,₃ is treated as a single, indivisible symbol (not the combination of W, 1, and 3).

Two special atomic symbols are predefined:

 True – always true.

 False – always false.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 33
 Introduction to AI and Applications (25CS1ETIAA)

2. Logical Connectives

Complex sentences are formed by combining atomic sentences using logical connectives. There are five main logical
connectives in propositional logic:

Symbol Name Meaning / Explanation

Example

¬ Negation (NOT) ¬W₁,₃ Represents “It is not the case that the Wumpus is in
[1,3].”

∧ Conjunction (AND) W₁,₃ ∧ P₃,₁ True if both W₁,₃ and P₃,₁ are true.

∨ Disjunction (OR) (W₁,₃ ∧ P₃,₁) ∨ W₂,₂ True if at least one of the disjuncts is true.

⇒ Implication (IF–THEN) (W₁,₃ ∧ P₃,₁) ⇒ Represents “If W₁,₃ and P₃,₁ are true, then W₂,₂ is
¬W₂,₂ false.”

⇔ Biconditional (IF AND ONLY W₁,₃ ⇔ ¬W₂,₂ True when both sides have the same truth value.
IF)

3. Types of Logical Sentences

A literal is either an atomic sentence (positive literal) or a negated atomic sentence (negative literal). Example: W₁,₃ and
¬W₁,₃ are literals. A conjunction uses ∧ (AND) and joins multiple conditions. A disjunction uses ∨ (OR) and represents
alternative possibilities. An implication represents cause-and-effect relationships and is also known as a rule or if–then
statement. Example: “If there is a breeze, then there must be a pit nearby.” A biconditional (⇔) states that both sentences
are equivalent in truth value.

Example from the Wumpus World

In the Wumpus World, propositional logic can represent rules that guide the agent’s reasoning:

 Rule 1: If there is a breeze in [1,2], then there must be a pit in an adjacent square: B₁,₂ ⇒ (P₁,₁ ∨ P₂,₂ ∨ P₁,₃)

 Rule 2: If there is no breeze in [1,1], then all adjacent squares are safe: ¬B₁,₁ ⇒ (¬P₁,₂ ∧ ¬P₂,₁)

These sentences illustrate how propositional logic allows the agent to reason about unseen dangers and plan safe moves.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 34
 Introduction to AI and Applications (25CS1ETIAA)

2.10.2. Semantics in Propositional Logic

After understanding the syntax of propositional logic—which defines how valid logical sentences are formed—the next
important concept is semantics. The semantics of propositional logic provides the rules that determine the truth or falsity of
logical sentences with respect to a particular model. In other words, semantics gives meaning to logical symbols by
specifying how their truth values are evaluated.

1. Meaning of Semantics

In propositional logic, a model represents a specific assignment of truth values (True or False) to each propositional symbol.
The truth value of a sentence is then computed based on these assignments.

For example, consider a model m₁:

m₁ = {P₁,₂ = False, P₂,₂ = False, P₃,₁ = True}

Here, we have three proposition symbols, and each has been assigned a truth value. Since there are three propositions, there
can be 2³ = 8 possible models representing all possible combinations of truth assignments.

These models are mathematical structures that describe possible situations in the world. The meaning of symbols like P₁,₂
depends on how we interpret them. For example, P₁,₂ could mean “There is a pit in [1,2]” in the Wumpus World, or it could
mean “It will rain tomorrow” in another context. Hence, semantics provides a way to evaluate logical sentences
independently of their real-world meaning.

2. Truth Value Assignment

The truth value of a sentence in propositional logic is determined recursively. Since every logical sentence is built using
atomic propositions and logical connectives (¬, ∧, ∨, ⇒, ⇔), the semantics must define the truth conditions for:

Atomic sentences, and Complex sentences formed using connectives.

Rules for Atomic Sentences

 The sentence True is always true in every model.

 The sentence False is always false in every model.

 Every other proposition symbol (e.g., P₁,₂) gets its truth value directly from the model.

Example: In m₁, the truth of P₁,₂ is False.

3. Rules for Complex Sentences

For any two sentences P and Q, and any model m, the truth of compound statements is determined as follows:

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 35
 Introduction to AI and Applications (25CS1ETIAA)

Sentence Type Truth Condition (in model m)

¬P (Negation) True iff P is False in m.

P ∧ Q (Conjunction) True iff both P and Q are True in m.

P ∨ Q (Disjunction) True iff either P or Q (or both) are True in m.

P ⇒ Q (Implication) True unless P is True and Q is False in m.

P ⇔ Q (Biconditional) True iff both P and Q have the same truth value (both true or both false).

4. Truth Tables

Truth tables are a systematic way to represent the semantics of logical connectives. Each row of a truth table represents a
possible combination of truth values of propositions, and the resulting truth value of the compound sentence.

P Q ¬P P ∧ Q P ∨ Q P ⇒ Q P ⇔ Q

F F T F F T T

F T T F T T F

T F F F T F F

T T F T T T T

These tables can be used to evaluate any propositional sentence.

Example:

Evaluate ¬P₁,₂ ∧ (P₂,₂ ∨ P₃,₁) in model m₁ = {P₁,₂ = F, P₂,₂ = F, P₃,₁ = T}.

 Step 1: ¬P₁,₂ → ¬F = T

 Step 2: (P₂,₂ ∨ P₃,₁) → (F ∨ T) = T

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 36
 Introduction to AI and Applications (25CS1ETIAA)

 Step 3: T ∧ T = T

Therefore, the sentence evaluates to True in model m₁.

5. Understanding Implication and Biconditional

The semantics of implication (⇒) can sometimes feel unintuitive. The statement P ⇒ Q means “If P is true, then Q must
also be true.”

It is false only when P is true and Q is false, and true in all other cases, even if P is false.

Example:

 “If it rains, then the road is wet.” (True implication)

 “If 5 is even, then Sam is smart.” (True in propositional logic, because the antecedent is false.)

Hence, implication does not require a causal relation between P and Q—it simply defines a logical dependency.

The biconditional (⇔) represents “if and only if,” meaning both statements must always share the same truth value.

It is true when both P and Q are true, or both are false.

Example from the Wumpus World:

A square is breezy if and only if there is a pit in an adjacent square.

This can be represented as:

B₁,₁ ⇔ (P₁,₂ ∨ P₂,₁)

Here, B₁,₁ means there is a breeze in room [1,1]. This biconditional statement captures both directions of logical
dependence—

 If there is a breeze, then at least one neighboring square has a pit.

 If there is a pit nearby, there will be a breeze in the current square.

6. Exclusive OR (XOR)

In addition to the standard connectives, there is also the exclusive OR (XOR), denoted as ⊕.

In exclusive OR, the result is True only when one of the two statements is true, but not both. This differs from the normal
disjunction (∨), which is true even if both are true.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 37
 Introduction to AI and Applications (25CS1ETIAA)

2.10.3. A Simple Knowledge Base in the Wumpus World

Once the semantics of propositional logic are clearly defined, we can apply them to build a knowledge base (KB) for an
artificial intelligence agent operating in the Wumpus World. A knowledge base is a collection of logical sentences that
describe what the agent knows about its environment. Each sentence in the KB is expressed in propositional logic, using
symbols to represent facts and logical relationships between those facts.

In the Wumpus World, each room in the cave is represented by its coordinates [𝑥,𝑦], and a set of propositional symbols is
used to describe what might be true in each room. For every grid cell, we define the following symbols:

 Pₓ,ᵧ: True if there is a pit in the location [x,y].

 Wₓ,ᵧ: True if there is a wumpus (alive or dead) in [x,y].
 Bₓ,ᵧ: True if the agent perceives a breeze in [x,y].
 Sₓ,ᵧ: True if the agent perceives a stench in [x,y].

Each of these symbols represents an atomic proposition, and logical sentences involving these symbols describe the
relationships and constraints of the world.

The goal of the knowledge base is to help the agent reason logically about what it perceives (through sensors like breeze or
stench) and make safe decisions—for example, determining which adjacent rooms are safe to move into. The agent achieves
this by using inference, that is, deriving new knowledge (new sentences) from the existing knowledge base.

Example: Constructing a Simple Knowledge Base

To illustrate this, we can construct a small knowledge base that captures the immutable rules of the Wumpus World — those
facts that always hold true regardless of the agent’s movements. These rules form the foundation for logical reasoning.

Each rule is represented as a propositional sentence, labeled R₁, R₂, R₃, etc., for easy reference.

R₁: There is no pit in the starting square.

The agent always begins in a safe position, so there cannot be a pit in cell [1,1].
Hence, the first rule is:
R₁: ¬P₁,₁
This means “There is no pit in [1,1].”

R₂: Relationship between breeze and neighboring pits (for square [1,1])

A square is breezy if and only if there is a pit in one of its adjacent squares. This relation is represented using the
biconditional (⇔) operator.
For the square [1,1]:
R₂: B₁,₁ ⇔ (P₁,₂ ∨ P₂,₁)

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 38
 Introduction to AI and Applications (25CS1ETIAA)

This means: “There will be a breeze in [1,1] if and only if there is a pit either in [1,2] or [2,1].”
The use of the biconditional ensures the relation works both ways — if a breeze exists, there must be a pit nearby, and if
there is a pit nearby, there will be a breeze in the current square.

R₃: Relationship for the next square ([2,1])

Similarly, for square [2,1], the breeze depends on the existence of pits in any of its neighboring squares:
R₃: B₂,₁ ⇔ (P₁,₁ ∨ P₂,₂ ∨ P₃,₁)
This rule means: “There will be a breeze in [2,1] if and only if there is a pit in [1,1], [2,2], or [3,1].”

R₄ and R₅: Percepts from the agent’s experience

While R₁–R₃ represent general rules that hold for all possible Wumpus Worlds, the next two sentences represent the specific
percepts that the agent actually experiences during its exploration.

 R₄: ¬B₁,₁ → The agent perceives no breeze in [1,1].

This means there are no pits adjacent to the starting square.

 R₅: B₂,₁ → The agent perceives a breeze in [2,1].

This tells us that at least one of the neighboring squares to [2,1] contains a pit.

2.10.4. Logical Inference from the Knowledge Base

Using these rules, the agent can infer new information. For example:

1. From R₁ (¬P₁,₁), we know the starting square is safe.

2. From R₂ and R₄, since B₁,₁ is false, we conclude that both P₁,₂ and P₂,₁ must be false.
¬B₁,₁ ⇒ ¬(P₁,₂ ∨ P₂,₁)
Therefore:
¬P₁,₂ ∧ ¬P₂,₁
Meaning there are no pits in [1,2] and [2,1].

This simple inference shows how propositional logic helps an AI agent deduce safe squares to move into using logical
reasoning, rather than random exploration.

Summary of Rules in the Knowledge Base

Rule Logical Sentence Meaning

R₁ ¬P₁,₁ No pit in [1,1]

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 39
 Introduction to AI and Applications (25CS1ETIAA)

R₂ B₁,₁ ⇔ (P₁,₂ ∨ P₂,₁) Breeze in [1,1] ↔ Pit in [1,2] or [2,1]

R₃ B₂,₁ ⇔ (P₁,₁ ∨ P₂,₂ ∨ P₃,₁) Breeze in [2,1] ↔ Pit in one of its neighboring squares

R₄ ¬B₁,₁ No breeze in [1,1]

R₅ B₂,₁ Breeze present in [2,1]

This example demonstrates how a knowledge-based agent builds and updates its knowledge base using logic.

 The immutable rules (R₁–R₃) define how the environment behaves.

 The mutable rules (R₄–R₅) capture the agent’s real-time observations.

By applying inference, the agent can derive new knowledge, such as determining safe paths or identifying
possible hazards. This logical reasoning is what makes knowledge-based AI systems powerful and explainable.

2.10.5. A Simple Inference Procedure

In artificial intelligence, one of the most fundamental reasoning tasks for a knowledge-based agent is inference — the
process of determining whether a particular sentence (called a query) logically follows from a given Knowledge Base (KB).
This relationship is written as KB ⊨ α, which is read as “KB entails α”.

In simple terms, this means that the sentence α must be true in every situation (model) in which all the sentences of the KB
are true. The inference procedure helps an intelligent agent verify this logical relationship and make rational decisions based
on what it knows.

1. Model Checking and Entailment

To test whether KB ⊨ α, a straightforward approach is to use a model-checking method. A model represents one possible
configuration of truth values (True or False) assigned to all the propositional symbols in the knowledge base.
If there are n symbols in total, there can be 2ⁿ possible models, because each symbol can independently take one of two
truth values.

The inference process using model checking involves three steps:

1. Enumerate all possible models – For each model, assign truth values (True/False) to all propositional symbols.

2. Check which models make the KB true.

3. Verify if α is true in all those models.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 40
 Introduction to AI and Applications (25CS1ETIAA)

o If α is true in every model where KB is true → KB ⊨ α (entailment holds).

o If α is false in any model where KB is true → entailment does not hold.

Example: The Wumpus World Inference

In the Wumpus World, the agent’s knowledge base (KB) includes logical sentences such as:

 R₁: ¬P₁,₁ → There is no pit in [1,1]

 R₂: B₁,₁ ⇔ (P₁,₂ ∨ P₂,₁)

 R₃: B₂,₁ ⇔ (P₁,₁ ∨ P₂,₂ ∨ P₃,₁)

 R₄: ¬B₁,₁

 R₅: B₂,₁

We now want to check whether the knowledge base entails the sentence:
α = ¬P₁,₂ (i.e., there is no pit in [1,2]).

To do this, we construct a truth table containing all possible combinations of truth values for the relevant symbols:
B₁,₁, B₂,₁, P₁,₁, P₁,₂, P₂,₁, P₂,₂, P₃,₁.

Since there are 7 symbols, the total number of models is 2⁷ = 128.

For each model, we evaluate whether all rules (R₁–R₅) are true simultaneously — this determines whether the KB as a
whole is true in that model.

Inference from the Truth Table

After evaluating all 128 models, it is found that:

 The KB (R₁–R₅) is true in 3 models.

 In all 3 of these models, P₁,₂ is false.

Therefore, ¬P₁,₂ is true in every model where KB is true.
Hence, we can conclude that:
KB ⊨ ¬P₁,₂
→ There is no pit in [1,2].

However, in these same 3 models, P₂,₂ is true in two models and false in one.
Thus, the agent cannot determine whether a pit exists in [2,2]; the available knowledge is insufficient for that conclusion.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 41
 Introduction to AI and Applications (25CS1ETIAA)

This kind of reasoning demonstrates how a knowledge-based agent makes logical inferences by evaluating all possible
worlds that are consistent with its knowledge base.

2.11. Introduction to First-Order Logic (FOL)

In Artificial Intelligence, logic-based knowledge representation allows an intelligent agent to reason about the world and
make informed decisions. Learnt on how a knowledge-based agent uses Propositional Logic (PL) to represent facts and
deduce actions based on those facts. Propositional Logic served as a useful foundation to introduce the basic principles of
logical reasoning, inference, and knowledge-based systems. However, Propositional Logic is limited in its expressive
power—it can represent only specific, fixed facts about the world but cannot easily describe general relationships,
objects, or their properties. For instance, while PL can express “Socrates is mortal,” it cannot represent the general
rule “All humans are mortal” that applies to many individuals.

To overcome these limitations, Artificial Intelligence uses First-Order Logic (FOL), also known as Predicate Logic or First-
Order Predicate Calculus (FOPC). FOL extends Propositional Logic by introducing quantifiers and predicates, which
make it more expressive and capable of representing a large amount of commonsense and relational knowledge. In
FOL, objects, their relationships, and their properties can be described using variables and functions.

For example, the statement “All humans are mortal” can be represented as:

∀x (Human(x) → Mortal(x))

which means “For all x, if x is a human, then x is mortal.” This concise representation shows how FOL can generalize
statements that would require many individual propositions in Propositional Logic.

2.11.1. The strengths of First-Order Logic:

1. Ability to describe complex environments,
2. Reason about multiple entities, and
3. Support generalized inference.
4. It serves as a foundation for various advanced knowledge representation techniques used in AI.
5. Because of its expressive power and mathematical rigor, FOL has been studied extensively and remains a
cornerstone of formal reasoning in Artificial Intelligence.

2.11.2. Syntax and Semantics of First-Order Logic (FOL)

In Artificial Intelligence, First-Order Logic (FOL) provides a powerful framework to represent knowledge about the real
world using objects, their properties, and relationships. To understand how FOL works, let’s explore its syntax (the
structure and symbols used to form sentences) and semantics (the meaning and interpretation of those sentences in possible
worlds or models). A model in logic represents a possible world that defines what is true or false.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 42
 Introduction to AI and Applications (25CS1ETIAA)

In Propositional Logic, models only map proposition symbols (like P or Q) to truth values (True or False). However, in
First-Order Logic, models are richer—they consist of objects, relations, and functions that describe how entities interact in
a particular world.

1. Models and the Domain

The domain of a model is the set of all objects or domain elements that exist in that world. Every model in FOL must have
at least one object (i.e., the domain is non-empty). For example, consider a simple world that contains the following five
objects as shown in Fig. 2.11.

 Richard the Lionheart (King of England from 1189 to 1199)

 King John (his younger brother and successor)

 Richard’s left leg

 John’s left leg

 A crown

Fig.2.11. A model containing five objects, two binary relations, three unary relations (indicated by labels on the objects),
and one unary function, left-leg.

These objects can have relations among them, which define how they are connected. For instance, the brother relation
connects Richard and John, represented as a set of tuples—ordered pairs of related objects. A tuple ⟨Richard, John⟩ means
“Richard is the brother of John,” while ⟨John, Richard⟩ means “John is the brother of Richard.” Similarly, the on-head
relation connects the crown with King John, indicating that the crown is on John’s head.

2. Relations in FOL can be of different types:

 Unary relations (properties): True for one object (e.g., Person(Richard), King(John), Crown(crown)).

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 43
 Introduction to AI and Applications (25CS1ETIAA)

 Binary relations: Involve two objects (e.g., Brother(Richard, John), OnHead(crown, John)).

3. Functions in FOL map objects to other objects in a consistent way. A function is a special kind of relationship
where each input has exactly one output. For example, the left_leg function may map:

 Richard → Richard’s left leg

 John → John’s left leg

Such a function is called a unary function because it takes one input. In formal terms, FOL requires total functions,
meaning every object must have a value for that function. However, in real scenarios, some objects (like a crown) may not
have a left leg. In such cases, an “invisible” or placeholder object can be assumed to satisfy the totality requirement.

Thus, a model for FOL includes:

 A domain (set of all objects),

 Relations (which describe how objects are connected), and

 Functions (which describe object mappings).

These components together define the structure of the logical world. The meaning—or semantics—of any sentence in FOL
is determined by how its symbols correspond to the elements, relations, and functions of a model. Therefore, understanding
FOL models helps an intelligent agent interpret and reason about the real world systematically.

2.11.3. Syntax of first-order logic

In First-Order Logic (FOL), the syntax defines the structure and symbols used to represent knowledge about objects,
their relationships, and the functions that connect them. While propositional logic could only describe entire facts as
true or false, FOL allows us to express statements about individual objects and relations between them, making it far
more expressive and suitable for real-world reasoning. The basic building blocks of FOL are symbols, which are divided
into three categories:

1. Constant Symbols: These represent specific objects or entities in the world.

Example – Richard, John, Crown (each referring to a distinct object).

2. Predicate Symbols: These denote relations or properties among objects. They can take one or more arguments,
depending on their arity (number of arguments).
Example –

o Brother(Richard, John) means “Richard is the brother of John.”

o Person(Richard) means “Richard is a person.”

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 44
 Introduction to AI and Applications (25CS1ETIAA)

o King(John) means “John is a king.”

3. Function Symbols: These represent functional relationships that map objects to other objects. Each function also
has a fixed arity.

Example –

 LeftLeg(Richard) represents the function “the left leg of Richard.”

 OnHead(Crown, John) represents “the crown is on John’s head.”

2.11.4. Semantics in First-Order Logic

In First-Order Logic (FOL), the semantics defines how symbols and expressions correspond to the objects, relations,
and functions in the real or imagined world (model). Understanding semantics helps an AI system interpret logical
sentences in a meaningful way.

1. Terms

A term in FOL is a symbolic expression that refers to an object in the domain of a model. It serves as the basic unit of
reference for entities that exist in the world being represented. There are two main kinds of terms:
 Constant Terms: These directly name specific objects. Each constant symbol refers to one fixed object in the
model.
Example: John, Richard, Crown
 Complex Terms: These are expressions built using function symbols that relate objects to other objects. Function
symbols help describe relationships without naming every object separately.
Example: LeftLeg(John) refers to King John’s left leg.

In general, a complex term has the form: f(t₁, t₂, …, tₙ) where f is a function symbol, and t₁…tₙ are argument
terms.

It is important to note that a function term in FOL is not a subroutine or executable operation, as in programming. It
merely represents a symbolic reference, not a computed value. For instance, LeftLeg(John) does not “compute” anything
but simply refers to the object denoted as John’s left leg in the model.

2. Atomic Sentences

Once we can refer to objects using terms, we can express facts about these objects using atomic sentences. An atomic
sentence (or atom) is the simplest type of statement in FOL that can be either true or false. It is formed by
combining a predicate symbol with one or more terms as arguments.

Example:

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 45
 Introduction to AI and Applications (25CS1ETIAA)

 Brother(Richard, John) – “Richard the Lionheart is the brother of King John.”

 Married(Father(Richard), Mother(John)) – “Richard’s father is married to John’s mother.”

3. Complex Sentences

Complex sentences are built by combining atomic sentences using logical connectives, following the same principles as
propositional logic. These include:
¬ (NOT), ∧ (AND), ∨ (OR), ⇒ (IMPLIES), and ⇔ (IF AND ONLY IF).

Examples (true under intended interpretation):

1. ¬Brother(LeftLeg(Richard), John) — “Richard’s left leg is not John’s brother.”

2. Brother(Richard, John) ∧ Brother(John, Richard) — “They are brothers of each other.”

3. King(Richard) ∨ King(John) — “Either Richard or John is a king.”

4. ¬King(Richard) ⇒ King(John) — “If Richard is not a king, then John is a king.”

Summary:

Concept Description Example

Term Refers to an object in the model. John, LeftLeg(John)

Constant Symbol Represents a specific named object. Crown, Richard

Function Symbol Maps objects to other objects. LeftLeg(John)

Atomic Sentence States a fact using predicates and terms. Brother(Richard, John)

Complex Sentence Combines sentences using logical connectives. King(John) ∨ King(Richard)

4. Quantifiers

In First-Order Logic (FOL), quantifiers are special symbols that allow us to express statements about sets or collections
of objects without naming each object individually. While propositional logic can only handle specific, fixed facts,
quantifiers give FOL the expressive power to describe general statements such as “All humans are mortal” or “There exists
a student who scored full marks.” FOL uses two standard quantifiers — the Universal Quantifier (∀) and the
Existential Quantifier (∃) — which together enable reasoning about all or some members of a domain.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 46
 Introduction to AI and Applications (25CS1ETIAA)

1. Universal Quantification (∀)

The Universal Quantifier (∀) is used to express that a statement holds true for every object in the domain of
discourse. It is symbolized by the upside-down capital letter A (∀), which means “for all” or “for every.”

Syntax: ∀x P(x)
This reads as “For all x, P(x) is true.”

Example: “All kings are persons” is written as:

∀x King(x) ⇒ Person(x)

This means that for every object x, if x is a king, then x must also be a person.

Semantics (Meaning):

The universally quantified statement ∀x P(x) is true in a model if P(x) is true for every possible value of x in the domain.

2. Existential Quantification (∃)

The Existential Quantifier (∃) is used to express that there exists at least one object in the domain for which a given
property holds. The symbol (∃) is read as “there exists” or “for some.”

Syntax: ∃x P(x)
This reads as “There exists an x such that P(x) is true.”

Example: “King John has a crown on his head” is expressed as:

∃x Crown(x) ∧ OnHead(x, John)

This means there exists some object x such that x is a crown and x is on John’s head.

Semantics (Meaning):

The statement ∃x P(x) is true if there is at least one object in the model for which P(x) holds true.

3. Logical Connectives and Quantifiers

Just as ⇒ works naturally with ∀, the and (∧) operator works naturally with ∃.

 With ∀: Implication (⇒) ensures that the statement applies only to objects satisfying the condition.

 With ∃: Conjunction (∧) connects the properties that must hold simultaneously for at least one object.

Summary

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 47
 Introduction to AI and Applications (25CS1ETIAA)

Quantifier Symbol Meaning Example in Logic Interpretation

Universal ∀ “For all” / “Every” ∀x King(x) ⇒ Person(x) Every king is a person.

Quantifier

Existential ∃ “There exists” / ∃x Crown(x) ∧ There exists at least one crown on

Quantifier “Some” OnHead(x, John) John’s head.

4. Equality in First-Order Logic

In addition to predicates, FOL allows us to express equality between two terms using the = symbol. Equality statements
are used to indicate that two different expressions refer to the same object in the domain.

Example:

Father(John) = Henry means “Father(John) is the same as Henry.”

The equality operator helps in defining relationships and comparisons between terms. Its negation, written as ¬(x = y) or
simply x ≠ y, states that the two terms refer to different objects.

2.11.5. Using First-Order Logic – Understanding Domains

Once the syntax and semantics of First-Order Logic (FOL) are understood, the next step is learning how to use this logic to
represent real-world knowledge. In Artificial Intelligence, FOL serves as a powerful representation language that allows us
to describe the structure of a world (called a domain) and express relationships, properties, and general rules about it in a
logical and systematic manner. A domain refers to a specific area or part of the real world about which we want to represent
and reason. It consists of the objects, entities, and relationships that are relevant to a given problem or environment. For
instance, if we are modeling a medical domain, the objects may include patients, doctors, diseases, and medicines, while
the relationships might describe which doctor treats which patient, or which medicine cures which disease. Similarly, in a
robotics domain, objects can be robots, locations, and objects to be moved; relationships can represent actions like “move,”
“pick,” and “place.”

When representing a domain using FOL, we must identify:

 Objects – the basic entities (people, places, items).

 Relations (Predicates) – relationships between objects (e.g., Loves(x, y), Teaches(Professor, Student)).
 Functions – mappings between objects (e.g., MotherOf(x), CapitalOf(y)).
 Facts – statements that describe known truths about the domain.
 Rules – general statements that describe how facts are related (e.g., ∀x,y Parent(x, y) ⇒ Ancestor(x, y)).

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 48
 Introduction to AI and Applications (25CS1ETIAA)

By systematically defining these components, FOL allows an AI system to infer new knowledge automatically through
reasoning processes such as unification and inference.

2.11.6. Wumpus World Representation using First-Order Logic (FOL)

The Wumpus World is a classic example used in Artificial Intelligence to demonstrate how agents can reason
logically in an uncertain environment. In this domain, a logical agent must represent knowledge about the world and
use reasoning to make intelligent decisions. First-Order Logic (FOL) offers a more expressive and compact representation
of the Wumpus World than Propositional Logic, enabling generalization across space and time.

Representation of Percepts and Time

In the Wumpus World, the agent receives a percept vector consisting of five elements: [Stench, Breeze, Glitter, Bump,
Scream]. Each percept occurs at a specific time step, represented as an integer.
For example:
Percept([Stench, Breeze, Glitter, None, None], 5) indicates that at time t = 5, the agent sensed a stench, a breeze, and
glitter.

 Here, Percept is a binary predicate linking the percept list with the time step.

 Similarly, actions such as moving, turning, or grabbing are expressed as terms:

o Turn(Right), Turn(Left), Forward, Shoot, Grab, Climb.

Percepts are converted into logical facts using quantified rules, for example:

 ∀t,s,g,m,c Percept([s, Breeze, g, m, c], t) ⇒ Breeze(t)

 ∀t,s,b,m,c Percept([s, b, Glitter, m, c], t) ⇒ Glitter(t)

These rules map percepts to logical facts in the KB, forming the basis of perception reasoning.
A simple reflex rule can then be added: ∀t Glitter(t) ⇒ BestAction(Grab, t)
→ If the agent perceives glitter at any time t, it should perform Grab.

Objects and relationships in the Wumpus World include squares, pits, and the Wumpus.
Instead of naming every square individually (like Square1,2), we represent locations as ordered pairs [x, y].

 Adjacency between squares can be defined as:

∀x, y, a, b Adjacent([x, y], [a, b]) ⇔ (x = a ∧ (y = b−1 ∨ y = b+1)) ∨ (y = b ∧ (x = a−1 ∨ x = a+1))

 Pit([x, y]) – true if there is a pit at location [x, y].

 At(Agent, s, t) – agent is at square s at time t.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 49
 Introduction to AI and Applications (25CS1ETIAA)

 At(Wumpus, [2,2], t) – wumpus is always at [2,2].

2.11.7. Perception-Based Inference

The agent can infer environmental properties from its percepts, for example:
∀s, t At(Agent, s, t) ∧ Breeze(t) ⇒ Breezy(s) → If the agent perceives a breeze while at square s, then that square is
breezy. The breezy property is time-independent since pits don’t move over time.

Instead of writing separate rules for each square as in propositional logic, FOL uses a single quantified axiom:
∀s Breezy(s) ⇔ ∃r Adjacent(r, s) ∧ Pit(r) → A square is breezy if and only if at least one of its adjacent squares has a
pit.

This reduces redundancy and expresses spatial relationships naturally.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 50
 Introduction to AI and Applications (25CS1ETIAA)

References

1. Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach (4th Edition), Pearson Education, 2023.

2. Elaine Rich, Kevin Knight, and Shivashankar B. Nair, Artificial Intelligence, McGraw Hill Education.

Summary

● Generate-and-test is simple but powerful for small-scale problems.

● It involves three essential steps: Generate → Test → Stop.

● Works effectively for problems with a small or finite search space.

● In complex cases, it is combined with heuristics, constraint satisfaction, or optimization techniques to improve
efficiency.

● Constraint Satisfaction is an intelligent search technique that relies on constraints rather than blind search to
reach a solution. By systematically propagating and strengthening constraints, AI systems can solve complex
combinatorial problems efficiently.

● CSPs represent problems as variables + constraints, making them structured and efficient to solve.

● Backtracking search forms the foundation, and adding heuristics and inference dramatically improves
performance.

● Real-world problems such as Sudoku, scheduling, map coloring, and logic puzzles can be elegantly expressed and
solved as CSPs.

● The stronger the constraint propagation, the fewer guesses are needed — leading to faster, more accurate
solutions.

● Means–Ends Analysis is a heuristic problem-solving technique that detects differences between the current and
goal states, selects an operator to reduce the difference, and recursively applies the same method until the goal is
reached.

● Heuristic functions are adopted when the problem domain is large, real-time performance is required, and
approximate reasoning is acceptable. By integrating domain knowledge into the search process, heuristics enable
intelligent agents to solve problems more like humans — efficiently, adaptively, and purposefully. On the other
hand, exhaustive search remains valuable for smaller or critical systems where completeness and precision are
more important than speed.

● Heuristic methods are intelligent problem-solving techniques that use prior knowledge to guide the search process
efficiently.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 51
 Introduction to AI and Applications (25CS1ETIAA)

● They are essential for real-world AI applications where optimal search is impractical due to time or resource
limits.

● Understanding the differences among heuristic strategies helps in selecting the right method for a given problem
type.

● Generate & Test: “Try and check if it works.”; Hill Climbing: “Keep improving until no better option remains.”;
Constraint Satisfaction: “Follow the rules and eliminate impossible cases.”; Means–Ends Analysis: “Plan actions
to reduce the gap between now and the goal.”

● Knowledge Representation serves as the backbone of Artificial Intelligence, enabling machines to store
knowledge in a meaningful way and apply logical reasoning to solve problems, learn from experience, and
communicate intelligently. Effective KR transforms static data into actionable knowledge, forming the bridge
between data processing and true understanding.

● Knowledge-Based Agent: An AI system that uses stored knowledge and reasoning to act intelligently.

● Key Components: Knowledge Base (facts/rules) + Inference Engine (reasoning mechanism).

● Cycle of Operation: Perceive → Infer → Act → Learn.

● Example: Wumpus World demonstrates reasoning and decision-making under uncertainty.

● Logical Foundation: Based on Propositional Logic and First-Order Logic for knowledge representation and
inference.

● Knowledge Base (KB): Central store of facts and rules expressed in a Knowledge Representation Language.

● Sentence: A statement about the world; may also be an axiom if accepted as true without proof.

● TELL: Operation to add new information to the KB.

● ASK: Operation to retrieve or infer information from the KB.

● Inference: Logical reasoning process to derive new knowledge from existing facts.

● Cycle of Operation: Perceive → TELL (add perception to KB); ASK (decide next action); TELL (record chosen
action)

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 52
 Introduction to AI and Applications (25CS1ETIAA)

● Importance: Enables reasoning-based decision-making and adaptive intelligence.

● Wumpus World models reasoning under uncertainty.

● Agents must combine perceptual input and logical inference to act safely.

● The PEAS model is essential for designing and evaluating intelligent agents.

● It exemplifies partial observability — the agent must infer unseen dangers.

● It serves as a foundation for studying propositional logic, inference, and planning in AI.

● Propositional logic is the foundation of knowledge representation and reasoning in AI. It enables an agent to:

● Represent knowledge symbolically.

● Draw logical inferences using rules and implications.

● Avoid ambiguity by defining clear syntax and semantics.

● Model reasoning in environments like the Wumpus World efficiently.

● Through propositional logic, AI systems can emulate human-like reasoning—deriving conclusions, detecting
contradictions, and deciding actions based on logical analysis.

● Entailment (⊨): Sentence α is true in every model where KB is true. Model: Assignment of truth values to all
proposition symbols.

● Quantifiers make First-Order Logic a powerful tool for knowledge representation and reasoning in Artificial
Intelligence. They enable: Compact representation of general rules (e.g., “All birds can fly”); Expression of specific
existence claims (e.g., “There exists a bird that cannot fly”); Logical inference over objects and relations, allowing
AI systems to deduce new knowledge efficiently.

● Understanding quantifiers and equality is fundamental in AI reasoning systems because: They allow generalization
over sets of objects instead of individual facts; Enable the representation of relationships and hierarchies (e.g., “All
humans are mortal”); Support logical inference, allowing AI to deduce new facts about entities in a knowledge base;
Form the foundation for semantic networks, ontologies, and logic programming languages like Prolog.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 53
 Introduction to AI and Applications (25CS1ETIAA)

● The domain forms the backbone of any knowledge-based system in AI. By clearly defining the elements of the
domain and their interrelations, we enable logical reasoning that mimics human intelligence. The same approach
can be scaled to larger domains such as medicine, law, or natural language understanding. Thus, using FOL to
represent domains bridges human conceptual understanding with machine reasoning, making it possible to automate
complex problem-solving through formal logic.

Prepared by: Dr Roopashree S, Dr. Priyanka C H, Prof Anita H K, Prof. Vidushi Dwivedi 54