Dedução Natural
Universidade Tecnológica Federal do Paraná
Curso de Engenharia de Computação
Método da dedução natural

Deduzir uma conclusão a partir de
premissas.

Regras de inferência.

Método prático.
Regras de inferência
Quantas regras se pode ter num
sistema?
Mínimo: duas regras para cada
operador – introdutora e eliminadora.



Regras de inferência diretas.
Regras de inferência hipotéticas.
Regras de inferência derivadas.
Regras de inferência diretas
Dupla Negação (DN):
¬¬

Separação (S):
 


Modus Ponens (MP):



Expansão (E):




Conjunção (C):



Regras de inferência diretas
Silogismo Disjuntivo (SD):


¬
¬


Condicionais para Bicondicional (CB):



Bicondicional para Condicionais (BC):




Exemplo de dedução
Pa  (Qab  Cq), (Qab  Cq)  Dc,
Dc  (E  (¬E  Fba)), Pa, ¬E ╞ Fba.
1.
2.
3.
4.
5.
Pa  (Qab  Cq)
(Qab  Cq)  Dc
Dc  (E  (¬E  Fba))
Pa
¬E
P
P
P
P
P
?Fba
1. Pa  (Qab  Cq)
2. (Qab  Cq)  Dc
3. Dc  (E  (¬E  Fba))
4. Pa
5. ¬E
6. Qab  Cq
7. Dc
8. E  (¬E  Fba)
9. ¬E  Fba
10. Fba
P
P
P
P
P
1,
2,
3,
5,
5,
?Fba
4
6
7
8
9
MP
MP
MP
SD
MP
Definições
“Definição 1: Sejam  um conjunto qualquer
de fórmulas e  uma fórmula. Uma dedução
de  a partir de  é uma sequência finita
1,...,n de fórmulas, tal que n =  e cada i,
1 i  n, é uma fórmula que pertence a  ou
foi obtida a partir de fórmulas que aparecem
antes na sequência, por meio da aplicação de
alguma regra de inferência.” (MORTARI,
2001:242)
Definições
“Definição 2: Sejam  um conjunto qualquer
de fórmulas e  uma fórmula. Dizemos que 
é consequência lógica (sintática) de , o que
denotamos por ├  , se há uma dedução de
 a partir de .” (MORTARI, 2001:243)
Exemplos
{Pa  (Qab  Cq), (Qab  Cq)  Dc,
Dc  (E  (¬E  Fba)), Pa, ¬E} ├ Fba.
{1,...,n} ├ 
1,...,n ├ 
Regras de inferência hipotéticas
Se Miau é um gato típico, ele não gosta de nadar. Se
não gosta de nadar, então não pratica pesca
submarina. Logo, se Miau é um gato típico, Miau não
pratica pesca submarina.
Gm  ¬Nm, ¬Nm  ¬Pm ├ Gm  ¬ Pm.
1. Gm  ¬Nm
2. ¬Nm  ¬Pm
3. | Gm
P
P
H
?Gm  ¬ Pm
?¬Pm
1.
2.
3.
4.
5.
6.
Gm  ¬Nm
¬Nm  ¬Pm
Gm
¬Nm
¬Pm
Gm  ¬Pm
P
P
?Gm  ¬ Pm
H
?¬Pm
1, 3 MP
2, 4 MP
3-5 RPC
Regra de prova condicional
Formulação

:


Uso apropriado da RPC
I.
II.
III.
IV.
Introduzir na derivação uma linha
vertical toda vez que uma hipótese
adicional for introduzida.
Não usar uma fórmula que ocorre à
direita de uma linha vertical depois de
terminada essa linha.
Descartar as hipóteses na ordem inversa
em que foram introduzidas.
Uma dedução não termina enquanto
não forem descartadas todas as
hipóteses adicionais.
Regras de inferência hipotéticas
Cb  ¬Fnp ├ ¬(Cb  Fnp)
1. Cb  ¬Fnp
2. Cb  Fnp
3. Cb
4. ¬Fnp
5. Fnp
6. Fnp  ¬Fnp
7.¬(Cb  Fnp)
P
?¬(Cb  Fnp)
H
?CTR
2S
1, 3 MP
2S
4, 5 C
2-6 RAA
Regra de redução ao absurdo
Formulação:

¬
¬
Regras de inferência derivadas
São as regras que podem ser provadas
a partir das regras mencionadas
anteriormente.
Podem ser consideradas como uma
maneira de abreviar parte de uma
dedução.
Regras de inferência derivadas
Modus Tollens (MT):

¬
¬
Dupla Negação (DN):
¬¬

Silogismo Hipotético(SH):



Contradição (CTR):

¬

Contraposição

¬¬
Leis de De Morgan (DM):
¬(  ) ¬(  )
¬  ¬ ¬  ¬
Teoremas
Definição 3: Uma fórmula  é um teorema
(do CQC) se há uma dedução de  a partir
do conjunto vazio de premissas.
Assim,  é um teorema se e somente se
├ , o que abreviamos escrevendo
simplesmente ├ .
Teoremas
Exemplo:
├ (Fa  Gb)  Fa.
1. Fa  Gb
2. Fa
3. (Fa  Gb)  Fa.
H
1S
1-2 RPC
Consequência sintática e
consequência semântica
Teorema de Correção e Completude
├  se e somente se ╞ 
 é uma consequência sintática de  se e
somente se  é uma consequência
semântica de .
O método de dedução natural é um sistema
de prova correto e completo. Correto porque
se uma conclusão pode ser deduzida de um
conjunto  de premissas, então ela de fato é
consequência lógica (semântica) de . E
completo porque, se uma fórmula é
consequência lógica (sintática) de um
conjunto de premissas, há uma dedução
demonstrando isso.