Example 4.1

The set of real numbers, $\mathbb{R}$, has the operations + and., for example,

$3+5=8???\text{and}???\text{3}\cdot \text{4}=\text{12}$

and we could combine any two numbers in this way and we would always get another real number.

Example 4.2

Consider the set of sets in some universal se ε, for example,

$\begin{array}{l}\mathcal{E}=\left\{\text{a},\text{b},\text{c},\text{d},\text{e}\right\}\\ \text{A}=\left\{\text{a},\text{d}\right\},???\text{B}=\left\{\text{a},\text{b},\text{c}\right\}\end{array}$

then

$\text{A}\cap \text{B}=\left\{\text{a}\right\}??\text{and}??\text{A}\cup \text{B}=\left\{\text{a},\text{b},\text{c},\text{d}\right\}.$

The operations of ∩and ∪ also result in another set contained in $\mathcal{E}$.

In both of these examples, the operations are binary operations because they use two inputs to give one output.

There is another sort of operation which is important, called a unary operation, because it only has one input to give one output. Consider Example 4.2: A′ = {b, c, e} gives the complement of A. This is a unary operation as only one input, A, was needed to define the output A'.

If we can find a rule which is always true for an algebra then that is called a property, (law or axiom) of that algebra. For example, (3 + 5) + 4 = 3 + (5 + 4) is an application of the associative law of addition which can be expressed in general in the following way for the set of real numbers:

$\forall \text{a},\text{b},\text{c}\in ℝ,????\left(a+b\right)+c=a+\left(b+c\right)$

If we can list all the properties of a particular algebra then we can give that algebra a name. For instance, the real numbers with the operations of + and. form a field.

Example 4.3

Show, using Venn diagrams, that, for any 3 sets A, B, C in some universal set $\mathcal{E}$,

$\text{A}\cap \left(\text{B}\cup \text{C}\right)=\left(\text{A}\cap \text{B}\right)\cup \left(\text{A}\cap \text{C}\right).$

Solution This can be shown to be true by drawing a Venn diagram of the left-hand side of the expression and another of the right-hand side of the expression. Operations are performed in the order indicated by the brackets and the result of each operation is given a different shading. This is done in Figure 4.1(a) and (b). The region shaded in Figure 4.1(a) representing A ∩ (B ∪ C) is the same as that representing (A ∩ B) ∪ (A ∩ C) in Figure 4.1(b), hence, showing that A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩C).

In the same way, other properties can be shown to be true. A full list of the properties gives:

For every A, B, C ⊆ $\mathcal{E}$

(B1) A ∪ A = A	A ∩ A = A	Idempotent
(B2) A ∪ (B ∪ C) = (A ∪ B) ∪ C	A ∩ (B ∩ C) = (A ∩ B) ∩ C	Associative
(B3) A ∪ B = B ∪ A	A ∩ B = B ∩ A	Commutative
(B4) A ∪ (A ∩ B) = A	A ∩ (A ∪ B) = A	Absorption
(B5) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)	A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)	Distributive laws
(B6) A ∪ $\mathcal{E}$ = ɛ	A ∩ ∅ = ∅	Bound laws
(B7) A ∪ ∅ = A	A ∩ $\mathcal{E}$ = A	Identity law
(B8) A ∪ A' = ɛ	A ∩ A' = ∅	Complement laws
(B9) ∅' = $\mathcal{E}$	$\mathcal{E}$' = ∅	0 and 1 laws
(B10) (A ∪ B)' = A' ∩ B'	(A ∩ B)' = A' ∪ B'	De Morgan's laws

Notice that all the laws come in pairs (called duals). A dual of a rule is given by replacing ∪ by ∩and ∅ by $\mathcal{E}$ and vice versa.

Example 4.4

Show, using truth tables, that for any propositions p, q, r

$(p\wedge q)\wedge r=p\wedge (q\wedge r)$

Solution The truth tables are given in Table 4.2. Note that there are eight lines in the truth table in order to represent all the possible states (T, F) for the three variables p, q, and r. As each can be either TRUE or FALSE, in total there are 2³ = 8 possibilities. To find (p ∧ q) ∧ r, p ∧ q is performed first and the result of that is ANDed with r. To find p ∧ (q ∧ r) then q ∧ r is performed first and p is ANDed with the result. As the resulting columns are equal we can conclude that

$(p\wedge q)\wedge r\iff p\wedge (q\wedge r)$

Table 4.2

A truth table to show (p q) r ⇔ p (q r). The fifth column gives the truth values of (p q) r and the seventh column gives the truth value of p (q r). As the two columns are the same we can conclude that (p q) r ⇔ p (q r)

p	q	r	p q	(p q) r	q r	p (q r)
T	T	T	T	T	T	T
T	T	F	T	F	F	F
T	F	T	F	F	F	F
T	F	F	F	F	F	F
F	T	T	F	F	T	F
F	T	F	F	F	F	F
F	F	T	F	F	F	F
F	F	F	F	F	F	F

Example 4.5

Show that for any two propositions p, q:

$\neg (p\wedge q)\iff (\neg p)\vee (\neg q)$

Solution The truth table is given in Table 4.3.

Table 4.3

A truth table to show ¬(p q) ⇔ (¬p) ∨ (¬q). The fourth column gives the truth values of ¬(p ∨ q) and the seventh column gives the truth value of (¬p) (¬q). As the two columns are the same we can conclude that ¬(p q) ⇔ (¬p) ∨ (¬q)

p	q	p q	¬(p q)	¬p	¬q	¬p ∨ ¬q
T	T	T	F	F	F	F
T	F	F	T	F	T	T
F	T	F	T	T	F	T
F	F	F	T	T	T	T

It turns out that all the properties we listed for sets are also true for propositions. We list them again, for any three propositions p, q, r

(B1) p ∨ p ⇔ p	p p ⇔ p	Idempotent
(B2) p ∨ (q ∨ r) ⇔ (p ∨ q) ∨ r	p (q ∧ r) ⇔ (p q) r	Associative
(B3) p q ⇔ q ∨ p	p q ⇔ q p	Commutative
(B4) p ∨ (p q) ⇔ p	p (p ∨ q) ⇔ p	Absorption
(B5) p ∨ (q r) ⇔ (p ∨ q) (p ∨ r)	p (q ∨ r) ⇔ (p q) ∨ (p r)	Distributive laws
(B6) p ∨ T ⇔ T	p F ⇔ F	Bound laws
(B7) p ∨ F ⇔ p	p T ⇔ p	Identity laws
(B8) p ∨ ¬p ⇔ T	p ¬p ⇔ F	Complement laws
(B9) ¬F ⇔ T	¬T ⇔ F	0 and 1 laws
(B10) ¬(p ∨ q) ⇔ ¬p ¬q	¬(p q) ⇔ ¬p ∨ ¬q	De Morgan's laws

Notice again that all the laws are duals of each other. A dual of a rule is given by replacing ∨ by ∧ and F by T, and vice versa.

Example 4.6

Evaluate the following where +,., and – are Boolean operators.

(a) $\mathrm{1.1.0}+\overline{0}.1$

(b) $\left(1.\overline{1}\right)+1$

(c) $\left(\overline{1}+1\right).0+\left(1+1\right).0$

Solution

(a) We use the convention that. is performed first:

$\mathrm{1.1.0}+\overline{0}.1=0+1.1=0+1=1$

(b) $\left(1.\overline{1}\right)+1=\left(1.0\right)+1=0+1=1$

(c) $\left(\overline{1}+1\right).0+\left(1+1\right).0=1.0+1.0=0+0=0$

The algebraic laws can be used to simplify a Boolean expression.

Example 4.7

Simplify

$abc+\overline{a}bc+b\overline{c}$

Solution

$\begin{array}{l}abc+\overline{a}b+b\overline{c}\\ =(a+\overline{a})bc+b\overline{c}(\text{using a distribute law})\\ =1.bc+b\overline{c}(\text{using a complement law})\\ =bc+b\overline{c}(\text{using an identify law})\\ =b(c+\overline{c})(\text{by one of the distributive laws})\\ =b(\text{using a complement and identify law})\end{array}$

Although it is possible to simplify in this way, it can be quite difficult to spot the best way to perform the simplification; hence, there are special techniques used in the design of digital circuits which are more efficient.

Example 4.8

Implement $ab\overline{c}+a\overline{b}+a\overline{c}.$

Solution We can use absorption to write this as $a\overline{b}+a\overline{c}$ and this can be implemented as in Figure 4.4 using AND, OR, and NOT gates. Alternatively, we can use the distributive and De Morgan's laws to write the expression as:

$a\overline{b}+a\overline{c}=a\left(\overline{b}+\overline{c}\right)=a\overline{bc}$

which can be implemented using an AND and a NAND gate.

Example 4.9

Minimize the following using a Karnaugh map:

$ab+\overline{a}b?+a\overline{b}$

and draw the implementation of the resulting expression as a logic circuit.

Solution Draw a Karnaugh map as in Figure 4.5(a). If there are two variables in the expression then there are 2² = 4 squares in the Karnaugh map. Figure 4.5(b) shows a Karnaugh map with the squares labelled term by term. Figure 4.5(c) shows that the map is like a Venn diagram of the sets a and b. In Figure 4.5(a) we put a 0 or 1 in the square depending on whether that term is present in our expression. Adjacent 1s indicate that we can simplify the expression. Figure 4.6 indicates how we go about the minimization. We draw a line around any two adjacent 1s and write down the term representing that section of the map. We are able to encircle the second row, representing a, and the second column, representing b. As all the 1s have now been included we know that a + b is a minimization of the expression. Notice that it does not matter if one of the squares with a 1 in it has been included twice but we must not leave any out. The implementation of a + b is drawn in Figure 4.7.

Example 4.10

Minimize $c\left(b+\overline{\left(ab\right)}\right)+\overline{c}ab$ and draw the implementation of the resulting expression as a logic circuit.

Solution First, we need to find the expression as a sum of products. This can be done by finding the truth table and then copying the result into the Karnaugh map. The truth table is found in Table 4.5. Notice that we calculate various parts of the expression and build up to the final expression. With practice, the expression can be calculated directly for instance when a = 0, b = 0, and c = 0 then $c\left(b+\overline{\left(ab\right)}\right)+\overline{c}ab=0\left(0+\overline{\left(0.0\right)}\right)+\overline{0}\mathrm{.0.0}$

$=0\left(0+1\right)+1.0=0.$

Table 4.5

A truth table to find $\text{a}\text{b}+\overline{\text{a}}\text{b}+\text{a}\overline{\text{b}}$

a	b	c	ab	$\overline{c}$	$\overline{\left(ab\right)}$	$\overline{c}ab$	$b+\overline{\left(ab\right)}$	$c\left(b+\overline{\left(ab\right)}\right)$	$c\left(b+\overline{\left(ab\right)}\right)+\overline{c}ab$
0	0	0	0	1	1	0	1	0	0
0	0	1	0	0	1	0	1	1	1
0	1	0	0	1	1	0	1	0	0
0	1	1	0	0	1	0	1	1	1
1	0	0	0	1	1	0	1	0	0
1	0	1	0	0	1	0	1	1	1
1	1	0	1	1	0	1	1	0	1
1	1	1	1	0	0	0	1	1	1

Draw a Karnaugh map as in Figure 4.8(a) and copy in the expression values as found in Table 4.5. There are three variables in the expression, therefore, there are 2³ = 8 squares in the Karnaugh map.

Figure 4.8(b) shows a Karnaugh map with the squares labelled term by term. Figure 4.8(c) shows the Venn diagram equivalence with sets a, b, and c. In Figure 4.8(a) we put a 0 or 1 in the square depending on whether that term is present, as given in the truth table in Table 4.5.

Adjacent l s indicate that we can simplify the expression. Figure 4.9 indicates how we go about the minimization. We draw a line around any four adjacent l s and write down the term representing that section of the map. The second column represents c and has been encircled. Then we look for any two adjacent l s. We are able to encircle the third row, representing ab As all the l s have now been included we know that c + ab is a minimization of the expression. An implementation of c + ab is drawn in Figure 4.10.

Example 4.11

Minimize $ab\overline{c}+\overline{a}bd+abc\overline{d}+a\overline{b}\overline{c}d+abc$ using a Karnaugh map and draw the implementation of the resulting expression as a logic circuit.

Solution Draw a Karnaugh map as in Figure 4.11(a). There are four variables in the expression therefore there are 2⁴ = 16 squares in the Karnaugh map. Figure 4.11 (b) shows a Karnaugh map with the squares labelled term by term. Figure 4.11 (c) shows the Venn diagram equivalence with sets a, b, c, and d. In Figure 4.11(a), we put a 0 or 1 in the square depending on whether that term is present in our expression. However, the term $ab\overline{c}$ involves only three out of the four variables. In this case, it must occupy two squares. As d could be either 0 or 1 for $‘ab\overline{c}’$ to be true, we fill in the squares for $ab\overline{c}d$ and $ab\overline{c}\overline{d}$. The number of squares to be filled with a 1 to represent a certain product is 2^mwhere m is the number of missing variables in the expression. In this case, $ab\overline{c}$ has no d term in it so the number of squares representing it is 2¹.

Adjacent l s indicate that we can simplify the expression. Figure 4.12 indicates how we go about the minimisation. We draw a line around any eight adjacent ln s of which there are none. Next we look for any four adjacent 1 s and write down the term representing that section of the map. The third row represents ab and has been encircled. The middle four squares represent bd and have been encircled. Then we look for any two adjacent l s. The bottom two squares of the second column represent $a\overline{c}d$. As all the l s have now been included we know that $ab+bd+a\overline{c}d$ is a minimization of the expression. This is implemented in Figure 4.13.

Example 4.12

To display the digits 0–9, a seven-segment light emitting diode (LED) display may be used as shown in Figure 4.14. The various states may be represented using a four-variable digital circuit. The logic control signals for the lamp drivers are given by the truth table given in Table 4.6. The X indicates a ‘don't care′ condition in the truth table. The column for the segment labelled p can be copied into a Karnaugh map as given in Figure 4.15. Wherever a 1 appears in the truth table representation for p there is a 1 copied to the Karnaugh map. Similarly, the Os and the ‘don't care′ crosses are copied. Minimize the Boolean expression for p using the Karnaugh map.

Solution The minimization is represented in Figure 4.15(b). We first look for any eight adjacent squares with a 1 or a X in them. The bottom two rows are encircled giving the term a. Now we look for groups of four. The central four squares represent bd and the third column represents cd. Finally, we can count the four corner squares as adjacent. This is because two squares may be considered as adjacent if they are located symmetrically with respect to any of the lines which divide the Karnaugh map into equal halves, quarters, or eighths. This means that squares that could be curled round to meet each other, as if the Karnaugh map where drawn on a cylinder, are considered adjacent and also the four corner squares. Here, the four corner squares represent the term $\overline{b}??\overline{d}$. Hence, the minimization for p gives

$p=a+cd+bd+\overline{b}\overline{d}.$