Math 200, homework 1         due 9/12/02

Since a number of you have been unable to obtain the book yet, I have transcribed the following problems from the text. I won't do this often, so get a copy of the book as soon as you can.

(2)

For each of the following, state whether it is a proposition, with a brief explanation. If you believe that a particular case is borderline, provide brief pros and cons for whether it should be considered a proposition. For those which are propositions, determine which are true and which are false, if possible.

1. 10 is a prime number.
2. Are there any even prime numbers?
3. Turn off that music or I'll scream.
4. Life is good.
5. 3+5.
6. The number $\pi$ is bigger than 4.
7. Benjamin Franklin had many friends.
8. The Chicago Cubs will win the World Series in the year 2106.
9. I like olives but not very much.
10. Goldbach's conjecture is true. (This was described in Chapter 1.)

(3)

Determine whether each of the following is a tautology, a contradiction, or neither. If you can determine answers by commonsense logic, do so; otherwise, construct truth tables.

1. $\mbox{$\sim$}(P \mbox{ $\wedge$ }Q) \mbox{ $\Rightarrow$ }\mbox{$\sim$}P \mbox{ $\wedge$ }\mbox{$\sim$}Q$
2. $\mbox{$\sim$}P \mbox{ $\wedge$ }\mbox{$\sim$}Q \mbox{ $\Rightarrow$ }\mbox{$\sim$}(P \mbox{ $\wedge$ }Q)$
3. $(P \mbox{ $\Leftrightarrow$ }Q) \mbox{ $\Leftrightarrow$ }(Q \mbox{ $\Leftrightarrow$ }P)$
4. $(P \mbox{ $\Rightarrow$ }Q) \mbox{ $\Leftrightarrow$ }(Q \mbox{ $\Rightarrow$ }P)$
5. $[(P \mbox{ $\vee$ }Q) \mbox{ $\vee$ }R] \mbox{ $\Leftrightarrow$ }[P \mbox{ $\vee$ }(Q \mbox{ $\vee$ }R)]$
6. $[(P \mbox{ $\vee$ }Q) \mbox{ $\wedge$ }R] \mbox{ $\Leftrightarrow$ }[P \mbox{ $\vee$ }(Q \mbox{ $\wedge$ }R)]$

(4)

Determine whether each of the following pairs of statements are propropositionally equvalent to each other. If you can determine answers by commonsense logic, do so; otherwise, construct truth tables.

1. $P \mbox{ $\wedge$ }Q$ and $Q \mbox{ $\wedge$ }P$
2. $P$ and $\mbox{$\sim$}\mbox{$\sim$}P$
3. $\mbox{$\sim$}(P \mbox{ $\vee$ }Q)$ and $\mbox{$\sim$}P \mbox{ $\vee$ }\mbox{$\sim$}Q$
4. $\mbox{$\sim$}(P \mbox{ $\vee$ }Q)$ and $\mbox{$\sim$}P \mbox{ $\wedge$ }\mbox{$\sim$}Q$
5. $P \mbox{ $\Rightarrow$ }Q$ and $Q \mbox{ $\Rightarrow$ }P$
6. $\mbox{$\sim$}(P \mbox{ $\Rightarrow$ }Q)$ and $\mbox{$\sim$}P \mbox{ $\Rightarrow$ }\mbox{$\sim$}Q$
7. $P \mbox{ $\Leftrightarrow$ }Q$ and $(P \mbox{ $\wedge$ }Q) \mbox{ $\vee$ }\mbox{$\sim$}(P\mbox{ $\vee$ }Q)$
8. $P \mbox{ $\wedge$ }(Q \mbox{ $\vee$ }R)$ and $(P \mbox{ $\wedge$ }Q) \mbox{ $\vee$ }R$
9. $P \mbox{ $\wedge$ }(Q \mbox{ $\wedge$ }R)$ and $(P \mbox{ $\wedge$ }Q) \mbox{ $\wedge$ }R$
10. $P \mbox{ $\Rightarrow$ }(Q \mbox{ $\Rightarrow$ }R)$ and $(P \mbox{ $\Rightarrow$ }Q) \mbox{ $\Rightarrow$ }R$
11. $P \mbox{ $\Leftrightarrow$ }(Q \mbox{ $\Leftrightarrow$ }R)$ and $(P \mbox{ $\Leftrightarrow$ }Q) \mbox{ $\Leftrightarrow$ }R$

(8)

Recall the discussion of the inclusive or and the exclusive or. Let the symbol $\mbox{ \underline{$\vee$} }$ represent the latter.

1. Construct the truth table for $P\mbox{ \underline{$\vee$} }Q$.
2. Write a statement using our five basic connectives that is equivalent to $P\mbox{ \underline{$\vee$} }Q$.
3. Write a statement using only the connectives $\sim$,  $\wedge$ , and $\mbox{ \underline{$\vee$} }$ that is equivalent to $P \mbox{ $\vee$ }Q$.
4. Make up an English sentence in which you feel the word ``or'' should be interpreted inclusively.
5. Make up an English sentence in which you feel the word ``or'' should be interpreted exclusively.
6. Make up an English sentence in which you feel the word ``or'' can be interpreted either way.

(10)

For each of the following statements, introduce a propositional variable for each of its atomic substatements, and then use these variables and connectives to write the most accurate symbolic translation of the original statement.

1. I need to go to Oxnard and Lompoc.
2. If a number is even and bigger than 2, it's not prime.
3. You're damned if you do and damned if you don't.
4. If you order from the dinner menu, you get a soup or a salad, an entree, and a beverage or dessert. (Be careful with the word ``or'' in this one.)
5. If it doesn't rain in the next week, we won't have vegetables or flowers, but if it does, we'll at least have flowers.
6. No shoes, no shirt, no service. (Of course, this is a highly abbreviated sentence. You have to interpret it properly.)
7. Men or women may apply for this job. (Be careful; this one's a bit tricky.)

(11)

(a)

If a symbolic statement has just one propositional variable (say $P$), how many lines are in its truth table?

(b)

How many different possible truth functions are there for such a statement? That is, in how many ways can the output column of such a truth table be filled in? Explain.

*(c)

Repeat parts (a) and (b) for a symbolic statement with two propositional variables $P$ and $Q$. Explain.

*(d)

On the basis of the previous parts of this problem, make conjectures that generalize them to a symbolic statement with an arbitrary number $n$ of propositional variables.