De Morgan

DE MORGAN’S LAW AND DUALITY SHYAMA A BSTRACT. A briefing on de Morgan’s laws, duality and it’s applications. Set theory, boolean and lattice algebra have varied applications, starting from digital systems design, to logical reasoning to real analysis.

Sets are the most basic building blocks in mathematics, and it is in fact not easy to give a precise definition of the mathematical object set. Once sets are introduced, however, one can compare them, define operations similar to addition and multiplication on them, and use them to define new objects such as various kinds of number systems. In fact, most of the topics in modern analysis are ultimately based on sets. Therefore, it is good to have a basic understanding of sets, and we will review a few elementary facts in this section. Most, if not all, of this section should be familiar and its main purpose is to define the basic notation so that there will be no confusion in the remainder of this text. 1. S ET & OPERATIONS ON SET Definition 1.1. Sets and Operations on Sets A set is a collection of objects chosen from some universe. The universe is usually understood from the context. Sets are denoted by capital, bold letters or curly brackets. • A ⊂ B: A is a subset of B means that every element in A is also contained in B. • A ∪ B: A union B is the set of all elements that are either in A or in B or in both. • A ∩ B: A intersection B is the set of all elements that are in both sets A and B. • A \ B: A minus B are all elements from A that are not in B. • comp(A): The complement of A consists of all elements that are not in A. • Two sets are disjoint if A ∩ B = 0 (the empty set). • Two sets A and B are equal if A ⊂ B and B ⊂ A. The most commonly used sets are the sets of natural numbers, integers, rational and real numbers, and the empty set. They are usually denoted by these symbols: • N = {1, 2, 3, 4, . . .} = natural numbers (sometimes 0 is considered part of the natural numbers as well). • Z = {. . . − 3, −2, −1, 0, 1, 2, 3, . . .} = integers. Date: 30-Aug-2006. 1991 Mathematics Subject Classification. Set theory, lattice and boolean algebra. Key words and phrases. Set, De Morgan’s law, Complement, intersection, union, dual. 1

2

SHYAMA

• Q = {p/q : p, q ∈ Z} (read as ”all number p / q, such that p and q are elements of Z”) = rational numbers. • R = real numbers. • φ = empty set (the set that contains no elements). All of the number systems (except the natural numbers) will be defined in a mathematically precise way in later sections. First, some examples: Example 1.2. • Define the following sets: E = {x : x = 2n, f orn ∈ N}, O = {x : x = 2n − 1, f orn ∈ N}, A = {x ∈ R : −4 < x < 3}, B = {x ∈ R : −1 < x < 7}, and I = {x ∈ R : x2 = −2}. Then: (1) What, in words, are the sets E, O, and I? (2) Find A ∪ B, A ∩ B, A \ B, comp(A). (3) Find φ ∪ E, φ ∩ I, comp(I). Sets can be combined using the above operations much like adding and multiplying numbers. Familiar laws such as associative, commutative, and distributive laws will be true for sets as well. As an example, the next result will illustrate the distributive law; other laws are left as exercises. 2. D ISTRIBUTION , AND DE M ORGAN L AWS Proposition 2.1. Distributive Law for Sets (1) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (2) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) Many results in set theory can be illustrated using Venn diagram, as in the above proof. However, such diagrams do not represent mathematically rigorous proofs. Nonetheless, before an actual proof is developed, it is first necessary to form a mental picture of the assumptions, conclusions, and implications of a theorem. For this process a Venn diagram can be very helpful. You can practice Venn diagrams by using them for some of the true/false statements in the exercises. There are many other theorems dealing with operation on sets. One that is particularly interesting is the theorem about de Morgan’s Laws, because it deals with any number of sets (even infinitely many). Drawing a Venn diagram in such a situation would be impossible, but a mathematical proof can easily deal with this situation: Theorem 2.2. de Morgan’s Laws T S (1) comp( j Aj ) = j comp(Aj ) S T (2) comp( j Aj ) = j comp(Aj ) In words of proposition logic - For every proposition involving logical addition and multiplication (”or” and ”and”), there is a corresponding proposition in which the words ”addition” and ”multiplication” are interchanged. Theorem 2.3. Duality A metatheorem stating that every theorem on partially ordered sets remains true

DE MORGAN’S LAW AND DUALITY

3

if all inequalities are reversed. In this operation, supremum must be replaced by infimum, maximum with minimum, and conversely. In a lattice, this means that meet and join must be interchanged, and in a Boolean algebra, 1 and 0 must be switched. Each of de Morgan’s two laws can be derived from the other by duality. R EFERENCES

I NDEX Boolean algebra, 3 complement, 1 de Morgan’s Laws, 2 disjoint, 1 distributive law, 2 Duality, 2 empty set, 1, 2 equal, 1 infimum, 3 integers, 1 intersection, 1 join, 3 lattice, 3 logical addition, 2 maximum, 3 meet, 3 minimum, 3 minus, 1 multiplication, 2 natural numbers, 1 proposition, 2 proposition logic, 2 rational, 1, 2 real numbers, 1, 2 subset, 1 supremum, 3 union, 1 Venn diagram, 2

4

DE MORGAN’S LAW AND DUALITY

5/A, C HATTERJEE L ANE , S ERAMPORE , H OOGHLY , WB, 712201, I NDIA E-mail address: [email protected]

5