Problem 7 Let A and B be subsets of the finite universal set

Problem 7 Let A and B be subsets of the finite universal set U. Show that:

|OverBar A OverBarB| = |U| - |A| - |B| + |A B|

Solution

To prove |OverBar A OverBarB| = |U| - |A| - |B| + |A B|

we have to prove

|OverBar A OverBarB| |U| - |A| - |B| + |A B|

|U| - |A| - |B| + |A B| |OverBar A OverBarB|

lets take x |OverBar A OverBarB| ==> x overbar|A U B| (BY demorgans law) so x |A U B|

x A and x B. => |U| - |A| - |B| + |A B|

Therefore |OverBar A OverBarB| = |U| - |A| - |B| + |A B|