Lógicas e Inferência para IA

Lógica

Métodos para determinação de

validade de fórmulas

Métodos para determinação de validade de fórmulas

Tabela verdade Métodos de dedução Método da negação ou absurdo

Método da negação ou absurdo (cont.)

Para provar que H é uma tautologia Supõe-se inicialmente, por absurdo

que H NÃO é uma tautologia

As deduções desta fórmula levam a um fato contraditório (ou absurdo)

Portanto, a suposição inicial é falsa e: H é uma tautologia (A não-validade de H é um absurdo)

Lógica de Predicados

Dedução Natural

Conseqüência lógica Definição informal:

Uma fórmula é uma conseqüência lógica de um conjunto de fórmulas se sempre que estas forem verdadeiras aquela também seja verdadeira.

Definição formal: Dada uma fórmula H e um conjunto

de hipóteses , H é conseqüência lógica de num sistema de dedução, se existir uma prova de H a partir de

Notação de Conseqüência Lógica e Teorema Dada uma fórmula H, se H é

conseqüência lógica de um conjunto de hipóteses ={H1,H2,...Hn}, diz-se que: ├ H ou {H1,H2,...Hn}├ H

Uma fórmula H é um teorema se existe uma prova de H que não usa hipóteses ├ H

Cálculo

Proposicional ou de Predicados Cálculo = Lógica + Sistema de

Prova (ou dedução) Um sistema de prova serve para

analisar e raciocinar sobre argumentos de uma lógica, de maneira a prová-los válidos ou inválidos.

Sistema de dedução natural

Alfabeto da Lógica de Predicados Conjunto de fórmulas da Lógica de

Predicados Conjunto de regras de dedução (ou

regras de inferência)

Regras de inferência de dedução natural Servem para inserção e retirada de

conectivos lógicos e quantificadores, criando derivações Regras de Introdução Regras de Eliminação

Chama-se dedução natural por estar próxima da maneira como nós raciocinamos quando queremos (informalmente) provar um argumento.

Regras de inferência - conjunção

Introdução da conjunção (^I): H G -> derivação

H^G Eliminação da conjunção (^E):

H^G H^G H G

Prova

Dados H uma fórmula e um conjunto de fórmulas (hipóteses)

Uma prova de H a partir de é uma derivação onde As regras de inferência são aplicadas

tendo como premissas fórmulas de A última fórmula da derivação é H

Exemplo de prova P ^ Q, R |- Q ^ R

P ^ Q (Premissa) Q (^E) R (Premissa)

Q^R (^I)

Exercícios: (P^Q) ^ R, S^T |- Q^S P^Q |- Q^P (P^Q) ^ R |- P ^ (Q^R)

Regras da Dedução Natural - implicação Eliminação da implicação - modus

ponens (E) H H G G

Introdução da implicação (I) [H] (hipótese eliminada)

| G .

H G

Exemplo de eliminação da implicação

P^Q, (P (Q R)) ├ (Q R) P^Q

P (^E) P (Q R) (premissa) (Q R) (E)

Exemplo de introdução da implicação ├ (P ((PQ)Q) Supor os antecedentes Eles não poderão ser usados

depois

[P] [(PQ)] (hipóteses) Q (E)

(PQ)Q) (I)(P ((PQ)Q) (I)

Exercício

├ (P(Q P)) ├ (P(Q R)) ((P^Q)R))

Exercícios

1. {P^Q, (P^Q)(R^P)} |- R^P

2. {P (Q R), PQ, P} |- R 3. {P (P Q), P} |- Q

Regras da Dedução Natural- disjunção Introdução da disjunção (vI)

H G . HvG HvG

Eliminação da disjunção (vE) [H] [G] (hipóteses)

D1 D2 HvG E E

E

Exemplo de Eliminação da disjunção

{PvQ,Q,P} |- false

PvQ .[P] P (prem.) [Q] Q (prem.)

false falsefalse

Regras da Dedução Natural- negação

De uma derivação de uma contradição (false) a partir de uma hipótese H, pode-se descartar a hipótese e inferir H e vice-versa

[H] (I) [H] (E ou RAA) | |

false false reductio ad H H absurdum

Exercícios: HH e H H

Exercício

Mostre que o seguintes argumento é válido:

Se este argumento for incorreto e válido, então nem todas as suas premissas são verdadeiras. Todas as suas premissas são verdadeiras. Ele é válido. Portanto ele é correto.

Solução

Identificando as Sentenças: P: as premissas deste argumento são

verdadeiras. S: este argumento é correto. V: este argumento é válido.

Formalizando:{(S ^ V) P, P, V} ├ S

Exercício

Deus não existe. Pois, se Deus existisse a vida teria significado. Mas a vida não tem significado. Prove isso!

Quando tudo o mais falhar EFQ: ex falso quodlibet ou regra da

contradição Podemos estar loucos, então

qualquer literal é aceitável! Note que esta regra NÃO SUPÕE E

NEM ELIMINA nada!! false

H

Prova de EFQ

{P, P} ├ Q Q . P P (prem.) false

Q (E)

Exemplo

Prove o Silogismo Disjuntivo, usando EFQ: {P v Q, P} ├ Q

Exercícios {P (QR), P, Q} |= R {P Q, P} |= Q {P (Q ^ R), P} |= P ^ Q {(P ^ Q) (R ^ S), P, Q} |= S

{AB, C(DvE), DC, AE} |= (C B)

{Cv(B A), A R, (B R) S} |= (C S)

Lógicas clássicas

Lógica minimal: {^v} x {IE} Lógica intuicionista =

Lógica minimal U EFQ

Regras de inferência - equivalência

Introdução da equivalência ( I): H G GH

HG Eliminação da equivalência (

E): HG HG

HG GH

Dedução Natural A diferença básica da Lógica de

Predicados para a Proposicional é que as contradições têm de ser em cima de instâncias

As instâncias normalmente têm de ser geradas a partir de fórmulas quantificadas

Quando fazer isso?

Ocorrência livre e ligada

Se x é uma variável e E uma fórmula, uma ocorrência de x em E é Ligada, se x está no escopo de um

quantificador (x) ou (x) em E Livre, se não for ligada

G=(x)(y)((z)p(x,y,w,z) (y)q(z,y,x,z1))

Variável livre e ligada

Se x é uma variável e E uma fórmula que contém x. x é Ligada em E, se existir uma ou mais

ocorrências ligadas de x em E Livre em E, se existir uma ou mais

ocorrências livres de x em E

No exemplo anterior, z é livre e ligada!

Regras da dedução natural – quantificador universal

Eliminação do quantificador universal (E) x H(x), se a é livre para x em H H(a)

Introdução do quantificador universal (I) H(a) . x H(x) se x não ocorre livre em nenhuma das

premissas das quais H(x) depende

Explicando I Papel reservado aos nomes arbitrários, algo que no

cotidiano usamos Uma forma abreviada de dizer :

“Todos os portugueses gostam de boa conversa” é dizer «O Zé-povinho gosta de boa conversa» «Zé-povinho» refere-se a qualquer português,

arbitrariamente Contudo, é necessário garantir que o nome seja

arbitrário, pois se for um nome próprio a inferência é inválida!

Não se pode concluir que todos os portugueses gostam de boa conversa só porque o Joaquim gosta de boa conversa.

Exemplo 1 x ((x) (x)) x (x) x (x)

[x ((x) (x))] (sup.) (x) (x) ( E) x(x) x (x) (I) x(x) x (x)

(I) x ((x) (x)) x (x) x (x) (I)

Exemplo 2 x( (x)) ( x(x)) se x não

ocorre livre em .

[x ( (x))](sup.) [](sup.) ( (x)) (E) (x) (E) x (x) (I) ( x (x)) (I ) x( (x)) ( x (x)) (I )

Regras da dedução natural – quantificador existencial

Eliminação do quantificador existencial (E) x H(x), se a é livre para x em H

H(a) Introdução do quantificador existencial (I)

[H(a)] (hipótese) |

x H(x) E E

x não ocorre livre em nenhuma das premissas usadas na derivação acima do travessão e nem E

Exemplo (x ((x) )) (x ) se x não ocorre

livre em .

[x ((x) )] [x ] [(x)] ((x) ) E E E x I (x((x) ) ) (x )) I

Regras da dedução natural – identidade

Eliminação da identidade (=E) t=u H(t)

H(u) Introdução da identidade (=I)

n=n x=y

P(x)P(y)

Exemplo x=y(z P(x,z) z P(y,z) )

[x=y] [z P(x,z)] P(x,z) E P(x,z) P(y,z) I= P(x,z)P(y,z) E P(y,z) E z P(y,z) I (z P(x,z) z P(y,z) ) I x=y(z P(x,z) z P(y,z) ) I

Lógica

Sistema Axiomático

Sistema axiomático Alfabeto da Lógica de Predicados Conjunto de fórmulas da Lógica de

Predicados Conjunto de regras de dedução (ou

regras de inferência) Normalmente só Modus Ponens

Um conjunto de axiomas Subconjunto de fórmulas Existem vários!!

Exemplo

Ax1= A(BA) Ax2= (A(BC) ((AB)(AC)) Ax3= (A B)((AB)A) Ax4= x H(x) H(a) Ax5= (x A B(x))(A x B(x)), se

x não é livre em H

Exemplo de prova

PP

(P((PP)P)) ((P(PP))(PP)) Ax2 com A=P, B=PP, C=P

P((PP)P), Ax1 (P(PP))(PP), Modus Ponens (P(PP)), Ax1 com A=P, B=P PP, Modus Ponens

Um sistema axiomático estranhíssimo... Regra de inferência: A A ^ (B

^C) C Ax1: (A^(B^C))^((A^(C^ A))

^((C^B)^((A^C)^(A^C))))

Conclusão: Sistemas axiomáticos são complicados de usar e de entender as provas!!