MODULE 2.
2
CS1542 : ARTIFICIAL INTELLIGENCE
MODULE 2
Module II: Knowledge Representation & Reasoning: Prepositional logic-Syntax, semantics,
normal forms; Predicate logic- Syntax, semantics, Clausal Normal Form; Procedural vs declarative
knowledge representation- Semantic Nets, Frames , Scripts.
FIRST ORDER LOGIC (FOL / FOPL)
First-order logic is another way of knowledge representation in artificial intelligence. It is an extension
to propositional logic.
FOL is sufficiently expressive to represent the natural language statements in a better way.
First-order logic is also known as Predicate logic or First-order predicate logic.
First-order logic is a powerful language that develops information about the objects in a more easy
way and can also express the relationship between those objects.
First-order logic consider the following
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, ......
SYNTAX AND SEMANTICS OF FIRST-ORDER LOGIC
The syntax of FOL determines which collection of symbols is a logical expression in first-order logic. The basic
syntactic elements of first-order logic are symbols.
Following are the basic elements of FOL syntax:
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.
Example: Consider the statement: "x is an integer.", it consists of two parts, the first part x is
the subject of the statement and second part "is an integer," is known as a predicate.
QUANTIFIERS IN FIRST-ORDER LOGIC
A quantifier is a language element which generates quantification, and quantification specifies the quantity of
specimen in the universe of discourse.
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:
a. Universal Quantifier, (for all, everyone, everything)
b. Existential quantifier, (for some, at least one).
a. Universal Quantifier:
Universal quantifier is a symbol of logical representation, which specifies that the statement within its range is
true for everything or every instance of a particular thing.
The Universal quantifier is represented by a symbol ∀, which resembles an inverted A.
Note: In universal quantifier we use implication "→".
If x is a variable, then ∀x is read as:
For all x
For each x
For every x.
Example: All man drink coffee.
∀x man(x) → drink (x, coffee).
It will be read as: There are all x where x is a man who drink coffee.
b) Existential Quantifier:
Existential quantifiers are the type of quantifiers, which express that the statement within its scope is true
for at least one instance of something.
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.
Note: In Existential quantifier we always use AND or Conjunction symbol (∧).
If x is a variable, then existential quantifier will be ∃x or ∃(x). And it will be read as:
o There exists a 'x.'
o For some 'x.'
o For at least one 'x.'
Example:
Some boys are intelligent.
∃x: boys(x) 𝖠 intelligent(x)
It will be read as: There are some x where x is a boy who is intelligent.
Properties of Quantifiers:
o In universal quantifier, ∀x∀y is similar to ∀y∀x.
o In Existential quantifier, ∃x∃y is similar to ∃y∃x.
o ∃x∀y is not similar to ∀y∃x.
Some Examples of FOL using quantifier:
1. All birds fly.
In this question the predicate is "fly(bird)."
And since there are all birds who fly so it will be represented as follows.
∀x bird(x) →fly(x).
2. Every man respects his parent.
In this question, the predicate is "respect(x, y)," where x=man, and y= parent.
Since there is every man so will use ∀, and it will be represented as follows:
∀x man(x) → respects (x, parent).
3. Some boys play cricket.
In this question, the predicate is "play(x, y)," where x= boys, and y= game. Since there are some boys so we will use ∃,
and it will be represented as:
∃x boys(x) → play(x, cricket).
4. Not all students like both Mathematics and Science.
In this question, the predicate is "like(x, y)," where x= student, and y= subject.
Since there are not all students, so we will use ∀ with negation, so following representation for
this:
¬∀ (x) [ student(x) → like(x, Mathematics) ∧ like(x, Science)].
5. For example from Natural Language to First order logic consider the following three
sentences:
– “Each animal is an organism”
– “All animals are organisms”
– “If it is an animal then it is an organism”
This can be formalised as:
∀x(Animal(x)→Organism(x))
6. “There are books that are heavy”
Written as: ∃x(Book(x)∧heavy(x))
Free and Bound Variables:
The quantifiers interact with variables which appear in a suitable way. There are two types of
variables in First-order logic which are given below:
Free Variable: A variable is said to be a free variable in a formula if it occurs outside the scope of
the quantifier.
Example: ∀x ∃(y)[P (x, y, z)], where z is a free variable.
Bound Variable: A variable is said to be a bound variable in a formula if it occurs within the scope
of the quantifier.
Example: ∀xy [A (x) B( y)], here x and y are the bound variables.
WELL-FORMED FORMULAS (WFFS) OF PROPOSITIONAL LOGIC
Well-formed formulas (WFFs) in first-order logic (FOL) are expressions constructed according to the
syntactic rules of FOL, representing meaningful statements about the world. These formulas serve as the building
blocks for encoding knowledge and reasoning in AI systems.
CLAUSE FORM
A literal is either an atomic formula or the negation of an atomic formula.
Examples: Odd(3). ¬Odd(Plus(x,3)).
A clause is the disjunction of literals. Variables in a clause are interpreted as universally quantified with the largest
possible scope.
Example: Odd(x) ∨ Odd(y) ∨ ¬Odd(Plus(x,y)) is interpreted as ∀x,y Odd(x) ∨ Odd(y) ∨ ¬Odd(Plus(x,y)).
CLAUSAL NORMAL FORM
Clause Normal Form (CNF) is a sub-language of 1st order logic. A clause is an expression of the form L1 |... | Lm
where each Li is a literal. Clauses are denoted by uppercase letters with a superscript |, e.g., C|.
There are satisfiability preserving transformations from 1st order logic to CNF, i.e., if a set of (1st order) formulae
are satisfiable, then their CNF is satisfiable. Conversely, if the CNF of a set of formulae is unsatisfiable, then the
formulae are unsatisfiable. This is then useful for showing logical consequence. The benefit of converting to CNF is
that more is possible using just the Herbrand interpretations. Computationally, CNF is easier to work with, and is
the form used by the resolution inference rule.
PROCEDURAL VS DECLARATIVE KNOWLEDGE