Lógica/Cálculo Proposicional Clássico/Dedução Natural - Parte II

Origem: Wikilivros, livros abertos por um mundo aberto.

Regras de Inferência Derivadas[editar | editar código-fonte]

Por meio das regras de inferência diretas e hipotéticas podemos demonstrar vários raciocínios bastante recorrentes. Estes raciocíonios, uma vez demonstrados, podem ser usados como regras de inferência diretas. Elas não são necessárias, mas são bastante úteis, tornando nossas derivações muito mais sucintas. Anteriormente demonstramos dois raciocínios que nos serão úteis como regras de inferência derivadas:

  • Dupla Negação em ambas direções (DN)
  • Silogismo Hipotético (SH)

Vamos ampliar nossa lista de regras de inferência derivadas, demonstrado uma por uma:

Repetição (R)[editar | editar código-fonte]

 
1.     Premissa
2.     1 DN
3.     2 DN

Modus Tollens (MT)[editar | editar código-fonte]

 
1.     Premissa
2.     Premissa
 
3.       Hipótese
4.       1,3 MP
5.       2,4 C
6.           3,5 RAA

Prefixação (PRF)[editar | editar código-fonte]

 
1.     Premissa
 
2.       Hipótese
3.       1 R
4.     2,3 RPC

Contraposição (CT)[editar | editar código-fonte]

Aproveitaremos o Modus Tollens como regra de inferência.

 
1.     Premissa
 
2.       Hipótese
3.       1,2 MT
4.     2,3 RPC

Agora tente você provar a recíproca, ou seja, que

Confira aqui sua resposta.

Contradição (CTR)[editar | editar código-fonte]

 
1.     Premissa
2.     Premissa
3.     1 E
4.     2,3 SD

Lei de Duns Scot (DS)[editar | editar código-fonte]

 
1.     Premissa
 
2.       Hipótese
3.       1,2 CTR
4.     2,3 RPC

Prove que também vale .

Confira aqui sua resposta.

Lei De Morgan I (DM)[editar | editar código-fonte]

 
01.     Premissa
 
02.       Hipótese
03.       2 E
04.       1,3 C
05.                                 2,4 RAA
06.       Hipótese
07.       6 E
08.       1,7 C
09.                         6,8 RAA
10.                   5,9 C

Agora tente você provar a recíproca, ou seja, que

Confira aqui sua resposta

Lei De Morgan II (DM)[editar | editar código-fonte]

 
01.          Premissa
 
02.           Hipótese
   
03.         Hipótese  
04.         3 E
05.         5,2 C
06.                                                 3,5 RAA
07.                                                 6 DN
08.         Hipótese  
09.         8 E
10.         9,2 C
11.                         8,10 RAA
12.                         11 DN
13.                         7,12 C
14.                         13,1 C
15.                           2,14 RAA
16.                           15 DN

Tente você agora provar a recíprova, ou seja, que

Confira aqui sua resposta

Lista das Regras Derivadas[editar | editar código-fonte]

Exercícios[editar | editar código-fonte]

Valendo-se das regras derivadas, prove que:

Resolução dos Exercícios

Teoremas[editar | editar código-fonte]

Agora não temos mais premissas para trabalhar, devemos nos limitar às hipóteses. Algumas estratégias para provar teoremas podem ser traçadas:

  • Por redução ao absurdo

Para provar , levante a hipótese e derive dela uma contradição e aplique RAA.

Para provar , levante a hipótese e derive dela uma contradição, aplique RAA e então DN.

  • Por regra para condicionais

Para provar , levante o antecedente como hipótese, derive e então aplique RPC.

Para provar , prove e , como explicado acima, e então aplique CB.

Exemplo 1[editar | editar código-fonte]

 
1.       Hipótese
2.     1 RAA

Exemplo 2[editar | editar código-fonte]

 
1.       Hipótese
   
2.       1 DM
3.     1,2 RAA
4.     3 DN

Exemplo 3[editar | editar código-fonte]

 
1.       Hipótese
   
2.         Hipótese
3.         1,2 MP
4.          3,2 MP
5.       2,6 RPC
 
6.     1,7 RPC

Exemplo 4[editar | editar código-fonte]

 
01.       Hipótese
02.       1 DM
03.       2 S
04.       2 S
05.         Hipótese
06.         5 PRF
07.           4,5 C
08.         5,7 RAA
09.         8 DS
10.         9,3 C
 
11.     1,10 RAA
12.     11 DN

Exemplo 5[editar | editar código-fonte]

 
01.       Hipótese
   
02.                     Hipótese
     
03.           Hipótese
       
04.             Hipótese
         
05.             3,2 C
06.           4,5 RAA
07.           6 DN
08.         3,7 RPC
09.         1,8 MP
10.         2,9 C
11.       2, 10 RAA
12.       11 DN
13.     1, 12 RPC

Exemplo 6[editar | editar código-fonte]

 
01.       Hipótese
   
02.                     Hipótese
     
03.           Hipótese
04.           2,3 C
05.           1,4 MP
       
06.         3,5 RPC
     
07.       2,6 RPC
 
08.     1,7 RPC
 
 
09.       Hipótese
   
10.                     Hipótese
11.         10 S
12.         9,11 MP
13.         10 S
14.         12,13 MP
     
15.       10,14 RPC
 
16.     9,15 RPC
17.     8,16 CB

Exercícios[editar | editar código-fonte]

Prove os seguintes teoremas por dedução natural:

Resolução dos Exercícios