AI Unit 3

Artificial Intelligence
(KCS071) Unit 3
KCS 071 Unit 3 Ankita Singh

Syllabus Unit 3
KNOWLEDGE REPRESENTATION: First Order Predicate Logic – Prolog Programming – Unification –
Forward Chaining-Backward Chaining – Resolution – Knowledge Representation – Ontological
Engineering-Categories and Objects – Events – Mental Events and Mental Objects – Reasoning
Systems for Categories – Reasoning with Default Information

Introduction to Logical agents
Intelligence of humans is achieved—not by purely reflex mechanisms but by processes of reasoning that operate on
internal representations of knowledge. In AI, this approach to intelligence is embodied in knowledge-based agents.
Knowledge-based agents are those agents who have the capability of maintaining a state of internal knowledge,
reason over that knowledge, update their knowledge after observations and take actions. These agents can
represent the world with some formal representation and act intelligently.
We have to represent knowledge about the world in a manner that facilitates inferencing(i.e. drawing conclusion)
from knowledge.
Example: Arithmetic logic
In AI based on
- Logic
- Probability
- Logic and Probability
Knowledge-based agents are composed of two main parts:
○ Knowledge-base and
○ Inference system.
Knowledge base
Knowledge-base is required for updating knowledge for an agent to learn with experiences and take action as per the knowledge.
Inference system
Inference means deriving new sentences from old. Inference system allows us to add a new sentence to the knowledge base. A sentence is
a proposition about the world. Inference system applies logical rules to the KB to deduce new information.
Inference system generates new facts so that an agent can update the KB. An inference system works mainly in two rules which are given
as:
○ Forward chaining
○ Backward chaining

Knowledge base
The central component of a knowledge-based agent is its knowledge base, or KB.
A knowledge base is a set of sentences. Each sentence is expressed in a language called a

knowledge representation language and represents some assertion about the world.
An axiom, is a sentence which is stated without being derived from other sentences.
TELL operation add new sentences to the knowledge base. ASK operation query from the knowledge
base.
Both operations may involve inference—that is, deriving new sentences from old.
The agent maintains a knowledge base, KB, which may initially contain some background knowledge.

Each time the agent program is called, it does three things.
First, it TELLs the knowledge base what it perceives.
Second, it ASKs the knowledge base what action it should perform. In the process of answering this
query, extensive reasoning may be done about the current state of the world, about the outcomes of
possible action sequences, and so on.
Third, the agent program TELLs the knowledge base which action was chosen, and the agent
executes the action.
knowledge-based agent can be built simply by TELLing it what it needs to know.
Starting with an empty knowledge base, the agent designer can TELL sentences one by one until the
agent knows how to operate in its environment. This is called the declarative approach to system
building

Example
TELL: Father of John is Bob
TELL: Jane is John's sister
TELL: John's Father is the same as John's sister's father
ASK: Who's Jane's Father?

Approaches to designing a knowledge-based agent:
There are mainly two approaches to build a knowledge-based agent:
1. Declarative approach: We can create a knowledge-based agent by initializing with an empty

knowledge base and telling the agent all the sentences with which we want to start with. This
approach is called Declarative approach.
2. Procedural approach: In the procedural approach, we directly encode desired behavior as a
program code. Which means we just need to write a program that already encodes the desired
behavior or agent.
However, in the real world, a successful agent can be built by combining both declarative and
procedural approaches, and declarative knowledge can often be compiled into more efficient
procedural code.

Common KR languages

Components of KR
•Syntax: defines the sentences in the language
•Semantics: defines the “meaning” to sentences
•Inference Procedure
–Algorithm
–Sound?
–Complete?
–Complexity
•Knowledge Base

The Wumpus World
● There are total 16 rooms which are connected with each
other.
● The cave has a room with a beast which is called Wumpus,

who eats anyone who enters the room.
● The Wumpus can be shot by the agent, but the agent has a
single arrow.
● In the Wumpus world, there are some Pits rooms which are
bottomless, and if agent falls in Pits, then he will be stuck
there forever.
● In one room there is a possibility of finding a heap of gold.

So the agent goal is to find the gold and climb out the cave
without fallen into Pits or eaten by Wumpus.

Performance measure
– gold +1000, death -1000
– -1 per step, -10 for using the arrow
Environment
– Squares adjacent to wumpus are smelly
– Squares adjacent to pit are breezy
– Glitter if gold is in the same square
– Shooting kills wumpus if you are facing it
– Shooting uses up the only arrow
– Grabbing picks up gold if in same square
– Releasing drops the gold in same square
Sensors: Stench, Breeze, Glitter, Bump, Scream
Actuators: Left turn, Right turn, Forward, Grab, Release, Shoot

The Wumpus world Properties
○ Partially observable: The Wumpus world is partially observable because the agent can only perceive the
close environment such as an adjacent room.
○ Deterministic: It is deterministic, as the result and outcome of the world are already known.
○ Sequential: The order is important, so it is sequential.
○ Static: It is static as Wumpus and Pits are not moving.
○ Discrete: The environment is discrete.
○ One agent: The environment is a single agent as we have one agent only and Wumpus is not considered as an
agent.

Exploring a Wumpus world




Logic
Knowledge bases consist of sentences. These sentences are expressed according to the syntax of the
representation language, which specifies all the sentences that are well formed.
The notion of syntax is clear enough in ordinary arithmetic: “x + y = 4” is a well-formed sentence, whereas “x4y+
=” is not.
A logic must also define the semantics or meaning of sentences. The semantics defines the truth of each
sentence with respect to each possible world. For example, the semantics for arithmetic specifies that the
sentence “x + y =4” is true in a world where x is 2 and y is 2, but false in a world where x is 1 and y is 1. In
standard logics, every sentence must be either true or false in each possible world—there is no “in between.”1

Logic in general
• Logics are formal languages for representing information such that conclusions can be drawn
• Syntax defines the sentences in the language
• Semantics define the "meaning" of sentences;
– i.e., define truth of a sentence in a world
• E.g., the language of arithmetic
– x+2 ≥ y is a sentence; x2+y > {} is not a sentence
– x+2 ≥ y is true if the number x+2 is no less than the number y
– x+2 ≥ y is true in a world where x = 7, y = 1
– x+2 ≥ y is false in a world where x = 0, y = 6

Entailment
Entailment means that one thing follows from another:
KB ╞ α
Knowledge base KB entails sentence α if and only if α is true in all worlds where KB is true
– E.g., the KB containing “the Giants won” and “the Reds won” entails “Either the Giants won
or the Reds won”
– E.g., x+y = 4 entails 4 = x+y
– Entailment is a relationship between sentences (i.e., syntax) that is based on semantics

Models
• Logicians typically think in terms of models, which are
formally structured worlds with respect to which truth
can be evaluated
• We say m is a model of a sentence α if α is true in m
• M(α) is the set of all models of α
Then KB ╞ α iff M(KB) ⊆ M(α)
– E.g. KB = Giants won and Red won
α = Giants won

Entailment in the wumpus world
Situation after detecting nothing in [1,1],
moving right, breeze in [2,1]
Consider possible models for KB assuming

only pits
3 Boolean choices -> 8 possible models

Wumpus models

Wumpus models
Is this true that there are no pits in [1,2]?
KB = wumpus-world rules + observations

• α1 = "[1,2] is safe", KB ╞ α1, proved by model checking
In every model in which KB is true, α2 is true


• α2 = "[2,2] is not safe",
In every model in which KB is true, α2 is not necessary true

Inference
KB ├i α = sentence α can be derived from KB by procedure i
• Soundness: i is sound if whenever KB ├i α, it is also true that KB╞ α
• Completeness: i is complete if whenever KB╞ α, it is also true that KB ├i α
• Preview: we will define a logic (first-order logic) which is expressive enough to say almost
anything of interest, and for which there exists a sound and complete inference procedure.
• That is, the procedure will answer any question whose answer follows from what is known
by the KB.

What is a Proposition??
● A proposition is a declarative sentence (that is, a sentence that declares a fact ,wish or intent) that can be classified as
either true or false, but not both.
● If the proposition is true, then its truth value is ‘true’ denoted by ‘T’, otherwise its truth value id ‘false’ denoted by “F’
Identify which of them is proposition:
1. The number 4 is even and less than 12. (P)
2. How are you doing? (NP)
3. 5<= 11 (P)
4. Temperature is less than 10 C (P)
5. It is cold today.(NP)
6. Read this carefully. (NP)
7. X + y = z (NP)

Types of proposition
Simple Proposition: A proposition that conveys one thought with no
connecting words.
Compound Proposition: It contains two or more simple propositions that are

put together by connective words (eg not, or, and, if-then)
We use letters to denote propositional variables to represent propositions eg

p, q, r, s.

Types of compound propositions
Let p,q,r and s are propositions:
1. Negation: - if p be a proposition, then negation of p is denoted by ¬p, is the statement “it is not
the case that p”.
Example: P ¬p
p : “It is raining today”,
¬p: It is not raining today”. T F
F T

2. Conjunction- If p and q be propositions. The conjunction of p and q, is denoted by p ∧ q. The
conjunction p ∧ q is true when both p and q are true and is false otherwise.
Example
p : “Today is Friday” and p q p∧q

q : “It is raining today”, T T T
p∧q : Today is Friday and it is raining today.
T F F
F T F
F F F

3. Disjunction- If p and q be propositions. The disjunction of p and q, is denoted by p ∨ q. The
disjunction p ∨ q is false when both p and q are false and is true otherwise.
Example
p q p∧q
p : “Today is Friday” and
q : “It is raining today”, T T T
p∨q : Today is Friday and it is raining today. T F F
F T F
F F F

4. Implication - If p and q be propositions. The conditional statement p → q is the proposition “if p,
then q”.
p is called hypothesis and q is called conclusion.
The conditional statement p → q is false when p is true and q is false, and true otherwise.
Example
p : sky is clear, p q p →q
q : we are able to see the stars
T T T
p→q : if sky is clear then we are able to see the stars.
T F F
F T T
KCS 071 Unit 3 F F T Ankita Singh

4. Bi-conditional- if p and q be propositions. The biconditional
statement p ↔ q is the proposition.
• p if and only q
• p is necessary and sufficient for q p q p↔q
• p iff q.
• p q = (p → q ) ∧ ( q → p)
T T T
• The biconditional statement p ↔ q is true when p and q have the
same values, and false otherwise. T F F
Eg. p: "A number is divisible by 2." F T F
q: "The number is even." F F T
p↔q : "A number is divisible by 2 if and only if the number is even."↔

Properties of Operators:
○ Commutativity:
○ P∧ Q= Q ∧ P, or
○ P ∨ Q = Q ∨ P.
○ Associativity:
○ (P ∧ Q) ∧ R= P ∧ (Q ∧ R),
○ (P ∨ Q) ∨ R= P ∨ (Q ∨ R)
○ Identity element:
○ P ∧ True = P,
○ P ∨ True= True.
○ Distributive:
○ P∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R).
○ P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R).
○ DE Morgan's Law:
○ ¬ (P ∧ Q) = (¬P) ∨ (¬Q)
○ ¬ (P ∨ Q) = (¬ P) ∧ (¬Q).
○ Double-negation elimination:
○ ¬ (¬P) = P.
Limitations of Propositional logic:
○ We cannot represent relations like ALL, some, or none with propositional logic. Example:
○ All the girls are intelligent.
○ Some apples are sweet.
○ Propositional logic has limited expressive power.
○ In propositional logic, we cannot describe statements in terms of their properties or logical relationships.

Inference
In artificial intelligence, we need intelligent computers which can create new logic from old logic or by evidence, so
generating the conclusions from evidence and facts is termed as Inference.
Inference rules:
Inference rules are the templates for generating valid arguments. Inference rules are applied to derive proofs in artificial
intelligence, and the proof is a sequence of the conclusion that leads to the desired goal.

Following are some terminologies related to inference rules:
○ Implication: It is one of the logical connectives which can be represented as P → Q. It is a

Boolean expression.
○ Converse: The converse of implication, which means the right-hand side proposition goes to
the left-hand side and vice-versa. It can be written as Q → P.
○ Contrapositive: The negation of converse is termed as contrapositive, and it can be
represented as ¬ Q → ¬ P.
○ Inverse: The negation of implication is called inverse. It can be represented as ¬ P → ¬ Q.

Hence from the above truth table, we can prove that P → Q is equivalent to ¬ Q → ¬ P, and Q→ P is equivalent to ¬ P
→ ¬ Q.

Types of Inference rules:
1. Modus Ponens
P and P → Q is true, then we can infer that Q will be true. It can be represented as:
2. Modus Tollens
The Modus Tollens rule state that if P→ Q is true and ¬ Q is true, then ¬ P will also true. It can be represented as:
3. Hypothetical Syllogism
The Hypothetical Syllogism rule state that if P→R is true whenever P→Q is true, and Q→R is true. It can be represented as
the following notation

4 Disjunctive Syllogism
The Disjunctive syllogism rule state that if P∨Q is true, and ¬P is true, then Q will be true.
5. Addition
The Addition rule is one the common inference rule, and it states that If P is true, then P∨Q will be true.
6. Simplification
The simplification rule state that if P∧ Q is true, then Q or P will also be true.
7. Resolution
The Resolution rule state that if P∨Q and ¬ P∧R is true, then Q∨R will also be true. I

Satisfiability, Validity, & Entailment
•S is satisfiable if it is true in some world
Eg. AVB, C
•S is unsatisfiable if it is false in all worlds
E.g., A Λ ~A
•S is valid if it is true in all worlds/models
Eg. A V~A, A-> A, (A Λ (A-> B)) ->B
•S1 entails S2 if wherever S1 is true S2 is also true

First Order Predicate Logic
PL is not sufficient to represent the complex sentences or natural language statements. The propositional logic
has very limited expressive power. Consider the following sentence, which we cannot represent using PL logic.
○ "Some humans are intelligent", or

○ "Sachin likes cricket."
Predicate logic in artificial intelligence, also known as first-order logic or first order predicate logic in AI, is a
formal system used in logic and mathematics to represent and reason about complex relationships and
structures.
FIRST-ORDER LOGIC is sufficiently expressive to represent a good deal of our commonsense knowledge.
It also either forms the foundation of many other representation languages and has been studied intensively
for many decades

○ First-order logic (like natural language) does not only assume that the world contains facts like
propositional logic but also assumes the following things in the world:
○ Objects: A, B, people, numbers, colors, wars, theories, squares, pits, wumpus, ......
○ Relations: It can be unary relation such as: red, round, is adjacent, or n-any relation
such as: the sister of, brother of, has color, comes between
○ Function: Father of, best friend, third inning of, end of, ......
○ As a natural language, first-order logic also has two main parts:

○ Syntax
○ Semantics

1. Terms: Terms are the basic building blocks representing objects or values in predicate logic. There are
three types of terms:
● Variables: Variables are symbols that represent objects or values in the domain of discourse. Commonly represented by
letters (e.g., x, y, z).
● Constants: Constants are specific, unchanging objects in the domain. They are typically represented by words or symbols
(e.g., "Alice," "42").
● Functions: Functions take one or more terms as arguments and return a new term. Functions are represented by
symbols or names (e.g., "f(x)", "Add(2, y)").
2. Atomic Formulas: Atomic formulas, also known as predicates, are statements that express
properties or relations about objects. They are constructed using:
● Predicate symbols (e.g., "IsHungry," "IsParent").

● Predicate symbols (e.g., "IsHungry," "IsParent").
● Terms as arguments (variables, constants, or functions).
● Examples:
● "IsHungry(x)" represents the atomic formula that asserts "x is hungry."
● "IsParent(Alice, Bob)" represents the atomic formula that asserts "Alice is a parent of Bob."
3. Logical Connectives: Logical connectives are used to build complex formulas by connecting atomic formulas or other logical
formulas. The primary logical connectives in predicate logic are:
● Conjunction (∧): Represents "and." For example, "IsHungry(x) ∧ IsEating(x)" means "x is hungry and x is eating."
● Disjunction (∨): Represents "or." For example, "IsHungry(x) ∨ IsThirsty(x)" means "x is either hungry or thirsty."
● Disjunction (∨): Represents "or." For example, "IsHungry(x) ∨ IsThirsty(x)" means "x is either hungry or thirsty."
● Negation (¬): Represents "not." For example, "¬IsHungry(x)" means "x is not hungry."
● Implication (→): Represents "if...then..." For example, "IsHuman(x) → IsMortal(x)" means "if x is human, then x is mortal."
● Biconditional (↔): Represents "if and only if." For example, "IsMarried(x, y) ↔ IsSpouse(x, y)" means "x is married to y if and only if x is a spouse of y."

Quantifiers in First-order logic:
○ These are the symbols that permit to determine or identify the range and scope of the variable
in the logical expression. There are two types of quantifier:
○ Universal Quantifier, (for all, everyone, everything)
○ Existential quantifier, (for some, at least one).

First-order logic statements can be divided into two parts:
○ Subject: Subject is the main part of the statement.

○ Predicate: A predicate can be defined as a relation, which binds two atoms together in a statement.
isInteger(x)
○ We can represent atomic sentences as Predicate (term1, term2, ......, term n).
Example: Ravi and Ajay are brothers: => Brothers(Ravi, Ajay).

Billy is a cat: => cat (Billy).
○ Complex sentences are made by combining atomic sentences using connectives.

Universal Quantifier:
The universal quantifier asserts that a statement is true for all objects in the domain of discourse.
The Universal quantifier is represented by a symbol ∀, which resembles an inverted A.
If x is a variable, then ∀x is read as:
○ For all x
○ For each x
○ For every x.
Note: In universal quantifier we use implication "→".

Existential Quantifier:
The existential quantifier asserts that there exists at least one object in the domain for which the
statement is true.
It is denoted by the logical operator ∃, which resembles as inverted E. When it is used with a
predicate variable then it is called as an existential quantifier.
If x is a variable, then existential quantifier will be ∃x or ∃(x). And it will be read as:
○ There exists a 'x.'

○ For some 'x.'
○ For at least one 'x.'
Note: in Existential quantifier we always use AND or Conjunction symbol (∧).

Negation
•¬ [∀x P(x)] = ∃x ¬P(x)
• ¬ [∃x P(x)] = ∀x ¬P(x)

Semantics of Predicate Logic:
The semantics of predicate logic determine whether a statement or formula is true or false. The truth value of a formula is evaluated
based on the interpretation of the predicate symbols, constants, variables, and the logical connectives.
1. Interpretation: An interpretation defines the domain of discourse (the set of objects), assigns meanings to constants, and specifies
the relationships defined by predicates. For example, in an interpretation, "Alice" might be assigned to a specific individual, "IsHungry"
might be defined to mean a person is hungry, and "IsParent" might represent the parent-child relationship.
2. Evaluation of Atomic Formulas: Atomic formulas are evaluated by substituting the constants or variables with their assigned
values in the interpretation. If the predicate holds for the specific objects and their relationships, the atomic formula is true; otherwise,
it is false.
3. Evaluation of Complex Formulas: Complex formulas are evaluated using truth tables, similar to propositional logic. Logical
connectives determine the truth value of compound statements based on the truth values of their component formulas. For example,
"IsHungry(x) ∧ IsEating(x)" is true if both "IsHungry(x)" and "IsEating(x)"

English Statement FOL (First-Order Logic)
1) Ram is a student. 1) Student(Ram)
2) Shyam is a teacher. 2) Teacher(Shyam)
3) Ram takes either Maths or Bio. 3) Takes(Ram, Maths) ∨

Takes(Ram, Bio)
4) Ram takes Bio if and only if Ram 4) Takes(Ram, Bio) ⟷

doesn't take Maths. ¬Takes(Ram, Maths)
5) There exists a student. 5) ∃x Student(x)
6) There exists a smart student. 6) ∃x (Student(x) ∧ Smart(x))
7) All students are smart. 7) ∀x (Student(x) ⟶ Smart(x))
8) Every student loves some student. 8) ∀x (Student(x) ⟶ ∃y

KCS 071 Unit 3 (Student(y) ∧ Loves(x, y))) Ankita Singh
Example- Convert to FOL
there is someone, whom no one like
∃x: There exists some person x.
∀y: For all people y (every person y).
¬Likes(y,x): No one y likes the person x.
Answer: ∃x∀y¬Likes(y,x)

for any given positive integer, there is a greater positive integer”
∀x: For all positive integers x,
∃y: there exists a positive integer y,
(y>x): such that y is greater than x.
G(y,x): y is greater than x
Answer: ∀x∃yG(y,x)

“not all rainy days are cold”
∃x: There exists at least one day x,
Rainy(x) such that it is a rainy day,
¬Cold(x) and that day is not cold.
Answer: ∃x(Rainy(x)∧¬Cold(x))

“Not all that glitters is gold”
∃x: There exists at least one object x,
Glitters(x): such that it glitters,
¬Gold(x) but it is not gold.
Answer: ∃x(Glitters(x)∧¬Gold(x))

Inference rules
Inference in First-Order Logic is used to deduce new facts or sentences from existing sentences. Before understanding the FOL inference rule,
Substitution: Substitution is a fundamental operation performed on terms and formulas. It occurs in all inference systems in first-order logic. The substitution is complex in the presence of
quantifiers in FOL. If we write F[a/x], so it refers to substitute a constant "a" in place of variable "x".
Equality:First-Order logic does not only use predicate and terms for making atomic sentences but also uses another way, which is equality in FOL. For this, we can use equality symbols which
specify that the two terms refer to the same object.
Example: Brother (John) = Smith.
As in the above example, the object referred by the Brother (John) is similar to the object referred by Smith. The equality symbol can also be used with negation to represent that two terms are not
the same objects.
Example: ￢(x=y) which is equivalent to x ≠y.
As propositional logic we also have inference rules in first-order logic, so following are some basic inference rules in FOL:
○ Universal Generalization
○ Universal Instantiation
○ Existential Instantiation
○ Existential introduction

Universal Generalization:
○ Universal generalization is a valid inference rule which states that if premise P(c) is true for any arbitrary
element c in the universe of discourse, then we can have a conclusion as ∀ x P(x).
○ It can be represented as
○ This rule can be used if we want to show that every element has a similar property.
Example: Let's represent, P(c): "A byte contains 8 bits", so for ∀ x P(x) "All bytes contain 8 bits.", it will also be true.

Universal instantiation (a.k.a. universal elimination)
○ Universal instantiation is also called as universal elimination or UI is a valid inference rule. It can be applied
multiple times to add new sentences.
○ The new KB is logically equivalent to the previous KB.
○ As per UI, we can infer any sentence obtained by substituting a ground term for the variable.
○ The UI rule state that we can infer any sentence P(c) by substituting a ground term c (a constant within domain
x) from ∀ x P(x) for any object in the universe of discourse.
Example:
IF "Every person like ice-cream"=> ∀x P(x) so we can infer that

"John likes ice-cream" => P(c)

Existential generalization(a.k.a. existential introduction)
○ An existential introduction is also known as an existential generalization, which is a valid inference rule in
first-order logic.
○ This rule states that if there is some element c in the universe of discourse which has a property P, then we
can infer that there exists something in the universe which has the property P.
○ It can be represented as:
○ Example: Let's say that,

"Priyanka got good marks in English."
"Therefore, someone got good marks in English."

Existential instantiation (a.k.a. existential elimination)
•Existential instantiation is also called as Existential Elimination, which is a valid inference rule in first-order logic.
○ It can be applied only once to replace the existential sentence.
○ The new KB is not logically equivalent to old KB, but it will be satisfiable if old KB was satisfiable.
○ This rule states that one can infer P(c) from the formula given in the form of ∃x P(x) for a new constant symbol c.
○ The restriction with this rule is that c used in the rule must be a new term for which P(c ) is true.
Example:
From the given sentence: ∃x Crown(x) ∧ OnHead(x, John),
So we can infer: Crown(K) ∧ OnHead( K, John), as long as K does not appear in the knowledge base.
○ The above used K is a constant symbol, which is called Skolem constant.
○ The Existential instantiation is a special case of Skolemization process.

Prolog Programming
● Prolog stands for programming in logic. In the logic programming paradigm, prolog language is most widely
available.
● Prolog is a declarative language, which means that a program consists of data based on the facts and rules
(Logical relationship) rather than computing how to find a solution.
● A logical relationship describes the relationships which hold for the given application.
● To obtain the solution, the user asks a question rather than running a program. When a user asks a question,
then to determine the answer, the run time system searches through the database of facts and rules.
● In prolog, logic is expressed as relations (called as Facts and Rules). Core heart of prolog lies at
the logic being applied. Formulation or Computation is carried out by running a query over these relations.

Applications of Prolog:
o Specification Language
o Robot Planning
o Natural language understanding
o Machine Learning
o Problem Solving
o Intelligent Database retrieval
o Expert System
o Automated Reasoning

Syntax and Basic Fields:
● In prolog, we declare some facts. These facts constitute the Knowledge Base of the system. We can query against the
Knowledge Base. We get output as affirmative if our query is already in the knowledge Base or it is implied by Knowledge
Base, otherwise we get output as negative.
● So, Knowledge Base can be considered similar to database, against which we can query. Prolog facts are expressed in
definite pattern.
● Facts contain entities and their relation. Entities are written within the parenthesis separated by comma (, ).Their
relation is expressed at the start and outside the parenthesis. Every fact/rule ends with a dot (.). So, a typical prolog fact
goes as follows

Syntax
Prolog language has various elements −
Facts − A fact is a predicate expression that makes a declarative statement about the problem domain. Whenever a variable
occurs in a Prolog expression, it is assumed to be universally quantified.
Eg. likes(john, susie). /* John likes Susie */
Rules − A rule is a predicate expression that uses logical implication (:-) to describe a relationship among facts.
Thus a Prolog rule takes the form left_hand_side :- right_hand_side .
This sentence is interpreted as: left_hand_side if right_hand_side. The left_hand_side is restricted to a single, positive, literal, which means
it must consist of a positive atomic expression. It cannot be negated and it cannot contain logical connectives.
This notation is known as a Horn clause. In Horn clause logic, the left hand side of the clause is the conclusion, and must be a single
positive literal. The right hand side contains the premises. The Horn clause calculus is equivalent to the first-order predicate calculus.
Examples of valid rules:

friends(X,Y) :- likes(X,Y),likes(Y,X). /* X and Y are friends if they like each other */
hates(X,Y) :- not(likes(X,Y)). /* X hates Y if X does not like Y. */
Questions/Query − The Prolog interpreter responds to queries about the facts and rules represented in its database. The database is
assumed to represent what is true about a particular problem domain. In making a query you are asking Prolog whether it can prove that
your query is true. If so, it answers "yes" and displays any variable bindings that it made in coming up with the answer. If it fails to prove
the query true, it answers "No".

Variables and Names
Variables begin with an uppercase letter. Predicate names, function names, and the names for objects must begin with
a lowercase letter. Rules for forming names are the same as for the predicate calculus..
Constants
Numbers, written with a lowercase letter, or enclosed in single quotes.
Symbols
Prolog expressions are comprised of the following truth-functional symbols, which have the same interpretation as in
the predicate calculus.
All Prolog sentences must end with a period.

Format : relation(entity1, entity2, ....k'th entity).
Example:
friends(raju, mahesh).
singer(sonu).
odd_number(5).
Explanation :
These facts can be interpreted as :
raju and mahesh are friends.
sonu is a singer.
5 is an odd number.

Key Features :
1. Unification : The basic idea is, can the given terms be made to represent the same structure.
2. Backtracking : When a task fails, prolog traces backwards and tries to satisfy previous task.
3. Recursion : Recursion is the basis for any search in program.
Advantages :
1. Easy to build database. Doesn’t need a lot of programming effort.
2. Pattern matching is easy. Search is recursion based.
3. It has built in list handling. Makes it easier to play with any algorithm involving lists.
Disadvantages :
1. LISP (another logic programming language) dominates over prolog with respect to I/O features.
2. Sometimes input and output is not easy.
Applications :
Prolog is highly used in artificial intelligence(AI). Prolog is also used for pattern matching over
KCS 071 language
natural Unit 3 parse trees. Ankita Singh
Unification
● Unification in First-Order Logic (FOL) is a process of making two logical expressions identical by finding a substitution
for their variables.
● Unification tries to determine if there exists a substitution that, when applied to the terms or predicates, makes the two
expressions syntactically identical.
● Let Ψ1 and Ψ2 be two atomic sentences and 𝜎 be a unifier such that, Ψ1𝜎 = Ψ2𝜎, then it can be expressed as UNIFY(Ψ1, Ψ2).
Example: Find the MGU for Unify{King(x), King(John)}
Let Ψ1 = King(x), Ψ2 = King(John),
Substitution θ = {John/x} is a unifier for these atoms and applying this substitution, and both expressions will be identical.

Key Concepts:
Terms: These are the basic objects in FOL, which include variables, constants, and functions.
● Variable: A symbol representing an arbitrary element (e.g., x, y).

● Constant: A symbol representing a specific object (e.g., a, b).
● Function: A mapping from a set of terms to a term (e.g., f(x)).
Substitution: This is the process of replacing variables in a term with other terms (which could be variables or constants). For
example, the substitution {x → a} replaces the variable x with the constant a.
Unifier: A substitution that, when applied to two expressions, makes them identical. If such a substitution exists, the
expressions are said to be unifiable.
Most General Unifier (MGU): The most general unifier is the substitution that unifies two expressions in the most general way,
meaning that any other unifier can be derived from this one by further substitutions.

Conditions for Unification:
1. Same Predicate or Function:
○ If the two expressions being unified are predicates or functions, they must have the same predicate or function
symbol, and they must have the same arity (number of arguments).
○ Example: P(x) can be unified with P(a), but P(x) cannot be unified with Q(x) because the predicate symbols P and Q
are different.
2. Matching Constants:
○ If two terms are constants, they must be identical to unify. If they are different constants, unification fails.
○ Example: a and a can be unified, but a and b cannot.
3. Unifying Variables:
○ A variable can be unified with a constant, another variable, or a compound term (like a function or predicate with
arguments). This is done by substituting the variable with the appropriate term.
○ Example: x can be unified with a, or with a more complex term like f(y).
4. Non-Occurs Check:
○ A variable cannot be unified with a term that contains that same variable (this would lead to an infinite loop). This
is known as the occurs-check condition.
○ Example: x cannot be unified with f(x) because x occurs within the term f(x). This would cause a circular reference,
leading to an unsolvable situation.

Steps of Unification:
Given two expressions A and B, unification works as follows:
1. Compare the expressions: Check if the top-level function symbols or constants are the same. If not, the expressions are
not unifiable.
2. Check variables: If one of the terms is a variable, apply a substitution to make the expressions match.
○ Example: To unify P(x) and P(a), you can substitute x with a.
3. Recursive unification: If the expressions contain sub-terms (e.g., functions or predicates with arguments), repeat the
process for each argument.
4. Apply the unifier: If possible, apply the most general unifier to both expressions to make them identical.

Example:
Let’s unify the expressions f(x,g(y))and f(a,g(z))
1. Start by comparing the outermost functions: both are f, so proceed to unify the arguments.
2. Unify the first arguments: x and a. The substitution {x→a}will make the first arguments the same.
3. Now unify the second arguments: g(y) and g(z). Since both are functions with the same outer function g, unify the inner
arguments y and z, giving the substitution {y→z}.
4. The unification succeeds with the final substitution {x→a,y→z}.

Solve
Trace the operation of the unification algorithm on each of the following pairs of literals:
I. f(Marcus)and f(Caesar)
II. f(x)and f(g(y))
III. f(Marcus,g(x,y)) and f(x,g(Caesar,Marcus))

Solution
I. f(Marcus) and f(Caesar)
Step 1: Ψ1 = f(Marcus) Ψ2 =f(Caeser), Check if the function symbols match. In this case, both are f, so we proceed to unify the
arguments.
Step 2: Compare the arguments. Here, we have Marcus and Caesar, which are two distinct constants.
Since constants cannot be unified if they are different, the unification fails.
Result: Unification fails for this pair.

II. f(x)and f(g(y))
Step 1: Ψ1 = f(x) Ψ2 =f(g(y)),
Step 2: Unify the arguments. Here, we need to unify x (a variable) with g(y) (a function). Variables can be unified with functions, so
we substitute x with g(y).
Substitution Ө = {g(y) / x}
Ψ1 = f(g(y)) Ψ2 =f(g(y)),
Result: The most general unifier (MGU) is {g(y) / x}

III. f(Marcus,g(x,y)) and f(x,g(Caesar,Marcus))
Step 1: Ψ1 = f(Marcus,g(x,y)) Ψ2 =f(x,g(Caesar,Marcus))
Step 2: Unify the first pair of arguments: Marcus and x. Since x is a variable, it can be unified with the constant Marcus.
Substitution Ө={Marcus/x}
Ψ1 = (Marcus,g(Marcus,y)) Ψ2 =f(Marcus,g(Caesar,Marcus))
Step 3: Now, we move to the second pair: g(x,y) and g(Caesar, Marcus). Since both are functions with the same symbol g, we can
unify their arguments. Notice after substituting x with Marcus, we now need to unify g(Marcus, y) with g(Caesar, Marcus).
Substitution Ө={Caeser/Marcus} Unify Marcus (first argument) with Caesar: This fails, as constants Marcus and Caesar
cannot be unified.
Result: Unification fails for this pair after substitution.

Forward Chaining-Backward Chaining:
The inference engine is the component of the intelligent system in artificial intelligence, which applies logical rules to the
knowledge base to infer new information from known facts.
The first inference engine was part of the expert system.
Inference engine commonly proceeds in two modes, which are:
a) Forward chaining
b) Backward chaining

Example
Problem: You have the following rules and facts, and you want to find out if "John has a fever."
Facts:
John has a cough.
John has a sore throat.
Rules:
If a person has a cough and a sore throat, they have the flu.
If a person has the flu, they have a fever.

Forward Chaining
Forward chaining is also known as a forward deduction or forward reasoning method when using an inference engine.
Forward chaining is a form of reasoning which start with atomic sentences in the knowledge base and applies inference rules
(Modus Ponens) in the forward direction to extract more data until a goal is reached.
The Forward-chaining algorithm starts from known facts, triggers all rules whose premises are satisfied, and add their
conclusion to the known facts. This process repeats until the problem is solved.
Properties of Forward-Chaining:
● It is a bottom-up approach, as it moves from bottom to top.

● It is a process of making a conclusion based on known facts or data, by starting from the initial state and reaches the goal
state.
● Forward-chaining approach is also called as data-driven as we reach to the goal using available data.
● Forward -chaining approach is commonly used in the expert system, such as CLIPS, business, and production rule
systems.

Example:
"As per the law, it is a crime for an American to sell weapons to hostile nations. Country A, an enemy of America, has some
missiles, and all the missiles were sold to it by Robert, who is an American citizen."
Prove that "Robert is criminal."

To solve the above problem, first, we will convert all the above facts into first-order definite clauses, and then we will use a forward-chaining algorithm to
reach the goal.
Facts Conversion into FOL:

● It is a crime for an American to sell weapons to hostile nations. (Let's say p, q, and r are variables)
American (p) ∧ weapon(q) ∧ sells (p, q, r) ∧ hostile(r) → Criminal(p) ...(1)
● Country A has some missiles. ∃p Owns(A, p) ∧ Missile(p). It can be written in two definite clauses by using Existential Instantiation, introducing
new Constant T1.
Owns(A, T1) ......(2)
Missile(T1) .......(3)
● All of the missiles were sold to country A by Robert.

∀p Missiles(p) ∧ Owns (A, p) → Sells (Robert, p, A) ......(4)
"As per the law, it is a crime for an American to sell weapons to hostile
● Missiles are weapons.
nations. Country A, an enemy of America, has some missiles, and all the
Missile(p) → Weapons (p) .......(5) missiles were sold to it by Robert, who is an American citizen."
● Enemy of America is known as hostile.
Enemy(p, America) →Hostile(p) ........(6)
● Country A is an enemy of America.
Enemy (A, America) .........(7)
● Robert is American
American(Robert). ..........(8)

Forward chaining proof:
Step-1:
In the first step we will start with the known facts and will choose the sentences which do not have implications, such as:
American(Robert), Enemy(A, America), Owns(A, T1), and Missile(T1). All these facts will be represented as below.
American (p) ∧ weapon(q) ∧ sells (p, q, r) ∧ hostile(r) → Criminal(p) ...(1)
Owns(A, T1) ......(2)
Missile(T1) .......(3)
Missile(p) → Weapons (p) .......(5)

Step-2:
At the second step, we will see those facts which infer from available facts and with satisfied premises.
Rule-(1) does not satisfy premises, so it will not be added in the first iteration.
Rule-(2) and (3) are already added.
Rule-(4) satisfy with the substitution {p/T1}, so Sells (Robert, T1, A) is added, which infers from the conjunction of Rule (2) and (3).
Rule-(6) is satisfied with the substitution(p/A), so Hostile(A) is added and which infers from Rule-(7).
American (p) ∧ weapon(q) ∧ sells (p, q, r) ∧ hostile(r) →

Criminal(p) ...(1)
Owns(A, T1) ......(2)
Missile(T1) .......(3)

Step-3:
At step-3, as we can check Rule-(1) is satisfied with the substitution {p/Robert, q/T1, r/A}, so we can add Criminal(Robert) which infers all the
available facts. And hence we reached our goal statement.
American (p) ∧ weapon(q) ∧ sells (p, q, r) ∧ hostile(r) →

Criminal(p) ...(1)
Owns(A, T1) ......(2)
Missile(T1) .......(3)

Backward Chaining:
Backward-chaining is also known as a backward deduction or backward reasoning method when using an inference engine. A backward chaining
algorithm is a form of reasoning, which starts with the goal and works backward, chaining through rules to find known facts that support the goal.
Properties of backward chaining:
● It is known as a top-down approach.

● Backward-chaining is based on modus ponens inference rule.
● In backward chaining, the goal is broken into sub-goal or sub-goals to prove the facts true.
● It is called a goal-driven approach, as a list of goals decides which rules are selected and used.
● Backward -chaining algorithm is used in game theory, automated theorem proving tools, inference engines, proof assistants, and various AI
applications.
● The backward-chaining method mostly used a depth-first search strategy for proof.

Example:

Backward-Chaining proof:
In Backward chaining, we will start with our goal predicate, which is Criminal(Robert), and then infer further rules.
Step-1:
At the first step, we will take the goal fact. And from the goal fact, we will infer other facts, and at last, we will prove those facts true. So our goal fact
is "Robert is Criminal," so following is the predicate of it.

Step-2:
At the second step, we will infer other facts form goal fact which satisfies the rules. So as we can see in Rule-1, the goal predicate Criminal (R
present with substitution {Robert/P}. So we will add all the conjunctive facts below the first level and will replace p with Robert.
Here we can see American (Robert) is a fact, so it is proved here

American (p) ∧ weapon(q) ∧ sells (p, q, r) ∧
hostile(r) → Criminal(p) ...(1)
Owns(A, T1) ......(2)
Missile(T1) .......(3)
∀p Missiles(p) ∧ Owns (A, p) → Sells (Robert, p,

A) ......(4)

Step-3:t At step-3, we will extract further fact Missile(q) which infer from Weapon(q), as it satisfies Rule-(5). Weapon (q) is also true with the
substitution of a constant T1 at q.

Owns(A, T1) ......(2)
Missile(T1) .......(3)
∀p Missiles(p) ∧ Owns (A, p) → Sells (Robert,

p, A) ......(4)

At step-4, we can infer facts Missile(T1) and Owns(A, T1) form Sells(Robert, T1, r) which satisfies the Rule- 4, with the substitution of A in place of r. So
these two statements are proved here.
American (p) ∧ weapon(q) ∧ sells (p, q, r)

∧ hostile(r) → Criminal(p) ...(1)
Owns(A, T1) ......(2)
Missile(T1) .......(3)
∀p Missiles(p) ∧ Owns (A, p) → Sells

(Robert, p, A) ......(4)
Enemy(p, America) →Hostile(p)

........(6)

Step-5:
At step-5, we can infer the fact Enemy(A, America) from Hostile(A) which satisfies Rule- 6. And hence all the statements are proved true using
backward chaining.

Owns(A, T1) ......(2)
Missile(T1) .......(3)
∀p Missiles(p) ∧ Owns (A, p) → Sells (Robert,

p, A) ......(4)

Resolution
● Resolution is a theorem proving technique that proceeds by building refutation proofs, i.e., proofs by
contradictions. It was invented by a Mathematician John Alan Robinson in the year 1965.
● Resolution is used, if there are various statements are given, and we need to prove a conclusion of those
statements.
● Unification is a key concept in proofs by resolutions.
● Resolution is a single inference rule which can efficiently operate on the conjunctive normal form or clausal
form.

Steps for Resolution:
1. Conversion of facts into first-order logic.
2. Convert FOL statements into CNF
3. Negate the statement which needs to prove (proof by contradiction)
4. Draw resolution graph (unification).
To better understand all the above steps, we will take an example in which we will apply resolution.

Example:
a. John likes all kind of food.
b. Apple and vegetable are food
c. Anything anyone eats and not killed is food.
d. Anil eats peanuts and still alive
e. Harry eats everything that Anil eats.
Prove by resolution that: John likes peanuts.

Step-1: Conversion of Facts into FOL
In the first step we will convert all the given statements into its first order logic.
a. John likes all kind of food.

b. Apple and vegetable are food
c. Anything anyone eats and not killed is food.
d. Anil eats peanuts and still alive
e. Harry eats everything that Anil eats.
To Prove: John likes peanuts.

Step-2: Conversion of FOL into CNF
In First order logic resolution, it is required to convert the FOL into CNF as CNF form makes easier for resolution proofs.
Conversion to Conjunctive Normal Form (CNF) involves several steps:
1) Eliminate all implications,

2) Move negations inward,
3) standardizing variables,
4) Skolemization,
5) Converting to a conjunction of disjunctions.
1. Eliminate all implication (→) and rewrite (by following equivalence rule P→Q is equivalent to ¬P∨Q)
a. ∀x: food(x) → likes(John, x) a. ∀x ¬ food(x) V likes(John, x)
b. food(Apple) ∧ food(vegetables) b. food(Apple) Λ food(vegetables)
c. ∀x ∀y: eats(x, y) ∧ ¬killed(x) → food(y) c. ∀x ∀y ¬ [eats(x, y) Λ ¬ killed(x)] V food(y)
d. eats(Anil, Peanuts) ∧ alive(Anil) d. eats (Anil, Peanuts) Λ alive(Anil)
e. ∀x : eats(Anil, x) → eats(Harry, x) e. ∀x ¬ eats(Anil, x) V eats(Harry, x)
f. ∀x: ¬killed(x) → alive(x) f. ∀x¬ [¬ killed(x) ] V alive(x)
g. ∀x: alive(x) → ¬killed(x)
g. ∀x ¬ alive(x) V ¬ killed(x)
likes(John, Peanuts)
2. Move negation (¬)inwards and rewrite
a. ∀x ¬ food(x) V likes(John, x) a. ∀x ¬ food(x) V likes(John, x)

b. food(Apple) Λ food(vegetables) b. food(Apple) Λ food(vegetables)
c. ∀x ∀y ¬ [eats(x, y) Λ ¬ killed(x)] V food(y) c. ∀x ∀y ¬ eats(x, y) V killed(x) V food(y)
d. eats (Anil, Peanuts) Λ alive(Anil) d. eats (Anil, Peanuts) Λ alive(Anil)
e. ∀x ¬ eats(Anil, x) V eats(Harry, x) e. ∀x ¬ eats(Anil, x) V eats(Harry, x)
f. ∀x¬ [¬ killed(x) ] V alive(x) f. ∀x killed(x) V alive(x)
likes(John, Peanuts).

3. Rename variables or standardize variables
a. ∀x ¬ food(x) V likes(John, x) a. ∀x ¬ food(x) V likes(John, x)

b. food(Apple) Λ food(vegetables) b. food(Apple) Λ food(vegetables)
c. ∀x ∀y ¬ eats(x, y) V killed(x) V food(y) c. ∀y ∀z ¬ eats(y, z) V killed(y) V food(z)
d. eats (Anil, Peanuts) Λ alive(Anil) d. eats (Anil, Peanuts) Λ alive(Anil)
e. ∀x ¬ eats(Anil, x) V eats(Harry, x) e. ∀w¬ eats(Anil, w) V eats(Harry, w)
f. ∀x killed(x) V alive(x)
f. ∀g killed(g) V alive(g)
g. ∀k ¬ alive(k) V ¬ killed(k)
likes(John, Peanuts). h. likes(John, Peanuts).

4. Skolemization (It is a process in FOL used to remove existential quantifiers (∃) by replacing them with Skolem constants or Skolem
functions. )
When converting a formula to CNF, we need to eliminate existential quantifiers while preserving the formula’s logical equivalence.
Skolemization accomplishes this by replacing existentially quantified variables with function or constants(making the formula simpler and
easier to work with in proofs.
In this example problem since there is no existential quantifier so all the statements will remain same in this step.
5. Converting to a conjunction of disjunctions.

In this step we will drop all universal quantifier. we assume that all statements are universally quantified, so we can omit the universal
quantifiers.
a. ∀x ¬ food(x) V likes(John, x) a) ¬ food(x) V likes(John, x)
b. food(Apple) Λ food(vegetables) b) food(Apple)
c. ∀y ∀z ¬ eats(y, z) V killed(y) V food(z) c) food(vegetables)
d. eats (Anil, Peanuts) Λ alive(Anil) d) ¬ eats(y, z) V killed(y) V food(z)
e. ∀w¬ eats(Anil, w) V eats(Harry, w) e) eats (Anil, Peanuts)
f. ∀g killed(g) ] V alive(g) f) alive(Anil)
g. ∀k ¬ alive(k) V ¬ killed(k) g) ¬ eats(Anil, w) V eats(Harry, w)
likes(John, Peanuts). h) killed(g) V alive(g)
i) ¬ alive(k) V ¬ killed(k)

Step-3: Negate the statement to be proved
In this statement, we will apply negation to the conclusion statements, which will be written as ¬likes(John, Peanuts)
Step-4: Draw Resolution graph:
Now in this step, we will solve the problem by resolution tree using substitution. For the above problem, it will be given as follows:
resolution rule
a) ¬ food(x) V likes(John, x)
b) food(Apple)
c) food(vegetables)
d) ¬ eats(y, z) V killed(y) V food(z)
e) eats (Anil, Peanuts)
f) alive(Anil)
g) ¬ eats(Anil, w) V eats(Harry, w)
h) killed(g) V alive(g)
i) ¬ alive(k) V ¬ killed(k)

Hence the negation of the conclusion has been proved as a complete contradiction with the given set of statements.
Explanation of Resolution graph:

● In the first step of resolution graph, ¬likes(John, Peanuts) , and likes(John, x) get resolved(canceled) by substitution of
{Peanuts/x}, and we are left with ¬ food(Peanuts)
● In the second step of the resolution graph, ¬ food(Peanuts) , and food(z) get resolved (canceled) by substitution of {
Peanuts/z}, and we are left with ¬ eats(y, Peanuts) V killed(y) .
● In the third step of the resolution graph, ¬ eats(y, Peanuts) and eats (Anil, Peanuts) get resolved by substitution
{Anil/y}, and we are left with Killed(Anil) .
● In the fourth step of the resolution graph, Killed(Anil) and ¬ killed(k) get resolve by substitution {Anil/k}, and we are left
with ¬ alive(Anil) .
● In the last step of the resolution graph ¬ alive(Anil) and alive(Anil) get resolved.

Knowledge Representation
In artificial intelligence (AI), knowledge representation is a critical area that enables systems to simulate
human-like reasoning and decision-making. Various techniques are employed to represent knowledge in AI
systems, each with specific applications and advantages.
Here are some key techniques:
Logic-Based Representation:
• Propositional Logic: Uses simple statements that are either true or false.
• Predicate Logic: Extends propositional logic with predicates that can express relations among objects and
quantifiers to handle multiple entities.
• Example: Representing the relationship, "All humans are mortal," can be written in predicate logic as
∀x (Human(x) → Mortal(x)).

Semantic Networks:
• Graph structures used to represent semantic relations between concepts. Nodes represent objects or concepts, and edges represent the
relations between them.
• Example: A node for "Socrates" linked by an "is a" edge to a "Human" node, and
"Human" linked to "Mortal".
Components of Semantic Networks
1. Nodes: These represent objects, concepts, or entities. For instance, "Dog," "Animal," "Barks," and "Has Fur" might each be a node in a
network.
2. Edges: These represent relationships between nodes. Common relationships include:
○ Is-a (Inheritance): Shows class-subclass relationships. For example, "Dog is-a Animal."
○ Has-a (Possession): Shows possession relationships. For example, "Dog has Fur."
○ Part-of (Composition): Shows part-whole relationships, such as "Engine part-of Car."
3. Properties and Attributes: Nodes can have specific attributes or properties. For example, a "Dog" node may have properties like
"Color," "Size," or "Breed."
4. Inheritance: Properties and relationships can be inherited in a hierarchy. If "Dog is-a Animal" and "Animals breathe," then "Dog"
inherits the "breathe" property.

Frame-Based Representation:
• A frame is a record like structure which consists of a collection of attributes and its values to describe an entity in the
world.
• Frames are the AI data structure which divides knowledge into substructures by representing stereotypes situations.
It consists of a collection of slots and slot values. These slots may be of any type and sizes. Slots have names and
values which are called facets.
• Frames are derived from semantic networks and later evolved into our modern-day classes and objects.
• Example: A frame for "Bird" might include properties like "has feathers," "can fly," and actions like "lay eggs."
Production Rules:
• Consist of sets of rules in the form of IF-THEN constructs that are used to derive conclusions from given data.
• Example: IF the patient has a fever and rash, THEN consider a diagnosis of measles.

Ontological Engineering
● In ontological engineering an entire knowledge base is structured in ways that mirror human
understanding.
● Complex domains such as shopping on the Internet or driving a car in traffic require more general and
flexible representations.
● Representations of abstract concepts such as Events, Time, Physical Objects, and Beliefs that occur
in many different domains is called ontological engineering.
● Representing everything in the world is overwhelming, so rather than describing everything in detail,
we’ll create a foundational framework with placeholders.
● For instance, we’ll define general concepts like “physical object,” and specific details about types of
objects (such as robots, televisions, or books) can be added as needed. This allows new knowledge to
be integrated into the framework over time without needing an exhaustive initial description.

The general framework of concepts is called an upper ontology because of the convention of drawing graphs with
the general concepts at the top and the more specific concepts below them

Categories
● The organization of objects into categories is a vital part of knowledge representation.
● While interactions happen with specific objects, much reasoning occurs at the category level. For instance,
someone may aim to buy a basketball in general, not a specific one like BB9.
● Categories also serve to make predictions about objects once they are classified. For example, based on its
appearance and placement in the fruit aisle, one can identify an object as a watermelon, and infer it's suitable
for a fruit salad.
● In first-order logic, categories can be represented either as predicates (e.g., Basketball(b)) or reified as objects
(e.g., Basketballs, with b∈Basketballs indicating membership).
● Categories also organize knowledge through inheritance; properties assigned to a broader category are
passed down to its subcategories. For example, if all Food is edible, and Fruit and Apples are subclasses, then all
apples are edible by inheritance.
● Categories are arranged in taxonomies (hierarchies) to reflect subclass relationships. This has applications in
biology, library science, and government systems, where organized classifications simplify knowledge.

First-order logic makes it easy to state facts about categories, either by relating objects to categories or by quantifying over their
members. Here are some types of facts, with examples of each:
• An object is a member of a category.

BB9 ∈ Basketballs
• A category is a subclass of another category.

Basketballs ⊂ Balls
• All members of a category have some properties.

(x∈ Basketballs) ⇒ Spherical (x)
• Members of a category can be recognized by some properties.

Orange(x) ∧ Round (x) ∧ Diameter(x)=9.5 ∧ x∈ Balls ⇒ x∈ Basketballs
• A category as a whole has some properties.

Dogs ∈DomesticatedSpecies
Notice that because Dogs is a category and is a member of DomesticatedSpecies , the latter must be a category of categories.
These structures enable efficient reasoning and knowledge simplification in AI systems.

● Although subclass and member relations are the most important ones for categories, we also
want to be able to state relations between categories that are not subclasses of each other.
● We say that two or more categories are disjoint if they have no members in common. For
example, Males and Females are disjoint subsets of Animals because a male cannot be a
female.
● However, if Males and Females cover all possibilities within Animals, then they form an
exhaustive decomposition, meaning every animal must be either male or female.
● When categories are both disjoint and exhaustive, they form a partition. Examples include:
Disjoint({Animals,Vegetables})
ExhaustiveDecomposition({Americans,Canadians, Mexicans},NorthAmericans)
Partition({Males, Females}, Animals) .
(Note that the ExhaustiveDecomposition of NorthAmericans is not a Partition, because some
people have dual citizenship.)

Physical composition
The idea that one object can be part of another is a familiar one. One’s nose is part of one’s head, Romania is part of Europe.
Objects can be grouped into PartOf hierarchies, reminiscent of the Subset hierarchy:
PartOf (Bucharest , Romania)
PartOf (Romania, Europe)
PartOf (Europe, Earth) .
The PartOf relation is transitive and reflexive; that is,
PartOf (x, y) ∧ PartOf (y, z) ⇒ PartOf (x, z) .
PartOf (x, x) .
Therefore, we can conclude PartOf (Bucharest , Earth).

Measurements
● Objects have properties like height, mass, cost,etc, Values that we assign to these properties are called
measures such as Inches(1.5) or Centimeters(3.81),
● While some properties like length are easy to quantify, others—such as difficulty, beauty, or
deliciousness—are harder to measure numerically,
● Such measures can still be meaningfully ordered (e.g., Exercise A is tougher than Exercise B). These
qualitative comparisons are sufficient for decision-making and form the foundation of qualitative physics, a
subfield of AI focused on reasoning about physical systems without exact numerical values.

Objects
● The real world consists of primitive objects (e.g., atomic particles) and composite objects (like cars and apples).To manage
complexity, we often reason at the level of large objects rather than individual particles.
● By reasoning at the level of large objects such as apples and cars, we can overcome the complexity involved in dealing with
vast numbers of primitive objects individually.
● Types of Objects:
● Stuff- Refers to materials or substances without clear individual boundaries or distinct units. Eg. Butter
● Things- Refers to discrete, countable objects with clear boundaries and individuality. Eg. dog
Stuff differs from things in that parts of stuff are also still that stuff, unlike discrete objects (e.g., half a dog is not two dogs).
● Objects has intrinsic properties (like density and color) which belong to the very substance of the object, rather than to the
object as a whole whereas extrinsic properties (like weight and shape) are not retained after subdivision.
● Categories defined by intrinsic properties are stuff / substance / mass noun, while those with extrinsic properties are Things /
count noun.

Events
Events: These are actions or occurrences, like "a dog barking" or "rain falling." Representing events helps the AI understand how
the world changes over time.’
Event calculus is a logical framework used in artificial intelligence to model and reason about events and their effects over
time.
Components of Event Calculus:
1. Time: Events are tied to specific times or intervals, enabling us to track when changes happen and how long they last.
2. Fluents: Properties or conditions that may vary over time (e.g., At(Shankar, Berkeley)). Fluents do not imply truth by
themselves; we use a predicate to confirm whether a fluent holds at a particular time.
The fluent At(Shankar, Berkeley): is an object that refers to the fact of Shankar being in Berkeley, but does not by itself
say anything about whether it is true.
To assert that a fluent is actually true at some point in time we use the predicate T, as in T(At(Shankar, Berkeley), t).
3. Events: Occurrences or actions that can cause changes in the state of the world. For example, Shankar flying from SF to DC
is an event that may alter Shankar's location. E1 ∈ Flyings(Shankar , SF , DC) .

● The complete set of predicates for one version of the event calculus is T(f, t) Fluent f is true at time t
T(f, t) Fluent f is true at time t
Happens(e, i) Event e happens over the time interval i
Initiates(e, f, t) Event e causes fluent f to start to hold at time t
Terminates(e, f, t) Event e causes fluent f to cease to hold at time t
Clipped(f, i) Fluent f ceases to be true at some point during time interval i
Restored (f, i) Fluent f becomes true sometime during time interval i

Processes
● Discrete events have a definite structure. Shankar’s trip has a beginning, middle, and
end.If interrupted halfway, the event would be something different—it would not be a
trip from San Francisco to Washington, but instead a trip from San Francisco to
somewhere over Kansas.
● On the other hand, the category of events denoted by Flyings has a different quality. If
we take a small interval of Shankar’s flight, say, the third 20-minute segment , that
event is still a member of Flyings.
● Any process e that happens over an interval also happens over any subinterval.
● Categories of events with this property are called process categories or liquid event
categories.
(e∈Processes)∧Happens(e,(t1,t4))∧(t1<t2<t3<t4)⇒Happens(e,(t2,t3))

Mental Events and Mental Objects
Knowledge about one’s own knowledge and reasoning processes is useful for controlling inference.
For example, suppose Alice asks “what is the square root of 1764” and Bob replies “I don’t know.” If Alice insists “think
harder,” Bob should realize that with some more thought, this question can in fact be answered. On the other hand,
if the question was “Is your mother sitting down right now?” then Bob should realize that thinking harder is unlikely to
help.
we need is a model of the mental objects that are in someone’s head (or something’s knowledge base) and of the
mental processes that manipulate those mental objects.
Mental Objects are the static entities within an agent's mind, like ideas, beliefs, or memories.
Mental Events refer to the occurrences that happen within an agent's mind, such as thoughts, decisions, or
intentions.

Propositional Attitudes and Their Challenges
Propositional attitudes, like Believes, Knows, and Intends, are attitudes an agent has towards mental objects e.g., "Lois knows that
Superman can fly").
Unlike normal predicates, they don’t follow standard logical rules, particularly when dealing with equality.
For instance, Knows(Lois, CanFly(Superman)) .
(Superman = Clark) ∧ Knows(Lois , CanFly(Superman))|= Knows(Lois, CanFly(Clark )) .
if "Superman is Clark Kent" is true, standard logic would imply that "Lois knows Clark can fly," even though Lois doesn't know
Superman's true identity.
In cases, if our agent knows that 2 + 2 = 4 and 4 < 5, then we want our agent to know that 2 + 2 < 5. This property is called
referential transparency
Thus in standard logic (with referential transparency), terms can be swapped freely if they refer to the same entity. However,
propositional attitudes require referential opacity—where the terms matter because agents might not know they refer to the
same thing. This means we can’t always substitute "Clark" for "Superman" without changing the meaning for an agent like Lois.

Using Modal Logic
● Regular logic is concerned with a single modality, the modality of truth, allowing us to express “P is true.” Modal logic
includes special modal operators that take sentences (rather than terms) as arguments. For example, “A knows P” is
represented with the notation KAP, where K is the modal operator for knowledge.
● It takes two arguments, an agent (written as the subscript) and a sentence. The syntax of modal logic is the same as
first-order logic, except that sentences can also be formed with modal operators.
● Agents' knowledge can be represented as "possible worlds"(rather than just one true world) connected by accessibility
relations(one relation for each modal operator), which show what an agent can know or believe. For instance, Lois might
have access to worlds where "Superman is not Clark," reflecting her incomplete knowledge.
Limitations of Modal Logic

● While modal logic models knowledge, it also assumes agents can deduce every logical consequence of their knowledge
(logical omniscience). This assumption isn’t realistic, especially for belief, as it suggests agents are capable of infinite
logical reasoning. Solutions for limited rationality (bounded reasoning steps or time) are still a work in progress.
● In summary, modal logic and possible worlds help handle the complexity of knowledge and belief but come with
challenges in representing realistic reasoning limits.

Reasoning Systems for Categories
There are two closely related families of reasoning systems for categories:
1.Semantic networks provide graphical aids for visualizing a knowledge base and efficient algorithms for inferring properties of
an object on the basis of its category membership;
2.Description logics provide a formal language for constructing and combining category definitions and efficient algorithms for
deciding subset and superset relationships between categories

Semantic Network
● Semantic networks, are capable of representing
individual objects, categories of objects, and relations
among objects.
● A typical graphical notation displays object or category

names in ovals or boxes, and connects them with labeled
links.
● For example, Figure has a MemberOf link between Mary

and FemalePersons , corresponding to the logical
assertion : Mary ∈FemalePersons ;
similarly, the SisterOf link between Mary and John

corresponds to the assertion SisterOf (Mary, John). HasMother is a relation between a person and his
or her mother, and categories do not have
We can connect categories using SubsetOf links, and so mothers.For this reason, we have used a special
on. notation—the double-boxed link—in Figure This link
asserts that∀x x∈ Persons ⇒ [∀ y HasMother (x,y)
⇒ y ∈ FemalePersons
The semantic network notation makes it convenient to perform inheritance reasoning.
Drawback of semantic network notation: links between bubbles represent only binary relations.
For example, the sentence Fly(Shankar , NewYork, NewDelhi ,Yesterday) cannot be asserted directly in a semantic network.
Nonetheless, we can obtain the effect of n-ary assertions by reifying the proposition itself as an event belonging to an
appropriate event category. Figure shows the semantic network structure for this particular event. Notice that the restriction
to binary relations forces the creation of a rich ontology of reified concepts.

Description Logics
● Description logics are notations that are designed to make it easier to describe definitions and
properties of categories.
● Description logic systems evolved from semantic networks to formalize what the networks
mean while retaining the emphasis on taxonomic structure as an organizing principle.
● The principal inference tasks for description logics are subsumption (checking if one category is
a subset of another by comparing their definitions) and classification (checking whether an
object belongs to a category).
● Some systems also include consistency of a category definition—whether the membership
criteria are logically satisfiable.
● The CLASSIC language (Borgida et al., 1989) is a typical description logic

Reasoning with Default Information
● Default reasoning involves making inferences based on commonly true assumptions when precise information isn't
available. For example, if you hear about a bird, you might default to thinking it can fly, even though some birds (like
penguins) can’t. This is because most birds do fly, so it's a reasonable default assumption unless specified otherwise.
● Traditional logic systems are monotonic, meaning that adding new information doesn't retract any previous conclusions.
However, default reasoning is nonmonotonic because new information can invalidate previous assumptions. For instance,
if you later learn that the bird is a penguin, you retract the assumption that it can fly.
● In AI, default information is represented using rules with exceptions.
For instance: If X is a bird, assume X can fly (unless specified otherwise)\text{If X is a bird, assume X can fly (unless
specified otherwise)}If X is a bird, assume X can fly (unless specified otherwise)
This rule captures the default (flying), but allows for exceptions (non-flying birds like penguins or ostriches).

Closed-World Assumption (CWA): Anything not known to be true is assumed to be false. This is
common in databases where if there’s no information about something, we assume it doesn't exist.
Open-World Assumption (OWA): Lack of information doesn’t imply falsity. In a large, open
environment, it’s unsafe to assume something is false just because it hasn’t been explicitly stated.
Various methods, such as default logic and circumscription, are used to encode default reasoning in
AI systems.
Default logic allows for defaults with exceptions, while circumscription limits the range of
assumptions the system can make, thereby constraining what it considers to be true by default.

Challenges in Knowledge Representation
Expressiveness vs. Efficiency: More expressive representations (like FOL) can describe complex ideas but are harder to
process. Simplified representations (like propositional logic) are easier to compute but can’t express as much detail.
Ambiguity and Vagueness: Human knowledge is often not clear-cut. AI systems must handle this ambiguity, which is
challenging because logic prefers exactness.
Handling Incomplete or Uncertain Information: Real-world data is rarely perfect, so AI systems have to make decisions even
when information is missing or only partially accurate. This is why reasoning with defaults and probabilistic approaches are
useful.

AI Unit 3

Uploaded by

Copyright:

Available Formats

AI Unit 3

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

AI Unit 3

Uploaded by

Copyright:

Available Formats

Artiﬁcial Intelligence

KCS 071 Unit 3 Ankita Singh

KCS 071 Unit 3 Ankita Singh

Example: Arithmetic logic

KCS 071 Unit 3 Ankita Singh

A knowledge base is a set of sentences. Each sentence is expressed in a language called a

KCS 071 Unit 3 Ankita Singh

First, it TELLs the knowledge base what it perceives.

knowledge-based agent can be built simply by TELLing it what it needs to know.

KCS 071 Unit 3 Ankita Singh

TELL: Jane is John's sister

TELL: John's Father is the same as John's sister's father

ASK: Who's Jane's Father?

KCS 071 Unit 3 Ankita Singh

1. Declarative approach: We can create a knowledge-based agent by initializing with an empty

KCS 071 Unit 3 Ankita Singh

KCS 071 Unit 3 Ankita Singh

•Semantics: deﬁnes the “meaning” to sentences

KCS 071 Unit 3 Ankita Singh

● The cave has a room with a beast which is called Wumpus,

● In one room there is a possibility of ﬁnding a heap of gold.

KCS 071 Unit 3 Ankita Singh

– gold +1000, death -1000

– -1 per step, -10 for using the arrow

– Squares adjacent to wumpus are smelly

– Squares adjacent to pit are breezy

– Glitter if gold is in the same square

– Shooting kills wumpus if you are facing it

– Shooting uses up the only arrow

– Grabbing picks up gold if in same square

– Releasing drops the gold in same square

Sensors: Stench, Breeze, Glitter, Bump, Scream

Actuators: Left turn, Right turn, Forward, Grab, Release, Shoot

KCS 071 Unit 3 Ankita Singh

○ Sequential: The order is important, so it is sequential.

○ Static: It is static as Wumpus and Pits are not moving.

○ Discrete: The environment is discrete.

KCS 071 Unit 3 Ankita Singh

KCS 071 Unit 3 Ankita Singh

KCS 071 Unit 3 Ankita Singh

KCS 071 Unit 3 Ankita Singh

KCS 071 Unit 3 Ankita Singh

KCS 071 Unit 3 Ankita Singh

• Syntax deﬁnes the sentences in the language

• Semantics deﬁne the "meaning" of sentences;

– i.e., deﬁne truth of a sentence in a world

• E.g., the language of arithmetic

– x+2 ≥ y is a sentence; x2+y > {} is not a sentence

– x+2 ≥ y is true if the number x+2 is no less than the number y

– x+2 ≥ y is true in a world where x = 7, y = 1

– x+2 ≥ y is false in a world where x = 0, y = 6

KCS 071 Unit 3 Ankita Singh

– E.g., x+y = 4 entails 4 = x+y

– Entailment is a relationship between sentences (i.e., syntax) that is based on semantics

KCS 071 Unit 3 Ankita Singh

• We say m is a model of a sentence α if α is true in m

• M(α) is the set of all models of α

Then KB ╞ α iﬀ M(KB) ⊆ M(α)

– E.g. KB = Giants won and Red won

KCS 071 Unit 3 Ankita Singh