Discrete Mathematics: Activities and Exercises

1. Implications.

1. Write down the contrapositive, converse and inverse of the implication: "if \(x < 3\) then \(x^2 < 9\text{.}\)" Which of these four statements are true? Which ones are false? Solution.

   • statement: \(x < 3\) then \(x^2 < 9\text{.}\) This is false, since \(-4 < 3\) and \((-4)^2 = 16 > 9\)

   • contrapositive: if \(x^2 \geq 9\) then \(x \geq 3\text{.}\) This is false for the same reason.

   • converse: if \(x^2 < 9\) then \(x < 3\text{.}\) This is true because the first statement forces \(-3 \leq x \leq 3\text{.}\)

   • inverse: if \(x \geq 3\) then \(x^2 \geq 9\) . This is true.

2. Write down the contrapositive, converse and inverse of the implication: "If it is warm and sunny then I go swimming." Solution.

   • statement: If it is warm and sunny then I go swimming.

   • contrapositive: If I do not go swimming then it is cold or it is cloudy.

   • converse: If I go swimming then it is warm and sunny.

   • inverse: If it is cold or it is cloudy then I do not go swimming.

2. Equivalent Statements.

1. Use a truth table to show that \(\neg (P \Rightarrow Q)\) is equivalent to \(P \wedge \neg Q\text{.}\)

   \begin{equation*} \begin{array}{c|c||c|c|c|c} P & Q & P \Rightarrow Q & \neg(P \Rightarrow Q) & \neg Q & P \wedge \neg Q \\ \hline T & T & & & & \\ T & F & & & & \\ F & T & & & &\\ F & F & & & &\\ \end{array} \end{equation*}

   Solution.

   \begin{equation*} \begin{array}{c|c||c|c|c|c} P & Q & P \Rightarrow Q & \neg(P \Rightarrow Q) & \neg Q & P \wedge \neg Q \\ \hline T & T & T & F & F& F\\ T & F & F &T & T& T\\ F & T & T &F & F&F\\ F & F & T &F & T &F\\ \end{array} \end{equation*}

   The columns for \(\neg(P \Rightarrow Q) \) and \(P \wedge \neg Q\) are identical. So these statements are equivalent.

2. Use a truth table to show that \(P \Leftrightarrow Q\) is equivalent to \((P \wedge Q) \vee (\neg P \wedge \neg Q)\text{.}\)

   \begin{equation*} \begin{array}{c|c||c|c|c|c|c} P & Q & P \Leftrightarrow Q & \neg P & \neg Q & P \wedge Q & \neg P \wedge \neg Q & (P \wedge Q) \vee (\neg P \wedge \neg Q)\\ \hline T & T & & & & & & \\ T & F & & & & & & \\ F & T & & & & & & \\ F & F & & & & & & \\ \end{array} \end{equation*}

   Solution.

   \begin{equation*} \begin{array}{c|c||c|c|c|c|c} P & Q & P \Leftrightarrow Q & \neg P & \neg Q & P \wedge Q & \neg P \wedge \neg Q & (P \wedge Q) \vee (\neg P \wedge \neg Q)\\ \hline T & T & T & F & F & T & F & T\\ T & F & F & F & T & F & F & F\\ F & T & F & T & F & F & F & F\\ F & F & T & T & T & F & T & T\\ \end{array} \end{equation*}

   The columns for \(\neg(P \Rightarrow Q) \) and \(P \wedge \neg Q\) are identical. So these statements are equivalent.

3. Two Logic Puzzles.

1. Each of the four cards below has a digit printed on one side and a letter printed on the other side.

   
   A classmate makes the following claim: "If there is a vowel on one side of a card then there is an odd number on the other side." Which cards must be turned over to check whether this statement is true? Solution.

   You must turn over the "E" card to ensure that there is an odd number, and you must turn over the "2" card to ensure that there is not a vowel on the other side.

2. Suppose that four women are drinking in a bar. The owner wants to enforce the rule that no one under twenty-one is allowed to drink alcohol. The owner asks each person to tell him either (1) what she is drinking, or (2) how old they are. Here are their truthful answers:

   Alice	Barbara	Clarice	Daria
   "I am drinking Coke."	"I am sixteen."	"I am drinking beer."	"I am twenty-five."

   Which of the people have to answer the additiona question (that they haven't answered yet) in order for the owners to ensure that the law is being observed? Solution.

   The owner must find out what Barbara is drinking, and the owner must find out the age of Clarice.

3. Which of the previous questions was easier, (a) or (b)? Why? Solution.

   Most people will find question (b) to be easier because it matches a context that we are already familiar with: the drinking age in the United States is 21. Meanwhile, the rule in part (a) is unfamiliar and we don't really know why the rule exists.

   But in fact, these two questions are variations of the same process: we are checking the validity of a statement of the form \(P \rightarrow Q\text{.}\) That also means that we have to check situations where \(\neg Q \rightarrow \neg P\) would apply.

4. Evaluating an Argument.

Determine the validity of the following arguments. Include a truth table to justify your conclusion.

1. If I stay up late at night, then I will be tired in the morning. I am tired this morning. Therefore, I stayed up late last night. Solution.

   Let \(P = \) "I stay up late" and let \(Q = \) "I am tired in the morning."

   \begin{equation*} \begin{array}{c|c|c|c|c} P & Q & P \rightarrow Q & Q \wedge (P \rightarrow Q) & \big( Q \wedge (P \rightarrow Q) \big) \rightarrow P \\ \hline T & T & T & T & T \\ T & F & F & F & T \\ F & T & T & T & F \\ F & F & T & F & T \\ \end{array} \end{equation*}

   The third line of the final column is false. Therefore the argument is not valid. This is because there are other reasons that I might be tired (perhaps I ran a marathon yesterday).

2. If I stay up late at night, then I will be tired in the morning. I am not tired this morning. Therefore, I did not stay up late last night. Solution.

   Once again, let \(P = \) "I stay up late" and let \(Q = \) "I am tired in the morning."

   \begin{equation*} \begin{array}{c|c|c|c|c|c|c} P & Q & P \rightarrow Q & \neg Q & \neg Q \wedge (P \rightarrow Q) & \neg P & \big( \neg Q \wedge (P \rightarrow Q) \big) \rightarrow \neg P \\ \hline T & T & T & F & F & F & T \\ T & F & F & T & F & F & T \\ F & T & T & F & T & T & T \\ F & F & T & T & F & T & T \\ \end{array} \end{equation*}

   The final column only contains true values. Therefore the argument is valid.

5. Evaluating Another Argument.

Determine the validity of the following argument. Include a truth table to justify your conclusion.

If I work hard, then I earn lots of money. If I earn lots of money, then I pay high taxes. Therefore, if I pay high taxes, then I have worked hard. Solution.