Logic In Artificial Intelligence

Part 3
Anuj Mahajan
Assistant Professor
School of CSE
Shri Mata Vaishno Devi University
Propositional Logic & First Order Logic
• Propositional Logic: Propositional logic is a branch of mathematical
logic which studies the logical relationships between propositions (or
statements, sentences, assertions) taken as a whole, and connected via
logical connectives(¬(Negation), ∧ (Conjunction), ∨(Disjunction),
→ (Implica on), ⇔ (Bi-conditional))
• First order Predicate Calculus: First-order logic is also known as first-order
predicate calculus or first-order functional calculus. A sentence in first-
order logic is written in the form Px or P (x), where P is the predicate and x
is the subject, represented as a variable.
First order predicate calculus becomes First Order Predicate Logic if
inference rules are added to it. Using inference rules one can derive new
formula using the existing ones.
Logical Equivalence in Propositional Logic
Courtesy: Artificial Intelligence A modern Approach, Stuart Russel & Peter Norvig, 3rd Ed.
Limitations of Propositional 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 (as they need
quantification).
• P="Some humans like Ice cream“, Q=“All Students are Pass“,
R=“None of the students have failed”
• “Peter is a man”, “Paul is a man”, “John is a man” can be similarly symbolized by P,
Q and R respectively in propositional logic.
But can we draw any conclusions about similarities between P, Q and R ?
Better to represent these facts as – MAN(Peter), MAN(Paul) and MAN(John).
• In Predicate Logic, these limitations are removed to great extent.
Predicate Logic is a logical extension of propositional logic.
First Order Predicate Logic is one where the quantification is defined using simple
variables.
Confusion in Propositional Logic
• The truth table for ⇒ may not quite fit one’s intuitive understanding of “P implies Q”
or “if P then Q.”
• E.g. (1)The sentence “5 is odd implies Tokyo is the capital of Japan”.
P: “5 is odd “
Q : “Tokyo is the capital of Japan”
As both P & Q are True, hence p Q is a true sentence of propositional logic.
Even though it is an odd sentence of English.
• E.g. (2) The sentence “5 is even implies Sam is smart”.
P: “5 is even “
Q : “Sam is smart”
As P is False & Q is True, hence p Q is a true (refer Truth Table) sentence of
propositional logic (regardless of whether Sam is smart or not).
FOPC (First Order Predicate Calculus) &
FOL (First Order (Predicate) Logic)
• First-Order Logic (FOL) is a way of Knowledge Representation in Artificial
Intelligence (an extension to propositional logic). First Order Predicate Calculus
(FOPC) becomes First Order Predicate Logic if inference rules are added to it.
Using inference rules one can derive new formula using the existing ones.
• FOL is sufficiently expressive to represent the natural language statements in a
concise 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.
• It has three more logical notions as compared to propositional calculus.
• Terms
• Predicates
• Quantifiers (universal (“for all' ), existential (“there exists”))
 Subjects & Predicate
• First-order logic statements can be divided into two parts:
The subject is what (or whom) the sentence is about.
The predicate tells something about the subject.
Predicate describes a property of object or a relation among subjects represented by the variables.
• In the statement "x is an integer", x is the subject of the statement.
In the statement “x is greater than y”, x and y are subjects of the statement
• Predicate: A predicate can be defined as a relation, which binds terms together in a statement. Predicate
is a relation that maps n terms to a truth value true (T) or false (F). Example:
(1) A statement “x is greater than y” is represented in predicate calculus as GREATER(x, y). It is defined as
follows:
GREATER( x, y) = T , if x > y
= F , otherwise
The predicate name GREATER takes two terms and map to True(T) or False(F) depending upon the values
of their terms
(2) A statement "x is an integer", can be represented in Predicate form as:
INTEGER(x) = T, if x is an integer,
= F, otherwise
The predicate name INTEGER takes on term and map to True(T) or False(F) depending upon the value of
the term.
 Term, Predicate, Quantifiers
• Term is either a:
• constant (single individual or concept i.e. 5, John etc.)
• variable that stands for different individuals
• function: a mapping that maps n terms to a term i.e., if f is n-place function (n-ary function)
symbol and t1, …, tn are terms, then f(t1, …, tn) is a term.
• Predicate: A relation that maps n terms to a truth value true (T) or false (F).
• LOVE (john , Mary)
• LOVE(father(john), john)
• LOVE is a predicate. father is a function which returns the name of father, say father(john)
returns Joseph
• Quantifiers: 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 quantifiers: “there exist”
(∃) and “for all” (∀).
Atomic & Complex Sentences
• Atomic sentences are the most basic sentences of first-order logic. Atomic
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).
Kitty is a cat: cat (kitty).
• Complex Sentences are made by combining atomic sentences using
logical connectives e.g.
∀ (x) [ student(x) → ( like(x, Mathematics) ∧ like(x, Science) ) ]
(Here three simple sentences (predicates) are combined using implication
(→) and Conjunction (∧), we will discuss what it means in later slides)
BNF(Backus-Naur Form) grammar of sentences in propositional
logic, along with operator precedence, from highest to lowest
Courtesy: Artificial Intelligence A modern Approach, Stuart Russel & Peter Norvig, 3rd Ed.
Free & Bound Variables
• Free Variable: A variable is said to be a free variable in a formula if it
occurs outside the scope of the quantifier.
• Bound Variable: A variable is said to be a bound variable in a formula
if it occurs within the scope of the quantifier.
Example: ∀x ∃(y)[P (x, y, z)] Here, z is a free , x & y are bound
Universal Quantifier
• 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.
• If x is a variable, then ∀x is read as: “For all x”, or “For each x”, or “For
every x.
• In universal quan fier we use implica on "→".
If A → B, then A is called Premise or Antecedent, and B is called
conclusion or consequent.
• Example:
“every man is mortal” can be represented as:
(∀x) (MAN(x) → MORTAL(x))
 Example (Universal Quantifier):
All men drink coffee.
• The Universe of Discourse(UOD), also called Universe, is the set of
objects of interest.
• UOD: {x1,x2…,xn}
Man(x) is a predicate which returns True if x is a man, False otherwise.
Drink(x, coffee) is predicate which returns True if x drinks coffee, False
otherwise,
• In First Order Predicate Calculus (FOPC), “All men drink coffee” can be
written as:
∀x man(x) → drink (x, coffee).
It will be read as: For all x, if “x is a man” then “x drinks coffee”
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.
• If x is a variable, then ∃x or ∃(x) is read as: “There exists a x”, or “For some
x”, or “For at least one x”.
• In Existential quantifier we always use AND or Conjunction symbol (∧).
• Example:
“There exists a student who has passed AI exam” can be represented as:
∃x: student(x) ∧ pass(x, AI)
Example(Existential Quantifier):
Some Boys are Intelligent
• UOD: {x1, x2, x3….xn}
boy(x) is predicate which returns True if x is a boy, False otherwise
intelligent(x) is a predicate which return True if x is intelligent, F
otherwise
• In FOPC it can be written as
∃x: boy(x) ∧ intelligent(x)
• It will be read as: There exists some x, where “x is a boy” and “x is
intelligent”.
Properties of Quantifiers
• In universal quantifier: ∀x∀y is similar to ∀y∀x.
• In Existential quantifier: ∃x∃y is similar to ∃y∃x.
• But ∃x∀y is not similar to ∀y∃x.
Summary
Constant 1, 2, A, John etc.

Variables x, y, z etc.

Predicates Brother(x,y), Love(x,y) etc. result in

either True or False
Function Sqrt(x) returns Square Root, Father(x)
return father of x

Connectives ∧(conjunction), ∨(disjunction),

¬(negation), ⇒ (implication), ⇔ (bi-
conditional)
Equality ==

Quantifier ∀, ∃
 Examples of FOPC
• All birds fly:
bird (x), fly(x) are predicates.
So it will be represented as follows: ∀x bird(x) →fly(x).
• Every man respects his parent.
man(x) and respect(x, y) are predicates. y= parent.
Since there is every man so will use ∀, and it will be represented as follows:
∀x man(x) → respects (x, parent).
• Some boys play cricket.
Boy(x), play(x, y) are predicates, and y= game.
Since there are some boys so we will use ∃, and it will be represented as:
∃x boy(x) ∧ play(x, cricket).
Example of FOPC
• "Every man is mortal. John is a man. Therefore, John is mortal" as
FOPC statement:
Let MAN(x), represent that x is a man
MORTAL(x), represent x is mortal
Every man is mortal : (∀x) (MAN(x) → MORTAL(x))
John is a man : MAN(john)
John is mortal : MORTAL(john)

The whole text can be represented in FOPC as:

(∀x) ( (MAN(x) → MORTAL(x)) Λ MAN(john)) → MORTAL(john)

Read as: ∀x [ [(MAN(x) → MORTAL(x)) Λ MAN(john)] → MORTAL(john) ]

Examples of FOPC
• Not all students like both Mathematics and Science.
student(x), like(x, y) are predicates, 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, Mathema cs) ∧ like(x, Science) ) ].
• Only one student failed in Mathematics.
Student(x), failed(x, y) are predicates, and y= subject.
Since there is only one student who failed in Mathematics, so we will
use following representation for this:
∃(x) [ student(x) ∧ failed (x, Mathematics) ] ∧ ∀ (y) [¬(x==y) ∧ student(y) → ¬failed (y, Mathematics)]
 Terminologies for Inference Rules
• 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 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: Represented as P → Q
• Converse: The converse of implication, which means the right-hand side proposition
goes to the left-hand. For P → Q its converse is written as Q → P.
• Contrapositive: The negation of converse is termed as contrapositive, represented
as ¬ Q → ¬ P.
• Inverse: The negation of implication is called inverse. Represented as ¬ P → ¬ Q.
Truth Table for Implication, Converse,
Contrapositive, Inverse
Modus Ponens (Inference Rule)
• The best-known rule is called Modus Ponens (Latin for mode that affirms)
and is written as:

• The notation means that, whenever any sentences of the form α ⇒ β and α
are given, then the sentence β can be inferred.
• We cannot run Modus Ponens in opposite direction.
i.e. given sentence β, we cannot infer α ⇒ β
• 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.
Modus Ponens: Proof by Truth Table
Modus Tollens (Inference Rule)
• The Modus Tollens rule states that:
if P→ Q is true and ¬ Q is true, then ¬ P will also true.
It can be represented as:

• Example:
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
Modus Tollens: Proof by Truth Table
Hypothetical Syllogism (Inference Rule)
• Syllogism is a kind of logical argument that applies deductive reasoning to arrive at a
conclusion based on two or more propositions that are asserted or assumed to be true.
• 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: p  R
Example:
• Statement-1: If you have my home key then you can unlock my home.
P: you have my home key
Q: you can unlock my home
P→Q
Statement-1 can be represented in FOPC as:

• Statement-2: If you can unlock my home then you can take my money.
Q: you can unlock my home
R: you can take my money
Statement-2 can be written as Q→R
P→R
• Conclusion: By using Hypothetical Syllogism we get:
If you have my home key then you can take my money
Hypothetical Syllogism: Proof by Truth Table
Disjunctive Syllogism (Inference Rule)
• 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:

Example:
Statement-1: Today is Sunday or Today is Monday:
P: Today is Sunday
Q: Today is Monday
Statement1 can be written as: P ∨ Q
Statement-2: ¬P: Today is not Sunday
( (P ∨ Q), and ¬P) implies Q
Conclusion: Q: Today is Monday
Disjunctive Syllogism: Proof by Truth Table
Addition Rule (Inference Rule)
• It states that If P is true, then P ∨ Q will be true
Example:
• Statement-1: P: I have a vanilla ice-cream.
Statement-2: Q: I have Chocolate ice-cream.
Conclusion: By addition Rule P∨Q:I have vanilla or chocolate ice-cream
• Proof by Truth Table:
And Elimination
• And-Elimination says that, from a conjunction, any of the conjuncts
can be inferred:

• By considering the possible truth values of α and β, one can show

easily that inference rules of Modus Ponens and And-Elimination are
correct.
Inference Rule from Bi-Conditional Elimination
References
• Artificial Intelligence – A Modern Approach, Stuart Russel & Peter Norvig
• http://cse.iitd.ac.in/~saroj/LFP/LFP_2013/L4.pdf
• https://ocw.mit.edu/courses/electrical-engineering-and-computer-
science/6-825-techniques-in-artificial-intelligence-sma-5504-fall-
2002/lecture-notes/Lecture5FinalPart1Save.pdf
• https://www.javatpoint.com/propositional-logic-in-artificial-intelligence
(Note: This source has lots of errors, use carefully)
• Artificial Intelligence – Strategies & Techniques for Complex Problem
Solving, George Luger
• Artificial Intelligence – A new Synthesis, Nils J Nilsson