Cálculo Proposicional

Alessandro Barbieri

Fernando Melo

Jessé Benevides

Rui Barbosa

Introdução

Lógica Formal.

Hoje é segunda-feira ou terça-feira.

Hoje não é segunda-feira.

> Hoje é terça-feira.

Ele é menor de 18 anos ou ele é jovem.

Ele não é menor de 18 anos.

> Ele é jovem.

Forma comum:

P ou Q.

Não é o caso que P.

> Q.

Letras sentencionais

Operadores Lógicos

Negação ¬

E ^

Ou V

Se, então

Se e somente se

Tabela verdade:

P ¬ P

V F

F V

P Q P∧Q

V V V

V F F

F V F

F F F

P Q P∨Q

V V V

V F V

F V V

F F F

P Q P→Q

V V V

V F F

F V V

F F V

P Q P↔Q

V V V

V F F

F V F

F F V

Formalização

Não está chovendo.

¬ C

Está chovendo e nevando.

C ^ N

Esta chovendo ou nevando.

C V N

Se não está chovendo, então está nevando.

¬ C N

Está chovendo se e somente se não está nevando

C ¬ N

Regras de Inferência

Regras Básicas:

◦ Hipotéticas

◦ Não hipotéticas.

Regras Derivadas

Eliminação da dupla negação

◦ De ¬¬p, infere-se p.

Introdução a conjunção

◦ De p e q, infere-se (p ∧ q).

Eliminação da conjunção

◦ De (p ∧ q), infere-se p De (p ∧ q), infere-se q.

Introdução a disjunção

◦ De p, infere-se (p ∨ q)De p, infere-se (q ∨ p).

Eliminação da disjunção

◦ De (p ∨ q), (p → r), (q → r), infere-se r.

Introdução do bicondicional

◦ De (p → q), (q → p), infere-se (p ↔ q).

Eliminação do bicondicional

◦ De (p ↔ q), infere-se (p → q);De (p ↔ q), infere-se (q → p).

Modus pones

◦ De p, (p → q), infere-se q.

Regras Hipóteticas

Prova do Condicional (PC).

◦ Estratégia de prova.

Assume-se a conclusão como hipótese.

Redução ao Absurdo (RAA).

◦ Estratégia de prova.

Assume-se a conclusão nagada como hipótese.

Regras Derivadas

As regras derivadas são obtidas através

de regras de inferências previamente

provadas.

As regras derivadas não permitem

realizar provas não prováveis pelas dez

regras básicas mencionadas.

Flexibilidade na estratégia de provas.

Equivalência

É uma bicondicional que também é um teorema, ou seja, prova-se a “ida” e a “volta”.

Muitas equivalências tem nomes, assim como as regras derivadas.

◦ Lei de Morgan (DM)

◦ Distributiva(DIST)

◦ Associação (ASSOC)

◦ Comutativa (COM)

Obrigado!

Fim