Tabla de Contenidos
Logic is a branch of mathematics, and part of it is set theory. De Morgan’s laws are two postulates about the interaction between sets. These laws record antecedents in Aristotle and William of Ockham. Augustus De Morgan lived between 1806 and 1871 and was the first to include the laws that he postulated in the formal structure of mathematical logic.
Operators in set theory
Before moving on to De Morgan’s postulates, let’s look at some definitions of set theory.
If there are any two sets of elements, which we will call A and B, the intersection of these two sets is the set of elements common to both sets. The intersection of two sets is denoted by the symbol ∩, and is another set that we can call C; C = A∩B, and C is the set of elements that appear in both group A and group B. Similarly, the union of two sets A and B is a new set containing all elements of A and B, and it is noted with the symbol U. The set C, union of A and B, C = AUB, is a set that is integrated with all the elements of A and B. The third definition that we must remember is the complement of a set: if we have a certain universe of elements and a set A of this universe, the complement of A is the set of elements of that universe that do not belong to the set A. The complement set of A is denoted as A C .
These three operators between sets can be generalized to the operation between several sets, that is, to the intersection, union and complement of several sets. Let’s look at a simple example. The following figure shows the Venn diagram of three sets: the birds, represented by the parrot, the ostrich, the duck and the penguin; the living beings that fly, represented by the parrot, the duck, the butterfly and the flying fish, and the living beings that swim, represented by the duck, the penguin, the flying fish and the whale. The duck is the intersection set of the three sets: the union set of birds and living beings that fly is made up of the ostrich, the parrot, the butterfly, the duck, the penguin, and the flying fish. And the complement of the living beings that fly and those that swim is the set that contains the ostrich.
De Morgan’s Laws
Now we can see the postulates of De Morgan’s laws. The first postulate says that the complement of the set intersection of two sets A and B is equal to the set union of the complement of A and the complement of B. Using the operators defined in the previous paragraph, De Morgan’s first law can be written as Following way:
(A∩B) C = A C UB C
De Morgan’s second law postulates that the complement of the union set of A and B is equal to the intersection of the complement set of A with the complement set of B, and it is noted as follows:
(AUB) C = A C ∩ B C
Let’s see an example. Consider the set of integers from 0 to 5. This is denoted as [0,1,2,3,4,5]. In this universe we define two sets A and B. A is the set of numbers 1, 2 and 3; A = [1,2,3]. YB is the set of numbers 2, 3 and 4; B = [2,3,4]. De Morgan’s first law would apply as follows.
A = [1,2,3]; B = [2,3,4]
De Morgan’s first law: (A∩B) C = A C UB C
(A∩B) C
A∩B = [1,2,3]∩[2,3,4] = [2,3]
(A∩B) C = [2,3] C = [0,1,4,5]
A C UB C
A C = [1,2,3] C = [0,4,5]
B C = [2,3,4] C = [0,1,5]
A C UB C = [0,4,5]U[0,1,5] = [0,1,4,5]
The result of the application of the operators on both sides of the equality shows that De Morgan’s first law is verified. Let us see the application of the example to the second postulate.
De Morgan’s second law: (AUB) C = A C ∩ B C
(AUB) C
AUB = [1,2,3]U[2,3,4] = [1,2,3,4]
(AUB) C = [1,2,3,4] C = [0,5]
A C ∩ B C
A C = [1,2,3] C = [0,4,5]
B C = [2,3,4] C = [0,1,5]
A C ∩ B C = [0,4,5]∩[0,1,5] = [0,5]
As with the first postulate, in the given example De Morgan’s second law also applies.
Sources
AG Hamilton. Logic for Mathematicians. Editorial Paraninfo, Madrid, 1981.
Carlos Ivorra Castillo. Logic and set theory . Accessed November 2021
