LógicaProf. Mário Benevides

mario@cos.ufrj.brMarço de 2008

LÓGICA

Índice:

I- Introdução ......................................................................................................3II- Lógica Clássica Proposicional ........................................................................5

1- Linguagem ..........................................................................................52- Semântica ...........................................................................................73- Sistemas Dedutivos ...........................................................................18

3.1. Dedução Natural ..........................................18 3.2. Provador Automático de Teoremas ..............25 3.3. Método Axiomático .....................................30

4- Relações entre Sintaxe e Semântica....................................................32III- Lógica Clássica de Primeira Ordem .............................................................36

1- Linguagem........................................................................................36 2- Sistemas Dedutivos...........................................................................40

2.1. Dedução Natural...........................................422.2 Método Axiomático......................................44

3- Semântica..........................................................................................464- Relação entre Sintaxe e Semântica ....................................................53

.

2

Motivação Prática:

· Álgebra de Boole· Programação em lógica, p. e. PROLOG· Sistemas especialistas· Especificação de programas· Banco de dados:

· dedutivos· hipótese de mundo fechado· default / prioridades

· Sistemas distribuídos:· tempo· recursos

· Lei (Lógica deôntica, p.e.) · Linguagens de programação

Livros:

· Lógica para a Computação - Cengage Learning - Flávio Soares Corrêa da Silva, Marcelo Finger e Ana Cristina Vieira de Melo

· Lógica para a Ciência da Computação – Ed. CampusJoão Nunes de Souza

· Introdução à Lógica Modal Aplicada a Computação Marcos Mota Costa

· Programação em Lógica e a Linguagem PROLOGCasanova

· LógicaJohn Nolt e Linnes Rohatyn

· A Mathematical Introduction to LogicEnderton

· Introduction to Mathematical LogicMendelson

3

I - Introdução

LÓGICA é o estudo do raciocínio dedutivo.

Histórico

· Aristóteles ® leis do discurso;· Idade Média ® lógica filosófica;· Boole (1815-1864) ® álgebra booleana;· Peano (c.1865) ® axiomatização da aritmética;· Frege (1874) ® investigar fundamentos da matemática;

® lógica moderna;· Russel-Wentehead (1910) ® Princípio Matemático - lógica moderna;· Hilbert (1925) ® formalização da noção de prova; ® mecanização da matemática;· Gentzen (1935) ® teoria da prova;· Godel (1931-1935) ® completude da lógica; ® incompletude da aritmética· Investigar Fundamentos da Computação.

Ä O que é Lógica?É o estudo do raciocínio dedutivo. (informal)

Mais formalmente:Ä Lógica é uma linguagem?

Lógica:LINGUAGEM

+ REGRAS DE DEDUÇÃO / INFERÊNCIA

+SEMÂNTICA

LinguagemÉ usada para descrever o conhecimento que se deseja representar.

Regras de DeduçãoServem para tirar conclusões a partir do conhecimento representado na

linguagem.

SemânticaServe para dar significado aos objetos descritos na linguagem.

4

Tipos mais comuns de lógica:· Lógica Clássica Proposicional· Lógica Clássica de 1a Ordem

Hipóteses da Lógica Clássica:

· proposicões atômicas;· proposições mais complexas podem ser construídas (decompostas) de

(em) proposições atômicas;· proposições atômicas são verdadeiras ou falsas (2 valores);· o valor verdade de uma proposição mais complexa somente depende

dos valores das proposições atômicas que a compõe.

Ex1: João ama Maria. (V ou F) Ex2: João é estudante e João é alto. ® o valor verdade só depende de sabermos se:

João é estudante. (V ou F?)João é alto. (V ou F?)

5

II-1. Linguagem da Lógica Clássica Proposicional

w A linguagem proposicional é uma linguagem formal cujo objetivo é representar trechos de discurso de uma maneira precisa e sem ambigüidades.

w Os seguintes operadores são usados para formar proposições mais complexas:

e Ùou Ú

se <condição> então <conclusão> ®não ¬

w Para representar proposições atômicas usaremos letras maiúsculas, por exemplo: A, B, C,...

Exemplos: A Ù B, A Ú B, A®B, ¬ A

Ex: Sócrates é um homem. Se Sócrates é um homem então Sócrates é mortal.

A - Sócrates é um homem. B - Sócrates é mortal.

BD: A A®B

Definição:

Um alfabeto proposicional é composto por três conjuntos de símbolos:Conectivos/operadores lógicos: Ù, Ú, ®, ¬ , «Símbolos auxiliares: ( e )Símbolos proposicionais: qualquer letra maiúscula é um símbolo

proposicional (ex: A, B,..., Z). Podemos acrescentar um subscrito numérico a letras maiúsculas (A1, A2,...). Denotamos este conjunto por P.

Apresentaremos a seguir uma gramática para definirmos quais são as fórmulas bem formadas da linguagem:

Definição:

A noção de fórmula bem formada, ou simplesmente fórmula, é definida, indutivamente, pelas seguintes condições:

Qualquer símbolo proposicional é uma fórmula.Se a e b são fórmulas então (a Ù b), (a Ú b), ¬ a, (a ® b), (a « b) também

o são;Nada mais é fórmula.

6

Exemplos:a) A®B (não é fórmula)b) (A) ® ¬ (B) (não é fórmula)c) (¬ AÚB) Ù (BÙC) ® D (não é fórmula)d) ( (A® (B® ¬ A)) ® (AÚB) ) (é fórmula)e) (A ® (BÙC)) (é fórmula)

Exercícios:

1. Represente as seguintes proposições utilizando a linguagem da lógica clássica proposicional. Utilize os símbolos proposicionais C (está chovendo) e N (está nevando).

a) Está chovendo, mas não está nevando.b) Não é o caso que está chovendo ou nevando.c) Se não está chovendo, então está nevando.d) Não é o caso que se está chovendo então está nevando.e) Está chovendo se e somente se está nevando.f) Se está nevando e chovendo, então está nevando.g) Se não está chovendo, então não é o caso que está nevando e chovendo.

Nos exercícios seguintes, represente o texto na linguagem da lógica proposicional, especificando significado dos símbolos proposicionais utilizados.

2. Ela não está em casa ou não está atendendo ao telefone. Mas se ela não está em casa, então ela foi seqüestrada. E se ela não está atendendo ao telefone, ela está correndo algum outro perigo. Ou ela foi seqüestrada ou ela está correndo um outro perigo.

3. Hoje é fim-de-semana se e somente se hoje é sábado ou domingo. Hoje não é sábado. Hoje não é domingo. Portanto, hoje não é um fim-de-semana.

4. A proposta de auxílio está no correio. Se os juízes a receberem até sexta-feira, eles a analisarão. Portanto, eles a analisarão porque se a proposta estiver no correio, eles a receberão até sexta-feira.

Observação:w Convenções sobre omissão de parênteses:

¬ > Ù > Ú > ®

¬ A ® B º (¬ A ® B) A® A Ù B º A ® (A Ù B)

w Parênteses mais externos podem ser omitidos:

A ® (B®C) º (A ® (B®C))

7

II-2. Semântica da Lógica Clássica Proposicional

A semântica da lógica clássica proposicional consiste na atribuição de significado às fórmulas da linguagem.

Isto é feito através da atribuição de valor verdade.Para cada fórmula é atribuído um valor verdadeiro ou falso.

valores-verdade: V - verdadeiro F - falso

O valor verdade de uma fórmula depende unicamente dos valores verdade atribuídos aos seus símbolos proposicionais.

Tabela Verdade

Conjunção:

A B A Ù BV V VV F FF V FF F F

Hoje tem aula e hoje é quinta-feira.

Disjunção (não-exclusiva):

A B A Ú BV V VV F VF V VF F F

Hoje tem aula ou hoje é quinta-feira.

Negação:

A ¬ AV FF V

Hoje não tem aula.

8

Implicação:

Exemplo: Considere o anúncio abaixo:

Em linguagem lógica: “Se pagamento à vista então 25% de desconto.”Suponha agora que D. Maria deseja verificar se este anúncio é honesto ou não.

Possibilidade Pagamto à vista 25% de desconto Anúncio1 V V V2 V F F3 F V V4 F F ?

A B A®BV V VV F FF V VF F V (?)

w Existem lógicas que discordam da linha 4 Ex: 3-valores, intuicionista, relevante...Exercício: Construa a tabela verdade de: (¬ A Ú B) ® C

A B C ¬ A (¬ A Ú B) (¬ AÚB)®CV V VV V FV F VV F FF V VF V FF F VF F F

9

Para pagamento à vista, nós damos 25% de desconto na compra de qualquer TV.

ÄMais formalmente:

A cada símbolo proposicional nós queremos atribuir um valor verdadeiro ou falso. Isto é feito através de uma função v de atribuição de valor verdade.

v: P ® {V,F}, onde P é conjunto dos símbolos proposicionais

Exemplos:v(A) = F, v(B) = V, v(C) = V

w Uma vez atribuído valor verdade a cada símbolo proposicional em P, queremos estender esta atribuição para o conjunto de todas as fórmulas da linguagem proposicional LP, que denotaremos por W.

w Definimos uma função v de atribuição de valor verdade a fórmulas da linguagem LP como uma extensão da função v tal que:

v: W ® {V,F}, onde v deve satisfazer as seguintes condições:

1. v(A) = v(A), se AÎP

2. v(¬ a) = V, se v(a) = F F, se v(a) = V

3. v(a Ù b) = V, se v(a) = v(b) = V F, caso contrário

4. v(a Ú b) = F, se v(a) = v(b) = F V, caso contrário

5. v(a®b) = F, se v(a) = V e v(b) = F V, caso contrário

Exemplo 1: (A® (B Ú ¬ C))v(A) = V v(B) = v(C) = F

v(A® (B Ú ¬ C)) = ? V

v(A) = V v(B Ú ¬ C) = ? V

v(B) = ? F v(¬ C ) = ? V

v(B) = F v(C) = ? F

v(C) = F

10

Exemplo 2: v( (A Ù ¬ D) ® (¬ C Ú B) ) = ?

v(A) = F, v(C) = V,v(B) = F, v(D) = V

v( (A Ù ¬ D) ® (¬ C Ú B) ) = ? V

v(A Ù ¬ D) = ? F v(¬ C Ú B) = ? F

v(A) = ? F v(¬ D) = ? F v(¬ C) = ? F v(B) = ? F

v(A) = F v(D) = ? V v(C) = ? V v(B) = F

v(D) = V v(C) = V

Ä Quantas linhas possui uma tabela verdade para (A Ù ¬ D) ® (¬ C Ú B) ?

Cada linha corresponde a uma possível atribuição de valores verdade aos símbolos proposicionais que compõe a fórmula. Como esta fórmula possui 4 símbolos proposicionais (A,B,C e D), sua tabela verdade deve ter 24 = 16 linhas.

w T.V. computa o valor verdade de uma fórmula para todas as possíveis atribuições v a seus símbolos proposicionais.

w Logo, o problema de se saber o valor verdade de uma fórmula na lógica clássica proposicional é DECIDÍVEL; o algoritmo é o seguinte:

passo 1: conte o número de símbolos proposicionais;passo2: monte uma tabela com 2n linhas e com quantas colunas for o

número de subfórmulas de a;passo 3: preencha as colunas dos símbolos proposicionais com V ou F

alternando de cima para baixo TFTF para a 1a coluna, TTFF... para a 2a, TTTTFFFF para a 3a e assim por diante, nas potências de 2.

passo 4: compute o valor verdade das outras colunas usando as tabelas básicas fornecidas.

11

Exemplo: (¬ A ® B) Ú C

23 = 8

A B C ¬ A (¬ A ® B) (¬ A ® B) Ú CV V V F V VF V V V V VV F V F V VF F V V F VV V F F V VF V F V V VV F F F V VF F F V F F

w Existem fórmulas onde todas as linhas da T.V. dão verdade.w Elas são verdadeiras não importando os valores verdade que atribuímos aos

seus símbolos proposicionais.w Estas fórmulas são chamadas tautologias.w Da mesma forma, existem fórmulas que são sempre falsas, independente dos

valores verdade atribuídos aos seus símbolos proposicionais. Estas são chamadas contradições.

¨ Além disso, existem fórmulas que, embora diferentes, têm tabelas verdade que coincidem linha a linha. Tais fórmulas são ditas equivalentes.

Exemplos:

A A®AV VF V

A ® A é uma tautologia.

12

A B B®A A ® (B ® A)V V V VV F V VF V F VF F V V

A ® (B®A) é uma tautologia.

A B (A Ú B) ¬ (A Ú B) A Ù ¬ (A Ú B)V V V F FV F V F FF V V F FF F F V F

A Ù (Ø (A Ú B)) é uma contradição.

A B A Ù B Ø (A Ù B)V V V FV F F VF V F VF F F V

A B ØA ØB ØA Ú ØBV V F F FV F F V VF V V F VF F V V V

Ø (A Ù B) é equivalente a ØA Ú ØB.

Definição:a) Uma fórmula a é uma tautologia se e somente se, para toda atribuição v,

v(a) = V.b) Uma fórmula a é uma contradição se e somente se, para toda atribuição v,

v(a) = F.

Exemplos de tautologias “famosas”:· A Ú ¬ A· A ® A· (A ® ((A®B) ® B)· A Ù B ® A· A Ù B ® B· ¬ ¬ A ® A· A ® A Ú B

13

· B ® A Ú B· ((A ® B) Ù ¬ B) ® ¬ A

Exemplos de contradições:· A Ù ¬ A· ¬ (A ® A)· A Ù (A ® B) Ù ¬ B

Exercício:Verificar se estas fórmulas são realmente tautologias e contradições.

Definição:Duas fórmulas são ditas equivalentes se e somente se elas têm a mesma

tabela verdade, isto é, a º b (ou a Û b) se e somente se, para toda atribuição v, v(a) = v(b).

Exemplos de equivalências:· ¬ ¬ A º A· ¬ (A Ú B) º ¬ A Ù ¬ B

Exercício:

Verificar se as seguintes fórmulas são equivalentes:¬ (A Ù B) º ¬ A Ú ¬ B¬ (P ® Q) º (P Ù ¬ Q)P Ù (Q Ú R) º (P Ù Q) Ú (P Ù R)P ® Q º ¬ Q ® ¬ PP Ú (Q Ù R) º (P Ú Q) Ù (P Ú R)

Observação:

Utilizando a noção de equivalência, é possível definir alguns de nossos conectivos a partir de outros. Desse modo, mostraremos que uma linguagem contendo apenas a negação (Ø) e mais um conectivo qualquer ( Ù, Ú ou ® ) permite expressar exatamente o mesmo conjunto de proposições que a linguagem da lógica proposicional completa. Assim:

w Definir ® e Ù usando ¬ e Ú P ® Q º ¬ P Ú QP Ù Q º ¬ (¬ P Ú ¬ Q)

w Definir ® e Ú usando ¬ e Ù

P ® Q º ¬ (P Ù ¬ Q)P Ú Q º ¬ (¬ P Ù ¬ Q)

14

w Definir Ù e Ú usando ¬ e ®P Ù Q º ¬ (P ® ¬ Q)P Ú Q º ¬ P ® Q

Exercício: Verificar as equivalências acima.

Exercício: (Sheffer Stroke P/Q)

Suponha P/Q é uma fórmula com a seguinte T.V.:

P Q P/QV V FV F FF V FF F V

Defina Ù, Ú, ¬ , ® usando / Dica: ¬ P º (P/P)

P ¬ P P/PV F FF V V

15

Ä Dada uma tabela verdade, como saber a fórmula correspondente?

P Q R S aV V V V VF V V V VV F V V VF F V V FV V F V FF V F V FV F F V FF F F V FV V V F FF V V F FV F V F FF F V F FV V F F FF V F F FV F F F FF F F F F

Ä Como achar a?

Linhas em que a é verdadeira:P Q R S aV V V V V P Ù Q Ù R Ù SF V V V V ¬ P Ù Q Ù R Ù SV F V V V P Ù ¬ Q Ù R Ù S

(P Ù Q Ù R Ù S) Ú (¬ P Ù Q Ù R Ù S) Ú (P Ù ¬ Q Ù R Ù S)

Formalizando:Para achar a fórmula correspondente a uma tabela verdade, procedemos

da seguinte maneira:1. Para cada linha da tabela verdade em que a fórmula a é verdadeira,

escrevemos uma fórmula correspondendo à conjunção ( E ) das fórmulas atômicas que forem verdadeiras e das negações daquelas que forem falsas na linha considerada.

2. A fórmula a é a disjunção ( OU ) das fórmulas escritas no passo 1.

16

Definição:

1. Uma fórmula atômica ou átomo é qualquer símbolo proposicional.Ex: A, B, C.

2. Um literal é um átomo ou sua negação.Ex: A, ¬ A, B, ¬ C.

Definição:

a) Forma Normal Disjuntiva (FND): Uma fórmula a está na forma normal disjuntiva se e somente se a tem a

seguinte forma:a = C1 Ú C2 Ú ... Ú Cn

onde cada Ci = (Q1 Ù Q2 Ù ... Ù Qm), 1£ i £ n, e Qj, 1£ j £ m, são literais, isto é, cada Ci é uma conjunção de literais.

b) Forma Normal Conjuntiva (FNC): Uma fórmula a está na forma normal conjuntiva se e somente se a tem a

seguinte forma:a = D1 Ù D2 Ù ... Ù Dn

onde cada Di = (Q1 Ú Q2 Ú ... Ú Qm), 1£ i £ n e Qj, 1 £ j £ m, são literais, isto é, cada Di é uma conjunção de literais.

ALGORITMO: Converter fórmulas para a FNC:

passo 1: elimine o conectivo ® usando:A ® B º (¬ A Ú B)

¬ (A ® B) º (A Ù ¬ B)passo 2: mova a negação (¬) para o interior da fórmula, usando as

seguintes regras: ¬ ¬ A º A ¬ (A Ù B) º (¬ A Ú ¬ B) ¬ (A Ú B) º (¬ A Ù ¬ B)

passo 3: distribua as definições sobre conjunções usando:AÚ (B Ù C) º (A Ú B) Ù (A Ú C)(A Ù B) Ú C º (A Ú C) Ù (B Ú C)

Exemplo: (A Ù B) ® Cº ¬ (A Ù B) Ú Cº (¬ A Ú ¬ B Ú C) ð FNC

17

Exercício: Fazer um algoritmo para converter fórmulas para a forma normal

disjuntiva.

Definição:Seja a uma fórmula e G um conjunto de fórmulas:1. Uma atribuição de valor verdade v, P ® {V, F} satisfaz a se e somente

se v(a)= V. E v satisfaz G se e somente se v satisfaz cada membro de G.

2. G é satisfatível se e somente se existe uma atribuição v que satisfaz G. Caso contrário, G é insatisfatível.

Definição:Um argumento é uma seqüência de fórmulas a1, a2, ..., an, b onde ai,

1£ i £ n, são as premissas (banco de dados) e b é a conclusão (pergunta).

a1

a2 . . a n

b

Exemplo: João está em casa ou no trabalho.João não está no trabalho.

C: João está em casa.T: João está no trabalho.

C Ú T ¬ T

C

Colocando numa notação horizontal:

C Ú T, ¬T |= C

Um argumento pode ser logicamente válido ou inválido.

18

Definição:Um conjunto de fórmulas a1, a2, ..., an implica logicamente numa

fórmula b, a1, a2, ..., an |= b, se somente se para toda valoração v se v(a1Ù a2 Ù ... Ù an)= V, então v(b)= V.

Definição:Um argumento a1, a2, ..., an, b é válido se somente se a1, a2, ..., an

implica logicamente em b, isto é, a1, a2, ..., an |= b.

TEOREMA:Um argumento a1, a2, ..., an, b é logicamente válido, ou seja,

a1, a2, ..., an |= b se somente se (a1 Ù a2 Ù ... Ù an) ® b for uma tautologia.

Exemplo: (baseado no exemplo anterior)

(C Ú T) Ù ¬T ® C é tautologia Þ (C Ú T) Ù ¬T |= C

Complexidade

Dois problemas distintos:

Problema 1: Dada uma fórmula j com comprimento n e uma valoração v para os símbolos proposicionais. Calcular n(j,v).

Onde o comprimento de uma fórmula é o número de símbolos da fórmula, i.e., número de símbolos proposicionais + número de conectivos lógicos.

Função n(j,v): booleno

caso j = P onde P é um símbolo proposicional, retorna v(P);= Øj1 , retornar NOT n(j1,v);= j1 Ù j2 , retornar n(j1,v) AND n(j2,v);= j1 Ú j2 , retornar n(j1,v) OR n(j2,v);= j1 ® j2 , retornar NOT n(j1,v) OR n(j2,v);

Complexidade da função n(j,v) é O(n), pois a função é chamada uma vez para cada símbolo proposicional e uma vez para cada conectivo lógico.

Problema 2: Dada uma fórmula j com comprimento n e m símbolos proposicionais. Verificar se existe alguma valoração que satisfaz j.

19

Função SAT(j): booleno

para cada valoração v façase n(j,v) então retorna verdadeiro

retorna falso

Complexidade da função SAT(j)

número de valorações diferentes X complexidade de n(j,v) ˜ O(2m) X O(n) ˜ O(2m . n)

Obs. 1) problema 1 é polinomial no comprimento da fórmula;

2) problema 2 é NP completo.

20

II-3. Sistemas Dedutivos

Resumo: · linguagem · semântica

a1

BD ¦ BDÃ q an

w Queremos fazer perguntas q a um banco de dados BD.w Nós já temos um algoritmo para responder BDÆ q montando a tabela verdade para a1 Ù a2 Ù...Ù an® q. Se for uma tautologia responde SIM, senão responde NÃO.

w A complexidade deste algoritmo é da ordem de 2n , onde n é o número de símbolos proposicionais em a1 Ù a2 Ù...Ù an® q.

II-3.1. Dedução Natural

w Jakowski(1924) e Gentzen(1935)w Somente regras de inferênciaw Para cada conectivo lógico temos 2 regras:

Þ Regra de IntroduçãoÞ Regra de Eliminação

w Regra de Introdução: como uma fórmula contendo o conectivo pode ser inferida

w Regra de Eliminação: que conseqüências podemos tirar de uma fórmula contendo o conectivo

w Queremos escrever regras de inferência que sejam válidas, isto é, que as premissas impliquem logicamente nas conclusões.

Regras de inferência

P 1 , P 2 , ..., P n C

Se as premissas P1, P2, ..., Pn forem verdadeiras, então a conclusão C é verdadeira. P1, P2, ..., Pn à C

Ä a é uma regra válida? Não, pois a não implica logicamente a Ù Øa, a Ù ¬ a visto que esta fórmula é uma contradição.

21

Regras de Inferência:

Conjunção Ù

Ù-I a b a Ù b

Se aÎBD e bÎBD, então responda sim para a Ù b. BDÃ a Ù b.

Ä Ù I é válida? Se v(a) = v(b) = V então v(a Ù b) = V

Ù-E a Ù b a Ù b a b

Ä Ù E é válida? v(a Ù b) = V então v(a) = v(b) = V

Disjunção Ú

Ú-I a b aÚb aÚb

Ä É válida? Se v(a) = V então v(aÚb) = V

Ú-E1 a Ú b , ¬ a Ú-E2 a Ú b , ¬ b b a

Ä É válida? Se v(aÚb) = V e v(¬ a) = V então v(a) = F e v(b) = V

Ú-E3 a Ú b a ® s b ® s s

Ä É válida? Se v(aÚb) = V então temos 2 casos:1. v(a) = V Como a® s, então v(s) = V2. v(b) = V Como b® s, então v(s) = V

Exemplo:

Hoje é terça-feira Ú Hoje é quinta-feira.Se Hoje é terça-feira então aula de lógica.Se Hoje é quinta-feira então aula de lógica.

aula de lógica

22

Implicação ®

®E a a ® b Se v(a) = V então v(b) = V para que v(a® b) = V b

Exemplo:quinta-feirase quinta-feira então aula de lógica

aula de lógica

®I [a]1

¦ β . a® β1

Onde [a] é uma suposição

Exemplo:

BD: eq. Newton Se solto objeto então objeto cai.

eq. Newton 3 Suponho que solto objeto

Objeto cai? SIM

Se solto objeto então objeto cai

®I1 ¬ a ®I2 b . a® b a® b

Exemplo 1:

1. A Ù B2. A® C BD Ã D3. C® D

4. A ÙE(1)5. C ®E(2,4)6. D ®E(3,5)

23

Exemplo 2:

1. A® C BD Ã A ® D2. C® D

3. [A]1

4. C ®E(3,1)5. D ®E(4,2)

6. A® D1 ®I(3,5)

Negação Ø

¬ - I a ¬ - E1 ¬ ¬ a Redução ao Absurdo: [¬a]1

¬ ¬ a a ... a a1

¬ - E2 b ¬ b a

ÄResumindo:

w CONJUNÇÃO:Ù- I a b Ú - E a Ù b a Ù b a Ù b a a

w DISJUNÇÃO:Ú - I a b Ú - E1 a Ú b , ¬ a aÚb aÚb b

Ú - E2 a Ú b , ¬ b a

Ú - E3 [a]1 [b]2

. . . . . .

a Ú b s s s1,2

w IMPLICAÇÃO:®E a a ® b ®I [a]1

b ¦ b .

a® b1

®I1 ¬ a ®I2 b .

24

a® b a® b

w NEGAÇÃO:

¬ - I a ¬ - E1 ¬ ¬ a Redução ao Absurdo: [¬a]1

¬ ¬ a a ... a a1

¬ - E2 b ¬ b a

Exemplo:BD = {A Ù B } BDÃ AÚB ?

1. AÙB2. A Ù E1 (1)3. AÚB Ú I (2)

Definição:1. Uma prova em dedução natural de uma formula φ a partir de um conjunto de

fórmulas BD={ φ1, φ2, ... , φk} é uma sequência de fórmulas rotuladas da seguinte forma:

i as fórmulas do BD formam o prefixo da sequência e são rotuladas 1: φ1, 2: φ2, ..., k: φk;ii se a última fórmula da sequência é ρ.r: φi (onde ρ pode ser a sequência

vazia), então a próxima fórmula rotulada será:ii.1 ρ.r.1: φj se φi é uma suposição;ii.2 ρ.r+1: φj se φj foi obtida pela aplicação de regras do grupo I a

fórmulas no escopo igual superior a σ, onde ρ=σ.r;ii.3 σ.s+1: φj se φj foi obtida pela aplicação das regras do grupo II e ρ= σ.s;iv n: φ é a última fórmula da seqüência.

1. A fórmula φ é dita um teorema do conjunto de fórmulas BD, BDÃ φ.

4. A fórmula φ é dita um teorema lógico se BD é vazio.

OBS: Uma prova pode ser chamada algumas vezes de derivação.

Definição:1. Um conjunto de fórmulas G = {a1, a2,..., an} é inconsistente se

somente se GÃ β Ù ¬b para alguma fórmula β.2. Um conjunto de fórmulas G = {a1, a2,..., an} é consistente se

somente se ele não é inconsistente.

25

Notação:

Nós abreviaremos:G È a à b por G, aà bÆ Ã a por à a

Um teorema muito importante da lógica proposicional é o chamado teorema da dedução.

(META) TEOREMA DA DEDUÇÃO:

Seja G um conjunto de fórmulas e a e b, fórmulas. Então:

Se G, aà b então Gà a ® b.

Prova do (Meta)Teorema da Dedução:

Suponha G = {a1, a2, ... , an}.

a1 a1

a2 a2

BD G ... Reescrever BD G ...

an Þ an

a [a]1

Prova P ... Prova P: ... b b

a®b1

Se G (conjunto de fórmulas) e a (fórmula) pertencem ao um banco de dados (BD) e a partir desse BD temos uma prova P e chegamos a b aplicando as regras do Cálculo Dedutivo. Então se dado um BD = G, consegue-se provar que a partir de G , a implica em b. Para esta prova , basta supor A e aplicar as mesmas regras de dedução da prova anterior (Prova P). Dessa forma chega-se em b, e fechamos a suposição feita fazendo a®b.

26

META TEOREMA 2:

Se G Ã A ® B então G, AÃ B.

A1 A1

A2 G A2

BD G ... Reescrever BD ...

An Þ An

Prova P ... A _____ Prova P ... A®B

A ® B B

Se a partir de um BD formado por um conjunto de fórmulas G chegamos em a®b através de uma prova P, siginifica que se supormos a dentro desse BD, podemos chegar até b através do Cálculo Dedutivo.

Portanto, se a pertencer ao BD e usarmos o Cálculo Dedutivo, conse-guimos chegar até b.

Exercícios:

Prove por dedução natural as seguintes afirmações:

1. BD = {A® BÚ C, A® ¬ B, C® ¬ D } ; BD à A® ¬ D ?2. P Ù Q à Q Ù P ?3.à (PÙQ) ® (Q Ù P) ?4.Q à P®Q ?5. P® Q Ù R à (P®Q) Ù (P®R) ?6. P® (QÙR) à (PÙQ) ®R ?7. ¬ a Ù ¬ b à ¬ (aÚ b) ?8. P Ú Q ® R à P ® (Q®R) ?9. B, RÚ S ® A,R Ú S,A Ù R ® C, B Ù S ® C à C ?10.(P®Q) Ù (Q®R) à P®R ?11. P®R, Q® S à PÙQ ® RÙS ?12. A ÙB,(AÚB) ® (R®S),(P®Q) ® R, AÙP®Q à S ?13. P®Q,¬ Q à ¬P ?14.(P®Q) ®Q, Q®P à P ?15.à ¬ (aÚb)® ¬ a Ù ¬ b?

27

II-3.2. - Provador de Dov Gabbay

Um provador automático de teoremas dirigido pelo objetivo.

w Objetivo: Dado um banco de dados e uma pergunta (objetivo) p, nós queremos responder SIM ou NÃO para a pergunta p.

w 2 Métodos: · Tabela Verdade BD|= p (semanticamente);· Regras de Dedução Natural BDÃ p (sintaticamente).

Tabela Verdade é mecânico mas pouco eficiente.Dedução Natural requer criatividade.

w Nosso objetivo: Responder BDÃ p automaticamente.

Provador Automático de Teoremas Dirijido pelo Objetivo (pergunta) :

w Linguagem: Linguagem da lógica clássica proposicional + o símbolo ^ (absurdo)

Definição: Cláusula, Objetivo e Banco de Dados.

(i) Qualquer átomo (símbolo proposicional) , incluindo ^, é uma cláusula e também um objetivo.

(ii) Se G é um objetivo e q um átomo, então G®q é uma cláusula e também um objetivo.

(iii) Se G1 e G2 são objetivos, então G1ÙG2 é também um objetivo.(vi) Um banco de dados BD é um conjunto de cláusulas.(v) Nenhuma fórmula é uma cláusula a não ser as definidas em (i),(ii),(iii) e (vi).

Transformação de fórmulas em Cláusulas e Objetivos:

1. ¬a º (a®^)2. a Ú b º(a ®^) ® b3. a ® (b®s) º (a Ù b)®s4. a® (b Ù s) º (a®b) Ù (a®s)5. Se na transformação do BD obtenho a1 Ù a2 Ù ... Ù an , nós colocamos

a1 , a2, ..., an no BD.

28

Exemplo:¬A Ú B ® B Ù C

(A®^) Ú B ® B Ù C (Regra 1)(A®^)®^) ® B ® BÙC (Regra 2)(((A®^)®^) ® B ® B) Ù (((A®^)®^) ® B ® C) (Regra 4)

TEOREMA:Toda fórmula da lógica proposicional é equivalente (pode ser traduzida) a

uma conjunção de cláusulas.

Problema: BDà G?Problema Transformado: BDoà Go?

Regras de Computação:

1. Provar BDà aÙb, prove BDà a e BDoà b.

2. Provar BDà a ®b, prove BD,aà b. Se a for uma conjunção a=a1 Ù a2 Ù...Ù an, adicione a BD a1, a2,..., an.

3. Provar BDÃ q, onde q é um átomo, temos 4 casos: 3.1. q Î BD, responda SIM. 3.2. ^ Î BD, responda SIM. 3.3. s ®q Î BD, pergunte BDÃ s. 3.4. s ® ^ Î BD, pergunte BDÃ s.

4. Regra do Reinício (restart) Nosso problema inicial era mostrar BDÃ A. No meio da computação, nós

queremos perguntar BD’Ã C e continuar a prova. BD’Ã C se BD’Ã A, onde A é o objetivo inicial. (BD’: banco de dados modificado.)

5. Checagem de LOOP: Nunca pergunte BDÃ A pela 2a vez para ao mesmo BD e mesmo A.

29

Exemplos:

(1) (A®B),(B®C),A Ã C (A®B),(B®C),A Ã B Regra (3.3) (A®B),(B®C),A Ã A Regra (3.3) SIM ! Regra (3.1)

(2) A ® (B Ù C), DÙ F ® A, DÙ F Ã B Ù F A®B,A®C,(DÙF) ®A,D,F Ã BÙF Transformação do BD

BDÃ B Regra (1) BDÃ F Regra (1)BD Ã A Regra (3.3) SIM ! Regra(3.1)BD Ã D Ù F Regra (3.3)

BDÃ D Regra (1) BD Ã F Regra (1)SIM ! Regra (3.1) SIM ! Regra (3.1)

30

(3) BD={ (A®B) ® B C ? A ® C B ® C }

BDÃ C

(3.3)

BDÃ A BDÃ B

FALHA (3.3)

BDÃ A®B

(2)

BD,AÃ B

(3.3)

BD,AÃ A®B

(2)

BD,AÃ B è ENTRA EM LOOP. Usar a Regra do Reinício.

(4)

BD,AÃ C

(3.3)

BD,AÃ A

(3.1)

SUCESSO

31

(4) BD={ (P®Q) ® P} P ?

BDÃ P

(3.3)

BDÃ (P®Q)

(2)

BD,PÃ Q èFALHA Usar a Regra do Reinício.

(4)

BD,PÃ P

(3.1)

SUCESSO

Execícios:(1) (A®B)®BÃ (B®A)®A(2) (A®B)®BÃ AÚB(3) (ØA®A)Ã A(4) (A®B)Ã (CÚA)®(CÚB)(5) AÃ AÚB(6) A®B,ØBÃ ØA(7)Ã AÚ(A®B)(8) (AÚB)ÚCÃ AÚ(BÚC)

32

II-3.3. Método de Tableau

As deduções são feitas por refutação, i.e., se queremos deduzir a a partir de um

banco de fórmulas BD, BD ½¾ a, partimos da negação de a e tentamos chegar

no absurdo.

As deduções têm forma de árvore.

Regras:

R1 αÙβ R2 αÚβ

α α β

β

R3 α ® β R4 ØØα

Øα β α

R5 Ø (αÙβ) R6 Ø (αÚβ)

Ø α Øβ Øα

Øβ

R7 Ø (α®β)

α

Øβ

33

exemplo 1: {A ® B, B ® C} ½¾ A ® C

A ® B

B ® C

Ø (A ® C)

A

ØC

ØB C

ØA B

Cada ramo corresponde a uma valoração que satisfaz a fórmula, por isso é

chamado Tableau Semântico.

Não é completo, mas é refutacionalmente completo.

Definição: Um ramo q de um tableau t é dito fechado se ele contiver a e Øa

para qualquer fórmula a.

Definição: Um tableau t é dito fechado se cada um dos seus ramos for fechado.

E aberto caso contrário.

34

exemplo: A Ú B ½¾ Ø(ØA ÙØB)

A Ú BØØ(ØA ÙØB)

(ØA ÙØB)

ØA

ØB

A B

Este tableau é fechado, pois todas as valorações são contraditórias, logo

A Ú B e Ø(ØA ÙØB) não é satisfatível.

Teorema (Completude): se BD ½= a então existe tableau fechado para BD, Øα.

Teorema (Completude): se existe um tableau fechado para BD, Øα., então BD

½= a.

Exercícios:

1. A ® B, Ø (A Ú B) ½¾ Ø(C ® A)

2. (P ®Q), Ø(P «Q) ½¾ ØP

3. Guga é inteligente. Guga é determinado. Se Guga é determinado e atleta

então ele não é um perdedor. Guga é atleta se ele é amante do tênis.

Guga é amante do tênis se é inteligente. Guga não é um perdedor?

35

4. (P ® (R ® Q)), (P ® R) ½¾ (P ® Q)

5. ØA Ú B, Ø(B Ú ØC), C ®D ½¾ ØA Ú D

II-3.4. Sistema Axiomático

w Outro sistema dedutivo.w Mais antigo e mais utilizado para fins teóricos.w Frege, Russel, Hulbert.

Sejam a, b e g fórmulas quaisquer da linguagem proposicional.

Axiomas Lógicos:

· Implicação:(1) a ®(b®a)(2) (a ®(b®g)) ®((a ® b ® a ®g

· Conjunção: a Ù b ® a a Ù b ® b a ® b ® a Ù b

· Disjunção:(6) a ® a Ú b b ® a Ú b a ® g Ù b ® g ® a Ú b ® g

· Negação:(9) a ® ØØa ØØa ® a a ® b ® a ® Øb ® Øa

· Regra de Inferência: Modus Pones (M.P.) a a®b

b

w Nosso cálculo dedutivo possui um conjunto infinito de axiomas lógicos. Para cada fórmula a b e g nós temos axiomas diferentes.w (1),...,(11) são chamadas de axiomas esquema.w A única regra é a Modus Pones (M.P.).

36

Definição:Uma fórmula a é dita um teorema de um conjunto de fórmulas G (GÃ a)

se e somente se existe uma seqüência de fórmulas a1,...,an tal que an = a e cada ai

é:(i) uma instância de um axioma esquema;(ii) ou for obtida por M.P. aplicada a al e ak e l, k < i.(iii) ou um membro de G.

A seqüência de fórmulas a1,...,an é chamada de uma prova de a a partir de G.

Exemplos:(1) G = {A Ù B, A ® C} CÚ D ?1. AÙB ® A axioma 32. AÙB G3. A M.P.(1,2)4. A ® C G5. C M.P.(3,4)6. C ®(C Ú D) axioma 67. C Ú D M.P.(5,6)

(2) Ã A ® A1. A ®((A® A)® A) axioma 12. (A ®((A ® A) ® A)) ® ((A ® (A ® A)) ® (A ® A)) axioma 23. (A ® (A ® A)) ® (A ® A) M.P.(1,2)4. A ® (A ® A) axioma 15. A ® A M.P.(4,3)

Exercícios:

Provar usando o Método Axiomático:

1) A® B, B ® C |- A ® C2) (A Ú B )® C |- A ® ( B Ú C )3) A ® (B Ú C) |- (A ® B) Ú ( A ® C)

Observação:

É importante notar ( e possível provar ) que os três métodos dedutivos estudados para a lógica clássica proposicional são equivalentes, ou seja, uma afirmação que pode ser provada utilizando um deles, sempre poderá ser provada utilizando qualquer dos outros. Isso é importante, na medida em que nos permite provar uma determinada propriedade dos sistemas dedutivos em geral, provando-a apenas para o método axiomático, que embora difícil de ser usado na prática para provar um teorema, é bastante simples no que diz respeito à sua construção, o que facilita a demonstração de propriedades teóricas, como a completude e a corretude, que veremos na próxima seção.

37

II-4. Relações entre Sintaxe e Semântica

Uma das aspectos mais importantes da lógica proposicional é a maneira como a sintaxe se relaciona com a semântica.

SEMÂNTICA SINTAXEValor verdade prova/dedução

valida teoremaimplica logicamente G |= a GÃ a

tabela verdade cálculo dedutivo

Nós queremos relacionar o fato de uma fórmula a ser um teorema de um conjunto de fórmulas G ( GÃ a) com a propriedade de G implicar logicamente em a (GÆ a).

Teorema da Corretude

“Tudo que o cálculo dedutivo prova é semanticamente válido.”Se GÃ a então GÆ a

Se uma fórmula é provada a partir de um conjunto de fórmulas então ela é logicamente implicada por este conjunto de fórmulas.Este teorema nos assegura que tudo que provamos no sistema dedutivo é correto em relação à semântica. Isto é, nosso sistema dedutivo só prova teoremas que semanticamente estão corretos.

Como se prova:1) Prova-se que os axiomas do cálculo dedutivo são semânticamente válidos, isto é, são tautologias;2) Prova-se que as regras de inferência sempre derivam conclusões verdadeiras a partir de premissas verdadeiras.

Teorema da Completude

“Tudo que é semânticamente válido é provado pelo cálculo dedutivo.”Se GÆ a então GÃ a

Se G implica logicamente em a então existe uma prova de a a partir de G no sistema dedutivo.O sistema dedutivo é completo em relação à semântica pois para toda fórmula a que é logicamente implicada por G existe uma prova a a partir de G no sistema dedutivo.Tudo que é semanticamente obtido pode ser também obtido no sistema dedutivo.

GÆ a \ a é conseqüência lógica de GÞ Toda atribuição de valores verdade que satisfaz G também satisfaz a.

38

Sendo G = { a1, ..., an }Quero provar que se Æ (a1 Ù ... Ù an) ® a então à (a1 Ù ... Ù an) ® a

Como se prova:

1a solução : Basta provar que o nosso sistema dedutivo é capaz de provar todas as tautologias.Problema: O número de tautologias é infinito.

2a solução: Modelo Canônico

Se GÆ a então GÃ aÛ

Se G È {a} é consistente então G È {a} é satisfatível

Prova do Modelo Canônico:

1. Suponha que se GÆ a então GÃ a.2. Suponha que G é consistente.3. Suponha, por contradição, que G é insatisfatível.4. Se G é insatisfatível, então, por definição, não existe nenhuma atribuição de valores verdade que seja tal que "aÎG, u(a)=V. Sendo assim, podemos dizer que GÆ a e GÆ Øa.5. Mas isso nos permite escrever, pela suposição em (1) que GÃ a e GÃ Øa6. A partir de (5) podemos escrever que GÃ a Ù Øa 7. Ora, (6) contradiz o fato, que havíamos suposto verdadeiro, de que G é consistente.Assim, por contradição, podemos afirmar que:

Se GÆ a então GÃ aÞ

Se G È {a} é consistente então G È {a} é satisfatível

Vamos agora provar a implicação contrária:

1. Suponha que se G é consistente então G é satisfatível.2. Suponha GÆ a3. Suponha, por contradição, que Ø(GÃ a) 4. Então G È {Øa} é consistente (já que Ø(GÃ a), não poderá GÃ a ÙØa)5. Então, pela suposição (1), G È {Øa} é satisfatível. 6. Logo, existe uma valoração u que satisfaz G È {Øa}.7. Mas isto é uma contradição, pois por (2) u satisfaz a também.

Observações:

39

· Um conjunto de fórmulas G é consistente se e somente se Ø(G Ã a ÙØa) · Uma valoração s é um modelo para G = { a1, ... , an } se e somente se s(ai)=V

para todo ai Î G.· Pelo modelo canônico, para provar a completude basta mostrar que todo

conjunto consistente de fórmulas é satisfatível.

Prova do Teorema da Completude:

Dado um conjunto de fórmulas consistente G, nós precisamos construir uma valoração s’ e mostrar que s’ satisfaz G.

1o passo: Estender o conjunto consistente G para um conjunto D satisfazendo as seguintes condições:a) G Í Db) D é maximal e consistente, isto é, para toda fórmula a da linguagem, ou aÎD ou ØaÎD.

2o passo: Seja L a linguagem proposicional e F o conjunto dos símbolos proposicionais .

Vamos construir uma valoração /modelo que satisfaz G a partir de D.

s : F ® {V,F} para todo símbolo proposicional A Î F.s(A) = V se A Î Ds(A) = F se A Ï D

Nós podemos estender s para um s’ que valorize fórmulas,s’: L ® {V,F}. ( Como definido em aulas anteriores)

Lema da VerdadeSeja G um conjunto de fórmulas e a uma fórmula. s’(a) = V Û a Î D

Prova do Lema da Verdade:

Por indução, sobre o comprimento da fórmula, isto é, no número de símbolos lógicos nela contidos (Ø,Ú, etc).a) Caso base:

|a|=0 (Fórmula Atômica)aÎF, a = As’(A) = s(A) = V Û A Î D (pela definição de s)

b) Hipótese de Indução: o lema vale para fórmula de tamanho |a|£ n.

c) Queremos mostrar que vale para |a|= n+1Considere |a|= n+1

Temos então vários casos:

40

i) a = Øbs’(Øb) = V sse s’(b) = F (definição de s’)

sse bÏD (pela hipótese de indução)Logo, Øb Î D (pois a é maximal)Logo a é V sse a Î D.

ii) a = b®gs’(b®g)= V sse s’(b)= F Ú s’(g)= V

sse b Ï D Ú g Î D sse Øb Î D Ú g Î D sse D Ã Øb Ú g sse D Ã b ® g, pois D Ã (Øb Ú g) « (b ® g) sse (b ® g) Î D, pois D é consistente.

Observação: os casos iii e iv são similares e ficam como exercício.iii) a = bÙgiv) a = bÚg

Vamos agora, a partir do lema demonstrado, provar o Teorema da Completude:

1. Suponha G é consistente.2. Estenda G para D maximal e consistente.3. Construir s e s’4. Seja G = { a1, ..., an }. Como G Í D, ai Î D Û s’(ai)= V, para todo i (pelo “lema da verdade”).5. Logo, s’ satisfaz G e portanto G é satisfatível.

41

III. Lógica Clássica de Primeira Ordem

"x, Emp_UFRJ(x) ® Func_Pub(x)"x $y, Suc(y,x)

w Formaliza o raciocínio dedutivo.w Lógica Proposicional é um modelo muito restrito:

Não podemos descrever propriedades sobre os elementos do universo de discurso: todos os elementos do domínio têm propriedade P; existem elementos do domínio que têm a propriedade P; não podemos representar relações e funções.Ex: Teoria dos Números < 0, suc, <, +, . , -,... >

III.1 Linguagem da Lógica Clássica de Primeira Ordem

Linguagem: alfabeto + regras gramaticais

Definição: Um alfabeto de 1a ordem consiste dos seguintes conjuntos de símbolos:

èSímbolos Lógicos:1. Conectivos lógicos: Ù, Ú, ®, «, Ø, ", $.2. Símbolos auxiliares: ( e ).3. Conjunto enumerável de variáveis: V = { v1,v2,...}

èSímbolos não Lógicos:4. Conjunto enumerável de constantes: C = {c1,c2...}5. Conjunto enumerável de símbolos de função: F = {f1,f2,...}

A cada símbolo funcional está associado um número inteiro n > 0, chamado de aridade.

6. Conjunto enumerável de símbolos predicativos (Predicados): P= {P1,P2,...}

A cada símbolo predicativo está associado um número inteiro n > 0, chamado aridade.

Variáveis: representam elementos quaisquer do domínio.Constantes: dão nome a elementos particulares do domínio.Funções: representam operações sobre elementos do domínio.Predicados: representam propriedades ou relações entre elementos do domínio." Quantificador universal: “para todo elemento do domínio”.$ Quantificador existencial: “existe ao menos um indivíduo”.

Exemplo: "x ($y ANCESTRAL(y,x) Ù ANCESTRAL(João,José))

42

Definição:Os termos da linguagem de 1a ordem são definidos recursivamente como:

(i) toda variável e constante é um termo;(ii) se t1, t2, ..., tn são termos e f um símbolo funcional de aridade n,

f(t1,t2,..., tn) é um termo;(iii) nada mais é termo.

Definição:As fórmulas da lógica de 1a ordem são definidas recursivamente como:

(i) Se P é um predicado de aridade n e t1, t2, ..., tn são termos, então P(t1,t2,..., tn) é uma fórmula chamada fórmula atômica;

(ii) Se a e b são fórmulas, então (¬ a), (a Ù b), (a Ú b), (a ® b) também são fórmulas;

(iii) Se a é uma fórmula e x uma variável, então "x a e $x a também são fórmulas;

(iv) Nada mais é fórmula.

Observações: 1. a « b º (a ® b) Ù (b ® a)

2. Convenções:(i) x, y, z, ... Variáveis;(ii) a, b, c, ... Constantes;(iii) f, g, h, ... Funções;(iv) A, B, C, P, U... Predicados.

3. ¬ $x GOSTA(x, collor) º "x ¬ GOSTA(x, collor)

Exercícios: Nos exercícios seguintes, represente cada proposição na linguagem da lógica de primeira ordem, especificando em cada caso o significado dos símbolos não lógicos utilizados.

1. Todo cachorro é um animal. Todo animal morre. Rex é um cachorro.

2. Qualquer pessoa passando nos exames de história e ganhando na loteria é feliz. Porém qualquer pessoa que estuda ou tem sorte pode passar em todos os exames. João não estudou, mas ele tem sorte. Qualquer pessoa que tem sorte ganha na loteria. João é feliz?

3. Toda pessoa que não é pobre e é esperta é feliz. Pessoas que lêem não são burras. João sabe ler e é rico. Pessoas felizes têm vidas excitantes. Existe alguém que tem vida excitante?

4. Ninguém conquistou o mundo. Portanto, todo mundo é livre.

43

5. Todo elétron tem carga negativa. Nenhum pósitron tem carga negativa. Portanto, nenhum pósitron é um elétron.

6. Se Jane está doente, ela não virá trabalhar. Se ela não vier trabalhar, nenhum de nós terá nada para fazer. Assim, se Jane está doente, nenhum de nós terá nada para fazer.

Exemplo: Conselheiro Financeiro:

1. Função: ajuda a decidir se devemos investir em investimentos tipo poupança ou no mercado de ações.

2. O investimento recomendado depende do ganho mensal da pessoa e quanto ela tem em poupança.

3. Pessoas com valor inadequado de poupança devem sempre aumentar o valor da poupança como 1a prioridade, independente do seu ganho.

4. Pessoas com valor adequado de poupança e um ganho adequado devem considerar um investimento mais arriscado, porém mais lucrativo no mercado de ações.

5. Pessoas com ganho inadequado e com poupança adequada podem considerar em dividir o valor a ser investido entre poupança e mercado de ações. Isto aumenta a poupança e tenta aumentar o ganho.

6. Poupança adequada se valor poupado maior do que 5.000 x no de dependentes.

7. Ganho adequado se valor ganho maior do que 15.000 + (4.000 x no de dependentes) e é estável. Um ganho instável, mesmo que grande, é sempre inadequado.

TOTAL_POUP(x): x é total na poupança.DEPEND(y): número de dependenteminpoup(y): função que retorna o valor da poupança mínima (5.000) vezes o

número de dependentesTOTAL_GANHO(x, estável): ganho total é x e este é estável.minganho(y): função que retorna o valor do ganho mínimo mais o acréscimo

por dependente.MAIOR(x,y): x > yPOUP(status): status é uma variável que indica a situação (adequada/inadequada)

da poupança.GANHO(status): aqui, status indica a situação (adequada/inadequada) do ganho.INVEST(tipo): tipo é uma variável que guarda o tipo de investimento

recomendado (poupança/combinado/ações)

Especificação:

1. POUP(inadequado) ® INVEST(poupança)2. POUP(adequado) Ù GANHO(inadequado) ® INVEST(combinado)3. POUP(adequado) Ù GANHO(adequado) ® INVEST(ações)4. "x TOTAL_POUP(x) Ù $y (DEPEND(y) Ù MAIOR(x, minpoup(y))) ®

POUP(adequado) onde minpoup(x) = 5.000x

44

5. "x TOTAL_POUP(x) Ù $y (DEPEND(y) Ù ¬ MAIOR(x, minpoup(y)) ® POUP(inadequado)

6. "x TOTAL_GANHO(x, estável) Ù $y (DEPEND(y) Ù MAIOR(x, minganho(y))) ® GANHO(adequado)

7. "x TOTAL_GANHO(x, estável) Ù $y (DEPEND(y) Ù ¬ MAIOR(x, minganho(y))) ® GANHO(inadequado)

8. "x TOTAL_GANHO(x, instável) ® GANHO(inadequado)

Entrada:9. TOTAL_POUP(22.000)10. TOTAL_GANHO(25.000, estável)11. DEPEND(3)

Exercício: Qual a saída produzida pela especificação acima para a entrada dada?

45

III.2 - Sistemas Dedutivos:

w Sistemas dedutivos para lógica de primeira ordem.

Definição:Dizemos que uma variável x ocorre livre em uma fórmula a se somente

se:(i) a é uma fórmula atômica e x ocorre em a;(ii) a é uma fórmula da forma b Ù g, b Ú g, b ® g e x ocorre livre em b

ou g;(iii) a é uma fórmula da forma ¬ b e x ocorre livre em b;(iv) a é uma fórmula da forma "yb ou $yb e x ocorre livre em b e x ¹ y.

Exemplos: Ä x ocorre livre?

1. P(x,y) SIM2. "y( P(x,y) Ù Q(y,x) ® R(y) ) SIM3. "y( "x(P(x) ® Q(y)) ® R(x) ) SIM4. "y "z ( ("xP(x,y) ® Q(z)) Ù (Q(x) ® R(x,y)) ) SIM5. P(z,y) NÃO6. "y $x ( P(x,y) ® Q(y) ) NÃO

Definição:Uma fórmula a é uma sentença (ou uma fórmula fechada) se somente se

a não tem nenhuma variável ocorrendo livre.

Definição:Seja a uma fórmula, x uma variável e t um termo. Pela substituição de x

por t em a (a(x/t)) entendemos a expressão resultante da troca de todas as ocorrências livres de x por t.

Exemplos:

1. "y(P(x, y,f(x, y))) ® Q(g(x), h(g(x)) x/h(a) "y(P(h(a), y, f(h(a), y)) ® Q(g(h(a), h(g(h(a))))

2. "y("x(Q(x, y, g(z)) ® P(f(x), y))) ® R(y(g(x))) x/f(z) "y("x(Q(x, y, g(z)) ® P(f(x), y))) ® R(y(g(f(z))))

3. [ "y(P(x, y, f(x,y))) ® Q(y,z) x/g(z) ] z/a "y (P(g(z), y, f(g(z), y)) ® Q(y, z) z/a "y (P(g(a), y, f(g(a), y)) ® Q(y, a)

46

Definição:Denotaremos por:

a(x1, x2, ..., xn) (x1/t1, x2/t2, ..., xn/tn)a substituição simultânea (paralelo) de todas as ocorrências livres de x1, ..., xn por t1, ..., tn respectivamente.

OBS: a(x1/t1) ... (xn/tn) é em série da esquerda para direita. a (x1/t1, x2/t2, ..., xn/tn) é em paralelo.

Exemplos:

1. P(x, f(y), g(x,y)) (x/a, y/b) P(a, f(b), g(a,b))

2. ("y"xP(x,y)) ® Q(g(x)) Ù R(h(y)) (x/f(a), y/z) ("y"xP(x,y)) ® Q(g(f(a))) Ù R(h(z))

3. P(x,y,f(x,z)) (x/g(z), z/y, y/a) P(g(z), a, f(g(z),y)

4. P(x,y,f(x,z)) (x/g(z)) (z/y) (y/a) P(g(z),y,f(g(z),z)) (z/y) (y/a) P(g(y),y,f(g(y),y)) (y/a) P(g(a),a,f(g(a),a))

Definição:Uma variável x é substituível em uma fórmula a por um termo t se, para

cada variável y ocorrendo em t, não existe nenhuma subfórmula de a da forma "yb ou $yb onde x ocorre livre em b.

O que queremos evitar com esta condição é que o quantificador "y ou $y capture alguma variável de t.

Exemplo:("y CHEFE(x,y) ® GERENTE(x)) x/y("y CHEFE(y,y) ® GERENTE(y))

47

III-2.1. Dedução Natural:

wRegras para Ù,Ú,®,Ø são as mesmas do caso proposicional.w Regras do Quantificador Universal:

"elim - " x a Condição: x é substituível em a por t a(x/t)

"int - a(a) Condição: a não ocorre em nenhuma fórmula do BD e "xa(x) nem em nenhuma suposição em aberto.

wRegras para o Quantificador Existencial:

$ int - a (a) Leitura: Se temos a(a) para um certo elemento a, então $xa(a/x) existe um x (o próprio a) tal que a(x), isto é, $xa(x).

$ elim - [a(x/a)] Condição: a não ocorre em $xa(x), b ... ou em qualquer suposição na qual b

$ x a (x) b depende, a não ser a(x/a). bLeitura: Se temos $xa(x), então seja a o elemento que satisfaz $xa(x). Se supondo um a genérico nós chegamos em b é porque de $xa(x) nós temos b.

Exemplo 1: "x"yP(x,y)®"y"xP(x,y)

1.["x"yP(x,y)]1 2."yP(a,y) "elim13.P(a,b) "elim24."xP(x,b) "int35."y"xP(x,y) "int46."x"yP(x,y)®"y"xP(x,y)1 ®I(1,5)

Exemplo 2: "x(Q(y)®P(x))®(Q(y)®"xP(x))

1. ["x(Q(y)®P(x))]1

2. Q(y)®P(a) "elim13.[ Q(y)]2 4. P(a) ®E(2,3)5."xP(x) "int46. (Q(y)®"xP(x)2 ®I(3,5)7. "x(Q(y)®P(x))®(Q(y)®"xP(x))1 ®I(1,6)

48

Exemplo 3:1."x"yP(x,y) 2."x"y(P(x,y)®Q(x)ÙR(y)) (deduz) $xT(x) ? 3.$xR(x)Ù"xQ(x)®$x(S(x)ÙT(x))

4."yP(a,y) "elim15.P(a,b) "elim46."y(P(a,y)®Q(a)ÙR(y)) "elim27.P(a,b)®Q(a)ÙR(b) "elim68.Q(a)ÙR(b) ®E(5,7)9.Q(a) ÙE(8)10."xQ(x) "int911.R(b) ÙE(8)12.$xR(x) $int1113.$xR(x) Ù "xQ(x) ÙI(10,12)14.$x(S(x) Ù T(x)) ®E(13,3)15.[S(a) Ù T(a)]1

16.T(a) ÙE(15)17.$xT(x) $int1618.$xT(x)1 $elim(14,15,17)

49

III.2.2-Método Axiomático:

wOs conectivos Ù,Ú,®,Ø são definidos pelos mesmos axiomas esquema da Lógica Proposicional.

Axiomas Lógicos:

· Implicação:(1) a ®(b®a)(2) (a ®(b®g)) ®((a ® b ® a ®g

· Conjunção: a Ù b ® a a Ù b ® b a ® b ® a Ù b

· Disjunção:(6) a ® a Ú b b ® a Ú b a ® g Ù b ® g ® a Ú b ® g

· Negação:(9) a ® ØØa ØØa ® a a ® b ® a ® Øb ® Øa

wQuantificador Universal:(12) "xa®a(x/t), onde x é substituível por t em a; ("-elim)(13) (a®b)®(a®"xb), onde x não ocorre livre em a; ("-introd)(14)$xa(x)«Ø"xØa(x) por definição

Exemplo 1: 1."xP(x) 2."x((P(x) Ù Q(x))®R(x)) Ã "yR(y) ? 3."x Q(x) 4."xP(x)®P(y) axioma 12 x/y5.P(y) MP(1,4)6."xQ(x)®Q(y) axioma 12 x/y7.Q(y) MP(3,6)8.P(y)®(Q(y)®(P(y)ÙQ(y))) axioma 5 9.Q(y)®(P(y) Ù Q(y)) MP(5,8)10.P(y) Ù Q(y) MP(7,9)

50

11."x((P(x) Ù Q(x))®R(x))®((P(y) Ù Q(y))®R(y)) axioma12 x/y12.(P(y) Ù Q(y))®R(y) MP(2,11)13.R(y) MP(10,12)14.R(y)®("xP(x)®R(y)) axioma115."xP(x)®R(y) MP(13,14)16("xP(x)®R(y))®("xP(x)®"yR(y)) axioma1317."xP(x)®"yR(y) MP(15,16)18."yR(y) MP(1,17)

OBS: As noções de prova, teorema e a relação de derivabilidade GÃ a são análogas às da Lógica Proposicional.

51

III.3. Semântica:

ÄRevisão da Semântica da Lógica Proposicional:

Maria foi ao cinema. Se ela foi ao cinema então ela comprou pipoca e assistiu ao filme. Se ela comprou pipoca então ela tem dinheiro ou ela pegou emprestado com João. Se ela pegou emprestado com João então João tem dinheiro.

C: Maria foi ao cinema.P: Maria comprou pipoca.F: Maria assistiu ao filme.D: Maria tem dinheiro.E: Maria pegou dinheiro emprestado com João.J: João tem dinheiro.

CC ® P Ù FP ® D Ú EE ® J

v(C) = F Não é um modelo para o conjunto de fórmulas, pois nãov(P) = V satisfaz todas as fórmulas.v(D) = v(E) = Fv(J) = V

v(C) = V É um modelo.v(P) = Vv(F) = Vv(D) = Fv(E) = Vv(J) = V

v(C) = V É um modelo.v(P) = Vv(F) = Vv(D) = Vv(E) = Fv(J) = F

w A semântica da lógica de primeira ordem tem como objetivo atribuir significados às fórmulas da linguagem.w Uma fórmula só tem significado quando uma interpretação é dada a seus símbolos não lógicos.

52

Ä"x(Q(x)®P(x)) é verdadeira ou falsa?

Nós só podemos dizer se esta fórmula é V ou F se interpretarmos seus símbolos não-lógicos.

Primeiro, precisamos saber qual o universo em que as variáveis estão quantificando. Por exemplo: números inteiros, números reais, pessoas...

Depois, precisamos interpretar os predicados, funções e constantes.

Exemplo: "x(Q(x)®P(x))

Interpretação: ·universo: pessoas ·predicados: Q: é funcionário da UFRJ.

P: é funcionário público.

QI PI

João João JoséJosé José JoãoPedro Pedro

U

Estrutura

"x(Q(x)®P(x)) é verdadeira na interpretação acima.

Exemplo 2:U={João, José, Pedro}QI = { <João>,<José>}PI = {<José>,<Pedro>}

"x(Q(x)®P(x)) é falsa nesta interpretação.

Exemplo 3: "x(Q(x)®P(x))U = Z (inteiros)QI = { <0>,<1>,...} (naturais)PI = {...<-2>,<-1>,<0>,<1>,<2>,...} (inteiros)

"x(Q(x)®P(x)) é verdadeira nesta interpretação.

Exemplo 4: $x(P(x) Ù Q(x,c))U = R (reais)QI = x > cPI = x é racionalcI = 0“Existe algum número real que também é racional e maior do que zero.

Exemplo 5: "x(P(x) Ù Q(x) ® R(x,f(c)))

53

U = Z (inteiros)cI = 0f I = x +1QI ={<2>,<4>,<6>,...}PI = {<1>,<2>,<3>, ...}RI = x > y

“Todo número inteiro positivo e par é maior do que 1.” (verdadeiro)

Exemplo 6: "x(P(x) Ù Q(x) ® R(x,f(c)))U = Z (inteiros)cI = 4f I = x +1QI ={<2>,<4>,<6>,...}PI = {<1>,<2>,<3>, ...}RI = x > y

“Todo número inteiro positivo e par é maior do que 4.” (falso)

Exemplo 7: ("yC(x,y)) ® G(x)U = {José,João,Pedro,Paulo}C : x é chefe de y G : x é gerente

CI GI

João José JoãoJoão Paulo PedroJoão PedroJoão JoãoPaulo JoãoPaulo PauloPaulo PedroPaulo JoséPedro José

x = João Vx = José V x = Pedro Vx = Paulo F

54

w Em geral, para sabermos se uma fórmula é verdadeira ou falsa, nós precisamos saber o universo e interpretar cada símbolo não-lógico neste universo.

(1) Interpretar variáveis livres e constantes em elementos do domínio.(2) Interpretar predicados em relações entre elementos do domínio.(3) Interpretar funções em funções sobre o domínio.

Def inição: Definimos uma interpretação como sendo um par ordenado <D,I> onde D é um conjunto não-vazio de indivíduos chamado domínio. E V é uma função chamada de função de interpretação, definida como:

1.I associa a cada variável livre x um elemento do domínio dI Î D. I(x) = dI

2.I associa a cada constante c, um elemento do domínio cI Î D. I(c) = cI

3.I associa a cada símbolo funcional n-ário f uma função n-ária fI : Dn ® D tal que I(f(t1,...,tn)) = f I(I(t1),...,I(tn)), onde t1,...,tn são termos.

4.I associa a cada símbolo predicativo n-ário P uma relação n-ária sobre D.I(P) = PI PI Í DI

Definição:Seja L uma linguagem de primeira ordem e a e b, fórmulas de L, t1,...,tn

termos, P um símbolo predicativo n-ário e <D,I> uma interpretação. Definimos a função de avaliação de fórmulas de L como:

VI : W ® {V,F}, onde W é o conjunto de fórmulas, tal que:

(1) VI(P(t1,...,tn)) = V se somente se <I(t1),...,I(tn)>Î PI F caso contrário.

(2) VI(Øa) = V se VI(a) = F F caso contrário.

(3) VI(a Ù b) = V se VI(a) = V e VI(b) = V F caso contrário.

(4) VI(a Ú b) = F se VI(a) = F e VI(b) = F V caso contrário.

(5) VI(a ® b) = F se VI(a) = V e VI(b) = F V caso contrário.

55

(6) VI("xa) = V se somente se para todo d Î D, VI(a) = V F caso contrário.

(7) VI($xa) = V se para algum d Î D, VI(a) = V F caso contrário.

Definição:Seja L uma linguagem de 1a ordem. I uma interpretação para L, G um

conjunto de fórmulas de L e a uma fórmula.

1. I satisfaz a (Æ Ia) se somente se VI(a) = V;2. I satisfaz G se somente se satisfaz cada membro de G;3. G é satisfatível se somente se existe uma interpretação I que satisfaça G;4. a é válida (Æ a) se somente se para toda interpretação I , Æ Ia, i.e., VI(a) = V para todo I; (*válida é equivalente a tautologia*)5. G implica logicamente em a (GÆ a) se somente se para toda interpretação I, se I satisfaz G, então I satisfaz a;6. G é insatisfatível se somente se G não é satisfatível, i.e., não existe uma interpretação I que satisfaz G;(7) Uma interpretação I que satisfaz G é dita modelo para G.

Exemplo 1: "x(P(x) ® E(x,s(x))Esta fórmula é satisfatível?

Interpretação: D = { João, José, Pedro, 0,100, 200}P : pessoasE : empregados : salário

pessoas empregado salárioJoão João 100 José 100José José 200 João 200

Pedro 0 ... ...

OBS: As funções têm que ser totais,i.e., devem retornar algum valor pertencente ao domínio a cada elemento do domínio.

VI("x(P(x) ® E(x,s(x))) = ?· Para todo d Î D: d = João

VI(P(João)) = V VI(E(João,200)) = F Þ VI("x(P(x) ® E(x,s(x))) = F

56

* Trocando os valores na tabela de salário:salárioJosé 200João 100... ...

· Para todo d Î D: d = João

VI(P(João)) = V VI(E(João,100)) = V Þ VI("x(P(x) ® E(x,s(x))) = V d = José

VI(P(José)) = V VI(E(José,200)) = V Þ VI("x(P(x) ® E(x,s(x))) = V d = Pedro VI(P(Pedro)) = F VI(E(Pedro,...)) = ? Þ VI("x(P(x) ® E(x,s(x))) = V d = 0

VI(P(0)) = F VI(E(0,...)) = ? Þ VI("x(P(x) ® E(x,s(x))) = V d = 100

VI(P(100)) = F VI(E(100,...)) = F Þ VI("x(P(x) ® E(x,s(x))) = V d = 200

VI(P(200)) = F VI(E(200,...)) = F Þ VI("x(P(x) ® E(x,s(x))) = V

Exemplo 2: "x(P(x) Ù $yQ(x,y))

não satisfaz satisfazD = {0,1} D = {0,1}PI = {<0>} PI = {<0>,<1>}QI = {<0,1>} QI = {<0,1>,<1,0>}

Exemplo 3: "x(P(x,y) ® Q(x) Ú R(c))

não satisfaz satisfazD = {0,1} D = {0,1}yI = 0 yI = 0cI = 0 cI = 0PI = {<1,1>} PI = {<0,0>,<1,0>}QI = {<1>} QI = ÆRI = {<0>} RI = {<1>}

57

III.4 - Relação entre Sintaxe e Semântica:

TEOREMA DA CORRETUDE:Se G Ã a então G Æ a..

TEOREMA DA COMPLETUDE:Se G Æ a então G Ã a..

58