Discrete Mathematical Structures by Pearson

Boolean Algebra 9-11

Example 4 Let [B, +, ., ′] be a Boolean algebra, then show that

(1) x + (x + y) = x + y (2) x

.

(x

.

y) = x

.

y

(3) x′ + x.y = x′ + y (4) x′ + xy = x′ + y

(5) x + x′y = x + y

Solution:

(1) x + (x + y) = (x + x) + y = x + y (By Associative law)

(2) x

.

(x

.

y) = (x

.

x)

.

y = x

.

y (By Associative and idempotent law)

(3) x′ + x

.

y = (x′ + x)

.

(x′ + y) (By Distributive law)

 = 1

.

(x′ + y) = x′ + y

(4) x′ + xy = (x′ + x)

.

(x′ + y) (By Distributive law)

 = 1

.

(x′ + y) = x′ + y

(5) x + x′y = (x + x′)

.

(x + y) (By Distributive law)

 = 1

.

(x + y) = x + y

Example 5 In a Boolean algebra [B, +, ., ′] prove that (x′.y)′ + (x.y′)′ = 1

Solution: By De Morgan’s law, left-hand side is

x + y′ + x′ + y = (x + x′) + (y + y′)

 = 1+1

 = 1 Proved

Example 6 Let {B, ...