Module 2

Logic based Knowledge Representation

Contents
• Introduction
• Propositional Logic
• Predicate Logic
• First order Logic, Properties of well-formed
formulas (Wffs)
• Conversion to Clausal Form
• The Resolution Principle, Inference in First Order
Logic (FOL)

2
INTRODUCTION

3
Introduction
Humans know things; and what they know helps them do
things.

How the intelligence of humans is achieved?

by processes of reasoning that operate on internal
representations of knowledge.

4
Representation
• AI agents deal with knowledge (data)
• Facts (believe & observe knowledge)
• Procedures (how to knowledge)
• Meaning (relate & define knowledge)
• Right representation is crucial
• Early realisation in AI
• Wrong choice can lead to project failure
• Active research area
In lay man term…
• Knowledge - facts, information, and skills acquired through
experience or education; the theoretical or practical understanding of
a subject.
• Reasoning- the action of thinking about something in a logical,
sensible way
• The process of thinking about something in order to make
a decision
• Logic- A particular way of thinking, especially one that
is reasonable and based on good judgment
• Inference- A guess that you make or an opinion that
you form based on the information that you have
• Deriving new sentences from old

6
Knowledge Representation &
Reasoning
• AI: The study and development of systems that demonstrate intelligent behavior
• KR&R is the part of AI that is concerned with thinking and how thinking contributes to
intelligent behavior
• KR suggests an approach to understanding intelligent behavior that is radically
different
• Instead of studying humans very carefully (biology, nervous systems, psychology,
sociology, etc.), it argues that what we need to study is what humans know.
• It is taken as a given that what allows humans to behave intelligently is that they
know a lot of things about a lot of things and are able to apply this knowledge as
appropriate to adapt to their environment and achieve their goals.
• KR&R focuses on the knowledge, not on the knower. We ask what any agent—human,
animal, electronic, mechanical—would need to know to behave intelligently, and what
sort of computational mechanisms might allow its knowledge to be manipulated.

8/5/2021
7
 Knowledge Based Agents
• In AI, this approach to intelligence is embodied in knowledge-based
agents - composed of a knowledge base and an inference mechanism.

It operates by
• storing sentences about the world in its knowledge base,
• using the inference mechanism to infer new sentences,
• using these sentences to decide what action to take.

8
Knowledge Based Agents..
• 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.
• There must be a way to add new sentences to the knowledge
base (TELL)and a way to query what is known(ASK).
• The standard names for these operations are TELL and ASK ,
respectively.

9
 Knowledge
• “Amith knows that sun will rise tomorrow
• Knowledge is a relation between a knower and a proposition
• knower : Amith
• proposition: the idea expressed by a simple declarative sentence, like “sun will rise tomorrow”

• For KR&R, what matters about propositions is that they are abstract entities that can be true
or false, right or wrong
• When we say, “Amith knows that p,” we can just as well say, “Amith knows that it is true that p.”

8/5/2021
10
 Reasoning
• What is reasoning? In general, it is the formal manipulation of the symbols
representing a collection of believed propositions to produce
representations of new ones.
• Symbols are more accessible than the propositions they represent: They must be
concrete enough that we can manipulate them (move them around, take them apart,
copy them, string them together) in such a way as to construct representations of new
propositions.
• We might start with the sentences “Amith loves Buzo” and “Buzo is hurt” and after a
certain amount of manipulation produce the sentence, “Someone Amith loves is hurt”
• We would call this form of reasoning logical inference because the final sentence
represents a logical conclusion of the propositions represented by the initial ones

• Reasoning is a form of calculation, not unlike arithmetic, but over symbols

standing for propositions rather than numbers

8/5/2021
11
 LOGIC
• A logic is a formal language, with
precisely defined syntax and
semantics, which supports sound
inference.
• Different logics exist, which allow you
to represent different kinds of things,
and which allow more or less efficient
inference.
• The logic may be different types like
propositional logic, predicate logic,
temporal logic, description logic etc.

8/5/2021
12
What is a Logic?
• A language with concrete rules
• No ambiguity in representation (may be other errors!)
• Allows unambiguous communication and processing
• Very unlike natural languages e.g. English
• Many ways to translate between languages
• A statement can be represented in different logics
• And perhaps differently in same logic
• Expressiveness of a logic
• How much can we say in this language?
• Not to be confused with logical reasoning
• Logics are languages, reasoning is a process (may use logic)
Logic Representation
• Logic is a great knowledge representation
language for many AI problems
• Propositional logic is the simple foundation and
fine for some AI problems
• First order logic (FOL) is much more expressive
as a KR language and more commonly used in AI
• There are many variations: horn logic, higher
order logic, three-valued logic, probabilistic
logics, etc.

8/5/2021
14
Syntax and Semantics
• Syntax
• Rules for constructing legal sentences in the logic
• Which symbols we can use (English: letters, punctuation)
• How we are allowed to combine symbols
• Semantics
• How we interpret (read) sentences in the logic
• Assigns a meaning to each sentence
• Example: “All lecturers are seven foot tall”
• A valid sentence (syntax)
• And we can understand the meaning (semantics)
• This sentence happens to be false (there is a counterexample)
Propositional Logic
• Syntax
• Propositions, e.g. “it is wet”
• Connectives: and, or, not, implies, iff (equivalent)

• Brackets, T (true) and F (false)

• Semantics (Classical AKA Boolean)
• Define how connectives affect truth
• “P and Q” is true if and only if P is true and Q is true
• Use truth tables to work out the truth of statements
Predicate Logic
• Propositional logic combines atoms
• An atom contains no propositional connectives
• Have no structure (today_is_wet, john_likes_apples)
• Predicates allow us to talk about objects
• Properties: is_wet(today)
• Relations: likes(john, apples)
• True or false
• In predicate logic each atom is a predicate
• e.g. first order logic, higher-order logic
First Order Logic
• More expressive logic than propositional
• Used in this course (Lecture 6 on representation in FOL)
• Constants are objects: john, apples
• Predicates are properties and relations:
• likes(john, apples)
• Functions transform objects:
• likes(john, fruit_of(apple_tree))
• Variables represent any object: likes(X, apples)
• Quantifiers qualify values of variables
• True for all objects (Universal): ∀X. likes(X, apples)
• Exists at least one object (Existential): ∃X. likes(X, apples)
Example: FOL Sentence
• “Every rose has a thorn”

• For all X
• if (X is a rose)
• then there exists Y
• (X has Y) and (Y is a thorn)
Propositional Logic

20
PROPOSITIONAL LOGIC

• A proposition is a declarative sentence (a

sentence that declares a fact) that is either true
or false, but not both.
• Are the following sentences propositions?
• Toronto is the capital of Canada. (Yes)
• Read this carefully. (No)
• 1+2=3 (Yes)
• x+1=2 (No)
• What time is it? (No)

21
Continued..
• Propositional logic (PL) is the simplest form of logic where all
the statements are made by propositions.
• A proposition is a declarative statement which is either true or
false.
• It is a technique of knowledge representation in logical and
mathematical form.
Examples:
• It is Sunday.
• The Sun rises from West (False proposition)
• 3+3= 7 (False proposition)
• 5 is a prime number

22
Continued..

• Propositional Logic – the area of logic that deals

with propositions
• Propositional Variables – variables that
represent propositions: p, q, r, s
• E.g. Proposition p – “Today is Friday.”
• Truth values – T, F

23
Syntax
• The syntax of propositional logic defines the allowable
sentences.
• The atomic sentences consist of a single proposition symbol.
• We use symbols that start with an uppercase letter and may
contain other letters or subscripts
• There are two proposition symbols with fixed meanings: True is
the always-true proposition and False is the always-false
proposition.
• Complex sentences are constructed from simpler sentences,
using parentheses and logical connectives.

24
Example:
• 2+2 is 4, it is an atomic proposition as it is a true fact.
• "The Sun is cold" is also a proposition as it is a false fact.
• Compound proposition - Compound propositions are
constructed by combining simpler or atomic propositions,
using parenthesis and logical connectives.
Example:
• "It is raining today, and street is wet."
• "Ankit is a doctor, and his clinic is in Mumbai."

25
Semantics
The semantics defines the rules for determining the truth of a
sentence with respect to a particular model.
In propositional logic, a model simply fixes the truth value—true
or false—for every proposition symbol.
• For example, if the sentences in the knowledge base make use
of the proposition symbols P1,2, P2,2, and P3,1, then one
possible model is
m1 = {P1,2 =false, P2,2 =false, P3,1 =true} .
• With three proposition symbols, there are 23 =8 possible
models

26
1.1 Propositional Logic
DEFINITION 1
Let p be a proposition. The negation of p, denoted by ¬p, is the statement
“It is not the case that p.”
The proposition ¬p is read “not p.” The truth value of the negation of p, ¬p
is the opposite of the truth value of p.

• Examples
• Find the negation of the proposition “Today is Friday.” and express this in simple
English.
Solution: The negation is “It is not the case that today is Friday.”
In simple English, “Today is not Friday.” or “It is not Friday today.”
• Find the negation of the proposition “At least 10 inches of rain fell today in Miami.”
and express this in simple English.
Solution: The negation is “It is not the case that at least 10 inches of rain
fell today in Miami.”
In simple English, “Less than 10 inches of rain fell today in Miami.”

27
1.1 Propositional Logic
• Note: Always assume fixed times, fixed places, and particular people
unless otherwise noted.
• Truth table: The Truth Table for the
Negation of a Proposition.
p ¬p
T F
F T

• Logical operators are used to form new propositions from two or more
existing propositions. The logical operators are also called connectives.

28
Logical connectives.
Symbol Meaning priority
￢ negation, no 1
∧ conjunction, and 2
∨ disjunction, or 3
⇒ implication 4
⇔ equivalence 5
￢(not) -- ￢P is called the negation. Either an atomic
sentence (a positive literal) or a negated atomic sentence (a
negative literal).
∧ (and) -- P ∧ Q, is called a conjunction; its parts are the
conjuncts.
[P= Rohan is intelligent, Q= Rohan is hardworking - P∧ Q]
∨ (or) -- P∨Q, is a disjunction of the disjuncts P and Q
[P= Ritika is Doctor. Q= Ritika is Engineer - P ∨ Q]

29
30
Logical connectives.
⇒ (implies) -- P ⇒ ￢Q, is an implication (or
conditional). Its premise or antecedent is P, and its
conclusion or consequent is ￢Q. Implications are also known as
rules or if–then statements. The implication symbol is sometimes
written as ⊃ or →.
If it is raining, then the street is wet.
[P= It is raining Q= Street is wet - P → Q]

⇔ (equivalence) -- P ⇔ ￢Q is a biconditional. If and only if

statements. Some books write this as ≡
If I am breathing, then I am alive

31
Truth tables for the five logical connectives

32
Propositional Logic
DEFINITION 2
Let p and q be propositions. The conjunction of p and q, denoted by p
Λ q, is the proposition “p and q”. The conjunction p Λ q is true when
both p and q are true and is false otherwise.

• Examples
• Find the conjunction of the propositions p and q where p is the
proposition “Today is Friday.” and q is the proposition “It is raining
today.”, and the truth value of the conjunction.

Solution: The conjunction is the proposition “Today is Friday and it

is raining today.” The proposition is true on rainy Fridays.

33
Propositional Logic
DEFINITION 3
Let p and q be propositions. The disjunction of p and q, denoted by p ν
q, is the proposition “p or q”. The conjunction p ν q is false when both
p and q are false and is true otherwise.
• Note:
inclusive or : The disjunction is true when at least one of the two
propositions is true.
• E.g. “Students who have taken calculus or computer science can take this class.” –
those who take one or both classes.
exclusive or : The disjunction is true only when one of the
proposition is true.
• E.g. “Students who have taken calculus or computer science, but not both, can take
this class.” – only those who take one of them.
• Definition 3 uses inclusive or.

34
Propositional Logic
DEFINITION 4
Let p and q be propositions. The exclusive or of p and q, denoted by p q, is the proposition that is true when
exactly one of p and q is true and is false otherwise.

The Truth Table for The Truth Table for The Truth Table for the
the Conjunction of the Disjunction of Exclusive Or (XOR) of
Two Propositions. Two Propositions. Two Propositions.
p q pΛq p q pνq p q p q
T T T T T T T T F
T F F T F T T F T
F T F F T T F T T
F F F F F F F F F

35
Propositional Logic
Conditional Statements
DEFINITION 5
Let p and q be propositions. The conditional statement p → q, is the proposition “if p, then q.” The
conditional statement is false when p is true and q is false, and true otherwise. In the conditional
statement p → q, p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or
consequence).

● A conditional statement is also called an implication.

● Example: “If I am elected, then I will lower taxes.” p→q
implication:
elected, lower taxes. T T |T
not elected, lower taxes. F T |T
not elected, not lower taxes. F F |T
elected, not lower taxes. T F |F

36
Propositional Logic
• Example:
• Let p be the statement “Maria learns discrete mathematics.” and q
the statement “Maria will find a good job.” Express the statement p
→ q as a statement in English.
Solution: Any of the following -
“If Maria learns discrete mathematics, then she will find a
good job.
“Maria will find a good job when she learns discrete
mathematics.”
“For Maria to get a good job, it is sufficient for her to learn
discrete mathematics.”
“Maria will find a good job unless she does not learn
discrete mathematics.”

37
Propositional Logic
DEFINITION 6

Let p and q be propositions. The biconditional statement p ↔ q is the proposition “p if and

only if q.” The biconditional statement p ↔ q is true when p and q have the same truth
values, and is false otherwise. Biconditional statements are also called bi-implications.

• p ↔ q has the same truth value as (p → q) Λ (q → p)

• “if and only if” can be expressed by “iff”
• Example:
• Let p be the statement “You can take the flight” and let q be the
statement “You buy a ticket.” Then p ↔ q is the statement
“You can take the flight if and only if you buy a ticket.”
Implication:
If you buy a ticket you can take the flight.
If you don’t buy a ticket you cannot take the flight.

38
Propositional Logic

The Truth Table for the

Biconditional p ↔ q.
p q p↔ q
T T T
T F F
F T F
F F T

39
Propositional Logic
Truth Tables of Compound Propositions
• We can use connectives to build up complicated compound propositions involving any number of
propositional variables, then use truth tables to determine the truth value of these compound
propositions.
• Example: Construct the truth table of the compound proposition
(p ν ¬q) → (p Λ q).

The Truth Table of (p ν ¬q) → (p Λ q).

p q ¬q p ν ¬q pΛq (p ν ¬q) → (p Λ q)
T T F T T T
T F T T F F
F T F F F T
F F T T F F

40
Propositional Logic
Precedence of Logical Operators
• We can use parentheses to specify the order in which logical operators in a
compound proposition are to be applied.
• To reduce the number of parentheses, the precedence order is defined for
logical operators.
Precedence of Logical Operators. E.g. ¬p Λ q = (¬p ) Λ q
Operator Precedence p Λ q ν r = (p Λ q ) ν r
¬ 1 p ν q Λ r = p ν (q Λ r)
Λ 2
ν 3
→ 4
↔ 5

41
Propositional Logic
Translating English Sentences
• English (and every other human language) is often ambiguous.
Translating sentences into compound statements removes the
ambiguity.
• Example: How can this English sentence be translated into a logical
expression?
“You cannot ride the roller coaster if you are under 4 feet
tall unless you are older than 16 years old.”
Solution: Let q, r, and s represent “You can ride the roller coaster,”
“You are under 4 feet tall,” and “You are older than
16 years old.” The sentence can be translated into:
(r Λ ¬ s) → ¬q.

42
Propositional Logic
• Example: How can this English sentence be translated into a logical
expression?
“You can access the Internet from campus only if you are a
computer science major or you are not a freshman.”
Solution: Let a, c, and f represent “You can access the Internet from
campus,” “You are a computer science major,” and “You are
a freshman.” The sentence can be translated into:
a → (c ν ¬f).

43
Interpretation of logic formulas
• When we see a logic formula, we do not care about the original
meaning of each proposition. Rather, we care about the logic
relation between the propositions.
• The main concern is to know if a logic formula is “true” or
“false” when the values of the atomic formulas contained in this
formula are given.
• The process for determining the “true/false” of a logic formula
based on the “true/false” of the atomic formulas is called
“interpretation”.

44
Wff- well formed formula
• A well-formed formula, wff, is a finite sequence of symbols from
a given alphabet that is part of a formal language. A formal
language can be identified with the set of formulas in the
language. We represent propositions by formulas called
well-formed formulas (wffs).
• A sentence (wff- well formed formula) is defined as follows:
• A symbol is a sentence
• If S is a sentence, then ¬S is a sentence
• If S is a sentence, then (S) is a sentence
• If S and T are sentences, then (S ∨ T), (S ∧ T), (S → T), and (S
↔ T) are sentences
• A sentence results from a finite number of applications of the
rules

45
Properties of wffs in PL
Types of logic formula
Tautology: A tautology is a logic formula that is always true regardless
of the true/false of the atomic formulas. A tautology is always “valid”.
Contradiction : If a logic formula is always false regardless of the
true/false of the atomic formulas, we say it is a contradiction. A
contradiction is unsatisfiable.
Satisfiable: If there exists a set of values for the atomic formulas that
makes the logic formula true, this formula is satisfiable. This set of
values is called an interpretation of the formula.
Equivalence- The wff V is equivalent to the wff W (written V ≡ W) iff V
and W have the same truth value for each assignment of truth values to
the propositional variables occurring in V and W.
• Example. ¬ A ∧ (B ∨ A) ≡ ¬ A ∧ B and A ∨ ¬ A ≡ B ∨ ¬ B

46
Properties of wffs in PL
• Propositional logic is also called Boolean logic as it works
on 0 and 1.
• Propositions can be either true or false, but it cannot be
both.
• Statements which are questions, commands, or opinions
are not propositions such as "Where is Rohini", "How are
you", "What is your name", are not propositions.

47
 Properties of wffs in PL- Logical equivalence
• Logical equivalence is one of the features of propositional logic.
Two propositions are said to be logically equivalent if and only if
the columns in the truth table are identical to each other.
• Let's take two propositions A and B, so for logical equivalence,
we can write it as A⇔B. In below truth table we can see that
column for ¬A∨ B and A→B, are identical hence A is Equivalent
to B

48
 Properties of wffs in PL - 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: 49
50
Example

propositions

hypotheses
51
Inference rules
• Logical inference creates new sentences that logically follow
from a set of sentences (KB)
• An inference rule is sound if every sentence X it produces when
operating on a KB logically follows from the KB
• i.e., inference rule creates no contradictions
• An inference rule is complete if it can produce every expression
that logically follows from (is entailed by) the KB.
• Logical inference is used to create new sentences that logically
follow from a given set of sentences (KB).
• 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.

52
Rules of Inference
• 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.

53
• The most commonly used Rules of Inference are tabulated below
1. Modus Ponens:
• it states that if P and P → Q is true, then we can infer that Q will be true.
It can be represented as:

Example:
• Statement-1: "If I am sleepy then I go to bed" ==> P→ Q
• Statement-2: "I am sleepy" ==> P
• Conclusion: "I go to bed." ==> Q.
• Hence, we can say that, if P→ Q is true and P is true then Q will be true.
Proof by Truth table:
P Q P 🡪Q P Q
1 1 1 1 1
1 0 0 1 No need
0 1 1 0 No need
0 0 1 0 No need
54
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:
• Example:
• Statement-1: If you have my home key then you can unlock my
home. P→Q
Statement-2: If you can unlock my home then you can take my
money. Q→R
Conclusion: If you have my home key then you can take my money. P→R

55
4. Disjunctive Syllogism:
• The Disjunctive syllogism rule state that if P∨Q is true, and ¬P is true,
then Q will be true. It can be represented as:

• Statement-1: Today is Sunday or Monday. ==>P∨Q

• Statement-2: Today is not Sunday. ==> ¬P
• Conclusion: Today is Monday. ==> Q

56
57
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:

• Statement-1: "If I am sleepy then I go to bed" ==> P→ Q

• Statement-2: "I do not go to the bed."==> ~Q
• Statement-3: Which infers that "I am not sleepy" => ~P
• Proof by Truth table:

58
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.

Example:
• Statement: I have a vanilla ice-cream. ==> P
• Statement-2: I have Chocolate ice-cream.
• Conclusion: I have vanilla or chocolate ice-cream. ==> (P∨Q)

59
6. Simplification:
• The simplification rule state that if P∧ Q is true, then Q or P will also be
true. It can be represented as:

60
7. Resolution:
• The Resolution rule state that if P∨Q and ¬ P∧R is true, then Q∨R will
also be true. It can be represented as

61
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.

62
Propositional logic is a weak language
• Hard to identify “individuals.” E.g., Mary, 3
• Can’t directly talk about properties of individuals or relations between
individuals. E.g. “Bill is tall”
• Generalizations, patterns, regularities can’t easily be represented. E.g., all
triangles have 3 sides
• First-Order Logic (abbreviated FOL or FOPC) is expressive enough to
concisely represent this kind of situation.
FOL adds relations, variables, and quantifiers, e.g.,
•“Every elephant is gray”: ∀ x (elephant(x) → gray(x))
•“There is a white alligator”: ∃ x (alligator(X) ^ white(X))

8/5/2021 63
• First Order Predicate Logic

64
 First order Predicate Logic
• First-order logic is another way of knowledge representation in AI. It is
an extension to propositional logic.
• FOPL 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.

65
Models for first-order logic
• The models of a logical language are the formal structures that
constitute the possible worlds under consideration. Each model links
the vocabulary of the logical sentences to elements of the possible
world, so that the truth of any sentence can be determined.
• Models have objects in them! The domain of a model is DOMAIN the set
of objects or domain elements it contains. The domain is required to be
nonempty—every possible world must contain at least one object.
• In the following figure, Richard and John are brothers. Formally
speaking, a relation TUPLE is just the set of tuples of objects that are
related.
• Thus, the brotherhood relation in this model is the set
{ Richard the Lionheart, King John, King John, Richard the Lionheart }

66
• Certain kinds of relationships are best considered as functions, in that
a given object must be related to exactly one object in this way. For
example, each person has one left leg, so the model has a unary “left
leg” function that includes the following mappings:
Richard the Lionheart → Richard’s left leg
King John → John’s left leg .
• Strictly speaking, models in first-order logic require total functions,
that is, there must be a value for every input tuple.

67
68
Symbols and interpretations
FOPL does not only assume that the world contains facts like
propositional logic but also assumes the following things in the world
like :
• Objects: A, B, people, numbers, colors, wars, theories, squares, pits,
......
• 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

69
Syntax of First-order Logic: Basic Elements
• Constant 1, 2, A, John, Mumbai, cat,....
• Variables x, y, z, a, b,....
• Predicates Brother, Father, >,....
• Function sqrt, LeftLegOf, ....
• Connectives ∧, ∨, ¬, ⇒, ⇔
• Equality ==
• Quantifier ∀, ∃
• We will use various kinds of individual constants that denote
individuals/objects: a,b,c, names,…
• Individual variables over objects: x, y, z , …
• The result of applying a predicate P to a constant a is the
proposition P(a)
Meaning: the object denoted by a has the property denoted by P.
• if P = “is a prime number”, then P(x) is the propositional form
“x is a prime number”.

70
• In addition to its objects, relations, and functions, each model includes an
interpretation that specifies exactly which objects, relations and
functions are referred to by the constant, predicate, and function symbols
• Example; Richard refers to Richard the Lionheart and John refers to the
evil King John.
• Brother refers to the brotherhood relation, that is, the set of tuples of
objects.
• OnHead refers to the “on head” relation that holds between the crown
and King John; Person, King, and Crown refer to the sets of objects that
are persons, kings, and crowns.
• LeftLeg refers to the “left leg” function,

71
Terms Atomic sentences
• A term is a logical expression that refers TERM to an object. Constant
symbols are therefore terms, but it is not always convenient to have a
distinct symbol to name every object.
• For example, in English we might use the expression “King John’s left
leg” rather than giving a name to his leg. This is what function symbols
are for: instead of using a constant symbol, we use LeftLeg(John).
• Atomic sentences are the most basic sentences of first-order logic.
• These sentences are formed from a predicate symbol followed by a
parenthesis with a sequence of terms.
• We can represent atomic sentences as
Predicate (term1, term2, ......, term n).
• Example:
Ravi and Ajay are brothers: => Brothers(Ravi, Ajay).
Tom is a cat: => cat (Tom)

72
Complex Sentences:
• Complex sentences are made by combining atomic sentences
using connectives.
• 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.
• Consider the statement:
• "x is an integer.“
• In the sentence “The dog is sleeping”:
• The phrase “the dog” denotes the subject -
which the sentence is about.
• The phrase “is sleeping” denotes the predicate- a property that is
true of the subject.
• Predicate logic will follow the same pattern.

73
Complex Sentences:
• ￢Brother (LeftLeg(Richard), John)
• Brother (Richard , John) ∧ Brother (John,Richard)
• King(Richard ) ∨ King(John)
• ￢King(Richard) ⇒ King(John)

Fig: Models of complex sentences

74
Examples of Connectives in Use
• “Simon lectures AI and bioinformatics”
lectures(simon,ai) ∧ lectures(simon,bioinfo)
• “If Simon isn’t lecturing AI, Bob must be”
┓lectures(simon,ai) → lectures(bob,ai)
• “George and Tony will win or Saddam will lose”
(will_win(george) ∧ will_win(tony)) ∨
┓will_win(saddam)

75
 Example of a Function
• The cost of an omelette at the red_lion is $5”
• cost_of is a function
Input: the name of a meal and the name of a Hotel
Output: the cost of the meal
cost_of (omelette, red_lion) = $5
• “Omelettes at the Red Lion cost less than pancakes at House of Pancakes”
less_than (cost_of (omelette,red_lion), cost_of(pancake, pancake_house))
• If we are talking about the output of a function
• We can replace it with the predicate part
• i.e., replace the RHS of equality with the LHS

76
 Quantifiers
• Universal quantifiers are often used with “implies” to form
“rules”:
(∀x) student(x) → smart(x) means “All students are smart”
• Universal quantification is rarely used to make blanket
statements about every individual in the world:
(∀x)student(x)∧smart(x) means “Everyone in the world is a
student and is smart”
• Existential quantifiers are usually used with “and” to
specify a list of properties about an individual:
(∃x) student(x) ∧ smart(x) means “There is a student who is
smart”

8/5/2021
77
 Quantifiers in First-order logic:
• There are two types of quantifier:
Universal Quantifier(∀)- (for all, everyone, everything)
Specifies that the statement within its range is true for
everything or every instance of a particular thing.
In universal quantifier we use implication "→".
Existential quantifier(∃) - (for some, at least one)
Express that the statement within its scope is true for at
least one instance of something.
In Existential quantifier we always use AND or Conjunction
symbol (∧)

78
 Quantifier Scope
• Switching the order of universal quantifiers does
not change the meaning:
• (∀x)(∀y)P(x,y) ↔ (∀y)(∀x) P(x,y)
• Similarly, you can switch the order of existential
quantifiers:
• (∃x)(∃y)P(x,y) ↔ (∃y)(∃x) P(x,y)
• Switching the order of universals and existentials
does change meaning:
• Everyone likes someone: (∀x)(∃y) likes(x,y)
• Someone is liked by everyone: (∃y)(∀x) likes(x,y)

8/5/2021
79
“∀” is the. FOR ∀LL or universal quantifier.
“∃” is the ∃XISTS or existential quantifier
For example,
∀x P(x) and ∃x P(x) are propositions
• “the parking spaces at University”
Let P(x) mean “x is full.”

∃x P(x) is the proposition saying that

• “Some parking spaces at University are full.”
• “There is a parking space at University that is full.”
• “At least one parking space at University is full.”

80
• “the parking spaces at University”
Let P(x) mean “x is occupied”

∀ x P(x), is the proposition

• “All parking spaces at University are occupied.”
• “For each parking space at University, that space is full.”
• The universally quantified sentence is equivalent to asserting the
following five sentences:
• Richard the Lionheart is a king ⇒ Richard the Lionheart is a
person.
• King John is a king ⇒ King John is a person.
• Richard’s left leg is a king ⇒ Richard’s left leg is a person.
• John’s left leg is a king ⇒ John’s left leg is a person.
• The crown is a king ⇒ the crown is a person

81
• ∃ x Crown(x) ⇒ OnHead(x, John) .
• Applying the semantics, the sentence says that at least one of the
following assertions is true:
• Richard the Lionheart is a crown ⇒ Richard the Lionheart is on
John’s head;
• King John is a crown ⇒ King John is on John’s head;
• Richard’s left leg is a crown ⇒ Richard’s left leg is on John’s
head;
and so on.
• Now an implication is true if both premise and conclusion are
true, or if its premise is false. So if Richard the Lionheart is not a
crown, then the first assertion is true and the existential is
satisfied.

82
Combining Quantifiers

∀ x ∃ y Loves(x,y)
• For everyone (“x”) there is someone (“y”) that
they love.

∃ y ∀ x Loves(x,y)
• There is someone (“y”) who is loved by
everyone (“X”)

Clearer with parentheses: ∃ y ( ∀ x Loves(x,y) )

8/5/2021
83
 whether it is a negation,
conjunction, disjunction, Whether
Scope of The Free
implication, universal it is a
Quantizer Variables
formula, existential sentence
formula
1. ∃x(A(x, y) ∧ B(x))

2. ∃x(∃y(A(x, y) → B(x))

3. ¬∃x(∃y(A(x, y))) → B(x)

4. ∀x(¬∃y(A(x, y)))
5. ∃x(A(x, y)) ∧ B(x)

6. ∃x(A(x, x)) ∧ ∃y(B(y))

8/5/2021
84
 whether it is a
negation, a
conjunction, a Whether
Free
disjunction, an Scope of The Quantizer it is a
Variables
implication, a sentence
universal formula, or
an existential formula
1. ∃x(A(x, y) ∧ B(x)) Existential ∃x: (A(x, y) ∧ B(x)) y No
∃x: (∃y(A(x, y) → B(x))
2. ∃x(∃y(A(x, y) → B(x)) Existential ∃y: A(x,y) None Yes
3. ¬∃x(∃y(A(x, y))) → ∃x: (∃y(A(x, y))
B(x) Implication ∃y: A(x, y) x in B(x) No
∀x : (¬∃y(A(x, y)))
4. ∀x(¬∃y(A(x, y))) Universal ∃y: A(x, y) None Yes
5. ∃x(A(x, y)) ∧ B(x) Conjunction ∃x: A(x, y)) y, x in B(x) No
∃x: (A(x, x))
6. ∃x(A(x, x)) ∧ ∃y(B(y)) Conjunction ∃y: (B(y)) None Yes

8/5/2021
85
 Translating English to FOL
Every gardener likes the sun.
∀x gardener(x) → likes(x,Sun)
You can fool some of the people all of the time.
∃x ∀t person(x) ∧time(t) → can-fool(x,t)
You can fool all of the people some of the time.
∀x ∃t (person(x) → time(t) ∧can-fool(x,t))
∀x (person(x) → ∃t (time(t) ∧can-fool(x,t)))
All purple mushrooms are poisonous.
∀x (mushroom(x) ∧ purple(x)) → poisonous(x)
No purple mushroom is poisonous.
¬∃x purple(x) ∧ mushroom(x) ∧ poisonous(x)
∀x (mushroom(x) ∧ purple(x)) → ¬poisonous(x)
There are exactly two purple mushrooms.
∃x ∃y mushroom(x) ∧ purple(x) ∧ mushroom(y) ∧ purple(y) ^ ¬(x=y) ∧ ∀z (mushroom(z) ∧ purple(z))
→ ((x=z) ∨ (y=z))
Clinton is not tall.
¬tall(Clinton)
X is above Y iff X is on directly on top of Y or there is a pile of one or more other objects directly on top of one
another starting with X and ending with Y.
∀x ∀y above(x,y) ↔ (on(x,y) ∨ ∃z (on(x,z) ∧ above(z,y)))

8/5/2021
86
 Translate the following sentences into FOL
1. Everything is bitter or sweet
2. Either everything is bitter or everything is
sweet
3. There is somebody who is loved by everyone
4. Nobody is loved by no one
5. If someone is noisy, everybody is annoyed
6. Frogs are green.
7. Frogs are not green.
8. No frog is green.
9. Some frogs are not green.
10. A mechanic likes Bob.
11. A mechanic likes herself.
12. Every mechanic likes Bob.
13. Some mechanic likes every nurse.
14. There is a mechanic who is liked by every
nurse.

8/5/2021
87
 Nested quantifiers
• “Brothers are siblings” can be written as
∀ x ∀ y Brother (x, y) ⇒ Sibling(x, y) .
• “siblinghood is a symmetric relationship”, we can write
∀ x, y Sibling(x, y) ⇔ Sibling(y, x) .
• “Everybody loves somebody” means that for every person, there is
someone that person loves:
∀ x ∃ y Loves(x, y) .
• On the other hand, to say “There is someone who is loved by everyone,”
we write
∃ y ∀ x Loves(x, y) .
[ Note:-The order of quantification is very important. It becomes clearer if
we insert parentheses.
∀ x (∃ y Loves(x, y)) says that everyone has a particular property, namely,
the property that they love someone. On the other hand, ∃ y (∀ x Loves(x,
y)) says that someone in the world has a particular property, namely the
property of being loved by everybody ]

88
Connections between ∀ and ∃
• The two quantifiers are actually intimately connected with each other,
through negation.
• Asserting that everyone dislikes parsnips is the same as asserting there
does not exist someone who likes them, and vice versa:
∀ x ￢Likes(x, Parsnips ) is equivalent to ￢∃ x Likes(x, Parsnips) .
• “Everyone likes ice cream” means that there is no one who does not like
ice cream:
∀ x Likes(x, IceCream) is equivalent to ￢∃ x ￢Likes(x, IceCream) .
• Because ∀ is really a conjunction over the universe of objects and ∃ is a
disjunction, they obey De Morgan’s rules. The De Morgan rules for
quantified and unquantified sentences are as follows:
• ∀ x ￢P ≡ ￢∃x P ￢(P ∨ Q) ≡ ￢P ∧￢Q
• ￢∀x P ≡ ∃x ￢P ￢(P ∧ Q) ≡ ￢P ∨￢Q
• ∀x P ≡ ￢∃x ￢P P∧ Q ≡ ￢(￢P ∨￢Q)
• ∃x P ≡ ￢∀x ￢P P∨ Q ≡ ￢(￢P ∧￢Q) .

89
Equality
• We can use the equality symbol to signify that two terms refer to the
same object. For example,
Father (John)=Henry
says that the object referred to by Father (John) and the object
referred to by Henry are the same. Because an interpretation fixes the
referent of any term, determining the truth of an equality sentence is
simply a matter of seeing that the referents of the two terms are the same
object.
• It can also be used with negation to insist that two terms are not the
same object. To say that Richard has at least two brothers, we would
write
∃ x, y Brother (x,Richard ) ∧ Brother (y,Richard ) ∧￢(x=y) .
• The sentence
∃ x, y Brother (x,Richard ) ∧ Brother (y,Richard )
does not have the intended meaning

90
Variables
• “There’s a meal at the Red Lion which costs $3” (more
expressive now)
• cost_of(meal,red_lion) = 3
• We’re really talking about some general meal
• Not a meal in particular
• Call this meal X (a variable)
• cost_of (X, red_lion) = 3
need to express “There is such a meal X”. This is
represented as: ∃
The exists sign is known as a existential quantifier
• ∃ X (cost_of (X, red_lion) = 3)

91
Examples
• “There is a meal at the Red Lion which costs three pounds”
∃ X (meal(X) ∧ cost_of (red_lion, X) = 3)

• “All the meals at the Red Lion cost three pounds”

Replace exists by forall:
∀ X (meal(X) ∧ cost_of (red_lion, X) = 3)
∀ X (meal(X) → cost_of(red_lion, X) = 3)

• “Every Monday and Wednesday I go to John’s house for dinner”

∀ X (day(X,mon) ^ day(X,weds)
→ go(me, house(john)) ∧ eat(me,dinner))

92
“All things in the bag are red”
Which of these translations is correct?

1. ∃ X (in_bag(X) → red(X))

2. ∀ X (red(X) → in_bag(X))

3. ∀ X (∀ Y (bag(X) ∧ in_bag(Y,X) → red(Y)))

93
 USING FIRST-ORDER LOGIC
Assertions and queries in first-order logic
• Sentences are added to a knowledge base using TELL, exactly as in
propositional logic. Such sentences are called assertions. For example,
we can assert that John is a king, Richard is a person, and all kings are
persons:
• TELL(KB, King(John)) .
• TELL(KB, Person(Richard)) .
• TELL(KB, ∀ x King(x) ⇒ Person(x)) .

• We can ask questions of the knowledge base using ASK. For example
ASK(KB, King(John))
returns true. Questions asked with ASK are called queries or goals.
Generally speaking, any query that is logically entailed by the knowledge
base should be answered affirmatively.

94
Practical Applications of Predicate Logic
• Basis for proving correctness of computer programs
• Basis for many Artificial Intelligence systems.
• Predicate-logic like statements are supported by some sophisticated
database query engines

95
USING FIRST-ORDER LOGIC
For example, given the two preceding assertions, the query ASK(KB,
Person(John))
• should also return true. We can ask quantified queries, such as
ASK(KB, ∃ x Person(x))
• The answer is true, but this is perhaps not as helpful as we would like.
It is rather like answering “Can you tell me the time?” with “Yes.” If we
want to know what value of x makes the sentence true, we will need a
different function, ASKVARS, which we call with
ASKVARS(KB, Person(x))
• In this case there will be two answers: {x/John} and {x/Richard}. Such
an answer is called a substitution or binding list.

96