terça-feira, 21 de janeiro de 2020

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
1VF    V
2FV    V

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


p~ pÙ ~ p
1VF     F
2FV    F

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

pq® q
1VV
V
2VF
F
3FV
V
4FF
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 .
RegrasFórmulas AtômicasFórmulas Compostas
Modus Ponens MPÙ (p ® q) Þ qA, A® B / B
Modus TollensMT~ q Ù ( p ® q ) Þ ~ p~ B, A® B / ~ A
Silogismo HipotéticoSH(p® q) Ù ( q ® r) Þ (p ® r)® B, B ® C / A ® C
Silogismo DisjuntivoSD(p Ú q) Ù ~ p Þ q~ A, A Ú B / B
SimplificaçãoSMÙ q Þ pÙ B / A
AdiçãoADÞ p Ú qA / A Ú B
EliminaçãoEL(p ® (q Ú r) ) Ù~ q Þ p ®r~ B , (A ® (BÚ C) / A ® C
Prova por CasosCS(p ® r) Ù ( q ® r) Þ (p Ú q) ® r® C, B ® C / (A Ú B ) ® C
· EQUIVALÊNCIAS TAUTOLÓGICAS : As fórmulas a e b são tautologicamente equivalentes e indicamosaÛbse e somente se a fórmula a«bé uma tautologia

Comutativa Ù q Û q Ù pÚ q Û q Ú p
Associativa (p Ù q)Ù r Û p Ù (q Ù r) (p Ú q)Ú r Û pÚ (qÚ r)
IdempotenteÙ p Û pÚ p Û p
Propriedades de V Ù V Û p Ú V Û V
Propriedades de F Ù F Û FÚ F Û p
Absorção Ù ( p Ú r ) Û pÚ (p Ù r) Û p
DistributivasÙ (q Ú r) Û (p Ù q ) Ú (p Ù r)Ú (q Ù r) Û (p Ú q ) Ù (p Ú r)
Distributivas® (q Ù r) Û (p® q) Ù (p ® r)® (q Ú r) Û (p® q) Ú (p ® r)
Leis de De Morgan~ (p Ù q) Û~ p Ú ~ q~ (p Ú q) Û~ p Ù ~ q
Def. implicação® q Û ~p Ú q® q Û ~ ( p Ù~ q)
Def. bicondicional« q Û (p ® q) Ù ( q ® p) « q Û (~p Ú q) Ù (~q Úp)
Negação~ (~ p) Û p
Contraposição® q Û ~ q ®~ p
Exportação(Þ )Importação (Ü ) (p Ù q) ® r Û p ® ( q ® r )
Troca de Premissas® (q ® r ) Û q ® ( p ®r )
Exemplo : Dadas as fórmulas A® (q Ù r) e B : ~(q Ù r ) ®~ p vamos verificar que Þ B ou ainda que A / B. Basta verificar, com o uso das tabelas verdade, que ® B é tautologia.
   p      q        r        ( p ® (q Ù r)) ®(~ (q Ù r ) ® ~ p)
VVVVVV
VVFFVF
VFVFVF
VFFFVF
FVVVVV
FVFVVV
FFVVVV
FFFVVV
Neste exemplo, Û B pois « 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 ®« , 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 ~Ú B e « B por (~ A Ú B) Ù (~ B Ú A)
2. elimina-se a negação que precede os parênteses substituindo-se:
~(A Ù B) por ~Ú~ B ~(AÚ B) por ~Ù~ 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 Ú (B Ù C) por (A Ú B) Ù (A Ú C)
para obter a FND : Ù (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 : Ú (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         ?
VVV(p Ù q)
VFF
FVF
FFV(~ 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       ?
VVV
VFF~ p Ú q
FVF   p Ú ~ q
FFV
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

Nenhum comentário:

Postar um comentário