A BOOLEAN ALGEBRA
pdf
keyboard_arrow_up
School
The Hong Kong University of Science and Technology *
*We aren’t endorsed by this school
Course
271
Subject
Mathematics
Date
Nov 24, 2024
Type
Pages
10
Uploaded by JusticeNeutronCapybara57
2 A BOOLEAN ALGEBRA 2.1 Before starting on what follows, the reader is advised to turn back to the Preface for suggestions on how much of this chapter to read, and how many of the examples to do. 2.2 We consider a collection of elements represented by A, B, C, ... , two binary operations represented by the symbols u and n, and a unary operation ('), which shall obey the postulates given in the table of 2.3. The dual of each postulate is also a postulate, so they are listed in pairs, (1), (1D); (2), (2D); etc. 2.3 The postulates The commutative laws The distributive laws AUB=BUA AnB=BnA A n (B u C) = (An B) u (An C) A u (B n C) = (A u B) n (Au C) The identity elements The complementary element The associate laws Au A'= 1 An A'= 0 (Au B) u C = A u (B u C) (A n B) n c = A n (B n C) (1) (1D) (2) (2D) (3) (3D) (4) (4D) (5) (SD) 2.4 Also we have the 'equality axioms' as given in 1.27. When we are using 1.27, (1), (II), or (III), this will not be stated. 7 A. P. Bowran, A Boolean Algebra
© A. P. Bowran 1965
8 A BOOLEAN ALGEBRA 2.5 Exercise. Rewrite 2.3 using the + . notation. 2.6 Some useful theorems AU1=1 AnO=O AUA=A AnA=A Au (An B)= A An (Au B)= A (A')'= A (0)' = 1 (1)' = 0 A u (A' n B) = A u B A n (A' u B) = A n B (A n B)' = A' u B' (A u B)' = A' n B' If A u B = 0, then A = B = 0 If A n B = 1, then A = B = 1 (A n B) u (B n C) u (C n A') = (An B) u (C n A') (A u B) n (B u C) n (C u A') = (Au B) n (C u A') [(A' n B) u (A n B')l' = (A n B) u (A' n B') (6) (6D) (7) (7D) (8) (8D) (9) (10) (IOD) (11) (ltD) (12) (12D) (13) (13D) (14) (14D) (15) 2.7 The theorems we are about to prove have been listed and numbered in 2.6, so that we can state, at any step in a proof, our number for the theorem or postulate we are using. If two steps are taken at once, both theorems used will be stated. For instance, instead of we write 1 n(Au 1) =(Au l)n1 =(Au 1) 1 n (Au 1) = Au 1 (ID) (3D) (1D, 3D) The duals of proved theorems will be stated but not proved; the reader is recommended to do several as exercises. 2.8 To prove AU1=1 AnO=O (6) (6D)
A BOOLEAN ALGEBRA A v 1 = (A v 1) n 1 =(A v 1) n (AvA') =A v (1 n A') =AVA' = 1 9 (3D) (4) (2D) (1D, 3D) (4) Exercise. Prove (i) 1 v 1 = 1 (ii) 0 v 1 = 1 (iii) 1 () 0 = 0 (iv) 0 n 0 = 0 2.9 The Laws of absorption A v (A n B) = A (8) An~V~=A ~~ A v (An B) = (An 1) u (An B) (3D) = A n (1 u B) (2) = An 1 (1, 6) =A (3D) 2.10 The laws of tautology (the names of several of these laws come from logic or other applications of the algebra) In (8) put B = 1, AUA=A AnA=A Au (An 1) =A AUA=A and similarly put B = 0 in (SD) for (7D). Exercise. Prove that (i) 0 U 0 = 0 (ii) 1 () 1 = 1. (7) (7D) (3D) 2.11 Our next theorem (see 1.18) is to prove that each element A has a unique complement, A'. We do this by assuming two elements, B and C, both satisfying the postualtes (4) and (4D), and proving them equal. So, given (a) (b) to prove AUB=AUC=1 AnB=AnC=O B=C B=Bnl = B n (Au C) = (B n A) u (B n C) = 0 v (B n C) =BnC (3D) (a) (2D) (1, (b)) (1' 3)
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
10 A 'SOOLEAN ALGEBRA similarly we can prove that C = C n B, and so, by (1D), B=C and A has one and only one complement. 2.12 It is also true that no element is its own complement; the proof of this depends on the assumption that (3) and (3D) define different elements, 0 and 1, so that 0 and 1 cannot be equal. For suppose there exists an element X such that X = X'. Then from (4D) we have X n X= 0 and also XU X= 1; but XnX=XUX=X (7&7D) so X = 0 and X = 1, which is impossible, and so X #-
X'. 2.13 Exercise. Prove that 0' = 1 (10) 2.14 Exercise. Prove that the number of elements in a Boolean algebra is always even. 2.15 Exercise. Fill in the numbers of the statements that justify each step in the following proof of (11) A u (A' n B) = (A u A') n (A u B) = 1 n (Au B) =AUB 2.16 Exercise. (i) Prove de Morgan's Laws (Au B)' = A' n B' (A n B)' = A' u B' Note that 2.11 shows us that it is sufficient to prove that (12) (12D) (A u B) n (A' n B') = 0 and also (A u B) u (A' n B') = 1 (ii) Extend (2) to prove that: WAn~uQu~=0n~u0n~u0n~ (b) (Au B) n (P u Q) = (An P) u (An Q) u (B n P) u (B n Q) and similarly extend (12D) to (A u B u C)' = A' n B' n C' when applying these we shall say we are applying (2), (12), etc. 2.17 Two other identities that are often useful are (An B) u (B n C) u (C n A') = (An B) u (C n A') (14)
A BOOLEAN ALGEBRA and its dual, (14D); for (A n B) u (B n C) u (C n A') = (An B) u [(B n C) n (Au A')] u (C n A') =(An B) u (B n C n A) u (B n C n A') u (C n A') = (A n B) u [(A n B) n C] u (C n A') u [(C n A') n B)] = (A n B) u (C n A') 2.18 Exercise. Justify each step in 2.17. 11 2.19 Exercise. Prove that, if both An B = AU C and also An B = A n C, then B = C. 2.20 De Morgan's laws show us that we can, if we wish, dispense entirely with one or other of the operators u or n. Example. Write Au {B n C n (DuE)}: (i) without using U (ii) , , n (i) A u {B n C n (D u E)} = A u {B n C n (D' n E')'} = [A' n {B n C n (D' n E')'}']' (ii) A u {B n C n (D u E)} = A u {(B' u C')' n (D u E)} = A u {(B' u C')" u (D u E)'}' = A u {(B' u C') u (D u E)'}' 2.21 Exercise. Justify each step in Example 2.20. 2.22 Exercise. Express: (i) AU B U C without using U, and (ii) A u (B n C) u (B n C' n D) without n 2.23 The major application of a Boolean algebra is made by express-
ing the idea we want in terms of the algebra, and then using the algebra to simplify the expression. Sometimes, as here, ~u~n~u~n~u~=~n~u~n~u~n~ (A u B)' = (A' n B') neither form is obviously simpler than the other, but the choice is easy in and A u (A' n B) = A u B A' u B' u (A n B) = 1 2.24 Examples. Simplify: (a) X.Y.Z + X'.Y.Z + X.Y'.Z + X.Y.Z'
12 A BOOLEAN ALGEBRA X.Y.Z. + X'.Y.Z = Y.Z.(X +X') = Y.Z.1 =Y.Z X.Y.Z + X'.Y.Z + X.Y'.Z+ X.Y.Z' = (X.Y.Z + X'.Y.Z) + (X.Y.Z + X.Y'.Z) (1) & (2) (4) (3D) + (X. Y. Z + X. Y. Z') (7) = Y. Z + Z. X + X. Y (as above) (b) A+ A'.B.C + A'.B.C' =A+ A'.B.(C + C') (2) =A+ A'.B.(l) (4) =A+ A'.B (3D) =A+B (11) (c) A.B + A'.C + A'.D + B'.C + B'.D = A.B +(A'+ B').(C +D) = A.B +(A. B)' .(C + D) = A.B + C + D (See also 2.28.) 2.25 Exercise. Simplify the following: (a) A'.B'.(A + B +C) (b) X.Y + X'.Y + X.Y' + X'.Y' (c) A.A'.B.C + A.B.B'.C + A.B.C.C' (d) A.B.C + A'.B.C. + A'.B'.C + A'.B'.C' (2) (12) (11) 2.26 In discussing expressions, etc., in Boolean algebra we retain many of the terms used in the algebra of numbers. Elements, like numbers, will be 'known', 'unknown', 'constant', 'variable', and so on, and we will talk of sums, products, and mononomials. These are elements represented by one letter, A, B, C, ... or its complement A', B', C', ... or any product formed by any number of these, for example, A.B' .C' .D. Note that (A.B)' is not a mononomial, but that (A'. B') is. 2.27 Exercise. Which of the following are mononomials (i) A n B n C' (ii) (A')' (iii) P n Q' n R (iv) P' n Q n (R n S)'? 2.28 The sum of a number of mononomials is called a polynomial. That every expression can be written in this form by using (12), (12D), and (2) is fairly easy to see. Example. Express as a polynomial (A.B + B.C + B'.X.Y).{A + B.C + (A.X + B.Y)'} = (A.B + B.C + B'.X.Y).{A + B.C +(A. X)' .(B.Y)'} (12)
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
A BOOLEAN ALGEBRA = (A.B + B.C + B'.X.Y) .{A+ B.C +(A'+ X').(B' + Y')} = (A.B + B.C + B'.X.Y) .(A+ B.C + A'.B' + A'.Y' + B'.X' + X'.Y') = (A.B + B.C + B'.X.Y) .(A+ B.C + B' + Y' + B'.X' + X'.Y') = (A.B + B.C + B'.X.Y).(A + B.C + B' + Y') = (A.B + B.C + B'.X.Y).(A + C + B' + Y') = A.A.B + A.B.C. + A.B'.X.Y + A.B.C. + B.C.C. + B'.C.X.Y + A.B.B' + B.B'.C + B'.B'.X.Y 13 (12D) (2) (11) (8) (9, 8) + A.B.Y' + B.C.Y' + B'.X.Y.Y' (2) = A.B + A.B.C + A.B'.X.Y + A.B.C + B.C + B'.C.X.Y + B'.X.Y + A.B.Y' + B.C.Y' (3),(4D)&(7D) = A.B + B.C + B'.X.Y (8) 2.29 Exercise. Express as polynomials: (a) (X'.Y.Z + X.Y'.Z + X.Y.Z')' (b) (A.B + A'.B')' (c) (A.B + C.D).(A'.B' + C'.D')' 2.30 The disjunctive normal form. First, we are concerned with the mononomials that can be formed from a given group of elements A
1
, A
2
, A
3
, ••. , A,; where in each mononomial each of these n ele-
ments, or its complement, is a factor. Exercise. Show that there are 2n such mononomials. We proceed to show how to express any Boolean function of given elements as the sum of a number of such terms. This is called the disjunctive normal form of the given function. First, as in 2.28 and 2.29 we reduce the expression to an equivalent polynomial, and then X+ X'.Y + X'.Y'.Z = X.(Y + Y').(Z + Z') + X'.Y.(Z + Z') + X'.Y'.Z (4) = X.Y.Z + X.Y.Z' + X.Y'.Z + X.Y'.Z' + X'.Y.Z + X'.Y.Z' + X'.Y'.Z (2) 2.31 Exercise. Express in their disjunctive normal forms the answers to 2.25 (d) and 2.29 (a) and (b). 2.32 Exercise. Simplify the following disjunctive normal forms: (i) A.B.C + A.B'.C + A.B.C' + A.B'.C' (ii) A.B'.C + A.B'.C' + A'.B'.C + A'.B'.C' (iii) A.B.C.D + A.B.C.D' + A.B.C'.D + A.B.C'.D'
14 A BOOLEAN ALGEBRA 2.33 The property of duality leads us at once to the dual of the disjunctive normal form, the conjunctive normal form, which is, of course, the product of a number of factors, each of which is the sum of n elements. To obtain the conjunctive normal form, we use an extension of (2D) A.B + P.Q.R = (A.B + P).(A.B + Q).(AB + R) =(A+ P).(B + P).(A + Q).(B + Q) .(A+ R).(B + R) and then L + M = L + M + 0 = L + M + N.N' = (L + M + N).(L + M + N') Example. X.Z + Y.Z' +X' .Y' .Z' =(X+ Y).(X + Z').(Z + Y).(Z + Z') + X'.Y'.Z' =(X+ Y).(X + Z').(Z + Y) + X'.Y'.Z' = (X + Y + X'). (X + Z' + X'). (X' + Y + Z) .(X+ Y + Y').(X + Y' + Z').(Z + Y + Y') .(X+ Y + Z').(X + Z' + Z').(Z + Y + Z') = 1. 1. (X' + Y + Z). 1. (X + Y' + Z'). 1. (X + Y + Z) .1.1 = (X' + Y + Z). (X + Y' + Z'). (X + Y + Z') 2.34 Express similarly : (a) A+ (B + C).(C + A) (b) Y. Z + Z. X + X. Y 2.35 Some other useful theorems are: (i) If A = 0 and B = 0, then A U B = 0 and conversely. A=O AUB=B =0 (given) 1.27 (IV) (given) conversely, if Au B = 0 An (Au B)= 0 Au (An B)= 0 A=O 1.27 (IVD) (2, 7D) (8) The dual theorems are 'If A = 1, and B = 1, then An B = 1. and conversely'. (ii) If and then A.B = 0 A'.C = 0 B.C = 0 (a) (b)
From (a) " (b) A BOOLEAN ALGEBRA A.B.C = 0 A'.B.C = 0 A.B.C + A'.B.C = 0 B.C.(A +A')= 0 B.C.l = 0 B.C = 0 15 (IVD) (IVD) 2.35 (i) (lD, 2) (4) (3D) 2.36 'Simplifying' a disjunctive normal form can lead to two answers which are equally 'simple' and not obviously equal. Consider X.Y.Z + X.Y.Z' + X.Y'.Z + X'.Y'.Z + X'.Y'.Z' = X.Y.(Z + Z') + X'.Y'.(Z + Z') + X.Y'.Z = X.Y + X'.Y' + X.Y'.Z = X.(Y + Y'.Z) + X'.Y' or X.Y + Y'.(X' + X.Z) = X.(Y + Z) + X'.Y' = X.Y + Y'.(X' + Z) = X.Y + X'.Y' + X.Z = X.Y + X'.Y' + Y'.Z = E
1 (say) = E
2 (say) 2.37 Exercise. Show that these two expressions satisfy E1·E2 = E1 E
1
.E~ = 0 (2) (4, 3D) (2) (11) (2) 2.38 'Solving equations'-a process one performs so often in the early stages of the algebra of numbers-is not often useful in Boolean Algebra. We can only take an equation connecting some known elements, A, B, C, ... and an unknown, X, and reshape it to describe X as clearly as possible. This is usually done by reducing the equation to the form (A n X) u (B n X') = 0 whence A n X = 0 and B n X' = 0 Exercise. Prove that this solution is possible iff AnB=O 2.39 Exercise. (i) Show that, if A = B, then A n B' = B n B' = 0 but that A n B' = 0 does not imply that A = B. (ii) Prove that A = B does follow from (A n B') u (A' n B) = 0 and conversely. 2.35 (i)
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
16 A BOOLEAN ALGEBRA 2.40 Our ability (see 2.28, etc.) to express any Boolean function as a polynomial allows us to write any equation in X in the form (A n X) u (B n X') u C = (P n X) u (Q n X') u R and we see, by 2.39, that this can be written (A.X + B.X' + C).(P.X + Q.X' + R)' + (A.X + B.X' + C)'.(P.X + Q.X' + R) = 0 which reduces to the form L. X + M. X' + N = 0 This can be written L. X + M. X' + N. (X + X') = 0 whence (L + N). X = (M + N). X' = 0 2.41 Exercise. (i) Perform this reduction and so get L, M, N m terms of A, B, C, P, Q, R. (ii) Solve: (a) A+ X =B (b) A.X + B = 0 2.42 A very important function in most applicat ons of Boolean algebra is (A' n B) u (A n B') and it is called the symmetric difference between A and B (see 2.39 (ii)). In many books that use the U n notation this is represented by A + B, but we must use (A' n B) u (A n B') = A~ B Many properties of this function of A and B follow readily. 2.43 Exercise. Prove that: (i) A~ B = B ~ A = A' ~ B' = B' ~ A' (ii) (A~ B)' = A'~ B = A~ B' (iii) A~ B = (A u B) 11 (A' u B') = (Au B) II (A II B)' = (Au B)~ (A II B) (iv) A~ 1 =A' (v) A~ A= 0 (vi) A~ A'= 1 (vii) A~ 0 = A (viii) 1 ~ 1 = 0 (ix) 1 ~ 0 = 1 (x) 0~ 0 = 0 (xi) (Au X)~ (A u Y) = A' II (X~ Y) (xii) (A n X)~ (A n Y) = A n (X~ Y) (see 2.29 (h))