Lógica Proposicional - Técnicas de Prova

Prova Direta (Dedução Natural)

Observações:

Uma diferença entre argumento válido e prova direta é que no segundo caso estamos interessados, normalmente, na construção do argumento a partir das premissas (nem todas as proposições que não são teorema são premissas).

Todo argumento válido pode ``ser visto`` também como uma prova direta. (Pelas definições, chamando a  conclusão de teorema)

Toda prova direta pode também ``ser vista'' como um argumento válido. (Pelas definições, chamando o teorema de conclusão e todas as outras proposições de premissas. Observe que se o argumento assim formado não fosse válido teriamos uma linha do tipo '1 1 1 ... 1 0' em sua tabela verdade...)

Exemplo 1

Teorema: s'
Premissas: t , t -> q'  ,  q' -> s'
Prova:
 
1. t P
2. t -> q' P
3. q' MP 1,2
4. q' -> s' P
5. s'  MP 3,4

Exemplo 2

Teorema: r + s'
Premissas: s.q , t->q' , t'->r
Prova:
 
1. s.q P
2. q S 1
3. (q')' DN 2
4. t->q' P
5. t' MT 3,4
6. t'->r P
7. r MP 5,6
8. r+s' A 7

Exemplo 3

Modelar a seguinte argumentação utilizando lógica proposicional. (Retirado do livro de L. Hegenberg)

- Anne assustou-se, esta noite, com um gato branco.
- Como sabe que foi um gato ?
- Bem, ela só poderia ter se assustado com um animal e só há cães e gato por lá. Se fosse um cão, o susto teria sido maior.
- E como sabe que o gato era branco ?
- Só temos gatos brancos e gatos pretos e os gatos pretos não seriam visíveis naquela escuridão.

Teorema: Um gato branco assustou Anne (G.B)
Premissas:
 
Anne Assustou-se A
Se ela se assustou, só poderia ser por causa de um cão ou de um gato. A -> (C + G)
Se fosse um cão o susto teria sido maior C -> M
O susto não foi maior M'
Os gatos são pretos ou brancos (não ambos) G -> ( P ⊕ B)
Gatos pretos não são visíveis (à noite) P -> V'
Alguma coisa não visível não teria assustado Anne V' -> A'

Prova:
 
1. A P Premissa
2. A -> ( C + G) P
3. (C + G) MP 1,2 Modus Ponens
4. C -> M P
5. M' P
6. C' MT 4,5 Modus Tollens
7. G SD 3,6 Silogismo Disjuntivo
8. G -> (P⊕B) P
9. P⊕B MP 7,8
10. P -> V' P
11. V -> P'  EQ 10 Equivalência
12. V' -> A' P
13. V + V' Tautologia
14. P' + A' DC 11,12,13 Dilema Construtivo
15. P' SD 1,14
16. (P+B).(PB)' EQ 9
17. P+B S 16 Simplificação
18. B SD 15,17
19. G.B U 7,18 União

Observações:

  • Qualquer argumento cuja conclusão é uma tautologia é um argumento válido (Nunca ocorre 1 0)
  • Qualquer equivalência pode ser convertida em 2 argumento válidos. ( Quando A <=> B temos que A => B e B => A)

    • Prova Condicional

    Técnica que pode ser usada quando o teorema é uma condicional ( r -> s ).
    Utiliza o princípio da importação-exportação:

    P ->t ( r -> s)   <=>  (P.r) ->t s
    pois
    P->(r->s) <=> P'+(r->s) <=> P'+(r'+s) <=> (P'+r')+s <=> (P.r)'+s <=> (P.r)->s

    Usando este princípio podemos agora provar r->s, fazendo de r uma premissa (provisória) e
    de s um teorema.

    Exemplo:

    Teorema: r->p'
    Premissas: p->q,r->q'
    Prova:
     
    1 r->q' P
    2 r PP (Premissa Provisória)
    3 q' MP 1,2
    4 p->q P
    5 p' MT 3,4
    6 r->p' PC 2,5

     Prova Bicondicional

    Para provar p <-> q podemos provar separadamente p -> q e q -> p

    Prova Indireta (Redução ao Absurdo)

    Propriedade: De uma contradição pode-se deduzir qualquer coisa.

    Seja a contradiçãp p.p' e uma proposição qualquer T. Provaremos agora que T é um teorema usando p.p' como premissa:
     
    1 p.p' P
    2 p S 1
    3 p' S 1
    4 p + T A 2
    5 T SD 3,4

    A Técnica: Para provar p adicionamos p' ao conjunto de premissas e deduzimos uma contradição (não necessariamente envolvendo p ou p').

    Exemplo:

    Teorema: p'
    Premissas: q'+r , p->r' , q
    Prova:
     
    1 (p')' PP (Premissa Provisória)
    2 p DN 1
    3 p->r' P
    4 r' MT 2,3
    5 q'+r P
    6 q' SD 4,5
    7 q P
    8 q.q' U 6,7
    9 p' PI 8 (8 é uma contradição)