Chap.3 Knowledge Representation Issues Chap.4 Inference in First Order Logic

Knowledge–based agents,
The Wumpus world Logic,
Propositional logic,
Propositional theorem proving
Effective propositional model checking,
Agents based on propositional logic,
First Order Logic,
Forward Chaining/ Resolution,
Backward Chaining/ Resolution,
Unification Algorithm, Resolution,
Clausal Normal Form (CNF)

1. Artificial Intelligence
Chap.3 Knowledge Representation
Issues
Prepared by:
Prof. KhushaliB Kathiriya

2. Outline for 8
th
semester
Representations And Mappings
Approaches To Knowledge Representation
Prepared by: Prof. Khushali B Kathiriya
2

3. Artificial Intelligence
Chap.3 Logical Agents & First
Order Logic
Prepared by:
Prof. KhushaliB Kathiriya

4. Outline for 6
th
semester
Logical Agents:
Knowledge–based agents
The Wumpus world
Logic
Propositional logic
Propositional theorem proving
Effective propositional model checking
Agents based on propositional logic
First Order Logic:
Representation Revisited
Syntax and Semantics of First Order logic
Using First Order logic
Prepared by: Prof. Khushali B Kathiriya
4

5. What is Knowledge?
Knowledge is a general term. Knowledge is a progression that starts with
data which is of limited utility.
By organizing or analyzing the data, we understand what the data means
and this becomes information.
The interpretation or evaluation of information yield knowledge.
An understanding of the principles embodied within the knowledge is
wisdom.
Prepared by: Prof. Khushali B Kathiriya
5

6. 6
Prepared by: Prof. Khushali B Kathiriya

7. What is Knowledge representation ?
Humansarebestatunderstanding,reasoning,andinterpretingknowledge.
Humanknowsthings,whichisknowledgeandaspertheirknowledgethey
performvariousactionsintherealworld.Buthowmachinesdoallthese
thingscomesunderknowledgerepresentationandreasoning.
Prepared by: Prof. Khushali B Kathiriya
7

8. What is Knowledge representation ?
(Cont.)
HencewecandescribeKnowledgerepresentationasfollowing:
1.Knowledgerepresentationandreasoning(KR,KRR)isthepartofArtificial
intelligencewhichconcernedwithAIagentsthinkingandhowthinking
contributestointelligentbehaviorofagents.
2.Itisresponsibleforrepresentinginformationabouttherealworldsothata
computercanunderstandandcanutilizethisknowledgetosolvethecomplex
realworldproblemssuchasdiagnosisamedicalconditionorcommunicating
withhumansinnaturallanguage.
3.Itisalsoawaywhichdescribeshowwecanrepresentknowledgeinartificial
intelligence.Knowledgerepresentationisnotjuststoringdataintosome
database,butitalsoenablesanintelligentmachinetolearnfromthat
knowledgeandexperiencessothatitcanbehaveintelligentlylikeahuman.
Prepared by: Prof. Khushali B Kathiriya
8

9. What to represent?
Object:Allthefactsaboutobjectsinourworlddomain.E.g.,Guitars
containsstrings,trumpetsarebrassinstruments.
Events:Eventsaretheactionswhichoccurinourworld.
Performance:Itdescribebehaviorwhichinvolvesknowledgeabouthowto
dothings.
Meta-knowledge:Itisknowledgeaboutwhatweknow.
Facts:Factsarethetruthsabouttherealworldandwhatwerepresent.
Knowledge-Base:Thecentralcomponentoftheknowledge-basedagents
istheknowledgebase.ItisrepresentedasKB.TheKnowledgebaseisa
groupoftheSentences(Here,sentencesareusedasatechnicaltermand
notidenticalwiththeEnglishlanguage).
Knowledge:Knowledgeisawarenessorfamiliaritygainedbyexperiences
offacts,data,andsituations.
Prepared by: Prof. Khushali B Kathiriya
9

10. Framework of Knowledge Representation
Prepared by: Prof. Khushali B Kathiriya
10

11. Artificial Intelligence
Knowledge-Based Agent in AI
Prepared by:
Prof. KhushaliB Kathiriya

12. Knowledge-Based Agent in AI
Anintelligentagentneedsknowledgeabouttherealworldfor
takingdecisionsandreasoningtoactefficiently.
Knowledge-basedagentsarethoseagentswhohavethe
capabilityofmaintaininganinternalstateofknowledge,reason
overthatknowledge,updatetheirknowledgeafterobservations
andtakeactions.Theseagentscanrepresenttheworldwithsome
formalrepresentationandactintelligently.
Knowledge-basedagentsarecomposedoftwomainparts:
1.Knowledge-baseand
2.Inferencesystem.
Prepared by: Prof. KhushaliB Kathiriya
12

13. The architecture of knowledge-based
agent
Prepared by: Prof. Khushali B Kathiriya
13

14. The architecture of knowledge-based
agent (Cont.)
Thediagramisrepresentingageneralizedarchitectureforaknowledge-
basedagent.Theknowledge-basedagent(KBA)takeinputfromthe
environmentbyperceivingtheenvironment.Theinputistakenbythe
inferenceengineoftheagentandwhichalsocommunicatewithKBto
decideaspertheknowledgestoreinKB.ThelearningelementofKBA
regularlyupdatestheKBbylearningnewknowledge.
Prepared by: Prof. Khushali B Kathiriya
14

15. Why use knowledge base?
Knowledge base:Knowledge-baseisacentralcomponent ofa
knowledge-basedagent,itisalsoknownasKB.Itisacollectionof
sentences(here'sentence'isatechnicaltermanditisnotidenticalto
sentenceinEnglish).Thesesentencesareexpressedinalanguagewhichis
calledaknowledgerepresentationlanguage.TheKnowledge-baseofKBA
storesfactabouttheworld.
Knowledge-baseisrequiredforupdatingknowledgeforanagenttolearn
withexperiencesandtakeactionaspertheknowledge.
Prepared by: Prof. Khushali B Kathiriya
15

16. Inference System
Inferencemeansderivingnewsentencesfromold.Inferencesystem
allowsustoaddanewsentencetotheknowledgebase.A
sentenceisapropositionabouttheworld.Inferencesystemapplies
logicalrulestotheKBtodeducenewinformation.
Inferencesystemgeneratesnewfactssothatanagentcanupdate
theKB.Aninferencesystemworksmainlyintworuleswhichare
givenas:
1.Forwardchaining
2.Backwardchaining
Prepared by: Prof. Khushali B Kathiriya
16

17. Artificial Intelligence
Techniques of Knowledge Representation
Prepared by:
Prof. KhushaliB Kathiriya

18. Techniques/ Approaches of Knowledge
Representation
Knowledge can berepresented usingthefollowing
approaches/techniques:
Prepared by: Prof. Khushali B Kathiriya
18

19. Artificial Intelligence
Logical Representation
Prepared by:
Prof. KhushaliB Kathiriya

20. 1. Logical Representation
Logicalrepresentationisalanguagewithsomeconcreteruleswhich
dealswithpropositionsandhasnoambiguityinrepresentation.Logical
representationmeansdrawingaconclusionbasedonvarious
conditions.
Thisrepresentationlaysdownsomeimportantcommunicationrules.It
consistsofpreciselydefinedsyntaxandsemanticswhichsupportsthe
soundinference.Eachsentencecanbetranslatedintologicsusing
syntaxandsemantics.
Logicalrepresentationcanbecategorizedinto:
1.PropositionalLogic
2.FirstOrderPredicateLogic
3.HigherorderPredicateLogic
4.FuzzyLogic
Prepared by: Prof. Khushali B Kathiriya
20

21. 1. Logical Representation (Cont.)
1.Propositional Logics:
All propositions either true/false (1/0).
We can not identify relation between 2 sentences.
For example…..
Prepared by: Prof. Khushali B Kathiriya
21
Sentences Truth value Proposition value
Sky is blue True True
Roses are red True True
2+2=5 False True

22. 1. Logical Representation (Cont.)
2.FirstOrderPredicatedLogic:
Thesearemuchmoreexpressiveandmakeuseofvariables,constants,
predicates,functionsandquantifiersalongwiththeconnectiveexplained
alreadyinprevioussection.
Prepared by: Prof. Khushali B Kathiriya
22

23. 1. Logical Representation (Cont.)
Advantages of logical representationDisadvantages of logical representation
Logical representation enables us to
do logical reasoning.
Logical representations have some
restrictions and are challenging to work
with.
Logical representation is the basis for
the programming languages.
Logical representation technique may
not be very natural, and inference may
not be so efficient.
Prepared by: Prof. Khushali B Kathiriya
23

24. Artificial Intelligence
Semantic net representation
Prepared by:
Prof. KhushaliB Kathiriya

25. 2. Semantic net representation
Semanticnetworksarealternativeofpredicatelogicforknowledge
representation.InSemanticnetworks,wecanrepresentourknowledgein
theformofgraphicalnetworks.Thisnetworkconsistsofnodesrepresenting
objectsandarcswhichdescribetherelationshipbetweenthoseobjects.
Semanticnetworkscancategorizetheobjectindifferentformsandcan
alsolinkthoseobjects.Semanticnetworksareeasytounderstandandcan
beeasilyextended.
Prepared by: Prof. Khushali B Kathiriya
25

26. 2. Semantic net representation (Cont.)
Following are some statements which we need to represent in the form of
nodes and arcs.
1.Jerry is a cat.
2.Jerry is a mammal
3.Jerry is owned by Priya.
4.Jerry is brown colored.
5.All Mammals are animal.
Prepared by: Prof. Khushali B Kathiriya
26

27. 2. Semantic net representation (Cont.)
Drawbacks in Semantic representation:
1.Semanticnetworkstakemorecomputationaltimeatruntimeasweneedto
traversethecompletenetworktreetoanswersomequestions.Itmightbe
possibleintheworstcasescenariothataftertraversingtheentiretree,we
findthatthesolutiondoesnotexistinthisnetwork.
2.Semanticnetworkstrytomodelhuman-likememory(Whichhas1015
neuronsandlinks)tostoretheinformation,butinpractice,itisnotpossible
tobuildsuchavastsemanticnetwork.
3.Thesetypesofrepresentationsareinadequateastheydonothaveany
equivalentquantifier,e.g.,forall,forsome,none,etc.
4.Semanticnetworksdonothaveanystandarddefinitionforthelinknames.
5.Thesenetworksarenotintelligentanddependonthecreatorofthesystem.
Prepared by: Prof. Khushali B Kathiriya
27

28. 2. Semantic net representation (Cont.)
Advantages of Semantic network:
1.Semanticnetworksareanaturalrepresentationofknowledge.
2.Semanticnetworksconveymeaninginatransparentmanner.
3.Thesenetworksaresimpleandeasilyunderstandable.
Prepared by: Prof. Khushali B Kathiriya
28

29. 2. Semantic net representation (Cont.)
Represent following sentences using semantic networks.
Isa(person, mammal)
Instance(Mike-Hall, person)
Team(Mike-Hall, Cardiff)
Prepared by: Prof. Khushali B Kathiriya
29

30. 2. Semantic net representation (Cont.)
Prepared by: Prof. Khushali B Kathiriya
30

31. Artificial Intelligence
Frame Representation
Prepared by:
Prof. KhushaliB Kathiriya

32. 3. Frame Representation
ThisconceptwasintroducedbyMarvinMinskyin1975.theyaremostlyused
whenthetaskbecomesquitecomplexandneedsmorestructured
representation.
Morestructuredthesystembecomesmorewouldbetherequirementof
usingframeswhichwouldprovebeneficial.Generallyframesarerecord
likestructuresthatconsistsofacollectionofslotsorattributesandthe
correspondingslotvalues.
Slotscanbeofanysizeandtype.Theslotshavenamesandvaluescalled
asfacts.Facetscanhavenamesornumberstoo.Asimpleframeisshown
infigforpersonram.
Prepared by: Prof. Khushali B Kathiriya
32

33. 3. Frame Representation (Cont.)
Prepared by: Prof. Khushali B Kathiriya
33
Ram Brothers Laxman Cat
Bharat
Grey
Color

34. 3. Frame Representation (Cont.)
Sr. No. Slot Value
1 Ram -
2 Profession Professor
3 Age 50
4 Wife Sita
5 Children LuvKush
6 Address 4C gbRoad
7 City Banaras
8 State UP
9 Zip 400615
Prepared by: Prof. Khushali B Kathiriya
34

35. 3. Frame Representation (Cont.)
Advantages of frame representation:
1.Theframeknowledgerepresentationmakestheprogrammingeasierby
groupingtherelateddata.
2.Theframerepresentationiscomparablyflexibleandusedbymany
applicationsinAI.
3.Itisveryeasytoaddslotsfornewattributeandrelations.
4.Itiseasytoincludedefaultdataandtosearchformissingvalues.
5.Framerepresentationiseasytounderstandandvisualize.
Prepared by: Prof. Khushali B Kathiriya
35

36. 3. Frame Representation (Cont.)
Disadvantages of frame representation:
1.Inframesysteminferencemechanismisnotbeeasilyprocessed.
2.Inferencemechanismcannotbesmoothlyproceededbyframe
representation.
3.Framerepresentationhasamuchgeneralizedapproach.
Prepared by: Prof. Khushali B Kathiriya
36

37. 4. Production Rules
Productionrulessystemconsistof(condition,action)pairswhich
mean,"Ifconditionthenaction".Ithasmainlythreeparts:
Thesetofproductionrules
WorkingMemory
Therecognize-act-cycle
Prepared by: Prof. Khushali B Kathiriya
37

38. 4. Production Rules (Cont.)
Example:
IF (at bus stop AND bus arrives) THEN action (get into the bus)
IF (on the bus AND paid AND empty seat) THEN action (sit down).
IF (on bus AND unpaid) THEN action (pay charges).
IF (bus arrives at destination) THEN action (get down from the bus).
Prepared by: Prof. Khushali B Kathiriya
38

39. 4. Production Rules (Cont.)
Advantages of Production rule:
1.Theproductionrulesareexpressedinnaturallanguage.
2.Theproductionrulesarehighlymodular,sowecaneasilyremove,add
ormodifyanindividualrule.
Disadvantages of Production rule:
1.Productionrulesystemdoesnotexhibitanylearningcapabilities,asit
doesnotstoretheresultoftheproblemforthefutureuses.
2.Duringtheexecutionoftheprogram,manyrulesmaybeactivehence
rule-basedproductionsystemsareinefficient.
Prepared by: Prof. Khushali B Kathiriya
39

40. Artificial Intelligence
Issues in Knowledge Representation
Prepared by:
Prof. KhushaliB Kathiriya

41. Issues in Knowledge Representation
ImportantAttributes:
Therecanbeattributesthatoccurinmanydifferenttypesofproblemwith
differentnames.
Forexample,instanceandisaandeachisimportantbecauseeachsupports
propertyinheritance.
Relationships:
Therelationships,suchas,inverses,existence;amongvariousattributesofan
objectneedtoberepresentedwithoutanyambiguity.
Forexample,band(John,NewYorkCity)
Prepared by: Prof. Khushali B Kathiriya
41

42. Issues in Knowledge Representation
(Cont.)
Granularity:
Thisrepresentsatwhatlevelshouldtheknowledgeberepresentedandwhatare
primitives.Choosingthegranularityofrepresentationprimitivesarefundamental
conceptssuchasholding,seeing,playingandasEnglishisaveryrichlanguage
withoverhalfamillionwordstochooseasourprimitivesinaseriesofsituations.
Forexample,ifTomfeedsadogthenitcouldbecome:feeds(tom,dog)
Iftomgivesthedogabonelike:gives(tom,dog,bone)arethesethesame?
Prepared by: Prof. Khushali B Kathiriya
42

43. Artificial Intelligence
Propositional Logic
Prepared by:
Prof. KhushaliB Kathiriya

44. Propositional Logic
Propositionallogic(PL)isthesimplestformoflogicwhereallthe
statementsaremadebypropositions.Apropositionisadeclarative
statementwhichiseithertrueorfalse.Itisatechniqueof
knowledgerepresentationinlogicalandmathematicalform.
Example:
ItisSunday.T
TheSunrisesfromWest. F
3+3=7. F
Some students are intelligent. T/F both
Prepared by: Prof. Khushali B Kathiriya
44
PL
SemanticSyntax

45. Propositional Logic (Cont.)
Following are some basic facts about propositional logic:
PropositionallogicisalsocalledBooleanlogicasitworkson0and1.
Inpropositionallogic,weusesymbolicvariablestorepresentthelogic,
andwecanuseanysymbolforarepresentingaproposition,suchA,B,
C,P,Q,R,etc.
Propositionscanbeeithertrueorfalse,butitcannotbeboth.
Propositionallogicconsistsofanobject,relationsorfunction,
andlogicalconnectives.
Theseconnectivesarealsocalledlogicaloperators.
Prepared by: Prof. Khushali B Kathiriya
45
PL
ComplexAtomic

46. Syntax in Propositional Logic (Cont.)
Rules for conjunction: NEGATIVEoperator
A sentence such as ¬ P is called negation of P. A literal can be
either Positive literal or negative literal.
Example,
P= Today is Sunday.
1 is represent as a true
0 is represent as a false
Prepared by: Prof. Khushali B Kathiriya
47
P ¬ P
1 0
0 1

47. Syntax in Propositional Logic (Cont.)
Rules for conjunction: ANDoperator
A sentence which has∧connective such as,P ∧Qis called a
conjunction.
Example:Rohan is intelligent andhardworking.
It can be written as,
P= Rohan is intelligent.
Q= Rohan is hardworking.
So we can write it as P ∧Q.
Prepared by: Prof. Khushali B Kathiriya
48
P Q P ^ Q
1 1 1
1 0 0
0 1 0
0 0 0

48. Syntax in Propositional Logic (Cont.)
Rules for Disjunction: ORoperator
A sentence which has ∨connective, such asP ∨Q. is called
disjunction, where P and Q are the propositions.
Example: "Ritika is a doctor orEngineer",
It can be written as,
P= Ritika is Doctor.
Q= Ritika is Engineer,
So we can write it asP ∨Q.
Prepared by: Prof. Khushali B Kathiriya
49
P Q P v Q
1 1 1
1 0 1
0 1 1
0 0 0

49. Syntax in Propositional Logic (Cont.)
Rules for conjunction: CONDITIONAL
A sentence such as P → Q, is called an implication. Implications
are also known as if-then rules.
Example: Ifit is raining, then the street is wet.
Let P= It is raining,
Q= Street is wet,
so it is represented as P → Q
Prepared by: Prof. Khushali B Kathiriya
50
P Q P →Q
1 1 1
1 0 0
0 1 1
0 0 1

50. Syntax in Propositional Logic (Cont.)
Rulesforconjunction:BICONDITIONAL
AsentencesuchasP⇔QisaBiConditionalsentence,
Example:IfIambreathing,thenIamalive
P=Iambreathing
Q=Iamalive
ItcanberepresentedasP⇔Q.
Prepared by: Prof. Khushali B Kathiriya
51
P Q P ⇔Q
1 1 1
1 0 0
0 1 0
0 0 1

51. Summarized table Propositional Logic
Connectives (Cont.)
Prepared by: Prof. Khushali B Kathiriya
52

52. Artificial Intelligence
Example of Propositional Logic
Prepared by:
Prof. KhushaliB Kathiriya

53. Properties of Operators
Commutatively
P∧Q= Q ∧P, or
P ∨Q = Q ∨P.
Associativity
(P ∧Q) ∧R= P ∧(Q ∧R),
(P ∨Q) ∨R= P ∨(Q ∨R)
Identity element
P ∧True = P,
P ∨True= True.
Prepared by: Prof. Khushali B Kathiriya
54
Distributive
P∧(Q∨R)=(P∧Q)∨(P∧R).
P∨(Q∧R)=(P∨Q)∧(P∨R).
DEMorgan'sLaw
¬(P∧Q)=(¬P)∨(¬Q)
¬(P∨Q)=(¬P)∧(¬Q).
Double-negationelimination
¬(¬P)=P.

54. What is Propositional Logic?
A^BandB^Ashouldhavesamemeaningbutinnaturallanguagewords
andsentencesmayhavedifferentmeaning
Example,
1.RadhastartedfeelingfeverishandRadhawenttothedoctor.
2.RadhawenttodoctorandRadhastaredfeelingfeverish.
Here,sentence1andsentence2havedifferentmeaning
InAIpropositionallogicisarelationbetweenthetruthvalueofone
statementtothatofthetruthtableofotherstatement.
Prepared by: Prof. Khushali B Kathiriya
55

55. Example of Propositional Logic
1.¬(P ^ Q) , P →¬Q
Prepared by: Prof. Khushali B Kathiriya
56
P Q ¬Q (P ^ Q) ¬(P ^ Q) P →¬Q
1 1 0 1 0 0
1 0 1 0 1 1
0 1 0 0 1 1
0 0 1 0 1 1
P QIF P →Q
1 1 1
1 0 0
0 1 1
0 0 1
P QIFP ^ Q
1 1 1
1 0 0
0 1 0
0 0 0
P QIFP v Q
1 1 1
1 0 1
0 1 1
0 0 0

56. Example of Propositional Logic (Cont.)
2.¬P v ¬Q v R , Q v R, P→R
Prepared by: Prof. Khushali B Kathiriya
57
PQ R¬P¬Q¬Pv ¬Qv R(Q v R) P →R
0 0 0 1 1 1 0 1
0 0 1 1 1 1 1 1
0 1 0 1 0 1 1 1
0 1 1 1 0 1 1 1
1 0 0 0 1 1 0 0
1 0 1 0 1 1 1 1
1 1 0 0 0 0 1 0
1 1 1 0 0 1 1 1

57. Example of Propositional Logic (Cont.)
3.(P v Q) v ~(P v (Q ^ R))=1
Prepared by: Prof. Khushali B Kathiriya
58
PQ RP v QQ ^ RP v (Q ^ R)~(P v (Q ^ R))(P v Q) v ~(P v (Q ^ R))
0 0 0 0 0 0 1 1
0 0 1 0 0 0 1 1
0 1 0 1 0 0 1 1
0 1 1 1 1 1 0 1
1 0 0 1 0 1 0 1
1 0 1 1 0 1 0 1
1 1 0 1 0 1 0 1
1 1 1 1 1 1 0 1

58. Example of Propositional Logic (Cont.)
4.~[{~P v ~(Q ^ R)} v (P ^ R)]
Prepared by: Prof. Khushali B Kathiriya
59
I1
I2
I3
PQ R ~P I1 ~ I1 I2 I3I2 vI3 ~ (I2 v I3)
0 00 1 0 1 1 0 1 0
0 01 1 0 1 1 0 1 0
0 10 1 0 1 1 1 1 0
0 11 1 1 0 1 0 1 0
1 00 0 0 1 1 0 1 0
1 01 0 0 1 1 1 1 0
1 10 0 0 1 1 0 1 0
1 11 0 1 0 0 1 1 0

59. Example of Propositional Logic (Cont.)
5.(P→(Q→R)) →((P→Q) →(P→R))
Prepared by: Prof. Khushali B Kathiriya
60
PQ RQ→R I1 I2 I3 I4I1→I4
0 00 1 1 1 1 1 1
0 01 1 1 1 1 1 1
0 10 0 1 1 1 1 1
0 11 1 1 1 1 1 1
1 00 1 1 0 0 1 1
1 01 1 1 0 1 1 1
1 10 0 0 1 0 0 1
1 11 1 1 1 1 1 1
I1 I2 I3
I4
P QIF P →Q
1 1 1
1 0 0
0 1 1
0 0 1

60. Example of Propositional Logic (Cont.)
Try out your self:
1.(P ⇔(Q→R))⇔((P ⇔Q)→R)
2.((P ⇔Q) ^ (~ Q →R)) ⇔(~ (P ⇔R) →Q)
Prepared by: Prof. Khushali B Kathiriya
61

61. Limitation of Propositional Logic
WecannotrepresentrelationslikeALL,some,ornonewith
propositionallogic.
Example:
Allthegirlsarecute.
Someapplesaresweet.
Fewstudentsareintelligent.
Propositionallogichaslimitedexpressivepower.
Inpropositionallogic,wecannotdescribestatementsintermsof
theirpropertiesorlogicalrelationships.
Prepared by: Prof. Khushali B Kathiriya
62

62. Artificial Intelligence
Inference Rules
Prepared by:
Prof. KhushaliB Kathiriya

63. Inference Rules
Inference:
Inartificialintelligence,weneedintelligentcomputerswhichcan
createnewlogicfromoldlogicorbyevidence,sogeneratingthe
conclusionsfromevidenceandfactsistermedasInference.
InferenceRule:
Inferencerulesarethetemplatesforgeneratingvalidarguments.
Inferencerulesareappliedtoderiveproofsinartificialintelligence,and
theproofisasequenceoftheconclusionthatleadstothedesired
goal.
Ininferencerules,theimplicationamongalltheconnectivesplaysan
importantrole.
Prepared by: Prof. Khushali B Kathiriya
64

64. Inference Rules (Cont.)
1.Modus Ponens
2.Modus Tollens
3.Hypothetical Syllogism
4.Disjunctive Syllogism
Prepared by: Prof. Khushali B Kathiriya
65

65. Inference Rules (Cont.)
1. Modus Ponens
The Modus Ponens rule is one of the most important rules of inference,
and it states that if P and P →Q is true, then we can infer that Q will be
true. It can be represented as:
66
Prepared by: Prof. Khushali B Kathiriya

66. Inference Rules (Cont.)
1. Modus Ponens
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.
67
Prepared by: Prof. Khushali B Kathiriya

67. Inference Rules (Cont.)
2. Modus Tollens
The Modus Tollens rule state that if P→Q is true and¬ Q is true, then
¬ Pwill also true. It can be represented as:
Prepared by: Prof. Khushali B Kathiriya
68

68. Inference Rules (Cont.)
2. Modus Tollens
Statement-1:"If I am sleepythen 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
Prepared by: Prof. Khushali B Kathiriya
69

69. Inference Rules (Cont.)
3. Hypothetical Syllogism
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:
Notation is : P →Q, Q →R
P →R
Prepared by: Prof. Khushali B Kathiriya
70

70. Inference Rules (Cont.)
3. Hypothetical Syllogism
Statement-1:If you have my password , then you can log on to
my face book.
Statement-2: If you can log onto my face book account then you
can delete my face book account .
Statement-3: If you have my password then you can delete my
face book account.
71
Prepared by: Prof. Khushali B Kathiriya

71. Inference Rules (Cont.)
4. Disjunctive Syllogism
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:
Prepared by: Prof. Khushali B Kathiriya
72

72. Inference Rules (Cont.)
4. Disjunctive Syllogism
Statement-1:Today is Sundayor Monday. ==>P∨Q
Statement-2:Today is not Sunday. ==> ¬P
Conclusion:Today is Monday. ==> Q
Prepared by: Prof. Khushali B Kathiriya
73

73. Inference Rules (Cont.)
Inshortinferencerulesaysthatnewsentencecanbecreatebylogically
followingthesetofsentencesofknowledgebase.
Prepared by: Prof. Khushali B Kathiriya
74
Sr. No.Inference RulesPremises (KB)Conclusion
1 Modus Ponens X, X →Y Y
2 Substitution X →Y & Y →Z X = Y
3 Chain Rule X →Y, Y →Z X →Z
4 AND introduction X, Y X ^ Y
5 Transposition X →Y ~X →~Y

74. Artificial Intelligence
Horn Clause
Prepared by:
Prof. KhushaliB Kathiriya

75. Horn Clause
A Horn clause is aclause (adisjunctionofliterals) with at most one positive
literal.
~A1 V ~A2 V ~A3 V . . . . . V ~An VB
Lets take one example,
(A1 ^ A2 ^ A3 ^ . . . . . ^ An) →B
Apply DE Morgan's Law on given equation,
~(A1 ^ A2 ^ A3 ^ . . . . . ^ An) VB
Apply Distributive Law,
~A1 V~A2 V~A3 V. . . . . V ~An VB
Prepared by: Prof. Khushali B Kathiriya
76
Horn clause

76. Properties of Operators
Commutatively
P∧Q= Q ∧P, or
P ∨Q = Q ∨P.
Associativity
(P ∧Q) ∧R= P ∧(Q ∧R),
(P ∨Q) ∨R= P ∨(Q ∨R)
Identity element
P ∧True = P,
P ∨True= True.
Prepared by: Prof. Khushali B Kathiriya
77
Distributive
P∧(Q∨R)=(P∧Q)∨(P∧R).
P∨(Q∧R)=(P∨Q)∧(P∨R).
DEMorgan'sLaw
¬(P∧Q)=(¬P)∨(¬Q)
¬(P∨Q)=(¬P)∧(¬Q).
Double-negationelimination
¬(¬P)=P.

77. Horn Clause (Cont.)
1.(A ^ B ) →C
= (A ^ B) →C
Apply DE Morgan's Law
= ~ (A ^ B) V C
Apply Distributive Law
= ~A V ~B V C
Prepared by: Prof. Khushali B Kathiriya
78
Horn clause

78. Horn Clause (Cont.)
2.(A V B) →C
= (A V B ) →C
Apply DE Morgan's Law
= ~(A V B ) V C
Apply Distributive Law
= (~A ^ ~B) V C
= (~A V C) ^ (~A V ~B)
= (~A V C) , (~B V C)
Prepared by: Prof. Khushali B Kathiriya
79

79. Horn Clause (Cont.)
3.( A ^ ~B ) →C
= ( A ^ ~B ) →C
Apply DE Morgan's Law
= ~(A ^ ~B) V C
Apply Distributive Law
= (~A V B) V C
= ~A V B V C
Prepared by: Prof. Khushali B Kathiriya
80
Not Possible

80. Artificial Intelligence
Wampus World
Prepared by:
Prof. KhushaliB Kathiriya

81. Wampus World
TheWumpusworldisacavewhichhas4/4roomsconnectedwith
passageways.Sotherearetotal16roomswhichareconnectedwitheach
other.Wehaveaknowledge-basedagentwhowillgoforwardinthis
world.ThecavehasaroomwithabeastwhichiscalledWumpus,whoeats
anyonewhoenterstheroom.TheWumpuscanbeshotbytheagent,but
theagenthasasinglearrow.
IntheWumpusworld,therearesomePitsroomswhicharebottomless,and
ifagentfallsinPits,thenhewillbestuckthereforever.Theexcitingthing
withthiscaveisthatinoneroomthereisapossibilityoffindingaheapof
gold.Sotheagentgoalistofindthegoldandclimboutthecavewithout
fallenintoPitsoreatenbyWumpus.Theagentwillgetarewardifhecomes
outwithgold,andhewillgetapenaltyifeatenbyWumpusorfallsinthe
pit.
Prepared by: Prof. Khushali B Kathiriya
82

82. Wampus World (Cont.)
FollowingisasamplediagramforrepresentingtheWumpusworld.Itis
showingsomeroomswithPits,oneroomwithWumpusandoneagentat
(1,1)squarelocationoftheworld.
Prepared by: Prof. Khushali B Kathiriya
83

83. Wampus World (Cont.)
Therearealsosomecomponentswhichcanhelptheagenttonavigate
thecave.Thesecomponentsaregivenasfollows:
1.TheroomsadjacenttotheWumpusroomaresmelly,sothatitwouldhavesome
stench.
2.TheroomadjacenttoPITshasabreeze,soiftheagentreachesneartoPIT,then
hewillperceivethebreeze.
3.Therewillbeglitterintheroomifandonlyiftheroomhasgold.
4.TheWumpuscanbekilledbytheagentiftheagentisfacingtoit,andWumpus
willemitahorriblescreamwhichcanbeheardanywhereinthecave.
Prepared by: Prof. Khushali B Kathiriya
84

84. Wampus World (Cont.)
PEAS description of Wumpus world
To explain the Wumpus world we have given PEAS description as
below:
Performance measure
Environment
Actuators
Sensors
The Wumpus world Properties
Exploring the Wumpus world
Prepared by: Prof. Khushali B Kathiriya
85

85. Wampus World (Cont.)
Performancemeasure:
+1000rewardpointsiftheagentcomesoutofthecavewiththegold.
-1000pointspenaltyforbeingeatenbytheWumpusorfallingintothe
pit.
-1foreachaction,and-10forusinganarrow.
Thegameendsifeitheragentdiesorcameoutofthecave.
Prepared by: Prof. Khushali B Kathiriya
86

86. Wampus World (Cont.)
Environment:
A4*4gridofrooms.
Theagentinitiallyinroomsquare[1,1],facingtowardtheright.
LocationofWumpusandgoldarechosenrandomlyexceptthefirst
square[1,1].
Eachsquareofthecavecanbeapitwithprobability0.2exceptthe
firstsquare.
Prepared by: Prof. Khushali B Kathiriya
87

87. Wampus World (Cont.)
Actuators:
Left turn,
Right turn
Move forward
Grab
Release
Shoot
Prepared by: Prof. Khushali B Kathiriya
88

88. Wampus World (Cont.)
Sensors:
Theagentwillperceivethestenchifheisintheroomadjacenttothe
Wumpus.(Notdiagonally).
Theagentwillperceivebreezeifheisintheroomdirectlyadjacentto
thePit.
Theagentwillperceivetheglitterintheroomwherethegoldispresent.
Theagentwillperceivethebumpifhewalksintoawall.
WhentheWumpusisshot,itemitsahorriblescreamwhichcanbe
perceivedanywhereinthecave.
Theseperceptscanberepresentedasfiveelementlist,inwhichwewill
havedifferentindicatorsforeachsensor.
Exampleifagentperceivesstench,breeze,butnoglitter,nobump,and
no scream then itcan be represented as:
[Stench,Breeze,None,None,None].
Prepared by: Prof. Khushali B Kathiriya
89

89. Wampus World (Cont.)
TheWumpusworldProperties:
Partiallyobservable:TheWumpusworldispartiallyobservablebecause
theagentcanonlyperceivethecloseenvironmentsuchasan
adjacentroom.
Deterministic:Itisdeterministic,astheresultandoutcomeoftheworld
arealreadyknown.
Sequential:Theorderisimportant,soitissequential.
Static:ItisstaticasWumpusandPitsarenotmoving.
Discrete:Theenvironmentisdiscrete.
Oneagent:Theenvironmentisasingleagentaswehaveoneagent
onlyandWumpusisnotconsideredasanagent.
Prepared by: Prof. Khushali B Kathiriya
90

90. Wampus World (Cont.)
ExploringtheWumpusworld:
Agent'sFirststep:
Initially,theagentisinthefirstroomoron
thesquare[1,1],andwealreadyknow
thatthisroomissafefortheagent,soto
representonthebelowdiagram(a)that
roomissafewewilladdsymbolOK.
SymbolAisusedtorepresentagent,
symbolBforthebreeze,GforGlitteror
gold,Vforthevisitedroom,Pforpits,W
forWumpus.
AtRoom[1,1]agentdoesnotfeelany
breezeoranyStenchwhichmeansthe
adjacentsquaresarealsoOK.
Prepared by: Prof. Khushali B Kathiriya
91

91. Wampus World (Cont.)
Prepared by: Prof. Khushali B Kathiriya
92

92. Wampus World (Cont.)
Agent's second Step:
Nowagentneedstomoveforward,soitwilleithermoveto[1,2],or
[2,1].Let'ssupposeagentmovestotheroom[2,1],atthisroomagent
perceivessomebreezewhichmeansPitisaroundthisroom.Thepitcan
bein[3,1],or[2,2],sowewilladdsymbolP?tosaythat,isthisPitroom?
Nowagentwillstopandthinkandwillnotmakeanyharmfulmove.The
agentwillgobacktothe[1,1]room.Theroom[1,1],and[2,1]are
visitedbytheagent,sowewillusesymbolVtorepresentthevisited
squares.
Prepared by: Prof. Khushali B Kathiriya
93

93. Wampus World (Cont.)
Agent's third step:
Atthethirdstep,nowagentwillmovetotheroom[1,2]whichisOK.In
theroom[1,2]agentperceivesastenchwhichmeanstheremustbea
Wumpusnearby.ButWumpuscannotbeintheroom[1,1]asbyrulesof
thegame,andalsonotin[2,2](Agenthadnotdetectedanystench
whenhewasat[2,1]).ThereforeagentinfersthatWumpusisintheroom
[1,3],andincurrentstate,thereisnobreezewhichmeansin[2,2]there
isnoPitandnoWumpus.Soitissafe,andwewillmarkitOK,andthe
agentmovesfurtherin[2,2].
Prepared by: Prof. Khushali B Kathiriya
94

94. Wampus World (Cont.)
Prepared by: Prof. Khushali B Kathiriya
95

95. Wampus World (Cont.)
Agent's fourth step:
Atroom[2,2],herenostenchandnobreezespresentsolet'ssuppose
agentdecidestomoveto[2,3].Atroom[2,3]agentperceivesglitter,so
itshouldgrabthegoldandclimboutofthecave.
Prepared by: Prof. Khushali B Kathiriya
96

96. Artificial Intelligence
Chap.3 First Order Predicate Logic
Prepared by:
Prof. KhushaliB Kathiriya

97. First Order Predicate Logic
InthetopicofPropositionallogic,wehaveseenthathowtorepresent
statementsusingpropositionallogic.Butunfortunately,inpropositional
logic,wecanonlyrepresentthefacts,whichareeithertrueorfalse.
PLisnotsufficienttorepresentthecomplexsentencesornaturallanguage
statements.Thepropositionallogichasverylimitedexpressivepower.
Considerthefollowingsentence,whichwecannotrepresentusingPLlogic.
"Somehumansareintelligent“.
"Sachinlikescricket."
Torepresenttheabovestatements,PLlogicisnotsufficient,sowerequired
somemorepowerfullogic,suchasfirst-orderlogic(FOL).
Prepared by: Prof. Khushali B Kathiriya
98

98. First Order Predicate Logic (Cont.)
First-orderlogicisanotherwayofknowledgerepresentationinartificial
intelligence.Itisanextensiontopropositionallogic.
FOLissufficientlyexpressivetorepresentthenaturallanguagestatementsin
aconciseway.
First-orderlogicisalsoknownasPredicatelogicorFirst-orderpredicate
logic.First-orderlogicisapowerfullanguagethatdevelopsinformation
abouttheobjectsinamoreeasywayandcanalsoexpresstherelationship
betweenthoseobjects.
Prepared by: Prof. Khushali B Kathiriya
99

99. First Order Predicate Logic (Cont.)
First-orderlogic(likenaturallanguage)doesnotonlyassumethattheworld
containsfactslikepropositionallogicbutalsoassumesthefollowingthingsinthe
world:
1.Constantterm:A,B,people,numbers,colors,wars,theories,squares,pits,
Wumpus,etc.
2.Variableterm:Itcanbeunaryrelationsuchas:red,round,isadjacent,or
n-anyrelationsuchas:thesisterof,brotherof,hascolor,comesbetween
3.Function:Fatherof,bestfriend,thirdinningof,endof,etc.
Asanaturallanguage,first-orderlogicalsohastwomainparts:
1.Syntax
2.Semantics
Prepared by: Prof. Khushali B Kathiriya
100

100. Atomic Sentences
Atomicsentencesarethemostbasicsentencesoffirst-orderlogic.These
sentencesareformedfromapredicatesymbolfollowedbyaparenthesis
withasequenceofterms.
WecanrepresentatomicsentencesasPredicate(term1,term2,temp3,
......,termn).
Example:
RaviandAjayarebrothers:=>Brothers(Ravi,Ajay).
Chinkyisacat:=>cat(Chinky).
Prepared by: Prof. Khushali B Kathiriya
101

101. Complex Sentences
Complexsentencesaremadebycombiningatomicsentencesusing
connectives.
First-orderlogicstatementscanbedividedintotwoparts:
Subject:Subjectisthemainpartofthestatement.
Predicate:Apredicatecanbedefinedasarelation,whichbindstwo
atomstogetherinastatement.
Example:
"xisaninteger."
Prepared by: Prof. Khushali B Kathiriya
102

102. Quantifiers in First-Order Logic
Aquantifierisalanguageelementwhichgeneratesquantification,and
quantificationspecifiesthequantityofspecimenintheuniverseof
discourse.
Thesearethesymbolsthatpermittodetermineoridentifytherangeand
scopeofthevariableinthelogicalexpression.Therearetwotypesof
quantifier:
1.UniversalQuantifier,(forall,everyone,everything)
2.Existentialquantifier,(forsome,atleastone).
Prepared by: Prof. Khushali B Kathiriya
103

103. Universal Quantifier
Universalquantifierisasymboloflogicalrepresentation,whichspecifies
thatthestatementwithinitsrangeistrueforeverythingoreveryinstanceof
aparticularthing.
TheUniversalquantifierisrepresentedbyasymbol∀,whichresemblesan
invertedA.
If x is a variable, then ∀x is read as:
•For all x
•For each x
•For every x.
Prepared by: Prof. Khushali B Kathiriya
104

104. Universal Quantifier (Cont.)
Prepared by: Prof. Khushali B Kathiriya
105

105. Existential Quantifier
Existentialquantifiersarethetypeofquantifiers,whichexpressthatthe
statementwithinitsscopeistrueforatleastoneinstanceofsomething.
Itisdenotedbythelogicaloperator∃,whichresemblesasinvertedE.
Whenitisusedwithapredicatevariablethenitiscalledasanexistential
quantifier.
Ifxisavariable,thenexistentialquantifierwillbe∃xor∃(x).Anditwillbe
readas:
•Thereexistsa'x.'
•Forsome'x.'
•Foratleastone'x.'
Prepared by: Prof. Khushali B Kathiriya
106

106. Existential Quantifier (Cont.)
Prepared by: Prof. Khushali B Kathiriya
107

107. Properties of Quantifiers
In Universal quantifier, ∀x∀yis similar to ∀y∀x.
In Existential quantifier, ∃x∃yis similar to ∃y∃x.
∃x∀yis not similar to ∀y∃x.
Prepared by: Prof. Khushali B Kathiriya
108

108. Artificial Intelligence
Example of FOL
Prepared by:
Prof. KhushaliB Kathiriya

109. Example of FOL
1.All birds fly.
In this question the predicate is "fly(bird).
And since there are all birds who fly so it will be represented as follows.
∀x bird(x) →fly(x).
Prepared by: Prof. Khushali B Kathiriya
110

110. Example of FOL
2.Every man respects his parent.
In this question, the predicate is "respect(x, y)," where x=man, and y=
parent.
Since there is every man so will use ∀, and it will be represented as
follows:
∀x man(x) → respects (x, parent).
Prepared by: Prof. Khushali B Kathiriya
111

111. Example of FOL (Cont.)
3.Some boys play cricket.
In this question, the predicate is "play(x, y)," where x= boys, and y=
game.
Since there are some boys so we will use∃, and it will be represented as:
∃x boys(x) ^ play(x, cricket).
Prepared by: Prof. Khushali B Kathiriya
112

112. Example of FOL (Cont.)
4.Not all students like both Mathematics and Science.
In this question, the predicate is "like(x, y)," where x= student, and y=
subject.
Since there are not all students, so we will use∀with negation,
sofollowing representation for this:
¬∀(x) [ student(x) → like(x, Mathematics) ∧like(x, Science)].
Prepared by: Prof. Khushali B Kathiriya
113

113. Example of FOL (Cont.)
5.Only one student failed in Mathematics.
In this question, the predicate is "failed(x, y)," where x= student, 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 (x, Mathematics)].
Prepared by: Prof. Khushali B Kathiriya
114

114. Artificial Intelligence
Representation Simple Facts in logic
Prepared by:
Prof. KhushaliB Kathiriya

115. Representation Simple Facts in logic
1.All students are smart.
∀x (Student(x) ⇒Smart(x))
2.There exists a student.
∃x Student(x)
3.There exists a smart student.
∃x (Student(x) ∧Smart(x))
Prepared by: Prof. Khushali B Kathiriya
117

116. Representation Simple Facts in logic
(Cont.)
4.Every student loves some student.
∀x (Student(x) ⇒∃y (Student(y) ∧Loves(x,y)))
5.Every student loves some other student.
∀x (Student(x) ⇒∃y (Student(y) ∧¬(x=y) ∧Loves(x,y)))
6.There is a student who is loved by every other student.
∃x (Student(x) ∧∀y (Student(y) ∧¬(x=y) ⇒Loves(y,x)))
Prepared by: Prof. Khushali B Kathiriya
118

117. Representation Simple Facts in logic
(Cont.)
1.Bill is a student.
Student(Bill)
2.Bill takes either Analysis or Geometry (but not both).
Takes(Bill,Analysis) ⇔¬Takes(Bill,Geometry)
3.Bill takes Analysis or Geometry (or both).
Takes(Bill,Analysis) ∨Takes(Bill,Geometry)
4.Bill takes Analysis and Geometry.
Takes(Bill,Analysis) ∧Takes(Bill,Geometry)
5.Bill does not take Analysis.
¬Takes(Bill,Analysis)
Prepared by: Prof. Khushali B Kathiriya
119

118. Representation Simple Facts in logic
(Cont.)
6.No student loves Bill.
¬∃x (Student(x) ∧Loves(x,Bill)
7.Bill has at least one sister.
∃x SisterOf(x,Bill)
8.Bill has no sister.
¬∃x SisterOf(x,Bill)
9.Bill has at most one sister.
∀x,y(SisterOf(x,Bill) ∧SisterOf(y,Bill) ⇒x=y))
10.Bill has exactly one sister.
∃x (SisterOf(x,Bill) ∧∀y (SisterOf(y,Bill) ⇒x=y))
11.Bill has at least two sisters.
∃x,y(SisterOf(x,Bill) ∧SisterOf(y,Bill) ∧¬(x=y))
Prepared by: Prof. Khushali B Kathiriya
120

119. Representation Simple Facts in logic
(Cont.)
1.Anyone whom Mary loves is a football star.
2.Any student who does not pass does not play.
3.John is a student.
4.Any student who does not study does not pass.
5.Anyone who does not play is not a football star.
6.If John does not study, then Mary does not love John.
Prepared by: Prof. Khushali B Kathiriya
121

120. Representation Simple Facts in logic
(Cont.)
1.Anyone whom Mary loves is a football star.
∀x (LOVES(Mary,x) → STAR(x))
2.Any student who does not pass does not play.
∀x (STUDENT(x) ∧¬ PASS(x) → ¬ PLAY(x))
3.John is a student.
STUDENT(John)
4.Any student who does not study does not pass.
∀x (STUDENT(x) ∧¬ STUDY(x) → ¬ PASS(x))
5.Anyone who does not play is not a football star.
∀x (¬ PLAY(x) → ¬ STAR(x))
6.If John does not study, then Mary does not love John.
¬ STUDY(John) → ¬ LOVES(Mary,John)
Prepared by: Prof. Khushali B Kathiriya
122

121. Representation Simple Facts in logic
(Cont.)
1.Every child loves Santa.
2.Everyone who loves Santa loves any reindeer.
3.Rudolph is a reindeer, and Rudolph has a red nose.
4.Anything which has a red nose is weird or is a clown.
5.No reindeer is a clown.
6.Scrooge does not love anything which is weird.
7.Scrooge is not a child.
Prepared by: Prof. Khushali B Kathiriya
123

122. Representation Simple Facts in logic
(Cont.)
1.Every child loves Santa.
∀x (CHILD(x) → LOVES(x, Santa))
2.Everyone who loves Santa loves any reindeer.
∀x (LOVES(x, Santa) → ∀y (REINDEER(y) → LOVES(x, y)))
3.Rudolph is a reindeer, and Rudolph has a red nose.
REINDEER(Rudolph) ∧REDNOSE(Rudolph)
4.Anything which has a red nose is weird or is a clown.
∀x (REDNOSE(x) → WEIRD(x) ∨CLOWN(x))
Prepared by: Prof. Khushali B Kathiriya
124

123. Representation Simple Facts in logic
(Cont.)
5.No reindeer is a clown.
¬ ∃x (REINDEER(x) ∧CLOWN(x))
6.Scrooge does not love anything which is weird.
∀x (WEIRD(x) → ¬ LOVES(Scrooge, x))
7.Scrooge is not a child.
¬ CHILD(Scrooge)
Prepared by: Prof. Khushali B Kathiriya
125

124. Representation Simple Facts in logic
(Cont.)
1.Anyone who buys carrots by the bushel owns either a rabbit or a grocery
store.
2.Every dog chases some rabbit.
3.Mary buys carrots by the bushel.
4.Anyone who owns a rabbit hates anything that chases any rabbit.
5.John owns a dog.
6.Someone who hates something owned by another person will not date
that person.
7.If Mary does not own a grocery store, she will not date John.
Prepared by: Prof. Khushali B Kathiriya
126

125. Representation Simple Facts in logic
(Cont.)
1.Anyone who buys carrots by the bushel owns either a rabbit or a grocery
store.
∀x (BUY(x) → ∃y (OWNS(x,y) ∧(RABBIT(y) ∨GROCERY(y))))
2.Every dog chases some rabbit.
∀x (DOG(x) → ∃y (RABBIT(y) ∧CHASE(x,y)))
3.Mary buys carrots by the bushel.
BUY(Mary)
4.Anyone who owns a rabbit hates anything that chases any rabbit.
∀x ∀y (OWNS(x,y) ∧RABBIT(y) → ∀z ∀w (RABBIT(w) ∧CHASE(z,w) → HATES(x,z)))
Prepared by: Prof. Khushali B Kathiriya
127

126. Representation Simple Facts in logic
(Cont.)
5.John owns a dog.
∃x (DOG(x) ∧OWNS(John,x))
6.Someone who hates something owned by another person will not date
that person.
∀x ∀y ∀z (OWNS(y,z) ∧HATES(x,z) → ¬ DATE(x,y))
7.(Conclusion) If Mary does not own a grocery store, she will not date John.
(( ¬ ∃x (GROCERY(x) ∧OWN(Mary,x))) → ¬ DATE(Mary,John))
Prepared by: Prof. Khushali B Kathiriya
128

127. Artificial Intelligence
Chap.4 Inference in First Order
Logic
Prepared by:
Prof. KhushaliB Kathiriya

128. Artificial Intelligence
Comparison between Propositional
Logic and First Order Logic
Prepared by:
Prof. KhushaliB Kathiriya

129. Comparison between Propositional
Logic and First Order Logic (Cont.)
Propositional Logic (PL) First Order Logic (FOL)
PL can not represent small worlds like
vacuum cleaner world.
FOL can very well represent small
world’s problems.
PL is a weak knowledge
representation language.
FOL is a strong way of representing
language.
PL uses propositions in which the
complete sentence is denoted by a
symbol.
FOL uses predicated which involve
constants, variables, functions,
relations.
PL can not directly represent
properties of individual entities or
relation between entities.
i.e., Hiral is short.
FOL can directly represent properties
of individual entities or relation
between entities.
i.e., Hiral is short.
Ans is: short (Hiral)
Prepared by: Prof. Khushali B Kathiriya
131

130. Comparison between Propositional
Logic and First Order Logic
Propositional Logic (PL) First Order Logic (FOL)
PL can not express specialization,
generalization, or patterns, etc.
i.e., all rectangle have 4 sides
FOL can express specialization,
generalization, or patterns, etc.
i.e., all rectangle have 4 sides
Ans. is: no of size(rectangle,4)
Foundation level language Higher level language
PL is not sufficiently expressive to
represent complex statements.
FOL is represent complex statements.
In PL meaning of the facts is context-
independent unlike natural language.
In FOL meaning of the sentences is
context dependent like natural
language.
Declarative in nature Derivative in nature
Prepared by: Prof. Khushali B Kathiriya
132

131. Artificial Intelligence
Inference in First Order Logic
Prepared by:
Prof. KhushaliB Kathiriya

132. Inference in First Order Logic
Theinferenceengineisthecomponentoftheintelligentsysteminartificial
intelligence,whichapplieslogicalrulestotheknowledgebasetoinfernew
informationfromknownfacts.Thefirstinferenceenginewaspartofthe
expertsystem.Inferenceenginecommonlyproceedsintwomodes,which
are:
1.Forwardchaining
2.Backwardchaining
Prepared by: Prof. Khushali B Kathiriya
134

133. Artificial Intelligence
Forward Chaining/ Resolution
Prepared by:
Prof. KhushaliB Kathiriya

134. 1. Forward Chaining
Forwardchainingisalsoknownasaforwarddeductionorforward
reasoningmethodwhenusinganinferenceengine.Forwardchainingisa
formofreasoningwhichstartwithatomicsentencesintheknowledgebase
andappliesinferencerules(ModusPonens)intheforwarddirectionto
extractmoredatauntilagoalisreached.
TheForward-chainingalgorithmstartsfromknownfacts,triggersallrules
whosepremisesaresatisfied,andaddtheirconclusiontotheknownfacts.
Thisprocessrepeatsuntiltheproblemissolved.
Forwardchainingiscalledasadatadriveninferencetechnique.
Prepared by: Prof. Khushali B Kathiriya
136

135. 1. Forward Chaining (Cont.)
PropertiesofForward-Chaining:
Itisadown-upapproach,asitmovesfrombottomtotop.
Itisaprocessofmakingaconclusionbasedonknownfactsordata,by
startingfromtheinitialstateandreachesthegoalstate.
Forward-chainingapproachisalsocalledasdata-drivenaswereach
tothegoalusingavailabledata.
Forward-chainingapproachiscommonlyusedintheexpertsystem,
suchasCLIPS,business,andproductionrulesystems.
Prepared by: Prof. Khushali B Kathiriya
137

136. 1. Forward Chaining / Resolution
(Cont.)
Example:
If it is raining then, we will take umbrella.
Data: It is raining
Decision: we will take umbrella
That’s means we already known that it’s raining that’s why it decided to
take umbrella.
Prepared by: Prof. Khushali B Kathiriya
138
Data
Decision

137. 1. Forward Chaining / Resolution
(Cont.)
Facts:
1.It is a crime for an American to sell weapons to enemy of America.
2.Country Nono is an enemy of America.
3.Nono has a some missiles.
4.All of the missiles were sold to Nono by colonel west.
5.Missiles are weapons.
6.Colonel west is American.
We have prove that west is a criminal.
Prepared by: Prof. Khushali B Kathiriya
139

138. 1. Forward Chaining / Resolution
(Cont.)
Facts conversion into FOL:
1.American (X) ∧weapon(Y) ∧sells (X,Y,Z) ∧enemy(Z, America) →
Criminal(X)
2.Enemy (Nono, America)
3.Owns ( Nono, X), Missile (X)
4.Missile (X) ^ owns (Nono, X)→Sell (West, X, Nono)
5.Missile (X) →Weapon (x)
6.American (West)
Prepared by: Prof. Khushali B Kathiriya
140

139. 1. Forward Chaining / Resolution
(Cont.)
Forward chaining proof:
STEP: 1
Prepared by: Prof. Khushali B Kathiriya
141
American (West) Missiles (X) Owns (Nono, X)
Enemy (Nono,
America)

140. 1. Forward Chaining / Resolution
(Cont.)
Forward chaining proof:
STEP: 2 apply rule number 4 and 5
4. Missile (X) ^ owns (Nono, X)→Sell (West, X, Nono)
5. Missile (X) →Weapon (x)
Prepared by: Prof. Khushali B Kathiriya
142

141. 1. Forward Chaining / Resolution
(Cont.)
Prepared by: Prof. Khushali B Kathiriya
143
American (West) Missiles (X) Owns (Nono, X)
Enemy (Nono,
America)
Weapon (X) Sell (West, X, Nono)
5
4

142. 1. Forward Chaining / Resolution
(Cont.)
Forward chaining proof:
STEP: 3 apply rule number 1
1. American (X) ∧weapon(Y) ∧sells (X,Y,Z) ∧enemy(Z, America) →
Criminal(X)
Prepared by: Prof. Khushali B Kathiriya
144

143. 1. Forward Chaining / Resolution
(Cont.)
Prepared by: Prof. Khushali B Kathiriya
145
American (West) Missiles (X) Owns (Nono, X)
Enemy (Nono,
America)
Weapon (X) Sell (West, X, Nono)
5
4
Criminal (West)
1

144. Artificial Intelligence
Backward Chaining/ Resolution
Prepared by:
Prof. KhushaliB Kathiriya

145. 2. Backward Chaining/ Resolution
Backward-chainingisalsoknownasabackwarddeductionorbackward
reasoningmethodwhenusinganinferenceengine.Abackwardchaining
algorithmisaformofreasoning,whichstartswiththegoalandworks
backward,chainingthroughrulestofindknownfactsthatsupportthegoal.
Prepared by: Prof. Khushali B Kathiriya
147
Decision
Data

146. 2. Backward Chaining/ Resolution
(Cont.)
Properties of backward chaining:
It is known as a top-down approach.
Backward-chaining is based on modus ponens inference rule.
In backward chaining, the goal is broken into sub-goal or sub-goals to
prove the facts true.
It is called a goal-driven approach, as a list of goals decides which rules
are selected and used.
Backward -chaining algorithm is used in game theory, automated
theorem proving tools, inference engines, proof assistants, and various
AI applications.
The backward-chaining method mostly used adepth-first
searchstrategy for proof.
Prepared by: Prof. Khushali B Kathiriya
148

147. 2. Backward Chaining/ Resolution
(Cont.)
Facts:
1.It is a crime for an American to sell weapons to enemy of America.
2.Country Nono is an enemy of America.
3.Nono has a some missiles.
4.All of the missiles were sold to Nono by colonel west.
5.Missiles are weapons.
6.Colonel west is American.
We have know that west is a criminal.
Prepared by: Prof. Khushali B Kathiriya
149

148. 2. Backward Chaining/ Resolution
(Cont.)
Facts conversion into FOL:
1.American (X) ∧weapon(Y) ∧sells (X,Y,Z) ∧enemy(Z, America) →
Criminal(X)
2.Enemy (Nono, America)
3.Owns ( Nono, X), Missile (X)
4.Missile (X) ^ owns (Nono, X)→Sell (West, X, Nono)
5.Missile (X) →Weapon (x)
6.American (West)
Prepared by: Prof. Khushali B Kathiriya
150

149. 2. Backward Chaining/ Resolution
(Cont.)
Backward chaining proof:
STEP: 1 Take conclusion (leaf node)
Prepared by: Prof. Khushali B Kathiriya
151
Criminal (West)

150. 2. Backward Chaining/ Resolution
(Cont.)
Backward chaining proof:
STEP: 2 Apply 1
st
rule
Prepared by: Prof. Khushali B Kathiriya
152
Criminal (West)
American (West) Missiles (X) Sell (West, X, Z)
Enemy (Nono,
America)
1

151. 2. Backward Chaining/ Resolution
(Cont.)
Backward chaining proof:
STEP: 3 Apply rules
Prepared by: Prof. Khushali B Kathiriya
153

152. 2. Backward Chaining/ Resolution
(Cont.)
Prepared by: Prof. Khushali B Kathiriya
154
Criminal (West)
American (West) Weapon (X) Sell (West, X, Z)
Enemy (Nono,
America)
1
Missiles (X)Owns (Nono, X)Missiles (X)

153. Artificial Intelligence
Unification Algorithm
Prepared by:
Prof. KhushaliB Kathiriya

154. Unification Algorithm
Algorithm Unify(L1,L2):
1.If L1 and L2 is a variable or constant then,
a.If L1 and L2 are identical return NIL,
b.Else if L1 is a variable, then if L1 occurs in L2 then return fail, else return { (L1/L2) }
c.Else if L2 is a variable, then if L2 occurs in L1 then return fail, else return { (L2/L1) }
d.Else return fail
2.If the initial predicate symbols in L1 and L2 are identical, then return Fail
3.If L1 and L2 have different number of arguments, then fails
a.i.e., P(L1,L2) and P(L1,L2,L3)
4.Set SUBST to nil.
5.Loop (apply for all variable/constant)
6.Return SUBST.
Prepared by: Prof. Khushali B Kathiriya
156

155. Unification Example
Unificationisallaboutmakingtheexpressionslookidentical.So,forthe
givenexpressionstomakethemlookidenticalweneedtodosubstitution.
(x,y)=(2,3)
Sowecansaylike,
x=2,{2forX}
y=3{3fory}
P(x,F(y))=P(a,F(g(z))
Inourcase,P(x,F(y))andP(a,F(g(z))
x=a(aforx)
y=g(z)(g(z)fory)
[a/x,g(z)/y]
Prepared by: Prof. Khushali B Kathiriya
157

156. Unification Example(Cont.)
Food (Peanuts) and Food (x)
So here we can say like this,
Peanuts for X
{X / Peanuts}
Like (Ravi, P) and like (Ravi, Apple)
So here we can say like this,
Apple for P
{P / Apple)
Prepared by: Prof. Khushali B Kathiriya
158

157. Artificial Intelligence
Resolution
Prepared by:
Prof. KhushaliB Kathiriya

158. Resolution
Resolutionisused,iftherearevariousstatementsaregiven,andweneed
toproveaconclusionofthosestatements.Unificationisakeyconceptin
proofsbyresolutions.Resolutionisasingleinferencerulewhichcan
efficientlyoperateontheconjunctivenormalformorclausalform.
Prepared by: Prof. Khushali B Kathiriya
160

159. Conversion from FOL Clausal Normal
Form (CNF)
StepsforResolution:
1.ConversionoffactsintoFOL.
2.ConvertFOLtoCNF
A.Eliminationofimplication
Eliminateall”→”sign
ReplaceP→Qwith~PVQ
B.Distributenegations
Replace~~PwithP
Replace~(PVQ)with~P^~Q(pVQ)→R
Prepared by: Prof. Khushali B Kathiriya
161

160. Conversion from FOL Clausal Normal
Form (CNF) (Cont.)
2.ConvertFOLtoCNF.(Cont.)
C.Eliminateexistentialquantifiersbyreplacingwithskolemconstantsor
skolemfunction
∀X∃Y((P1(X,Y)v(P2(X,Y)))≡∀X((P1(X,F(Y))v(P2(X,F(Y)))
D.Rename variables/usestandardvariabletoavoidduplicate
quantifiers.
E.Dropalluniversalquantifiers.
(P1(X,F(Y))v(P2(X,F(Y))
Prepared by: Prof. Khushali B Kathiriya
162

161. Conversion from FOL Clausal Normal
Form (CNF) (Cont.)
3.Negatethestatementwhichneedstoprove(proofby
contradiction)
Inthisstatement,wewillapplynegationtotheconclusionstatements,
whichwillbewrittenas
¬likes(John,Peanuts)
4.DrawResolutiongraph
Nowinthisstep,wewillsolvetheproblembyresolutiontreeusing
substitution.
Prepared by: Prof. Khushali B Kathiriya
163

162. Conversion from FOL Clausal Normal
Form (CNF) (Cont.)
Facts:
1.It is a crime for an American to sell weapons to enemy of America.
2.Country Nono is an enemy of America.
3.Nono has a some missiles.
4.All of the missiles were sold to Nono by colonel west.
5.Missiles are weapons.
6.Colonel west is American.
Prove: We have know that west is a criminal.
Prepared by: Prof. Khushali B Kathiriya
164

163. Conversion from FOL Clausal Normal
Form (CNF) (Cont.)
Step 1: Convert English to FOL
1.American (X) ∧weapon(Y) ∧sells (X,Y,Z) ∧enemy(Z, America) →
Criminal(X)
2.Enemy (Nono, America)
3.Owns ( Nono, X), Missile (X)
4.Missile (X) ^ owns (Nono, X)→Sell (West, X, Nono)
5.Missile (X) →Weapon (x)
6.American (West)
Prepared by: Prof. Khushali B Kathiriya
165

164. Conversion from FOL Clausal Normal
Form (CNF) (Cont.)
Step 2: Remove →sign from the FOL
1.American (X) ∧weapon(Y) ∧sells (X,Y,Z) ∧enemy(Z, America) →Criminal(X)
~(American (X) ∧weapon(Y) ∧sells (X,Y,Z) ∧enemy(Z, America)) VCriminal(X)
Apply ~sign in whole sentence ,
~American (X) V ~weapon(Y) V ~sells (X,Y,Z) V ~enemy(Z, America) V Criminal(X)
2.Enemy (Nono, America)
3.Owns ( Nono, X), Missile (X)
Owns ( Nono, X)
Missile (X)
Prepared by: Prof. Khushali B Kathiriya
166

165. Conversion from FOL Clausal Normal
Form (CNF) (Cont.)
Step 2: Remove ‘→’ sign from the FOL
4.Missile (X) ^ owns (Nono, X) →Sell (West, X, Nono)
~(Missile (X) ^ owns (Nono, X))VSell (West, X, Nono)
Apply ~sign in whole sentence ,
~Missile (X) V ~owns (Nono, X)V Sell (West, X, Nono)
5.Missile (X) →Weapon (x)
~Missile (X) VWeapon (x)
6.American (West)
7.Criminal (West)
Prepared by: Prof. Khushali B Kathiriya
167

166. Artificial Intelligence
Example for Conversion from FOL
Clausal Normal Form (CNF)
Prepared by:
Prof. KhushaliB Kathiriya

167. Example for Conversion from FOL
Clausal Normal Form (CNF)
Step 1: Convert English to FOL
Prepared by: Prof. Khushali B Kathiriya
169

168. Example for Conversion from FOL
Clausal Normal Form (CNF) (Cont.)
Step 2: Eliminate all implication (→) and rewrite
Prepared by: Prof. Khushali B Kathiriya
170

169. Example for Conversion from FOL
Clausal Normal Form (CNF) (Cont.)
Step 3: Move negation (¬)inwards and rewrite
Prepared by: Prof. Khushali B Kathiriya
171

170. Example for Conversion from FOL
Clausal Normal Form (CNF) (Cont.)
Step 4: Rename variables or standardize variables
Prepared by: Prof. Khushali B Kathiriya
172

171. Example for Conversion from FOL
Clausal Normal Form (CNF) (Cont.)
Step 5: Eliminate existential instantiation quantifier by elimination.
In this step, we will eliminate existential quantifier ∃, and this process is
known asSkolemization. But in this example problem since there is no
existential quantifier so all the statements will remain same in this step.
Prepared by: Prof. Khushali B Kathiriya
173

172. Example for Conversion from FOL
Clausal Normal Form (CNF) (Cont.)
Step 6: Drop Universal quantifiers
Prepared by: Prof. Khushali B Kathiriya
174

173. 175
Prepared by: Prof. KhushaliB Kathiriya
¬likes(John, Peanuts) ¬ food(x) V likes(John, x)
¬ food(Peanuts)
{Peanuts/x}
¬ eats(y, z) V killed(y) V food(z)
{Peanuts/z}
¬ eats(y, z) V killed(y) eats (Anil, Peanuts)
{Anil/y}
killed(Anil) ¬ alive(k) V ¬ killed(k)
¬ alive(Anil)
{Anil/k}
alive(Anil)
{ }
Step 7:
Draw Resolution graph