AI Lecture 6 (logical agents)

cse 412 - artificial intelligence, Lectures by Tajim Md. Niamat Ullah Akhund.

1. CSE 412: Artificial IntelligenceCSE 412: Artificial Intelligence
Fall 2018Fall 2018
Topic – 6: Topic – 6: Logical AgentsLogical Agents
Tajim Md. Niamat Ullah Akhund
Lecturer
Department of Computer Science and Engineering
Daffodil International University
Email: [email protected]

2. Knowledge-Based AgentsKnowledge-Based Agents
LogicLogic
Propositional Logic: A Very Simple LogicPropositional Logic: A Very Simple Logic
 SyntaxSyntax
 Semantics Semantics
 A simple knowledge baseA simple knowledge base
 InferenceInference
 Equivalence, validity, and satisfiabilityEquivalence, validity, and satisfiability

Topic ContentsTopic Contents

3. Architecture of a
Simple Intelligent Agent
Environment Agent
Sensors
Effectors
Reasoning &
Decisions Making
Model of World
(being updated)
List of
Possible Actions
Prior Knowledge
about the World
Goals/Utility
33

4. Knowledge Based Agent
Knowledge base:
–A knowledge base (abbreviated KB or kb) is a special
kind of database for knowledge management.
–A knowledge base is an information repository that
provides a means for information to be collected,
organized, shared, searched and utilized.
–The part of an expert system that contains the facts
and rules needed to solve problems.
–A collection of facts and rules for problem solving.
44

5. Knowledge Based Agent
The agent must be able to:
–represent states, actions, etc.
–incorporate new percepts
–update internal representation of world
–deduce hidden properties of world
–deduce appropriate actions
One of the core problems in developing an
intelligent agent is knowledge representation:
–how to represent knowledge
–how to reason using that knowledge
55

6. Knowledge Bases (KB)
A knowledge base:
–contains the domain-specific content for an agent
–is a set of representations of facts about the world
is a set of sentences in a formal language
Building the KB:
–learning: agent discovers what it knows
–telling: agent is given what it knows (declarative)
66

7. Knowledge Bases (KB)
Main actions of intelligent agent:
–TELL information to KB in the form of percept
–ASK KB what to do in the form of action
Answers should follow from KB.
Agent should not make things up!
An inference engine is composed of domain-
independent algorithms that are used to
determine what follows from the knowledge
base.
77

8. Knowledge Bases (KB)
View of agent (levels of abstraction):
–knowledge level:
what the agent knows at a high level
–logic level:
level of sentence encoding
–implementation level:
level that runs on the architecture,
detail of data structures and algorithms.
88

9. Algorithm
99

10. General Logic
The agent internally represents its
world/environment in its knowledge base.
The Sky is blue.
The sun is shining
representation in agent
world/environment
Sentences are representations in some language.
Facts are claims about the world that are true/false.
Sentences
Facts
1010

11. General Logic
Sentences represent facts in the world.
Sentences
Facts
representation in agent
world/environment
Meaning connects sentences to their facts.
Meaning / Interpretation
A sentence is true if what it represents is
actually the case in the current state of world.
Time flies.
1111

12. General Logic
repr.
world
Knowledge Conclusions
infer
follows
Facts
New Facts
Proper reasoning ensures that conclusions
inferred from the KB are consistent with reality.
That means they represent new facts that actually
follow from the original facts (represented by sentences
in the KB).
1212

13. Conclusions
General Logic
repr.
world
Knowledge
infer
Computers don't know the meaning.
A mechanical inference procedure is needed that derives
conclusions without needing to know the meaning of the
sentences.
Sentences New Sentences
entails
follows
Facts
New Facts
1313

14. Entailment
KB ╞ α
Knowledge base KB entails sentence α
if and only if α is true in all worlds where KB is true
1414

15. Entailment
KB ╞ α
Knowledge base KB entails sentence α
if and only if α is true in all worlds where KB is true
For example:
KB: "sky is blue" = true, "sun is shining" = true
entails α: "sky is blue and sun is shining" = true
–α represents a true fact
as long as facts represented in KB are true
–if the sky was actually cloudy then KB isn't the true world state
then α wouldn't represent a true fact
Entailment requires sentences in KB to be true.
1515

16. Logical Inference
Inference procedure can:
–generate new sentences α entailed by KB
–determine whether or not a given sentence α
is entailed by KB (i.e. prove α)
1616

17. General Logic
Logics are formal languages for representing
information from which conclusions can be drawn.
1717

18. General Logic
Logics are characterized by
what they commit to as "primitives".
Logic What Exists in WorldKnowledge States
Propositional facts true/false/unknown
First-Order facts, objects, relationstrue/false/unknown
Temporal facts, objects,
relations, times
true/false/unknown
Probability Theoryfacts degree of belief 0..1
Fuzzy degree of truth degree of belief 0..1
1818

19. Propositional Logic (PL) Basics
propositions: assertions about an aspect of a world
that can be assigned either a true or false value
–e.g. SkyIsCloudy, JimIsHappy
–True, False are propositions meaning true and false
1919

20. Logical Connectives of PL
Ø S negation (not)
 S
1
ÙS
2
conjunction (and)
S
1
and S
2
are conjuncts
S
1
ÚS
2
disjunction (or)
S
1
and S
2
are disjuncts
S
1
ÞS
2
implication/conditional (if-then)
S
1
is the antecedent/premise
S
2
is the consequent/conclusion
S
1
ÛS
2
equivalence/biconditional (if and only if)
2020

21. Syntax of PL
Models specify truth value for each proposition:
e.g. S
1
= true, S
2
= false
Rules for evaluating truth with respect to model m
ØS is true iff Sis false
S
1
ÙS
2
is true iff S
1
is true and S
2
is true
S
1
ÚS
2
is true iff S
1
is true or S
2
is true
S
1ÞS
2 is true iff S
1is true or S
2 is true
is true iff S
1
is false or S
2
is true
is false iff S
1
is false and S
2
is false
S
1
ÛS
2
is true iff S
1
ÞS
2
is true and S
2
ÞS
1
is true
Operator Precedence: (highest) Ø Ù Ú Þ Û (lowest)
2121

22. Truth Tables
A B C
falsefalsefalse
falsefalsetrue
falsetruefalse
falsetruetrue
truefalsefalse
truefalsetrue
truetruefalse
truetruetrue
Given n symbols,
2
n
possible combinations of
truth value assignments.
here each row is an interpretation
2222

23. Implication Truth Table
A B
falsefalse
falsetrue
truefalse
truetrue
AÞB
true
true
false
true
AÞB is equivalent to BÚ ØA
BÚ ØA
true
true
false
true
2323

24. Validity
A B C
falsefalsefalse
falsefalsetrue
falsetruefalse
falsetruetrue
truefalsefalse
truefalsetrue
truetruefalse
truetruetrue
A sentence is valid
if it's true in all interpretations:
P
1
Ú ØP
1
P
1
ÞP
1
(tautologies)
(i.e. its entire column is true)
AÚ ØA
true
true
true
true
true
true
true
true
2424

25. Satisfiability
A B C
falsefalsefalse
falsefalsetrue
falsetruefalse
falsetruetrue
truefalsefalse
truefalsetrue
truetruefalse
truetruetrue
A sentence is satisfiable
if it's true in some interpretations:
P
1
Ú ØP
2
P
2
ÞP
1
(i.e. its column is true and false)
AÚ ØB
true
true
false
false
true
true
true
true
2525

26. Unsatisfiability
A B C
falsefalsefalse
falsefalsetrue
falsetruefalse
falsetruetrue
truefalsefalse
truefalsetrue
truetruefalse
truetruetrue
A sentence is unsatisfiable
if it's true in no interpretations:
P
1
Ù ØP
1
(inconsistent/contradiction)
(i.e. its entire column is false)
CÙ ØC
false
false
false
false
false
false
false
false
2626

27. Inference Proof Methods
Model Checking:
–truth table enumeration
sound and complete for propositional logic
–heuristic search in model space
sound but incomplete
Application of Syntactic Operations
(i.e. Inference Rules):
–sound generation of new sentences from old
–could use inference rules as operators for search
2727

28. Inference by Enumeration
LET: KB = AÚC, BÚ ØC α = AÚB
DOES: KB ╞ α ?
A B C
falsefalsefalse
falsefalsetrue
falsetruefalse
falsetruetrue
truefalsefalse
truefalsetrue
truetruefalse
truetruetrue
RECALL: The computer
doesn't know the meaning
of the proposition symbols.
So all logically distinct cases
must be checked to prove that
a sentence can be derived
from a KB.
2828

29. Inference by Enumeration
LET: KB = AÚC, BÚ ØC α = AÚB
DOES: KB ╞ α ?
AÚCBÚ ØCKB
falsetruefalse
truefalsefalse
falsetruefalse
truetruetrue
truetruetrue
truefalsefalse
truetruetrue
truetruetrue
Rows where all of
sentences in KB
are true are the
models of KB
A B C
falsefalsefalse
falsefalsetrue
falsetruefalse
falsetruetrue
truefalsefalse
truefalsetrue
truetruefalse
truetruetrue
2929

30. Inference by Enumeration
LET: KB = AÚC, BÚ ØC α = AÚB
DOES: KB ╞ α ?
AÚCBÚ ØCKB
falsetruefalse
truefalsefalse
falsetruefalse
truetruetrue
truetruetrue
truefalsefalse
truetruetrue
truetruetrue
α is entailed by KB,
if all models of KB
are models of α,
i.e. all rows where
KB is true, α is true
A B C
falsefalsefalse
falsefalsetrue
falsetruefalse
falsetruetrue
truefalsefalse
truefalsetrue
truetruefalse
truetruetrue
AÚB
false
false
true
true
true
true
true
true
YES!
In other words:
KB Þα is valid.
KBÞα
true
true
true
true
true
true
true
true
3030

31. Inference by Enumeration
Though complete for PL, the proofs using this
enumeration grow exponentially in length as the
number of symbols increases.
There must be a better way.
Natural deduction is an inference procedure
that uses sound inference rules to derive new
sentences from the KB and any previously
derived sentences until the conclusion sentence
is derived.
3131

32. THANKS…

33. COURTESY:
Md. Tarek Habib
Assistant Professor
Daffodil International
University

34. ********** ********** If You Need Me ********** **********
Mail: [email protected]
Website: https://www.tajimiitju.blogspot.com
ORCID: https://orcid.org/0000-0002-2834-1507
LinkedIn: https://www.linkedin.com/in/tajimiitju
ResearchGate: https://www.researchgate.net/profile/Tajim_Md_Niamat_Ullah_Akhund

YouTube: https://www.youtube.com/tajimiitju?sub_confirmation=1
SlideShare: https://www.slideshare.net/TajimMdNiamatUllahAk
Facebook: https://www.facebook.com/tajim.mohammad
GitHub: https://github.com/tajimiitju
Google+: https://plus.google.com/+tajimiitju
Gmail: [email protected]
Twitter: https://twitter.com/Tajim53
Thank you
Tajim Md. Niamat Ullah AkhundTajim Md. Niamat Ullah Akhund