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 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. 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.
Posted on: Mon, 24 Jun 2013 19:36:47 +0000
Trending Topics
Recently Viewed Topics
© 2015