80-110: The Logic of Mathematical Reasoning
Spring 1997
Sample Questions for Test 2
1) Below is Euclid's proof that there are an infinite number of prime numbers.
1) Suppose that the primes are finite.
2) Then the set of all primes P = {P
3) Let the number X be the product of all of the primes + 1,
i.e., X = (P
1 * P2 * ... * Pn) + 14) Then X > P
n, so X cannot be prime.5) But if X is not prime, there must be a prime P
i > 1 such that X = Pi *Y.6) But for every prime P
i, when Pi is divided into X, there will be a remainder of 1, so X has no prime factors.7) X is therefore prime, contrary to what we proved in 4, thus the primes are infinite.
Explain the justification for steps 1, 5 and 7 in this argument. Are they assumptions for a conditional proof, for a reductio, are they applications of a definition, are they argument by cases, are they reductio, are they axioms, etc.
2) Axioms, theorems and definitions
In 1-4, identify which are axioms, which are theorems, and which are definitions.
1) A person is an alpha-nerd if i) they always wear pants, and ii) they wear pants that do not reach their shoes while they are standing up.
2) A person is a beta-nerd if they like work more than play.
3) Every professor is an alpha-nerd or a beta-nerd.
4) A professor who occasionally wears a skirt is a beta-nerd.
3) a) What is the point of truth tables?
b) What is the point of a formal proof system like ND? Why do we need a formal proof system like ND when we already have truth tables?
4) Identify which of the following are atomic sentences.
a) p is even
b) p is either even or odd.
c) if p
d) x = 7
e) 5 = (6 - 1)
5) When is a sentence in FOL satisfiable (give the definition of satisfiable)?
Is the sentence (p & ~p) satisfiable, according to this definition?
6) Give a definition of valid argument using possible worlds.
7) Give the semantics for the connective "->"
8) Show that the argument from no premises to (p -> q) -> (~q -> ~p)
is valid: a) with a truth table, b) with a proof in the natural deduction system ND.
9) I have 24 socks in my draw, 12 of which are blue and 12 of which are brown. When I open the draw in the morning it is too dark to see and I don't want to turn on the light to bother my wife, so I take some socks downstairs and examine them there. Using argument by cases, prove that the largest number of socks I need to take to guarantee I will have a matched pair is three.
10) Draw a Tarski's World like grid that is 3x3. Create a world in which sentences 1 - 3 are true but 4 is false.
1) a is a large cube that is in front of b, which is a tetrahedron.
2) if b is large then c is small
3) b is a small cube
4) c is a large tetrahedron.