Transcript Semantic Web

The Semantic Web –
WEEK 7: Logic, Reasoning
and Proof
You are here!
The “Layer Cake” Model –
[From Rector & Horrocks
Semantic Web cuurse]
Recap
• A good deal of the data on the Semantic Web will be in the form of
‘Conceptual Knowledge’. This has traditionally been captured by
diagrams in software engineering but for the web we need a precise,
symbolic language such as a logic language.
• Fundamental to logic languages is the idea of
INTERPRETATIONS - mapping predicates and constants to some
conceptualization of the world.
• A well formed sentence in Logic is called a Wff.
Wff2 LOGICALLY FOLLOWS from Wff1 if and only if every
interpretation that makes Wff1 true also makes Wff2 true.
Wff2 is LOGICALLY EQUIVALENT to Wff1 if and only if every
interpretation that makes Wff1 true also makes Wff2 true AND viceversa.
The Semantic Web
Reasoning


Processes (agents) working in the Semantic Web need
to be a good deal more flexible than normal programs they need to be able to negotiate, reason, plan etc
As well as being suited to capturing conceptual
knowledge, FOL is well known for its
AUTOMATED REASONING capabilities
In the next couple of weeks I will show you methods that
do automated reasoning with FOL
The Semantic Web
Interpretations revisited
Ax Ey R(y,x)
These 2
Interpretations
SATISFY this WFF
Greater_than
Mother_of
persons
WFF =
numbers
“Given any person there is
Someone who is their mother”
WFF =
NB Ax Ey … =/= Ey Ax
The Semantic Web
“Given any number there
Is some number greater than it”
Meaning of Quantifiers
Consider a Universe with individuals a,b,c,…
Ax P(x) = P(a) & P(b) & P(c) & ….
Ex P(x) = P(a) V P(b) V P(c) V ….
Ax Ay R(x,y) = R(a,a) & R(a,b) & R(a,c) &…
& R(b,a) & R(b,b) & R(b,c) & …
Ax Ey R(y,x) = Ey R(y,a) & Ey R(y,b) & Ey R(y,c) &…
=
(R(a,a) V R(b,a) V R(c,a) V …) &
(R(a,b) V R(b,b) V R(c,b) V …) &
(R(a,c) V R(b,c) V R(c,c) V …) & ….
The Semantic Web
Meaning of Connectives
The Connectives
&, V, ¬, =>, , <=
Get their meaning via propositional truth tables –

P
T
T
F
F
Q
T
F
F
T
PVQ
T
T
F
T
ETC
The Semantic Web
“Laws”
These are some well known equivalent FORMS in FOL
called laws ( De Morgans laws etc)
¬(P&Q)
¬(PVQ)
P=>Q
¬¬P
PQ
etc
=
=
=
=
=
¬P V ¬Q
¬P & ¬Q
¬P V Q
P
(P=>Q)&(Q=>P)
The Semantic Web
Quantifiers + Negation LAWS
1.
2.
¬ Ax P(x) = Ex ¬ P(x)
¬ Ex P(x) = Ax ¬ P(x)
Similary (and abstractly)
¬AE=EA¬
The Semantic Web
Example Revisited
“Every student is an academic.
Everybody who teaches an academic is an academic.
Jeff teaches Fred who is a student.”
What can we say about the statement “Jeff is an academic”
Translate to FOL:
S = student, D = academic, T = teaches
Ax S(x)=>D(x)
Ax (Ey T(x,y) & D(y)) => D(x)
S(Fred) T(Jeff,Fred)
Goal: D(Jeff)
How can we get agents to automatically deduce such
facts??
The Semantic Web
Another Example:
The Remote Agent Experiment
On May 17th and 21st 1999
NASA’s Deep Space 1
spacecraft was controlled
completely by its own
REASONING SYSTEM!
The Semantic Web
Another Example
Imagine Deep Space 1 travels to Mars and observes many things about
the Martians, including the fact that some seem very hostile towards
humans. Concrete observations are as follows:
(a) All green Martians have antennae.
(b) A Martian is friendly to humans if all of its children have antennae.
(c) A Martian is green if at least one of its parents is green.
On its way back from Mars the robot is hotly pursued
by a spacecraft containing green Martians only. Should the robot
suspect it is being attacked? Or can the robot reason with its observations
to answer the question: `Are all green Martians friendly?''
and hence avert an inter-planetary conflict.
The Semantic Web
Automated Deduction
Roughly, agents can be equipped with the ability
to deduce knowledge from observations by
automating Laws of Inference
A Law of Inference
 is a method for deducing wffs
 is SOUND if it only ever deduces wffs that also
logically follow.
The Semantic Web
Natural Deduction
The most famous Laws of Inference is known by
its Latin name “Modus Ponens”
From wffs OF THE FORM…
P(a)
Ax P(x)=>Q(x)
We can deduce the following Wff
Q(a)
Example: Socrates is a Man, All Men are Mortal
Deduce: Socrates is Mortal
The Semantic Web
Natural Deduction
Another is called “Modus Tollens”
From wffs OF THE FORM…
¬Q(a)
Ax P(x)=>Q(x)
We can deduce the following Wff
¬P(a)
Example: If a thing is smoking then it is on fire.
I am not on fire.
Deduce: I am not smoking
The Semantic Web
Unsound Deduction
Example: If a person is the murderer then that
person must have bloody hands.
The Butler has bloody hands.
Deduce: The Butler is the murderer
This is UNSOUND!!!
BH(butler)
Ax M(x)=>BH(x)
We can’t deduce anything from this!!
The Semantic Web
Summary
FOL is equipped with a form of reasoning
called deduction that can be automated
Next week I will cover ONE very efficient way to
automate deduction.
The Semantic Web