Cap6 (Dedução Natural da Lógica Proposicional)

Prévia do material em texto

Capítulo 6 
 
Dedução Natural da 
Lógica Proposicional 
 
Sistema Axiomático Pa 
Definição 6.1 (Sistema Axiomático Pa) O 
sistema formal axiomático Pa da Lógica 
Proposicional é definido pela composição dos 
quatro elementos: 
 o alfabeto da lógica proposicional a forma 
simplificada; 
o conjunto das fórmulas da lógica proposicional; 
um subconjunto das fórmulas, denominados 
axiomas; 
um conjunto de regras de dedução. 
Sistema Axiomático Pa 
Definição 6.2 (Axiomas do Sistema Pa) Os 
axiomas do sistema Pa são fórmulas da 
Lógica Proposicional determinadas pelos 
esquemas indicados a seguir, onde E, G e H 
são fórmulas quaisquer: 
 Ax1 = (H  H)  H 
 Ax2 = H  (G  H) 
 Ax3 = ( (H  G))  (((E  H))  (G  E)) 
Regras de Inferência 
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 b, H é conseqüência lógica de b 
num sistema de dedução, se existir uma 
prova de H a partir de b 
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 b={H1,H2,...Hn}, diz-se 
que: 
b├ 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 
 
 
 
Regras de inferência de dedução 
natural 
Servem para inserção e retirada de 
conectivos lógicos, 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 b um conjunto 
de fórmulas (hipóteses) 
Uma prova de H a partir de b é uma 
derivação onde 
As regras de inferência são aplicadas 
tendo como premissas fórmulas de b 
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 ((PQ)Q) 
Supor os antecedentes 
Eles não poderão ser usados depois 
 
[P] [(PQ)] (hipóteses) 
 Q (E) 
(PQ)Q) (I) 
(P ((PQ)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), PQ, 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 false 
 false 
 
 
 
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: HH e 
 H H 
 
 
Argumento Válido 
Um argumento é uma sequência de 
proposições (declarações/afirmações) na qual 
uma delas é a conclusão e as demais são 
premissas. 
H1, H2, … , Hn ├ H ou 
H1  H2  …  Hn  H 
Argumentos e Regras de Inferência 
1. P ├ P  Q (AD ou Adição) 
2. P , Q ├ P  Q (CONJ ou Conjunção) 
3. P  Q ├ P ou P  Q ├ Q (SIMP ou Simplificação) 
4. P, P  Q ├ Q (MP ou Modus Ponens) 
5. P  Q , ¬ Q├ ¬ P (MT ou Modus Tolens) 
6. P  Q, Q  R ├ P  R (SH ou Silogismo Hipotético) 
7. P  Q, R  S, P  R ├ Q  S 
8. P  Q, R  S, ¬Q  ¬S ├ ¬P  ¬R 
9. P  Q, ¬P├ Q (SD ou Silogismo Disjuntivo) 
Dedução Natural 
Exemplo 
A  (B C) [(A B)(¬C D)]  B D 
1. A Premissa 
2. B C Premissa 
3. (A B)(D¬C) Premissa 
4. B Premissa 
5. C 2,4 MP 
6. A B 1,4 Conj 
7. ¬C D 3,6 MP 
8. C D 7 Equiv 
9. D 5,8 MP 
 
 
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!