Logic_Predicate_Propositional_Updated.pdf

updated pdf

Predicate and Propositional logic

1. Logic in AI
By:
Vijeta Rani
Delhi Technological University
©Delhi Technological University

2. Definition of Logic
"One of the prime activity of human intelligence is reasoning. The activity
of reasoning involves construction, organization and manipulation of
statements to arive at new conclusions.
"Thus logic can be defined as a scientific study of the process of
reasoning and the system of rules and procedures that help in the
reasoning process.
"The logic process takes in some information (called premises) and
produces some outputs (called conclusions). There exist some basic
laws that help in theorem proving. These laws along with standard
formulae help in deriving new information from the existing ones.

3. Types of 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.
"The logic may be of different types:-
!’ Propositional logic
!’ Predicate logic
!’ Temporal logic
!’ Description logic
etc.

4. Propositional Logic
"This is the simplest form of logic.
"Here all the statements made are called as Propositions.
"A proposition in a propositional logic takes only two values: either TRUE
or FALSE.
"It means that a proposition can either be true or false.
"Example:
Statement 1: Rubber is a good conductor of electricity.
Statement 2: Diamond is a hard material
"Both statement 1 and 2 are propositions. Statement 1 is False whereas
statement 2 is True.

5. Types of Prepositions
"There are two types of propositions:-
1. Atomic 2. Molecular
"Atomic propositions are also called simple propositions.
"Molecular propositions are also called as compound propositions. They
are formed by combining one or more atomic propositions using a set of
logical connectives.
"Example:
Bhasker is a golfer !’ Atomic proposition
Bhasker is a golfer and Ravi is not a doctor !’ Molecular proposition
"Logical connectives like AND, OR, NOT

6. Commonly used Logical connectives
Name Connective Symbols
Conjunction AND E &
Inclusive Disjunction OR V |
Negation NOT
¬ ~
Material condition IMPLIES !’
Material biconditional IFF < >
Exclusive disjunction XOR + enclosed in a circle
Joint denial NAND !‘
Disjoint denial NOR !“

7. Syntax of Propositional Logic
"The letters (along with subscripted numerals) represent atomic
propositions.
E.g. A, B, C, D1, E1 etc.
"The atomic propositions with logical connectives are used to represent
molecular propositions.
E.g.
¬A
A Å B
A Ä B
A !’ B

8. Semantics of Logical Propositions
"A clear meaning of the logical propositions can be arrived at by
constructing appropriate truth tables for molecular propositions.
A B ¬A ¬BAÅBAÄBA !’ BA < > B
T T F F T T T T
F T T F T F T F
T F F T T F F F
F F T T F F T T

9. Implies Connective !’
"A !’ B means that if proposition A is TRUE then proposition B is also
TRUE.
"E.g.
Proposition A : The machine is defective.
Proposition B : The production is less
the implication is written as
IF the machine is defective THEN the production is less.
"Truth table for this is given in the previous slide and can be verified.

10. Logical Equivalences
"Two propositions are logically equivalent if they have the same truth
values for combinations of truth table for their atomic parts
e.g. : (A !’ B) is equivalent to (¬A Å B)
A B A !’ B ¬A ¬A Å B
T T T F T
T F F F F
F T T T T
F F T T T

12. Tautologies
"Propositions that are TRUE for all possible combinations of truth values
of their atomic parts are called as Tautologies.
E.g. ((A Ä (A !’ B) !’ B)
A B A !’ BA Ä (A !’ B)((A Ä (A !’ B) !’ B)
T T T T T
T F F F T
F T T F T
F F T F T

13. Contradictions
"Whenever the truth table value of a proposition is always false for all
combinations of its constituents, then the proposition is called as a
Contradiction.
E.g. : (A Ä ¬A) is a contradiction.
A ¬A (A Ä ¬A)
T F F
F T F

14. Contingencies
"A proposition is called a Contingent if its truth table has both TRUE and
FALSE as its ouput.
E.g. (A !’ B) is a contingent.
A BA !’ B
T T T
F T T
T F F
F F T

16. Normal Forms in Propositional Logic
"There are two major normal forms of statements in Propositional logic:-
1. Conjunctive Normal Form (CNF)
2. Disjunctive Normal Form (DNF)
"A formula can be converted into its normal form by substituting it by its
equivalent formulae. Two formulae A and B are equivalent if and only if,
the truth table values of A and B are same for all values of A and B.

17. CNF & DNF
"CNF: A formula is said to be in CNF if it has the form :-
A = A1 Ä A2 Ä A3 & Ä An , n >=1
where each A1, A2, A3, &, An is a disjunction of an atom or negation of an
atom.
"DNF: A formula is said to be in DNF if it has the form :-
A = A1 Å A2 Å A3 & Å An , n >=1
where each A1, A2, A3, &, An is a conjunction of an atom or negation of
an atom.

18. Procedure to convert to CNF/DNF
Step 1: Eliminate implications (!’ ) and biconditionals (< > ). For this, use
the equivalence laws;-
(A !’ B) = ¬A Å B
(A < > B) = (A !’ B ) Ä (B !’ A) = (¬A Å B) Ä (¬B Å A)
Step 2: Reduce the scope of NOT symbol by the formula (¬(¬A) = A and
apply De Morgan s theorem to bring negations before the atoms.
¬(A Å B) = ¬A Ä ¬B
¬(A Ä B) = ¬A Å ¬B
Step 3: Use Distributive laws and other equivalent formulae to obtain the
normal forms.

19. Predicate Logic
"It is also called as First oder logic or predicate calculus or
quantificational logic.
"Propositional logic are not enough to represent all the real life
problems, hence we need predicate logic that uses three additional
notations i.e. predicates, terms and quantifiers.

20. Predicates
"A predicate is defined as a relation that binds two atoms together.
E.g. Bhaskar likes aeroplane is represented as
LIKES (Bhaskar, aeroplane)
"Here LIKES is a predicate that links two atoms Bhaskar and aeroplane .
"This predicate can be generalised as LIKES(x,y) means x likes y. Here x
and y are variables.

21. Terms
"Terms are the arguments in the predicate.
E.g. LIKES (Bhaskar, aeroplane)
In this, Bhaskar and aeroplane are Terms.
"It is also possible to have a function as an argument.
E.g. Ravi s father is Rani s father is represented as
FATHER(father(Ravi), Rani)
Here FATHER is a predicate and father(Ravi) is a function to indicate
Ravi s father.

22. Terms
Terms can be defined as follows:-
1. A constant is a term.
E.g. LIKES (Bhaskar, Aeroplane),
Bhaskar and Aeroplane are constant terms.
2. A Variable is a term.
E.g. LIKES (x,y)
x and y are variable terms.
3. If f is a function and x1, x2, x3, &,xn are terms, then f(x1, x2, x3, &,xn) is a
term.
E.g. FATHER(father(Ravi,Raj,Shalu),Rani)

23. Quantifier
"A Quantifier is a symbol that permits one to declare or identify the
range or scope of variables in a logical expression.
"There are two basic quantifiers used in logic. They are:-
1. Universal quantifier (V)
2. Existential quantifier (Ž)
"If x is a variable, then Vx is read as
1) for all x2) for each x3) for every x
"If y is a variable, then Žy is read as
1) there exists a y2) for some y3) for atleast one y

24. Example Predicate statements
English Sentence
1.Marcus was a man.
2.All Pompeians were Romans.
3.All Romans were either loyal to
Caesar or hated him.
4.Everyone is loyal to someone.
5.People only try to assassinate rulers
they are not loyal to.
6.Marcus tried to assassinate Caesar.
7.All men are people.
Corresponding Predicate statement
1.man(Marcus)
2. Vx : Pompeian(x) !’ Roman(x)
3. Vx : Roman(x) !’ loyalto(x, Caesar) Å
hate(x, Caesar)
4. Vx : !’ y : loyalto(x,y)
5. Vx : Vy : person(x) Ä ruler(y) Ä
tryassassinate(x,y) !’ ¬ loyalto(x,y)
6.Tryassassinate(Marcus, Caesar)
7. Vx : man(x) !’ person(x)

26. Some predicate calculus expressions
Calculus Expression Meaning
Vx [A(x)] A is true for all x
Žx [A(x)] A is true for some x
Vx [¬A(x)] A is false for all x
Žx [¬A(x)] A is false for some x
¬( Vx [¬A(x)]) A is true for some x
¬(Žx [¬A(x)]) A is true for all x

27. Free and Bound Variables
"A variable in the formula is bound if and only if its occurence is within
the scope of the quantifier.
E.g. Vx (A(x) !’ B(x))
The formula states that for all x, A(x) implies B(x). Any change in the
quantifier has an effect on both A(x) and B(x). Hence the variable x is a
bound variable.
" A variable in the formula is free if and only if its occurence is outside
the scope of the quantifier having the variable.
E.g. VxŽy (A(x,y,z)
The variable z is a free variable in this formula.

28. Normal forms in Predicate Logic
"In predicate logic, the normal form is called as Prenex Normal form
(PNF). It is also called as clause form.
"A formula A in predicate logic is said to be in Prenex Normal form if it
has the form
(Q1x1)(Q2x2)(Q3x3) &(Qnxn) B
where Qixi is the quantifier and B is the formula without any quantifier.
"(Q1x1)(Q2x2)(Q3x3) &(Qnxn) is called the prefix and B is called the matrix
of the formula A.
"Examples:-VxŽy (A(x,y) Ä B(x))
ŽxŽyŽz ((A(x,y,z) Ä B(x,z) Å ¬C(y,z)

29. Conversion Procedure to PNF or Clause Form
Step 1: Eliminate implications (!’ ) and biconditionals (< > ). For this, use
the equivalence laws;-
(A !’ B) = ¬A Å B
(A < > B) = (A !’ B ) Ä (B !’ A) = (¬A Å B) Ä (¬B Å A)
Step 2: Reduce the scope of NOT symbol by the formula (¬(¬A) = A and
apply De Morgan s theorem to bring negations before the atoms.
¬(A Å B) = ¬A Ä ¬B
¬(A Ä B) = ¬A Å ¬B
Also use the formulae:- ¬(Vx (A(x))) = Žx (¬A(x))
¬(Žx (A(x))) = Vx (¬A(x))

30. Conversion Procedure to PNF contd...
Step 3: for the sake of clarity, rename bound variables if necessary.
Step 4: Use equivalent formulae to move quantifiers to the left of the
formula to obtain the normal form.
Some equivalent formulas are:-
(Qx) A(x) Å B = (Qx) (A(x) Å B)
(Qx) A(x) Ä B = (Qx) (A(x) Ä B)
(Q1x) A(x) Å (Q2y) B(y) = (Q1x) (Q2y) (A(x) Å B(y))
(Q1x) A(x) Ä (Q2y) B(y) = (Q1x) (Q2y) (A(x) Ä B(y))

32. Herbrand s Theorem
"Herbrand in 1930 published a theorem that formed the basis for
mechanical theorem proving. The first practical implementation of
Herbrand s theorem was carried out by Gilmore in 1960 and later
modified by Davis and Putnam in the same year. David and Putnam
method is widely used.
"The steps involved in this method are:-
1. Transform the formulae into Prenex Normal Form.
2. Transform the matrix into CNF.
3. Eliminate existential quantifiers by using skolem functions.

33. Skolem Form
"A formula P in the Prenex Normal Form has a skolem for P
s
, which is
obtained when all Ž are removed by replacing the variables as functions
of variables preceding it.
"If there are no V before Ž, a constant symbol is used.
"E.g. The formula P = Žq Vr Žs Žt (A (q,r) !’ B (s,t)) can be converted into
its skolem form as P
s
= Vr (A (c,r) !’ B (f1 (r ), f2 (r ))

34. Herbrand Universe and Base
"A formula, if valid in all interpretations, becomes a theorem. Finding out
whether it is valid in all interpretations is a tedious task. Herbrand s
work reduce the work of considering all the interpretations.
"Variable-free terms are called ground terms.
"The set of ground terms is called as the Herbrand Universe.
"Since the terms and atoms are constructed from constants, functions
and symbols of the language under consideration, they are also
variable-free.
"The set of ground atoms is called as Herbrand Base.

35. Rules of Inference
"The manipulation procedures that help one to deduce new statements
from the given statements, in order to prove something, are called as
Rules of inferences.
"Some important rules of inferences are:-
For propositional logic:
1. Addition : A !’ (A Å B)
2. Simplification : (A Ä B) !’ A
3. Modus Ponens : (A Ä (A !’ B) !’ B)
4. Modus Tollens : (¬B Ä (A !’ B)) !’ ¬A
5. Disjunctive Syllogism : ((P Å Q) Ä ¬P) !’ Q

36. 6. Hypothetical Syllogism: [(A !’ B) Ä (B !’ C)] !’ [(A !’ C)]
7. Constructive Dilemma: [(A !’ B) Ä (C !’ D) Ä (A Å C)] !’ (B Å D)
8. Destructive Dilemma : [(A !’ B) Ä (C !’ D) Ä (¬B Å D)] !’ [(¬A Å ¬C)]
9. Negation: (¬(¬A)) = A
Rules of Inference for Predicate logic are:-
1. Universal instantiation : Vx P(x)
.: P(a)
2. Universal generalization: P(a)
.: Vx P(x)
3. Existential instantiation :Žx P(x)
.: P(c )
4. Existential generalization: P(c)
.: Žx P(x)

37. Resolution
"Resolution Principle: Given any two clauses A and B, if there is a literal
P1 in A , which has a complementary literal P2 in B, delete P1 and P2
from A and B and construct a disjunction of the remaining clauses. The
clause so constructed is called the resolvent of A and B .
"E.g. Consider the following clauses:-
A : PÅQÅRB: ¬PÅQÅRC: ¬QÅR
Hence AÄBÄC = (PÅQÅR) Ä (¬PÅQÅR) Ä (¬QÅR)
= (QÅR) Ä (¬QÅR)
= R
"Sometimes the resolution might ultimately lead to an empty set or NIL

38. Substitutions
"When there are variables in a clause then the problem becomes
complicated and neccessitates to make proper substitutions.
"There are three major types of substitutions:-
1. Substitution of a variable by a constant.
2. Substitution of a variable by another variable.
3. Substitution of a variable by a function that does not contain the
same variable.
"If A is a formula of predicate calculus, then (x|t)A denotes the formula
that results when every occurence of x in A is substituted by t.

39. Unification Algorithm
"A substitution that makes two clauses resolvable is called a Unifier and
the process of identifying such unifiers is carried out by the unification
algorithm.
"The unification algorithm tries to find out the Most General Unifier
(MGU) between a given set of atomic formulae.
"E.g. Question: Find the MGU of A(x, f(g(x), a) and A(b,y,z)
Solution: step 1: SUBST = []
step 2: SUBST = [(x|b)] ie A(b, f(g(b),a)
step 3: SUBST = [(y|f(g(b)), (x|b)]
step 4: SUBST = [(z|a), (y|f(g(b)), (x|b)] = MCU

40. Theorem Proving using Resolution
"There are two basic methods of theorem proving:
Method 1: Start with the given axiom, use the rules of inference and
prove the theorem.
Method 2: Prove that the negation of the result cannot be TRUE.
"The second method is commonly known as theorem proving using
refutation. The methodology for that is :-
Step 1: Find the negation of the result to be proved.
Step 2: Add it as a valid statement to the given set of statements.
Step 3: Perform resolution on these statements until a contradiction is
encountered.

41. Step 4: Conclude that the contradiction is due to the assumed negation
of the result.
Step 5: So the negated assumption that is made is FALSE or the result
to be proved is TRUE.
E.g. Question: Given that a) Vx [Physician (x) !’ knows_surgery (x)]
b) Physician(Bhaskar)
Prove that knows_surgery(Bhaskar)
Proof using Method 1: Modus Ponens states that if there is an axiom of
the form P !’ Q and another of the form P, then Q logically follows.
Assuming Physician(Bhaskar) as P and Vx [Physician (x) !’ knows_surgery
(x)] as P !’ Q, then the knows_surgery(Bhaskar) is Q and it logically
follows.

42. Proof using Method 2:
Assume the negation of the result
¬ knows_surgery(Bhaskar) & Equation 1
The given axioms are:
Physician(Bhaskar) & Equation 2
Vx [Physician (x) !’ knows_surgery (x)] & Equation 3
Equation 3 can be written as
¬Physician (x) Å knows_surgery (x) & Equation 4
(Because the quantifier is universal)
In Equation 4, substitute (x|Bhaskar). so we have,
¬Physician (Bhaskar) Å knows_surgery (Bhaskar) & Equation 5
Resolving Equations 1 and 5 , we have

43. ¬Physician (Bhaskar) & Equation 6
Resolving equations 2 and 6, we have a contradiction.
This contradiction was due to the assumption that was made ie the
negation of the result. Hence the negation of the result was FALSE or the
result is TRUE.
Strategies used to resolve statements:-
1. breadth first
2. Set of support
3. Unit preference
4. Linear input form
5. Ancestry filtered form

44. Question Answering
"Resolution and unification also help in deriving answers to questions.
"Chang divided the type of questions into 4 major classes:-
Class A: Questions that require yes or no answer
Class B: Questions that start with Where is or Who is or Under
what condition etc.
Class C: Here answer is in the form of sequence of actions and the order
is important.
Class D: Questiosn whose answers require testing of some conditions.

45. Limitations of Logic as KR scheme
"It is monotonic in nature. Hence not ideal for real world problems.
"It cannot handle uncertainity.
"Coding is difficult.
"Requires considerable amount of time to prove statements.
"Difficult to codify heuristics in logic
"Search will not terminate until a solution exists. Hence we will be going
on adding clause after clause, but the solution will be still elusive

46. References
"Artificial Intelligence by Elain Rich, Kevin Knight and Shivashankar B Nair.
"Foundations of Artificial Intelligence and Expert Systems by V S
Jankiraman, K Sarukesi & P Gopalakrishan.