apresentacao_da_aula 11

Prévia do material em texto

CCT0350 – MATEMÁTICA APLICADA A COMPUTAÇÃO
Aula 11: Cálculo Proposicional
1
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.
2
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.
3
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.
4
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.
5
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
6
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.
7
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. 
8
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo Proposicional
AULA 11: Cálculo Proposicional
Vamos verificar utilizando a tabela verdade:
9
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo Proposicional
AULA 11: Cálculo Proposicional
Vamos verificar utilizando a tabela verdade:
10
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo Proposicional
AULA 11: Cálculo Proposicional
Vamos verificar utilizando a tabela verdade:
11
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
12
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.
13
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.
14
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo Proposicional
AULA 11: Cálculo Proposicional
Exemplo: fórmula proposicional p ^(~p ^ q ). 
15
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo Proposicional
AULA 11: Cálculo Proposicional
Exemplo: fórmula proposicional p ^(~p ^ q ). 
16
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo Proposicional
AULA 11: Cálculo Proposicional
Exemplo: fórmula proposicional p ^(~p ^ q ). 
17
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.
18
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo Proposicional
AULA 11: Cálculo Proposicional
- Contingência
Exemplos: p q
19
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)
20
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.
21
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.
22
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo Proposicional
AULA 11: Cálculo Proposicional
Exemplo: 5 x 5 = 20  (2+1)2 = 32.
23
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
24
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.
25
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo Proposicional
AULA 11: Cálculo Proposicional
Exemplo: 3 > 2  3 > 4.
26
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo Proposicional
AULA 11: Cálculo Proposicional
Exemplo: 3 > 2  3 > 4.
3 > 2 3 > 4 é falsa
27
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
28
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)
29
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.
30
MATEMÁTICA APLICADA 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.
31
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
32
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
33
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo Proposicional
AULA 11: Cálculo Proposicional
34
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. 
35
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.
36
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
37
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.
38
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
39
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: 
40
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
41
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
42
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
43
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:
44
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:
45
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:
46
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:
47
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%E1tica.%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
48
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
49
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.
50