Matematica-Discreta_Logica

Prévia do material em texto

1 
I Lista de Exercícios – Matemática Discreta 
Lógica 
 
1. Faça os seguintes cálculos: 
a. FVVVV ∧∧∧∧ 
b. ( ) VV ∨¬ 
c. ( )VV ∨¬ 
d. ( ) FVV ∧∨ 
e. ( )FVV ∧∨ 
 
2. Quais das frases a seguir são sentenças? 
a. A lua é feita de queijo verde. 
b. Ele é um homem alto. 
c. Dois é um número primo. 
d. O jogo terminará logo? 
e. Que bom! 
f. x –(– 4 ) = 0. 
 
3. Prove: ( ) ( )yxyx ¬∧∨∧ é logicamente equivalente a x. 
 
4. Prove que yx↔ é logicamente equivalente a ( ) ( )yx ¬↔¬ . 
 
5. Prove que yx↔ é logicamente equivalente a ( ) ( )xyyx →∧→ . 
 
6. Prove que yx↔ é logicamente equivalente a ( ) ( ) ( )( )yxyx ¬→¬∧→ . 
 
7. Prove que ( ) zyx →∨ é logicamente equivalente a ( ) ( )zyzx →∧→ . 
 
8. Responda à seguinte pergunta, justificando sua resposta: “Qual a relação dos valores lógicos de 
duas sentenças equivalentes?” 
 
9. Suponha que tenhamos duas expressões booleanas que envolvam dez variáveis. Para provar que 
essas duas expressões são logicamente equivalentes, construímos uma tabela verdade. Quantas 
linhas, além da linha do cabeçalho, essa tabela teria? 
 
10. Como se refutaria uma equivalência lógica? Mostre que: 
a. yx→ não é logicamente equivalente a xy→ . 
b. yx→ não é logicamente equivalente a yx↔ . 
c. yx ∨ não é logicamente equivalente a ( ) ( )( )yxyx ∧¬∨¬∨ . 
 
11. Prove que as expressões seguintes são tautologias: 
a. ( ) ( )( )yxyx ¬∨∨∨ . 
b. ( )( ) yyxx →→∧ . 
c. ( )( ) xx ↔¬¬ . 
d. xx→ . 
 
 2 
e. ( ) ( )( ) ( )zxzyyx →→→∧→ . 
f. xF → . 
 
12. Todas as sentenças tautológicas são equivalentes? Por quê? 
 
13. Prove que as expressões seguintes são contradições: 
a. ( ) ( )( ) xyxyx ¬∧¬∨∧∨ . 
b. ( ) ( )yyxx ¬∧→∧ . 
c. ( ) ( )( ) yyxyx ¬∧→¬∧→ . 
 
14. Todas as sentenças contraditórias são equivalentes? Por quê? 
 
15. Construa as t tabelas-verdade das sentenças: “(P∨Q)→R” e “P∨ (Q→R)”. Discuta a 
importância da posição dos parênteses numa sentença. 
 
16. Eis outra operação booleana chamada ou-exclusivo. Denota-se pelo símbolo v e é definido pela 
tabela seguinte: 
 
x y x v y 
V V F 
V F V 
F V V 
F F F 
 
a. Prove que x v y é logicamente equivalente a ))(()( yxyx ∧¬∨¬∧ . 
b. Prove que x v y é logicamente equivalente a ))(()( yxyx ∧¬∧∨ . 
c. Explique por que a operação v é chamada ou-exclusivo. 
 
17. Marque a alternativa correta: 
a. O conjunto { }0)1)(2(; ≠−−∈= xxRxB pode ser representado na forma 
1. { }.21; ≠≠∈= xexRxB 
2. { }.21; ≠≠∈= xouxRxB 
 
b. Se { }11; <≤−∈= xRxA e se ,Ax∉ então Rx∈ é tal que 
1. .1ou 1 −<> xx 
2. .1 e 1 −<≥ xx 
3. .1ou 1 ≥−< xx 
 
18. Dados os valores-verdade A verdadeiro, B falso e C verdadeiro, qual o valor-verdade de cada 
uma das expressões booleanas? 
a. ( )CBA ∨∧ 
b. ( ) CBA ∨∧ 
c. ( ) CBA ∨∧¬ 
d. ( )CBA ∧¬¬∨¬ 
 
 3 
19. Quais os valores-verdade das seguintes sentenças? 
a. 8 é par ou 6 é ímpar. 
b. 8 é par e 6 é ímpar. 
c. 8 é ímpar ou 6 é ímpar. 
d. 8 é ímpar e 6 é ímpar. 
e. Se 8 é ímpar, então 6 é ímpar. 
f. Se 8 é par, então 6 é ímpar. 
g. Se 8 é ímpar, então 6 é par. 
h. Se 8 é ímpar e 6 é par, então 8 < 6. 
 
20. Sabendo-se que as afirmações abaixo são falsas, o que podemos afirmar em cada uma delas? 
a. Mário vai viajar e jogar futebol. 
1. Mário não vai jogar futebol, mas vai viajar. 
2. Mário não vai viajar ou não vai jogar futebol. 
3. Mário não vai viajar e nem jogar futebol. 
 
 b. Luiz irá visitar seus tios ou seus avós. 
1. Luiz não irá visitar seus tios ou seus avós. 
2. Luiz não irá visitar seus tios e seus avós. 
3. Luiz não irá visitar seus tios e nem seus avós. 
 
 c. x < y e z é ímpar. 
1. x > y e z é par. 
2. x ≥ y e z é par. 
3. x ≥ y ou z é ímpar. 
4. x ≥ y ou z é par. 
 
21. Com o uso de letras para denotar as sentenças componentes, traduza as seguintes sentenças 
compostas para notação simbólica: 
a. Tanto ir para cama como nadar é condição suficiente para trocar de roupa; no entanto, 
trocar de roupa não significa que se vai nadar. 
b. Ou vai chover ou vai nevar, mas não ambos. 
c. Se Janet vencer ou perder, ela estará cansada. 
d. Ou Janet irá vencer ou, se perder, ficará cansada. 
 
22. Explique por que “ 1010 ≥ ” é uma sentença verdadeira. 
 
23. Seja p : “está frio” e seja q : “está chovendo”. Escreva uma sentença verbal que descreva cada 
proposição. 
a) ¬p 
b) p ∧ q 
c) p ∨ q 
d) q ∨ ¬ p 
e) ¬p ∧ ¬q 
f) ¬ ¬ p 
 
24. Seja p : “ele é alto” e q : “ele é bonito”. Escrever cada uma das proposições na forma 
simbólica. 
a) Ele é alto e bonito. 
b) Ele é alto mas não bonito. 
c) É falso que ele é baixo e bonito. 
d) Ele não é alto, nem bonito. 
e) Ele é alto, ou ele é baixo e bonito. 
 
 4 
25. Dentre as afirmações a seguir, detecte quais não representam a idéia do que seja um número 
par. 
Um número par é um número inteiro m tal que 
a. m = 2k , para algum .Zk∈ 
b. m é da forma 2k , para todo .Zk∈ 
c. ,Zk∈∀ m = 2k. 
d. ,Zk∈∃ m = 2k. 
 
26. Determine o valor lógico das seguintes sentenças, justificando sua resposta: 
a. Existem dois números primos entre os números 22 e 32, ou .3>π 
b. Se x é um número real, então 013 >−x e .02 >x 
c. 93 >− e 35 < , ou .325 > 
 
27. Sejam x, y .R∈ Responda às seguintes perguntas, justificando sua resposta: 
a. Se você não conhece os números x e y, e alguém afirma “x > 0 ou y > 0”, pode-se concluir que: 
1. x pode ser negativo? 
2. y pode ser zero? 
3. x pode ser negativo ou zero? 
4. y não pode ser negativo? 
 
b. E se essa pessoa diz “x > 0 e y < 0”, então: 
1. x ou y podem ser nulos? 
2. x e y podem ser nulos? 
3. x ou y podem ser positivos? 
4. x pode ser negativo ou nulo ou y pode ser positivo? 
 
28. Marque a alternativa correta para as seguintes questões. Sua resposta só é válida com a respectiva 
justificativa. 
a. O conjunto { }0)1)(2(; =−−∈= xxRxA pode ser representado na forma 
1. { }1 e 2; ==∈= xxRxA 2. { }1ou 2; ==∈= xxRxA
 
b. Se Ryx ∈, são tais que 0<
y
x , podemos afirmar: 
1. 0ou 0 << yx 
2. 0 e 0 << yx 
3. 0ou 0 <> yx 
4. 0ou 0 >< yx 
5. ( ) ( )0 e 0ou 0 e 0 ><<> yxyx 
6. ( ) ( )0ou 0 e 0ou 0 ><<> yxyx 
 
c. Se Ryx ∈, são tais que 0. >yx , podemos afirmar: 
1. 0ou 0 >> yx 
2. 0 e 0 >> yx 
 
3. ( ) ( )0 e 0ou 0 e 0 <<>> yxyx 
4. ( ) ( )0ou 0 e 0ou 0 <<>> yxyx 
29. Ao resolverem uma equação algébrica do segundo grau na variável x, quatro alunos escreveram 
suas respostas de maneiras distintas. Eles afirmaram que as raízes eram: 
a. “x = 2 e x = 3” 
b. “x = 2 ou x = 3” 
c. “x1 = 2 e x2 = 3” 
d. “x1 = 2 ou x2 = 3
Quais das respostas estão formuladas se maneira correta? Por quê?