Discrete Mathematics: Activities and Exercises

1. Statements.

Consider the following two statements:

• \(P = \) The rent increases.

• \(Q = \) I will renew my lease.

Express the following statements in words.

1. \(\displaystyle P \vee Q\)

2. \(\displaystyle (\neg P) \wedge Q\)

3. \(\displaystyle (\neg P) \Rightarrow Q\)

4. \(\displaystyle P \Rightarrow (\neg Q)\)

Solution.

2. Implications.

Each of the following statements is an implication \(P \Rightarrow Q\text{.}\) For each statement, indicate what \(P\) and \(Q\) are, then rephrase the statment as "if \(P\) then \(Q\text{.}\)"

(Hint: an implication \(P \Rightarrow Q\) is only false when \(P\) is true and \(Q\) is false. Thus, it may help you to imagine what it would mean for each of these statements to be false.)

1. I think, therefore I am.

2. You can drive from Minneapolis to Madison if your car has a full tank of gas.

3. I’m only going to my class reunion if I get a promotion at work.

4. I will take you to the pool as long as you do your afternoon chores.

5. Passing Linear Algebra is necessary to register for Algebraic Structures.

Solution.

3. Two Truth Tables.

1. Fill in this truth table.

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

   Solution.

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

2. Now fill in this truth table.

   \begin{equation*} \begin{array}{c|c|c|c|c} P & Q & \neg P & \neg Q & \neg P \vee \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} P & Q & \neg P & \neg Q & \neg P \vee \neg Q \\ \hline T & T & F& F& F \\ T & F & F & T & T\\ F & T & T & F & T\\ F & F & T & T & T \\ \end{array} \end{equation*}

3. Look at the last column of each of the two tables above. What do you conclude? Write a mathematical statement (using symbols) that summarizes your observation. Solution.

   These two statements are equivalent. In other words, \[ \neg (P \wedge Q) \Longleftrightarrow \neg P \vee \neg Q. \]

4. Truth Table for \(\neg (P \vee Q)\).

Fill in the following truth table. Using the previous problems as inspiration, find another compound statement that is equivalent to \(\neg (P \vee Q)\text{.}\) Add columns to your truth table to show that you are correct.

Solution.

5. The Effect of Negation.

Look back at the last two problems. What is the effect of negation on the AND operator? The OR operator? Solution.