NOÇÕES DE LÓGICA MATEMÁTICA

TAUTOLOGIA E CONTRA -TAUTOLOGIA

· TAUTOLOGIA ou FÓRMULA LOGICAMENTE VÁLIDA : Fórmula que possui apenas valor V em sua tabela verdade. Exemplo : p Ú~ p


  p ~ p p Ú ~ p
1 V F     V
2 F V     V

 

· CONTRA-TAUTOLOGIA ou FÓRMULA LOGICAMENTE FALSA: Fórmula que possui apenas valor F em sua tabela verdade. Exemplo : p Ù ~ p

 

  p ~ p p Ù ~ p
1 V F      F
2 F V     F

 

· CONTINGENTE ou INDETERMINADA: Fórmula que possui valores V e F em sua tabela verdade.
Exemplo : p ® q

  p q p ® q
1 V V
V
2 V F
F
3 F V
V
4 F F
V

· REGRAS DE INFERÊNCIA.: A fórmula a implica tautologicamente a fórmula b e indicamos a Þ bse e somente se a fórmula bé uma tautologia .

Regras   Fórmulas Atômicas Fórmulas Compostas
Modus Ponens  MP p Ù (p ® q) Þ q A, A® B / B
Modus Tollens MT ~ q Ù ( p ® q ) Þ ~ p ~ B, A® B / ~ A
Silogismo Hipotético SH (p® q) Ù ( q ® r) Þ (p ® r) A ® B, B ® C / A ® C
Silogismo Disjuntivo SD (p Ú q) Ù ~ p Þ q ~ A, A Ú B / B
Simplificação SM p Ù q Þ p A Ù B / A
Adição AD p Þ p Ú q A / A Ú B
Eliminação EL (p ® (q Ú r) ) Ù~ q Þ p ®r ~ B , (A ® (BÚ C) / A ® C
Prova por Casos CS (p ® r) Ù ( q ® r) Þ (p Ú q) ® r A ® C, B ® C / (A Ú B ) ® C

· EQUIVALÊNCIAS TAUTOLÓGICAS : As fórmulas a e b são tautologicamente equivalentes e indicamos aÛbse e somente se a fórmula a«bé uma tautologia
 
Comutativa  p Ù q Û q Ù p p Ú q Û q Ú p
Associativa  (p Ù q)Ù r Û p Ù (q Ù r)  (p Ú q)Ú r Û pÚ (qÚ r)
Idempotente p Ù p Û p p Ú p Û p
Propriedades de V  p Ù V Û p Ú V Û V
Propriedades de F  p Ù F Û F p Ú F Û p
Absorção  p Ù ( p Ú r ) Û p p Ú (p Ù r) Û p
Distributivas p Ù (q Ú r) Û (p Ù q ) Ú (p Ù r) p Ú (q Ù r) Û (p Ú q ) Ù (p Ú r)
Distributivas p ® (q Ù r) Û (p® q) Ù (p ® r) p ® (q Ú r) Û (p® q) Ú (p ® r)
Leis de De Morgan ~ (p Ù q) Û~ p Ú ~ q ~ (p Ú q) Û~ p Ù ~ q
Def. implicação p ® q Û ~p Ú q p ® q Û ~ ( p Ù~ q)
Def. bicondicional p « q Û (p ® q) Ù ( q ® p)  p « q Û (~p Ú q) Ù (~q Úp)
Negação ~ (~ p) Û p  
Contraposição p ® q Û ~ q ®~ p  
Exportação(Þ ) Importação (Ü (p Ù q) ® r Û p ® ( q ® r )
Troca de Premissas p ® (q ® r ) Û q ® ( p ®r )  

Exemplo : Dadas as fórmulas A: p ® (q Ù r) e B : ~(q Ù r ) ®~ p vamos verificar que A Þ B ou ainda que A / B. Basta verificar, com o uso das tabelas verdade, que A ® B é tautologia.
   p      q        r        ( p ® (q Ù r)) ®(~ (q Ù r ) ® ~ p)
V V V V V V
V V F F V F
V F V F V F
V F F F V F
F V V V V V
F V F V V V
F F V V V V
F F F V V V

Neste exemplo, A Û B pois A « B é tautologia.

As TAUTOLOGIAS são infinitas e desempenham um importante papel nos processos de dedução no Cálculo Proposicional como veremos em próximos tópicos.


FORMAS NORMAIS CONJUNTIVA E DISJUNTIVA

Algumas EQUIVALÊNCIAS TAUTOLÓGICAS dadas acima nos permitem transformar qualquer fórmula em uma fórmula logicamente equivalente, que não contenha os conectivos ®e « , transformando-a em uma FORMA NORMAL CONJUNTIVA (FNC) ou em uma FORMA NORMAL DISJUNTIVA (FND) como segue:

1. substitui-se fórmulas: A® B por ~A Ú B e A « B por (~ A Ú B) Ù (~ B Ú A)
2. elimina-se a negação que precede os parênteses substituindo-se:
~(A Ù B) por ~A Ú~ B e ~(AÚ B) por ~A Ù~ B .
3. eliminam-se as negações múltiplas substituindo ~(~ A) por A.
4. elimina-se o alcance dos conectivos substituindo

para obter a FNC : A Ú (B Ù C) por (A Ú B) Ù (A Ú C)
para obter a FND : A Ù (B Ú C) por (A Ù B) Ú (A Ù C)

Deste modo, uma fórmula está em FORMA NORMAL CONJUNTIVA: FNC ou em FORMA NORMAL DISJUNTIVA: FND se, e somente se:

1. No máximo contém os conectivos~, Ù , Ú.
2. A negação ~ não tem alcance sobre os conectivos Ù e Ú .
3. Não aparecem negações sucessivas.
4. O conectivo Ú não tem alcance sobre Ù na FNC e, o conectivo Ù não tem alcance sobre Ú na FND.

Exemplos:    FNC : (~ p Ú q) Ù (r Ú s Ú p)
                     FND : p Ú (q Ù r) Ú (~ s Ù p)

Exemplo: Determine uma FND e uma FNC equivalente à fórmula
                 ((p Ú q) Ù~ q) ® ( r Ù q) .
1. ((p Ú q) Ù ~ q) ® ( r Ù q) Fórmula dada
2. ~ ((p Ú q) Ù~ q) Ú ( r Ù q) 1. Def. de Implicação
3. (~ (p Ú q) Ú~~ q) Ú (r Ù q) 2. De Morgan
4. (~ p Ù ~ q) Ú q Ú (r Ù q ) 3. Negação e De Morgan
5. (~ p Ù ~ q) Ú q Ú (r Ù q ) 4.FND
6. ((~ p Ú q) Ù (~ q Ú q)) Ú (r Ù q) 5. Distributiva
7. ((~ p Ú q) Ù V) Ú (r Ù q) 6. Tautologia
8. (~ p Ú q) Ú ( r Ù q) 7. Propriedade de V
9. (~ p Ú q Ú r) Ù (~ p Ú q Ú q) 8. Distributiva
10. (~ p Ú q Ú r) Ù (~ p Ú q ) 9. Idempotente e FNC


PROBLEMA DE POST

Como já  observamos podemos construir a tabela verdade de uma fórmula conhecidos os valores verdade das fórmulas que a compõem. O problema recíproco se coloca : para toda tabela verdade, existe uma fórmula que a determina? Este problema é conhecido como PROBLEMA DE POST (Emil Leon Post 1888-1995) e pode ser resolvido obtendo-se uma FNC ou uma FND que satisfaça a tabela verdade dada.

· Para se obter uma FND:

1. Observamos todas as linhas da tabela que possuem V na última coluna;
2. Construimos para cada uma destas linhas as conjunções correspondentes;
3. Fazemos a disjunção destas conjunções obtendo uma fórmula em FND que satisfaz a tabela verdade.

Exemplo: Determine uma fórmula que satisfaça a tabela verdade abaixo:
                                                                  p         q         ?

V V V (p Ù q)
V F F  
F V F  
F F V (~ p Ù ~ q)

Resposta: Fórmula obtida (p Ù q) Ú (~ p Ù~ q) FND

· Para se obter uma FNC:

1. Observamos todas as linhas da tabela que possuem F na última coluna;
2. Construimos para cada uma destas linhas as disjunções correspondentes;
3. Fazemos a conjunção destas disjunções obtendo uma fórmula em FNC que satisfaz a tabela verdade.

Exemplo: Determine uma fórmula que satisfaça a tabela verdade abaixo:
                                                                     p        q       ?

V V V  
V F F ~ p Ú q
F V F    p Ú ~ q
F F V  

Resposta: Fórmula obtida (~ p Ú q) Ù (p Ú ~ q) FNC

As FND e FNC obtidas como acima são completas ou seja, em cada disjuncto (FND) ou em cada conjuncto (FNC) todas as variáveis proposicionais estão presentes.


CELINA ABAR
- 2004 -