mdiscreta

I Lista de Exercícios – Matemática Discreta
Lógica
1. Faça os seguintes cálculos:
a. V ∧ V ∧ V ∧ V ∧ F
b. (¬V ) ∨ V
c. ¬(V ∨ V )
d. (V ∨ V ) ∧ F
e. V ∨ (V ∧ F )
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: (x ∧ y ) ∨ (x ∧ ¬y ) é logicamente equivalente a x.
4. Prove que x ↔ y é logicamente equivalente a (¬ x) ↔ (¬y ).
5. Prove que x ↔ y é logicamente equivalente a (x → y ) ∧ ( y → x).
6. Prove que x ↔ y é logicamente equivalente a (x → y ) ∧ ((¬ x) → (¬y )).
7. Prove que (x ∨ y ) → z é logicamente equivalente a (x → z ) ∧ ( y → z ).
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. x → y não é logicamente equivalente a y → x .
b. x → y não é logicamente equivalente a x ↔ y .
c. x ∨ y não é logicamente equivalente a (x ∨ ¬y ) ∨ ((¬ x) ∧ y ).
11. Prove que as expressões seguintes são tautologias:
a. (x ∨ y ) ∨ (x ∨ (¬y )).
b. (x ∧ (x → y )) → y .
c. ¬((¬ x)) ↔ x .
d. x → x .
1

e. ((x → y ) ∧ ( y → z )) → (x → z ).
f. F → x .
12. Todas as sentenças tautológicas são equivalentes? Por quê?
13. Prove que as expressões seguintes são contradições:
a. (x ∨ y ) ∧ (x ∨ (¬y )) ∧ ¬x .
b. x ∧ (x → y ) ∧ (¬y ).
c. (x → y ) ∧ ((¬ x) → y ) ∧ ¬y .
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