lista 1 matematica discreta 2017 1

Prévia do material em texto

Universidade Federal do Esp´ırito Santo - UFES
Centro de Cieˆncias Exatas, Naturais e da Sau´de - CCENS
Departamento de Computac¸a˜o - DECOMP
Lista de Exerc´ıcios (1) - Noc¸o˜es de Lo´gica
1. Sabendo que os valores verdade das proposic¸o˜es p e q sa˜o respectivamente V e F , determine o valor
lo´gico (V ou F ) de cada uma das seguintes proposic¸o˜es:
a) p ∧ ¬q
b) p ∨ ¬q
c) ¬p ∨ q
d) ¬p ∧ ¬q
e) ¬p ∨ ¬q
f) p ∧ (¬p ∨ q)
2. Determine V (p) em cada um dos seguintes casos, sabendo que:
a) V (q) = V e V (p ∧ q) = F
b) V (q) = F e V (p ∨ q) = F
c) V (q) = F e V (p→ q) = F
d) V (q) = F e V (q → p) = V
e) V (q) = V e V (p↔ q) = F
f) V (q) = F e V (q ↔ p) = V
3. Determine V (p) e V (q) em cada um dos casos, sabendo que:
a) V (p→ q) = V e V (p ∧ q) = F
b) V (p→ q) = V e V (p ∨ q) = F
c) V (p↔ q) = V e V (p ∧ q) = V
d) V (p↔ q) = V e V (p ∨ q) = V
e) V (p↔ q) = F e V (¬p ∨ q) = V
4. Construa as tabelas verdade das seguintes fo´rmulas e identifique as que sa˜o tautologias ou con-
tradic¸o˜es:
a) ¬(p ∨ ¬q)
b) ¬(p→ ¬q)
c) p ∧ q → p ∨ q
d) ¬p→ (q → p)
e) (p→ q) → p ∧ q
f) q ↔ ¬q ∧ p
g) p→ (q → (q → p))
h) ¬(p→ (¬p→ q))
i) p ∧ q → (p↔ q ∨ r)
j) ¬p ∧ r → q ∨ ¬r
k) p→ r ↔ q ∨ ¬r
l) p→ (p→ ¬r) ↔ q ∨ r
m) (p ∧ q → r) ∨ (¬p↔ q ∨ ¬r)
5. Prove, usando tabela-verdade, as seguintes equivaleˆncias:
a) Idempoteˆncia
p ∧ p⇔ p
p ∨ p⇔ p
b) Comutativa
p ∧ q ⇔ q ∧ p
p ∨ q ⇔ q ∨ p
c) Associativa
p ∧ (q ∧ r) ⇔ (p ∧ q) ∧ r
p ∨ (q ∨ r) ⇔ (p ∨ q) ∨ r
d) Distributiva
p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r)
p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)
6. Prove, usando tabela-verdade, que qualquer um dos conetivos estudados pode ser expresso usando-se
somente os conetivos ¬ e ∧.
7. Prove, usando tabela-verdade, que os seguintes conetivos podem ser expressos usando os conetivos
ja´ estudados:
a) Conetivo EXOR (abreviatura dos termos em ingleˆs exclusive e or cuja semaˆntica e´ dada pela
Tabela 1.
1
Universidade Federal do Esp´ırito Santo - UFES
Centro de Cieˆncias Exatas, Naturais e da Sau´de - CCENS
Departamento de Computac¸a˜o - DECOMP
b) Conetivo NAND (abreviatura dos termos em ingleˆs not e and cuja semaˆntica e´ dada pela
Tabela 1.
x y x EXOR y x NAND y
V V F F
V F V V
F V V V
F F F V
Tabela 1: Tabela-verdade: EXOR e NAND
2