Logica matematica

Ciência da Computação – Prof. Gerson Pastre de Oliveira

Aula 7 – Lógica Matemática
Redução do número de conectivos e formas normais

Redução do número de conectivos

De acordo com Alencar Filho (1999, p.81 e 82), e considerando os conectivos fundamentais ~, ^, v,  e , pode-se dizer que:
a) ^,  e  podem ser expressos em termos de ~ e v p ^ q  ~~p ^ ~~q  ~(~p v ~q) p  q  ~p v q p  q  (p  q) ^ (q  p)  (~p v q) ^ (~q v p)  ~(~(~p v q) v ~(~q v p))
b) v,  e  podem ser expressos em termos de ~ e ^ p v q  ~~p v ~~q  ~(~p ^ ~q) p  q  ~p v q  ~(p ^ ~q) p  q  (p  q) ^ (q  p)  (~p v q) ^ (~q v p)  ~(p ^ ~q) ^ ~(q ^ ~p)
c) ^, v e  podem ser expressos em termos de ~ e : p ^ q  ~~p ^ ~~q  ~(~p v ~q)  ~(p  ~q) p v q  ~p  q p  q  (p  q) ^ (q  p)  (~p v q) ^ (~q v p)  ~(~(~p v q) v ~(~q v p))
 ~((~p v q)  ~(~q v p))  ~((p  q)  ~(q  p))

Observação: o conectivo v pode ser expresso em termos de v, ^ e ~, ou seja: p v q  (p v q) ^ ~(p ^ q)  (p v q) ^ (~p v ~q)

Ciência da Computação – Prof. Gerson Pastre de Oliveira

Forma Normal das Proposições

Uma proposição está na forma normal (FN) se e somente se contém, quando muito, os conectivos ~, ^ e v. Uma proposição comporta dois tipos de formas normais: a forma normal conjuntiva (FNC) e a forma normal disjuntiva (FND).

Uma proposição está na FNC quando:

a) contém, no máximo, os conectivos ~, ^ e v;
b) Não ocorre ~~ e ~só incide sobre proposições simples, assim entendidas como letras proposicionais;
c) v não tem alcance sobre ^.

Por exemplo, as proposições ~p v ~q, p ^ ~q ^ r, (~p ^ r) ^q e (~p v r) ^ (~q v p) estão na FNC.

Para determinar a FNC de uma proposição, deve-se:
a) Eliminar  e , substituindo p  q por ~p v q e p  q por (~p v q) ^ (~q v
p);
b) Eliminar ~~ pela regra da Dupla Negação e parênteses precedidos por ~ pela regra de De Morgan;
c) Substituir p v (q ^ r) por (p v q) ^ (p v r) e (p ^ q) v r por (p v r) ^ (q v r).