jurusan teknik informatika –universitas widyatama · pdf file2/28/2012 if-utama 1...
TRANSCRIPT
2/28/2012
IF-UTAMA 1
Jurusan Teknik Informatika Universitas Widyatama
IF-UTAMA 1
Reasoning (Proposional Logic)
Pertemuan : 5
Dosen Pembina :
Sriyani Violina
Danang Junaedi
IF-UTAMA 2
Deskripsi
Reasoning
Propositional logic
Problems with propositional logic
Overview
IF-UTAMA 3
Pertemuan ini mempelajari bagaimana
memecahkan suatu masalah dengan teknik
reasoning.
Metode reasoning yang dibahas pada
pertemuan ini adalah propositional logic
Deskripsi
IF-UTAMA 4
Representations are Models of the world
If we are going to create programs that are intelligent, then we need to figure out how to represent models of the world
An important aspect of an AI agent is its model of the world
As humans, we carry sophisticated models of the world in our heads
They allow us to predict certain things about the future, play scenarios though in our heads to see what might happen, and not be constantly surprised by everything we see
2/28/2012
IF-UTAMA 2
IF-UTAMA 5
The Role of a Model
Represent the environment
Provide a structure for the assimilation of new knowledge
Be able to change in the light of new evidence, but not too readily
Dry run without the need for sensor input or actual actuator output
Be able to generate new facts that have not been sensed from those that have
IF-UTAMA 6
Reasoning
Definisi : Teknik menyelesaikan masalah dengan cara merepresentasikan masalah ke dalam basis pengetahuan (knowledge base) menggunakan logic atau bahasa formal
Metode
Untuk masalah yang memiliki kepastian
Proportional Logic
First Order Logic/Predicate Calculus
Untuk masalah yang tidak memiliki kepastian
Fuzzy Logic
IF-UTAMA 7
Perbedaan Reasoning dengan
Searching
Searching
Masalah direpresentasikan dalam state dan ruang masalah,
Solusi ditentukan / dihasilkan dengan menggunakan strategi searching
Reasoning
Masalah direpresentasikan dalam basis pengetahuan dan
Solusi ditentukan / dihasilkan dengan melakukan proses penalaran
IF-UTAMA 8
Logic
Contrariwise, continued Tweedledee, if it
was so, it might be, and if it were so, it would
be; but as it isnt, it aint. Thats logic!
Lewis Carroll
2/28/2012
IF-UTAMA 3
IF-UTAMA 9
What is a logic?
A formal language Syntax what expressions are legal (well-formed)
Semantics what legal expressions mean
in logic the truth of each sentence with respect to each possible
world.
E.g the language of arithmetic X+2 >= y is a sentence, x2+y is not a sentence
X+2 >= y is true in a world where x=7 and y =1
X+2 >= y is false in a world where x=0 and y =6
IF-UTAMA 10
Logic consists of a
representation
Logical constants: true, false
Proposition symbols: P, Q, R, ...
Logical connectives: & (or ^), , , ,
Parentheses: ( )
Propositional logic is an extremely simple
representation
IF-UTAMA 11
Models
Logicians typically think in terms of models,
which are formally structured worlds with
respect to which truth can be evaluated.
m is a model of a sentence if is true in m
M() is the set of all models of
IF-UTAMA 12
Propositional Logic
One way to represent or model the world is propositional logic.
It can reason about such logical implications, we introduce Propositional Logic (PL).
It allows us
to express simple truth facts like I have money or I have an iPod,
to express logical statements like If I have money then I have an iPod, and
to draw conclusions like If I have money and (if I have money then I have an iPod) then I have an iPod.
2/28/2012
IF-UTAMA 4
IF-UTAMA 13
Propositional logic (PL)
A simple language useful for showing key ideas and
definitions
User defines a set of propositional symbols, like P and Q.
User defines the semantics of each propositional symbol:
P means It is hot
Q means It is humid
R means It is raining
A sentence (well formed formula) is defined as follows:
A symbol is a sentence
If S is a sentence, then S is a sentence
If S is a sentence, then (S) is a sentence
If S and T are sentences, then (S T), (S T), (S T), and (S T) are sentences
A sentence results from a finite number of applications of the above rules
IF-UTAMA 14
Semantics
A proposition symbol can mean anything at all. The logical system has no understanding of its meaning.
The semantics of propositional logic specifies the meaning of the logical connectives and how they combine propositions.
A truth table can be used to specify the semantics of the logical
IF-UTAMA 15
Propositional Logic
Represents facts as being either true or false
Formally represented by a letter, e.g. P or Q These symbols can represent whole propositions such as Elvis is alive.
Actually refer to facts about the environment, e.g. the speed limit in town is 30mph
Single facts can be combined into sentences using Boolean operators such as (^,v )
These sentences, if true, can become facts in the Knowledge Base (KB).
A KB is said to entail a sentence if it is true in the KB
IF-UTAMA 16
Propositional logic
Logical constants: true, false
Propositional symbols: P, Q, S, ... (atomic sentences)
Wrapping parentheses: ( )
Sentences are combined by connectives:
...and [conjunction]
...or [disjunction]
...implies [implication / conditional]
..is equivalent [biconditional]
...not [negation] Literal: atomic sentence or negated atomic sentence
2/28/2012
IF-UTAMA 5
IF-UTAMA 17
Syntax rules for propositional
logic The constants true and false are propositions by
themselves.
A proposition symbol such as P or Q is a proposition by itself.
Wrapping parentheses around a proposition produces proposition.
A proposition can be formed by using a logical connective to combine two propositions.
Constants or proposition symbols by themselves make atomic propositions. Propositions containing a connective are called complex propositions.
IF-UTAMA 18
Propositional Logic - Syntax
Sentences in Propositional Logic are defined in Backus-Naur Form (BNF):
A variable symbol (P,Q,R,), and the constantsTrue, False are correct sentences.
Given correct sentences a, b: , , , ( a) is a correct sentence. (negation)
(a ^ b) is a correct sentence. (conjunction)
(a b) is a correct sentence. (disjunction)
(a b) is a correct sentence. (implication)
(a b) is a correct sentence. (equivalence)
IF-UTAMA 19
A BNF grammar of sentences in
propositional logic
S := ;
:= |
;
:= "TRUE" | "FALSE" |
"P" | "Q" | "S" ;
:= "(" ")" |
|
"NOT" ;
:= "AND" | "OR" | "IMPLIES" |
"EQUIVALENT" ;
IF-UTAMA 20
Propositional Logic - Syntax
To avoid the excessive use of parentheses, we agree to use
the following convention on the order of precedence of
operators:
(highest), ^ , V , , (lowest)
Now, we can write
((((P) V (Q ^ R)) True) S)
as
P V Q ^ R True S
Even though these sentences are ambiguous in syntax
because of their unique semantics (to be defined next) we
allow sentences like P V Q V R, P ^ Q ^ R, and P Q
R. Sentences like P Q R are not allowed.
2/28/2012
IF-UTAMA 6
IF-UTAMA 21
Propositional Logic - Syntax
A model or instantiation to a sentence in
propositional logic is an assignment of truth
values to each variable:
For the sentence P Q ^ R True S
potential models are:
m1 = { P=true, Q=true, R=false, S=false }
m2 = { P=false, Q=true, R=false, S=true}
We write a|m to denote the evaluation of a
under model m.
IF-UTAMA 22
Examples of PL sentences
(P Q) R
If it is hot and humid, then it is raining
Q P
If it is humid, then it is hot
Q
It is humid.
A better way:
Ho = It is hot
Hu = It is humid
R = It is raining
IF-UTAMA 23
Truth tables
IF-UTAMA 24
Truth tables II
The five logical connectives:
A complex sentence:
2/28/2012
IF-UTAMA 7
IF-UTAMA 25
Models of complex sentences
IF-UTAMA 26
Inference rules
Logical inference is used to create new sentences that logically follow from a given set of predicate calculus sentences (KB).
An inference rule is sound if every sentence X produced by an inference rule operating on a KB logically follows from the KB. (That is, the inference rule does not create any contradictions)
An inference rule is complete if it is able to produce every expression that logically follows from (is entailed by) the KB. (Note the analogy to complete search algorithms.)
IF-UTAMA 27
Sound rules of inference
Here are some examples of sound rules of inference
A rule is sound if its conclusion is true whenever the premise is true
Each can be shown to be sound using a truth table
RULE PREMISE CONCLUSION
Modus Ponens A, A B B
And Introduction A, B A B
And Elimination A B A
Double Negation A A
Unit