1. In the following compound propositions there are two simple propositions connected by a conditional. Indicate for each pair of simple propositions which proposition is the necessary condition for the other and which proposition is the sufficient condition for the other.

a) If I pass my algebra class I'm done taking math.

b) Unless the engine is overhauled the car won't run.

c) Without gas in the tank the car won't run.

d) Henry won't go to school unless he feels better.

2. Each proposition below is followed by a list of statements. Indicate which of the statements are syntactically equivalent to the original proposition.

a) If the weather doesn't improve the game is cancelled.

i) If the weather improves the game won't be cancelled.

ii) If the game is cancelled the weather does not improve.

iii) If the game is not cancelled the weather does improve.

iv) Unless the weather improves the game is cancelled.

v) Unless the game is cancelled the weather improves.

vi) The weather improves or the game is cancelled.

i) If Sally has the proper motivation she will do her homework.

ii) If Sally hasn't the proper motivation she won't do her homework.

iii) If Sally does her homework she has the proper motivation.

iv) If Sally doesn't do her homework she does not have the proper motivation.

v) Unless Sally has the proper motivation she won't do her homework.

vi) Unless Sally does her homework she does not have the proper motivation.

i) If the book of Genesis is literally true, the earth is not 4.5 billion years old.

ii) If the book of Genesis is not literally true, the earth is 4.5 billion years old.

iii) If the earth is not 4.5 billion years old, the book of Genesis is literally true.

iv) Unless the earth is not 4.5 billion years old, the book of Genesis is not literally true.

v) Unless the earth is 4.5 billion years old, the book of Genesis is literally true.

vi) The book of Genesis is literally true or the earth is not 4.5 billion years old.

i) If the Vikings have a loss on the next game, the Packers make the playoffs.

ii) If the Packers make the playoffs the Vikings have a loss on the next game.

iii) If the Packers don't make the playoffs the Vikings do not have a loss on the next game.

iv) If the Vikings don't have a loss on the next game, the Packers don't make the playoffs.

v) Unless the Packers make the playoffs, the Vikings do not have a loss on the next game.

vi) Unless the Vikings have a loss on the next game, the Packers make the playoffs.
 
 

a) 

b) 

c) 

d) 

e) 

f) 

g) 

h) 

i) 

j) 
 
 

4. Represent the following statements with quantifiers using the predicates given. In addition for each sentence state what you think is the intended domain of the variables.

m(x)="I mean x" ; s(x)="I say x" .

a) I mean whatever I say.

b) I say whatever I mean.

c) Unless I mean something, I don't say it.

d) Unless I say something, I don't mean it.

e) The meek shall inherit the earth.

f) Everything that's fun is either illegal, immoral or fattening.

g) Not every politician is dishonest.

h) There are honest politicians.

i) All men are created equal.

5. State the negation of each of the following by changing universal quantifiers to existential quantifiers and vice versa.
 

a) I mean whatever I say.

b) There is at least one honest man.
 

c) Everything that's fun is either illegal, immoral or fattening.

 

d) For any real number x , f (x) > 0 .

e) 
 

6. In English, as in probably all languages spoken by humans, there occur sentences called idioms. In an idiom the meaning (semantics) is not clearly conveyed by the sentence's structure (syntax). In fact, the semantics may be at odds with the syntax. For example, the sentence, "there ain't nobody home today", because of its double negative syntactically should be equivalent to "somebody is home today". However, its common interpretation would be "there is no one home today".
In Act II, Scene VII of William Shakespeare's play, The Merchant of Venice, there occurs the line "All that glisters is not gold". This statement predates Shakespeare and can also be found in the following sources :
"But all thing which that shineth as the gold Ne is no gold, as I have herd it told." From Chaucer The Chanones Yemannes Tale. Line 16430.
"Do not hold everything as gold which shines like gold." From Alanus de Insulis in the Parabolae.
"All is not golde that outward shewith bright." From Lydgate in On the Mutability of Human Affairs.
"Gold all is not that doth golden seem." From Edmund Spenser in the Faerie Queene, book ii. canto viii. st. 14.
"All is not gold that glisteneth." From Thomas Middleton in A Fair Quarrel, verse 1.
"All, as they say, that glitters is not gold." From John Dryden in The Hind and the Panther.
"Que tout n'est pas or c'on voit luire (Everything is not gold that one sees shining)." From Denise Cordelier in Li Diz de freire.

 

 

Let g(x) be the predicate "x glisters" and a(x) be the predicate "x is gold". Render "All that glisters is not gold" symbolically using quantifiers. Does your rendering have the intended meaning? If not, give a second representation of this statement that does.

 

 
 
 

7. Classify each of the following arguments as either valid (from the syntactical point of view) or invalid. Justify your choice.

a)
Premise: If 2^r-1 is a prime number, then r is a prime number.
Premise: 11 is a prime number.
Conclusion: 2¹¹ is a prime number.
 

b)

Premise: If bombs were planted both by right-wing extremists and foreign terrorists, then either the police or the FBI are not baffled.

Premise: Right-wing extremists did plant a bomb, but both the police and the FBI are baffled.

Conclusion: A bomb was not planted by foreign terrorists.

 

 

c)

Premise: Unless you pay your rent you will be evicted from your apartment.

Premise: If you are evicted from your apartment, you will move back in with your parents.

Premise: You move back in with your parents.

Conclusion: You did not pay your rent.

 

 

d)

Premise: The party will not be a success unless Peter attends.

Premise: If the party is a success, Mary will call Jane.

Premise: Mary does not call Jane.

Conclusion: Peter did not attend the party.

 e)

Premise: If there is a God, no person will suffer extreme pain unless God is unable to prevent it.

Premise: If God is unable to prevent suffering God is not omnipotent.

Premise: There are people suffering extreme pain.

Conclusion: Either there is no God or God is not omnipotent.

 

f)

Premise: If life is fair, then either all criminals are punished in proportion to their crimes or there is an after-life.

Premise: Some criminals are not punished in proportion to their crimes.

Conclusion: Either there is an after-life or life is not fair.

 

 

8. Assume that the following premises are all true.

Premise: If the US intervenes unilaterally in the Balkans, then US-Russia relations will suffer.

Premise: If US-Russia relations suffer, then either US-China relations won't get worse or the defense budget will increase.

Premise: If the defense budget increases then the rate of inflation will increase.

Is it a certainty that if the US intervenes unilaterally in the Balkans that the rate of inflation will increase?Explain your answer.
 

Is it a possibility that if the US intervenes unilaterally in the Balkans that the rate of inflation will increase? Explain your answer.

 

Is it a certainty that if the inflation rate increased that the US intervened unilaterally in the Balkans?Explain your answer.
 

Is it a possibility that if the inflation rate increased that the US intervened unilaterally in the Balkans?Explain your answer.

 

What can you conclude if the rate of inflation remains constant and US-China relations deteriorate?

 

 

9. Draw a valid conclusion from the stated premises and detail your reasoning.

Premise: If there is at least one person who fails to lose weight on diet A, then all of the brochures must be revised and the advertising manager will be fired.

Premise: Some of the brochures were not revised.

Conclusion:
10. If  2^r-1 is a prime number, then r is a prime number. Is 2^1000000-1 a prime number? Justify your answer.

 

11. All odd degree polynomials with real coefficients have at least one real root. Q(x) is a polynomial with no real roots. What can you conclude about Q(x) ?

 

 

 

12. Construct an informal proof of each of the following set operation identities.
 

a) 
 

b) 
 

c) 
 

d) 

 

e) 

 

f) 

 

 

13. Assuming a Universe S, draw a Venn diagram that illustrates the following set operation identities.

 

 

a) 

 

 

 

b) 

 

 

 

c) 

 

 

 

d) 

 

 

14. Prove the following:

a) The sum of the first n natural numbers is given by .

 

 
 
 

b) The sum of the squares of the first n natural numbers is given by.
 
 
 
 
 

15. Consider the following:

Is it true that every odd natural number is the difference of the squares of consecutive integers?

16. Consider the function that inputs a Social Security number and outputs the name of the person who has that Social Security number. Is this function 1-1? Explain your answer.
 
 

17. Consider the function from N to N that outputs the square of its input. Is this function 1-1? Explain your answer. Is this function onto? Explain your answer. What is the inverse to this function commonly called?
 
 

18. Consider the linear function from R to R that is given by the formula f (x) = mx + b , where m is a real constant called the slope and b is a real constant called the y intercept. Evaluate the following:

a) _________

b) _________

c) _________

d) _________

e) _________

f) _________________

g) _________________

 h) _________________

i) For what values of m is this a 1-1 function?

j) For what values of m is this an onto function?

19. A perfect number is a whole number equal to the sum of its proper divisors (i.e., the sum of all its whole number factors less than itself). For example, the first two perfect numbers are 6 and 28. 6 = 1 + 2 + 3 and 28 = 1 + 2 + 4 + 7 + 14 .
Euclid proved that if 2^r-1 is a prime number, then  2^r-1(2^r-1) is a perfect number. Euler proved that if  p is an even perfect number, then there exists a prime number r with 2^r-1 a prime number and p = 2^r-1(2^r-1) . For a prime number r, prime numbers of the form 2^r-1 are called Mersenne primes. Unresolved questions (at least at the date of this writing, 2002) are whether there are any odd perfect numbers (though it is known that if any odd perfect numbers exist they must be larger than 10³⁰⁰ !) and whether there are infinitely many Mersenne primes.

Suppose there are infinitely many perfect numbers, what conclusion can you draw about the number of Mersenne primes?
 

Suppose there are infinitely many Mersenne primes, what conclusion can you draw about the number of perfect numbers?
 
 

20. Is the set of irrational numbers countable? Explain your answer.
 

21. Consider the set . Are the elements of this set rational or irrational? Explain your answer. Is this set countable? Explain your answer.
 

22. Must the union of countable sets be countable? Explain your answer.
 

23. Must the intersection of countable sets be countable? Explain your answer.
 

24. Must the union of uncountable sets be uncountable? Explain your answer.
 

25. Must the intersection of uncountable sets be uncountable? Explain your answer.
 
 

26. Why did mathematicians and logicians find Russell's Paradox so disturbing?
 
 
 
 
 
 

27. Russell's Paradox was not the first "crisis" result in mathematics. Some 2300 years earlier the Greeks were scandalized that numbers like the square root of two could be irrational. This was called the problem of the "incommensurables". Why do you suppose the existence of irrational numbers was so disturbing?
 
 

1. Math Wars Episode I : The Logic Menace

You and your stalwart rebel companions are fighting the diabolical forces of the evil galactic empire. You were all held prisoners in the Intelligence Citadel of Azhal, but through a brilliant series of maneuvers, you have managed to free yourself from your cells. You are desperately seeking to exit the stronghold, but security forces are right behind in hot pursuit. You are now at a point in a long corridor that branches into two different directions. You know that one of the paths leads to freedom, the other straight into the heavily guarded Security Headquarters. However, you don't know which path leads where. You are about to flip a coin to decide the issue, when you spot an Info-Droid. If you state a proposition to an Info-Droid it will reply either TRUE or FALSE depending on the sentence entered. However, it is possible to program the Info-Droid to either always tell the truth or to always lie. Only the Imperial Security Forces and the droids themselves know which option was used. Furthermore, unless you have a Security Access Card, Info-Droids will only reply to one enquiry an hour. Thus, you only have time to enter one sentence, though it may be a compound proposition. Is there a statement you can enter that will tell you which way to go? If so, what is it?
 
 
 
 

2. A valid Argument or Splitting Hares?

a) What if anything is wrong with the following demonstration by Mathematical Induction that if one rabbit is white all rabbits are white?

Hypothesis: In any set of n rabbits, if one of the rabbits is white, all of the rabbits are white.

3. A triple of natural numbers a, b, and c is called a Pythagorean Triple if and only if a² + b² = c² . Is the set of Pythagorean Triples finite? Explain your answer.
 

4. Consider the subset of RRgiven by { (a, b) | a and b are both integers} called a "lattice". Now connect every point of this lattice to the origin [i.e., the ordered pair (0, 0) ] with a straight line. Are there points in RRwhichare not on any of these lines? Explain how you know.
 

5. Could a positive irrational number raised to an irrational power ever be a rational number? Explain your answer.
 

6. Consider a 1-1 function from the set {1, 2, 3, … , n} to {1, 2, 3, … , n}. Must such a function be a bijection? Explain your reasoning.
 

7. Consider an onto function from the set {1, 2, 3, … , n} to {1, 2, 3, … , n}. Must such a function be a bijection? Explain your reasoning.
 

8. The set of all bijections from the set {1, 2, 3, … , n} to {1, 2, 3, … , n} forms a set called the Permutation Group of order n.

a) How many elements does the Permutation Group of order one have?

b) How many elements does the Permutation Group of order two have?

c) How many elements does the Permutation Group of order three have?

d) How many elements does the Permutation Group of order four have?

e) How many elements does the Permutation Group of order n have?

9. The thirteen cards of a given suit of an ordinary deck of playing cards are dealt according to the following scheme. The top card is placed face up and the next card is then moved to the bottom of the deck. This process is repeated until all cards are face up. Determine the initial order of the cards which will result in the cards appearing face up in the sequence ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, jack, queen, king.

10. What does the Axiom of Choice say? Is this true for anyfinite set?