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 | |
2 | V | F | |
3 | F | V | |
4 | F | F |
· REGRAS DE INFERÊNCIA.: A fórmula a implica tautologicamente a fórmula b e indicamos a Þ bse e somente se a fórmula a®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 | 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.
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 |
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.