Propositional logic class 2 of AI/ Ml for Diploma students

It is a topic in AI/ML

2. Introduction
Apropositionisadeclarativestatementwhichiseithertrueor
false.
Propositionscanbeeithertrueorfalse,butitcannotbeboth.
Apropositionformulawhichisalwaystrueiscalledtautology.
Apropositionformulawhichisalwaysfalseis
calledContradiction.
Apropositionformulawhichhasbothtrueandfalsevaluesis
calledContingency.

3. Propositional Logic Connectives
Symbol Word Technical
Term
Example
 AND Conjunction A B
 OR Disjunction A B
 Implies Implication A B
 If and only IfBi-Conditional AB
 Not Negation A or B

4. Inference rules
Inverse−Aninverseoftheconditionalstatementisthe
negationofboththehypothesisandtheconclusion.Ifthe
statementis“Ifp,thenq”,theinversewillbe“Ifnotp,thennot
q”.Thustheinverseofp→qis¬p→¬q.
Converse−Theconverseoftheconditionalstatementis
computedbyinterchangingthehypothesisandthe
conclusion.Ifthestatementis“Ifp,thenq”,theconversewill
be“Ifq,thenp”.Theconverseofp→qisq→p.
Contra-positive−Thecontra-positiveoftheconditionalis
computedbyinterchangingthehypothesisandtheconclusion
oftheinversestatement.Thecontra-positiveofp→
q is ¬q→¬p.

5. Types of Inference rules
1. Modus Ponens:
It states that if “P” and “P →Q” is true, then we can infer that
Q will be true.
2. Modus Tollens:
It states that if “P→Q” is true and”¬ Q” is true, then “¬
P”will also true. It can be represented as:
3. Hypothetical Syllogism
It states that if “P→R” is true whenever “P→Q” is true, and
“Q→R” is true.
4. Disjunctive Syllogism:
It states that if “P∨Q is true”, and “¬P is true”, then Q will be
true.

6. 5.Addition
ItstatesthatIf“Pistrue”,thenP∨Qwillbetrue.
6.Simplification
ItstatesthatifP∧Qistrue,thenQorPwillalsobetrue.
7.Resolution
ItstatesthatifP∨Qand¬P∧Ristrue,thenQ∨Rwillalsobe
true.

7. Few more Inference Rules
. Unit Resolution:
•If is True & is True, Then is True
3. Resolution:
or
•The 2 premises are said to be resolvedand the variable is said to be
resolved away.
…. and several other rules
7

8. A sentence/premisemay have:
Validity(always true):-Tautology
Satisfiability(sometimes true):-Contingency
No Satisfiability(always false):-Contradiction
8

9. Find if the following is valid, satisfactory or invalid?
((P Q) R) (P R).
Ans:-Valid/ Tautology

10. 10
Conjunctive Normal Form (CNF)
Conjunctive normal form (CNF) is an approach to Boolean logic that
expressesformulasas :
Conjunctionsof clauseswith an ANDor OR
Each clauseconnected by a conjunction, (AND)must be either a literalor
contain a disjunction(OR) operator.
CNFis useful for automated theorem proving
CNF is used for automated theorem proving.

11. 11
Conjunctive Normal Form (CNF)
// Replace all
// De Morgan’s theorem
// in normal form

12. 12
Propositional Logic –Example-1
3
rd
inference rule (resolution)
// B is resolved away
// Q is resolved away

13. 13
Propositional Logic –Example-2
Problem:
If it is “Hot”, Then it is “Humid”
If it is “Humid”, Then it will “Rain”
Q: If it is “Hot”, Show that it will “Rain”
Solution: H: It is “Humid” (sentences)
R: it will “Rain”
O: It is “Hot”
•If it is “Hot”, Then it is “Humid”: O => H
•If it is “Humid”, Then it will “Rain : H => R
•It is “Hot” : O
•Add “Negation of Goal”:
CNF: Step-1
(eliminate =>)
Apply Resolution
Inference rule on
H, O & R
Resolution rule

14. 14
Propositional Logic –Example-3

15. LimitationsofPropositionalLogic
Inpropositionallogic,wecanonlyrepresentthefacts,which
areeithertrueorfalse.
PLisnotsufficienttorepresentthecomplexsentencesor
naturallanguagestatements.
Thepropositionallogichasverylimitedexpressivepower.