Baixe o app para aproveitar ainda mais
Prévia do material em texto
CCT0350 – MATEMÁTICA APLICADA A COMPUTAÇÃO Aula 12: Cálculo Proposicional MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Formas Normais. Podemos transformar fórmulas em fórmulas semanticamente equivalentes. Fórmulas de formas especiais satisfabilidade ou validade das fórmulas originais. Definições: • Um literal é uma variável proposicional (p) ou a sua negação (~p). • Fórmula normal negativa se a ocorrência de ~ for só em literais. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Formas Normais. Proposição – Qualquer fórmula contendo apenas as conectivas ^ , e ~ é semanticamente equivalente a uma fórmula em forma normal negativa. Exemplo: Determinar a forma normal negativa de ~ ((p q) ^ ~p). MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Formas Normais. Problema de Post; Proposição – Qualquer fórmula contendo apenas as conectivas ^ , e ~ é semanticamente equivalente a uma fórmula em forma normal negativa. Exemplo: Determinar a forma normal negativa de ~ ((p q) ^ ~p). a) ~((p q) ^ ~p) MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Formas Normais. Problema de Post; Proposição – Qualquer fórmula contendo apenas as conectivas ^ , e ~ é semanticamente equivalente a uma fórmula em forma normal negativa. Exemplo: Determinar a forma normal negativa de ~ ((p q) ^ ~p). a) ~((p q) ^ ~p) b) ~(p q) ~~p (DeMorgan) MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Formas Normais. Problema de Post; Proposição – Qualquer fórmula contendo apenas as conectivas ^ , e ~ é semanticamente equivalente a uma fórmula em forma normal negativa. Exemplo: Determinar a forma normal negativa de ~ ((p q) ^ ~p). a) ~((p q) ^ ~p) b) ~(p q) ~~p (DeMorgan) c) (~p ^ ~q) ~~p (DeMorgan) MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Formas Normais. Problema de Post; Proposição – Qualquer fórmula contendo apenas as conectivas ^ , e ~ é semanticamente equivalente a uma fórmula em forma normal negativa. Exemplo: Determinar a forma normal negativa de ~ ((p q) ^ ~p). a) ~((p q) ^ ~p) b) ~(p q) ~~p (DeMorgan) c) (~p ^ ~q) ~~p (DeMorgan) d) (~p ^ ~q) p (Dupla Negação) Portanto: (~p ^ ~q) p MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional TAUTOLOGIA ou FÓRMULA LOGICAMENTE VÁLIDA Fórmula que possui apenas valor V em sua tabela verdade. Exemplo : p ~ p MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional TAUTOLOGIA ou FÓRMULA LOGICAMENTE VÁLIDA Fórmula que possui apenas valor V em sua tabela verdade. Exemplo : p ~ p Portanto p ~ p é uma Tautolodia MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional CONTRA-TAUTOLOGIA ou FÓRMULA LOGICAMENTE FALSA Fórmula que possui apenas valor F em sua tabela verdade. Exemplo : p ^ ~ p MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional CONTRA-TAUTOLOGIA ou FÓRMULA LOGICAMENTE FALSA Fórmula que possui apenas valor F em sua tabela verdade. Exemplo : p ^ ~ p Portanto p ^ ~ p é uma Contra-Tautolodia MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional CONTINGENTE ou INDETERMINADA Fórmula que possui valores V e F em sua tabela verdade. Exemplo : p q MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional CONTINGENTE ou INDETERMINADA Fórmula que possui valores V e F em sua tabela verdade. Exemplo : p q Portanto p q é Contingente MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Algumas EQUIVALÊNCIAS TAUTOLÓGICAS nos permitem transformar qualquer fórmula em uma fórmula logicamente equivalente, que não contenha os conectivos e : FORMA NORMAL CONJUNTIVA (FNC) ou em uma FORMA NORMAL DISJUNTIVA (FND) 1. Substituem-se fórmulas: a. A B por ~A B b. A B por (~ A B) ^ (~ B A) MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Algumas EQUIVALÊNCIAS TAUTOLÓGICAS fórmula logicamente equivalente, que não contenha os conectivos e , FORMA NORMAL CONJUNTIVA (FNC) ou em uma FORMA NORMAL DISJUNTIVA (FND) 1. Substituem-se fórmulas: a. A B por ~A B b. A B por (~ A B) ^ (~ B A) 2. Elimina-se a negação que precede os parênteses, substituindo-se: a. ~(A ^ B) por ~A ~B b. ~(A B) por ~A ^ ~ B . MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Algumas EQUIVALÊNCIAS TAUTOLÓGICAS fórmula logicamente equivalente, que não contenha os conectivos e , FORMA NORMAL CONJUNTIVA (FNC) ou em uma FORMA NORMAL DISJUNTIVA (FND) 1. Substituem-se fórmulas: a. A B por ~A B b. A B por (~ A B) ^ (~ B A) 2. Elimina-se a negação que precede os parênteses, substituindo-se: a. ~(A ^ B) por ~A ~B b. ~(A B) por ~A ^ ~ B. 3. Eliminam-se as negações múltiplas, substituindo ~(~ A) por A. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Algumas EQUIVALÊNCIAS TAUTOLÓGICAS fórmula logicamente equivalente, que não contenha os conectivos e , FORMA NORMAL CONJUNTIVA (FNC) ou em uma FORMA NORMAL DISJUNTIVA (FND) 1. Substituem-se fórmulas: a. A B por ~A B b. A B por (~ A B) ^ (~ B A) 2. Elimina-se a negação que precede os parênteses, substituindo-se: a. ~(A ^ B) por ~A ~B b. ~(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 a. para obter a FNC : A (B ^ C) por (A B) ^ (A C) b. para obter a FND : A ^ (B C) por (A ^ B) (A ^ C) MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional FORMA NORMAL CONJUNTIVA (FNC) ou 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. 5. O conectivo ^ não tem alcance sobre v na FND. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Exemplos: FNC : (~ p q) ^ (r s p) MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional 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) . MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional PROBLEMA DE POST Podemos construir a tabela verdade de uma fórmula, conhecidos os valores verdade das fórmulas que a compõem. O problema recíproco: Para toda tabela verdade, existe uma fórmula que a determina? MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional PROBLEMA DE POST O problema recíproco: Para toda tabelaverdade, existe uma fórmula que a determina? PROBLEMA DE POST MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional PROBLEMA DE POST 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. Construímos 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. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Exemplo: Determine uma fórmula que satisfaça a tabela verdade abaixo: Fórmula obtida (p ^ q) (~ p ^ ~ q) FND MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Para se obter uma FNC: 1. Observamos todas as linhas da tabela que possuem F na última coluna; 2. Construímos para cada uma dessas linhas as disjunções correspondentes; 3. Fazemos a conjunção dessas disjunções obtendo uma fórmula em FNC que satisfaz a tabela verdade. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Exemplo: Determine uma fórmula que satisfaça a tabela verdade abaixo: Fórmula obtida (~ p q) ^(p ~ q) FNC MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Conjuntos Adequados de Conectivos; Representar uma fórmula qualquer basta dois destes conectivos (^, , , e ~ ), mas não dois quaisquer. Portanto, teremos que um conjunto de conectivos é adequado se para toda fórmula proposicional existe uma fórmula equivalente formada só pelos conectivos (^, , , e ~ ). MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Conjuntos Adequados de Conectivos; A linguagem do cálculo proposicional utilizará apenas os conectivos básicos ( ~ e ). Conectivos derivados: (^, e ). Proposição: Cada função de verdade e gerada por uma fórmula envolvendo apenas os conectivos ~, ^ e . Proposição – Toda fórmula e logicamente equivalente a uma fórmula na forma normal disjuntiva. Proposição: {~,^}, {~, }, {~, } são conjuntos adequados de conectivos. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Argumento e Regras de Inferência. ARGUMENTOS: conjunto de enunciados dos quais um é a CONCLUSÃO, e os demais PREMISSAS. Definição: Chamamos ARGUMENTO toda afirmação de que uma dada sequência A1 , A2 ,A3 ,... , An , B (n 1) de proposições tem como consequência ou acarreta uma proposição final Q. Premissas: são Ai (0< i < n). MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Argumento e Regras de Inferência. Definição: Um ARGUMENTO A1 , A2 ,A3 ,... , An , B é VÁLIDO se, e somente se, sendo as premissas verdadeiras a conclusão B também é verdadeira, ou ainda, se e somente se, a fórmula A1 ^ A2 ^A3 ^... ^ An B é uma tautologia. Exemplo: O argumento que segue é válido? Se eu ganhar na Loteria, serei rico. Eu ganhei na Loteria. Logo, sou rico. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Argumento e Regras de Inferência. Definição: Um ARGUMENTO A1 , A2 ,A3 ,... , An , B é VÁLIDO se, e somente se, sendo as premissas verdadeiras à conclusão B também são verdadeiras, ou ainda, se e somente se, a fórmula A1 ^ A2 ^A3 ^... ^ An B é uma tautologia. Exemplo: O argumento que segue é válido? Se eu ganhar na Loteria, serei rico. Eu ganhei na Loteria. Logo, sou rico. É Válido (a conclusão é uma decorrência lógica das duas premissas). MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Exemplo: O argumento que segue é válido? Se eu ganhar na Loteria, serei rico Eu não ganhei na Loteria Logo, não sou rico MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional Exemplo: O argumento que segue é válido? Se eu ganhar na Loteria, serei rico Eu não ganhei na Loteria Logo, não sou rico Não é Válido (a conclusão não é uma decorrência lógica das duas premissas). AULA 12: Cálculo Proposicional MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Exemplo: Toda baleia é um mamífero. ( V ) Todo mamífero tem pulmões. ( V ) Logo, toda baleia tem pulmões. ( V ) É Válido e a conclusão é verdadeira. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional REGRAS DE INFERÊNCIA A fórmula a implica tautologicamente a fórmula b (a b) se e somente se: a fórmula a b é uma tautologia. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Exemplo: MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional EQUIVALÊNCIAS TAUTOLÓGICAS As fórmulas a e b são tautologicamente equivalentes (a b) se, e somente se: fórmula a b é uma tautologia MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Exemplo: MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Exemplo: Determine se o argumento dado é valido e se sua conclusão deve ser verdadeira apenas pela validade do argumento. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 12: Cálculo Proposicional Exemplo: Determine se o argumento dado é valido e se sua conclusão deve ser verdadeira apenas pela validade do argumento. Seja p a proposição e q a proposição 2 > As premissas do argumento são p q e p e q é a conclusão. Esse argumento é válido pois é construído de acordo com modus ponens, uma forma válida de argumento. No entanto, é falsa. Consequentemente, não podemos deduzir que a conclusão seja verdadeira. Neste caso, notamos que a conclusão é falsa, pois 2 < 9/4. MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 12: Cálculo Proposicional Sugestão de resolução dos exercícios propostos. 1- Mostre que os argumentos abaixo são válidos, utilizando tabela verdade e as regras de inferência: Se o programa é eficiente, ele executará rapidamente. O programa é eficiente ou tem um erro. O programa não executa rapidamente. Portanto o programa tem um erro; Exercícios Propostos MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 12: Cálculo Proposicional p: O programa é eficiente q: O programa executa rápido r: O programa tem um erro. Temos então, na linguagem simbólica, as premissas p → q, p r, ~q e a conclusão r, ou seja, (p → q) (p ν r) (~q) r Exercícios Propostos Sugestão de resolução dos exercícios propostos. 1- Mostre que os argumentos abaixo são válidos, utilizando tabela verdade e as regras de inferência: Se o programa é eficiente, ele executará rapidamente. O programa é eficiente ou tem um erro. O programa não executa rapidamente. Portanto o programa tem um erro; MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 12: Cálculo Proposicional Sugestão de resolução dos exercícios propostos. (p → q) (p ν r) (~q) r p q r p → q p r ~q r V V V V V F V V V F V V F F V F V F V V V V F F F V V F F V V V V F V F V F V F F F F F V V V V V F F F V F V F Exercícios Propostos MATEMÁTICA APLICADA A COMPUTAÇÃOAULA 12: Cálculo Proposicional As premissas são (1) p → q (2) p r (3) ~q (4) ~p , modus tollens nas premissas (1) e (3) (5) r silogismo disjuntivo nas premissas (2) e (4); Portanto, podemos concluir a proposição “r” das premissas (1), (2) e (3), ou seja, o argumento é válido. Exercícios Propostos Sugestão de resolução dos exercícios propostos. MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 12: Cálculo Proposicional Exercícios Propostos Sugestão de resolução dos exercícios propostos. 2- Mostre a regra da Adição MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 12: Cálculo Proposicional Lembre-se: FORMA NORMAL CONJUNTIVA (FNC) ou em uma FORMA NORMAL DISJUNTIVA (FND) 1. substitui-se fórmulas: a. A B por ~A B Exercícios Propostos Sugestão de resolução dos exercícios propostos. 2) Mostre a regra da Adição Solução: Regra de Adição p p q ~p (p q) (~p p) q MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 12: Cálculo Proposicional ~p p ~p p V F V V F V F V V F V V Exercícios Propostos Sugestão de resolução dos exercícios propostos. 2) Mostre a regra da Adição Solução: Regra de Adição p p q ~p (p q) (~p p) q MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 12: Cálculo Proposicional ~p p ~p p V F V V F V F V V F V V Exercícios Propostos Sugestão de resolução dos exercícios propostos. 2) Mostre a regra da Adição Solução: Regra de Adição p p q ~p (p q) (~p p) q V q V. MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 12: Cálculo Proposicional Sugestão de resolução dos exercícios propostos. 3) Mostre a Regra Modus Ponens Exercícios Propostos MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 12: Cálculo Proposicional Sugestão de resolução dos exercícios propostos. 3) Mostre a Regra Modus Ponens Solução: (p q) ^ p q (~p q) ^ p q (~p ^ p) (q ^ p) q F (q ^p) q (q ^ p) q ~(q ^p) q (~q ~ p) q (~q q) ~ p V ~ p V. Exercícios Propostos MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 12: Cálculo Proposicional Sugestão de resolução dos exercícios propostos. 4) Mostrar, sem usar tabela verdade, que : (~p q) ^ p q Exercícios Propostos MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 12: Cálculo Proposicional Sugestão de resolução dos exercícios propostos. 4) Mostrar, sem usar tabela verdade, que : (~p q) ^ p q Solução: (~p q) ^p q ~((~p q) ^p) q (p ^~ q) ~ p q (p ^ ~ q) ~( p ^ ~ q) V. Exercícios Propostos MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 12: Cálculo Proposicional Sugestão de resolução dos exercícios propostos. 5- Diga qual regra de inferência é base do seguinte argumento: "Está esfriando e chovendo agora. Portanto, está esfriando agora.“ Exercícios Propostos MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 12: Cálculo Proposicional Sugestão de resolução dos exercícios propostos. 5- Diga qual regra de inferência é base do seguinte argumento: "Está esfriando e chovendo agora. Portanto, está esfriando agora.“ Solução: Seja p a proposição "Está esfriando" e q a proposição "Está chovendo agora.." Então, esse argumento é da forma: p ^ q ------ ∴p Esse é um argumento que usa a regra da simplificação. Observação: ∴ representa portanto. Exercícios Propostos MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 12: Cálculo Proposicional Sugestão de resolução dos exercícios propostos. 6) Diga qual regra de inferência é base do seguinte argumento: "Se chover, então não haverá churrasco hoje. Se não houver churrasco hoje, haverá amanhã. Portanto, se chover hoje, então haverá churrasco amanhã.“ Exercícios Propostos MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 12: Cálculo Proposicional Sugestão de resolução dos exercícios propostos. 6) Diga qual regra de inferência é base do seguinte argumento: "Se chover, então não haverá churrasco hoje. Se não houver churrasco hoje, haverá amanhã. Portanto, se chover hoje, então haverá churrasco amanhã.“ Solução: Seja p a proposição "Está chovendo hoje" e q a proposição "Não terá churrasco hoje" e r a proposição "Terá churrasco amanhã" Então, esse argumento é da forma: p q Q r ------ ∴ p r Esse é um argumento é um silogismo hipotético. Exercícios Propostos MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 12: Cálculo Proposicional Indicação de Leitura Específica • Recomendamos a leitura do capítulo referente Teoria de Conjuntos no material didático. • Acesse a Biblioteca Virtual da Estácio e pesquise mais exercícios nos livros de Teoria de Conjuntos disponíveis. Sugestão de material: http://www.otricolor.com/images/noticias/1278/Inicia%E7%E3o%20a%20L%F3gica%20Matem%E1tic a.%20Edegard%20Filho.%20Editota%20Nobel%20(1).pdf https://www.google.com.br/?gfe_rd=cr&ei=TdqhVaOOEeGB8QeEu4DIDA&gws_rd=ssl#q=Proposi%C3 %A7%C3%B5es+Simples http://www.feata.edu.br/downloads/revistas/avessodoavesso/v3_artigo04_logica.pdf http://uol.iesde.com.br/aprovaconcursos/demo_aprova_concursos/raciocinio_logico_01.pdf Indicação de Leitura MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 12: Cálculo Proposicional Indicação de Leitura Específica Sugestão de leitura: http://renecomputer.net/lg/aula10.pdf http://homepages.dcc.ufmg.br/~loureiro/md/md_1FundamentosDaLogica.pdf Indicação de Leitura VAMOS AOS PRÓXIMOS PASSOS? Unidade 6 - Cálculo dos Predicados 6.1. Predicados. Conjunto Universo. Conjunto Verdade; 6.2. Quantificadores; 6.3. Variáveis Livres e Ligadas. Alcance do Quantificador.
Compartilhar