Baixe o app para aproveitar ainda mais
Prévia do material em texto
CCT0350 – MATEMÁTICA APLICADA A COMPUTAÇÃO Aula 11: Cálculo Proposicional MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Álgebra de Booleana aplicada à construção de tabelas verdade - Três operações ou funções básicas. • operação OU, • operação E • complementação. Todas as funções Booleanas podem ser representadas em termos dessas operações básicas. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional - Operação OU (Adição Lógica) Assume valor 1 - se pelo menos uma das variáveis de entrada vale 1. Assume valor zero - somente quando todas as variáveis de entrada valem 0. Símbolo: + , tal como o símbolo da adição algébrica (dos reais). Teoria de conjuntos: OU é representado pela união. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Atenção: Variáveis Booleanas adição lógica. Operação OU : 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 1 Observação: Operação OU só pode ser definida se houver, pelo menos, duas variáveis envolvidas. Por isso operador + (OU) é dito binário. Propriedades: associativa e comutativa. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Operação E (Multiplicação Lógica) resulta 0 se pelo menos uma das variáveis de entrada vale 0. será 1 se, e somente se, todas as entradas valerem 1. Símbolo: ×. Teoria dos conjuntos: E é representado pela interseção. Operação E: 0 ×0 = 0 0 ×1 = 0 1 ×0 = 0 1 ×1 = 1 Observação: só pode ser definida entre, pelo menos, duas variáveis. Operador × (E) também é binário. Propriedades: associativa e comutativa. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Complementação (ou Negação, ou Inversão) Valor complementar ao que a variável apresenta. O valor complementar será: 1 se a variável vale 0 0 se a variável vale 1. Símbolos: variável Booleana A são , ~A e A' (lê-se A negado). Observação: só é definida sobre uma variável, ou sobre o resultado de uma expressão. O operador complementação é dito unário. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Tautologia, Contradição e Contingência; - Tautologia Definição: Uma tautologia é uma fórmula proposicional a n variáveis, p1, p2, ... pn que ao ser aplicada a quaisquer n proposições,representadas pelas variáveis p1, p2, ... p n, resulta em proposição verdadeira. Exemplo: fórmula proposicional p ^ q p. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Vamos verificar utilizando a tabela verdade: MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Vamos verificar utilizando a tabela verdade: MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Vamos verificar utilizando a tabela verdade: MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Exemplo: fórmula proposicional ~p p é uma tautologia ? https://ccbela.wordpress.com MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Exemplo: fórmula proposicional ~p p é uma tautologia ? ~p p ~p p V F V V F V F V V F V V P é uma tautologia = P é uma fórmula proposicional tautológica = P é logicamente verdadeira. Símbolo: Uma tautologia é em geral indicada por V, T ou 1. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional - Contradição Definição: Uma contradição é uma fórmula proposicional a n variáveis, p1, p2, ... pn que, ao ser aplicada a quaisquer n proposições, representadas pelas variáveis p1, p2, ... pn, resulta em proposição falsa. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Exemplo: fórmula proposicional p ^(~p ^ q ). MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Exemplo: fórmula proposicional p ^(~p ^ q ). MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Exemplo: fórmula proposicional p ^(~p ^ q ). MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional - Contingência Definição: Contingência ocorre quando há tanto valores V como F na última coluna da tabela verdade de uma proposição. Em outras palavras, será contingência se não for tautologia e nem contradição. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional - Contingência Exemplos: p q MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Implicação Lógica Definição: Proposições compostas P e Q, diz-se que ocorre uma implicação lógica (ou relação de implicação ou proposição condicional) entre P e Q quando a proposição condicional P Q é uma tautologia, ou seja, diz-se que uma proposição P implica logicamente uma proposição Q, se Q é verdadeira todas as vezes que P é verdadeira. Notação : P Q (P implica Q) MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Diferença entre e O símbolo representa uma operação matemática entre as proposições P e Q que tem como resultado a proposição P Q, com valor lógico V ou F. O símbolo representa a não ocorrência de VF na tabela-verdade de P Q, ou ainda que o valor lógico da condicional P Q será sempre V, ou então que P Q é uma tautologia. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Exemplo: fórmulas proposicionais P: p ^ q e Q: p, temos que P Q é tautológica, portanto, P Q. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Exemplo: 5 x 5 = 20 (2+1)2 = 32. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Exemplo: 5 x 5 = 20 (2+1)2 = 32. 5 x 5 = 20 (2+1)2 = 32 é verdadeira MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Exemplo: 5 x 5 = 20 (2+1)2 = 32. 5 x 5 = 20 (2+1)2 = 32 é verdadeira 5 x 5 = 20 (2+1)2 = 32. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Exemplo: 3 > 2 3 > 4. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Exemplo: 3 > 2 3 > 4. 3 > 2 3 > 4 é falsa MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Exemplo: 3 > 2 3 > 4. 3 > 2 3 > 4 é falsa 3 > 2 3 > 4 MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Exemplo: (p ^ q) (p q): (p ^ q) (p q) é uma tautologia, por isso (p ^ q) (p q) MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Equivalência Lógica Dizemos que uma fórmula proposicional P é equivalente à fórmula proposicional Q ou, simplesmente, que P é equivalente a Q se a fórmula proposicional P Q é tautológica. Notação: Para indicar que P é equivalente a Q usamos a notação P Q. MATEMÁTICAAPLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Equivalência Lógica Exemplo: fórmulas proposicionais P: p q e Q : ~p q, temos que P Q é tautológica, portanto P Q. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Observação: Os símbolos e são distintos! indica uma operação lógica. estabelece que P Q é tautológica (estabelece uma relação entre P e Q). Propriedades Reflexiva : P P Simétrica : Se P Q então Q P Transitiva: Se P Q e Q R, então P R MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Equivalências Tautológicas As fórmulas a e b são tautologicamente equivalentes e indicamos a b se e somente se a fórmula a b é uma tautologia MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Exemplo: Fórmulas A: p (q ^ r) e B : ~(q ^ r ) ~ p vamos verificar que A B, ou ainda que A / B. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Exemplo: 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. MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional Exemplo: Fórmulas A: p (q ^ r) e B : ~(q ^ r ) ~ p vamos verificar que A B, ou ainda que A / B. A B pois A B é tautologia MATEMÁTICA APLICADA A COMPUTAÇÃO Cálculo Proposicional AULA 11: Cálculo Proposicional As TAUTOLOGIAS são infinitas e desempenham um importante papel nos processos de dedução no Cálculo Proposicional. MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 11: Cálculo Proposicional Sugestão de resolução dos exercícios propostos. 1- Monte a tabela lógica que representa: Exercícios Propostos MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 11: Cálculo Proposicional Exercícios Propostos Sugestão de resolução dos exercícios propostos. 1- Monte a tabela lógica que representa: MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 11: Cálculo Proposicional Sugestão de resolução dos exercícios propostos. 2- Utilizando tabelas verdade, verifique se existe a implicação lógica p ^ ~p q Exercícios Propostos MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 11: Cálculo Proposicional Sugestão de resolução dos exercícios propostos. 2- Utilizando tabelas verdade, verifique se existe a implicação lógica p ^ ~p q Verificamos que é uma tautologia portanto existe a implicação lógica. Exercícios Propostos MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 11: Cálculo Proposicional Sugestão de resolução dos exercícios propostos. 3- Utilizando tabelas verdade, verifique se existem as seguintes relações de implicação lógica: Exercícios Propostos MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 11: Cálculo Proposicional É uma tautologia! Exercícios Propostos Sugestão de resolução dos exercícios propostos. 3- Utilizando tabelas verdade, verifique se existem as relações de implicação lógica: MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 11: Cálculo Proposicional É uma tautologia! Exercícios Propostos Sugestão de resolução dos exercícios propostos. 3- Utilizando tabelas verdade, verifique se existem as relações de implicação lógica: MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 11: Cálculo Proposicional Não é uma tautologia! Exercícios Propostos Sugestão de resolução dos exercícios propostos. 3- Utilizando tabelas verdade, verifique se existem as relações de implicação lógica: MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 11: Cálculo Proposicional É uma tautologia! Exercícios Propostos Sugestão de resolução dos exercícios propostos. 3- Utilizando tabelas verdade, verifique se existem as relações de implicação lógica: MATEMÁTICA APLICADA A COMPUTAÇÃO AULA 11: 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%E1ti ca.%20Edegard%20Filho.%20Editota%20Nobel%20(1).pdf https://www.google.com.br/?gfe_rd=cr&ei=TdqhVaOOEeGB8QeEu4DIDA&gws_rd=ssl#q=Proposi%C 3%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 11: Cálculo Proposicional Indicação de Leitura Específica Sugestão de leitura: https://docente.ifrn.edu.br/cleonelima/disciplinas/fundamentos-de-programacao- 2.8401.1m/fundamentos-de-logica-e-algoritmos-1.8401.1v/apostila-equivalencias-logicas Indicação de Leitura VAMOS AOS PRÓXIMOS PASSOS? Unidade 5 – Cálculo Proposicional 5.10. Formas Normais. Problema de Post; 5.11. Conjuntos Adequados de Conectivos; 5.12. Argumento e Regras de Inferência.
Compartilhar