Use the Venn diagram to prove DeMorgans theorem, as given in expression 15b in Section 2.5. Section

Question:

Use the Venn diagram to prove DeMorgan’s theorem, as given in expression 15b in Section 2.5.

Section 2.5

In 1849 George Boole published a scheme for the algebraic description of processes involved in logical thought and reasoning [1]. Subsequently, this scheme and its further refinements became known as Boolean algebra. It was almost 100 years later that this algebra found application in the engineering sense. In the late 1930s Claude Shannon showed that Boolean algebra provides an effective means of describing circuits built with switches [2]. The algebra can, therefore, be used to describe logic circuits. We will show that this algebra is a powerful tool that can be used for designing and analyzing logic circuits. The reader will come to appreciate that it provides the foundation for much of our modern digital technology.

Axioms of Boolean Algebra
Like any algebra, Boolean algebra is based on a set of rules that are derived from a small number of basic assumptions. These assumptions are called axioms. Let us assume that Boolean algebra involves elements that take on one of two values, 0 and 1. Assume that the following axioms are true:
1a. 0· 0 = 0
1b. 1+ 1 = 1
2a. 1· 1 = 1

2b. 0+ 0 = 0
3a. 0· 1 = 1 · 0 = 0
3b. 1+ 0 = 0 + 1 = 1
4a. Ifx = 0, then x = 1
4b. Ifx = 1, then x = 0

Single-Variable Theorems
From the axioms we can define some rules for dealing with single variables. These rules are often called theorems. If x is a Boolean variable, then the following theorems hold:
5a. x · 0 = 0
5b. x + 1 = 1
6a. x · 1 = x
6b. x + 0 = x
7a. x · x = x
7b. x + x = x
8a. x · x = 0
8b. x + x = 1
9. x = x
It is easy to prove the validity of these theorems by perfect induction, that is, by substituting the values x = 0 and x = 1 into the expressions and using the axioms given above. For
example, in theorem 5a, if x = 0, then the theorem states that 0 · 0 = 0, which is true according to axiom 1a. Similarly, if x = 1, then theorem 5a states that 1 · 0 = 0, which
is also true according to axiom 3a. The reader should verify that theorems 5a to 9 can be proven in this way.

Duality
Notice that we have listed the axioms and the single-variable theorems in pairs. This is done to reflect the important principle of duality. Given a logic expression, its dual is obtained by replacing all + operators with · operators, and vice versa, and by replacing all 0s with 1s, and vice versa. The dual of any true statement (axiom or theorem) in Boolean algebra is also a true statement. At this point in the discussion, the reader might not appreciate why duality is a useful concept. However, this concept will become clear later in the chapter, when we will show that duality implies that at least two different ways exist to express every logic function with Boolean algebra. Often, one expression leads to a simpler physical implementation than the other and is thus preferable.

Two- and Three-Variable Properties
To enable us to deal with a number of variables, it is useful to define some two- and three-variable algebraic identities. For each identity, its dual version is also given. These identities are often referred to as properties. They are known by the names indicated below. If x, y, and z are Boolean variables, then the following properties hold:

Again, we can prove the validity of these properties either by perfect induction or by performing algebraic manipulation. Figure 2.13 illustrates how perfect induction can be used to prove DeMorgan’s theorem, using the format of a truth table. The evaluation of left-hand and right-hand sides of the identity in 15a gives the same result.
We have listed a number of axioms, theorems, and properties. Not all of these are necessary to define Boolean algebra. For example, assuming that the + and · operations are defined, it is sufficient to include theorems 5 and 8 and properties 10 and 12. These are sometimes referred to as Huntington’s basic postulates [3]. The other identities can be derived from these postulates. The preceding axioms, theorems, and properties provide the information necessary for performing algebraic manipulation of more complex expressions.