Transcript PPT

Logics for Data and Knowledge
Representation
Exercises: First Order Logics (FOL)
Originally by Alessandro Agostini and Fausto Giunchiglia
Modified by Fausto Giunchiglia, Rui Zhang and Vincenzo Maltese
Outline




2
Introduction
Syntax
Semantics
Reasoning Services
INTRODUCTION :: SYNTAX :: SEMANTICS :: REASONING SERVICES
Example of what we can express in FOL
constants
predicates
relations
Cita
Monkey
Eats
Hunts
Kimba
Simba
Near
3
Lion
Write in FOL the following NL sentences

“Fausto is a Professor”
Professor(fausto)

“There is a monkey”
∃x Monkey(x)

“There exists a dog which is black”
∃x (Dog(x)  Black(x))

4
“All persons have a name”
∀x (Person(x) → ∃y Name(x, y))
Write in FOL the following NL sentences

“The sum of two odd numbers is even”
∀x ∀y ( Odd(x)  Odd(y) → Even(Sum(x,y)) )

“A father is a male person having at least one child”
∀x ( Father(x) → Person(x)  Male(x)  ∃y hasChilden(x, y) )

“There is exactly one dog”
∃x Dog(x)  ∀x ∀y ( Dog(x)  Dog(y) → x = y )

“There are at least two dogs”
∃x ∃y ( Dog(x)  Dog(y)  (x = y) )
5
The use of FOL in mathematics

Express in FOL the fact that every natural number x multiplied by 1
returns x (identity):
∀x ( Natural(x)  (Mult(x, 1) = x) )

Express in FOL the fact that the multiplication of two natural
numbers is commutative:
∀x ∀y ( Natural(x)  Natural(y)  (Mult(x, y) = Mult(y, x)) )
6
Express the following problem in FOL

“There are 3 blocks A, B, C in a stack. Each block can be either black
or white. We know that the block A is on the bottom. A block is on the
top if there are no blocks above it. It is possible to be on top if and
only if the block is black”.

Constants = {a, b, c}

Predicates = {Black, White, Top}

Relations = {Above}
γ1 : ∃x Above(a,x)
γ2 : Top(y)  Black(y)  ∃z Above(z,y)
7
C
B
A
Satisfiability of the problem of blocks

Constants = {a, b, c}

Predicates = {Black, White, Top}

Relations = {Above}
C
B
A
γ1 : ∃x Above(a,x)
γ2 : Top(y)  Black(y)  ∃z Above(z,y)

Is Γ = {γ1, γ2} satisfiable? Is there any structure M = <D,I> and an
assignment a such that M ⊨ γ1 [a] and M ⊨ γ2 [a]?
D = {A, B, C}
I(a) = A
I(b) = B
I(Top) = {C}
I(c) = C
I(Black) = {A, C}
I(White) = {B}
I(Above) = {<B,A>, <C,B>}
Ia(y) = a(y) = C
NOTE: we can assign a different color to A and B. y is free.
8
Entailment

Let be  a set of FO- formulas, γ a FO- formula, we say that
⊨γ
(to be read  entails γ)
iff for all the structures M and assignments a,
if M ⊨  [a] then M ⊨ γ [a].
9
Entailment


Given:
α : ∀x ∀y ∃z (p(x, y) → (p(x, z)  p(z, y)))
β : ∀x ∀y (p(x, y)→ ∃z (p(x, z)  p(z, y)))
Does α ⊨ β?
Yes, because in α we can put ∃z inside:
∀x ∀y (∃z p(x, y) → ∃z (p(x, z)  p(z, y)))
z is not in the scope of ∃z p(x, y) and therefore we obtain β
10
Entailment

For all formulas of the form p(x, y):
1. Is ∃x∃y p(x, y) ⊨ ∃y∃x p(x, y)?
2. Is ∃x∀y p(x, y) ⊨ ∀y∃x p(x, y)?
3. Is ∀x∃y p(x, y) ⊨ ∃y∀x p(x, y)?
If no provide a counterexample.
Assume p(x, y) is x  y.
(1) Yes. The two formulas both says that there are at least two objects which
are related via p.
(2) Yes. The first formula says that there is an x such that for all y we have x
 y. We can take x = 0. The second formula says that for all y there exist an
x such that x  y. x = 0 is fine again.
(3) In this case is No. The first formula says that for all x there exist a y such
that x  y. We can take y = Succ(x). The second formula says that there
exists a y such that for all x we have x  y. We should take y = +.
11
Validity

Is it possible to prove that:
⊨ ∀x (Person(x)  Male(x)) [a] where D = {a, b, c}
We have only 3 possible assignments a(x) = a, a(x) = b, a(x) = c
We can translate it as follows:
P: (Person(a)  Male(a))  (Person(b)  Male(b)) 
(Person(c)  Male(c))
P: (Person(a)  Male(a))  (Person(b)  Male(b)) 
(Person(c)  Male(c))
P: (Person-a  Male-a)  (Person-b  Male-b) 
(Person-c  Male-c)
We check that DPLL(P) returns false.
12