Buscar

Aula 11

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 50 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 50 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 50 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

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.

Outros materiais