AI PPT-ALR_Unit-3-1.pdf

This is an ai book

1. ADITYA ENGINEERING COLLEGE (A)
Course : ARTIFICIAL INTELLIGENCE
UNIT-3

2. Artificial Intelligence
Unit–III
LogicConcepts:Introduction,propositionalcalculus,propositionallogic,natural
deductionsystem,axiomaticsystem,semantictableausysteminpropositionallogic,
resolutionrefutationinpropositionallogic,predicatelogic.

3. Aditya Engineering College (A)
LOGIC CONCEPTS
Logic helps in investigating and classifying the structure of statements and
arguments through the system of formal study of inference.
Logicisastudyofprinciplesusedto
–distinguishcorrectfromincorrectreasoning.
–Logical system should possesses properties such as consistency, soundness, and
completeness.
–Consistency implies that none of the theorems of the system should contradict each other.
–Soundness means that the inference rules shall never allow a false inference from true
premises.
Formally itdealswith
–thenotionoftruthinanabstractsenseandisconcerned withtheprinciplesofvalid
inferencing.

4. Aditya Engineering College (A)
Logic…
Apropositioninlogicisadeclarativestatementswhichareeithertrueor
false(butnotboth)inagivencontext.Forexample,
–“Jackisamale”,
–"JacklovesMary"etc.
Givensomepropositionstobetrueinagiven context,
–logichelpsininferencingnewproposition,whichisalso trueinthe
samecontext.
Supposewearegivenasetofpropositions as
–“Itishottoday"and
–“Ifitishotitwillrain",then
–wecaninferthat
“Itwill raintoday".

5. Propositional Calculus
Aditya Engineering College (A)
Propositional Calculus is a language of propositions basically
refers
–tosetofrulesusedtocombinethepropositionstoformcompound
propositionsusinglogicaloperatorsoftencalledconnectivessuchas
ordot,V,~,or(),
1.Well-FormedFormula
Well-formed formulaisdefinedas:
–Anatomisawell-formedformula.
–Ifisawell-formed formula,then~isawell-formed
formula.
–Ifandarewellformedformulae,then(),(V), (),
()arealsowell-formedformulae.
–Apropositional expressionis awell-formedformula
ifand onlyifitcanbeobtainedby usingaboveconditions.

6. Propositional Calculus
Aditya Engineering College (A)
Well-FormedFormulaExamples
R1-Anatomisawell-formedformula.
R2-IfisaWFF, then ~is a
well-formedformula.
R3-Ifandarewellformedformulae,then(),
(V), (),()arealsowell-formed
formulae.

7. Aditya Engineering College (A)
Propositional Calculus…
2.TruthTable
Truth table gives us operational definitions of
important logical operators.
–Byusingtruthtable,thetruthvaluesofwell-formed
formulaearecalculated.
●Truthtableelaboratesallpossibletruthvaluesofa
formula.
●Themeaningsofthelogicaloperatorsaregivenby
thefollowingtruthtable.
PQ ~PPQPVQPQ PQ
TT F T T T T
TF F F T F F
FT T F T T F
FF T F F T T
Q) Compute the TT: (AVB)∧(~B->A)
Negation ~
Conjunction^ or dot
Disjunction V
If-then(Implication) ->
iff(Biconditional) <->

8. Aditya Engineering College (A)
3.EquivalenceLaws
8
1.PQ  QP
2.PVQ  QVP
Commutation
Association
1.P(QR)  (PQ)R
2.PV(QVR)  (PV Q)V R
DoubleNegation
~(~P)
DistributiveLaws
 P
1.P(QVR)  (P Q)V(PR)
2.PV(QR)  (PVQ)(PVR)
Morgan’sLaws
1.~(P Q) ~PV~Q
2.~(PVQ) ~P~Q
De
LawofExcludedMiddle
PV ~P
LawofContradiction
P~P
 T(true)
 F(false)
Propositional Calculus…

9. Aditya Engineering College (A)
Propositional Logic
•Knowledge Representation can be done with
1)Propositional Logic 2)First Order Logic
•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.
•Propositional logic is also called Boolean logic as it works on 0 and
1.
•Machine In AI can be given input in terms of knowledge but machine cannot understand this
knowledge which is framed using English sentences.
•So this knowledge must be represented inaway understandable to machine , this is called
knowledge representation.

10. Aditya Engineering College (A)
Propositional Logic
•In propositional logic, we use symbolic variables to represent the logic, and we can
use any symbol for a representing a proposition, such A, B, C, P, Q, R, etc.
•Propositions can be either true or false, but it cannot be both.
•Propositional logic consists of an object, relations or function, and logical
connectives.
•These connectives are also called logical operators.
•The propositions and connectives are the basic elements of the propositional logic.
•Connectives can be said as a logical operator which connects two sentences.
•A proposition formula which is always true is called tautology, and it is also called a
valid sentence.
•ApropositionformulawhichisalwaysfalseiscalledContradiction.
•Apropositionformulawhichhasbothtrueandfalsevaluesiscalled.
•Statementswhicharequestions,commands,oropinionsarenotpropositions
suchas"Whereis","Howareyou","Whatisyourname",arenotpropositions.

11. Aditya Engineering College (A)
Propositional Logic
Syntax of propositional logic:
•The syntax of propositional logic defines the allowable sentences for the knowledge
representation. There are two types of Propositions:
Atomic Propositions:
Atomic Proposition: Atomic propositions are the simple propositions. It consists of a
single proposition symbol. These are the sentences which must be either true or false.
a)2+2is4,itisanatomicpropositionasitisatruefact.
b)"TheSuniscold"isalsoapropositionasitisafalsefact.
Compound propositions
•Compoundpropositionsareconstructedbycombiningsimpleroratomic
propositions,usingparenthesisandlogicalconnectives.
Example:
a)"Itisrainingtoday,andstreetiswet."
b)“Rajisadoctor,andhisclinicisinMumbai."

12. Aditya Engineering College (A)
Propositional Logic
LogicalConnectives
Negation ~
Conjunction^
Disjunction V
If-then(Implication) ->
iff(Biconditional) <->
Logical connectives are used to connect two simpler propositions or representing a sentence
logically. We can create compound propositions with the help of logical connectives.
Example:
X: It is cold
Y: It is sunny
Z:It is breezy
1.It is not cold ~X
2.It is cold and it is breezy X^Z
3.It is cold or it is breezy XvZ
4.If it is breezy then it is cold Z->X
5.If it is breezy and cold then it is not sunny Z^X -> ~Y
6.It will be cold iffit is breezy X <-> Z

13. Aditya Engineering College (A)
Propositional Logic
Examples:
Raj did not read book
~ read(Raj,book)
Raj watches Amazon or Netflix
Watches(Raj,Amazon) v Watches(Raj,Netflix)
If Raj buys mobile then color is black
Buys(Raj,Mobile) -> Color( Mobile,black)
Raj becomes happy if and only if Raj eats dairy milk.
becomes(Raj,happy) <-> eats( Raj,Dairymilk)

14. LimitationsofPropositionallogic:
•WecannotrepresentrelationslikeALL,some,ornonewithpropositional
logic.Example:
•Alltheboysareintelligent.
•Someapplesaresweet.
•Propositionallogichaslimitedexpressivepower.
•Inpropositionallogic,wecannotdescribestatementsintermsoftheir
propertiesorlogicalrelationships.
Propositional Logic

15. Aditya Engineering College (A)
Natural Deduction System
●NDisbasedonthesetoffewdeductiveinference rules.
●Thenamenaturaldeductivesystemisgivenbecause itmimics
thepatternofnaturalreasoning.
●Ithasabout10deductiveinferencerules.
Conventions:
–EforElimination,IforIntroducing.
–P, P
k, (1 kn)areatoms.
–
k,(1 kn)andareformulae.

16. Aditya Engineering College (A)
Natural Deduction System
ND RULES:
Rule1:I-(Introducing)
I-:IfP
1,P
2,…,P
nthen P
1P
2…P
n
Interpretation:IfwehavehypothesizedorprovedP
1,P
2,…andP
n,thentheirconjunction
P
1P
2…P
nisalsoprovedorderived.
Rule2:E-(Eliminating)
E-:IfP1P2…PnthenPi( 1in)
Interpretation:IfwehaveprovedP1P2…Pn,thenanyPiisalsoprovedorderived.
Thisruleshowsthatcanbeeliminatedtoyieldoneofitsconjuncts.
Rule3:I-V(IntroducingV)
I-V:IfP
i(1in)thenP
1VP
2V…VP
n
Interpretation:IfanyPi(1 in)isproved,thenP
1V…VP
nisalsoproved.

17. Aditya Engineering College (A)
Natural Deduction System
ND RULES…
Rule4:E-V(Eliminating V)
E-V:IfP
1 V… VP
n,P
1P,…,P
nPthenP
Interpretation:IfP
1V…VP
n,P
1P,…,andP
nPare proved,thenPisproved.
Rule5:I- (Introducing)
I-:Iffrom
1,…,
ninferis provedthen

1…
nisproved
Interpretation:Ifgiven
1,
2,…and
ntobeprovedandfromthesewededucethen
1
2…
n
isalsoproved.
Rule6:E- (Eliminating) -ModusPonen
E-:IfP
1P,P
1thenP

18. Aditya Engineering College (A)
Natural Deduction System
ND RULES…
Rule7:I-(Introducing )
I-: IfP
1P
2,P
2P
1thenP
1P
2
Rule8:E-(Elimination)
E-:IfP
1P
2 then P
1 P
2, P
2P
1
Rule9:I-~(Introducing~)
I-~:IffromPinferP
1~P
1isprovedthen
~Pisproved
Rule10:E-~(Eliminating~)
E-~:Iffrom~PinferP
1 ~P
1isproved
then Pisproved

19. Aditya Engineering College (A)
Natural Deduction System
Cont…
●Ifaformulaisderived/provedfromasetof
premises/hypotheses{
1,…,
n},
–thenonecanwriteitasfrom
1,…,
n
●Innaturaldeductivesystem,
infer.
–atheorem tobeprovedshouldhave
from1, …,ninfer.
aform
●Theoreminfermeansthat
–therearenopremisesandistrueunderall
interpretationsi.e.,isatautologyorvalid.

20. Aditya Engineering College (A)
Natural Deduction System
●Ifweassumethatisapremise,thenwe
concludethatisprovedifisgiveni.e.,
–if‘frominfer’ isatheoremthenisconcluded.
–Theconverseofthisisalsotrue.
DeductionTheorem:Infer(
1
2…
n)
isatheoremofnaturaldeductivesystemifand
onlyif
from
1,
2,…,
ninferisatheorem.
Usefultips:Toproveaformula
1
2…
n
,itissufficienttoproveatheorem
from
1,
2,…,
ninfer.
Cont..

21. Aditya Engineering College (A)
Natural Deduction System
Example
Example1:ProvethatP(QVR)followsfromPQ
Solution:Thisproblemisrestatedinnaturaldeductivesystemas"fromP
QinferP(QVR)".Theformalproofisgivenasfollows:
{Theorem}
{ premise}
fromP QinferP(QVR)
PQ (1)
{E-,(1)} P (2)
{E-,(1)} Q (3)
{I-V ,(3)} QVR (4)
{I-,(2,4)} P(QVR) Conclusion

22. Aditya Engineering College (A)
AxiomaticSystem(AS)
●ASisbasedonthesetofonlythreeaxiomsand oneruleof
deduction.
–Itisminimalinstructurebutaspowerfulasthetruthtableandnatural
deductionapproaches.
–Theproofsofthetheoremsareoftendifficultandrequireaguessin
selectionofappropriateaxiom(s)andrules.
–Thesemethodsbasicallyrequireforwardchainingstrategywherewestart
withthegivenhypothesesandprovethegoal.
–Onlytwologicaloperatorsnot(~)andimplies(->)areallowed.
(V,,<->canbeconvertedintotheaboveoperators).
Example:
AB=~(A->~B)
AVB=~A->B
A<->B=(A->B)(B->A)=~[((A->B)->~((B->A)]

23. Aditya Engineering College (A)
AxiomaticSystem(AS)
●Threeaxiomsandoneruleofdeduction.
Axiom1(A1): ()
Axiom2(A2):(())(()())
Axiom3(A3): (~~ )( )
ModusPonen(MP)definedasfollows:
Hypotheses:andConsequent:

24. Aditya Engineering College (A)
AxiomaticSystem(AS)
Definition:AdeductionofaformulainAxiomatic
SystemforPropositionalLogicisasequenceofwell-
formedformulae
1,
2,...,
nsuchthatforeachi,
(1in),either
–Either
iisanaxiomor
iisahypothesis(giventobetrue)
–Or
iisderivedfrom
jand
kwherej,k<iusingmodus
poneninferencerule.
Wecall
itobeadeductiveconsequenceof{
1,
...,
i-1}.
Itisdenotedby{
1,..,
i-1 }|-
i.Moreformally,
deductiveconsequenceisdefinedonnextslide.
Cont…

25. Aditya Engineering College (A)
Examples
Establishthefollowing:
Ex1:
{Q}|-(PQ)i.e.,PQisadeductiveconsequence of{Q}.
{Hypothesis} Q (1)
{AxiomA1}
{MP,(1,2)}
Q
P
(P
Q
Q) (2)
proved
AxiomaticSystem(AS)

26. Aditya Engineering College (A)
Examples–Cont…
Ex2:
{P Q,QR}|-(PR)i.e.,P Risa
deductiveconsequenceof{PQ,QR}.
PQ (1)
QR
{Hypothesis}
{Hypothesis}
{AxiomA1}
{MP,(2,3)}
{AxiomA2}
(2)
(QR)(P (QR))(3)
P(QR)
(P(QR))
((PQ)(PR))
(4)
(5)
{MP,(4,5)}
{MP, (1,6)}
(PQ)(PR)
PR
(6)
proved
AxiomaticSystem(AS)

27. Aditya Engineering College (A)
Semantic Tableaux System in PL
●Earlierapproachesrequire
–constructionofproofofaformulafromgivensetof formulaeand
arecalleddirectmethods.
●Insemantictableaux,
–thesetofrulesareappliedsystematicallyonaformulaor setofformulae
toestablish itsconsistencyorinconsistency.
●Semantictableau
–binarytreeconstructedbyusingsemanticrules formulaasaroot
●Assumeandbeanytwoformulae.

28. Aditya Engineering College (A)
Semantic Tableaux System…
●Semantictableau
–binarytreeconstructedbyusingsemanticrules formulaasaroot
●Assumeandbeanytwoformulae.
RULES
Letandbeanytwoformulae.
Rule1:Atableauforaformula()isconstructedbyaddingbothandto
thesamepath(branch).Thiscanberepresentedasfollows:



Interpretation:istrueifbothandaretrue

29. Aditya Engineering College (A)
Semantic Tableaux System…
Rules-Cont…
Rule2: Atableauforaformula~()is
constructedbyaddingtwoalternativepathsone
containing~andothercontaining~
~()
~ ~ 
Interpretation:
or~istrue
~()istrueifeither~

30. Aditya Engineering College (A)
Semantic Tableaux System…
Cont…
Rule3:Atableauforaformula(V)is
constructedbyaddingtwonewpathsone
containingandothercontaining.
V
 
Interpretation:Vistrueifeither
oristrue

31. Aditya Engineering College (A)
Semantic Tableaux System…
Rule4:Atableauforaformula~(V)is
constructedbyaddingboth~and~tothe
samepath.Thiscanbeexpressedasfollows:
~(V)
~
~
Rule5:Semantictableaufor~~
~~ 


32. Aditya Engineering College (A)
Semantic Tableaux System…
Rule6:Semantictableaufor

~ 
Semantictableaufor~()Rule7:
~()

~

33. Aditya Engineering College (A)
Semantic Tableaux System…
Rule8: Semantic tableaufor
()V(~~)

Rule9:
 ~~
Semantictableaufor~()
)~()(~ )V(~
~()
~ ~

34. Aditya Engineering College (A)
Artificial Intelligence Dr P Udayakumar
Semantic Tableaux System…
Consistencyand Inconsistency: Satisfiability and Unsatisfiability
IfanatomPand~Pappearonasame pathofa
semantictableau,
–theninconsistencyisindicatedandsuchpathissaidto
becontradictoryorclosed(finished)path.
–Evenifonepathremainsnoncontradictoryor
unclosed(open),thentheformulaattherootofa
tableauisconsistent.

35. Aditya Engineering College (A)
Artificial Intelligence Dr P Udayakumar
Semantic Tableaux System…
Avaluationissaidtobeamodelof(or 
satisfies)iff()=T.
Intableauxapproach,modelforaconsistent formulais
constructedasfollows:
–Onanopenpath,assigntruthvaluestoatoms (positiveor
negative)ofwhichisattherootofa tableausuchthatismade
tobetrue.
–ItisachievedbyassigningtruthvalueTtoeach atomicformula
(positiveornegative)onthat path.
Valuation

36. Aditya Engineering College (A)
Artificial Intelligence Dr P Udayakumar
Semantic Tableaux System…
Contradictorytableau(orfinishedtableau)isdefinedto
beatableauinwhichallthepathsarecontradictoryor
closed(finished).
ConsistentandInconsistent
Ifatableauforaformulaattherootisacontradictory
tableau,thenaformulaissaidtobeinconsistent.
Aformulaisconsistentifthereisatleastonopenpath
inatableauwithroot
ContradictoryTableau

37. Aditya Engineering College (A)
Artificial Intelligence Dr P Udayakumar
Semantic Tableaux System…
Example:Showthat
:(PQR)(~PS)Q~R~Sis
inconsistent(Unsatisfiable)usingtableauxmethod.
R)(~PS)Q~R~S{T-root}(PQ 
{Applyrule1to1}
(1)
(2)
(3)
PQR
~PS
Q
~R
~S
S{Applyrule6to3} P
{Applyrule6to2)}~(PQ)
Closed:{S,~S}onthepath
R
Closed{R,~R}
~P ~Q
{P,~P}Closed Closed{~Q,Q}

38. Aditya Engineering College (A)
Artificial Intelligence Dr P Udayakumar
Semantic Tableaux System…
Problem:Showthat:(Q~R)(RP) is
consistent( satisfiable)andfinditsmodel.
Solution:
{T-root} (Q~R)(RP)
{Applyrule1to1}
(1)
(2)
(3)
(Q~R)
(RP)
{Applyrule1to2}Q
{Applyrule6to3}~R
~R P
open open

39. Aditya Engineering College (A)
Artificial Intelligence Dr P Udayakumar
Semantic Tableaux System…
Sincetableauforhasopenpaths,weconclude thatis
consistent.
ThemodelsareconstructedbyassigningTtoall atomicformulae
appearingonopenpaths.
–AssignQ=Tand~ R= Ti.e.,R=F.
•So{Q=T,R =F}isamodelof.
–AssignQ= Tand~R= TandP=T.
•So{P=T,Q=T,R=F}isanothermodel.
UsefulTip:
–Thumbruleforconstructingatableauisto applynon
branchingrulesbeforethebranching rulesinanyorder
Example-Cont…

40. Aditya Engineering College (A)
Artificial Intelligence Dr P Udayakumar
Semantic Tableaux System…
Theorem:(Soundness)
Ifistableauprovable(|-), thenis
valid(|=)i.e.,|-|=.
Theorem:(Completeness)
Ifisvalid,thenistableauprovablei.e.,
|=|-.
SoundnessandCompleteness

41. Aditya Engineering College (A)
Artificial Intelligence Dr P Udayakumar
Semantic Tableaux System…
Example-Validity
Example:Showthat:P(QP)isvalid
Solution:Inordertoshowthatisavalid,wewilltry
toshowthatistableauprovablei.e.,~is
inconsistent.
{T-root} ~(P(QP)) (1)
P) (2)
{Apply rule7to2}
{Applyrule7to1}P
~(Q
Q
~P
Closed{P,~P}
HenceP( QP)isvalid.

42. Aditya Engineering College (A)
Artificial Intelligence Dr P Udayakumar
Resolution Refutation in PL
Resolutionrefutationisanothersimplemethod toprovea formulaby
contradiction.
–Herenegationofgoaltobeprovedisaddedtogivenset ofclauses.
–Itisshownthenthatthereisarefutationinnewsetusing resolutionprinciple.
Resolution:Duringthisprocessweneedto identify
–twoclauses,onewithpositiveatom(P)andotherwith negativeatom(~P)forthe
applicationofresolutionrule.
Resolutionisbasedonmodusponeninferencerule.
–Thismethodismostfavouredfordeveloping computerbasedtheorem
provers.
–Automatictheoremproversusingresolutionare simpleandefficientsystems.
Resolutionisperformedonspecialtypesof formulaecalledclauses.
–Clauseispropositionalformulaexpressedusing
•{V,~}operators.

43. Aditya Engineering College (A)
Artificial Intelligence Dr P Udayakumar
Resolution Refutation in PL
Conjunctive and Disjunctive NormalForms
InDisjunctiveNormalForm(DNF),
–a formulaisrepresented intheform
–(L
11…..L
1n)V..…V(L
m1….. L
mk ), whereallL
ijare
literals.Itisadisjunctionofconjunction.
InConjunctive NormalForm(CNF),
–a formulaisrepresented intheform
–(L
11V…..VL
1n)……(L
p1V…..VL
pm),
L
ij
whereall areliterals.Itisa
conjunctionofdisjunction.
Aclauseisaspecialformulaexpressedasdisjunctionofliterals.If
aclausecontainsonlyoneliteral,thenitiscalledunitclause.

44. Aditya Engineering College (A)
Artificial Intelligence Dr P Udayakumar
Resolution Refutation in PL
ConversionofaFormulato itsCNF
EachformulainPropositionalLogiccanbeeasily
transformedintoitsequivalentDNForCNFrepresentation
usingequivalencelaws.
–Eliminateandbyusingthefollowing
equivalencelaws.
PQ
PQ


~PVQ
(PQ)(QP)
–Eliminatedoublenegationsignsbyusing
~~P  P

45. Aditya Engineering College (A)
Artificial Intelligence Dr P Udayakumar
Resolution Refutation in PL
Cont…
UseDeMorgan’slawstopush~(negation)
immediatelybeforeatomic formula.
~(PQ)
~(PVQ)


~PV~Q
~P~Q
Usedistributivelaw togetCNF.
PV(QR) (PVQ)(PVR)
WenoticethatCNFrepresentationofaformulais
oftheform
–(C
1…..C
n),whereeachC
k,(1kn)is
aclausethatisdisjunctionofliterals.

46. Aditya Engineering College (A)
Artificial Intelligence Dr P Udayakumar
Resolution Refutation in PL
ResolutionofClauses
ProfSarojKaushik,CSE,
IITD
IftwoclausesC
1andC
2containacomplementarypair
ofliterals{L,~L},then
–theseclausescanberesolvedtogetherbydeletingLfromC
1
and~LfromC
2andconstructinganewclausebythe
disjunctionoftheremainingliteralsinC
1andC
2.
Thenewclausethusgeneratediscalled
resolventofC
1andC
2.
–HereC
1andC
2arecalledparentsofresolvedclause.
–Iftheresolventcontainsoneormoresetof
iscomplementarypairofliterals,thenresolvent
alwaystrue.

47. Aditya Engineering College (A)
Artificial Intelligence Dr P Udayakumar
Resolution Refutation in PL
ResolutionTree
Invertedbinarytreeisgeneratedwiththelastnodeof
thebinarytreetobearesolvent.
Thisalsocalledresolutiontree.
Example:Findresolventof:
C
1=PVQVR
C
2=~QV~W
C
3=~PV~W

48. Aditya Engineering College (A)
Artificial Intelligence Dr P Udayakumar
Resolution Refutation in PL
Example-ResolutionTree
PVQVR ~QV~W
{Q,~Q}
PVRV~W
{P,~P}
~PV~W
R V~W
ThusResolvent(C
1,C
2,C
3)=RV~W

49. Aditya Engineering College (A)
Artificial Intelligence Dr P Udayakumar
Resolution Refutation in PL
Example:“Marywillgetherdegreeifsheregistersasa
studentandpassherexam.Shehasregisteredherselfasa
student.Shehaspassedherexam”.Showthatshewillgeta
degree.
Solution:Symbolizeabovestatementsasfollows:R:Mary
isaregisteredstudent
P:MaryhaspassedherexamD:Mary
getsherdegree
Theformulaecorrespondingtoabovelistedsentencesareas
follows:

50. Aditya Engineering College (A)
Artificial Intelligence Dr P Udayakumar
Resolution Refutation in PL
Marywillgetherdegreeifsheregistersasa
studentandpassherexam.
RPD(~RV~PVD)
Shehasregisteredherselfasastudent.
R
Shehaspassed herexam.
P
Conclude“Mary willgetadegree”.
D
Cont…

51. Aditya Engineering College (A)
Artificial Intelligence Dr P Udayakumar
Resolution Refutation in PL
Setofclausesare:
–S={~RV~PVD,R,P}
Addnegationof"Marygetsherdegree(= D)"toS.
NewsetS'is:
–S'={~RV~PVD,R,P,~D}
Wecaneasilyseethatemptyclauseis deduced
fromaboveset.
Hencewecanconcludethat“Marygetsher degree”
Example–Cont…

52. Aditya Engineering College (A)
Artificial Intelligence Dr P Udayakumar
Resolution Refutation in PL
DerivingContradiction
~RV~PVD R
~PVD P
D ~D

53. Aditya Engineering College (A)
Artificial Intelligence Dr P Udayakumar
Resolution Refutation in PL
Exercises
I.Establishthe following:
1.{PQ,QR}|-(PR)
2.{P Q}|-(RP)(RQ)
3.{P }|-(~PQ)
4.{~Q,P(~QR)}|-PR
5.{PQ,~Q}|-~P.ThisiscalledModusTollenrule.
II.Provethefollowingtheorems
1.|-(PP)
2.|-(~PP)P
3.|-(P Q)(~Q~P)
4.|-(P ~Q)(Q~P)
III.Givetableauproofofeachofthefollowingformulaeandshowthatformulaearevalid.
1.P(QP)
2.(P(QVR)((PQ)V(P R))
3.~ (PVQ)(~P ~Q)
IV.Arethefollowingargumentsvalid?
1.IfJohn livesinEnglandthenhelivesinUK.JohnlivesinEngland.Therefore,JohnlivesinUK.
2.IfJohnlivesinEnglandthenhelives inUK.JohnlivesinUK.Therefore,JohnlivesinEngland.
3.IfJohnlivesinEnglandthenhelivesinUK.Johndoesnotlive inUK.Therefore,Johndoesnotlive inEngland.
V.Prove byresolutionrefutation
1.{PQ,~PV R}|=QV R
2.{P ,QR,PR}|=PR
3.{PQR,P}|=R

54. Aditya Engineering College (A)
Artificial Intelligence Dr P Udayakumar
Resolution Refutation in PL