We are searching data for your request:
Upon completion, a link will appear to access the found materials.
Mathematical statistics sometimes requires the use of set theory. De Morgan's laws are two statements that describe the interactions between various set theory operations. The laws are that for any two sets A and B:
- (A ∩ B)C = AC U BC.
- (A U B)C = AC ∩ BC.
After explaining what each of these statements means, we will look at an example of each of these being used.
Set Theory Operations
To understand what De Morgan's Laws say, we must recall some definitions of set theory operations. Specifically, we must know about the union and intersection of two sets and the complement of a set.
De Morgan's Laws relate to the interaction of the union, intersection, and complement. Recall that:
- The intersection of the sets A and B consists of all elements that are common to both A and B. The intersection is denoted by A ∩ B.
- The union of the sets A and B consists of all elements that in either A or B, including the elements in both sets. The intersection is denoted by A U B.
- The complement of the set A consists of all elements that are not elements of A. This complement is denoted by AC.
Now that we have recalled these elementary operations, we will see the statement of De Morgan's Laws. For every pair of sets A and B we have:
- (A ∩ B)C = AC U BC
- (A U B)C = AC ∩ BC
These two statements can be illustrated by the use of Venn diagrams. As seen below, we can demonstrate by using an example. In order to demonstrate that these statements are true, we must prove them by using definitions of set theory operations.
Example of De Morgan's Laws
For example, consider the set of real numbers from 0 to 5. We write this in interval notation 0, 5. Within this set we have A = 1, 3 and B = 2, 4. Furthermore, after applying our elementary operations we have:
- The complement AC = 0, 1) U (3, 5
- The complement BC = 0, 2) U (4, 5
- The union A U B = 1, 4
- The intersection A ∩ B = 2, 3
We begin by calculating the union AC U BC. We see that the union of 0, 1) U (3, 5 with 0, 2) U (4, 5 is 0, 2) U (3, 5. The intersection A ∩ B is 2, 3. We see that the complement of this set 2, 3 is also 0, 2) U (3, 5. In this way we have demonstrated that AC U BC = (A ∩ B)C.
Now we see the intersection of 0, 1) U (3, 5 with 0, 2) U (4, 5 is 0, 1) U (4, 5. We also see that the complement of 1, 4 is also 0, 1) U (4, 5. In this way we have demonstrated that AC ∩ BC = (A U B)C.
Naming of De Morgan's Laws
Throughout the history of logic, people such as Aristotle and William of Ockham have made statements equivalent to De Morgan's Laws.
De Morgan's laws are named after Augustus De Morgan, who lived from 1806-1871. Although he did not discover these laws, he was the first to introduce these statements formally using a mathematical formulation in propositional logic.