Lógica Proposicional

• Modelo: qualquer mundo em que a sentença é verdadeira para alguma interpretação.

• Uma sentença α é consequência lógica de um KB se os modelos de KB forem todos os modelos de α.

• Regras de inferência:

\frac{α⇒β,α}{β}  \frac{α_{1}∧α_{2}∧...∧α_{n}}{α_{i}}
\frac{α_{1},α_{2},...,α_{n}}{α_{1}∧α_{2}∧...∧α_{n}}  \frac{α_{i}}{α_{1}∨α_{2}∨...∨α_{n}}
\frac{¬¬α}{α}  \frac{α∨β,¬β}{α}

\frac{α∨β,¬β∨γ}{α∨γ}

Lógica Proposicional

• Complexidade

• Método da tabela verdade é completo:

possível enumerar 2^{n} linhas para a tabela com valores T e F para qualquer prova envolvendo n síbolos proposicionais.

• Tempo exponencial, mas a maioria dos problemas pode ser resolvido em tempo polinomial usando as regras de inferência.

• Característica de lógica clássica:

monotonicidade.

• if KB_{1} ⊨ α then (KB_{1} ∪ KB_{2}) ⊨ α

• Horn sentences (cláusulas de Horn): possui um procedimento de inferência com tempo polinomial.

Lógica Proposicional

• Agente para o mundo do wumpus!

• B: brisa, S: mau cheiro, W: wumpus.

• ¬S_{1,1}, ¬S_{2,1}, S_{1,2}, ¬B_{1,1}, B_{2,1}, ¬B_{1,2}: fatos.

• Regras:

R_{1} : ¬S_{1,1} ⇒ ¬W_{1,1} ∧ ¬W_{1,2} ∧ ¬W_{2,1}

R_{2} : ¬S_{2,1} ⇒ ¬W_{1,1} ∧ ¬W_{2,1} ∧ ¬W_{2,2} ∧ ¬W_{3,1} R_{3} : ¬S_{1,2} ⇒ ¬W_{1,1} ∧ ¬W_{1,2} ∧ ¬W_{2,2} ∧ ¬W_{1,3} R_{4} : S_{1,2} ⇒ W_{1,1} ∨ W_{1,2} ∨ W_{1,3} ∨ W_{2,2}

Lógica Proposicional

• Como encontrar o wumpus?

• Tabela verdade vai ter 12 símbolos proposicionais: S_{1,1}, S_{2,1}, S_{1,2}, W_{1,1}, W_{1,2}, W_{2,1}, W_{2,2}, W_{3,1}, W_{1,3}, B_{1,1}, B_{2,1}, B_{1,2}

• 2^{12} entradas na tabela!

• Aplicação das regras de inferência.

Lógica Proposicional

1. Modus Ponens sobre ¬S_{1,1} (R_{1}):

¬W_{1,1} ∧ ¬W_{1,2} ∧ ¬W_{2,1}

2. Eliminação E em (1): ¬W_{1,1}, ¬W_{1,2}, ¬W_{2,1}

3. Modus Ponens sobre ¬S_{2,1} (R_{2}) e elim E: ¬W_{1,1}, ¬W_{2,2}, ¬W_{2,1}, ¬W_{3,1}

4. Modus Ponens sobre S_{1,2} (R_{4}):

W_{1,3} ∨ W_{1,2} ∨ W_{2,2} ∨ W_{1,1}

5. Resolução unitária com α: W_{1,3} ∨ W_{1,2} ∨ W_{2,2} e β: W_{1,1}, obtém-se: W_{1,3} ∨ W_{1,2} ∨ W_{2,2}

6. Res. Unit. com α: W_{1,3} ∨ W_{1,2} e β: W_{2,2}. Obtém-se: W_{1,3} ∨ W_{1,2}

7. Res. Unit. com α: W_{1,3} e β: W_{1,2}. Wumpus está na posição W_{1,3}!.

Lógica Proposicional

• Prova mostrou onde estava o wumpus, mas não mostra ações.

• Para as ações:

A_{1,1} ∧ East_{A} ∧ W_{1,2} ⇒ ¬F orward, uma para cada posição e orientação possíveis.

• Lógica proposicional não responde “que ação devo tomar”, mas responde “Posso mover para a frente?”, “Posso virar para a direita?”.

Lógica Proposicional

function PROPOSITIONAL-KB-AGENT(percept) returns an action

static: KB, knowledge base

t, contador, init 0, indica tempo TELL(KB,MAKE-PERCEPT-SENTENCE(percept,t)) for each action in the list of possible actions do

if ASK(KB,MAKE-ACTION-QUERY(t,action)) then t ← t + 1 return action

end

Lógica Proposicional

• Problemas com lógica proposicional:

• muitas proposições para o quadrado 4x4.

• Ex: “não ande para a frente se o wumpus está na sua frente” precisa de um conj de 64 regras (16 quadrados x 4 orientações).

• não tem memória do caminho a menos que se represente uma proposição para cada instante no tempo.

• Ex: move para A_{2,1} se torna verdade e A_{1,1} se torna falso. Mas pode ser importante guardar o fato de que o agente esteve em A_{1,1}.

• problema: não sabemos o tempo que vai levar para terminar o jogo.

Lógica Proposicional

• Exemplo de proposições adicionais:

A_{1,1}^{0} ∧ East_{A}^{0} ∧ W_{2,1}^{0} ⇒ ¬F orward^{0} A_{1,1}^{1} ∧ East_{A}^{1} ∧ W_{2,1}^{1} ⇒ ¬F orward^{1} A_{1,1}^{2} ∧ East_{A}^{2} ∧ W_{2,1}^{2} ⇒ ¬F orward^{2} ⋮

• índice no topo de cada símbolo indica tempo.

• para 100 unidades de tempo: 6400 destas regras, somente para dizer: “não mova para a frente se o wumpus estiver lá”.

• lógica de primeira ordem: reduz as 6400 para apenas 1!

[figure]

Lógica de Primeira Ordem

• objetos e relações entre objetos, propriedades, funções.

• Objetos: pessoas, casas, números, teorias, Fernando Henrique, cores, jogos de futebol, séculos etc.

• Relações: irmão/irmã de, parte de, maior que, tem cor, ocorreu depois, pertence etc.

• Funções: pai de, melhor amigo de, vencedor de, um mais que etc.

• Ex: “quadrados vizinhos ao quadrado do wumpus têm mau cheiro”. Objetos: wumpus, quadrado; Propriedade: mau cheiro; Relação: vizinhança.

• Motivação para o uso de lógica de primeira ordem: formalismo mais estudado e melhor entendido que outras abordagens.

Lógica de Primeira Ordem

• Sintaxe e Semântica.

\begin{aligned}S & → & AS | SCS | QV ar, … S | ¬S | (S) \\ AS & → & P red(T erm, …) | T erm = T erm \\ T erm & → & F unc(T erm, …) | Const | V ar \\ C & → & ⇒| ∧ | ∨ |⇔ \\ Q & → & ∀ | ∃ \\ Const & → & A | X_{1} | John … \\ V ar & → & a | x | s | … \\ P red & → & Mother | LeftLegOf | … \end{aligned}

Lógica de Primeira Ordem

• Termo: expressão lógica que se refere a um objeto. Ex: LeftLegOf(ReiJoao).

• Fórmulas atômicas: representam fatos. Símbolo de predicado seguido de uma lista de termos entre parênteses. Ex: Irmão(Ricardo, João), Casados(Pai(Ricardo), Mãe(João)). Convenção: P(x,y), x é P de y.

• Sentenças complexas: Irmão(Ricardo, João)∧ Irmão(João, Ricardo), MaisVelho(João, 30) ∨ MaisNovo(João, 30), MaisVelho(João,30) ⇒ ¬ MaisNovo(João,30).

[figure]

Lógica de Primeira Ordem • Quantificadores: fazem lógica de primeira

ordem ser mais expressiva do que lógica proposicional. Ex: ∀xGato(x) ⇒ Mamifero(x).

• Termo ground: termo sem variáveis.

• quantificador existencial:

∃xIrma(x, Spot) ∧ Gato(x).

• Quantif aninhados: caso mais simples ∀x, yP ai(x, y) ⇒ F ilho(y, x), equivalente a ∀x∀yP ai(x, y) ⇒ F ilho(y, x).

• “Todos amam alguém”: ∀x∃yama(x, y).

• “Há alguém que é amado por todos”: ∃y∀xama(x, y)

• ordem de utilização dos quantif importante.

• dificuldade:

∀x[Gato(x) ∨ (∃xIrmao(Ricardo, x))].

Lógica de Primeira Ordem • Relações entre ∀ e ∃.

• ∀x¬Gosta(x, Gatos) é equivalente a ¬∃xGosta(x, Gatos).

• “Todo mundo gosta de sorvete”:

∀xGosta(x, Sorvete) ou

¬∃x¬Gosta(x, Sorvete).

• Leis de De Morgan se aplicam a fórmulas quantificadas e não quantificadas.

• Para efeito de representação não precisamos usar quantificadores ou todos os conectivos.

• Igualdade: dois termos referem ao mesmo objeto.

Extensões e Variações Notacionais

• lógica de mais alta ordem: quantificação feita em cima de funções além de objetos. Ex: ∀x, y(x = y) ⇔ (∀p p(x) ⇔ p(y)), ∀f, g(f = g) ⇔ (∀xf(x) = g(x)).

• Outras extensões: leitura para casa!

• Variações notacionais: leitura para casa!

Lógica de Primeira Ordem

• Utilizando lógica de primeira ordem: bancos de dados, prova de teoremas, manipulação de conjuntos.

• Ex: conjuntos.

– ∀sSet(s) ⇔ (s = EmptySet) ∨ (∃x, s_{2}Set(s_{2}) ∧ s = AdJoin(x, s_{2}))

– ¬∃x, sAdJoin(x, s) = EmptySet

– ∀x, sMember(x, s) ⇔ s = AdJoin(x, s)

– Notação especial usada para conjuntos: [], [x], [x,y], [x,y|l].

Lógica de Primeira Ordem • Perguntando e recebendo respostas: TELL e

ASK.

• sentenças adicionadas com TELL: assertivas.

• sentenças perguntadas com ASK: consultas ou objetivos.

• respostas podem “instanciar” variáveis: substituições e listas de “bindings”.

Lógica de Primeira Ordem

• Agente lógico para o mundo do wumpus.

• três tipos de agentes: reflexos, baseados em modelo e baseados em objetivos.

• 1o. passo: definir a interface com o mundo externo

• sentença (interface) típica:

Percept([Maucheiro,Brisa,Brilho,N,N],5), onde elem1: percebe ou não percebe mau cheiro, elem2: percebe ou ão percebe brisa, elem3: percebe ou não percebe brilho, elem4: percebe ou não percebe parede, elem5: percebe ou não percebe grito (wumpus sendo morto).

• Ações: Turn(Right), Turn(Left), Forward, Shoot, Grab, Release, Climb.

Lógica de Primeira Ordem

• Determinação de que ação é a melhor: MAKE-ACTION-QUERY cria uma consulta tal que ∃aAction(a, 5). ASK deve retornar uma lista com a substituição {a/Grab}.

• o agente chama novamente TELL para registrar qual ação tomada.

Lógica de Primeira Ordem

function KB-AGENT(percept) returns an action

static: KB, knowledge base

t, contador, init 0, indica tempo TELL(KB,MAKE-PERCEPT-SENTENCE(percept,t)) action ← ASK(KB,MAKE-ACTION-QUERY(t)) TELL(KB,MAKE-ACTION-SENTENCE(action,t)) t ← t + 1

return action end

Lógica de Primeira Ordem • Um agente reflexo simples.

• ∀s, b, u, c, tP ([s, b, Brilho, u, c], t) ⇒ Action(Grab, t)

• ∀b, g, u, c, tP ([MauCheiro, b, g, u, c], t) ⇒ MauCheiro(t)

• ∀s, g, u, c, tP ([s, Brisa, g, u, c], t) ⇒ Brisa(t)

• ∀s, b, u, c, tP ([s, b, Brilho, u, c], t) ⇒ Ouro(t)

• ∀tAtOuro(t) ⇒ Action(Grab, t)

Lógica de Primeira Ordem

• Limitações de um agente reflexo:

– não faz parte da percepção deste tipo de agente saber onde está ou se está com o ouro.

– é incapaz de evitar “loops”. Ex: assuma que o agente conseguiu pegar o ouro e está no caminho de volta para casa. Se passar novamente pelo mesmo quadrado visitado na ida, entra em loop.

– problema: não está representado neste agente o fato dele estar carregando o ouro e a situação ser diferente da situação da ida.

• precisa de representação de modificações no mundo.

Lógica de Primeira Ordem

• Representação de modificações: uma das áreas mais importantes em representação do conhecimento.

• regras diacrônicas.

• representação de situações e ações não é diferente de representação de objetos e relações.

• Cálculo de Situações: forma de descrever modificações em lógica de primeira ordem.

Lógica de Primeira Ordem

• Considera o mundo como uma sequência de situações.

• formato: At(Agente,posição,situação). Ex: At(Agent, [1, 1], S_{0}) ∧ At(Agent, [1, 2], S_{1})

• cálculo de situações utiliza Result(action, situation) para representar a situação decorrente da execução de uma ação em situação anterior.

• Ex: Result(F orward, S_{0}) = S_{1}, Result(T urn(Right), S_{1}) = S_{2}, Result(F orward, S_{2}) = S_{3}

Lógica de Primeira Ordem • Ações: são descritas através de seus efeitos:

axiomas de efeito.

• P ortable(Ouro)

• ∀sAtOuro(s) ⇒ P resent(Ouro, s)

• ∀x, sP resent(x, s) ∧ P ortable(x) ⇒ Holding(x, Result(Grab, s))

• ∀x, s¬Holding(x, Result(Release, s))

• não sufuciente para saber se o agente está segurando o ouro ou continua segurando o ouro.