I Lista de Exercícios – Matemática Discreta
Lógica

1. Faça os seguintes cálculos:
a.
b.
c.
d.
e.

2. Prove: é logicamente equivalente a x.

3. Prove que é logicamente equivalente a .

4. Prove que é logicamente equivalente a .

5. Prove que é logicamente equivalente a .

6. Prove que é logicamente equivalente a .

7. Responda à seguinte pergunta, justificando sua resposta: “Qual a relação dos valores lógicos de duas sentenças equivalentes?” 8. 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?

9. Como se refutaria uma equivalência lógica? Mostre que:
a. não é logicamente equivalente a .
b. não é logicamente equivalente a .
c. não é logicamente equivalente a .

10. Prove que as expressões seguintes são tautologias:
a. .
b. .
c. .
d. .
e. .
f. .

11. Todas as sentenças tautológicas são equivalentes? Por quê?

12. Prove que as expressões seguintes são contradições:
a. .
b. .
c. .

13. Todas as sentenças contraditórias são equivalentes? Por quê?

14. 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 v verifica as propriedades comutativa e associativa; isto é, prove as equivalências lógicas x v y = y v x e (x v y) v z = x v (y v z).
b. Prove que x v y é logicamente