UNIT 3

Boolean Algebra: Introduction , Axioms and Theorems of Boolean algebra,Boolean Functions. Simplification of Boolean Functions, Karnaugh maps, Logic gates, Digital circuits and Boolean algebra.

Boolean Algebra

INTRODUCTION

Both sets and propositions satisfy similar laws. These laws are used to define an abstract mathematical structure called a Boolean algebra, which is named after the mathematician George Boole (1815–1864).

AXIOMS OF BOOLEAN ALGEBRA

Let B be a nonempty set with two binary operations + and ∗, a unary operation , and two distinct elements 0 and 1. Then B is called a Boolean algebra if the following axioms hold where a, b, c are any elements in B:

[B1] Commutative laws:
(1a) a + b = b + a   (1b) a ∗ b = b ∗ a

[B2] Distributive laws:
(2a) a + (b ∗ c) = (a + b) ∗ (a + c)   (2b) a ∗ (b + c) = (a ∗ b) + (a ∗ c)

[B3] Identity laws:
(3a) a + 0 = a   (3b) a ∗ 1 = a

[B4] Complement laws:
(4a) a + a'=1   (4b) a ∗ a'= 0

We will sometimes designate a Boolean algebra by (B,+, ∗,', 0, 1) when we want to emphasize its six parts.
We say 0 is the zero element, l, is the unit element, and a' is the complement of a.We will usually drop the symbol ∗ . Then (2b) is written a(b + c) = ab + ac which is the familiar algebraic identity of rings and fields. However, (2a) becomes a + bc = (a + b)(a + c), which is certainly not a usual identity in algebra.
The operations +, ∗, and ' are called sum, product, and complement, respectively. We adopt the usual convention that, unless we are guided by parentheses, ' has precedence over ∗, and ∗ has precedence over +.
For example,
a + b ∗ c means a + (b ∗ c) and not (a + b) ∗ c;     a ∗ b' means a ∗ (b') and not (a ∗ b)'
Of course when a + b ∗ c is written a + bc then the meaning is clear.

EXAMPLE

(a) Let B = {0, 1}, the set of bits (binary digits), with the binary operations of + and ∗ and the unary operation ' defined by Fig. Then B is a Boolean algebra. (Note ' simply changes the bit, i.e., 1'= 0 and 0'= 1.)


(b) Let Bn = B × B×· · ·×B (n factors) where the operations of +, ∗, and 'are defined componentwise using Fig. For notational convenience, we write the elements of Bn as n-bit sequences without commas, e.g.,
x = 110011 and y = 111000 belong to Bn. Hence
x + y = 111011, x∗ y = 110000, x' = 001100
Then Bn is a Boolean algebra. Here 0 = 000 · · · 0 is the zero element, and 1 = 111 · · · 1 is the unit element.
We note that Bn has 2n elements.

(c) Let D70 = {1, 2, 5, 7, 10, 14, 35, 70}, the divisors of 70. Define +, ∗, and 'on D70 by
a + b = lcm(a, b),      a ∗ b = gcd(a, b), a'= 70/a
Then D70 is a Boolean algebra with 1 the zero element and 70 the unit element.

(d) Let C be a collection of sets closed under the set operations of union, intersection, and complement. Then C is a Boolean algebra with the empty set as the zero element and the universal set U as the unit element.

THEOREMS OF BOOLEAN ALGEBRA

Using the axioms [B1] through [B4], we prove the following theorem.

Theorem :

Let a, b, c be any elements in a Boolean algebra B.

(i) Idempotent laws:   (5a) a + a =a   (5b) a ∗ a = a

(ii) Boundedness laws:   (6a) a + 1 = 1   (6b) a ∗ 0 = 0

(iii) Absorption laws:   (7a) a + (a ∗ b) =a   (7b) a ∗ (a + b) = a

(iv) Associative laws:   (8a) (a + b) + c = a + (b + c)   (8b) (a ∗ b) ∗ c = a ∗ (b ∗ c)

Theorem :

Let a be any element of a Boolean algebra B.

(i) (Uniqueness of Complement) If a + x = 1 and a ∗ x = 0, then x = a'

(ii) (Involution law) (a')'= a

(iii) (9a) 0' = 1.   (9b) 1' = 0.

Theorem (DeMorgan’s laws):

(10a) (a + b)'= a' ∗ b'   (10b) (a ∗ b)' = a' + b'

SIMPLIFICATION OF BOOLEAN FUNCTION

SUM-OF-PRODUCTS FORM FOR SETS

This section motivates the concept of the sum-of-products form in Boolean algebra by an example of set theory. Consider the Venn diagram in Fig.of three sets A, B, and C.
Observe that these sets partition the rectangle (universal set) into eight numbered sets which can be represented as follows:

(1)   A∩ B ∩C        (3)   A∩ Bc ∩C      (5)   A∩ Bc ∩ Cc      (7)   Ac ∩ Bc ∩ C
(2)   A∩ B ∩ Cc     (4)   Ac ∩ B ∩C     (6)   Ac ∩ B ∩ Cc     (8)   Ac ∩ Bc ∩ Cc

Each of these eight sets is of the form A∗ ∩ B∗ ∩ C∗ where:

A = A or Ac    , B = B or Bc    , C = C or Cc    

Consider any non empty set expression E involving the sets A, B, and C, say,
E = [(A ∩ Bc)c ∪ (Ac ∩ Cc)] ∩ [(Bc ∪ C)c ∩ (A ∪ Cc)]
Then E will represent some area in Fig. and hence will uniquely equal the union of one or more of the eight sets.

Suppose we now interpret a union as a sum and an intersection as a product. Then the above eight sets are products, and the unique representation of E will be a sum (union) of products. This unique representation of E is the same as the complete sum-of-products expansion in Boolean algebras which we discuss below.

SUM-OF-PRODUCTS FORM FOR BOOLEAN ALGEBRAS

Consider a set of variables (or letters or symbols), say x1, x2, . . . , xn. A Boolean expression E in these variables, sometimes written E(x1, . . . , xn), is any variable or any expression built up from the variables using the Boolean operations +, ∗, and '. (Naturally, the expression E must be well-formed, that is, where + and ∗ are used as binary operations, and ' is used as a unary operation.) For example,

E1 = (x + y'z)'+ (xyz'+ x'y)'     and     E2 = ((xy'z'+ y)' + x'z)'
are Boolean expressions in x, y, and z.

A literal is a variable or complemented variable, such as x, x', y, y', and so on. A fundamental product is a literal or a product of two or more literals in which no two literals involve the same variable. Thus
              xz', xy'z, x, y', x'yz
are fundamental products, but xyx'z and xyzy are not. Note that any product of literals can be reduced to either 0 or a fundamental product, e.g., xyx'z = 0 since xx'= 0 (complement law), and xyzy = xyz since yy = y (idempotent law).

A fundamental product P1 is said to be contained in (or included in) another fundamental product P2 if the literals of P1 are also literals of P2. For example, x'z is contained in x'yz, but x'z is not contained in xy'z since x' is not a literal of xy'z. Observe that if P1 is contained in P2, say P2 = P1 ∗ Q, then, by the absorption law,
P1 + P2 = P1 + P1 ∗ Q = P1

Thus, for instance, x'z + x'yz = x'z.

Definition: A Boolean expression E is called a sum-of-products expression if E is a fundamental product or the sum of two or more fundamental products none of which is contained in another.

Definition: Let E be any Boolean expression. A sum-of-products form of E is an equivalent Boolean sum-of-products expression.

EXAMPLE

Consider the expressions

E1 = xz'+ y'z + xyz'     and     E2 = xz'+ x'yz' + xy'z

Although the first expression E1 is a sum of products, it is not a sum-of-products expression. Specifically, the product xz' is contained in the product xyz' .However, by the absorption law, E1 can be expressed as

E1 = xz'+ y'z + xyz' = xz' + xyz' + y'z = xz' + y'z

This yields a sum-of-products form for E1. The second expression E2 is already a sum-of-products expression.

Algorithm for Finding Sum-of-Products Forms

Figure gives a four-step algorithm which uses the Boolean algebra laws to transform any Boolean expression into an equivalent sum-of-products expression.

EXAMPLE

Suppose Algorithm is applied to the following Boolean expression:

E = ((xy)'z)'((x'+ z)(y' + z'))'

Step 1. Using DeMorgan’s laws and involution, we obtain
E = (xy''+ z')((x'+ z)' + (y' + z')') = (xy + z')(xz' + yz)
E now consists only of sums and products of literals.

Step 2. Using the distributive laws, we obtain
E = xyxz'+ xyyz + xz'z'+ yzz'
E now is a sum of products.

Step 3. Using the commutative, idempotent, and complement laws, we obtain
E = xyz'+ xyz + xz'+ 0
Each term in E is a fundamental product or 0.

Step 4. The product xz' is contained in xyz' ; hence, by the absorption law,
xz' + (xz'y) = xz'
Thus we may delete xyz' from the sum. Also, by the identity law for 0, we may delete 0 from the sum.
Accordingly,
E = xyz + xz'
E is now represented by a sum-of-products expression.

LOGIC GATES AND CIRCUITS

Logic circuits (also called logic networks) are structures which are built up from certain elementary circuits called logic gates. Each logic circuit may be viewed as a machine L which contains one or more input devices and exactly one output device. Each input device in L sends a signal, specifically, a bit (binary digit),
              0 or 1
to the circuit L, and L processes the set of bits to yield an output bit. Accordingly, an n-bit sequence may be assigned to each input device, and L processes the input sequences one bit at a time to produce an n-bit output sequence. First we define the logic gates, and then we investigate the logic circuits.

LOGIC GATES

There are three basic logic gates which are described below.We adopt the convention that the lines entering the gate symbol from the left are input lines and the single line on the right is the output line.

(a) OR Gate: Figure (a) shows an OR gate with inputs A and B and output Y = A + B where “addition” is defined by the “truth table” in Fig.(b). Thus the output Y = 0 only when inputs A = 0 and B = 0. Such an OR gate may, have more than two inputs. Figure(c) shows an OR gate with four inputs, A, B, C, D, and output Y = A + B + C + D. The output Y = 0 if and only if all the inputs are 0.

Suppose, for instance, the input data for the OR gate in Fig.(c) are the following 8-bit sequences:
              A = 10000101,     B= 10100001,     C= 00100100,     10010101
The OR gate only yields 0 when all input bits are 0. This occurs only in the 2nd, 5th, and 7th positions (reading from left to right). Thus the output is the sequence Y = 10110101.

(b) AND Gate: Figure (a) shows an AND gate with inputs A and B and output Y = A · B (or simply Y = AB) where “multiplication” is defined by the “truth table” in Fig.(b). Thus the output Y = 1 when inputs A = 1 and B = 1; otherwise Y = 0. Such anANDgate may have more than two inputs. Figure (c) shows an AND gate with four inputs, A, B, C, D, and output Y = A · B · C · D. The output Y = 1 if and only if all the inputs are 1.

Suppose, for instance, the input data for theAND gate in Fig. are the following 8-bit sequences: A = 11100111, B= 01111011, C= 01110011, D= 11101110
The AND gate only yields 1 when all input bits are 1. This occurs only in the 2nd, 3rd, and 7th positions. Thus the output is the sequence Y = 01100010.

(c) NOT Gate: Figure (a) shows a NOT gate, also called an inverter, with input A and output Y = A' where “inversion,” denoted by the prime, is defined by the “truth table” in Fig.(b). The value of the output Y = A' is the opposite of the input A; that is, A'= 1 when A = 0 and A'= 0 when A = 1. We emphasize that a NOT gate can have only one input, whereas the OR and AND gates may have two or more inputs.
Suppose, for instance, a NOT gate is asked to process the following three sequences:

       A1 = 110001, A2 = 10001111, A3 = 101100111000
The NOT gate changes 0 to 1 and 1 to 0. Thus
A'1 = 001110, A'2 = 01110000, A' 3 = 010011000111 are the three corresponding outputs.

LOGIC CIRCUITS

Observe that the truth tables for the OR, AND, and NOT gates are respectively identical to the truth tables for the propositions p ∨ q (disjunction, “p or q”), p ∧ q (conjunction, “p and q”), and ¬p (negation, “not p”). The only difference is that 1 and 0 are used instead of T and F. Thus the logic circuits satisfy the same laws as do propositions and hence they form a Boolean algebra.We state this result formally.

Theorem:

- Logic circuits form a Boolean Algebra.

Accordingly, all terms used with Boolean algebras, such as, complements, literals, fundamental products, minterms, sum-of-products, and complete sum-of-products, may also be used with our logic circuits.

AND-OR Circuits

The logic circuit L which corresponds to a Boolean sum-of-products expression is called an AND-OR circuit. Such a circuit L has several inputs, where:

(1) Some of the inputs or their complements are fed into each AND gate.
(2) The outputs of all the AND gates are fed into a single OR gate.
(3) The output of the OR gate is the output for the circuit L.

The following illustrates this type of a logic circuit.

EXAMPLE

Figure is a typical AND-OR circuit with three inputs, A, B, C and output Y . We can easily express Y as a Boolean expression in the inputs A, B, C as follows. First we find the output of each AND gate:

(a) The inputs of the first AND gate are A, B, C; hence A · B · C is the output.
(b) The inputs of the second AND gate are A, B', C; hence A · B'· C is the output.
(c) The inputs of the third AND gate are A'and B; hence A'· B is the output.

Then the sum of the outputs of the AND gates is the output of the OR gate, which is the output Y of the circuit. Thus:

NAND and NOR Gates

There are two additional gates which are equivalent to combinations of the above basic gates.

(a) A NAND gate, pictured in Fig.(a), is equivalent to an AND gate followed by a NOT gate.
(b) A NOR gate, pictured in Fig.(b), is equivalent to an OR gate followed by a NOT gate.
The truth tables for these gates (using two inputs A and B) appear in Fig.(c). The NAND and NOR gates can actually have two or more inputs just like the corresponding AND and OR gates. Furthermore, the output of a NAND gate is 0 if and only if all the inputs are 1, and the output of a NOR gate is 1 if and only if all the inputs are 0.



Observe that the only difference between theAND and NAND gates between the OR and NOR gates is that the NAND and NOR gates are each followed by a circle. Some texts also use such a small circle to indicate a complement before a gate. For example, the Boolean expressions corresponding to two logic circuits in Fig. are as follows:

(a) Y = (A'B)', (b) Y = (A' + B'+ C)'

BOOLEAN FUNCTIONS

Consider a logic circuit L with n = 3 input devices A, B, C and output Y , say
Y = A · B · C + A · B'· C + A' · B
Each assignment of a set of three bits to the inputs A, B, C yields an output bit for Y . All together there are 2n = 23 = 8 possible ways to assign bits to the inputs as follows:

000, 001, 010, 011, 100, 101, 110, 111

The assumption is that the sequence of first bits is assigned to A, the sequence of second bits to B, and the sequence of third bits to C. Thus the above set of inputs may be rewritten in the form

A = 00001111, B= 00110011, C= 01010101

We emphasize that these three 2n = 8-bit sequences contain the eight possible combinations of the input bits.
The truth table T = T (L) of the above circuit L consists of the output sequence Y that corresponds to the input sequences A, B, C. This truth table T may be expressed using fractional or relational notation, that is, T may be written in the form

T (A,B,C) = Y or T (L) = [A,B,C; Y ]

This form for the truth table for L is essentially the same as the truth table for a proposition.
The only difference is that here the values for A, B, C, and Y are written horizontally.
Consider a logic circuit L with n input devices.There are many ways to form n input sequencesA1,A2, . . . , An so that they contain the 2n different possible combinations of the input bits. (Note that each sequence must contain 2n bits.) One assignment scheme is as follows:

A1: Assign 2n−1 bits which are 0’s followed by 2n−1 bits which are 1’s.

A2: Repeatedly assign 2n−2 bits which are 0’s followed by 2n−2 bits which are 1’s.

A3: Repeatedly assign 2n−3 bits which are 0’s followed by 2n−3 bits which are 1’s.

And so on. The sequences obtained in this way will be called special sequences. Replacing 0 by 1 and 1 by 0 in the special sequences yields the complements of the special sequences.

EXAMPLE

(a) Suppose a logic circuit L has n = 4 input devices A, B, C, D. The 2n = 24 = 16-bit special sequences for A, B, C, D follow:

A = 0000000011111111    ,     C= 00110011001100110011

B = 0000111100001111    ,     D= 01010101010101010101

That is:

(1) A begins with eight 0’s followed by eight 1’s. (Here 2n−1 = 23 = 8.)

(2) B begins with four 0’s followed by four 1’s, and so on. (Here 2n−2 = 22 = 4.)

(3) C begins with two 0’s followed by two 1’s, and so on. (Here 2n−3 = 21 = 2.)

(4) D begins with one 0 followed by one 1, and so on. (Here 2n−4 = 20 = 1.)

(b) Suppose a logic circuit L has n = 3 input devices A, B, C. The 2n = 23 = 8-bit special sequences for A, B, C and their complements A', B', C' are as follows:

A = 00001111, B= 00110011, C= 01010101 A'= 11110000, B' = 11001100, C' = 10101010
Figure contains a three-step algorithm for finding the truth table for a logic circuit L where the output Y is given by a Boolean sum-of-products expression in the inputs.

EXAMPLE

(a) Consider Boolean expressions E = E(x, y, z) with three variables. The eight minterms (fundamental products involving all three variables) are as follows:

xyz, xyz', xy'z, x'yz, xy'z', x'yz', x'y'z'


The truth tables for these minterms (using the special sequences for x, y, z) follow:
xyz = 00000001, xyz '= 00000010, xy'z = 00000100, x'yz = 00001000
xy'z' = 00010000, x'yz' = 00100000, x'y'z = 01000000, x'y'z'= 10000000

Observe that each minterm assumes the value 1 in only one of the eight positions.

(b) Consider the Boolean expression E = xyz' + x'yz + x'y'z.
Note that E is a complete sum-of-products expression containing three minterms. Accordingly, the truth table T = T (E) for E, using the special sequences for x, y, z, can be easily obtained from the sequences in part (a). Specifically, the truth table T (E) will contain exactly three 1’s in the same positions as the 1’s in the three minterms in E. Thus T (00001111, 00110011, 01010101) = 01001010
or simply T (E) = 01001010.

KARNAUGH MAPS

Karnaugh maps, where minterms involving the same variables are represented by squares, are pictorial devices for finding prime implicants and minimal forms for Boolean expressions involving at most six variables. We will only treat the cases of two, three, and four variables. In the context of Karnaugh maps, we will sometimes use the terms “squares” and “minterm” interchangeably. Recall that a minterm is a fundamental product which involves all the variables, and that a complete sum-of-products expression is a sum of minterms.

First we need to define the notion of adjacent products. Two fundamental products P1 and P2 are said to be adjacent if P1 and P2 have the same variables and if they differ in exactly one literal. Thus there must be an uncomplemented variable in one product and complemented in the other. In particular, the sum of two such adjacent products will be a fundamental product with one less literal.

EXAMPLE

Find the sum of adjacent products P1 and P2 where:

(a) P = xyz' and P2 = xy'z'.
P1 + P2 = xyz'+ xy'z' = xz'(y + y') = xz'(1) = xz'

(b) P1 = x'yzt and P2 = x'yz't . P1 + P2 = x'yzt + x'yz't = x'yt (z + z') = x'yt (1) = x'yt

(c) P1 = x'yzt and P2 = xyz't .
Here P1 and P2 are not adjacent since they differ in two literals. In particular,
P1 + P2 = x'yzt + xyz't = (x'+ x)y(z + z')t = (1)y(1)t = yt

(d) P1 = xyz' and P2 = xyzt .

Here P1 and P2 are not adjacent since they have different variables. Thus, in particular, they will not appear as squares in the same Karnaugh map.

Case of Two Variables

The Karnaugh map corresponding to Boolean expressions E = E(x, y) with two variables x and y is shown in Fig.(a). The Karnaugh map may be viewed as a Venn diagram where x is represented by the points in the upper half of the map, shaded in Fig.(b), and y is represented by the points in the left half of the map, shaded in Fig.(c). Thus x is represented by the points in the lower half of the map, and y is represented by the points in the right half of the map. Accordingly, the four possible minterms with two literals, xy, xy , x y, x y are represented by the four squares in the map, as labeled in Fig. 15-16(d). Note that two such squares are adjacent, as defined above, if and only if the squares are geometrically adjacent (have a side in common).


Any complete sum-of-products Boolean expression E(x, y) is a sum of minterms and hence can be represented in the Karnaugh map by placing checks in the appropriate squares. A prime implicant of E(x, y) will be either a pair of adjacent squares in E or an isolated square, i.e., a square which is not adjacent to any other square of E(x, y). A minimal sum-of-products form for E(x, y) will consist of a minimal number of prime implicants which cover all the squares of E(x, y) as illustrated in the next example.

EXAMPLE

Find the prime implicants and a minimal sum-of-products form for each of the following complete sum-of-products Boolean expressions:

(a) E1 = xy + xy ; (b) E2 = xy + x y + x y ; (c) E3 = xy + x y
This can be solved by using Karnaugh maps as follows:
(a) Check the squares corresponding to xy and xy as in Fig.(a). Note that E1 consists of one prime implicant, the two adjacent squares designated by the loop in Fig.(a). This pair of adjacent squares represents the variable x, so x is a (the only) prime implicant of E1. Consequently, E1 = x is its minimal sum.



(b) Check the squares corresponding to xy, x y, and x y as in Fig.(b). Note that E2 contains two pairs of adjacent squares (designated by the two loops) which include all the squares ofE2. The vertical pair represents y and the horizontal pair represents x ; hence y and x are the prime implicants of E2. Thus E2 = x + y is its minimal sum.
(c) Check the squares corresponding to xy and x y as in Fig. 15-17(c). Note that E3 consists of two isolated squares which represent xy and x y ; hence xy and x y are the prime implicants of E3 and E3 = xy + x y is its minimal sum.

Case of Three Variables

The Karnaugh map corresponding to Boolean expressions E = E(x, y, z) with three variables x, y, z is shown in Fig.(a). Recall that there are exactly eight minterms with three variables:
xyz, xyz , xy z , xy z, x yz, x yz , x y z , x y z
These minterms are listed so that they correspond to the eight squares in the Karnaugh map in the obvious way. Furthermore, in order that every pair of adjacent products in Fig.(a) are geometrically adjacent, the right and left edges of the map must be identified. This is equivalent to cutting out, bending, and gluing the map along the identified edges to obtain the cylinder pictured in Fig.(b) where adjacent products are now represented by squares with one edge in common.


Viewing the Karnaugh map in Fig.(a) as a Venn diagram, the areas represented by the variables x, y, and z are shown in Fig. Specifically, the variable x is still represented by the points in the upper half of the map, as shaded in Fig.(a), and the variable y is still represented by the points in the left half of the map, as shaded in Fig.(b). The new variable z is represented by the points in the left and right quarters of

the map, as shaded in Fig.(c). Thus x , y , and z are represented, respectively, by points in the lower half, right half, and middle two quarters of the map.

By a basic rectangle in the Karnaugh map with three variables, we mean a square, two adjacent squares, or four squares which form a one-by-four or a two-by-two rectangle. These basic rectangles correspond to fundamental products of three, two, and one literal, respectively. Moreover, the fundamental product represented by a basic rectangle is the product of just those literals that appear in every square of the rectangle.

Suppose a complete sum-of-products Boolean expression E = E(x, y, z) is represented in the Karnaugh map by placing checks in the appropriate squares.Aprime implicant of E will be a maximal basic rectangle of E, i.e., a basic rectangle contained in E which is not contained in any larger basic rectangle in E.Aminimal sum-ofproducts form for E will consist of a minimal cover of E, that is, a minimal number of maximal basic rectangles of E which together include all the squares of E.

Case of Four Variables

The Karnaugh map corresponding to Boolean expressions E = E(x, y, z, t) with four variables x, y, z, t is shown in Fig. Each of the 16 squares corresponds to one of the 16 minterms with four variables,
xyzt, xyzt , xyz t , xyz t, . . . , x yz t
as indicated by the labels of the row and column of the square. Observe that the top line and the left side are labeled so that adjacent products differ in precisely one literal. Again we must identify the left edge with the right edge (as we did with three, variables) but we must also identify the top edge with the bottom edge. (These identifications give rise to a donut-shaped surface called a torus, and we may view our map as really being a torus.)


A basic rectangle in a four-variable Karnaugh map is a square, two adjacent squares, four squares which form a one-by-four or two-by-two rectangle, or eight squares which form a two-by-four rectangle. These rectangles correspond to fundamental products with four, three, two, and one literal, respectively. Again, maximal basic rectangles are the prime implicants. The minimization technique for a Boolean expression E(x, y, z, t) is the same as before.

EXAMPLE

Find the fundamental product P represented by the basic rectangle in the Karnaugh maps shown in Fig.
In each case, find the literals which appear in all the squares of the basic rectangle; P is the product of such literals.
(a) xy, and z appear in both squares; hence P = xy z .
(b) Only y and z appear in all four squares; hence P = yz.
(c) Only t appears in all eight squares; hence P = t .