Transcript Dia 1

Distributed
knowledge & beliefs
Lennart v. Luijk
Tijs Zwinkels
Jeroen Kuijpers
Jelle Prins
Overview

Recapitulation


Proving a system
Implicit knowledge

Message logic (ML)
Belief
 Discussion

Recapitulation

Commonly used symbols


├ (single flubber) used for axiom systems(K)
╞ (double flubber) used for world models(K)
s2

Seriality
s3
s1
s2

Euclidicity:
s1
s3
Proving a system

You prove a System S by proving:

S├ φ  M╞ φ

Soundness

Completeness
Soundness

Definition
Let S be an axiom system for epistemic formulas, and let
M be a class of Kripke models. Then S is called sound
with respect to M, if S├ φ => M ╞ φ
“Everything that can be proven with
the axiom system is actually true.”
Completeness

Definition
Let S be an axiom system for epistemic formulas, and let
M be a class of Kripke models. Then S is called complete
with respect to M, if M ╞ φ => S├ φ
“Everything that actually is true
can be proven with the axiom system”
Implicit knowledge (§2.3)

(M,s)╞ Iφ  (M,t)╞ φ for all t such that (s,t) є R1∩
… ∩ Rm

If φ is true in every world which can be reached
by all agent from the current world w1, then φ is
implicit knowledge in w1 ( (M,w1)╞ Iφ )

(A11) Kiφ  Iφ (i=1,…,m)
Implicit knowledge (§2.3)
Distributed Knowledge:

R4:
( 1  ...   m )  
( K1 1  ...  K m m )  I
Implicit knowledge (§2.3)
Distributed Knowledge:
(M,s)╞ Iφ (M,t)╞ φ for all t such that (s,t) є R1∩ … ∩ Rm
You are here
W2
p,q
R1,R2
W1
R1
p,~q
R2
~p, ~q
<M,w1> ╞ K1p
<M,w1> ╞ K2(pq)
<M,w1> ╞ Iq
W3
(and also Ip)
Implicit knowledge (§2.3)

In normal human language:

Iφ : ‘A clever man knows φ’ such as a detective

If one agent knows a b and another knows a
then together they know b.

Compare this to C : ‘Any fool knows φ’

Compare this to Ki : ‘Person i knows φ’
Examples

Distributed knowledge:

Universe Background radiation:
• Arno Penzias and Robert Wilson have
noise in their satellite dish. Thinks this is
because of ‘white dielectric material’ (bird
droppings)
• This radiation has been predicted years
earlier by George Gamow, but didn’t have
the instruments to measure the radiation.
Implicit knowledge (§2.3)
Some axioms and systems with I
Axioms:
 (A11) Kiφ  Iφ
(i=1,…,m)
 (R4)
(  ...   )  
1
m
( K1 1  ...  K m m )  I
Systems:
 KI(m)= K(m) + (A11) + KI
 TI(m) = T(m) + (A11) + TI
 S4I(m) = S4(m) + (A11) + S4I
 S5I(m) = S5(m) + (A11) + S5I
Implicit knowledge (§2.3)
Proof:
 Soundness (A11):
Kip  Ip:
Suppose (M,s) |= p. If t is such that (s,t) є (R1 ^ .. ^ RN),
then ofcourse Rist, so (M,t) |= ip.

Mention Completeness
Message Logic
ML axiom is added to S5I(m)
 (ML) I  ( K   ...  K  )

1
m
“The axiom(ML) says that, if it is implicit knowledge that a
state is impossible, then the stronger formula is true that some
agent knows that the state is impossible.”
W2

Counter example:
~q
R1,R2
W1
<M,w1>╞ I~q
but also ~(K~q)
R1
q
R2
W3
q
Belief (§2.4)

(M,s)╞ Biφ  (M,t)╞ φ for all t with (s,t) є Ri
The escaped Knock-knock canary brought false
hope to many a lonely citizen
Knock
Knock!
© Gummbah
Come in!
Belief (§2.4)
s
Biφ



t
φ
(D) ¬Bi(┴)
(axiom: a knowledge base is not inconsistent)
Same as :


Ri
¬ Bi(φ ^ ¬φ)
Same as S5 but no (A3), instead we have (D)
KD45(m) = (R1)+(R2)+(A1)+(A2)+(D)+(A4)+(A5)
Belief (§2.4)

Proof soundness of KD45

We know that the canonical model Mc(KD45(m))
posesses accessibility relations Ric that are serial,
transitive and euclidian.

We may combine this with the observation that serial,
transitive and euclidian Kripke models are models for
(D), (A4) and (A5), respectively. For (A4) and (A5) we
know this already. Therefore, we only have to
consider the soundness of the Axiom (D).
Belief (§2.4)

Proof soundness of KD45

Suppose KD45(m) ╞ ¬Bi(┴). Then there would be an
KD45(m)-model M with a state s such that (M,s)╞ Bi┴. This
would mean that all Ri-successors of s would verify ┴,
which is only possible if s does not have any Ri
successor.

However, by seriality, we know that s does have them,
so our assumption, i.e. that KD45(m) ╞ ¬Bi(┴), must be
false.


Hence we have KD45(m) ╞ ¬Bi(┴).
Completeness possible to prove, not of interest here.
Belief (§2.4)
W2
R1
p
R1
W1
p
R2
W3
~p
<M,w1>╞ B1p
<M,w1>╞ B2¬p
R2
Discussion
Logical Omniscience (§2.5)

L01-L010 given, give criticism on L05-L09
Knowledge & Belief (§2.13)
“logics gone bad”

Combining knowledge & beliefs (axiom system KL)

Both sound systems

Both systems have axioms that are good, but not
watertight

Combination of the two shows the flaws in the axioms

Result: Wrong example: 2.13.6


T4: Kip ↔ BiKip
Is this a valid theorem in KL?
Proof: Ki φ  BiKi φ
1) KL(i) ├ Kiφ  KiKiφ
(A4)
2) KL(i) ├ Kiφ  Biφ
(KL14)
3) KL(i) ├ (Kiφ  Biφ)  (KiKiφ  BiKiφ)
(A1)
4) KL(i) ├ KiKiφ  BiKiφ
(MP 2,3)
5) KL(i) ├ (Kiφ  KiKiφ)  (Kiφ  BiKiφ)
(HS short)
6) KL(i) ├ Kiφ  BiKiφ
(MP 4,5)
Short proof: BiKi φ  Ki φ
1) KL(i) ├ BiKiφ  ¬Bi¬Kiφ
(D “¬Bi(┴)” in its form ¬(Biφ ^ Bi¬φ) and prop. logic)
2) KL(i) ├ ¬Bi¬Kiφ  ¬Ki¬Kiφ
(KL14 “Kiφ  Biφ” and prop. logic: contraposition)
3) KL(i) ├ ¬Ki¬Kiφ  Kiφ
4) KL(i) ├ BiKiφ  Kiφ
(A5/KL3 “¬Kiφ  Ki¬Kiφ” and prop. logic: contraposition)
(from 1,2,3 by prop. logic: hypothetical syllogism)
Problems with K&B

Example:

Homeopathic dilution

Two persons live in axiom system KL (Hippie Tijs and
scientist Lennart)
Both take the same homeopathic medicine to releave
them from extreme fatigue due to too much work at their
university





Tijs believes he knows it works (BtKtw)
Lennart believes he knows it doesn’t work (BLKL¬w)
One dies and one survives.
Who will survive?
Problems with K&B

Another Example:


Two persons live in axiom system KD45(m) (Hippie Tijs
and scientist Lennart)
Both take the same homeopathic medicine to releave
them from extreme fatigue due to too much work at
their university

Tijs believes he knows it works (BtKtw)
Lennart believes he knows it doesn’t work (BLKL¬w)

What happens now?

FIN
Full Proof of: BiKip  Kip
To prove: BiKip  Kip
1) KL(i) ├ ¬Bi(┴)
2) KL(i) ├ ¬Bi(┴)  ¬(Biφ ^ Bi¬φ)
3) KL(i) ├ ¬(Biφ ^ Bi¬φ)
4) KL(i) ├ ¬(Biφ ^ Bi¬φ)  ¬(BiKiφ ^ Bi¬Kiφ)
5) KL(i) ├ ¬(BiKiφ ^ Bi¬Kiφ)
6) KL(i) ├ ¬(BiKiφ ^ Bi¬Kiφ)  ¬BiKiφ V ¬Bi¬Kiφ
7) KL(i) ├ ¬BiKiφ V ¬Bi¬Kiφ
8) KL(i) ├ (¬BiKiφ V ¬Bi¬Kiφ)  (BiKiφ  ¬Bi¬Kiφ)
9) KL(i) ├ BiKiφ  ¬Bi¬Kiφ
10) KL(i) ├ (Kiφ  Biφ)
11) KL(i) ├ (Kiφ  Biφ)  (Ki¬Kiφ  Bi¬Kiφ)
(D)
(A1)
(mp 1,2)
(A1)
(MP 3,4)
(A1)
(MP 5,6)
(A1)
(MP 7,8)
(KL 14)
(A1)
To prove: BiKip  Kip
9) KL(i) ├ BiKiφ  ¬Bi¬Kiφ
10) KL(i) ├ (Kiφ  Biφ)
11) KL(i) ├ (Kiφ  Biφ)  (Ki¬Kiφ  Bi ¬Kiφ)
12) KL(i) ├ (Ki¬Kiφ  Bi¬Kiφ)
13) KL(i) ├ ¬Bi¬Kiφ  ¬Ki¬Kiφ
14) KL(i) ├ ¬Kiφ  Ki¬Kiφ
15) KL(i) ├ ¬Ki¬Kiφ  Kiφ
| 16) KL(i) ├ BiKiφ
| 17) KL(i) ├ ¬Bi¬Kiφ
| 18) KL(i) ├ ¬Ki¬Kiφ
| 19) KL(i) ├ Kiφ
(MP 10,11)
(Contraposition of 12)
(A5/ KL3)
(Contraposition of 14)
(Assumption)
(MP 16, 9)
(MP 17, 13)
(MP 18, 15)
To prove: BiKip  Kip
| 16) KL(i) ├ BiKiφ
| 17) KL(i) ├ ¬Bi¬Kiφ
| 18) KL(i) ├ ¬Ki¬Kiφ
| 19) KL(i) ├ Kiφ
20) KL(i) ├ BiKiφ  Kiφ
(Assumption)
(MP 16, 9)
(MP 17, 13)
(MP 18, 15)
( intro 16-19)