1

Unit 2 : Logic for AI

2
 Table of Contents
1. Propositional logic
2. Predicate logic
3. Resolution
1. Resolution in proportional logic
2. Resolution in predicate logic
4. Clause form
5. Unification algorithm

3
 Introduction to Logic
What is Logic?
The study of principles and methods used to distinguish correct reasoning
from incorrect reasoning.

Father of Logic
Aristotle (384–322 BCE): Often considered the "father
of logic," Aristotle developed the first formal system of
logic, known as syllogistic logic. His work, particularly
in "Organon," laid the groundwork for future logical
studies.
 Propositional Logic
• Propositional logic is also known as propositional calculus or
sentential logic.
• It is a branch of logic that deals with propositions and their
relationships through logical connectives.
• It forms the foundation for many areas of formal logic, computer
science, and mathematics.

5
 Propositions
• A proposition is a declarative statement that is either True or False but
not both.
• Examples include:
• "It is raining" (True or False)
• "2 + 2 = 4" (True).

6
 Logical Connectives

Connectives: Symbols representing logical operations.

Types of Connectives:
• Negation (¬) : The negation of a proposition P is denoted as ¬P and is True if
P is False, and False if P is True.
• Conjunction (∧) : The conjunction of propositions P and Q is denoted as P∧Q
and is True if both P and Q are True.
• Disjunction (∨) : The disjunction of propositions P and Q is denoted as P∨Q
and is True any one of P or Q is True.
• Implication (→) : The implication P→Q is true if whenever P is True, Q is also
True. It is False only if P is True and Q is False.
• Bi-implication ( ) : The biconditional P Q is true if P and Q are either both
True or both False.

7
 Truth Tables
Purpose: Systematically determine the truth value of compound
propositions.

Construction: Assign truth values to variables and apply logical

connectives.

Example: Truth table for (𝑝∧𝑞)∨¬𝑝

8
 Truth Table Examples

For a detailed tutorial on Truth Tables, please refer to:

[Link]

9
 Laws of Propositional Logic
• Commutative Laws: 𝑝∧𝑞 ≡ 𝑞∧𝑝
• Associative Laws: (𝑝∧𝑞)∧𝑟 ≡ 𝑝∧(𝑞∧𝑟)
• Distributive Laws: 𝑝∧(𝑞∨𝑟) ≡ (𝑝∧𝑞)∨(𝑝∧𝑟)
• De Morgan's Laws: ¬(𝑝∧𝑞) ≡ ¬𝑝∨¬𝑞
• Idempotent Laws: 𝑝∧𝑝 ≡ 𝑝

Example: Applying De Morgan's Law: ¬(𝑝∨𝑞) ≡ ¬𝑝∧¬𝑞

10
 Examples

• Simplify the expression ¬(p∨q)∧(p→q)

11
 Solution
Simplifying the expression ¬(p∨q)∧(p→q)

1. Apply De Morgan's Law to ¬(p∨q) :

¬(p∨q)≡¬p∧¬q
2. Apply the definition of implication to p→q:
p→q≡¬p∨q
3. Substitute these into the original expression:
(¬p∧¬q)∧(¬p∨q)
4. Distribute ¬p across (¬p∧¬q) and (¬p∨q) :
(¬p∧¬q)∧(¬p∨q)≡(¬p∧¬q∧¬p)∨(¬p∧¬q∧q)
5. Simplify the expression:
(¬p∧¬q∧¬p)∨(¬p∧¬q∧q)≡¬p∧¬q
So, the simplified expression is:
¬p∧¬q

12
 What is Predicate Logic?
Predicate Logic: Deals with predicates and quantified variables.

Predicates: Statements containing variables that can be either true

or false.

Quantifiers: Symbols indicating the extent of the variable's

applicability (e.g., ∀ for universal quantification, ∃ for existential
quantification).

Example: ∀𝑥(𝑃(𝑥)) represents "for all x, P(x)".

13
 Predicates and Quantifiers
Predicates: Expressions containing variables that can be true or
false.

Quantifiers: Determine the scope of variables.

Examples:

Predicate: 𝑃(𝑥) - "x is a prime number."

Quantified Statement: ∀𝑥(𝑃(𝑥)) - "All x are prime numbers."

14
 Quantifier Negation
Negating Quantified Statements:
Universal Quantification: ¬(∀𝑥(𝑃(𝑥)))≡∃𝑥(¬𝑃(𝑥))
Existential Quantification: ¬(∃𝑥(𝑃(𝑥)))≡∀𝑥(¬𝑃(𝑥))

Example:

Negating "All cats are mammals"

becomes
"Some cats are not mammals".

15
 Rules of Inference
• Modus Ponens: If 𝑝 implies 𝑞 and 𝑝 is true, then 𝑞 is true.
• Modus Tollens: If 𝑝 implies 𝑞 and 𝑞 is false, then 𝑝 is false.
• Hypothetical Syllogism: If 𝑝 implies 𝑞, and 𝑞 implies 𝑟, then 𝑝
implies 𝑟.
• Disjunctive Syllogism: If 𝑝 or 𝑞 is true, and ¬𝑝 is true, then 𝑞 is
true.
• Constructive Dilemma: If 𝑝 implies 𝑞, and 𝑟 implies 𝑠, and 𝑝∨𝑟 is
true, then 𝑞∨𝑠 is true.

Example: Using Modus Ponens: If "It is raining" implies "The ground

is wet", and "It is raining", then "The ground is wet".

16
 Predicate Logic Inference Rules
• Universal Instantiation: If ∀𝑥(𝑃(𝑥)) is true, then 𝑃(𝑎) is true for
any individual 𝑎.
• Existential Instantiation: If ∃𝑥(𝑃(𝑥)) is true, then 𝑃(𝑎) is true for
some particular 𝑎.
• Universal Generalization: If 𝑃(𝑎) is true for any individual 𝑎, then
∀𝑥(𝑃(𝑥)) is true.
• Existential Generalization: If 𝑃(𝑎) is true for some particular 𝑎,
then ∃𝑥(𝑃(𝑥)) is true.
Example: Using Universal Instantiation: If "All cats are mammals",
then "Fluffy is a mammal".

17
 Predicate Logic Equivalences
• Universal Quantifier Equivalence:
¬∀𝑥(𝑃(𝑥))≡∃𝑥(¬𝑃(𝑥))

• Existential Quantifier Equivalence:

¬∃𝑥(𝑃(𝑥))≡∀𝑥(¬𝑃(𝑥))

• Negation Equivalence:
¬(∀𝑥(𝑃(𝑥)))≡∃𝑥(¬𝑃(𝑥)) and ¬(∃𝑥(𝑃(𝑥)))≡∀𝑥(¬𝑃(𝑥))

18
 Applications of Logic

Mathematics: Proving theorems, solving equations.

Computer Science: Designing algorithms, programming languages.

Philosophy: Analyzing arguments, studying language.

Linguistics: Understanding sentence structure, semantics.

Example: Using logic to verify software correctness.

19
 What is Resolution?

• Resolution Method is an inference rule which is used in both

proposition as well as First order predicate logic (FOPL) in different
ways.

• This method is basically used for proving the satisfiability of a

sentence.

• In resolution method, we use “Proof by Refutation” technique to

prove the given statement.

20
 What is Resolution?

• The Key idea for the resolution method is to use the knowledge
base and negated goal to obtain null clause (which indicates
contradiction).

• Resolution method is also called Proof by Refutation. Since the

knowledge base itself is consistent, the contradiction must be
introduced by a negated goal.

• As a result , we have to conclude that the original goal is true.

21
 Resolution Method in AI

• There are two methods for resolution in AI:

• Resolution Method in Proposition logic
• Resolution Method in Predicate logic

22
 Resolution Method in Propositional Logic

• In propositional logic, the resolution method is only the

reference rule which gives a new clause when two or more
clauses are coupled together.

• Using propositional logic, it becomes easy to make a theorem

prover sound and complete for all.

23
 Resolution Method in Propositional Logic

• The process followed to convert the propositional logic into

resolution method contains the below steps:
1. Convert the given axiom into clause form, i.e., Disjunction
form.
2. Apply and proof the given goal using negotiation rule.
3. Using those literals which are needed to prove.
4. Solve the clause together and achieve the goal.

24
25
26
27
28
29
30
31
32
Example:

33
34
35
36
37
38
39
40
41
42
43
44
45
46
47