Representação, Raciocínio e Lógica

• Representação do Conhecimento: expressar conhecimento de forma tratável pelo computador.

• Linguagens:

– sintaxe: descreve as possíveis configurações da linguagem que constituem sentenças válidas.

– semântica: determina o signifcado de cada sentença.

• exemplo: x > y,

– sintaxe: se x é um número e y é um número, então x > y é uma sentença sobre números.

– semântica: se x > y retorna verdadeiro, senão retorna falso.

[figure]

Representação, Raciocínio e Lógica

• Se linguagem tem sintaxe e semântica precisas, então podemos chamar esta linguagem de lógica.

• Mecanismo de inferência: derivado da sintaxe e semântica.

• Importante: distinguir entre os fatos e sua representação: não podemos colocar todos os fatos do mundo no computador! Neste caso, devemos operar em representações dos fatos (codificação em alguma linguagem).

• Raciocínio: processo de construir novas configurações a partir de configurações já existentes.

• Bom raciocínio deve assegurar que as novas configurações representam fatos que se seguem dos fatos já existentes.

Representação, Raciocínio e Lógica

• “Entailment”: relação entre sentenças tal que novas sentenças geradas são verdadeiras, dado que as anteriores também são.

• KB ⊨ α.

• Mecanismo de inferência:

– dada uma base de conhecimento KB, pode gerar novas sentenças que seguem de KB.

– dada uma base de conhecimento e uma sentença α, pode dizer se α é consequência lógica de KB.

– é sound ou truth-preserving se somente produzir sentenças que sejam consequência lógica de KB.

Representação, Raciocínio e Lógica

• Prova: procedimento de inferência “sound”.

• Analogia: procurar uma agulha num palheiro. – “entailment”: a agulha está no palheiro.

– prova: encontrar a agulha.

– se o palheiro for de tamanho finito, e procedimento sistemático de busca, então agulha vai ser encontrada: procedimento de inferência completo.

• Como obter um procedimento “sound”?

– passos de inferência devem respeitar a semântica das sentenças já existentes no KB.

– derivar novas sentenças que sejam consequência lógica dos fatos já representados no KB.

Representação, Raciocínio e Lógica

• Teoria de Prova: especifica passos de inferência “sound”.

• Exemplo: E = mc^{2}

– sintaxe: permite que duas expressões sejam conectadas por um =.

– semântica: as duas expressões devem ter valores iguais.

– ET = mc^{2}T, nova sentença possível.

Representação, Raciocínio e Lógica

[figure]

Representação, Raciocínio e Lógica

• Representação: duas classes de linguagens, programação e natural.

• Vantagens de linguagens de programação:

– descrever algoritmos e estruturas de dados concretas.

– Ex: World[2,2] ← Pit.

• Desvantagem: pouca expressividade. Como representar “há um buraco em [2,2] ou [3,1]”? Ou “há um monstro em algum quadrado”?

• Vantagens de linguagens naturais:

– grande poder de expressao.

– ideal para comunicação.

• Desvantagens:

– mais para comunicação do que para representação.

– sensível ao contexto.

– ambígua.

Representação, Raciocínio e Lógica

• Boa linguagem para representação do conhecimento deve combinar vantagens de linguagens naturais e linguagens de programação.

• Lógica de primeira ordem: precisa, concisa, independente do contexto, e não ambígua.

• linguagem em si não importante: principal é como uma linguagem formal pode representar o conhecimento, e como mecanismos sistemáticos podem operar sobre as expressões da linguagem de forma a raciocinar.

Representação, Raciocínio e Lógica

• Semântica: significado de uma sentença.

• Interpretação.

• Linguagens composicionais: linguagem que impõe uma relação sistemática entre sentenças e fatos. O significado de uma sentença é função do significado de suas partes.

• Exemplos: “S_{1,2}” verdadeiro na interpretação em que há “mau cheiro” no quadrado [1,2] do mundo do wumpus, falso em outros mundos ou se [1,2] tivesse interpretação de ter “brisa” invés de “mau cheiro”.

Representação, Raciocínio e Lógica

• Inferência: qualquer processo pelo qual se chega a alguma conclusão.

• Inferência lógica ou dedução: raciocínio “sound”.

• Validade e satisfabilidade

– uma sentença é válida se for verdadeira para todas as interpretações. Ex: “há um mau cheiro na posição [1,1] ou não há um mau cheiro na posição [1,1]” (p ∨ ¬p).

– uma sentença é satisfatível se existir alguma interpretação para a qual a sentença é verdadeira.

Representação, Raciocínio e Lógica

• Outros exemplos:

– “há uma posição aberta em frente de mim ou há uma parede em frente de mim”: não necessariamente válida.

– “Se todo quadrado tem uma área aberta ou uma parede, então há uma posição aberta em frente de mim ou há uma parede em frente de mim”: válida.

• sinônimos para sentenças válidas:

tautologia, sentenças analíticas.

• Sentenças insatisfatíveis: valor falso para todas as interpretações. Ex: “há uma parede em frente de mim e não há uma parede em frente de mim”.

Representação, Raciocínio e Lógica

• Inferência em computadores: utiliza conceitos de validade e instatisfabilidade para chegar a conclusões.

• Computador tem duas desvantagens:

– não conhece nada sobre a interpretação que estamos usando.

– não conhece nada sobre o domínio do problema, exceto o que aparece no banco de conhecimento.

• Suponha: “posso mover para a posição [2,2]”?

• Computador deve provar que mover para posição [2,2] é consequência lógica dos fatos no banco de conhecimento (Sentença: “Se KB é verdadeiro então posso mover para [2,2]” deve ser provada).

Representação, Raciocínio e Lógica

• vantagem de aplicar inferência formal: pode ser usada para derivar conclusões válidas mesmo quando o computador não conhece nada sobre o domínio ou sobre a interpretação das sentenças.

• Uma Lógica consiste de:

– sistema formal para descrever estados e relações (sintaxe e semântica).

– teoria de prova: conjunto de regras para deduzir se uma sentença é consequência lógica do banco de conhecimento.

[figure]

Representação, Raciocínio e Lógica

• Lógica proposicional e lógica de primeira ordem (cálculo de predicados de primeira ordem com igualdade).

• Lógica proposicional: símbolos são proposições. Ex: D pode ter a int de que o wumpus está morto. Pode assumir valor falso ou verdadeiro.

• símbolos proposicionais combinados através de conectivos booleanos formando sentenças mais complexas.

• Linguagem bem simples.

• Lógica de primeira ordem: objetos e predicados relacionando objetos.

• Admite quantificadores (∀ e ∃).

• Mais expressividade do que proposicional.

Lógica Proposicional

Sintaxe:

S → AS | CS
AS → True | False | P | Q | R | …
CS → ( S ) | S C S | ¬ S
C → ∧ | ∨ | ⇔ | ⇒

Lógica Proposicional

• conjunções, disjunções.

• sentença atômica = literal.

• ordem de precedência (do maior p/ o menor): ¬, ∧, ∨, ⇒ e ⇔.

• ¬P ∨ Q ∧ R ⇒ S é equivalente a ((¬P) ∨ (Q ∧ R)) ⇒ S.

• semântica simples.

• tabelas-verdade: definição de conectivos e teste de validade de sentenças.

Lógica Proposicional

Exemplo: S = ((P ∨ H) ∧ ¬H) ⇒ P é válida.

P H P ∨ H (P ∨ H) ∧ ¬H S
F F F  F  T
F T T  F  T
T F T  T  T
T T T  F  T

• P: wumpus está na posição [1,3].

• H: wumpus está na posição [2,2].

• Se sabemos que (P ∨ H) é verdadeiro e ¬H também é verdadeiro, então o wumpus só pode estar na posição [1,3].