Artificial Intelligence & Machine

Learning

• Asst. Prof. Barsha Pattanaik

• NIT, Bhubaneswar
Adversarial Search

• The Adversarial search is a well-suited approach in a competitive environment, where two or more agents

have conflicting [Link] adversarial environments — such as games — there are multiple agents whose

goals conflict.

In artificial intelligence, adversarial search plays a vital role in decision-making, particularly in competitive

environments associated with games and strategic interactions.

 Structure of a Game
A game is formally represented by:
[Link] State – The starting position and the player to move.
[Link] – Usually two: MAX and MIN.
[Link](s) – Legal moves available to a player in state s.
[Link](s, a) – The state that results from action a in state s.
[Link]-Test(s) – True if s is a terminal (game-over) state.
[Link](s) – Numerical value of the terminal state.
1. Win = +1
2. Loss = –1
3. Draw = 0
(or other game-specific utilities)

Example:
In Tic-Tac-Toe, the initial state is an empty board, the actions are legal moves, and terminal states correspond to
win/loss/draw outcomes.
The Mini–Max Algorithm

• The Mini–Max algorithm computes the optimal strategy for a player, assuming the opponent also plays
optimally.
• The Principle:
 Backtracking
 Best Move strategy
 Max will try to maximize its utilize (Best move)
 Min will try to minimize utility(Worst Move)
• “A rational player should choose a move that maximizes its minimum possible payoff — hence the name
minimax.”
• That is:
 MAX player chooses the move with the highest value assuming MIN plays to minimize it.
 MIN player chooses the move with the lowest value assuming MAX plays to maximize it.
• Formal Definition:

• If UTILITY(n) is the terminal value of node n, then:

Alpha–Beta Pruning

• Because Mini–Max explores every node, it’s computationally expensive.

• Alpha–Beta pruning improves it by pruning branches that cannot possibly influence the final decision.

Key Idea:
While performing the Mini–Max search:
•α (alpha) = the best (highest) value so far found along the path for MAX.
•β (beta) = the best (lowest) value so far found along the path for MIN.
If at any point it’s found that:

then that branch can be pruned, since it will never be chosen by either player.
 Max α

Min Min
β β

Max α Max
α Max α Max α

Min
Min Min Min
Min Min Min
β β β Min β β β β β

3 4 2 1 7 8 9 10 2 11 1 12 14 9 13 16

Terminal
Knowledge Representation and Reasoning (KRR)

• Knowledge Representation (KR) and Reasoning (R) are the core of Artificial Intelligence.

• Knowledge Representation deals with how to represent information about the world so that an

intelligent system can use it to solve complex problems like diagnosing a disease, understanding language,

or planning.

•Reasoning is the process of drawing conclusions from known facts or rules.

 KRR

Semantic
Logic Rules Frame Scripts
net

Google Slots/
Propositional: If then graph Differ(Ob Movies
True/False jects/
Predicate: Attribute)
Quantitative, eg,
Forall, there exists
2. Logical Agents
A logical agent uses inference to decide what to do.
It consists of:
•Knowledge base (KB): A set of sentences (facts and rules) expressed in a formal language (like
propositional or first-order logic).
•Inference engine: A mechanism that derives new information from the knowledge base.
Architecture:
Percepts → Knowledge Base → Inference → Actions
Example (Russell & Norvig):
•KB: “If it rains, the grass gets wet.”
•Fact: “It rains.”
•Reasoning: “Therefore, the grass is wet.”
Logical agents are the foundation of Knowledge-Based Agents.
3. Knowledge-Based Agents

These agents operate by:

[Link] knowledge about the world.

[Link] to infer new knowledge.

[Link] their knowledge base as they perceive

4. the environment.

Example:

•Agent knows: “If the room is dark, turn on the light.”

•Perception: “Room is dark.”

•Action: “Turn on the light.”

4. Logic
Logic is a formal language for representing knowledge and reasoning about it.
Two main types:
[Link] Logic (PL): Deals with propositions (simple statements that are true or false).
[Link]-Order Logic (FOL): Extends propositional logic with quantifiers, variables, and
relations to describe complex statements about objects.
Propositions Logic

A proposition is a statement that can either be true or false. It does not matter how complicated
statement is if it can be classified as true or false then it is a proposition. For example:

Example of Propositions Logic

•P: "The sky is blue." (This statement can be either true or false.)

•Q: "It is raining right now." (This can also be true or false.)

•R: "The ground is wet." (This is either true or false.)

These can be combined using logical operations to create more complex statements. For example:
•P ∧ Q: "The sky is blue AND it is raining." (This is true only if both P and Q are true.)

•P ∨ Q: "The sky is blue OR it is raining." (This is true if at least one of P or Q is true.)

•¬P: "It is NOT true that the sky is blue." (This is true if P is false means the sky is not blue.)
6. Resolution Using Propositional Logic

Resolution is a mechanical inference rule for propositional logic used in automated theorem proving.

It’s based on refutation — meaning we try to show that the negation of what we want to prove leads to a

contradiction ( hence the original statement must be true).

Steps:

[Link] all statements into Conjunctive Normal Form (CNF).

[Link] resolution rule to eliminate complementary literals.

[Link] you derive an empty clause (⊥), the conclusion is proved.

CNF (Conjunctive Normal Form)

CNF (Conjunctive Normal Form) is a standardized logical form where a formula is written as a
conjunction (AND) of one or more clauses, and each clause is a disjunction (OR) of literals.

In simple words:
CNF = AND of ORs
(Each OR group is a clause, and all clauses are combined with AND)

Example:

This is in CNF because:

•It’s a conjunction (AND, i.e., ∧) of three clauses:
• Clause 1:
• Clause 2:
• Clause 3:
Example:1

If we have two clauses:

 (A ∨ B) and (¬B ∨ C)
 Then by the Resolution rule, we can infer: (A ∨ C)
 Because B and ¬B cancel out (they “resolve”).

Example:2
1. P ∨ Q
2. ¬Q ∨ R
3. ¬P
⇒R
Using resolution:
•(P ∨ Q) + (¬P) ⇒ Q
•(Q) + (¬Q ∨ R) ⇒ R
Example:3

Let’s prove:
Statement: “If it is raining, the ground is wet. It is raining. Therefore, the ground is wet.”

Step 1: Represent in Propositional Logic

Let
•It is raining
•The ground is wet
Given statements:
1.

Prove:

Step
1. 2: Convert to Clausal Form (CNF)

≡ C1: ¬R ∨ W
C2: R
[Link] the conclusion we want to prove: C3: ¬W (negation of what we want to prove)
Now we have clauses:
 Step 3: Apply Resolution Rule

[Link] C1 (¬R ∨ W) and C2 (R)

1. Resolving R and ¬R gives → W
2. New clause:
 C4: W

[Link] resolve C4 (W) and C3 (¬W)

•Resolving W and ¬W gives → Empty Clause (⊥)

Step 4: Interpret Result

•Getting an empty clause (⊥) means a contradiction.
•Hence, the negation of the conclusion is false →
Therefore, the original conclusion (W) is true.
Importance in AI
AI systems that use first-order or propositional logic must be
1 Foundation of Automated Reasoning
able to:
Resolution is the main reasoning mechanism in:
•Infer new facts from known ones.
•Automated theorem proving
•Prove whether a conclusion follows logically.
•Knowledge-based systems
Resolution gives them a single, sound, and complete rule to do
•Logic programming (Prolog)
this.

Sound → It never derives a false conclusion.

Complete → It can derive all logically true conclusions.

2 Used in Knowledge Representation and Reasoning (KRR)

In AI, knowledge about the world is often stored as logical statements (facts and rules).

Resolution helps an AI agent reason with these facts.

For example:

Rule: If it rains, the ground is wet. (¬Rain ∨ Wet)

Fact: It rains. (Rain)

Query: Is the ground wet?

Using resolution, the agent can derive that the ground is wet.
3. Basis for Problem Solving and Theorem Proving
Resolution is used in refutation-based theorem proving:
•To prove a goal , you assume ¬G,
•Then use resolution to try to derive a contradiction (⊥).
•If a contradiction is found → must be true.
This principle forms the logic behind automated theorem provers and SAT solvers, which are
essential in AI reasoning, verification, and planning.

4 Logical Decision-Making (Thinking Rationally)

AI aims to think rationally, meaning its conclusions should follow logically from the evidence.
Resolution gives the mathematical backbone for this:
•It guarantees that every conclusion follows by logic, not by guessing.
•Hence, AI decisions become explainable and provably correct.
5 Practical Applications in AI

Area Role of Resolution

Expert Systems Deduce new facts from a rule base

Prolog Programming Uses resolution (SLD-resolution) to answer queries

Automated Theorem Provers Use resolution to prove logical formulas

Uses propositional resolution to check system

Model Checking / Verification
correctness

Logical inference between propositions (entailment,

Natural Language Understanding
contradiction)

6 Link with Rational Thinking and Acting

Example:
A robot can reason:
“If obstacle ahead → stop.”
If “obstacle ahead” is true, resolution helps conclude “stop” — hence, it acts rationally.
Logical Connectives

Logical connectives are used to combine simple propositions into more complex ones. The main connectives
are:
•AND (∧): This operation is true if both propositions are true.
Example: "It is sunny ∧ it is warm" is true only if both "It is sunny" and "It is warm" are true.

•OR (∨): This operation is true if at least one of the propositions is true.
Example: "It is sunny ∨ it is raining" is true if either "It is sunny" or "It is raining" is true.

•NOT (¬): This operation reverses the truth value of a proposition.

Example: "¬It is raining" is true if "It is raining" is false.

•IMPLIES (→): This operation is true if the first proposition leads to the second.
Example: "If it rains then the ground is wet" (It rains → The ground is wet) is true unless it rains and the
ground is not wet.

•IF AND ONLY IF (↔): This operation is true if both propositions are either true or false together.
Example: "It is raining ↔ The ground is wet" is true if both "It is raining" and "The ground is wet" are either
true or both false.
 Truth Tables: They are used to find the truth value of complex propositions by checking all possible combinations of
truth values for their components. They systematically list every possible combination, which helps in making it easy to
find how different logical operators affect the overall outcome. This approach ensures that no combination is given extra
importance, which provides a clear and complete picture of the logic at work.

Tautologies, Contradictions and Contingencies

•Tautology: A proposition that is always true no matter the truth values of the individual components.
Example: "P ∨ ¬P" (This is always true because either P is true or P is false).

•Contradiction: A proposition that is always false.

Example: "P ∧ ¬P" (This is always false because P can't be both true and false at the same time).

•Contingency: A proposition that can be true or false depending on the truth values of its components.
Example: "P ∧ Q" (This is true only if both P and Q are true).
Predicate Logic

• Predicate logic, also known as first-order logic (FOL), is an extension of propositional logic that
allows us to express relationships between objects and their properties or to reason about objects,
their properties, and relations between them.
• In AI, predicate logic is widely used to represent knowledge and perform reasoning in more
complex scenarios where relationships matter.
While propositional logic can only say:
“It’s raining” (a simple true/false statement)
Predicate logic can say:
“For all cities, if it’s raining there, the streets are wet.”
So, FOL adds quantifiers, variables, and predicates to express statements about a domain.
Role of Predicate Logic in AI

•Knowledge Representation: It provides a structure for representing complex facts about objects and
their relationships in a system.

•Reasoning: AI systems use predicate logic to infer new information from existing facts, making it
suitable for decision-making tasks.

Example: “John is the father of Mary” can be represented as: Father(John,Mary)

logic → reasoning → decision → action

This chain connects thinking rationally (reasoning) to acting
rationally (decision-making).
Key components of First-Order Logic

FOL extends propositional logic by introducing quantifiers and predicates, making it more
expressive and versatile. Let's see various key components of FOL:

1. Constants: These represent specific objects or entities (Example: Alice, 2, NewYork).

2. Variables: These stand for unspecified objects or entities (Example: x, y, z).

3. Functions: It map objects to other objects (Example: MotherOf(x) refers to the mother of x).

4. Predicates: These define properties or relationships (Example: Likes(Alice, Bob) means "Alice
likes Bob").
1. Predicate Symbol
•The predicate symbol defines the property or relationship being described.
•Example:
• IsHungry(x) represents whether a person (x) is hungry.
• Married(x, y) denotes that person x is married to person y.
•Predicates are named based on the relationship or property they represent. The symbol is followed
by arguments enclosed in parentheses.

2. Arguments and Arity

•Arguments refer to the specific objects that the predicate is applied to.
•The arity of a predicate refers to the number of arguments it takes.
Examples:
•IsHungry(x): A predicate with 1 argument (arity = 1).
•Married(x, y): A predicate with 2 arguments (arity = 2).
•X(a, b, c): A predicate with 3 arguments (arity = 3), representing something like “a + b + c = 0.”
3. Quantifiers in Predicate Logic: Quantifiers allow us to specify the scope of variables. There are
two main types:

Universal Quantifier (∀) [∀ → Universal Quantifier (“for all”)]

Meaning: The given condition holds for all objects in the domain.
Example: ∀x (IsHuman(x)→IsMortal(x))
This means that all humans are mortal.
Negation: The negation of the universal quantifier means there is at least one exception.
¬∀x IsHuman(x)→IsMortal(x)
This implies that at least one human is not mortal.
Means for all or for every.
“All humans are mortal.”

This reads as:

For every x, if x is a human, then x is mortal.
Existential Quantifier (∃) [there exists]
Meaning: There exists at least one object that satisfies the given condition.
Example: ∃x IsHungry(x)
This statement means that at least one person is hungry.
Negation: The negation of the existential quantifier means that no such object exists.
¬∃x IsHungry(x)
This means that no one is hungry.

Means there exists at least one.

“There exists someone who loves Mary.”

This reads as:

There is some x such that x loves Mary.

Logical Connectives: Include conjunction (∧), disjunction (∨), implication (→), biconditional (↔) and negation
(¬).
Building Blocks of Predicate Logic

Concept Symbol / Example Meaning

Constant john, london, 0 Refers to a specific object or entity

Represents any object in the

Variable x, y, z
domain

Predicate Human(x), Loves(john, x) Describes a property or relation

Function FatherOf(x) Returns an object related to x

Quantifiers ∀ (for all), ∃ (there exists) Used to generalize or specify

¬ (not), ∧ (and), ∨ (or), →

Connectives Logical operators
(implies), ↔ (iff)
Translating FOL to English

FOL Expression Meaning

∀x (King(x) → Mortal(x)) All kings are mortal

∃x (Teacher(x) ∧ Tall(x)) There exists a tall teacher

∀x ∃y (Parent(x, y)) Everyone has at least one child

∃x (Doctor(x) ∧ ¬Married(x)) There is a doctor who is not married

Inference Rules (used in reasoning) : These are used to derive conclusions from
given facts.

Rule Description Example

Universal Instantiation (UI) Replace ∀ variable with a constant From ∀x (P(x)), infer P(John)

Replace ∃ variable with a constant (say

Existential Instantiation (EI) From ∃x P(x), infer P(c)
c)

Modus Ponens (MP) If P → Q and P are true, infer Q From P → Q, P, infer Q

Conjunction (AND) Combine statements From P, Q infer P ∧ Q

Resolution Used in automated theorem proving From P ∨ Q and ¬P, infer Q

Inference Rules (How AI “Thinks” with Predicate Logic)

AI uses rules like these to derive new facts:

Rule Description Example

If P → Q and P is true, then Q is If it rains, the ground is wet. It rains

Modus Ponens
true → Ground is wet.

From ∀x Human(x) → Mortal(x),

Universal Instantiation Replace variable with a constant derive Human(Socrates) →
Mortal(Socrates)

∃x Loves(x, Mary) → Loves(John,

Existential Instantiation Replace ∃x with a new symbol
Mary) (assume some John exists)
Step-by-Step Example Example 2
Example 1: If a person is a mother, she is female.
All humans are mortal. Mary is a mother.
Socrates is a human. Therefore, Mary is female.
Therefore, Socrates is mortal. Step 1: Represent
Representation: 1.∀x (Mother(x) → Female(x))
1.∀x (Human(x) → Mortal(x)) [Link](Mary)
[Link](Socrates) Step 2: Infer
[Link] 1 and 2 using UI + Modus Ponens, By UI + Modus Ponens,
⇒ Mortal(Socrates) → Female(Mary)
Example 3 with AND
John is a king and greedy.
All greedy kings are evil.
Therefore, John is evil.
FOL:
[Link](John)
[Link](John)
3.∀x (King(x) ∧ Greedy(x) → Evil(x))
Inference:
From (1) and (2): King(John) ∧ Greedy(John)
From (3): Evil(John)
Answers

Translate these into FOL:

[Link] student loves some teacher. ∀x(Student(x)→∃y[Teacher(y)∧Loves(x,y)])

[Link] dogs are not friendly. ∃x[Dog(x)∧¬Friendly(x)]

[Link] exists a bird that cannot fly. ∃x[Bird(x)∧¬CanFly(x)]

[Link] programmers are logical. ∀x(Programmer(x)→Logical(x))​

[Link] loves everyone who loves Mary. ∀x(Loves(x,Mary)→Loves(John,x))​

 Unification

• Unification is the process of making two logical expressions identical by finding suitable substitutions
for their variables.
• It is a fundamental operation in predicate logic, automated reasoning, and logic programming.
• In simple terms, unification is a kind of pattern matching used in logical inference — it helps determine
whether two expressions can refer to the same thing.
• Unification is the backbone of reasoning in first-order logic — it allows computers to match patterns,
apply rules, and derive logical conclusions automatically.

Purpose of Unification

Unification is used to: 3. Enable automated theorem proving using the resolution

[Link] logical statements during inference. principle.

4. Perform variable substitution in logic programming
[Link] rules to facts in reasoning systems.
languages such as Prolog.
How It Works

Unification tries to find a substitution (θ) such that:

Expr1θ = Expr2θ

That is, when substitution θ is applied to both expressions, they become identical.

This substitution θ is called the Unifier.

If multiple unifiers exist, the simplest and most general one is called the Most General Unifier (MGU).

Example 1
Unifier (θ): {x/Bill, y/John}
Knows(John, x)
After substitution, both expressions become:
Knows(y, Bill)
Knows(John, Bill)
We can make these identical if:
x = Bill This means: substitute x with Bill and y with John.
You can read it aloud as:
y = John “Theta is a unifier where x is replaced by Bill and y is replaced by John.”
 Algorithm: UNIFY(x, y, θ)
[Link] θ = failure, return failure.
Unification Algorithm [Link] x = y, return θ.
[Link] x is a variable, return UNIFY-VAR(x, y, θ).
[Link] y is a variable, return UNIFY-VAR(y, x, θ).
[Link] x and y are compound:
1. If their predicate names or number of arguments differ, return failure.
2. Otherwise, unify their corresponding arguments recursively.
[Link] none of the above cases apply, return failure.
Function: UNIFY-VAR(var, x, θ)
•If var is already bound in θ, unify the binding with x.
•If x is already bound, unify var with the binding of x.
•If var occurs in x (Occurs Check), return failure.
•Otherwise, extend θ with {var/x}.
Output: The Most General Unifier (MGU) or Failure.
Lifting

• Lifting is the process of generalizing a propositional inference rule to the predicate level.
In simple words:
• When an inference rule that works for specific, ground propositions (like Modus Ponens) is
extended so that it can handle variables and quantifiers, the process is called lifting.

lifting = inference rule + unification + variables/generalization.

How It Works
[Link] with a propositional inference rule (like Modus Ponens, Resolution, etc.).
[Link] constants with variables to make it general.
[Link] unification when necessary — to make the predicates match.
Example
Let’s start with propositional logic:
P→Q
P
∴Q
This is Modus Ponens — it works with specific (ground) propositions only.
Now, when we move to predicate logic, we can “lift” this rule as follows:
∀x (P(x) → Q(x))
P(John)
∴ Q(John)
This lifted version means we’re applying Modus Ponens, but not to a single proposition, rather to a
family of propositions parameterized by x.
Example with unification:

1. Loves(John, x) → Loves(x, Mary)

2. Loves(John, Bill)
Using unification, we can substitute x = Bill and lift the rule to infer:
Loves(Bill, Mary)
So, lifting = inference rule + unification + variables/generalization.
Forward Chaining
• Forward chaining is a data-driven inference technique in Artificial Intelligence. It starts with known facts and
applies inference rules to derive new facts until a goal is reached.
• It uses IF–THEN rules of the form:
How it Works

[Link] with the initial facts in the knowledge base.

[Link] these facts with the IF part (conditions) of the rules.

[Link] all conditions of a rule are satisfied, apply that rule.

[Link] the THEN part (new facts) to the knowledge base.

[Link] until:

1. No more rules can be applied, or

2. The goal fact is derived.

Example
Knowledge base:
[Link] it rains THEN the ground gets wet.
[Link] the ground gets wet THEN the grass becomes slippery.
[Link] rains.
Forward chaining steps:
Conclusion: The grass becomes slippery.

Step Known Facts Rule Applied New Fact Inferred

1 It rains Rule 1 The ground gets wet

The grass becomes

2 The ground gets wet Rule 2
slippery
Apply Forward Chaining to infer whether “Sam plays football.”
Given:
[Link] it is sunny THEN Sam goes out.
[Link] Sam goes out THEN Sam plays football.
[Link] is sunny.
Solution:
Conclusion: Sam plays football.

Step Known Fact Rule Applied Inferred Fact

1 It is sunny Rule 1 Sam goes out

2 Sam goes out Rule 2 Sam plays football

Applications

•Expert systems (e.g., MYCIN for medical diagnosis)

•Decision support systems

•Rule-based control systems

•Event monitoring and real-time reasoning

Backward Chaining

• Backward Chaining is a reasoning technique in Artificial Intelligence that starts from a goal (hypothesis) and
works backward to find whether the known facts support that goal.
• It is a goal-driven approach — because reasoning starts from what you want to prove.
How It Works

[Link] with a goal (what you want to prove).

[Link] for a rule whose THEN part matches the goal.

[Link] if the IF conditions of that rule are known facts.

[Link] not, treat each missing condition as a new subgoal.

[Link] repeating the process until:

1. All subgoals are satisfied ( goal proven), or

2. No rules can support the goal ( goal cannot be proven).

 Example
Backward chaining steps:
[Link] prove “grass is slippery,” find a rule whose THEN part
Knowledge base: is “grass is slippery.”
[Link] it rains THEN the ground is wet. → Rule 2: IF ground is wet THEN grass is slippery.
[Link] the ground is wet THEN the grass is So, new subgoal: prove “ground is wet.”
slippery. [Link] prove “ground is wet,” find a rule whose THEN part is
[Link] rains. “ground is wet.”
Goal: Is the grass slippery? → Rule 1: IF it rains THEN ground is wet.
So, new subgoal: prove “it rains.”
3.“It rains” is a known fact.
[Link], “ground is wet” → “grass is slippery”
Conclusion: The grass is slippery.
 Example

(Simple Medical Expert System) Backward Chaining:

Rules: •To prove “flu,” we need “cough” AND “fever.”

[Link] cough AND fever THEN flu. •“fever” known.

[Link] sore_throat AND fever THEN •“cough” not known, and no rule to prove it.

throat_infection. Conclusion: Flu cannot be proven.

[Link], sore_throat are known facts. If goal = “throat_infection”:

Goal: Prove flu. •Need “sore_throat” AND “fever” → both true

Conclusion: Throat infection is diagnosed.

Applications

•Diagnostic systems (medical, mechanical fault finding)

•Troubleshooting and debugging

•Question–answering systems (e.g., MYCIN, DENDRAL)

•Expert systems for hypothesis testing