149
L´ogicaEpistˆ emica e Mudan¸cas de Cren¸ cas Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013 - DCC - UFRJ Benevides: L´ogica Epistˆ emica e Mudan¸ cas de Cren¸cas DCC-13

L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

  • Upload
    others

  • View
    0

  • Download
    0

Embed Size (px)

Citation preview

Page 1: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Logica Epistemica e Mudancas de Crencas

Mario Benevides

Universidade Federal do Rio de JaneiroRio de Janeiro, Brasil

2013 - DCC - UFRJ

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 2: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Inteligencia Artificial

◮ ”Construir Sistemas Raciocinam como Humanos (???)”

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 3: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Inteligencia Artificial

◮ ”Construir Sistemas Raciocinam como Humanos (???)”

◮ Raciocınio ⇒ Conhecimento

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 4: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Inteligencia Artificial

◮ ”Construir Sistemas Raciocinam como Humanos (???)”

◮ Raciocınio ⇒ Conhecimento

◮ Como Representar o Conhecimento e Raciocinar sobre ele?

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 5: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Inteligencia Artificial

◮ ”Construir Sistemas Raciocinam como Humanos (???)”

◮ Raciocınio ⇒ Conhecimento

◮ Como Representar o Conhecimento e Raciocinar sobre ele?

◮ Logica

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 6: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Inteligencia Artificial

◮ ”Construir Sistemas Raciocinam como Humanos (???)”

◮ Raciocınio ⇒ Conhecimento

◮ Como Representar o Conhecimento e Raciocinar sobre ele?

◮ Logica

◮ Redes Neurais e etc

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 7: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Inteligencia Artificial

◮ ”Construir Sistemas Raciocinam como Humanos (???)”

◮ Raciocınio ⇒ Conhecimento

◮ Como Representar o Conhecimento e Raciocinar sobre ele?

◮ Logica

◮ Redes Neurais e etc

◮ Raciocınio ⇒ Conhecimento ⇒ Logica

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 8: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Roteiro

◮ Jogos e Quebra-Cabeca.

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 9: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Roteiro

◮ Jogos e Quebra-Cabeca.

◮ Logica Epistemica Multi-Agente.◮ Halpern, Fagin, Moses e Vardi

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 10: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Roteiro

◮ Jogos e Quebra-Cabeca.

◮ Logica Epistemica Multi-Agente.◮ Halpern, Fagin, Moses e Vardi

◮ Logicas Epistemicas Dinamicas.

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 11: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Roteiro

◮ Jogos e Quebra-Cabeca.

◮ Logica Epistemica Multi-Agente.◮ Halpern, Fagin, Moses e Vardi

◮ Logicas Epistemicas Dinamicas.

◮ Public Anouncement Logic

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 12: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Roteiro

◮ Jogos e Quebra-Cabeca.

◮ Logica Epistemica Multi-Agente.◮ Halpern, Fagin, Moses e Vardi

◮ Logicas Epistemicas Dinamicas.

◮ Public Anouncement Logic

◮ Action Models Logic

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 13: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Jogos e Quebra-Cabeca

◮ Cartas Russas (Russian Cards)

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 14: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Jogos e Quebra-Cabeca

◮ Cartas Russas (Russian Cards)

◮ Cem prisioneiros e uma Lampada

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 15: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Jogos e Quebra-Cabeca

◮ Cartas Russas (Russian Cards)

◮ Cem prisioneiros e uma Lampada

◮ Criancas com Lama na Testa

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 16: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Cartas Russas (Russian Cards)

◮ 3 Agentes: ana e beto e carla

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 17: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Cartas Russas (Russian Cards)

◮ 3 Agentes: ana e beto e carla

◮ 7 Cartas: {0, 1, 2, 3, 4, 5, 6}

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 18: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Cartas Russas (Russian Cards)

◮ 3 Agentes: ana e beto e carla

◮ 7 Cartas: {0, 1, 2, 3, 4, 5, 6}

◮ Distribuicao: 3 cartas para ana e beto e 1 para carla

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 19: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Cartas Russas (Russian Cards)

◮ 3 Agentes: ana e beto e carla

◮ 7 Cartas: {0, 1, 2, 3, 4, 5, 6}

◮ Distribuicao: 3 cartas para ana e beto e 1 para carla

◮ Objetivo: descobrir as cartas dos outros

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 20: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Cartas Russas (Russian Cards)

◮ 3 Agentes: ana e beto e carla

◮ 7 Cartas: {0, 1, 2, 3, 4, 5, 6}

◮ Distribuicao: 3 cartas para ana e beto e 1 para carla

◮ Objetivo: descobrir as cartas dos outros

◮ Regra: ana e beto podem se comunicar publicamente

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 21: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Cartas Russas (Russian Cards)

◮ 3 Agentes: ana e beto e carla

◮ 7 Cartas: {0, 1, 2, 3, 4, 5, 6}

◮ Distribuicao: 3 cartas para ana e beto e 1 para carla

◮ Objetivo: descobrir as cartas dos outros

◮ Regra: ana e beto podem se comunicar publicamente

◮ Ganha carla: se apos comunicacao ela descobre

◮ Ganha ana e beto: se apos comunicacao um deles descobremas nao carla

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 22: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Cartas Russas (Russian Cards) - Exemplo

◮ Distribuicao: ana ⇒ {0, 1, 2} e beto ⇒ {3, 4, 5} ecarla ⇒ {6}

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 23: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Cartas Russas (Russian Cards) - Exemplo

◮ Distribuicao: ana ⇒ {0, 1, 2} e beto ⇒ {3, 4, 5} ecarla ⇒ {6}

◮ Comunicacao 1: ana diz ”tenho 012 ou beto tem 012”ebeto diz ”tenho 345 ou ana tem 345”, bom ou ruim?

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 24: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Cartas Russas (Russian Cards) - Exemplo

◮ Distribuicao: ana ⇒ {0, 1, 2} e beto ⇒ {3, 4, 5} ecarla ⇒ {6}

◮ Comunicacao 1: ana diz ”tenho 012 ou beto tem 012”ebeto diz ”tenho 345 ou ana tem 345”, bom ou ruim?

◮ Ruim: carla ganha!!! /

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 25: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Cartas Russas (Russian Cards) - Exemplo

◮ Distribuicao: ana ⇒ {0, 1, 2} e beto ⇒ {3, 4, 5} ecarla ⇒ {6}

◮ Comunicacao 1: ana diz ”tenho 012 ou beto tem 012”ebeto diz ”tenho 345 ou ana tem 345”, bom ou ruim?

◮ Ruim: carla ganha!!! /

◮ Comunicacao 2: ana diz ”tenho 012 ou 034 ou 056 ou 135ou 246”, bom ou ruim?

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 26: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Cartas Russas (Russian Cards) - Exemplo

◮ Distribuicao: ana ⇒ {0, 1, 2} e beto ⇒ {3, 4, 5} ecarla ⇒ {6}

◮ Comunicacao 1: ana diz ”tenho 012 ou beto tem 012”ebeto diz ”tenho 345 ou ana tem 345”, bom ou ruim?

◮ Ruim: carla ganha!!! /

◮ Comunicacao 2: ana diz ”tenho 012 ou 034 ou 056 ou 135ou 246”, bom ou ruim?

◮ Bom: : ana e beto ganham!!! ,

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 27: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Cartas Russas (Russian Cards) - Exemplo

◮ Distribuicao: ana ⇒ {0, 1, 2} e beto ⇒ {3, 4, 5} ecarla ⇒ {6}

◮ Comunicacao 1: ana diz ”tenho 012 ou beto tem 012”ebeto diz ”tenho 345 ou ana tem 345”, bom ou ruim?

◮ Ruim: carla ganha!!! /

◮ Comunicacao 2: ana diz ”tenho 012 ou 034 ou 056 ou 135ou 246”, bom ou ruim?

◮ Bom: : ana e beto ganham!!! ,

◮ Como ana chegou a esta comunicacao???

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 28: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Cem prisioneiros e uma Lampada

◮ Inicio: Comunicado a todos os prisioneiros

◮ 100 prisioneiros estao numa sala◮ eles vao ser colocados numa cela sozinhos e sem comunicacao◮ eles vao ser escolhidos aleatoriamente um de cada vez para

uma sala de interrogatorio◮ nesta sala tem um interruptor que acende ou apaga uma

lampada◮ a lampada comeca apagada◮ um prisioneiro pode ser interrogado mais de uma vez

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 29: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Cem prisioneiros e uma Lampada

◮ Inicio: Comunicado a todos os prisioneiros

◮ 100 prisioneiros estao numa sala◮ eles vao ser colocados numa cela sozinhos e sem comunicacao◮ eles vao ser escolhidos aleatoriamente um de cada vez para

uma sala de interrogatorio◮ nesta sala tem um interruptor que acende ou apaga uma

lampada◮ a lampada comeca apagada◮ um prisioneiro pode ser interrogado mais de uma vez

◮ Objetivo: descobrir se todos ja foram interrogados.

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 30: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Cem prisioneiros e uma Lampada

◮ Inicio: Comunicado a todos os prisioneiros

◮ 100 prisioneiros estao numa sala◮ eles vao ser colocados numa cela sozinhos e sem comunicacao◮ eles vao ser escolhidos aleatoriamente um de cada vez para

uma sala de interrogatorio◮ nesta sala tem um interruptor que acende ou apaga uma

lampada◮ a lampada comeca apagada◮ um prisioneiro pode ser interrogado mais de uma vez

◮ Objetivo: descobrir se todos ja foram interrogados.

◮ Ruim: se errar todos morrem!!! /

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 31: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Cem prisioneiros e uma Lampada

◮ Inicio: Comunicado a todos os prisioneiros

◮ 100 prisioneiros estao numa sala◮ eles vao ser colocados numa cela sozinhos e sem comunicacao◮ eles vao ser escolhidos aleatoriamente um de cada vez para

uma sala de interrogatorio◮ nesta sala tem um interruptor que acende ou apaga uma

lampada◮ a lampada comeca apagada◮ um prisioneiro pode ser interrogado mais de uma vez

◮ Objetivo: descobrir se todos ja foram interrogados.

◮ Ruim: se errar todos morrem!!! /

◮ Bom: : se acertar, todos estao livres!!! ,

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 32: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Cem prisioneiros e uma Lampada

◮ Inicio: Comunicado a todos os prisioneiros

◮ 100 prisioneiros estao numa sala◮ eles vao ser colocados numa cela sozinhos e sem comunicacao◮ eles vao ser escolhidos aleatoriamente um de cada vez para

uma sala de interrogatorio◮ nesta sala tem um interruptor que acende ou apaga uma

lampada◮ a lampada comeca apagada◮ um prisioneiro pode ser interrogado mais de uma vez

◮ Objetivo: descobrir se todos ja foram interrogados.

◮ Ruim: se errar todos morrem!!! /

◮ Bom: : se acertar, todos estao livres!!! ,

◮ Como bolar uma estrategia para libertar todos???

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 33: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas brincando na lama;

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 34: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas brincando na lama;

◮ Pai chega e ve que algumas possuem lama na testa;

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 35: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas brincando na lama;

◮ Pai chega e ve que algumas possuem lama na testa;

◮ Crincas podem ver a lama na testas das outras mas nao napropria testa;

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 36: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas brincando na lama;

◮ Pai chega e ve que algumas possuem lama na testa;

◮ Crincas podem ver a lama na testas das outras mas nao napropria testa;

◮ Pai Anuncia:

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 37: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas brincando na lama;

◮ Pai chega e ve que algumas possuem lama na testa;

◮ Crincas podem ver a lama na testas das outras mas nao napropria testa;

◮ Pai Anuncia:

1. Tem pelo menos uma crianca c. lama!!!

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 38: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas brincando na lama;

◮ Pai chega e ve que algumas possuem lama na testa;

◮ Crincas podem ver a lama na testas das outras mas nao napropria testa;

◮ Pai Anuncia:

1. Tem pelo menos uma crianca c. lama!!!2. Alguem ja sabe se tem lama na testa???

...

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 39: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas brincando na lama;

◮ Pai chega e ve que algumas possuem lama na testa;

◮ Crincas podem ver a lama na testas das outras mas nao napropria testa;

◮ Pai Anuncia:

1. Tem pelo menos uma crianca c. lama!!!2. Alguem ja sabe se tem lama na testa???

...k. Alguem ja sabe se tem lama na testa???

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 40: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas brincando na lama;

◮ Pai chega e ve que algumas possuem lama na testa;

◮ Crincas podem ver a lama na testas das outras mas nao napropria testa;

◮ Pai Anuncia:

1. Tem pelo menos uma crianca c. lama!!!2. Alguem ja sabe se tem lama na testa???

...k. Alguem ja sabe se tem lama na testa???

◮ Quantos anuncios serao feitos ate que criancas c. lama

saibam que estao sujas?

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 41: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas n brincando na lama;

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 42: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas n brincando na lama;

◮ Tem k com lama na testa;

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 43: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas n brincando na lama;

◮ Tem k com lama na testa;

◮ Quantos anuncios serao feitos ate que criancas c. lama

saibam que estao sujas?

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 44: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas n brincando na lama;

◮ Tem k com lama na testa;

◮ Quantos anuncios serao feitos ate que criancas c. lama

saibam que estao sujas?

◮ Exemplos:

◮ n =3 e k=1 serao 1 anuncios;◮ n =3 e k=2 serao 2 anuncio;

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 45: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas n brincando na lama;

◮ Tem k com lama na testa;

◮ Quantos anuncios serao feitos ate que criancas c. lama

saibam que estao sujas?

◮ Exemplos:

◮ n =3 e k=1 serao 1 anuncios;◮ n =3 e k=2 serao 2 anuncio;

◮ Serao necessarios k anuncios!!!

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 46: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas n brincando na lama;

◮ Tem k com lama na testa;

◮ Quantos anuncios serao feitos ate que criancas c. lama

saibam que estao sujas?

◮ Exemplos:

◮ n =3 e k=1 serao 1 anuncios;◮ n =3 e k=2 serao 2 anuncio;

◮ Serao necessarios k anuncios!!!

◮ Por que?

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 47: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Modelando Conhecimento

◮ Agentes: ana e beto

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 48: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Modelando Conhecimento

◮ Agentes: ana e beto

◮ Carta contendo a informacao:

p = ”ana ganhou R$ 1,00”

¬p = ”ana nao ganhou R$ 1,00”

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 49: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Modelando Conhecimento

◮ Agentes: ana e beto

◮ Carta contendo a informacao:

p = ”ana ganhou R$ 1,00”

¬p = ”ana nao ganhou R$ 1,00”

◮ envelope lacrado e sobre a mesa

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 50: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Modelando Conhecimento

◮ Agentes: ana e beto

◮ Carta contendo a informacao:

p = ”ana ganhou R$ 1,00”

¬p = ”ana nao ganhou R$ 1,00”

◮ envelope lacrado e sobre a mesa

◮ O que ana e beto sabem?

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 51: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Modelando Conhecimento◮ Dois estados possıveis para ana e beto

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 52: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Modelando Conhecimento◮ Dois estados possıveis para ana e beto

◮ s1 = ”ana ganhou R$ 1,00”⇒ p◮ s2 = ”ana nao ganhou R$ 1,00”⇒ ¬p

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 53: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Modelando Conhecimento◮ Dois estados possıveis para ana e beto

◮ s1 = ”ana ganhou R$ 1,00”⇒ p◮ s2 = ”ana nao ganhou R$ 1,00”⇒ ¬p◮ ana e beto nao sabem se estao em s1 ou s2

s1 s2a, b

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 54: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Modelando ConhecimentoM = 〈S ,∼,V 〉:

◮ S = {s1, s2}◮ ∼a = {(s1, s2), (s1, s1), (s2, s1), (s2, s2)}◮ ∼b = {(s1, s2), (s1, s1), (s2, s1), (s2, s2)}◮ V (p) = {s1}

s1 s2a, ba, ba, b a, b s1 s2a, b

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 55: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Logica Epistemica - Linguagem

◮ Alfabeto◮ Φ conj. contavel de sımbolos prop.,◮ A conjunto finito de agentes,◮ ¬ e ∧ conectivos booleanos,◮ Ka uma modalidade para cada agente a.

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 56: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Logica Epistemica - Linguagem

◮ Alfabeto◮ Φ conj. contavel de sımbolos prop.,◮ A conjunto finito de agentes,◮ ¬ e ∧ conectivos booleanos,◮ Ka uma modalidade para cada agente a.

◮ Linguagem

ϕ ::= p | ⊤ | ¬ϕ | ϕ1 ∧ ϕ2 | Kaϕ

onde p ∈ Φ, a ∈ A.

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 57: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Modelando Conhecimento

s1 s2a, b

◮ Ana nao sabe p ⇒ ¬Kap

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 58: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Modelando Conhecimento

s1 s2a, b

◮ Ana nao sabe p ⇒ ¬Kap

◮ Ana sabe que Beto nao sabe p ⇒ Ka¬Kbp

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 59: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Modelando Conhecimento

s1 s2a, b

◮ Ana nao sabe p ⇒ ¬Kap

◮ Ana sabe que Beto nao sabe p ⇒ Ka¬Kbp

◮ Beto sabe que Ana sabe que Beto nao sabe p ⇒ KbKa¬Kbp

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 60: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Modelando Conhecimento

s1 s2a, b

◮ Ana nao sabe p ⇒ ¬Kap

◮ Ana sabe que Beto nao sabe p ⇒ Ka¬Kbp

◮ Beto sabe que Ana sabe que Beto nao sabe p ⇒ KbKa¬Kbp

◮ Por que as proposicoes sao verdadeiras na Estrutura?

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 61: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Modelando Conhecimento

s1 s2a, b

◮ Por que Ana nao sabe p em s1?⇒ s1 |= ¬Kap?

”Ana nao distingue s1 de s2, e s1 |= p e s2 |= ¬p”

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 62: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Modelando Conhecimento

s1 s2a, b

◮ Por que Ana nao sabe p em s1?⇒ s1 |= ¬Kap?

”Ana nao distingue s1 de s2, e s1 |= p e s2 |= ¬p”

◮ Por que Ana sabe (p ∨ ¬p) em s1?⇒ s1 |= Ka(p ∨ ¬p)?

”Ana nao distingue s1 de s2, e s1 |= (p ∨ ¬p) es2 |= (p ∨ ¬p)”

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 63: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Modelando Conhecimento

s1 s2a, b

◮ Por que Ana nao sabe p em s1?⇒ s1 |= ¬Kap?

”Ana nao distingue s1 de s2, e s1 |= p e s2 |= ¬p”

◮ Por que Ana sabe (p ∨ ¬p) em s1?⇒ s1 |= Ka(p ∨ ¬p)?

”Ana nao distingue s1 de s2, e s1 |= (p ∨ ¬p) es2 |= (p ∨ ¬p)”

◮ ”Ana sabe uma proposicao ϕ em um estado s1 (s1 |= Kaϕ), seem todos os estados que ela nao distingue de s1 ϕ everdadeira.”

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 64: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Semantica

◮ Um frame e um par F = (W ,∼a) onde

◮ W e um conjunto nao-vazio de estados;◮ ∼a e uma relacao binaria sobre W , para cada agente a

◮ Reflexiva

◮ Transitiva

◮ Simetrica

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 65: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Semantica

◮ Um frame e um par F = (W ,∼a) onde

◮ W e um conjunto nao-vazio de estados;◮ ∼a e uma relacao binaria sobre W , para cada agente a

◮ Reflexiva

◮ Transitiva

◮ Simetrica

◮ Um modelo e um par M = (F ,V ) onde◮ F = (W ,R) e um frame e◮ V e uma funcao de Φ no conjunto das partes de W , que faz

corresponder a todo sımbolo proposicional p ∈ Φ o conjuntode estados nos quais p e satisfeito, i.e., V : Φ 7−→ Pow(W ).

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 66: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Semantica

◮ Dada uma estrutura M = 〈S ,∼a,V 〉

M, s |= p iff s ∈ V (p)M, s |= ¬ϕ iff M, s 6|= ϕM, s |= ϕ ∧ ψ iff M, s |= ϕ e M, s |= ψM, s |= Kaϕ iff p/ todo t ∈ S : s ∼a t implica M, t |= ϕ

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 67: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Jogo de Cartas

◮ 3 Cartas: 0, 1 and 2,

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 68: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Jogo de Cartas

◮ 3 Cartas: 0, 1 and 2,

◮ 3 Jogadores ana, beto and carla,

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 69: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Jogo de Cartas

◮ 3 Cartas: 0, 1 and 2,

◮ 3 Jogadores ana, beto and carla,

◮ Cada jog. recebe 1 carta e nao sabe as cartas dos outros

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 70: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Jogo de Cartas

◮ 3 Cartas: 0, 1 and 2,

◮ 3 Jogadores ana, beto and carla,

◮ Cada jog. recebe 1 carta e nao sabe as cartas dos outros

◮ 0x , 1x , 2x , x ∈ {a, b, c} para: “jogador x tem carta 0, 1 or 2.

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 71: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Jogo de Cartas

◮ 3 Cartas: 0, 1 and 2,

◮ 3 Jogadores ana, beto and carla,

◮ Cada jog. recebe 1 carta e nao sabe as cartas dos outros

◮ 0x , 1x , 2x , x ∈ {a, b, c} para: “jogador x tem carta 0, 1 or 2.

◮ Estados: 012 e o estado onde a tem 0, b tem 1 e c tem 2

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 72: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Jogo de Cartas

Hexa1 = 〈S ,∼,V 〉:

◮ S = {012, 021, 102, 120, 201, 210}

◮ ∼a = {(012, 012), (012, 021), (021, 021), . . . }

◮ V (0a) = {012, 021}, V (1a) = {102, 120}, ...

201

102

012 021

210

120

a

a

a

b b

bc

c c

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 73: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Jogo de Cartas

201

102

012 021

210

120

a

a

a

b b

bc

c c

012 |= Ka(1b ∨ 2b)

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 74: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Jogo de Cartas - Exercıcios

1. 012 |= Ka(Kc1c ∨ Kc2c)

2. 012 |= Bc(1b ∧ Ka2a)

3. 012 |= ¬Ka(Kc1c ∧ Kb2b)

4. 012 |= Ka(0a ∧ Kb(1b ∧ Kc1c ))

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 75: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Axiomatizacao

◮ Axiomas

1. Todas as instancias das tautologias proposicionais,2. Ka(ϕ→ ψ) → (Kaϕ→ Kaψ),3. Kaϕ→ ϕ,4. Kaϕ→ KaKaϕ (+ introspection),5. ¬Kaϕ→ Ka¬Kaϕ (− introspection),

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 76: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Axiomatizacao

◮ Axiomas

1. Todas as instancias das tautologias proposicionais,2. Ka(ϕ→ ψ) → (Kaϕ→ Kaψ),3. Kaϕ→ ϕ,4. Kaϕ→ KaKaϕ (+ introspection),5. ¬Kaϕ→ Ka¬Kaϕ (− introspection),

◮ Regras de inferencia

M.P. ϕ,ϕ→ ψ/ψ U.G. ϕ/Kaϕ UB. ϕ/σϕonde σ e um mapa substituindo uniformemente formulas paravariaveis proposicionais.

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 77: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Logicas Epistemicas Dinamicas

◮ Acoes que mudam o estado epistemico do Agente

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 78: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Logicas Epistemicas Dinamicas

◮ Acoes que mudam o estado epistemico do Agente

◮ Acoes Publicas

”Todos os agentes percebem (sabem) o conteudo”Ex. Broadcast de uma mensagem

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 79: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Logicas Epistemicas Dinamicas

◮ Acoes que mudam o estado epistemico do Agente

◮ Acoes Publicas

”Todos os agentes percebem (sabem) o conteudo”Ex. Broadcast de uma mensagem

◮ Acoes Privadas

”Todos os agentes num grupo percebem (sabem) o conteudo”Ex. mensagem de um agente para outro,

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 80: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Logicas Epistemicas Dinamicas

◮ Acoes Publicas

”Public Annoucement Logic”

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 81: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Logicas Epistemicas Dinamicas

◮ Acoes Publicas

”Public Annoucement Logic”

◮ Acoes Privadas

”Action Model Logic”

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 82: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Public Annoucement Logic

201

102

012 021

210

120

a

a

a

b b

bc

c c

◮ Ana anuncia Publicamente que nao tem carta 1

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 83: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Public Annoucement Logic

201

102

012 021

210

120

a

a

a

b b

bc

c c

◮ Ana anuncia Publicamente que nao tem carta 1

◮ Apos anucio Carla sabe Beto tem carta 1

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 84: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Public Annoucement Logic

201

102

012 021

210

120

a

a

a

b b

bc

c c

◮ Ana anuncia Publicamente que nao tem carta 1

◮ Apos anucio Carla sabe Beto tem carta 1

◮ Apos anucio Carla sabe Ana tem carta 0

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 85: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Public Annoucement Logic

201

102

012 021

210

120

a

a

a

b b

bc

c c

◮ Ana anuncia Publicamente que nao tem carta 1

◮ Apos anucio Carla sabe Beto tem carta 1

◮ Apos anucio Carla sabe Ana tem carta 0

◮ Apos anucio Beto nao sabe a carta de Ana

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 86: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Public Annoucement Logic

201

102

012 021

210

120

a

a

a

b b

bc

c c

◮ Apos anucio Carla sabe Beto tem carta 1

[¬1a]Kc1b

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 87: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Public Annoucement Logic

201

102

012 021

210

120

a

a

a

b b

bc

c c

◮ Apos anucio Carla sabe Beto tem carta 1

[¬1a]Kc1b◮ Apos anucio Carla sabe Ana tem carta 0

[¬1a]Kc0a

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 88: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Public Annoucement Logic

201

102

012 021

210

120

a

a

a

b b

bc

c c

◮ Apos anucio Carla sabe Beto tem carta 1

[¬1a]Kc1b◮ Apos anucio Carla sabe Ana tem carta 0

[¬1a]Kc0a◮ Apos anucio Beto nao sabe a carta de Ana

[¬1a]¬(Kb0a ∨ Kb1a ∨ Kb2a)

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 89: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Public Announcement Logic: Linguagem

ϕ ::= p | ¬ϕ | (ϕ ∧ ϕ) | Kaϕ | [ϕ]ψ

Significado: [ϕ]ψ ⇒ “depois do anuncio de ϕ, ψ e verdadeiro.”

Exemplo: [¬1a]Kc1b ⇒ Apos anucio que Ana nao tem a carta 1,Carla sabe Beto tem carta 1

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 90: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Public Announcement Logic: Semantica

◮ O efeito de anunciar ϕ publicamente e um restricao nomodelo para conter somente estados onde ϕ ’verdadeiro.

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 91: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Public Announcement Logic: Semantica

◮ O efeito de anunciar ϕ publicamente e um restricao nomodelo para conter somente estados onde ϕ ’verdadeiro.

◮ Anuncios sao publicos e verdadeiros.

M, s |= [ϕ]ψ iff (M, s |= ϕ implica M|ϕ, s |= ψ)

M|ϕ := 〈S ′,∼′,V ′〉:

S ′ := [[ϕ]]M := {s ∈ S | M, s |= ϕ}∼′

a := ∼a ∩ ([[ϕ]]M × [[ϕ]]M)V ′(p) := V (p) ∩ [[ϕ]]M

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 92: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Exemplo Anuncio

201

102

012 021

210

120

a

a

a

b b

bc

c c

⇒ 201

012 021

210

a

a

bc

Hexa, 012 |= [¬1a]Kc0a⇔Hexa, 012 |= ¬1a and Hexa|¬1a, 012 |= Kc0a⇐Hexa, 012 |= ¬1a and (Hexa|¬1a, 012 |= 0a and ∼c (012) ={012})⇐012 6= V (1a) and 012 ∈ V ′(0a)

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 93: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Jogo de Cartas - PAL - Exercıcios

Represente (como uma formula em PAL) e verifique, formalmente(|=), se algum jogador ja sabe a sua carta para os seguintesanuncios:

1. Ana anuncia que ou tem a carta 1 ou a carta 2.

2. Ana anuncia que acredita que a carta de Beto e a 2.

3. Beto anuncia que se ele tem a carta 1 a Ana tem a 0.

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 94: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas brincando na lama;

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 95: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas brincando na lama;

◮ Pai chega e ve que algumas possuem lama na testa;

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 96: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas brincando na lama;

◮ Pai chega e ve que algumas possuem lama na testa;

◮ Crincas podem ver a lama na testas das outras mas nao napropria testa;

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 97: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas brincando na lama;

◮ Pai chega e ve que algumas possuem lama na testa;

◮ Crincas podem ver a lama na testas das outras mas nao napropria testa;

◮ Pai Anuncia:

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 98: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas brincando na lama;

◮ Pai chega e ve que algumas possuem lama na testa;

◮ Crincas podem ver a lama na testas das outras mas nao napropria testa;

◮ Pai Anuncia:

1. Tem pelo menos uma crianca c. lama!!!

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 99: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas brincando na lama;

◮ Pai chega e ve que algumas possuem lama na testa;

◮ Crincas podem ver a lama na testas das outras mas nao napropria testa;

◮ Pai Anuncia:

1. Tem pelo menos uma crianca c. lama!!!2. Alguem ja sabe se tem lama na testa???

...

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 100: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas brincando na lama;

◮ Pai chega e ve que algumas possuem lama na testa;

◮ Crincas podem ver a lama na testas das outras mas nao napropria testa;

◮ Pai Anuncia:

1. Tem pelo menos uma crianca c. lama!!!2. Alguem ja sabe se tem lama na testa???

...k. Alguem ja sabe se tem lama na testa???

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 101: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas brincando na lama;

◮ Pai chega e ve que algumas possuem lama na testa;

◮ Crincas podem ver a lama na testas das outras mas nao napropria testa;

◮ Pai Anuncia:

1. Tem pelo menos uma crianca c. lama!!!2. Alguem ja sabe se tem lama na testa???

...k. Alguem ja sabe se tem lama na testa???

◮ Quantos anuncios serao feitos ate que criancas c. lama

saibam que estao sujas?

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 102: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas n brincando na lama;

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 103: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas n brincando na lama;

◮ Tem k com lama na testa;

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 104: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas n brincando na lama;

◮ Tem k com lama na testa;

◮ Quantos anuncios serao feitos ate que criancas c. lama

saibam que estao sujas?

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 105: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas n brincando na lama;

◮ Tem k com lama na testa;

◮ Quantos anuncios serao feitos ate que criancas c. lama

saibam que estao sujas?

◮ Exemplos:

◮ n =3 e k=1 serao 1 anuncios;◮ n =3 e k=2 serao 2 anuncio;

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 106: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas n brincando na lama;

◮ Tem k com lama na testa;

◮ Quantos anuncios serao feitos ate que criancas c. lama

saibam que estao sujas?

◮ Exemplos:

◮ n =3 e k=1 serao 1 anuncios;◮ n =3 e k=2 serao 2 anuncio;

◮ Serao necessarios k anuncios!!!

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 107: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

◮ Grupo de criancas n brincando na lama;

◮ Tem k com lama na testa;

◮ Quantos anuncios serao feitos ate que criancas c. lama

saibam que estao sujas?

◮ Exemplos:

◮ n =3 e k=1 serao 1 anuncios;◮ n =3 e k=2 serao 2 anuncio;

◮ Serao necessarios k anuncios!!!

◮ Por que?

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 108: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa: Exemplo

◮ Grupo de criancas 3: ana, beto, carla;

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 109: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa: Exemplo

◮ Grupo de criancas 3: ana, beto, carla;

◮ Representacao Array : < a, b, c >;

010 ⇒ ana e carla limpas e beto com lama101 ⇒ ana e carla com lama e beto limpo

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 110: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa: Exemplo

◮ Grupo de criancas 3: ana, beto, carla;

◮ Representacao Array : < a, b, c >;

010 ⇒ ana e carla limpas e beto com lama101 ⇒ ana e carla com lama e beto limpo

◮ Tem 2 com lama na testa: ana e beto ⇒ Estado real 110

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 111: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa: Exemplo

◮ Grupo de criancas 3: ana, beto, carla;

◮ Representacao Array : < a, b, c >;

010 ⇒ ana e carla limpas e beto com lama101 ⇒ ana e carla com lama e beto limpo

◮ Tem 2 com lama na testa: ana e beto ⇒ Estado real 110

◮ Quantos anuncios serao feitos ate que criancas c. lama

saibam que estao sujas?

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 112: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa: Exemplo

◮ Grupo de criancas 3: ana, beto, carla;

◮ Representacao Array : < a, b, c >;

010 ⇒ ana e carla limpas e beto com lama101 ⇒ ana e carla com lama e beto limpo

◮ Tem 2 com lama na testa: ana e beto ⇒ Estado real 110

◮ Quantos anuncios serao feitos ate que criancas c. lama

saibam que estao sujas?

◮ 2 anuncios

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 113: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

000 100

010 110

001 101

011 111

a

a

c c

b b

b b

a

c c

a

Representacao

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 114: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

100

010 110

001 101

011 111

a

c

b

b b

a

c c

a

Anuncio: tem pelo menos uma c. lama.

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 115: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

110

101

011 111

b

c

a

Anuncio: Alguem ja sabe se tem lama na testa?

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 116: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa

110

Anuncio: Alguem ja sabe se tem lama na testa?

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 117: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa: Exemplo

◮ O que esta sendo anunciado?

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 118: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa: Exemplo

◮ O que esta sendo anunciado?

◮ Anuncio + Silencio

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 119: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa: Exemplo

◮ O que esta sendo anunciado?

◮ Anuncio + Silencio

◮ Primeiro Anuncio:

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 120: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa: Exemplo

◮ O que esta sendo anunciado?

◮ Anuncio + Silencio

◮ Primeiro Anuncio:

◮ [¬(0a ∧ 0b ∧ 0c)]

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 121: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa: Exemplo

◮ O que esta sendo anunciado?

◮ Anuncio + Silencio

◮ Primeiro Anuncio:

◮ [¬(0a ∧ 0b ∧ 0c)]

◮ Segundo Anuncio:

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 122: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa: Exemplo

◮ O que esta sendo anunciado?

◮ Anuncio + Silencio

◮ Primeiro Anuncio:

◮ [¬(0a ∧ 0b ∧ 0c)]

◮ Segundo Anuncio:

◮ [¬Ka1a ∧ ¬Kb1b ∧ ¬Kc1c ]

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 123: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Problema Criancas c/ Lama na testa: Exemplo

◮ O que esta sendo anunciado?

◮ Anuncio + Silencio

◮ Primeiro Anuncio:

◮ [¬(0a ∧ 0b ∧ 0c)]

◮ Segundo Anuncio:

◮ [¬Ka1a ∧ ¬Kb1b ∧ ¬Kc1c ]

◮ Exercıcio: descreva os anuncios para n = 5 e k = 3

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 124: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Axiomatizacao

[ϕ]p ↔ (ϕ→ p)[ϕ]¬ψ ↔ (ϕ→ ¬[ϕ]ψ)[ϕ](ψ ∧ χ) ↔ ([ϕ]ψ ∧ [ϕ]χ)[ϕ]Kaψ ↔ (ϕ→ Ka[ϕ]ψ)[ϕ][ψ]χ ↔ [ϕ ∧ [ϕ]ψ]χFrom ϕ, infer [ψ]ϕFrom χ→ [ϕ]ψ and χ ∧ ϕ→ EBχ, infer χ→ [ϕ]CBψ

Expressividade (Plaza, Gerbrandy):Today formula da linguagem de PAL, sem conhecimento comum, eequivalente a uma formula na linguagem da logica epistemica.

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 125: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Action Models

◮ Modelar Acoes entre Agentes.

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 126: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Action Models

◮ Modelar Acoes entre Agentes.

◮ Acoes Privadas

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 127: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Action Models

◮ Modelar Acoes entre Agentes.

◮ Acoes Privadas

◮ Porem todos sabem que elas ocorreram

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 128: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Action Models

◮ Modelar Acoes entre Agentes.

◮ Acoes Privadas

◮ Porem todos sabem que elas ocorreram

◮ Embora so alguns distinguam seu conteudo.

◮ Exemplos:

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 129: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Action Models

◮ Modelar Acoes entre Agentes.

◮ Acoes Privadas

◮ Porem todos sabem que elas ocorreram

◮ Embora so alguns distinguam seu conteudo.

◮ Exemplos:

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 130: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Action Models

◮ Modelar Acoes entre Agentes.

◮ Acoes Privadas

◮ Porem todos sabem que elas ocorreram

◮ Embora so alguns distinguam seu conteudo.

◮ Exemplos:

◮ Um jogador mostrar suas cartas para outro;

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 131: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Action Models

◮ Modelar Acoes entre Agentes.

◮ Acoes Privadas

◮ Porem todos sabem que elas ocorreram

◮ Embora so alguns distinguam seu conteudo.

◮ Exemplos:

◮ Um jogador mostrar suas cartas para outro;◮ Um jogador sussurrar um informacao para outro;

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 132: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Exemplo: Jogo das 3 Cartas

◮ ana ⇒ 0, beto ⇒ 1 e carla ⇒ 2

◮ ana mostra sua carta para beto

◮ carla nao ve a carta de ana

201

102

012 021

210

120

a

a

a

b b

bc

c c

?

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 133: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Exemplo: Jogo das 3 Cartas

◮ ana ⇒ 0, beto ⇒ 1 e carla ⇒ 2

◮ ana mostra sua carta para beto

◮ carla nao ve a carta de ana

201

102

012 021

210

120

a

a

a

b b

bc

c c

201

102

012 021

210

120

a

a

a

c

c c

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 134: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Modelos de Acao

Um modelo de acao M e uma estrutura 〈S,∼a, pre〉

◮ S e um domınio finito de acoes ou eventos

◮ ∼a e uma relacao de equivalencia entre S

◮ pre : S 7→ L e uma funcao de pre-condicao que atribui umapre-condicao para cada s ∈ S.

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 135: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Exemplo Cartas

◮ gente a deseja mostrar a sua carta para o agente b.

◮ 3 acoes, a mostra 0, 1 or 2.

◮ a e b distinguem as 3 acoes mas c nao.

sh0 sh1

sh2

c

cc

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 136: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Exemplo Cartas

sh0 sh1

sh2

c

cc

◮ S = {sh0, sh1, sh2}

◮ ∼a = {(s, s) | s ∈ S}

◮ ∼b = {(s, s) | s ∈ S}

◮ ∼c = S× S

◮ pre(sh0) = 0a◮ pre(sh1) = 1a◮ pre(sh2) = 2a

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 137: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Exemplo Cartas

◮ a sussura p/ b que nao tem a carta 0.

◮ 3 acoes, a sussurra que nao tem 0, 1 or 2.

◮ a e b distinguem as 3 acoes mas c nao.

wh0 wh1

wh2

c

cc

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 138: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Exemplo Cartas

wh0 wh1

wh2

c

cc

◮ S = {wh0,wh1,wh2}

◮ ∼1 = {(s, s) | s ∈ S}

◮ ∼2 = {(s, s) | s ∈ S}

◮ ∼3 = S× S

◮ pre(wh0) = ¬0a◮ pre(wh1) = ¬1a◮ pre(wh2) = ¬2a

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 139: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Acoes

◮ se distinguimos duas acoes, entao distinguimos os estadosresultantes da execucao das mesmas

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 140: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Acoes

◮ se distinguimos duas acoes, entao distinguimos os estadosresultantes da execucao das mesmas

◮ estados que distinguimos antes da execucao de uma acaocontinuamos a distinguir apos a execucao;

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 141: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Acoes

◮ se distinguimos duas acoes, entao distinguimos os estadosresultantes da execucao das mesmas

◮ estados que distinguimos antes da execucao de uma acaocontinuamos a distinguir apos a execucao;

◮ acoes so podem ser executadas em estados onde as suaspre-condicoes sao satisfeitas.

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 142: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Produto

Dado um estado epistemico (M, s) com M = 〈S ,∼a,V 〉 e ummodelo de acao (M, s) com M = 〈S,∼, pre〉. O resultado daexecucao (M, s) em (M, s) e (M⊗M, (s, s)) ondeM⊗M = 〈S ′,∼′,V ′〉 de tal forma que:

1. S ′ = {(s, s) de tal forma que s ∈ S , s ∈ S, e M, s |= pre(s)}

2. (s, s) ∼′

a (t, t) sse (s ∼a t e s ∼a t)

3. (s, s) ∈ V ′(p) sse s ∈ V (p)

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 143: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Ana mostra carta 0 p/ Beto

201

102

012 021

210

120

a

a

a

b b

bc

c c

×sh0 sh1

sh2

c

cc

201

102

012 021

210

120

a

a

a

c

c c

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 144: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Ana sussrra p/ Beto ‘nao 0’

201

102

210

120

201

012 021

210

102

012 021

120

c

c

a

a

b c

a

a

bc

a

a

bc

c

c

c c

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 145: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Linguagem

ϕ ::= p | ¬ϕ | (ϕ ∧ ϕ) | Kaϕ | CBϕ | [M, s]ϕ

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 146: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Semantica

M, s |= p :iff s ∈ V (p)M, s |= ¬ϕ :iff M, s 6|= ϕM, s |= ϕ ∧ ψ :iff M, s |= ϕ and M, s |= ψM, s |= Kaϕ :iff para todo s ′ ∈ S : s ∼a s

′ implica M, s ′ |= ϕM, s |= [M, s]ϕ :iff M, s |= pre(s) implica M ⊗M, (s, s) |= ϕ

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 147: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Semantica

◮ Mistura Sintaxe com Semantica?

SIM e NAO

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 148: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Axiomatizacao

[M, s]p ↔ (pre(s) → p)[M, s]¬ϕ↔ (pre(s) → ¬[M, s]ϕ)[M, s](ϕ ∧ ψ) ↔ ([M, s]ϕ ∧ [M, s]ψ)[M, s]Kaϕ↔ (pre(s) →

∧s∼at

Ka[M, t]ϕ)

[M, s][M′, s′]ϕ↔ [(M, s); (M′, s′)]ϕDe ϕ, infira [M, s]ϕ

Toda formula da linguagem de Logica de Modelos de Acao, semconhecimento comum, e equivalente a uma formula na linguagemda Logica Epistemica.

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13

Page 149: L´ogica Epistˆemica e Mudan¸cas de Crenc¸as · L´ogica Epistˆemica e Mudan¸cas de Crenc¸as Mario Benevides Universidade Federal do Rio de Janeiro Rio de Janeiro, Brasil 2013

Conclusoes

◮ Desenvolver Linguagens e Algorıtimos para Representar eInferir sobre estas estruturas

◮ Sistemas Assıncronos e Distribuidos

◮ Probabilısticos

◮ Temporais

Benevides: Logica Epistemica e Mudancas de Crencas DCC-13