aula 25 set 2008

Prévia do material em texto

Nicia Riccio Lógica 2000.2
LÓGICA PARA COMPUTAÇÃO
MATA47 
Consequência Lógica
A →→→→ M
A
M
Como decidir se uma fórmula é consequência lógica de outra?
• Se José foi assassinado, então ele está 
morto
• José foi assassinado
• Então, José está morto
Como provar que um 
argumento é válido?
Definição intuitiva:
Um argumento é válido se a verdade das premissas implica 
na verdade da conclusão
ou
Sempre que as premissas forem verdadeiras, a conclusão 
também será 2
Nicia Riccio Lógica 2000.2
Consequência Lógica
Definição:Dadas as fórmulas F1,F2,...,Fn e a fórmula G, G é 
dita ser consequência lógica de F1,F2,...,Fn (ou segue 
logicamente de F1,F2,...,Fn ) se e somente se para 
qualquer interpretação I na qual F1 ∧∧∧∧ F2 ∧∧∧∧... ∧∧∧∧ Fn é V, 
G é também V. F1,F2,...,Fn são chamados axiomas ou 
postulados ou premissas de G.
A →→→→ M
A
M
A M (A →→→→ M)
V V V
V F F
F V V
F F V
Modus Ponens
3
Consequência Lógica
Teorema da dedução: Dadas fórmulas F1,F2,...,Fn e uma 
fórmula G, G é dita ser consequência lógica de 
F1,F2,...,Fn (ou segue logicamente de F1,F2,...,Fn ) se e 
somente se a fórmula ((F1 ∧∧∧∧ F2 ∧∧∧∧... ∧∧∧∧ Fn ) →→→→ G) é 
válida.
Teorema: Dadas fórmulas F1,F2,...,Fn e uma fórmula G, G é 
consequência lógica de F1,F2,...,Fn (ou segue 
logicamente de F1,F2,...,Fn ) se e somente se a fórmula 
(F1 ∧∧∧∧ F2 ∧∧∧∧... ∧∧∧∧ Fn ∧∧∧∧ ~G) é inconsistente
4
Nicia Riccio Lógica 2000.2
Consequência Lógica
• Os teoremas acima são muito importantes. Mostram que 
provar que uma fórmula é consequência lógica de um 
conjunto finito de fórmulas é equivalente a provar que 
uma certa fórmula (relacionada às primeiras) é válida ou 
inconsistente.
• Se G é consequência lógica de F1,F2,...,Fn então a 
fórmula ((F1 ∧∧∧∧ F2 ∧∧∧∧... ∧∧∧∧ Fn ) →→→→ G) é chamada teoremateorema, e G 
é chamada de conclusão do teorema.conclusão do teorema.
5
Regras de Inferência
P →→→→ Q
~Q
~P
P Q ~P ~Q (P →→→→ Q)
V V F F V
V F F V F
F V V F V
F F V V V
Modus Tolens
P ∨∨∨∨ Q
~P
Q
P Q ~P (P ∨∨∨∨ Q)
V V F V
V F F V
F V V V
F F V F
Silogismo
Disjuntivo
6
Nicia Riccio Lógica 2000.2
Regras de Inferência
P →→→→ Q
Q →→→→ R
P →→→→ R
P Q R (P →→→→ Q) (Q →→→→ R) (P →→→→ R)
V V V V V V
V V F V F F
V F V F V V
V F F F V F
F V V V V V
F V F V F V
F F V V V V
F F F V V V
Silogismo 
Hipotético
7
Regras de Inferência
(P →→→→ Q) ∧∧∧∧ (R →→→→ S)
P ∨∨∨∨ R
Q ∨∨∨∨ S
Dilema 
Construtivo
P →→→→ Q
P →→→→ (P ∧∧∧∧ Q)Absorção
Simplificação
P ∧∧∧∧ Q
P Conjunção
P 
Q
P ∧∧∧∧ Q
Adição
P 
P ∨∨∨∨ Q
8
Nicia Riccio Lógica 2000.2
Regras de Substituição
Definição:Duas fórmulas F e G são equivalentesequivalentes (ou F é 
equivalente a G), se e somente se o valor verdade de 
F e G são o mesmo sob qualquer interpretação.
~(P ∧∧∧∧ Q) = (~P ∨∨∨∨ ~Q)
P Q ~P ~Q (P ∧∧∧∧ Q) ~(P ∧∧∧∧ Q) = (~P ∨∨∨∨ ~Q)
V V F F V F F
V F F V F V V
F V V F F V V
F F V V F V V
Leis de Morgan
9
Regras de Substituição
~(P ∨∨∨∨ Q) = (~P ∧∧∧∧ ~Q)
P Q ~P ~Q (P ∨∨∨∨ Q) ~(P ∨∨∨∨ Q) = (~P ∧∧∧∧ ~Q)
V V F F V F F
V F F V V F F
F V V F V F F
F F V V F V V
Leis de Morgan
(P ∨∨∨∨ Q) = (Q ∨∨∨∨ P)
(P ∧∧∧∧ Q) = (Q ∧∧∧∧ P)
Comutação
10
Nicia Riccio Lógica 2000.2
Regras de Substituição
(P ∨ (Q ∨ R)) = ((P ∨ Q ) ∨ R)
(P ∧ (Q ∧ R)) = ((P ∧ Q ) ∧ R)
Associação
(P ∨ (Q ∧ R)) = (P ∨ Q ) ∧ (P ∨ R)
(P ∧ (Q ∨ R)) = (P ∧ Q ) ∨ (P ∧ R)
Distribuição
~~P = PDupla Negação
11
Regras de Substituição
(P → Q) = (~Q → ~P)Transposição
Implicação
P = P ∧ P
P = P ∨ P
Dupla Implicação
(P → Q) = (~P ∨ Q)
(P ↔↔↔↔ Q) = (P → Q) ∧ (Q → P)
Exportação ((P ∧ Q) → R) = (P → (Q → R))
Tautologia
Equivalência (P ↔↔↔↔ Q) = (P ∧ Q) ∨ (~P ∧ ~Q))
12
Nicia Riccio Lógica 2000.2
Regras de Substituição
� Sempre V
 Sempre F
P ∨ � = �
P ∨  = P
P ∨ ~P = �
P ∧  = 
P ∧ � = P
P ∧ ~P = 
13
Método da Dedução
• A noção de consequência lógica determina se um 
argumento é válido ou não.
• Posso provar a validade de argumentos com a tabela
verdade
(Copi)
Método da Dedução
A construção da prova se dá através da dedução da 
conclusão a partir das suas premissas, utilizando-se 
regras de inferência e de substituição
Desvantagem Não praticidade
14
Nicia Riccio Lógica 2000.2
Método da Dedução 
1. A ∨ B
2. ~B 
∴ A 
3. B ∨ A 1,Comutação
4. A 3,2,SD
Exemplo: Provar que o argumento abaixo é válido
15
Método da Dedução 
1. A ∧ B
2. (A ∨ C) → D 
∴ A ∧ D
3. A 1,Simpl.
4. A ∨ C 3,Adição
5. D 4,2,MP
6. A ∧ D 3,5, Conjunção
Exemplo: Provar que o argumento abaixo é válido
16
Nicia Riccio Lógica 2000.2
Método da Dedução 
1. A → B
2. B → C
3. C → D
4. ~D
5. A ∨ E
∴ E
6. A → C 1,2,SH
7. A → D 6,3,SH
8. ~A 7,4,MT
9. E 5,8,SD
Exemplo: Provar que o argumento abaixo é válido
17
Corretude 
18
� Se uma fórmula G pode ser derivada a partir de um conjunto de 
fórmulas F, então G é conseqüência de F
� Ou seja, um sistema de prova correto nunca produz fórmulas 
que não sejam conseqüência lógica da teoria usada como 
hipótese.
� Se um sistema de prova é correto, então ele provê uma 
alternativa às tabelas verdade.
Nicia Riccio Lógica 2000.2
Completude 
19
� F ╞ G se e somente se F ├ G 
� Completude afirma a existência de uma lista de regras que nos 
permite deduzir toda conseqüência a partir de qualquer conjunto 
de fórmulas de uma lógica .
Método da Dedução 
1. (A ∨ B) → C
2. (C ∨ B) → (A → (D ↔ E))
3. A ∧ D 
∴ D ↔ E
Prática: Provar a validade dos argumentos abaixo pelo método da dedução
a)
1. F → ~G
2. ~F → (H → ~G)
3. (~I ∨ ~H) → ~~G
4. ~I
∴ ~H
b) 1. A → B
2. C → ~B 
∴ A → ~C
1. (D ∧ E) → ~F
2. F ∨ (G ∧ H) 
3. D ↔ E
∴ D → G
c) d)
20