Sol_L10D131

Prévia do material em texto

MAT 01375 – Matema´tica Discreta B 2013/1
Lista de Exerc´ıcios 10
Soluc¸o˜es de Exerc´ıcios Escolhidos
3 (c).
x ∧ (x ∧ y) ∨ (x ∧ y) = x ∧ (y ∧ x) ∨ (y ∧ x) = x ∧
(
y ∧ (x ∨ x)
)
= x ∧ (y ∧ 1) = x ∧ y.
A primeira igualdade utiliza a comutatividade de ∧, a segunda segue da dis-
tributividade, a terceira vem da lei de complementaridade para ∨ e a quarta e´
consequeˆncia do fato de 1 ser identidade para ∧.
4 (a).
x ∧ 0 = x ∧ (x ∧ x) = (x ∧ x) ∧ x = x ∧ x = 0.
Para chegarmos a essa conclusa˜o, utilizamos a lei de complementaridade para ∧,
a associatividade de ∧, a idempoteˆncia de ∧ e, novamente, a lei de complementa-
ridade para ∧.
4 (d). Sejam x, y tais que x ∨ y = 0. Temos que
x = x ∧ (x ∨ y) = x ∧ 0 = 0,
onde a primeira igualdade vem do item 4(c), a segunda vem da hipo´tese e a
terceira da lei de complementaridade para ∧. Um argumento ana´logo demonstra
que y = 0.
4 (e). Suponha que x ∧ y = 0. Temos
x = x ∧ 1 = x ∧ (y ∨ y) = (x ∧ y) ∨ (x ∧ y) = (x ∧ y) ∨ 0 = x ∧ y,
onde a primeira igualdade vem de propriedade de identidade, a segunda da lei de
complementaridade para ∨, a terceira da distributividade, a quarta da hipo´tese e
a quinta de propriedade de identidade.
4 (f). Sejam x, y tais que (x∧y)∨(y∧x) = y. Por um lado, ((x ∧ y) ∨ (y ∧ x))∧y =
y ∧ y = 0. Por outro lado,
((x ∧ y) ∨ (y ∧ x)) ∧ y = y ∧ ((y ∧ x) ∨ (y ∧ x)) = (y ∧ (y ∧ x)) ∨ (y ∧ (y ∧ x))
= ((y ∧ y) ∧ x)) ∨ ((y ∧ y) ∧ x)) = (y ∧ x) ∨ (0 ∧ x)
= (y ∧ x) ∨ 0 = y ∧ x.
Nas igualdades acima, utilizamos comutatividade, distributividade, associativi-
dade, idempoteˆncia, o item 4(a) e a lei de complementaridade de ∨, respectiva-
mente. Conclu´ımos que y∧x = 0, de forma que x∧y = x devido a 4(e). Portanto,
x = x ∧ y = x ∧ ((x ∧ y) ∨ (y ∧ x)) = (x ∧ (x ∧ y)) ∨ (x ∧ (y ∧ x))
= ((x ∧ x) ∧ y) ∨ ((x ∧ x) ∧ y) = (x ∧ y) ∨ 0 = x ∧ y = 0,
como quer´ıamos demonstrar. Aqui, as propriedades utilizadas foram a hipo´tese,
distributividade, associatividade, idempoteˆncia , o item 4(a), a lei de complemen-
taridade de ∨ e a identidade x ∧ y = 0, obtida anteriormente.
5.
∨ 0 1 a b
0 0 1 a b
1 1 1 1 1
a a 1 a 1
b b 1 1 b
∧ 0 1 a b
0 0 0 0 0
1 0 1 a b
a 0 a a 0
b 0 b 0 b
6.
a) 16 func¸o˜es.
b) f1 ∧ f2: f(0, 0) = 1, f(0, 1) = 0, f(1, 0) = 0 e f(1, 1) = 0.
f1 ∨ f2: f(0, 0) = 1, f(0, 1) = 1, f(1, 0) = 1 e f(1, 1) = 0.
(f 1): f(0, 0) = 0, f(0, 1) = 1, f(1, 0) = 0 e f(1, 1) = 1.
c) f = 0: f(0, 0) = 0, f(0, 1) = 0, f(1, 0) = 0 e f(1, 1) = 0.
f = 1: f(0, 0) = 1, f(0, 1) = 1, f(1, 0) = 1 e f(1, 1) = 1.