Algebra_das_proposies

Prévia do material em texto

Álgebra das Proposições 
 
 As regras de inferência são chamadas regras 
de substituição porque estabelecem as 
transformações entre proposições logicamente 
equivalentes. Por exemplo, a proposição pode 
ser inferida a partir da proposição ~~p, e é a 
partir desta regra de inferência que iniciamos a 
nossa lista. 
Álgebra das Proposições 
Propriedades da Conjunção 
• Idempotência 
 
p ^ p  p 
 
• Comutatividade 
 
p ^ q  q ^ p 
 
 
 
Propriedades da Conjunção 
• Associatividade 
(p ^ q) ^ r  p ^ (q ^ r) 
 
 
Propriedades da Disjunção 
• Idempotência 
 
p v p  p 
 
• Comutatividade 
 
p v q  q v p 
 
 
 
Propriedades da Disjunção 
• Associatividade 
(p v q) v r  p v (q v r) 
 
 
■ Propriedades Distributivas 
□ p v (q ^ r)  (p v q) ^ (p v r) 
□ p ^( q v r)  (p ^ q ) v (p ^ r) 
Note que a fórmula possui 
conjunção e disjunção. 
Diferente da associativa 
que possui uma ou outra, 
mas não ambas ao mesmo 
tempo. 
Propriedades da Conjunção e 
da Disjunção 
 
■ Propriedade Comutativa 
□ p v q  q v p 
□ p ^ q  q ^ p 
□ p ↔ q  q ↔ p 
Álgebra das Proposições 
■ Propriedade Associativa 
□ (p v q) v r  p v (q v r) 
□ (p ^ q) ^ r  p ^ (q ^ r) 
 
 
Em geral, o que esta regra de inferência nos diz é 
que em conjunções e disjunções a ordem das 
proposições componentes não altera o valor lógico 
do conjunto, assim, os parênteses poderiam ser 
removidos, como em p˄q˄r, sem gerar ambiguidade. 
A ordem das proposições 
não altera o resultado 
Álgebra das Proposições 
■ Leis de De Morgan 
□ ~(p ^ q)  ~p v ~q 
□ ~(p v q)  ~p ^ ~q 
 
■ Propriedade da Dupla Negação 
□ ~(~p)  p 
 
■ Propriedade da Condicional 
□ pq  ~p v q 
□ ~(p  q)  ~(~ p ˅ q)  p ^ ~ q 
Álgebra das Proposições 
■ Propriedades dos Elementos Neutros 
□ p v F  p 
□ p ^ V  p 
■ Propriedade de Negação 
□ p v ~p  V 
□ p ^ ~p  F 
■ Transposição (Contrapositiva) 
□ p → q  ~q → ~p 
 
 
Álgebra das Proposições 
■ Propriedades de Dominação 
□ p v V  V 
□ p ^ F  F 
■ Propriedades Idempotentes 
□ p v p  p 
□ p ^ p  p 
■ Propriedade de Absorção 
□ p v (p ^ q)  p 
□ p ^ (p v q)  p 
Álgebra das Proposições 
p ↔ q  (p  q) ^ (q  p) 
p ↔ q  ~p ↔ ~q 
Álgebra das Proposições 
Exercícios 
Exercícios 
Demonstrar por tabelas-verdade as 
equivalências: 
 
a) p  q  r  (p  q)  (p  r) 
b) p  q  r  (p  q)  (p  r) 
 
As Olimpíadas de 2016 foram realizadas no Rio 
de Janeiro e dentre as modalidades de esportes o 
voleibol masculino obteve um grande resultado, 
ganhando medalha de ouro como a muito tempo 
merecido. Sabemos que “se um time de voleibol 
ganha três sets então ele ganha a partida”. Uma 
regra equivalente a esta seria: 
 
A.Se um time de voleibol ganha a partida então 
ele ganha três sets. 
B.Se o time de voleibol não ganha os três sets 
então ele não ganha a partida 
C.O time de voleibol não ganha os três sets ou ele 
ganha a partida 
D.O time de voleibol ganha três sets e ganha a 
partida 
As Olimpíadas de 2016 foram realizadas no 
Rio de Janeiro e dentre as modalidades de 
esportes o voleibol masculino obteve um 
grande resultado, ganhando medalha de 
ouro como a muito tempo merecido. 
Sabemos que “se um time de voleibol 
ganha três sets então ele ganha a partida”. 
Uma regra equivalente a esta seria: 
 
p: um time de voleibol ganha três sets q: 
ele ganha a partida 
p: um time de voleibol ganha três sets 
q: ele ganha a partida 
p q 
 
A.Se um time de voleibol ganha a partida então 
ele ganha três sets.(qp) 
B.Se o time de voleibol não ganha os três sets 
então ele não ganha a partida (~p~q) 
C.O time de voleibol não ganha os três sets ou 
ele ganha a partida (~p v q) 
D.O time de voleibol ganha três sets e ganha a 
partida (p ^ q) 
p q 
 
A) (qp) 
B) (~p~q) 
C)(~p v q) 
D)(p ^ q) 
pq  ~p v q (propriedade condicional) 
pq  ~q~p (Contrapositiva) 
 
A) (qp) 
B) (~p~q) 
C)(~p v q) 
D)(p ^ q) 
(ESAF/AFC/2002) Dizer que não é verdade 
que Pedro é pobre e Alberto é alto, é 
logicamente equivalente a dizer que é 
verdade que: 
 
A.Pedro não é pobre ou Alberto não é alto; 
B.Pedro não é pobre e Alberto não é alto; 
C.Pedro é pobre ou Alberto não é alto; 
D.Se Pedro não é pobre então Alberto não é 
alto. 
(ESAF/AFC/2002) Dizer que não é verdade 
que Pedro é pobre e Alberto é alto, é 
logicamente equivalente a dizer que é 
verdade que: 
 
p: Pedro é pobre q: Alberto é alto 
 
~(p ^ q) 
(ESAF/AFC/2002) Dizer que não é verdade 
que Pedro é pobre e Alberto é alto, é 
logicamente equivalente a dizer que é 
verdade que: 
 
p: Pedro é pobre q: Alberto é alto 
 
~(p ^ q) 
 
Vamos aplicar De Morgan!!! 
(ESAF/AFC/2002) Dizer que não é verdade 
que Pedro é pobre e Alberto é alto, é 
logicamente equivalente a dizer que é 
verdade que: 
 
p: Pedro é pobre q: Alberto é alto 
 
~(p ^ q)  ~p v ~q 
 
Vamos aplicar De Morgan!!! 
(ESAF/AFC/2002) Dizer que não é verdade 
que Pedro é pobre e Alberto é alto, é 
logicamente equivalente a dizer que é 
verdade que: 
 
p: Pedro é pobre q: Alberto é alto 
 
~(p ^ q)  ~p v ~q 
 
Pedro não é pobre ou Alberto não é alto!!! 
Um economista deu a seguinte declaração em 
uma entrevista: “Se os juros bancários são altos, 
então a inflação é baixa”. Assinale a alternativa 
que contém uma proposição logicamente 
equivalente à do economista: 
 
A)Se a inflação não é baixa, então os juros 
bancários não são altos; 
B)Se a inflação é alta, então os juros bancários 
são altos; 
C)Se os juros bancários não são altos, então a 
inflação não é baixa; 
D)Os juros bancários são baixos e a inflação é 
baixa. 
“Se os juros bancários são altos, então a inflação 
é baixa”. 
p: os juros bancários são altos q: inflação é 
baixa 
 
A)Se a inflação não é baixa, então os juros 
bancários não são altos; 
B)Se a inflação é alta, então os juros bancários 
são altos; 
C)Se os juros bancários não são altos, então a 
inflação não é baixa; 
D)Os juros bancários são baixos e a inflação é 
baixa. 
“Se os juros bancários são altos, então a inflação 
é baixa”. pq 
p: os juros bancários são altos q: inflação é 
baixa 
 
A)Se a inflação não é baixa, então os juros 
bancários não são altos; ~q~p 
B)Se a inflação é alta, então os juros bancários 
são altos; ~q  p 
C)Se os juros bancários não são altos, então a 
inflação não é baixa; ~p  ~q 
D)Os juros bancários são baixos e a inflação é 
baixa. ~p ^ q 
pq  ~p v q (propriedade condicional) 
p q  ~q~p (Contrapositiva) 
A)~q~p 
B)~q p 
C)~p ~q 
D)~p q 
Exercícios 
Usar equivalências lógicas para simplificar cada uma 
das seguintes proposições: 
 
a) ~p  (p  ~q) 
b) (p  q)  (p  ~q) 
c) (p  q)  (p  (~q  r)) 
d) ~(p  q)  ~(q  r) 
e) (p  q)  (p  ~q)  (~p  ~q) 
f) (q  (p  r))  (p  (q  ~r)) 
 
Mostre a equivalência lógica da seguinte 
proposição usando apenas as leis da lógica: 
 
(p → r) ∨ (q → r)  (p ∧ q) → r 
(p → r) ∨ (q → r)  (p ∧ q) → r 
 (~p ∨ r) ∨ (~q ∨ r)  
~p ∨ ~q ∨ r  
(~p ∨ ~q) ∨ r  
~(~p ∨ ~q) → r  
(p ∧ q) → r  
Simplifique a expressão: 
[p ∧ ~(~p v q)] v (p ∧ q) 
(p ∧ (~(~p ∨ q))) ∨ (p ∧ q) Lei De Morgan sobre 
~(~p ∨ q). 
(p ∧ (p ∧ ~q)) ∨ (p ∧ q) Propriedade da 
Associatividade sobre p ∧ (p ∧ ~q). 
((p ∧ p) ∧ ~q) ∨ (p ∧ q) Propriedade da 
Idempotência sobre p ∧ p. 
(p ∧ ~q) ∨ (p ∧ q) Propriedade da Distributividade. 
p ∧ (~q ∨ q) Negação sobre ~q ∨ q. 
p ∧ t Identidade com a tautologia t. 
p 
Demonstre, utilizando tabelas-verdade, as 
seguintes relações de equivalência: 
 
a) p  ( p  q )  p 
b) p  ( p  q )  p 
c) ( p  q )  ( p  r )  p  p  r 
 
 
Demonstre, utilizando tabelas-verdade, as 
seguintes relações de equivalência: 
 
a) p  ( p  q )  p (equivalentes) 
b) p  ( p  q )  p (equivalentes) 
c) (p  q )  ( p  r )  p  p  r (não 
equivalentes) 
 
Negue em linguagem corrente as seguintes 
proposições: 
 
a) Atlético é alvi-verde e Coritiba é rubro-negro. 
b) As vendas diminuem e os preços aumentam. 
c) É falso que está frio ou que está chovendo. 
d) Se João passar em Física então se formará. 
e) Não tenho carro e não tenho moto. 
 
a) Atlético não é alvi-verde ou Coritiba é rubro-
negro. 
b) As vendas não diminuem ou os preços não 
aumentam. 
c) Está frio ou está chovendo. 
d) João passa em Física e não se forma. 
e) Tenho carro ou tenho moto. 
 
Demonstre as relações abaixo utilizando as 
equivalências notáveis: 
 
a) p  q  r  ( p  q )  ( p  r ) 
b) p  q  r  ( p  q )  ( p  r ) 
c) p  ( r  s  t )  ( p  r )  ( p  s )  ( p  t ) 
d) p  q  r  p  ( q  r ) 
e) e) ~( ~p  ~q )  ~p  q 
 
 
 
a) p  q  r  ( p  q )  ( p  r ) 
p  q  r  
~p  ( q  r )  (reescrita da condicional) 
(~p  q)  (~p  r)  (distributiva) 
(p  q)  (p  r) (reescrita da condicional) 
 
b) p  q  r  ( p  q )  ( p  r ) 
p  q  r  
~p  ( q  r )  (reescrita da condicional) 
~p  q  r  (associativa) 
~p  ~p  q  r  (idempotente, adicionei um 
~p, pois ~p  ~p  ~p) 
 (~p  q)  (~p  r )  (associativa) 
(p  q)  (p  r) (reescrita da condicional) 
 
c) p  ( r  s  t )  ( p  r )  ( p  s )  ( p  t ) 
p  ( r  s  t )  
p  ( r  (s  t))  (associativa em s  t ) 
(p  r)  (p  (s  t))  (distributiva) 
(p  r)  (p  s)  (p  t) (distributiva) 
 
d) p  q  r  p  ( q  r ) 
p  q  r  
~(p  q)  r  (reescrita da condicional) 
~p  ~q  r  (De Morgan) 
~p  (~q  r)  (associativa) 
~p  ( q  r)  (reescrita da condicional) 
p  (q  r) (reescrita da condicional) 
 
e) ~( ~p  ~q )  ~p  q 
~( ~p  ~q )  
~( ~~p  ~q)  (reescrita da condicional) 
~(p  ~q)  (dupla negação) 
~p  ~~q  (De Morgan) 
~p  q (dupla negação) 
 
Demonstre as leis de Morgan para três 
proposições: 
 
a) ~( p  q  r )  ~p  ~q  ~r 
b) ~( p  q  r )  ~p  ~q  ~r 
 
 
a) ~( p  q  r )  ~p  ~q  ~r 
~(p  ( q  r) )  (associativa) 
~p  ~(q  r)  (De Morgan) 
~p  ~q  ~r (De Morgan) 
 
b) ~( p  q  r )  ~p  ~q  ~r 
~(p  ( q  r) )  (associativa) 
~p  ~(q  r)  (De Morgan) 
~p  ~q  ~r (De Morgan)