oa Barronis Educational Series, Inc. $695 I@GC AND BO@IEAN He Presupposes only some -high school rt algebra ; © _ Provides slow cultivation of manipulative i skillsI@GCAND | BO@LLAN© Copyright 1979 by Barron’s Educational Series, Inc. All rights reserved. No part of this book may be reproduced in any form, by photostat, microfilm, xerography, or any other means, or incorporated into any information retrieval system, electronic or mechanical, without the written permission of the copyright owner Alll inquiries should be addressed to. Barron’s Educational Series, Inc. 113 Crossways Park Drive Woodbury, New York 11797 Library of Congress Catalog No. 75-1006 International Standard Book No. 0-8120-0537-6 Dae: Coenen eee ee tater ‘Logic, Symbolic and mathematical. 2. Algebra, Boolean. I. Levitz, Hilbert, joint author. II. Title. LAT SHV'.3 75-1 0-8120-0537-6 PRINTED IN THE UNITED STATES OF AMERICATO OUR MENTORS JOE L. MOTT KURT SCHUTTEen el Contents PREFACE vii INTRODUCTION | viii 1 Sentence Composition 1 1 12 2 14 15 1.6 17 18 The Basic Logical Operations 1 Truth Values 2 Alternative Translations 7 Converses and Contrapositives 8 Logic Forms and Truth Tables 9 Tautologies, Contradictions, and Contingencies 14 Sentential Inconsistency 15 Constructing Logic Forms from Truth Tables 16 2 Algebra of Logic 21 21 2 23 24 2.5 2.6 2.7 28 29 Logical Equivalence 21 Basic Equivalences 23 Algebraic Manipulation 24 Conjunctive Normal Form 29 Reduction to Conjunctive Normal Form 30 Uses of Conjunctive Normal Form 33 Disjunctive Normal Form 35 Uses of Disjunctive Normal Form 38 Interdependence of the Basic Logical Operations 40 3 Analysis of Inferences 45 BE 3.2 oa Sentential Validity 45 BasicInferences 49 Checking Sentential Validity of Inferences by Re- peated Use of Previously Proven Inferences 50 4 Switching Circuits 53 41 42 Representing Switching Circuits by Logic Forms 53 Simplifying Switching Circuits 58vi CONTENTS 43 Limitations of the Logic Form Method of Simpli- fying Switching Circuits 62 44 Designing a Switching Circuit Starting with a Table Which Describes Its Behavior 63 5 Set Theory 69 Ors Elementary Set Theory 69 5.2 Basic Identities and Relations of Set Theory 74 $3 Checking Consistency of Data 76 6 Boolean Algebra 81 61 The Abstract Approach 81 6.2 Definition of “Boolean Algebra” 83 63 Duality 86 6.4 Some Theorems of Boolean Algebra 87 7 Sample Examination 93 Answers 95 Exercises 95 Sample Examination 125 Suggested Books for Further Reading 129 Index 130ee ee ee ee ee Preface This book was intended for students who plan to study in the hu- manities and in the social and management sciences. Students in- terested in the physical and natural sciences, however, might also find its study rewarding. All that is presupposed is some high school algebra. The authors strongly urge that the topics be studied in the order in which they appear and that no topics be skipped. In recent years there has been considerable divergence of opinion among mathematics teachers as to the degree of abstraction, rigor, formality, and generality that is appropriate for elementary courses. We believe that the trend lately has been to go too far in these direc- tions. Quite naturally, this book reflects our views on this question. Although the subject matter is considered from a modern point of view, we have consciously tried to emulate the informal and lucid style of the better writers of a generation ago. Manipulative skills are cultivated slowly, and the progression from the concrete to the abstract is very gradual. We wish to extend our thanks to our typist Susan Schreck and to Matthew Marlin and Anne Park, who were students in a course from which this book evolved. We also wish to thank the editorial con- sultants of Barron’s for their helpful suggestions. KATHLEEN Levitz Tallahassee, Florida HILBert LevitzIntroduction Logic is concerned with reasoning. Its central concern is to dis- tinguish good arguments from poor ones. One of the first persons to set down some rules of reasoning was Aristotle, the esteemed philoso- pher of ancient Greece. For almost two thousand years logic re- mained basically as Aristotle had left it. Students were required to memorize and recite his rules, and generally they accepted these rules on his authority, At the end of the eighteenth century Kant, one of the great philoso- phers of modern times, expressed the opinion that logic was a com- pleted subject. Just fifty years later, however, new insights and results ‘on logic started to come forth as a result of the investigations of George Boole and others. In his work, Boole employed symbolism in a manner suggestive of the symbolic manipulations in algebra. Since then, logic and mathematics have interacted to the point that it no longer seems possible to draw a boundary line between the two. During the last forty years some deep and astounding results about logic have been discovered by the logician Kurt Gédel and others. Unfortunately, these results are too advanced to be presented in this book. We hope that what you learn here will stimulate you to study these exciting results later. Finally, we must tell you that complete agreement does not yet exist on the question of what constitutes correct reasoning. Even in mathematics, where logic plays a fundamental role, some thoughtful people disagree on the correctness of certain types of argumentation. Perhaps someday, someone will settle these disagreements once and for all. vii1 Sentence Composition 1.1 The Basic Logical Operations Compound sentences are often formed from simpler sentences by means of the five basic logical operations. These operations and their symbols are: conjunction ~ disjunction v negation q implication — bi-implication <> The symbols are usually read as follows: | SYMBOL || TRANSLATION Note that a good way to keep from confusing the symbols a and v is to remember that a looks like the first letter of the word “AND.” If the letters A and B denote particular sentences, you can use the logical operations to form these compound sentences: AaB, read AvB, read TA, read AB, read A+B, read AandB AorB it is not the case that A if AthenB Aif and only if B2 SENTENCE COMPOSITION Examples. Let A be the sentence: “Snow is white.” Let B be the sentence: “Grass is green.” Then A a Bis the sentence: “‘Snow is white and grass is green.” Let A be the sentence: ‘Humpty Dumpty is an egg.” Then 7A is the sentence: “It is not the case that Humpty Dumpty is an egg.” Let Abe: ‘Jack is a boy.” Let Boe: “‘Jillis a girl.” Then A — Bis: “If Jack is a boy, then Jill is a girl.” Let Abe: “Birds fly.” Let Bbe: ‘Bees sting.” Let C be: “Bells ring.” Then 7 A - (B v C) is: “If it is not the case that birds fly, then bees sting or bells ring.” Note that in the last example, the ‘‘not” sign applies only to the sen- tence A. If we had wanted to negate the entire sentence A — (B v C), we would have enclosed it in parentheses and written 1 [A —> (B v C)]. Then it would read, “It is not the case that if birds fly, then bees sting or bells ring.” 12 Truth Values A property of declarative sentences is that they are true or false, but not both. If a sentence is true, it has truth value t. If it is false, it has truth value f. You can compute the truth value of a compound sentence built from simpler sentences and logical operations if you know the truth values of the simpler sentences. This can be done by means of tables. The table for the conjunction operation is given below. Here is how to read it. On a given row, the extreme right-hand entry shows the truth value that the compound sentence A a B should have if the sentences A and B have the truth values entered for them in that row.ee eee ee ee 1.2 TRUTH VALUES 3 TABLE FOR « (“AND”) Examples. Use the table just given to find the truth values of these compound sentences: a) Giants are small and New York is large. b) New York is large and giants are small. c) America is large and Russia is large. ANSWERS: a) First label each part of the sentence with its own truth value. f t OO {Giants are small] 4 [New York is large]. Now look in the table to see which row has the values f, t (in that order) entered in the two left-hand col- umns. This turns out to be the third row (below the headings). Looking to the extreme right of that row, you will find that the entire sentence has the truth value f. b) Labeling each part with its truth value, we get ——~——. [New York is large] « [Giants are small]. Now look in the table to see which row has the values 1, f (in that order) entered in the two left-hand col- umns. This turns out to be the second row. Looking to the extreme right of that row, you will find that the entire sentence has the truth value f.4 SENTENCE COMPOSITION c) First label the parts: t t [America is large] a [Russia is large]. The first row of the table indicates that the entire sentence has the truth value t. We make the tables for the other four logical operations in a similar way: TABLE FOR TABLE FOR. v (“OR”) 1 (“NOT”) A eff | rt | TABLE FOR TABLE FOR -+ (IF ... THEN ...”) (IF AND ONLY IF”) B [a-B t t t f f fit t f jf t According to the table for v, the disjunction A v B is a true sen- tence if A is true, if B is true, or if both A and B are true. Unfor- tunately, in ordinary conversation people do not always use “or” this way. However, in mathematics and science (and in this book), the sentence A v Bis considered true even in the case where A and B are both true. The implication operation presents a similar problem. Quite often “if A, then B” indicates a cause-and-effect relationship as in the sen- tence: If it rains, the game will have to be postponed. Mathematicians and scientists, however, do not require such a cause- and-effect relationship in affirming the truth of A — B, and ouree es 1.2 TRUTH VALUES 5 table has been set up in accordance with their time-honored conven- tions. Examples. ANSWERS: Use the tables just given to compute the truth values of the following sentences: a) Af tyo equals six, then three equals three. b) (5 = 2) v6 = 8). c) Itis not the case that three equals three. 4) (2 = 4) v3 = 3) + (6 = 946 = DI. First label the parts with their truth values: t ———— a) [two equals six] — [three equals three] The third row of the table for + shows that the entire sentence gets the truth value t. b) f f a (S = 7) v (6 = 8) The fourth row of the table for v shows that the en- tire sentence gets the truth value f. c) t —— 7 [three equals three] The first row of the table for 1 shows that the en- tire sentence gets the truth value f. d) This one will involve the use of three tables because it contains three logical operation symbols. First label the elementary parts: =e — oe f “~ a-4 =4v 6-3 a (G=9) 0) a (6 = DI). From the third row of the table for v you can see that the part to the left of the arrow gets the truth value t. From the fourth row of the table for a, you6 SENTENCE COMPOSITION can see that the part to the right of the arrow gets the truth value f. Now labeling the parts to the left and right of the arrow with the truth values just com- puted for them, you have t f (2 = 4 vB = 31+ (6 - a6 = DY. From the second row of the table for — you can see that the entire sentence should have the truth value f, Exercises 1.2 1, Let A denote “Geeks are foobles” and let B denote “Dobbies are tootles.”” Write the English sentences corresponding to the following: (a) 1A (©) TAB) (b) AaB @) AB (c) AATB (g) (TAVB)+A (dd) TA>B (h) (A AB)<* 7B 2. Let A denote “Linus is a dog,” let B denote “Linus barks,” and let C denote “Linus has four legs.”” Write each of the following sentences in symbolic form: (a) Linus is a dog and Linus barks. (b) Linus is a dog if and only if Linus barks. (c) Ifit is not the case that Linus is a dog, then Linus barks. (d) If Linus is a dog, then (Linus barks or Linus has four legs). (e) If (Linus barks and Linus has four legs), then Linus is a dog. (f) (It is not the case that Linus barks) if and only if Linus is a dog. (g) It is not the case that (Linus is a dog if and only if Linus barks). 3. Let A denote “1 + 1 = 2” and let B denote “2-2 = 2.” Use the tables to find the truth values of the following sentences: (a) AvB (hy) B-rA . (bt) AvIB (i) TA (BAA) (c) TAVB G) IASB (d) TAAB (k) IBA (e) AaB (1) (VA vB)v(A4 B) (f) TA+B (m) (BvA)v 7 (BvA) (2) TA> 7B (n) (B— A) (A B) io+¥ . 3 4 A— 1.3 ALTERNATIVE TRANSLATIONS 7 4. Let A and B be sentences. Assuming that B has truth value f, use the tables to find those truth values for A which make the following ( sentences true. (@) BoA (b) AaB () IASB (d) (AvB)>B (ec) (1B>A)>A 13 Alternative Translations In English there are many ways of saying the same thing. Here is a list of some of the alternative ways which can be used to translate the logical operation symbols. A+B Not only A but B Aalthough B AorB Either Aor B AorBorboth Aand/orB [found in legal documents] TA A doesn’t hold It is not the case that A AB | IfA,then B. Ais a sufficient condition for B Aonly if B Bis a necessary condition for A Aimplies B B provided that A 7 A+B | Aifandonly ifB Aexactly , when B8 SENTENCE COMPOSITION Exercises 1.3 1. LetAbe: Peterisa canary. LetBbe: Joe isa parakeet. LetCbe: Peter sings. Let Dbe: Joe sings. : Translate the following into symbols. (a) 0) (c) qd) (e) Joe is a parakeet and Peter isa canary. - Although Joe does not sing, Peter sings. Peter sings if and only if Joe does not sing. Either Peter is a canary or Joe is a parakeet. Peter sings only if Joe sings. 2. Let M be: Mickey is a rodent. LetJbe: Jerry is a rodent. LetTbe: Tomisa cat. Translate the following into symbols. (a) (b) ©) @) () «) (g) Although Mickey is a rodent, Jerry is a rodent also. Mickey and Jerry are rodents, but Tom is a cat. If cither Mickey or Jerry are rodents, then Tom is a cat. Jerry is a rodent provided that Mickey i: Either Mickey isn’t a rodent or Jerry is a rodent. Jerry is a rodent only if Mickey is. Tom isa cat only if Jerry isn’t a rodent. Hot and Contrapositives Suppose you are given an implication A —> B. Two related implica- tions are given special names. B — Aiscalled the converse of A — B. 1B — 171 Aiscalled the contrapositive of A > B. The truth value of an implication and its converse may or may not agree. Below are given some examples to show this. Later you will see that an implication and its contrapositive always have the same truth value.lle lle telefon feces) (ufc) | culen)ec) fe) 1.5 LOGIC FORMS 9 : Examples. LetAbe: 1 = 2 Let Bbe: 2s aneven number. Then A — Bhas truth value t, while its converse B—> A has truth value f. : Let Ebe: 2isan even number. © LetObe: 3 is an odd number. Then E — 0 has truth value t, and its converse 0 > E 7 also has truth value t. Exercises 1.4 1. Let Dbe: Ollie is a dragon. Let Tbe: Ollie is toothless. Let Rbe: Ollie roars. Represent each of the following sentences symbolically. Then write the converse and the contrapositive of each sentence, both in symbols and in English. (a) If Ollie is a dragon, then Ollie roars. (b) If Ollie is toothless, then Ollie does not roar. (c) Ollie roars only if Ollie is a dragon. 2. Let A and B be two sentences. If A has truth value t, which truth value must B have to insure that: (a) A — Bhas truth value t? (b) the contrapositive of A —> Bhas truth value t? (c) the converse of A — B has truth value t? 3. Give examples of implications that have truth value t such that: (a) the converse has truth value t. (b) the converse has truth value f. 15 Logic Forms and Truth Tables Logical symbolism enables us to see at a glance how compound sen- tences are built from simpler sentences. Meaningful expressions built from variable symbols, logical operation symbols, and parentheses are called logic forms. Capital letters like A, B,C ... can be used as10 SENTENCE COMPOSITION the variable.symbols in constructing logic forms. The following are examples of logic forms: A>B B Ave (1A B)—-B Note that a single variable symbol is acceptable as a logic form. Logic forms will often be discussed. When talking about logic forms, heavy-type capital leters like A, B, C (with or without numerical sub- scripts) will be used to denote them. Thus in a given discussion, you might use the symbol B to denote the logic form (B-> A) (C> A) Remember: 1, Heavy type capital letters, like A, denote entire logic forms. 2. Regular capital letters, like A, are variable symbols which appear in a logic form. You have already seen that the truth value of a logic form is deter- mined by the truth values assigned to its variable symbols. Let A and B be variable symbols. A preceding section contained tables listing the values assigned to each of the logic forms: TA AvB AaB A+B AB for given truth values of A and B. The tables are examples of truth tables. Using these five tables, you can construct the truth table of any logic form. As an example, consider the truth table of the logic form (A vC) > (B= A). In each row give an assignment of truth values to the variable symbols A, B, and C, and at the right-hand end of the row list the value of the entire logic form for that assignment. The optional columns headed “A v C” and “B — A” are included to help fill in the table. If you feel sufficiently confident, you can omit such intermediate columns when building future truth tables.a, 1.5 LOGIC FORMS 11 TRUTH TABLE FOR (Av C)-> (B- A) Aj Bc | avc | B+A]| (AvC)~(B- A) t t t t t t t tif t t t t fit t t t t f {if t t t fiele t f f fi tele f f t f f i]t t t t fifif f t t U~— optional columns ‘We suggest that you first fill in the columns under the variable symbols A, B, C ... and then complete these columns one at a time. Below are repeated the first three columns of the preceding table. Note that the places in the columns which have t as entries are shaded, and observe that there is a pattern to this shading. By following the pattern you can be sure that a logic form with n distinct variable symbols will have a truth table with 2" rows and that these rows dis- play all the possible ways of assigning truth values to the variable symbols. Note that the top half of the left-hand column consists only of t entries, the bottom half of f entries. In the next column blocks of t entries and blocks of f entries are alternated; each block consists of 1/4 the total number of rows in the table. In the third column, each block makes up 1/8 of the total number of rows, etc.12. SENTENCE COMPOSITION Exercises 1.5 1. Construct the truth table for each of the following logic forms: (a) A+1A (b) (CAB) v(A>B) (c) Avo @) [A+ B)v (C> 1D) — (AaD) (©) [((Bv A) aC] + [(BaC) v(AaC)] 2. Use truth tables to determine the truth value of D, given the fol- lowing: (a) CistrueandC a Dis true (b) Cis false and D v Cis true ' (c) 1Dv 1 Cis false (d) Cis false and (C « D) > (C v D)istrue 3. a) Write a logic form corresponding to the following sentence: If the stock’s value rises or a dividend is declared, then the stock- holders will meet if and only if the board of directors summons them, but the chairman of the board does not resign. b) Determine the truth value of the preceding statement under the following assumptions by (partially) filling out the truth table for its logic form. i) The stock’s value rises, no dividend is declared, the stockholders will meet, the board of directors summons the stockholders, and the chair- man resigns. ii) The stock’s value rises and a dividend is declared, the board of directors fails to summon the stockholders, and the chairman resigns. 4. Horace, Gladstone, and Klunker are suspected of embezzling com- pany funds. They are questioned by the police and testify as follows: Horace: Gladstone is guilty and Klunker is innocent. Gladstone: If Horace is guilty, then so is Klunker. Klunker: 1’m innocent, but at least one of the others is guilty. (a) Assuming everyone is innocent, who lied? (b) Assuming everyone told the truth, who is innocent and who is guilty? (c) Assuming that the innocent told the truth and the guilty lied, who is innocent and who is guilty?SS a Ta 15 LOGIC FORMS 13 [Hint: Let H denote: Horace is innocent. Let Gdenote: Gladstone is innocent. Let K denote: Klunker is jnnocent. Now symbolize all three testimonies and make one single truth table with a column for each testimony. The desired information can be read from the table.] 5. Agent 006 knows that exactly one of four diplomats is really a spy. He interrogates them, and they make the following statements: Diplomat A: Diplomat C is the spy. Diplomat B: Lam nota spy. Diplomat C: Diplomat A’s statement is false. Diplomat D: Diplomat A is the spy. (a) 1f006 knows that exactly one diplomat is telling the truth, who is the spy? (b) If 006 knows that exactly one diplomat’s statement is false, who is the spy? [Hint: Let A denote: Diplomat A is a spy. Let Bdenote: Diplomat Bis a spy. LetC denote: Diplomat Cis a spy. Let Ddenote: Diplomat Disa spy. Now symbolize the reply of each diplomat and make a single truth table with a column for each reply. The desired information can be tead from the table.] *6. A certain college offered exactly four languages: French, German, Russian, and Latin. The registrar was instructed to enroll each stu- dent for exactly two languages. After registration, the following facts were compiled: i) All students who registered for French also registered for ex- actly one of the other three languages. ii) All students who registered for neither Latin nor German regis- tered for French. iii) All students who did not register for Russian registered for at least two of the other three languages. iv) No candidate who registered for Latin and German registered for Russian. Did the registrar actually follow his instructions? *This denotes a difficult problem.14 SENTENCE COMPOSITION [Hint: Let x be an arbitrary student at the college. Let Fdenote: x registered for French. Let Gdenote: x registered for German. Let Ldenote: x registered for Latin. Let Rdenote: x registered for Russian. Symbolize each of the four facts. Make a truth table with a column for each of the four facts. Locate the rows for which all four facts have truth value t. Examine these rows closely.] 1.6 Tautologies, Contradictions, and Contingencies Certain logic forms have truth tables in which the right-hand column consists solely of t’s. These forms are called tautologies. Hence a tautology is a logic form which has truth value t no matter what values are given to its variable symbols. If the right hand column of the truth table of a logic form consists solely of f’s, the logic form is called a contradiction. Thus a contradiction has truth value f no mat- ter what values are given to its variable symbols. If a logic form is not a tautology and not a contradiction, it is called a contingency. Example 1. Tautology: AviA Contradiction. AaaA Contingency. A->B Notice that if the variable symbols of a tautology are replaced by sentences, the compound sentence is always true. Example2. You have already observed that A v 7 A isa tautology. Thus the sentence: A TA {t is raining or'it is not raining is a true sentence. The truth of the sentence in this example does not depend on any facts from meteorology. It is true by?. Ae 1.7 SENTENTIAL INCONSISTENCY 15 virtue of the way it is built up from its parts by means of the logical operations. In other words, it is true by virtue of its form. Logicians call a sentence like this one a substitutive instance of a tautology. Exercises 1.6 1. Make truth tables for the following logic forms. Indicate which are tautologies, which are contradictions, and which are contingencies. (@) AA (be) A>(B-A) (©) (AvB)>(Aa 10) @ Av(TAAC) (© A>(1A4B) (f) (AaB) (7A v7 B) 1.7 Sentential Inconsistency Let A,, Ap... A, bea collection of logic forms. These logic forms are said to be sententially inconsistent if their conjunction is a contradic- tion. Otherwise, they are said to be sententially consistent. To test a collection of logic forms A,, Az... A, for sentential inconsis- tency, you have only to form their conjunction A, 4 A,A--- AA, make a truth table for this conjunction, and look to see whether the right-hand column of the table has all f’s. If this is so, then they are sententially inconsistent. If there is at least one t, then they are sen- tentially consistent. If, after symbolizing a collection of sentences, you find that the re- sulting collection of logic forms is sententially inconsistent, then you would know that these sentences are built from their elementary sen- tences in such a way that it is impossible for all of them to be true. Exercises 1.7 1. Test the following collection of logic forms for sentential incon- sistency: V(AAB) W(AA7B) 1(7AAB) 1(1A 47 8B)16 SENTENCE COMPOSITION 2. Symbolize the following sentences and test the resulting logic forms for sentential inconsistency. (a) Either a recession will occur or, if unemployment does not de- crease, wage controls will be imposed. If a recession does not oc- cur, unemployment will decrease. If wage controls are imposed, unemployment will not decrease. (b) If imports increase or exports decrease, either tariffs are im- posed or devaluation occurs. Tariffs are imposed when and only when imports increase and devaluation does not occur. If exports decrease, then tariffs are not imposed or imports do not increase. Either devaluation does not occur, or tariffs are imposed and ex- ports decrease. 3. After discovering his immense popularity with the American people, Bagel the beagle decided to run for president. He called to- gether his top political advisors for a brainstorming session. Out of this session came the following advice: Owl: Beagles can’t be president, or the country will go to the dogs. Fox: If a beagle can be president, the country won't go to the dogs. Bear: Either a beagle can be president, or the country will go the dogs. Cat: IW’s not the case that (the country will go to the dogs and a beagle can’t be president). Since Bagel’s confidence in his advisors was a shade less than ab- solute, he decided to run a sentential consistency test. What did it re- veal? 18 Constructing Logic Forms from Truth Tables You know that for each logic form a truth table can be made. In this section you will learn how to reverse the procedure. Here we have a truth table for an unknown logic form with n given variable symbols, The problem will be to construct a logic form having this given table for its truth table. Given the truth table, the following procedure is employed to con- struct the desired logic form. 1. For each row whose right hand entry is t, make a check mark / to the right of that row,¥ 1.8 CONSTRUCTING LOGIC FORMS FROM TRUTH TABLES 7 2. To the right of each check mark V write a sequence of n terms (one corresponding to each variable symbol) as follows: if in that row a variable symbol has the value t entered for it, then the cor- responding term is to be that variable symbol itself; if the variable symbol has the value f entered for it, then the corresponding term is to be the negation of that variable symbol. 3. To the right of each sequence of terms which you made in step 2, write the conjunction of those terms, 4, Beneath the table, form the disjunction of all the conjunctions which you made in step 3. The disjunction formed in step 4 will be the desired answer. Example. Construct a logic form having the following truth table.18 SENTENCE COMPOSITION The result of Step 4 is the desired logic form. To check your work, make the truth table for the logic form just constructed, lalelel (An Ba 1) v(An7 BAC ee Bac) Comparing this table with the table you were given, you can see that they coincide. Hence (AABATC)vV(AATBAC) v¥(TA ATBAG) is a correct answer. Probably you have noticed that this method doesn’t mention what to do in case the right-hand column of the given table only has f’s. This case is even easier; just make a contradiction of the form (X 4 1 X) for each variable symbol X, and then take the disjunction of these contradictions. Exercises 1.8 1. Using the procedure outlined in this section, find a logic form for each of the following truth tables: (a)| al B |[ 27 (b)| A B 22 — tit t t t f tif t t f t fit t f t f fif jf fife1.8 CONSTRUCTING LOGIC FORMS FROM TRUTH TABLES 19 | ‘Check each answer by making the truth table of each logic form con- i structed, 2. Find a logic form with the 3 variable symbols A, B, C, which has the following truth table: *3, The people who live on the banks of the Ooga River always tell the truth or always tell lies, and they respond to questions only with a yes or a no. An explorer comes to a fork in the river, where one branch leads to the top of a mile high waterfall and the other branch leads to a settlement. Of course there is no sign telling which branch leads to the settlement, but there is a native, Mr. Blanco, standing on the *This denotes a difficult problem.20 SENTENCE COMPOSITION shore. What yes-or-no question should the explorer ask Mr. Blanco to determine which branch leads to the settlement? {Hint: Let A stand for “‘Mr. Blanco tells the truth,” and let B stand for “The left-hand branch leads to the settlement.” Construct, by means of a suitable truth table, a logic form involving A and B such that Blanco’s answer to the question will be “tyes” (i.e., true) if and only if Bis true.]a 2 Algebra of Logic 21 Logical Equivalence Let A and B be logic forms. A and B are logically equivalent if and only if the logic form A <> Bis a tautology. If A is logically equivalent to B, it is indicated by writing A = B. Suppose A = B. Then if all the variable symbols appearing in A or B are listed, the assignments of truth values to these symbols which make A true will be precisely those which make B true. Example 1. Prove: (A -> B) = 7 (A 4 7B) ANSWER: To do this, construct the truth table of the logic form (A — B) + 7(A 4 7B) which, for brevity, will be denoted by E. From the truth table you can see that E is a tautology. Hence: A> B27 (Aa7B) Example2. Prove: A > (B-> A) = Cv 7 c ANSWER: Construct the truth table for the logic form [A> (B> A (Cv 10) which is denoted by E. a22, ALGEBRA OF LOGIC By inspecting the truth table for E, you can conclude: A—(B—> A) = (Cv 10) The second example shows that the tautologies A > (B — A) and Cv 1 Care logically equivalent. Actually it is true that all tautologies are logically equivalent, and all contradictions are logically equiva- lent. Exercises 2.1 1. By constructing the appropriate truth table, prove or disprove the following claims: (a) (Av B) =1(1A478B) (bt) (AvB)=7(1Ba70) (c) Aa(BvC) = (AaB) v(Aac) (d) Ca (BvD) = (Cv D)a (BvD) (e:) A>(B>C) = (A> B)+C 2. Construct a logic form distinct from, bat logically equivalent to, the logic form A> (B+ OC). [Hint: Make the truth table for A — (B — C). Then use the proce- dure for constructing a logic form, given its truth table. Check that the logic form so obtained is logically equivalent to A —> (B — C).]2.2 BASIC EQUIVALENCES 23 22 Basic Equivalences Here is a list of twenty basic equivalences which will be used repeatedly throughout this book. You should familiarize yourself with all of the equivalences listed. They can be easily verified by the truth table technique which you used earlier to check for logical equivalency. (In fact, you already verified a couple of them in previous exercises.) The symbol T is used to denote the particular tautology A v 7 A, and the symbol F is used to denote the particular contradiction AAA. Basic Equivalences _ TTAzA law of double negation AvB=BvA commutative laws AnB=Bad Av (BvC) = (AvB)vC An (BAC) = (AABAC associative laws AA (BVO) = (AaB) v(AAC) distributive laws 7 (AvB)=17A407B V(AnB)=7AV1B de Morgan’s laws 1 2. 3 4 3 6. Av(BaC) = (AvB)a(AvC) 7 8 9 0. 1 10. AaAZA . Wl AvVASA idempotent laws 12. Aa (AVB)EA - 13. Av(AaB)=A absorption laws 4, BaAT=B = 15. BvF=B identity laws 16 ByT=T aot 17, BAF=F domination laws 18, A>B=1AVB arrow law 19. A+>B=21B+ 7A law of contraposition 20. A+ B= (A > B) a (B— A) double arrow law274 ALGEBRA OF LOGIC We close this section with a few observations. In Chapter 1 we introduced the concept of “contrapositive” of an implication. Basic equivalence 19 asserts that an implication is logically equivalent to its contrapositive. From your basic algebra course you may be familiar with the commutative, associative, and distributive laws. In contrast to the situation in ordinary algebra, there are two distributive laws here. Note that one of these may be obtained from the other by interchang- ing the a and vsymbols. In ordinary algebra this doesn’t work. If you interchange the + and - symbols in the distributive law a:(b + c) = (a-b) + (a-c) you get a + (b-c) = (a + b)-(@t c) which is false in ordinary algebra. (Note, for example, that it fails when a, b,c, each have the value 1) 23 Algebraic Manipulation In this section you will learn another method for proving that two logic forms are logically equivalent. For this procedure you need the following two rules. 1.Replacement rule. If part of a logic form A is replaced at one or more occurrences by a logically equivalent form, then the result is logically equivalent to the original form A. Il. Transitivity rule. If A, B, and C are logic forms such that A = BandB = C,thenA = C. The technique used to show logical equivalency here resembles the process used in algebra to show that two algebraic expressions are equal. Starting with one of the logic forms and making successive applications of the replacement tule and the basic equivalences of the preceding section you convert it into the other logic form. Then,2.3 ALGEBRAIC MANIPULATION 25 by using the transitivity rule, you can conclude that the two logic forms are logically equivalent. Here are a few examples to show the algebraic manipulation of logic forms. Study these examples carefully before attempting the ex- ercises which follow. Example 1. PROOF: Example 2. ANSWER: Prove: Aa (Bv7A)= AaB Start with the left side and, in a series of steps (listed vertically), manipulate your way to the right side: Aa(By 7A) distributive law (Aa B)v(Aat A) definition of F (AaB)vF identity law AaB Since you went from the left side to the right side in steps which leave each line logically equivalent to the one pre- ceding it, you can conclude by the transitivity rule that the desired equivalence holds. Show that 1(A + B) = An 7B 1(A— B) arrow law 7 (VA VB) de Morgan’s law TTAATB double negation law AaB Since you started with the left side of the equivalence in question and ended with the right side, you can conclude by the transitivity rule that the equivalence holds.2% ALGEBRA OF LOGIC Example 3. ANSWER: Example 4. ANSWER: Simplify {(B v 7 A) 4B] > B [(Bv VA)AB>B commutative law [Ba(BvIA | > B absorption law BoB Write the negation of the following sentence, and then express it in such a way that the negated parts are elementary (not compound) sentences If the survey is accurate, we should propose legisla- tion to Congress and release our findings to the news- papers. LetI be: The survey is accurate. Let Lbe: | Weshould propose legislation to Congress. LetNbe: We should release our findings to the news- Papers. Then you can represent the negation of the given sen- tence symbolically as: afl (LaN)] You can now manipulate this logic form: 3 [l>(WaNn)] arrow law a[alv(LaN)] de Morgan’s law ta1Tata(LaNn) double negation law Tal (LAN) de Morgan’s law Ia(1Lv¥4N) Hence the negation of the given sentence, can be written: The survey is accurate and either we should not propose legislation to Congress or we should not release our findings to the newspapers. ¥2.3 ALGEBRAIC MANIPULATION 27 Exercises 2.3 1, Establish the following equivalences using algebraic manipulations. (a) AvB=1A>B (b) 1(A>B)=AA1B (©) A>(B>O = (AaB)>C @ (AaB) v(1AA0) = (A— B)a [C v(A 4 B)] 2. Simplify the following expressions. (Try to minimize the total number of occurrences of operation symbols and variable symbols. Answers won’t be unique.) (a) TAv(AvB) (b) 12(7 BWA) (c) TAA (AvB) (d) (AaB) v(A 7B) (e) 1(A 417 (A vB)) (f) Aa(A v BvC) (8) (TBVA)sA] +A (h) (A v B)a [(B vv A)AC] (i) (Av 1 (Bac) (ij) Aa(TA VB) (k) Av[TAv(Barc) (1) (7A 47B)v 1 (A vB] ~(7A 4 7B) (m) [Aa (aC) v[1A a(Ba CO} (n) EaDa[1((A>B)*+(1B>1A)>C) 3. Negate each of the following sentences, and then express the an- swer in such a way that only elementary (not compound) parts of the sentence are negated. (a) Freedom of the press is an important safeguard of liberty, and in protecting it, our courts have played a major role. (b) If a politician seeks the presidency, and he has sufficient fi- nancial backing, then he can afford to appear on nationwide televi- sion frequently. (c) A man has self respect if he is contributing to a better society. (d) We can halt pollution only if we act now. (c) Ifa man cannot join the union, he cannot find a job in that factory and he must relocate his family. (f) Ifa worker can share on the company profits, he works harder and he demands fewer fringe benefits.28 ALGEBRA OF LOGIC 4. IfA4 B = AA C,can you conclude that B = C? 5. Show that you can manipulate from one side of the absorption law to the other side, using only the remaining 18 basic equivalences. 6. The Internal Revenue Service lists the following three rules as guidelines for filing tax returns: (a) A person pays taxes only if he is over 18 years of age, or has earned $1000 during the past twelve months, or both. (b) No widow must pay taxes unless she has earned $1000 during the past twelve months. (c) Anyone over 18 years of age who has not earned $1000 during the past twelve months does not pay any taxes. Find a simpler form for these rules. [Hint: Let x be an arbitrary person. Let Tdenote: x is a taxpayer. Let W denote: x is a widow. Let A denote: x is over 18 years of age. Let Edenote: x earned over $1000 in the past twelve months. Then the guidelines given can be represented symbolically by: [T+ (A vB a[VE> 1(WaT)A[(A a 1B) 47] Simplify this logic form.] *7, In the Tooba tribe, the elders use the following rules to decide a man’s role in the tribal society. Try to replace this set of rules by a simpler (but logically equivalent) set of rules. (a) The warriors shall be chosen from among the hunters. (b) Any Tooba man who is both a farmer and a hunter should also be a warrior. (c) No farmer shall be a warrior. (Hint: Let x be an arbitrary Tooba man. Let W denote: x is a warrior. Let Fdenote: x is a farmer Let Hdenote: x isa hunter.] *This denotes a difficult problem.24 CONJUNCTIVE NORMAL FORM 29 2.4 Conjunctive Normal Form Logic form A is a conjunctive normal form if it satisfies one of the fol- lowing conditions: i) Aisa variable symbol. ii) A is the negation of a variable symbol. iii) A is a disjunction of two or more terms, each of which is either a variable symbol or the negation of a variable symbol. iv) A is a conjunction of two or more terms, each of which is one of the three types listed above. It is very important to be able to recognize a conjunctive normal form. Example 1. The following logic forms are conjunctive forms: A (satisfies condition i) 1B (satisfies condition ii) TCvBvA (satisfies condition iii) (TC vBvA)a AaB (satisfies condition iv) (7A vB) a (Cv A) a (B vC) (satisfies condition iv) The following logic forms are not conjunctive normal forms: A>B (Aa B)v 1c (A vB) a(4B—> A) 1 (A AB) To help fix the idea in your mind, think of a conjunctive normal form as a logic form which looks like (AvBv---)a(CvDv---) a vee a (EVE ves) where the heavy-type letters denote logic forms no more complicated than single variable symbols or negations of variable symbols. We are allowing as special cases of this, the case where only one of the bracketed expressions actually appears, and the case where some of the bracketed expressions have only one term. The bracketed expres- sions between the conjunction symbols are called the conjuncts ofeee 30 ALGEBRA OF LOGIC the normal form. If the conjunctive normal form has no conjunction symbols, the entire expression is thought of as a single conjunct. Thus, AvBv1C has only one conjunct, namely the expression AvBvic. Exercises 2.4 1. Determine which (if any) of the following logic forms are conjunc- tive normal forms. (a) (AvBv 7 B)a(AvC) (b) (AvBv 1B) A(AaC) (c) (A> B)v(Ca 1B) (d) AaB () TAaB (f) 3AlAvBya(Avoj (g) WAABATC (h) Aa[{Bv(Ca 1 D)] (i) (Aa B)v[(A aC) v (Aa 1B)] 2.5 Reduction to Conjunctive Normal Form By using algebraic manipulations it is possible to reduce any logic 7 form to an equivalent conjunctive normal form, L Example. Find a conjunctive normal form logically equivalent to: t (AB) v(Ba 7 C) ANSWER: (Aa B)v(Ba 10) distributive law {(A 4 B) v BJ (Aa B) v7 C) distributive law (A vB) a(B v By} a ((A 4B) v 1] distributive law (A vB) A(Bv By] al(Av 7 C)a(Bv 70) associative law (A vB) a(B vB) a(Aa 1 C) A(BY 10)2.5 REDUCTION TO CONJUNCTIVE NORMAL FORM 31 The last line is, as desired, a conjunctive normal form. Itis not the simplest answer, but for the intended ap- plications of conjunctive normal form, this will not matter. Note that a logic form might be manipulated into a conjunctive normal form in various ways, and the answer might come out in various ways. All answers, of course, would be logically equivalent. Now it turns out that in reducing to a conjunctive normal form you need to use just one of the two distributive laws learned in Section 2.2. If you now switch to an “arithmetical notation” and write A + Binstead of Aa B ABinstead of A v B then you see that of the two distributive laws, the one you need ap- pears in the new notation as A(B + C) = AB + AC. The other distributive law would look rather strange and unfamiliar in arithmetical notation. It would appear as A + (BC) = (A + BXA + ©). You are probably so accustomed to working with ordinary numbers where this second distributive law fails, that we might have confused you if we had introduced and used arithematical notation earlier in the book. Fortunately, for reduction to conjunctive normal form you do not need to make use of this “funny looking” distributive law. So perhaps in reducing to conjunctive normal form, it might be more con- venient to use arithmetical notation. For one thing, your expressions will take up less space. For another, repeated application of the dis- tributive law to complicated expressions can be handled just as though you were “multiplying out” an expression of ordinary algebra. A further space saving device would be to write A’ instead of 7A.eT 32 ALGEBRA OF LOGIC De Morgan’s laws would then appear as (A + BY = A'B’ (AB) = A’ + B’ Of course, for uncomplicated expressions you may prefer not to use the new arithmetical notation at all. It is entirely optional. A good way to reduce to a conjunctive normal form is to perform the following four steps: 1. Use the arrow laws to remove all—+ and<+. 2, Use de Morgan’s laws repeatedly until the only negated terms are variable symbols. 3. Switch to arithmetical notation. 4. Multiply out (as in ordinary algebra). Naturally, if you get a chance to simplify things along the way by using the absorption, idempotent, domination, or identity laws, so much the better. Example, Find a conjunctive normal form logically equivalent to: (A > B)~ C)v (Dak ANSWER: ((A > B)—> C] v[Da E] arrow law (QA vB)>C)v([DaE} arrow law [1 (A vB)vC)v[Da E) de Morgan’s law ((7 7A 4 7B)vC)v[Da E] double negation law (A a 1B) vC)v(DaE) change notation to arithmetical (A + B’)C(D + E) associative and commutative laws C(A + BD + BE) multiply out (distributive law) CAD + CB’D + CAE + CB'E The last line is the desired conjunctive normal form. A good way to remember that it is the “and” symbol 4 which cor- Si «or myrna Public Librarya a 2.6 USES OF CONJUNCTIVE NORMAL FORM 33 responds to the symbol + when reducing to a conjunctive normal form, is to think of the word CAP, which is made from the first letters of the words Conjunctive (normal form) And Plus. Exercises 2.5 1. Reduce each of the following logic forms to a conjunctive normal form: (@@) TA>B (b) (1 ByvA) (c) (A*B)v (Aa 7B) (dé) 1(A47 (A vB)) («) A+B (f) Aa(Bv(C 47D) (g) (A B)alCv (Aa B) (h) (A AB) v[(A aC) v(A 47 B)] 2.6 Uses of Conjunctive Normal Form Ifa logic form A is a conjunctive normal form, there is a way of tell- ing at a glance whether or not it is a tautology. Just apply the follow- ing rule: A conjunctive normal form is a tautology if and only if in each conjunct there appears some variable symbol and its negation. In applying the above rule, do not forget that if no conjunction symbols actually appear in the conjunctive normal form, the entire normal form is thought of as a single conjunct. Examplel. (A vBv 1A) a(CvDvEv 71 D)isa tautology be- cause of the appearance of A, 7 A in the left conjunct and D, 1 Din the right conjunct. (AvBv 71A)a(C v1 By D)a (Ev 7) is not a tautology because the middle conjunct fails to have some variable symbol and its negation.a 34 ALGEBRA OF LOGIC Av By Dv 7B is a tautology because of the ap- pearance of B, 1 B. A vB v 1 Cis not a tautology. Its only conjunct (the whole expression itself) fails to have some variable symbol and its negation. Here is how to test any logic form A for tautology (regardless of whether A is a conjunctive normal form or not). First reduce A to a conjunctive normal form. Then you can see at a glance whether the normal form (and hence A) is a tautology. Example 2. _ Is the following logic forma tautology? A> (B— A) ANSWER: Reduce to a conjunctive normal form A (B—> A) = 7Av(B— A) = TAv(1BVvA) BIAVIBVA Now 1 Av 7B vA is a conjunctive normal form, and it is evident by inspection that it is a tautology. Consequently, so is A > (B — A). Example 3. _ Is the following logic form a tautology? (A> B)>A ANSWER: Reduce to a conjunctive normal form (A+ B)+ A= 1(1AVB)VA S(VIAATB VA = (17 AVA) A(1BVWA) = (AvA)A(7 BVA) = Aa(1BYA) Now A 4( 1B v A) is a conjunctive normal form. By inspection it is evident that it is not a tautology, so neither is(A — B) > A.et ee eee ete Pt lls ft 2.7 DISJUNCTIVE NORMAL FORM 35 In both examples a truth table could have been used just as easily to settle the question. For expressions with three or more distinct letters, making a table can be tedious, and the method of conjunctive normal forms is preferable. Using a conjunctive normal form to test for tautologies also gives additional information. If the test shows that a logic form is not a tautology, the conjunctive normal form helps to find an assignment of truth values to the variable symbols, which makes the original logic form have truth value f. All that has to be done is to locate a conjunct which fails to have both a variable symbol and its negation. Then assign values to the variables so as to make that conjunct false. Exercises 2.6 1. Test the following to see if they are tautologies using the method of conjunctive normal form. For each logic form which is not a tau- tology, use the conjunctive normal form to find an assignment of truth values to the variables which makes the logic form false. (a) [Aa(A— B+ B (bt) AvIA (c) A—(AvB) (d) (A> B)aTA)>B (©) [1(A— By > (A vB) (ff) [AvB]>A (g) (A B)v (Ca B) (h) (Aa B)v((D—C)vE) (i) (As B)a(C vD)— Al 2.7 Disjunctive Normal Form A logic form A is a disjunctive normal form if its satisfies one of the following conditions: i) Aisa variable symbol. ii) A is the negation of a variable symbol. iii) A is a conjunction of two or more terms each of which is a variable symbol or the negation of a variable symbol. iv) A is a disjunction of two or more terms each of which is one of the three types described above.td eee) eet ft debehd 36 ALGEBRA OF LOGIC Example I. The following logic forms are disjunctive normal forms: A TByC AaABaICaD (TBaAC)vAaD)vIE The following logic forms are not disjunctive nor- mal forms: A>B (IBYC)AA (AC) v(A — B) Note that some logic forms, for example the form 7 A, can be both a conjunctive normal form and a disjunctive normal form. A disjunctive normal form looks just like a conjunctive normal form except that the roles of the symbols a and v are reversed. Thus (Av7B)aD is a conjunctive form, while (Aa 1B)vD is a disjunctive normal form. Every logic form A can be reduced to a logic form which is a dis- junctive normal form logically equivalent to A. Example 2. ANSWER: Find a disjunctive normal form which is logically equiv- alent to: (A> B)>C (A> B)>C arrow law V(A> B)vCc arrow law VV AVB)vC de Morgan’s law (Aa TB)vC The last line is, as desired, a disjunctive normal form.¥ 2.7 DISJUNCTIVE NORMAL FORM 37 Example 3. Find a disjunctive normal form which is logically equiv- alent to: Axa (BvC) ANSWER: AA (BYC) = (AaB) v(AAC) The right-hand side is the answer. Now it turns out that in reducing to disjunctive normal form you need to use only one of the two distributive laws. In fact, it’s the one you did not need for reducing to conjunctive normal form. Recall that in switching to arithmetical notation this distributive law looked un- familiar. You can avoid dealing with a “funny looking” representa- tion of this distributive law by reversing the role of the + symbol. This time write A+B for AvB AB for AaB Again the distributive law that you do need is A(B + C) = AB + AC. Any logic form can be reduced to a disjunctive normal form by the following steps: 1, Eliminate arrows. 2. Repeat the use of de Morgan’s laws until negation symbols appear only in front of variable symbols. 3. Switch to arithmetical notation. 4, Multiply out (like in ordinary algebra). In order to help you remember that it is the “tor symbol which should correspond to + in reducing to a disjunctive normal form, think of the word DOPE whose first three letters come from Disjunctive (normal form) Or Plus. Recall that for conjunctive normal form the key word was CAP. Of course, if the logic form in question isn’t very complicated, you may prefer not to use arithmetical notation.38 ALGEBRA OF LOGIC Example 4. Find a disjunctive normal form logically equivalent to @) ©) ) (g) (a) ©) () @) qi) Gi) (k) VA AB) A(A + C) Ac ANSWER: VA A B)A(A+)AaC arrow law A AB)A(TAVO)AC de Morgan’s law (TAvVITBya(TAVOac change notation to arithmetical (A’ + BA’ + CC multiply out (distributive law) AVA'C + BYA'C + A'CC + BICC. The last line is a disjunctive normal form. Exercises 2.7 1, Determine which (if any) of the following logic forms are disjunc- tive normal forms. AAB (b+) AvB Aa(BvC) @) AvBac AviCv(Aac) (@f) (A B)v IC 7 (A vB) (ht) TAATB 2. Reduce each of the following forms to a logic form which is a dis- junctive normal form. A>B (bt) AvB 7 (AvB) () (A+B) AABAC (f) (AvB),B>+O [1@+O)]-+A (hy) 1[(B>O) >A) (A vB) 4 ((Bv A) 4C] Aa((1A— B)vC] (A> B)> [(B>C)> (A> CO) 2.8 Uses of Disjunctive Normal Form If a logic form is a disjunctive normal form, there is a way of telling by inspection whether or not it is a contradiction. Just apply the fol- lowing rule:ME 2.8 USES OF DISJUNCTIVE NORMAL FORM 39 A disjunctive normal form is a contradiction if and only if in each disjunct there appears some variable symbol and its negation. Example 1. D «1 Disacontradiction. (A 4B) v (A 4 C)is not a contradiction. Bis not a contradiction. (A 47 A) v(A a C)is not a contradiction. (A a 7A 4 B)isa contradiction. (A 417A) v(BaC a 1 B)isa contradiction. To test an arbitrary logic form to see if it is a contradiction, reduce it to a disjunctive normal form, and then check the normal form by in- spection. Example 2. Use reduction to a disjunctive normal form to tell whether the following logic form is a contradiction. (A > 1B)a (A AB) ANSWER: (A > 1B)a(AaB)=(TAVI B) a(A 4B) = (1A4AAB)v(1BAA 4B) Each disjunct has some letter and its negation. Therefore, the origi- nal logic form is a contradiction. Even if reduction to a disjunctive normal form reveals that a logic form A is not a contradiction, some useful knowledge can be obtained. You can use the disjunctive normal form to determine an assignment of truth values to the variable symbols in A which gives A truth value t. All you have to do is locate a disjunct which fails to have a variable symbol and its negation. Then assign values to the variables so as to make that disjunct true. Exercises 2.8 1. Reduce each of the following logic forms to a disjunctive normal form and determine whether it is a contradiction. If it is not a contra- diction, use the disjunctive normal form to find an assignment of4 ALGEBRA OF LOGIC truth values to the variable symbols which makes the original logic form true. (a) A>(TAAB) (b) A>(VAvB) (c) (AvB)ara(7A>B) (@) (AAV) a(TA>(1BA70) 2. Use reduction to a conjunctive normal form and to a disjunctive normal form to determine which of the following logic forms are tau- tologies, which are contradictions, and which are contingencies. (a) TAv(B>7 C)v(C>A) (b) (A B) > C] + [(C > A) > (D> A)] (c) (A> B)>[(B>OQ-> (A>) @ [(AaC)vBarOl=[4 Aa v(1B4 170) 3. Check the following set of assumptions for sentential consistency. If the XYZ company builds a new factory or some of its machinery must be replaced, either the company can obtain a loan or it will be threatened with bankruptcy. The company can obtain a loan if and only if it builds a new factory and no machinery must be replaced. If machinery must be replaced, then the company cannot obtain a loan or it does not build a new factory. Either the company will be threatened with bankruptcy, or some of its machiner must be re- placed and the company can obtain a loan. [Hint; Symbolize the sentences, take the conjunction and reduce to a disjunctive normal form. See if it is a contradiction.] 2.9 Interdependence of the Basic Logical Operations Previously you were introduced to the five basic logical operations: tya<>SS SSS 2.9 INTERPENDENCE OF LOGICAL OPERATIONS 41 The double arrow law mentioned earlier in this chapter shows how to express the operation +> in terms of the operations —> and a: A+ B= (A— B)a(B—> A) It follows that any logic form with occurrences of +> can be con- verted to a logic form having no occurrences of «> by replacing the left side of the above equivalence with the right side. This shows that you can get along with just the remaining four logical operations. Furthermore, the arrow law and de Morgan’s law can be used to ex- press — and ain terms of vand7: A~>B=7 AvB AnB=7(1(AaB)] = 1(7 Av 7B) Hence, given any logic form A, you can eliminate all occurrences of», —>, anda in favor of vand 7 , and the new logic form would be logically equivalency to A. The above discussion shows that of the five basic operations avail- able, it is possible to get along with just two of them, namely v and 7. Example. Find a logic form logically equivalent to the one below, but which uses only the connectives vand 1: ANSWER: A+B = (A B)a(B— A) = (7A vB)a(1BvA) = (7A vB)a TB) v((7A vB) aA} = (7A 7B) v(Ba 7B) v((7 AAA) v(Ba AD] = (1A4 7B)v(BAA) = 1(AvB)v 1(7 Av 7B). The example above shows one reason why we did not merely in- troduce the two logical operations v and 7 at the beginning of the book and do all subsequent work using just these two operations. Many short logic forms, for example A ++ B, would be expressed by long unwieldy ones. Thus, even though it is possible to manage in principle with just two operations, it is convenient to have all five of them available.Ne 42 ALGEBRA OF LOGIC ‘There is a new logical operation in terms of which each of the five ‘basic operations can be expressed. It is called the Sheffer stroke, and it is denoted by a vertical stoke | . Its truth table is: TRUTH TABLE FOR | (SHEFFER STROKE) [a [5 [ais | Since the truth table of A|B is the same as the truth table of a (Aa B), we have ALB =7(Aa B). ‘You have already seen that any logic form can be expressed using only the operations v and 1. Thus, to conclude that all the basic logi- cal operations can be expressed in terms of the Sheffer stroke alone, you need only show that v and 1 can each be expressed in terms of | . You can see that 1 A may be so expressed by observing that: IA = V(AAA)FAIA That A v B can be expressed in terms of the Sheffer stroke follows from: AvB= 1[1(A vB)} BV(TA4A7B) = 1 (ALA) 4 (BIB) = (al a)| (BIB) ‘The conclusion to be drawn from this section is that every logic form can be expressed by an equivalent one whose sole operation symbol is the Sheffer stroke. Our interest in this result is only theoreti- cal, not practical.2.9 INTERPENDENCE OF LOGICAL OPERATIONS 43 Exercises 2.9 1. For each logic form below, find one logically equivalent to it, but which uses only the operations v, 1. (a) (A> B) + ClaA (b) (AaB) v(B> 10) (c) [Av(CaD)] > B 2. Show that v, —>, and +> can cach be expressed in terms of aand 1. 3. Find a logic form equivalent to the one below, but which uses only aand 7. (A> B)vCc 4. Express each of the basic logical operations v, a, and «> in terms of 7 and. 5. Find a logic form equivalent to the one below but which uses only 1 and—. Aa(BvC) 6. For each logic form below, find one logically equivalent to it, but which uses only the Sheffer stroke. (a) AaB (b+) A>B («c)AvaB (dd) 1B>+A *7. Show that it is not always possible to express a logic form by means ofa logically equivalent one which uses only the logical opera- tions—, v. (Hint: Show that you cannot build any contradictions using only the operations — and v.] *This denotes a difficult problem.3 Analysis of Inferences 3.1 Sentential Validity You have probably met the following types of argument before. The first example constitutes good reasoning, while the second one does not. Example 1. _ If grass is green, snow is white. Grass is green. Therefore, snow is white. Example 2. If x and y are even numbers, x + y is even. x + yiseven. x and y are even numbers. Each of these examples is called an inference or an instance of an in- ference pattern. An inference pattern is a finite list of logic forms pre- sented as follows: The logic forms above the bar are called premises while B is called the conclusion. (The symbol .. is read “‘therefore.”) An inference pattern is sententially valid if and only if (conjunction of the premises) —> conclusion is a tautology. An inference is called sententially valid if its inference . pattern is sententially valid. 45le 46 ANALYSIS OF INFERENCES Example 3. Consider the inference: If grass is green, snow is white. Grass is green. Therefore, snow is white. To check it for sentential validity, first symbolize. G: Grass is green S: Snow is white. The inference pattern is i G>s G i oS Since (G +S) aG]—>s ; is a tautology (verify that yourself), the inference is sententially valid. The sentential validity of an inference depends solely on the way in which the premises and conclusion are built from their basic sentences by means of the logical operations. You should convince yourself that if you substitute sentences for the variable symbols in a sen- tentially valid inference pattern, and if by doing so you get premises ! which are true statements, then the conclusion will also be a true 1 statement. Thus an inference which is sententially valid constitutes : good reasoning. Example 4. You observed above that A>B A B is a sententially valid inference pattern. An inference which is an instance of this pattern is:3.1 SENTENTIAL VALIDITY 47 If cars sing, dogs whistle. Cars sing. Therefore, dogs whi: le. This inference, then, is a sententially valid inference. The preceding example vividly demonstrates that it is only the form of the inference that determines whether or not it is valid. The fact that the premises and the conclusion are unrealistic has no bearing on the matter. Study the following important example. Example 5. All countries have armies. France is a country. Therefore, France has an army. Let Abe: All countries have armies. Let B be: France is a country. LetC be: France has an army. The inference pattern corresponding to the above in- ference is: A BL ra It is easy to see that the logic form (Aa B)>C is not a tautology. Thus the inference is not sententially valid. On the other hand, any reasonable person would probably agree that the inference’s conclusion really does follow from its premises. The reason that a sentential validity test doesn’t help to recognize that this inference constitutes correct reasoning is that its correctness is somehow related to the way in which the premises and conclusion are built from their re-48 ANALYSIS OF INFERENCES spective subjects and predicates. B and C have the same subject while A and C have the same predicate. Our symbolic resources are not adequate for the job of revealing this. Logic forms display only the way in which compound sentences are built from their basic elementary sentences; they do not display the subject- predicate structure of the elementary sentences them- selves. The problem of how to recognize the correct- ness of such inferences involves an area of logic known as “quantification theory,” which is beyond the scope of this book and will not be pursued. Remember: Inferences which are sententially valid constitute good reasoning. Inferences which are not sententially valid might represent good reasoning nevertheless. Exercises 3.1 1, Test the following inference patterns for sentential validity. (@) AvB (+) A+B @ A+B BvCc C+A IBS+1C “A .C>B “BV IC (@) AvB @ 4A (f) A+(B>C) IBvC¢ 7 (AaB) PBA AVC A () ID+1B (h) 1BvVQ+7B ac D-1C D-+A BA BvC “A> ID oA 2. Determine which of the following inferences are sententially valid. (a) If the legislature meets today, the executive committee met yesterday. The executive committee met yesterday. Therefore, the legislature meets today.3.2 BASIC INFERENCES 49 (b) If wages are raised, inflation continues. If there is a depression, wages cannot be raised. Therefore, if there is a depression, inflation cannot continue. (©) If this child is challenged, then he will enjoy learning. If he is not challenged, this child will be bored with school. This child does not enjoy learning. Therefore, he is bored with school. (q) If other countries develop new weapons, we feel that our na- tional security is threatened. If we do not feel that our national security is threatened, then we will spend more money on social reform programs. Therefore, if other countries develop new weapons, then we will not spend more money on social reform programs. (©) If the Department of Agriculture is correct, corn blight does not occur if the crop is sprayed weekly. Corn blight does occur. Therefore, if the corn is sprayed weekly, the Department of Agri- culture is wrong. (f) Unless protective tariffs are imposed, our balance of payments will be unfavorable. If our balance of payments is unfavorable, the foreign aid appropriations will be cut. Therefore, if protective tariffs are imposed, foreign aid appropria- tions will not be cut. 3. Give an example of an inference which is not sententially valid, but which has a true conclusion. 4, Give an example of an inference which is sententially valid, but which has a false conclusion. 5. Give an example of an inference which is sententially valid and which has false premises and a false conclusion. 3.2 Basic Inferences Here is a list of three basic inference patterns and their names. Each of these can be shown to be sententially valid by the method introducedS® ANALYSIS OF INFERENCES in the preceding section. These three inferences will be so essential in later work that you are urged to memorize them. LA AB detachment 0B ILA>B B>C hypothetical syllogism ASC IW. A+C B-+C case inference =(AvB)—>C Exercises 3.2 1. Verify that the three inference patterns just given are sententially valid, 33 Checking Sentential Validity of Inferences by Repeated Use of Previously Proven Inferences The method introduced earlier for checking the sentential validity of an inference has the advantage of being conclusive in that it ulti- mately leads to an answer. Unfortunately, it sometimes leads to in- volved symbolic manipulations. The technique described now seems closer to the natural reasoning process and is often shorter. However, this new method is recommended only if you already suspect that the inference in question is sententially valid. In the new technique, inferences that have already been shown to be sententially valid (in particular those introduced in the preceding section) are used to prove that the given inference is sententially valid. The method is based on the following rule: An inference is sententially valid if the conclusion ap- Pears as the last line in a vertical list of logic forms,3.3 CHECKING SENTENTIAL VALIDITY 51 each of which satisfies one of the following four condi- tions: 1. itis a premise, 2. itis a tautology, 3. it is logically equivalent to a logic form preceding it in the list, 4. it follows from logic forms preceding it in the list by virtue of a previously proven inference. Example 1. Verify: A— B 1B . ITA DEMONSTRATION: (1) A>B__ premise (2) 1B— 7A. equivalent to (1) by the law of the contrapositive @G) 1B premise (4) VA Detachment; 3,2. Example2. Verify: A—>B c—-D AvC “.ByD DEMONSTRATION: (i) A+B Q) B— (BvD) @) A> (BvD) (4) C+D (Ss) D- (BvD) (6) C—> (BvD) premise tautology Hypothetical Syllogism; 1,2 premise tautology Hypothetical Syllogism; 4,5 (1) (Av C)— (B v D) Case Inference; 3,6 (8) AvC (9) ByD premise Detachment; 8,752 ANALYSIS OF INFERENCES A chain of inferences like the one in the preceding example is called a deduction of the conclusion from the premises. Such deductions resemble mathematical proofs (for example, the proofs of Greek geometry). This is not to say, however, that all proofs in geometry are such simple deductions. Analysis of the reasoning used in ge- ometry has shown that many of the inferences used there depend not only on the way in which the premises and conclusions are built from their elementary sentences by means of the logical operations, but also on the internal (subject—predicate) structure of the elementary sentences as well. The ancient Greeks did not carry the analysis of these inferences far enough; the logical analysis of the Greeks was inadequate for making fully explicit the reasoning used in their own mathematics. Exercises 3.3 1. Verify that the following inferences are valid by giving a deduction from the premises to the conclusion. (The list of basic equivalences in section 2.2 should be very helpful.) @_ A (b) A> B BoA 1C> 1B c—D “A-~-D )A>B (d) (A > B) v(A> C) Cc> 1B A Cc “BvC “ A (@) A>B (ff) BoA AvB D-C “B BvD AVC () 1A>B+10) aAv1D 1TE>B D 7~E4 Switching Circuits 41 Representing Switching Circuits By Logic Forms In this chapter the relationship between the design of switching cir- cuits and the algebra of logic forms will be investigated. First you will see how to represent a switching circuit by means of a logic form. This is done by making use of some basic properties of electric circuits and switches. To each switching circuit you will have to associate a circuit diagram. Examples of such diagrams are: ® — ioe ae The symbol “6 ” represents a terminal of the circuit, while the symbol ** ” represents a switch in the circuit. 53eee 54 SWITCHING CIRCUITS You know that for current to flow from one terminal to the other, there must be an unbroken path connecting the terminals. A path is unbroken if and only if all the switches occurring along it are closed. Using this fact, you can assign to each circuit a logic form which re- flects the structure of the circuit, The following examples demonstrate this. Example 1. Consider the circuit si“ Switches joined together in this way are said to be con- nected in series. Assign the logic form A « B to this circuit because current flows if and only if both switches A and B are closed. Example 2. The following two switches are said to be connected in parallel. Jt if B Assign the logic form A v B to this circuit because cur- rent flows if and only if A is closed or B is closed.4.1 REPRESENTING SWITCHING CIRCUITS 55 Example 3. The circuit aaa is an example of a series-parallel combination. Its logic form is A. (B vC) because current flows if and only if A isclosed, and Bor Cis closed. In some circuits, one handle operates several switches simultaneously. Whenever one handle closes or opens several switches together, these switches are labeled with the same letter. Example 4. In the circuit ~[ oh both switches labeled A act in concert and are operated by the same handle. Its associated logic form is A a(A vB). This circuit has three switches, but only two control handles, an A-handle and a B-handle.56 SWITCHING CIRCUITS If one handle simultaneously opens one switch while closing an- other, it is indicated by labeling the one switch by a letter and the other by the negation of that letter. Example 5. In the circuit aA is A the two switches labeled A act in concert but in op- position to the switch labeled 7 A. All three are con- trolled by one common handle. This circuit therefore, has four switches and two control handles, an A- handle and a B-handle. Its logic form is AaBa(VAvaA). The following table summarizes the procedure used to determine the logic form which represents a switching circuit. Diagram Representation Aor B must be closed for current to flow4.1 REPRESENTING SWITCHING CIRCUITS 57 Exercises 4.1 1, Write the logic form associated with each of the following switch- ing circuits. is | aoeg ee. AC A ® Fale ca iM58 SWITCHING CIRCUITS ob 2. Draw the circuit associated with each of the following logic forms: (a) AA[(Aa B)vBv(7A 47 B)} (b) (Aa B)v {(C vA) 4 1B] (c) Av(BaTA)v¥(CA1BaA) VIC (@) Ea[FvGvAja(Fv(1Ga 1B) 42 Simplifying Switching Circuits Consider the following switching circuits: oe For a given setting of the handles, current flows in the first circuit if and only if it flows in the second circuit. The first one, however, has fewer switches. Thus, the first circuit may be called a simplification of4.2 SIMPLIFYING SWITCHING CIRCUITS 59 the second. Actually there is a very practical reason for wanting to simplify a switching circuit; the smaller the number of switches in a circuit, the lower the cost of manufacturing it. Imagine how much money the telephone company could save if it eliminated just one switch from each bank of switches in the phone system! In Chapter 2 you learned how to simplify a logic form by algebraic manipulations. Now you can use the skills you developed there to simplify switching circuits by doing the following: 1. Determine the logic form associated with the circuit. 2. Use algebraic manipulations to simplify the logic form. 3, Determine the switching circuit associated with the simplified logic form. Example. —_ Simplify the following switching circuit and sketch the simplified circuit. ‘A 4a 2 a) B Cc c ANSWER: The logic form associated with this circuit is: (A vB) a (VA vO) 4 (B vO). Now simplify this logic form: (A VB) a(TAvO)a(BvC) commutative law (A vB) a(BvC)a(1AvC) commutative law (BV A)a (BvC)a(1AvC) identity law (BVA) a(BvOC)a(1AvOja(tA vA) distributive law [Bv(AaC)]a[TAv(AaC)] distributive law (BA 7 A) v(AaC) The switching circuit associated with the logic form@ =SWITCHING CIRCUITS (Ba 7 A) v(Aa Cis: a : A ay This circuit is a simplification of the circuit with which you started. Exercises 4.2 1. Simplify the following circuits. © K4.2 SIMPLIFYING SWITCHING CIRCUITS 61 © B co (d) IB B B om ee ce : A TB (f) ay Ba gactheee 62 SWITCHING CIRCUITS A (g) 7 AB Pea | ic A c Ac AB i—“ 1 43 Limitations of the Logic Form Method Of Simplifying Switching Circuits i In the last section logic forms were used to simplify certain circuits. There are two main drawbacks to this method. First, there is not yet a “nice” practical way to determine if a switching circuit is simplified as much as possible. In fact, this Problem is still being investigated by Tesearch mathematicians. Also, this method does not take into ac- count circuits which are not “series-parallel” circuits. Example. The following is a diagram of a “bridge” circuit.4.4 DESIGNING A SWITCHING CIRCUIT 63 A ac The circuits which correspond to logic forms are “series-parallel” circuits, not “bridge” circuits. Thus, our method would never lead us to a circuit like this. Consequently, if this were the simplest circuit for a given situation, our method would fail to reveal that fact. Exercises 4.3 1. Find a “series-parallel” circuit which behaves like the following “bridge” circuit. qE 44 Designing a Switching Circuit Starting With a Table Which Describes Its Behavior By examining the diagram of any switching circuit, you can -im- mediately determine whether current flows for any given setting of the64 SWITCHING CIRCUITS switches. Then you can compile a table that shows what the circuit will do for each setting of the switches. Example. Display a table describing the behavior of the following switching circuit for cach possible setting of its switches. ae 7 ANSWER: The table should appear as follows: Now suppose you are given a table like the one constructed in the preceding example. It may seem surprising, but by using techniques developed earlier, you can actually design a switching circuit whose behavior is prescribed by the given table! First think of the table as a truth table (with “on” playing the role of the truth value t). Then con- struct the logic form which has this table for its truth table (You learned how to do this in Section 1.8.) After that, construct the cir- cuit which corresponds to this logic form. This will be the desired cir- cuit,ee) eee 4.4 DESIGNING A SWITCHING CIRCUIT 65 Example 1. Design a switching circuit whose behavior is described by the following table, and sketch this circuit. ANSWER: 1. Restrict your attention to the rows with checks: row 1 and row 4. 2. The sequence of terms corresponding to row | is A,B, and the resulting conjunction is AAB. The sequence of terms corresponding to row 4 is 1 A,7B, and the resulting conjunction is TAATA. 3. The disjunction you are seeking is (Aa B)v(7A 4 78B) and the diagram of the corresponding switching cir- cuit is aoe K46 SWITCHING CIRCUITS The method just outlined will always lead to a switching circuit with the desired behavior. However, the circuit obtained by this method may not be the simplest circuit with this behavior. Example 2. ANSWER: Design and simplify a circuit whose behavior is de- scribed by the table: The method just learned shows that the table describes the behavior of the switching circuit corresponding to the logic form: (A 4B) v¥(7A 4B) Now this can be simplified. (AaB) v(TAAB) distributive law (Av TA)aB identity law B Hence the table also describes the behavior of the very simple circuit: a44 DESIGNING A SWITCHING CIRCUIT 67 Exercises 4.4 1. Design and simplify a circuit whose behavior is described by the following table: CIRCUIT — off off off on off off off 2. Construct a circuit to control a light switch from three different locations. [Hint: Make a table to describe the behavior of the circuit. From the table, construct the logic form and then the circuit.] 3. The five members of the Pookaville city countil are meeting to vote ona new tax bill, Each man votes in secret by flipping a switch. Design acircuit so that a light will come on if and only if a majority of the council votes ‘tyes’ for the bill. [Hint: Make a table.] 4, A certain king’s five advisors must decide whether to ratify a pro- posed treaty with the United States. It takes a majority vote of the ad- visors to ratify the treaty, except that the advisor who is prime minister has a veto (i.e., the treaty is ratified only if he votes for it). Design a circuit so that each advisor can vote for ratification by throwing a switch, and a bell rings if and only if the treaty is ratified. [Hint: Make a table.}SSS See 5 Set Theory 5.1 Elementary Set Theory The idea of a set is the foundation upon which most of modern mathe- matics is built. It is so fundamental that we will not even try to de- fine it. Synonyms like “collection” or “‘class” or “family” are often used to convey the same idea. The objects which make up a set are called the elements or members of the set. If an object x is an element of the set A, we write xEA. If x is not an element of A, we write xGA. Ifevery member of A is also a member of B, we say A is a subset of B, and write ACB. It is easy to sce that every set is a subset of itself. Two sets, A and B, are equal (written A = B) if and only if they have the same members; that is, every member of A is a member of B and vice versa. In case A CB, but A # B,wesayA is a proper subset of B and write ACB. This happens when every member of A is a member of B, but some member of Bis not a member of A. Example 1. The box on the next page should help to clarify the notions introduced so far. .fee 70 SET THEORY ONE See ONE OF ITS SUBSETS The set of math teachers at ) Dogwood High The set consist- ing of Snoopy and Lucy In many applications of the theory of sets all the sets which come into play are built from elements taken from a set U which is specified in advance and called the universe (for that application). For example, in plane geometry the universe U is usually taken to be the set of all points in the plane, and the geometric figures like lines, circles, and triangles are thought of as sets of such points. In denoting sets, set braces { , | are often used. A set is sometimes specified by listing its elements inside set braces. For example, {1, 2, 8} is the set whose elements are 1, 2, and 8. In specifying a set this way, it is immaterial in what order the elements are written and how often they are repeated. Thus {1,2} = (2, = 12,2.) A set can also be specified by stating a property its members will have, For example, “the set of all objects which have the property of being an odd number,” in short, “the set of all odd numbers.”y 5.1 ELEMENTARY SET THEORY 71 Using x to denote a typical member of this set, we write {x | x is an odd number} and read this “the set of all x such that x is an odd number.” The symbol “|” is read “such that.” It is convenient to introduce the so-called empty set which has no members. The symbol ¢ is used to denote it. It can easily be shown that is a subset of any set A by the following reasoning. To assert g C Ais the same as asserting that for any x, the implication xEGrKEA holds; but this implication holds automatically since for any x, the left side of the implication is false. If A and B are sets, the set of elements belonging to either A or B is called the union of A and B. We write this AUB. For example, {1,2} U {2,3} = {1,23}. The set of elements in both A and B is called the intersection of A and B, We write this AM B. For example, {1, 2} M {2,3} = {2}. The set of elements which is in A but not in B is called the difference of A and B. We write this A- B. For example, {1,2} — {2,3} = {1}. When a universe U is specified and A is a subset of U, U-A is called the complement of A (with respect to the universe U). The com- plement of A is denoted by A’. For example, if U is the set of all whole numbers, and A is the set of all even numbers, then A’ is the set of all odd numbers.72, SET THEORY Example 2. Suppose universe U is the set of all positive whole num- bers. Let A = {1,2,3,4,5} Let B = {1,3,4,9} LetC = {6,7} Then A U B = {1,2,3,4,5,9} AB = [I1,3,4} Anc=¢ A- B= (2,5) A’ = (6,7,8,9...} It is possible for the elements of a set to be sets themselves. For example, for each set A, the power set of A can be formed which has the subsets of A as its elements. It can be shown that if A has n elements, the power set of A has 2" elements. Example3. IfA = {1,2, 3}, the elements of the power set of A are: J. UM (12, £12.34 {2}, (33, (2,3), 13} Relationships among sets can be visualized by making a type of pic- ture called a Venn diagram. A few diagrams are given below. Think of the areas enclosed by the rectangles as the universe U. The rest ought to be self-explanatory. A and its complement A’ Intersection of A and B (shaded)5.1 ELEMENTARY SET THEORY 73 OO Union of A and B (shaded) A and B having no members incommon Cu B isasubsetof A A - B(shaded) Exercises 5.1 1. Are the sets {1, 1, 1} and {1} equal? Why? 2. Let U = {a,b,c,d,e, x, y, 2} LetA = {a,b,c} Let B = {a,e,x} LetC = {x,y,z} } It is also given that the objects denoted by the small letters are all different. Exhibit the following sets. (a) A’ (b) AUB ©) A-~C @ ANC @) ANC () AUBUC @) B-Cc (ht) C-BI 74 SET THEORY 3. List the elements in the power set of A = {a,b,c, dj. 4. Given: A = {1,b,c} | B = {e,f,b,g,h} C = {1,2,¢,b} D = {a,c,e,i} Assuming that all of the symbols in the set braces above denote dis- tinct objects, determine which of the following are truc: @ cE(BUANC (b+) BDEANBNY (c) ¢€ (AND) @ 2€ (CUD) 5.2 Basic Identities and Relations of Set Theory In this section we have listed the set identities and relations most fre- quently needed when using set theory to solve mathematical problems. It is assumed that all the sets appearing in the following list are subsets ofa given universe U. Basic Identities law of double | 1 (AY =A complement ANB=BNA 2. . | 3 AUB=BUA commutative laws 4 5. (AU B)UC=AU (BUC) (ANB)NC=ANBNO associative lawsa 5.2 BASIC IDENTITIES AND RELATIONS OF SET THEORY 75 AN (BUC) =(ANB)U(AN C) AU(BNC)=(AUB)N(AUC) 7 distributive laws 8 (AU BY = A' NB 9. 0. 1 (AA BY = ATUB de Morgan’s laws ANA=A AUA=A idempotent laws 12 AN(AUB)=A 13. AU(ANB)=A 144. AQU=A absorption laws IS. AUP=A identity laws 7 : 4 $ r¢ domination laws 18. A C Bifand only if A’ U B = U 19. A C Bifand only if B’ C A’ 20. A = BifandonlyifA C BandBC A. You have, no doubt, been struck by the formal similarity between these identities and the basic logical equivalences used to manipulate logic forms. More will be said about this later. In the example below, one of these identities will be verified for you. The rest of them can be done in a similar way. Example. Verify de Morgan’s law (for sets). (AU By = A’ B' PROOF: Let x denote an arbitrary object; then, x € (A U BY’ = 7 [x € (A U B)] definition of com- plement = 1(( € A) v (x € B)] definition of union = 1 (x € A)a 1(x € B) de Morgan's law (for logic) = (x € A’) a(x € B’) definition of complementT_T eee e_. 76 SET THEORY = x € (A' 1B’) definition of intersection thusx € (A U BY’ = x € (A’ 1 B') Therefore(A U B)' = A’ B’ Exercises 5.2 All the sets appearing in these exercises are subsets of a given uni- verse U. 1. Under what circumstances are the following statements true? @ ANB =A &) acg (c) AUB=ANMB (d) A-B=B-A (e) ANB=A (f) (AU BYOB =A (g) (AN B)YUB=AUB 2. Verify the following identities. fa) (AY =A (b+) AN BUC) = (AN BYUAN OC (c) AN (AU B)=A (d) (AM By = A'U BY (e) (AU B) - (AM B) = (A ~ B)U (B- A). (f) A = (A- B)U (AN B) 5,3 Checking Consistency of Data Social scientists working for the government spend much time col- lecting and evaluating data to reach conclusions that help shape government programs. Private enterprise spends much moncy on market research in which data is collected and evaluated to determine the public’s response to a company’s products. It may surprise you to learn that some very elementary set theory can be useful in checking that the collected data make sense, but this is indeed the case!sees es a eee Rie 5.3 CHECKING CONSISTENCY OF DATA 177 If A is a set, let #(A) denote the number of elements in A. The following formula, although easy to verify, is important. #(A U B) = #(A) + #(B) — #(A MB) Using it, you can now derive a similar formula for #(A U B U C). The basic idea is to think of A U B U C as the union of two sets, namely A and (B U C). Now apply the above formula to these two sets to get #(A U [BU C}) = #(A) + ABU © - KAM [BU C). The formula can further be applied to the second term. Moreover, after applying the distributive law to the third term, the formula can be applied to its parts. Collecting terms, the result is #HAU BUC) = #A) + #(B) + AC) — #A 1 B)- HAN C) - BM C) +#HAMBMC) Study the two boxed equations! Compare them! If you look at both of them the right way, you should be able to make a good guess as to how the formula for four sets ought to look. In the following two examples you will see how to use the above formulae in a practical way. Example 1. Ina random survey of 100 people who owned houses or cars, it was found that 70 people owned a house, and 30 people owned both a house and a car. How many people surveyed owned a car? ANSWER: Let H = set of house owners C = set of car owners The basic formula is #(H_U C) = #(H) + HC) - HH C). Substituting the data, the result is 100 = 70 + #(C) — 30.a LL 78 SET THEORY Example 2. Thus solving for #(C), the answer is #(C) = 60. Hence, 60 of the people surveyed own cars. Data concerning the sex, education, and marital status of the 500 employees of the Sunshine Brewery were reported as follows: 250 females 156 college graduates 235 married 21 female college graduates 73 married females 43 married college graduates 12 married female college graduates Now the man in charge of assembling the data was a bit of a boozer, and it was rumored that he made up the data after having too much to drink. His boss be- came suspicious and was able to check the data for consistency as follows: F = set of female employees G = set of college graduate employees M = set of married employees The data can now be written 250 = #(F) 156 = #(G) 235 = #(M) 21 = FM G) 73 = #(M 1 F) 43 = #(M 1M G) 12 = #(MO FG) Putting this data into the previously given formula for the union of three sets, we get #(M U F U G) = 250 + 156 + 235 - 21 - 73 - 43 + 12 = 5165.3 CHECKING CONSISTENCY OF DATA 79 Recall that the company had only 500 employees and MU FU G being a subset of the set of employees can have no more than 500 members. This contradicts the figure of 516 just calculated, so the data is in- consistent. The data collector, by the way, was trans- ferred to the tasting department where he seems to be getting along well. Exercises 5.3 *1. For the finite sets A, B, C, D, derive the formula: #HAUBUCUD) = #(A) + #(B) + AC) + HD) - HA 2 B) - HAM C)- HA MD) - BAO) ~ BM D)- HOM D) + HAN BNO + KA MBAD) + HAN COD) + MBACND) - HA NBACND) 2. Ina survey of 100 welfare recipients, the following facts were dis- covered: 45 had severe physical handicaps 14 were illiterate 86 lived in substandard housing 5 were illiterate and had severe physical handicaps 39 lived in substandard housing and had severe physical handicaps 12 were illiterate and lived in substandard housing 4 were illiterate, had severe physical handicaps, and lived in sub- standard housing. How many of these recipients had severe physical handicaps and lived in substandard housing, but were not illiterate? How many were illiterate but were not physically handicapped and did not live in substandard housing? How many of those surveyed had none of the above mentioned prob- lems? *This denotes a difficult problem.a LLL rh hr 80 SET THEORY 3. Ina certain city, drivers lose their licenses if and only if they are guilty of speeding, failing to stop for a red light, or passing another car in a “no passing” zone. In 1952, 60% of those with revoked licenses were guilty of speeding, 75% failed to stop for a red light, 70% passed another car in a “‘no passing” zone, 45% were speeding and did not stop for a red light, 50% were speeding and passed another car in a “no passing” zone, 40% did not stop for a red light and passed another car in a “no passing” zone. What percentage of all the drivers who lost their licenses were guilty of all three violations? 4. The United States Senate is considering three proposals to curb in- flation: raising income taxes, imposing wage and price controls, and imposing higher tariffs on imports. Of the 100 senators: 62 support higher tariffs on imports 58 support higher income taxes 24 support wage and price controls No senator supporting higher tariffs on imports favors wage and price controls. Of the senators supporting higher taxes, as many favor wage and price controls as favor higher tariffs. Moreover, each senator favors at least one of the three proposals. (a) How many senators favor both higher taxes and wage and price controls? (b) How many senators favor only higher taxes? Only higher tariffs? Only wage and price controls?