L10D131

Prévia do material em texto

MAT 01375 – Matema´tica Discreta B 2013/1
Lista de Exerc´ıcios 10
1. Seja (B = {0, 1},∨,∧,−, 0, 1) a´lgebra de Boole associada a` lo´gica bina´ria.
Usando as portas lo´gicas, AND, NOT, NAND, OR, XOR e NOR,
diagrame um circuito equivalente a cada expressa˜o booleana dada:
a) x ∨ (x ∧ y).
b) (x ∨ y).
c) x ∨ ((x ∧ y) ∨ (x ∧ y)).
d) (x ∧ y) ∨ (y ∧ x).
2. Considere o circuito diagramado abaixo chamado ENOR e use a a´lgebra
de Boole (B = {0, 1},∨,∧,−, 0, 1) para simplifica´-lo e diagrame o circuito
resultante. Sugesta˜o: Denote a porta XOR como x⊕ y ⇔ (x ∨ y) ∧ (x ∧ y).
3. Prove as propriedades a seguir para A´lgebras de Boole. Justifique cada passo.
(a) x ∧ (y ∨ (x ∧ z)) = (x ∧ y) ∨ (x ∧ z)
(b) x ∨ (y ∧ (x ∨ z)) = (x ∨ y) ∧ (x ∨ z)
(c) x ∨ y = x ∨ ((x ∧ y) ∨ (x ∧ y))
(d) (x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z) = x ∨ y
(e) (x ∧ (z ∨ y)) ∨ (x ∨ y) = x
4. Utilizando a definic¸a˜o de uma A´lgebra de Boole B e o fato de que as suas
operac¸o˜es bina´rias ∨ e ∧ sa˜o idempotentes (isto e´, x∨x = x e x∧x = x para
todo x ∈ B), demonstre os fatos a seguir. Justifique cada passo.
(a) x ∧ 0 = 0
(b) x ∨ 1 = 1
(c) x ∧ (x ∨ y) = x
(d) x ∨ y = 0 implica x = 0 e y = 0
(e) x ∧ y = 0 implica x ∧ y = x
(f) (x ∧ y) ∨ (y ∧ x) = y implica x = 0
(g) x ∨ y = y se, e somente se, x ∧ y = x
5. Seja S = {0, 1, a, b} e sejam ∨ e ∧ operac¸o˜es bina´rias e − operac¸a˜o una´ria.
Sabendo que [S,∨,∧,−, 0, 1] forma uma A´lgebra Booleana, complete as tabelas
abaixo que definem as operac¸o˜es bina´rias ∨ e ∧, usando a primeira tabela
que define a operac¸a˜o una´ria −.
−
0 1
1 0
a b
b a
∨ 0 1 a b
0
1
a
b
∧ 0 1 a b
0
1
a
b
6. Seja A o conjunto {0, 1}. Enta˜o A2 e´ o conjunto de todos os pares ordenados
formados com 0 e 1. Considere o conjunto B de todas as func¸o˜es de A2 em A.
Por exemplo, uma dessas func¸o˜es f(x, y) e´ dada por f(0, 0) = 0, f(0, 1) = 1,
f(1, 0) = 1 e f(1, 1) = 1.
(a) Quantos elementos tem B?
(b) Se f1 e f2 sa˜o elementos de B e se (x, y) ∈ A
2, defina
(f1 ∨ f2)(x, y) = max{f1(x, y), f2(x, y)},
(f1 ∧ f2)(x, y) = min{f1(x, y), f2(x, y)},
(f1)(x, y) =
{
1, se f1(x, y) = 0,
0, se f1(x, y) = 1.
Suponha que f1 e f2 sejam dadas por f1(0, 0) = 1, f1(0, 1) = 0, f1(1, 0) =
1, f1(1, 1) = 0 e f2(0, 0) = 1, f2(0, 1) = 1, f2(1, 0) = 0 e f2(1, 1) = 0.
Quais sa˜o as func¸o˜es f1 ∧ f2, f1 ∨ f2 e (f1).
(c) Determine quais devem ser as func¸o˜es 0 e 1 para que [B,∨,∧,−, 0, 1] seja
uma A´lgebra Booleana. Justifique que temos uma A´lgebra Booleana.