Question

7. Prove the following properties by using whole
numbers and check if they are correct


(a) x+y =y+y

(b) x-y=y-x

(c) x-y+y=y-x+x

(d) x×(y+z) = (y+z) × x

(e) (x-y) -z=x-(y-z)​

Answer 1

Answer:

x.1 using (b)

=x Identity laws

x.(x+y) = x.x+x.y Distributivity laws

=x+x.y by (a)

=x Just shown above.

Q.E.D.

Definition: An element y in B is called a complement of an element x in B if x+y=1 and xy=0

Theorem 2: For every element x in B, the complement of x exists and is unique.

Proof:

 Existence. Let x be in B. x’ exists because ‘ is a unary operation. X’ is a complement of x

because it satisfies the definition of a complement (x+x’=1 and xx’=0).

 Uniqueness. Let y be a complement of x. We will show that y=x’. Since y is a complement of x,

we have x+y=1 and xy=yx=0.

y=y.1=y.(x+x’)=yx+yx’=0+yx’=xx’+yx’=(x+y)x’=1.x’=x’ => y=x’. QED

Corollary 1: (x’)’=x.

Proof, since x’+x=1 and x’x=0, it follows that x is a complement of x’. Since the complement of x’ is

unique, it follows then that (x’)’ , which is a complement of x’, and x, which is also a complement of x’,

must be equal. Thus, (x’)’=x. QED

Theorem 3 (De Morgan’s Laws):

a) (x+y)’=x’y’

b) (xy)’=x’+y’

Proof:

a) Show that x’y’+(x+y)=1 and (x’y’)(x+y)=0.

x’y’+(x+y)=(x’y’+x)+y=(x’+x)(y’+x)+y=1.(y’+x)+y=(y’+x)+y=(x+y’)+y=x+(y’+y)=x+1=1

(x’y’)(x+y)=(x’y’)x+(x’y’)y=(y’x’)x+x’(y’y)=y’(x’x)+x’0=y’0+0=0+0=0

b) The proof is similar and left as an exercise.

QED.

Definition: Let (B,+, . , ‘, 0,1) be a Boolean Algebra. Define the following ≤ relation in B:

x ≤ y if xy=x

Theorem 4: The relation ≤ is a partial order relation.

Proof: We need to prove that ≤ is reflexive, antisymmetric and transitive

 Reflexivity: since xx=x (by Theorem 1-a), it follows that x ≤ x

 Antisymmetry: need to show that x≤y and y≤x => x=y. x≤y and y≤x => xy=x and yx=y