Yale-New Haven Teachers Institute Home

## Logic and Set Theory

by
Richard Canalor

#### To Guide Entry

The following unit is designed to offer teachers and children a chance to explore what may be to them a different area of Finite Mathematics. While in no way does the unit cover the entire fields of Set Theory and Logic, it does, I hope, offer an introduction to the basic concepts, symbols and importance of these two fields of Mathematics. As you will see, Set Theory and Logic are related and have therefore been combined for the content of this unit. The unit is approximately two weeks in length and is intended for grade 6,7, or 8 although both length and grade level may vary.

We will begin with a short Pretest. The purpose of the pretest is twofold. On one hand it will give some barometer of success (there will be a posttest) and hopefully the pretest will foster discussion and motivate children to want to hear more.

### Pretest

1. There were 20 people at a party. Thirteen had coke, 7 had sandwiches, 5 had both. How many did not eat or drink?
2. “If I see then I learn” is equivalent to “I do not see or I learn.” True or false?
3. If A= {0,1,2} B= {2,3,4} and C= {4,5,6}then A {B C} = ?
Note: {} = Set
= Union
= Intersection
4. Which is not a statement?
a. n+6=9
b. 5+3=7
c. The sky is blue.
5. Use any three of the following terms correctly in sentences to show their meanings.
1. hypothesis
2. implication
3. negation
4. converse
5. inverse
6. contrapositive
7. conjunction
8. disjunction
Hopefully the reader has read the above problems and responded to them. The explanations and answers to the questions represent the areas to be covered. The answers to the first four questions are as follows: (1) 5 (2) True (3) (0,1,2,4) (4) a.) n+6=9. The answer to question 5 will be explained more fully in the unit but any sentences using the words correctly would be acceptable.

### Logic

In mathematics the study of logic deals with statements or propositions. A statement is a sentence that is either true or false, but not both. The statement is said to have a truth value.

“All children are lefthanded” is a false statement. “Many people enjoy science fiction” is a true statement. “5 + 4 = 9” is a true statement while 5+4=8 is a false statement. “This sentence is true” is not a statement at all since it can be both true and false. The same is true for “6+n=9.” It is neither a true nor false statement since this depends upon the replacement for the variable n.

In logic we use symbols to represent statements. For example, if we use p to represent a statement then we use ~ p to represent the negation of p. If p is “I am a plumber” then the negation of p written, ~ p, would be “I am not a plumber.” It is worth noting that the negation of p must be false if p is true and must be true when p is false. Try the following:

Part 1 Identify each of the following as a statement or not a statement.

a. The house is red.

b. Joan is not at home.

c. n+3 = 7 d. 6+2 = 7

Part 2 Give the negation for each of the following statements.

a. I like school

b. No one is happy at work.

c. All trees are green.

Solutions:

Part 1. a. yes b. yes c. no d. yes.

Part 2. a. I do not like school b. Some people are happy at work c. Not all trees are green.

Note In example part 2b the negation cannot be all people are happy at work since it is possible for some people to be happy at work and some to be unhappy at work. Some statements are a little harder to negate, especially when they include all or none statements.

### Conjunctions and Disjunction’s

Once the simple statement and the negation described above are understood the next step in the study of logic is the introduction of compound statements. Compound statements are two or more simple statements joined by connectives.

Two connectives used to make compound statements are the words “and” and “or.” The compound statement formed by the word “and” is called a conjunction, and the compound statement formed by the word “or” is called a disjunction. The connective “and” is often denoted by the symbol ^ , while the connective “or” is denoted by the symbol^. Example.

If p represents the statement I will go to the movies and q represents the statement I will eat at the restaurant then p ^ q represents the statement I will go to the movies and I will eat at the restaurant while p^q represents the statement I will go to the movies or I will eat at the restaurant.

Statements connected with the conjunction “and” are only true when the p statement is true and when the q statement is true. Statements connected with the disjunction “or” are true if either p or q are true. The section on truth tables will further define conjunction and disjunction.

### Negation

The process of negating compound statements uses the tilde symbol,~~, which we have already used in negating simple statements. It is important to note that in negating compound statements the tilde symbol is placed before the statement we wish to negate. If we wish to negate the entire compound statement we place the tilde before a parenthesis. Example.

In p ^q only the p statement is negated while in ~ (p ^ q) the whole statement is negated.

To negate a conjunction or disjunction of two or more simple statements we negate each of the simple statements and then change all of the connectives from disjunction’s to conjunctions and all of the conjunctions to disjunction’s.

Example:

~ (~P q) = p^~ q

Try these. Give the negation for each of the following:

1.~~(P~ q)

2. ~ (P^ q)

Solutions:

1. pvr~ q 2.) ~ p ^~ q.

The reason we are able to negate each simple statement and change the connectives is that the statements are equivalent. In the example above if we let p be “I try” and q be “I succeed” then the negation of I do not try or I succeed written ~( ~ p ^q) would be “I try” and “I do not succeed” written p^~q. Both compound statements say the same thing in different ways are equivalent.

The teacher may wish to give the class exercises such as those which follow: Let p be I race and let q be I win. Give a verbal translation for each of the following:

a. P^ q

b. p^~ q

c. ~ p ^~ q

d. ~(pv~q)

e. (P v~ q)

f. (p^~ q) v( ~ p ^~ q)

Solutions:

a. I race and I win

b. I race and I do not win

c. I do not race and I do not win

d. It is not true that I race or that I do not win

e.’ The statement I do not race or I do not win is not true.

f. I race and I do not win or I do not race and I do not win.

Note: In solution d. the language becomes very difficult and so we may wish to use the equivalent statement, “I do not race and I win.” We know this is equivalent since in negating any compound statement we can simply negate each simple statement and change all of the connectives. In this example for instance the two equivalent statements would be written symbolically as follows: ~(pv ~ q)=p^q.

Note: = is the symbol for equivalent.

A truth table for the above problem will be constructed at the end of the section dealing with truth tables.

### Conditional Statements

If it rains then we will go to the movies is a conditional statement. Two simple statements are connected by the words if. . .then. The first statement labeled p is called the hypothesis and the second statement labeled q is called the conclusion. Symbolically, conditional statements are written p > q.

The study of conditional statements and their use in proving the validity of an argument through deductive reasoning is a topic beyond the scope of this paper. Sample lesson plan 1, however, at the end of this unit does show one way in which conditional statements are used to determine the validity of an argument.

### Other types of statements

Statements can be written in other ways as well and these other forms have identifying names: They are the biconditional, the converse, the inverse, and the contrapositive.

Consider the following conditional statement:

If I try then I will succeed.

p> q

The biconditional form for this given conditional statement would be: I will succeed if and only if I try.

p > q or (q>p) ^ (p>) q)

The converse would be If I succeed I try.

q> p

The inverse would be: If I do not try then I do not succeed.

~ p>~ q

Finally, the contrapositive would be: If I do not succeed then I do not try. ~ p>~p.

Children after seeing an example done might be able to give the various statements and symbols for a similar type problem or create one of their own. The vocabulary introduced should be discussed and children should become familiar with these words especially the prefixes bi con contra and in . Pretest question ~ should no longer be a mystery. Other words with these prefixes may also be studied.

### Truth Tables

To this point we have discussed simple statements, negations, conjunctions, disjunction’s and conditional statements all of which are statements that are either true or false but not both. Often tables, called truth tables are used to determine whether various types of statements are true or false. These tables show all the possible combinations of truth values of simple statement involved in the truth values of the resulting compound statements. The tables shown below show the truth table for p^q and also for pvq. There are four possible cases for each. If p is true and q is true then p^q is true; if p is true and q is false then p^q is false since p^q requires both statements to be true. The tables for conjunction and disjunction follow:

(figure available in print form)

The truth table for conditional statements is as follows:

(figure available in print form)

What is most confusing about the truth table above is that in only case 2 is the result false. What a conditional statement merely says is that if a hypothesis is true then the conclusion is true. It says nothing of the case where the hypothesis is false, so we arbitrarily give a truth value of true to every case in which the hypothesis is false cases 3 and 4. Thus to define a conditional statement we can say it is always true unless the hypothesis is true and the conclusion is false case 2.

Consider the following example, “If you go to the beach then I’ll never talk to you again.” The hypothesis is “you go to the beach.” If this statement is false that does not necessarily mean that the conclusion is false. I may still talk to you. On the other hand If I do not ever talk to you again it is impossible for you to have gone to the beach.

### Comparing Truth Tables

Truth tables are useful in discussing equivalent forms of statements. For example we can prove that p> q is equivalent to ~ p v q through the use of truth tables. We must first construct a truth table for each case.

(figure available in print form)

The column under p>q is equivalent to the column under ~Pv q proving that the two statements are equivalent. Statements can be substituted to further show equivalence. Let p be “I see” and q be “I learn.” The statement “If I see then I learn” is equivalent to “I do not see or I learn.” Referring back to the Pretest we can now prove that question two is true.

Try constructing truth tables for the following:

a. ~ p v q

b. p v ~ p

c. ~ (p q)

d. ~ (p v q)

Solutions:

(figure available in print form)

Prove that the following two statements are equivalent by constructing a truth table.

“It is not true that I race or that I do not win”=”I do not race and I win.”

~ (P v ~ q)= ~ p ^ q

~ q)= ~ p ^ q

(figure available in print form)

Since the tables for ~ (P v ~ q) and ~ p ^ q are identical we can say that the statements are equivalent. Also since the conditional statement (last row of table) is true in all cases we call it a tautology. A tautology is a statement which is always true. Statements can be tautologies without being equivalent if they are always true but not identical. This too is beyond the scope of this unit.

### Set Theory

As with the section on logic it should be noted that the following information on set theory is only an introduction. Hopefully children will be interested enough to want to know more either now or in the future.

A set is a well defined collection of “objects.” The term “well defined” means that the set is described in such a way that we can determine whether or not any given object belongs to that set.

Example.

The following are sets.

a. the set of all men

b. the set of whole numbers between 17

Example. The following are not well defined, so are not sets.

a.) all wellknown artists

b.) three wealthy men

Every set is a collection of elements or members of that set. When there are only a few members of a set we usually use the tabulation or roster method to denote the set.

Example.

The set of whole numbers between 1 and 4 would be written { 2,3} . The elements of the set are all listed between the set braces.

The tabulation method can also be used when a set has a great or even infinite number of elements, provided that those elements are ordered.

Example.

The set of whole numbers less than 50 can be denote {0,1,2....,49}

The set of all whole numbers would be {0,1,2,...}.

Note: The first three elements are shown, then 3 dots and finally the last element if the set is not infinite.

Another method for naming a set is the descriptive method which is used when the above tabulation method is not convenient or will not work. The diagram shows the descriptive method:

(figure available in print form)

We also use the symbol · to denote the phrase “is an element of.” Thus we can say, “If A= {2,3,4), then A is a set containing 3 elements. 2 £ A, 3 · A, and 4 · A.”

The next ideas to be discussed are the universal and the null set. The universal set describes that set from which we select all our sets in a particular problem. The null set on the other hand is a set which contains no elements. The universal set usually is shown by U and the null set by ~ .

If U= {1,2,3,4,5} and B= {1,2} and C= {3,4} then the set of all elements common to B and C is the null set ¯ since no element of B is an element of C. All of the elements of B and C however are elements of U, the universal set.

Equal sets are sets in which both elements of set A and elements of set B are the same written A> B. If A = {1,2,3} and B= {3,1,2} they are equal sets. Any element of A is an element of B and any element of B is an element of A.

Subsets are sets in which all of the elements of set A are elements of set B yet not all of the elements of set B are elements of set A. For example A= {1,2}, B= {1,2,3}. Set A is a subset of set B, written A ² B, Note: the ¯ is always a subset of another set since there are never any elements in ¯ which are not in any other set A. Therefore ¯²A,

The following exercises relate to the material introduced to this point,

Part 1. Determine the following sets.

1. The set of odd numbers between 16 and 24
2. The set of states whose names begin with “New.”
3. The set of whole numbers between 2 and 20 which are exactly divisible by 3.
4. The set of all foreigners elected President of the U.S.

Part 2. Using the sets below answer the following questions yes or no:

U = { 1,2,3,4,5,6}

A = { 1,2,5}

B = { 1,2,3,4,5}

C = { 1,5,2}

D ={6}

1. Is A = D?

2. Is D ² U?

3. Is C = A?

4. Is A ² B?

5. Is ¯ = B?

6. Is ¯ ² B?

Solutions Part 1.

1. { 17, 19, 21, 23}

2. { New York, New Jersey, New Hampshire, New Mexico)

3. { 3,6,9,12,15,18}

4. ¯

Part 2.

1. No

2. Yes

3. Yes

4. Yes

5. No

6. Yes

### Intersection

If A and B are two sets taken from some universe U, then the intersection of A and B written A ½ B, is the set containing all elements common to sets A and B.

A ½ B = { X \ (X · A) ^(X

· B)}

Example.

A = { 1,2,4}

B = { 2,4,6,7}

A ½ B = { 2,4}

Note: The definition for intersection says that in order for an element to be part of the solution set for A ½ B it must be both an element of A and an element B. The definition of the conjunction “and” also requires that both statements, p and q be true.

### Union

If A and B are two sets taken from some universe U, then the union of A and B written AUB, is the set containing any element of either A or B.

A U B = {X \(X · A) V(X ·B)}

Example.

A = { 1,2,3}

B = { 4,5,6}

AUB = {1,2,3,4,5,6}

Note: The definition for union says that in order for an element to be part of the solution set for AU B it must only be a member of either set A or of set B. The definition of the disjunction “or” also requires that only one statement p or q be true.

### Complementation

In set theory there is also a similar term to that of negation in logic. It is called complementation. If set A is taken from some universe then A’, the complement of A, is all the members of that universe not in set A. The following is an example.

U = { 1,2,3,4,5}

A = { 1,2,}

A’= { 3.4.5}

### Set Difference

One other operation in set theory is called set difference. Given two sets A and B taken from some universe U, then A minus B, written AB is the set of all elements that are in A but not in B.

Example.

U = { 1,2,3,4,5,6}

A = { 1,4,5,6}

B = {1,3,4}

AB = {5,6}

Combining operations allows us to solve problems such as those below.

U = {1,2,3,4}

A = { 1,2}

B = { 2,3}

Find (A ½B)’

The part in parentheses is done first giving us the number 2. (A ½ B)’ = { 1,3,4} since these are the elements in the universe which are not in the intersection of (A½ B.)

Try the following:

(figure available in print form)

Find:

(figure available in print form)

Solutions:

(figure available in print form)

Additional exercises can be developed by the teacher to test understanding for set concepts presented in this unit. One such exercise is shown below.

Prove that AB = A ½B’

Solution:

AB = A. B’ is A which makes A ½B’ also equal to A. Since both sides of the equation equal set A we have proven that A B = A ½B’.

### The Venn Diagram

The last section of this unit deals with the Venn Diagram. Instead of using capital letters and brackets to denote sets we shall now use a pictorial method.

In a Venn diagram there is a rectangle which shows the universal set. Circles within the rectangle show subsets of the universal set.

(figure available in print form)

If you have the universal set { 1,2,3,4,5} and Set A= {1,2,3} and set B = {3,4} then the two circles are shown to intersect since 3 is a member of both set A and set B. The diagram above shows the 3 where the circles intersect. Also shown are the 1 and 2 in A only and the 4 in B only. The number 5 is part of the Universal set but is neither an element of A or B.

Draw a Venn diagram to show the following:

1. U= {1,2,3,4,5}

A= {2,3}

B= {1,2,4}

Solution:

(figure available in print form)

2. U= { 2,4,6,8,12}

A= {2,6,4,12}

B= {2,12}

C= {6}

Solution:

(figure available in print form)

Sample lesson Plan 2 describes how the Venn diagram can be used to simplify problems dealing with intersection.

The use of diagrams can indeed make what appears to be a difficult problem rather easy. Students should be encouraged to use the Venn diagram as well as other pictures and charts to help make their word problems and problem solving easier and more meaningful.

### Sample Lesson Plan 1

Objective: Children will be able to state the law of syllogism and use it to prove the validity of an argument.

Motivation: Place on board the following:

(figure available in print form)

Have class substitute a simple statement for each letter. For example p might be I go to school; q I learn; and r I succeed. Next substitute conditional statements for these simple statements. It now reads. If I go to school then I learn. If I learn then I succeed. Therefore (...) if I go to school then I succeed. Children may wish to read their results and should be encouraged to do so.

This is the law of syllogism and can be

written:

[(P > q) ^ (p> r) > (p>r)

Using the law of syllogism prove that the following arguments are valid or invalid:

1. If John is smart then he will be the leader. If John is smart then he will make a speech. John is a leader therefore he will make a speech.
2. If Mary sings then she will be happy. If Mary is happy then she will dance. Mary sings therefore Mary dances.
Argument 1 is invalid. The proof appears as follows:

p John is smart

q he will be the leader

r he will make a speech

(Invalid) p >q p>r

(figure available in print form)

You cannot deduce that if q then r since both are conclusions and one does not imply the other. There is no syllogism.

Argument 2 is Valid. The proof appears as follows:

p Mary sings

q she will be happy

r she will dance

(Valid)

(figure available in print form)

The law of syllogism is satisfied and therefore the argument is valid.

### Sample Lesson Plan 2:

Objective Using the Venn diagram

to solve problems.

Motivation: Take the pretest problem 1 and write it on the board. Discuss methods used in solving.

The problem was as follows: There are 20 children at a party; 13 had cokes; 7 had sandwiches; and five had

both. How many did not eat or drink?

A Venn diagram consists of a rectangle which represents the universe, and circles within the rectangle representing the sets involved.

Draw a Venn diagram for the above.

(figure available in print form)

Begin with those that had both. It is placed where the circles intersect. How many people then had only cokes? 135=8. How many had only sandwiches 75=2. The Venn diagram now appears as follows:

(figure available in print form)

The total of those who had something to eat or drink is 15 leaving 5 who had nothing to eat or drink.

Try the following problem:

A survey of 100 students at Sheridan gave the following data:

41 students taking Spanish

29 students taking French

26 students taking Italian

15 students taking Spanish and French

8 students taking French and Italian

19 students taking Spanish and Italian

5 students taking all three languages

Find the number of students among the 100 that are not taking any of the 3 languages. How many take just one of the languages?

Solution:

(figure available in print form)

Solution:

41 Children are studying no foreign language. 27 children are studying only one language.

### PostTest

The following PostTest may or may not be relevant depending on the emphasis given to each area of this unit. The five questions below are similar to those given in the pretest. The posttest results will depend on which areas of this unit (including sample lesson plans) were taught. Teachers may wish to devise a test of their own or simply add to this brief posttest.

1. The 15 players on the team were asked to name their favorite baseball team. 6 chose the Yankees and 6 chose the Red Sox. 3 children chose both. How many children chose neither of these teams?
2. p>q is equivalent to ~ p v q. True or false?
3. If A= {5,10,15,20}, B= {15,20} and C= {5,20,25} then A ½(B U C) =?
4. Which is not a statement? a.) 5+2=6 b.) 6+n=9 c.) 7+5=12.
5. What is the converse and what is the inverse of the following statement: If it rains then I will get wet.

Solutions:

1. 6

2. True

3. { 5,15,20}

4. 6+n=9

5. Inverse If I get wet then it rains.

Converse If it does not rain then I will not get wet.

### Conclusion

The language of logic and set theory is not merely about statements in a textbook. If q then r can signify anything one wishes to put in the blanks.

The elementary school student may have difficulty with even the most simple ideas of set theory and logic and yet they should get some introduction to these ideas. Problem solving in all areas of mathematics requires the ability to reason and to form valid conclusions.

### Bibliography

Cheifetz, Philip and Avenoso, Frank J. Logic and Set Theory. Belmont California: Wadsworth Publishing Company, Inc. 1970.

A selfstudy work book covering logic and set theory. Excellent. Would be ideal for classroom use if more complete coverage of these areas is desired.

Goodman, A. W. and Ratti, J.S. Finite Mathematics with Application. New York: The Macmillan Co., 1971.

The first two major sections deal with logic and the algebra of sets. An excellent source of problems as well as the relationship between logic and set theory.

_____. The Growth of Mathematical Ideas K12. Washington DC, The National Council of Teachers of Mathematics, Inc., 1959.

Chapter 4 entitled “Proof” by Eugene P. Smith and Kenneth B. Henderson deals with logic, euler circles and inferences.

Hallerberg, Arthur E. Logic in Mathematics—An Elementary Approach. New York. Hafner Press, 1974.

Workbook covering the study of logic through an easy to understand method. This workbook is recommended for classroom use unless the teacher wishes to include set theory.

Peterson, John M. Finite Mathematics. New York. Holt, Rinehart and Winston, Inc. 1974.

Chapters 1 and 2 deal with set theory including truth tables and switching networks Chosen as text to be used in our seminar group. A good beginning.

Scott, Lloyd. Trends in Elementary School Mathematics. Chicago, Illinois. Rand McNally and Co., 1966.

A short chapter containing a brief introduction to set theory and logic as well as the importance of these areas in the elementary school.