how to proof de morgan's law step wise

De-Morgan’s laws are:

  • 24

Let x be an element of (A U B)'.

Then x is not an element of A U B.

Suppose x is an element of A.
Then x is an element of A U B.
But this is a contradiction, so x is not an element of A.
I.e. x is an element of A'.

Similarly, if x is an element of B, then we reach a contradiction, so x is an element of B'.

x is an element of A' and x is an element of B', so x is an element of A' n B'.

Therefore (A U B)' is a subset of A' n B'.

-------

Now assume that x is an element of A' n B'.

Then x is an element of A' and x is an element of B'.

I.e. x is not an element of A and x is not an element of B.

Now assume that x is an element of A U B, so either x is an element of A or x is an element of B. Both of these are contradictions, though, so x must not be an element of A U B.

Therefore x is an element of (A U B)'.

This shows that A' n B' is a subset of (A U B)'.

=====

Since both sides are subsets of one another, they must be equal as sets. Is it OK?

  • -1

Let x be an element of (A U B)'.

Then x is not an element of A U B.

Suppose x is an element of A.
Then x is an element of A U B.
But this is a contradiction, so x is not an element of A.
I.e. x is an element of A'.

Similarly, if x is an element of B, then we reach a contradiction, so x is an element of B'.

x is an element of A' and x is an element of B', so x is an element of A' n B'.

Therefore (A U B)' is a subset of A' n B'.

-------

Now assume that x is an element of A' n B'.

Then x is an element of A' and x is an element of B'.

I.e. x is not an element of A and x is not an element of B.

Now assume that x is an element of A U B, so either x is an element of A or x is an element of B. Both of these are contradictions, though, so x must not be an element of A U B.

Therefore x is an element of (A U B)'.

This shows that A' n B' is a subset of (A U B)'.

=====

Since both sides are subsets of one another, they must be equal as sets.

  • 1
What are you looking for?