3.E: Symbolic Logic and Proofs (Exercises)

$\def\d{\displaystyle}$
$\newcommand{\f}[1]{\mathfrak #1}$
$\newcommand{\s}[1]{\mathscr #1}$
$\def\N{\mathbb N}$
$\def\B{\mathbf{B}}$
$\def\circleA{(-.5,0) circle (1)}$
$\def\Z{\mathbb Z}$
$\def\circleAlabel{(-1.5,.6) node[above]{$A$}}$
$\def\Q{\mathbb Q}$
$\def\circleB{(.5,0) circle (1)}$
$\def\R{\mathbb R}$
$\def\circleBlabel{(1.5,.6) node[above]{$B$}}$
$\def\C{\mathbb C}$
$\def\circleC{(0,-1) circle (1)}$
$\def\F{\mathbb F}$
$\def\circleClabel{(.5,-2) node[right]{$C$}}$
$\def\A{\mathbb A}$
$\def\twosetbox{(-2,-1.5) rectangle (2,1.5)}$
$\def\X{\mathbb X}$
$\def\threesetbox{(-2,-2.5) rectangle (2,1.5)}$
$\def\E{\mathbb E}$
$\def\O{\mathbb O}$
$\def\U{\mathcal U}$
$\def\pow{\mathcal P}$
$\def\inv{^{-1}}$
$\def\nrml{\triangleleft}$
$\def\st{:}$
$\def\~{\widetilde}$
$\def\rem{\mathcal R}$
$\def\sigalg{$\sigma$-algebra }$
$\def\Gal{\mbox{Gal}}$
$\def\iff{\leftrightarrow}$
$\def\Iff{\Leftrightarrow}$
$\def\land{\wedge}$
$\def\And{\bigwedge}$
$\def\entry{\entry}$
$\def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}$
$\def\Vee{\bigvee}$
$\def\VVee{\d\Vee\mkern-18mu\Vee}$
$\def\imp{\rightarrow}$
$\def\Imp{\Rightarrow}$
$\def\Fi{\Leftarrow}$
$\def\var{\mbox{var}}$
$\def\Th{\mbox{Th}}$
$\def\entry{\entry}$
$\def\sat{\mbox{Sat}}$
$\def\con{\mbox{Con}}$
$\def\iffmodels{\bmodels\models}$
$\def\dbland{\bigwedge \!\!\bigwedge}$
$\def\dom{\mbox{dom}}$
$\def\rng{\mbox{range}}$
$\def\isom{\cong}$
$\DeclareMathOperator{\wgt}{wgt}$
$\newcommand{\vtx}[2]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2]{}}$
$\newcommand{\va}[1]{\vtx{above}{#1}}$
$\newcommand{\vb}[1]{\vtx{below}{#1}}$
$\newcommand{\vr}[1]{\vtx{right}{#1}}$
$\newcommand{\vl}[1]{\vtx{left}{#1}}$
$\renewcommand{\v}{\vtx{above}{}}$
$\def\circleA{(-.5,0) circle (1)}$
$\def\circleAlabel{(-1.5,.6) node[above]{$A$}}$
$\def\circleB{(.5,0) circle (1)}$
$\def\circleBlabel{(1.5,.6) node[above]{$B$}}$
$\def\circleC{(0,-1) circle (1)}$
$\def\circleClabel{(.5,-2) node[right]{$C$}}$
$\def\twosetbox{(-2,-1.4) rectangle (2,1.4)}$
$\def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}$
$\def\ansfilename{practice-answers}$
$\def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }$
$\renewcommand{\bar}{\overline}$
$\newcommand{\card}[1]{\left| #1 \right|}$
$\newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}$
$\newcommand{\lt}{<}$
$\newcommand{\gt}{>}$
$\newcommand{\amp}{&}$

$\newcommand{\hexbox}[3]{ \def\x{-cos{30}*\r*#1+cos{30}*#2*\r*2} \def\y{-\r*#1-sin{30}*\r*#1} \draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle; \draw (\x,\y) node{#3}; }$

$\renewcommand{\bar}{\overline}$
$\newcommand{\card}[1]{\left| #1 \right|}$
$\newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}$
$\newcommand{\lt}{<}$
$\newcommand{\gt}{>}$
$\newcommand{\amp}{&}$

3.1: Propositional Logic

1

Consider the statement about a party, “If it's your birthday or there will be cake, then there will be cake.”

1. Translate the above statement into symbols. Clearly state which statement is $P$ and which is $Q\text{.}$
2. Make a truth table for the statement.
3. Assuming the statement is true, what (if anything) can you conclude if there will be cake?
4. Assuming the statement is true, what (if anything) can you conclude if there will not be cake?
5. Suppose you found out that the statement was a lie. What can you conclude?

Solution

1. $P\text{:}$ it's your birthday; $Q\text{:}$ there will be cake. $(P \vee Q) \imp Q$
2. Hint: you should get three T's and one F.
3. Only that there will be cake.
4. It's NOT your birthday!
5. It's your birthday, but the cake is a lie.

2

Make a truth table for the statement $(P \vee Q) \imp (P \wedge Q)\text{.}$

Solution

$P$	$Q$	$(P \vee Q) \imp (P \wedge Q)$
T	T	T
T	F	F
F	T	F
F	F	T

3

Make a truth table for the statement $\neg P \wedge (Q \imp P)\text{.}$ What can you conclude about $P$ and $Q$ if you know the statement is true?

Solution

$P$	$Q$	$\neg P \wedge (Q \imp P)$
T	T	F
T	F	F
F	T	F
F	F	T

If the statement is true, then both $P$ and $Q$ are false.

4

Make a truth table for the statement $\neg P \imp (Q \wedge R)\text{.}$

Hint

Like above, only now you will need 8 rows instead of just 4.

5

Determine whether the following two statements are logically equivalent: $\neg(P \imp Q)$ and $P \wedge \neg Q\text{.}$ Explain how you know you are correct.

Solution

Make a truth table for each and compare. The statements are logically equivalent.

6

Are the statements $P \imp (Q\vee R)$ and $(P \imp Q) \vee (P \imp R)$ logically equivalent?

7

Simplify the following statements (so that negation only appears right before variables).

1. $\neg(P \imp \neg Q)\text{.}$
2. $(\neg P \vee \neg Q) \imp \neg (\neg Q \wedge R)\text{.}$
3. $\neg((P \imp \neg Q) \vee \neg (R \wedge \neg R))\text{.}$
4. It is false that if Sam is not a man then Chris is a woman, and that Chris is not a woman.

Answer

1. $P \wedge Q\text{.}$
2. $(\neg P \vee \neg R) \imp (Q \vee \neg R)$ or, replacing the implication with a disjunction first: $(P \wedge Q) \vee (Q \vee \neg R)\text{.}$
3. $(P \wedge Q) \wedge (R \wedge \neg R)\text{.}$ This is necessarily false, so it is also equivalent to $P \wedge \neg P\text{.}$
4. Either Sam is a woman and Chris is a man, or Chris is a woman.

8

Use De Morgan's Laws, and any other logical equivalence facts you know to simplify the following statements. Show all your steps. Your final statements should have negations only appear directly next to the sentence variables or predicates ($P\text{,}$ $Q\text{,}$ $E(x)\text{,}$ etc.), and no double negations. It would be a good idea to use only conjunctions, disjunctions, and negations.

1. $\neg((\neg P \wedge Q) \vee \neg(R \vee \neg S))\text{.}$
2. $\neg((\neg P \imp \neg Q) \wedge (\neg Q \imp R))$ (careful with the implications).

9

Tommy Flanagan was telling you what he ate yesterday afternoon. He tells you, “I had either popcorn or raisins. Also, if I had cucumber sandwiches, then I had soda. But I didn't drink soda or tea.” Of course you know that Tommy is the world's worst liar, and everything he says is false. What did Tommy eat?

Justify your answer by writing all of Tommy's statements using sentence variables ($P, Q, R, S, T$), taking their negations, and using these to deduce what Tommy actually ate.

10

Determine if the following deduction rule is valid:

	$P \vee Q$
	$\neg P$
$\therefore$	$Q$

Solution

The deduction rule is valid. To see this, make a truth table which contains $P \vee Q$ and $\neg P$ (and $P$ and $Q$ of course). Look at the truth value of $Q$ in each of the rows that have $P \vee Q$ and $\neg P$ true.

11

Determine if the following is a valid deduction rule:

	$P \imp (Q \vee R)$
	$\neg(P \imp Q)$
$\therefore$	$R$

12

Determine if the following is a valid deduction rule:

	$(P \wedge Q) \imp R$
	$\neg P \vee \neg Q$
$\therefore$	$\neg R$

13

Can you chain implications together? That is, if $P \imp Q$ and $Q \imp R\text{,}$ does that means the $P \imp R\text{?}$ Can you chain more implications together? Let's find out:

1. Prove that the following is a valid deduction rule:

   	$P \imp Q$
   	$Q \imp R$
   $\therefore$	$P \imp R$

2. Prove that the following is a valid deduction rule for any $n \ge 2\text{:}$

   	$P_1 \imp P_2$
   	$P_2 \imp P_3$
   	$\vdots$
   	$P_{n-1} \imp P_n$
   $\therefore$	$P_1 \imp P_n\text{.}$

   I suggest you don't go through the trouble of writing out a $2^n$ row truth table. Instead, you should use part (a) and mathematical induction.

14

We can also simplify statements in predicate logic using our rules for passing negations over quantifiers, and then applying propositional logical equivalence to the “inside” propositional part. Simplify the statements below (so negation appears only directly next to predicates).

1. $\neg \exists x \forall y (\neg O(x) \vee E(y))\text{.}$
2. $\neg \forall x \neg \forall y \neg(x \lt y \wedge \exists z (x \lt z \vee y \lt z))\text{.}$
3. There is a number $n$ for which no other number is either less $n$ than or equal to $n\text{.}$
4. It is false that for every number $n$ there are two other numbers which $n$ is between.

Solution

1. $\forall x \exists y (O(x) \wedge \neg E(y))\text{.}$
2. $\exists x \forall y (x \ge y \vee \forall z (x \ge z \wedge y \ge z))\text{.}$
3. There is a number $n$ for which every other number is strictly greater than $n\text{.}$
4. There is a number $n$ which is not between any other two numbers.

15

Suppose $P$ and $Q$ are (possibly molecular) propositional statements. Prove that $P$ and $Q$ are logically equivalent if and only if $P \iff Q$ is a tautology.

Hint

What do these concepts mean in terms of truth tables?

16

Suppose $P_1, P_2, \ldots, P_n$ and $Q$ are (possibly molecular) propositional statements. Suppose further that

	$P_1$
	$P_2$
	$\vdots$
	$P_n$
$\therefore$	$Q$

is a valid deduction rule. Prove that the statement

$$\begin{equation*} (P_1 \wedge P_2 \wedge \cdots \wedge P_n) \imp Q \end{equation*}$$

is a tautology.

3.2: Proofs

1

Consider the statement “for all integers $a$ and $b\text{,}$ if $a + b$ is even, then $a$ and $b$ are even”

1. Write the contrapositive of the statement.
2. Write the converse of the statement.
3. Write the negation of the statement.
4. Is the original statement true or false? Prove your answer.
5. Is the contrapositive of the original statement true or false? Prove your answer.
6. Is the converse of the original statement true or false? Prove your answer.
7. Is the negation of the original statement true or false? Prove your answer.

Solution

1. For all integers $a$ and $b\text{,}$ if $a$ or $b$ is not even, then $a+b$ is not even.
2. For all integers $a$ and $b\text{,}$ if $a$ and $b$ are even, then $a+b$ is even.
3. There are numbers $a$ and $b$ such that $a+b$ is even but $a$ and $b$ are not both even.
4. False. For example, $a = 3$ and $b = 5\text{.}$ $a+b = 8\text{,}$ but neither $a$ nor $b$ are even.
5. False, since it is equivalent to the original statement.
6. True. Let $a$ and $b$ be integers. Assume both are even. Then $a = 2k$ and $b = 2j$ for some integers $k$ and $j\text{.}$ But then $a+b = 2k + 2j = 2(k+j)$ which is even.
7. True, since the statement is false.

2

Consider the statement: for all integers $n\text{,}$ if $n$ is even then $8n$ is even.

1. Prove the statement. What sort of proof are you using?
2. Is the converse true? Prove or disprove.

Solution

1. Direct proof.

   Proof

   Let $n$ be an integer. Assume $n$ is even. Then $n = 2k$ for some integer $k\text{.}$ Thus $8n = 16k = 2(8k)\text{.}$ Therefore $8n$ is even.

2. The converse is false. That is, there is an integer $n$ such that $8n$ is even but $n$ is odd. For example, consider $n = 3\text{.}$ Then $8n = 24$ which is even but $n = 3$ is odd.

3

Your “friend” has shown you a “proof” he wrote to show that $1 = 3\text{.}$ Here is the proof:

Proof

I claim that $1 = 3\text{.}$ Of course we can do anything to one side of an equation as long as we also do it to the other side. So subtract 2 from both sides. This gives $-1 = 1\text{.}$ Now square both sides, to get $1 = 1\text{.}$ And we all agree this is true.

What is going on here? Is your friend's argument valid? Is the argument a proof of the claim $1=3\text{?}$ Carefully explain using what we know about logic. Hint: What implication follows from the given proof?

4

Suppose you have a collection of 5-cent stamps and 8-cent stamps. We saw earlier that it is possible to make any amount of postage greater than 27 cents using combinations of both these types of stamps. But, let's ask some other questions:

1. What amounts of postage can you make if you only use an even number of both types of stamps? Prove your answer.
2. Suppose you made an even amount of postage. Prove that you used an even number of at least one of the types of stamps.
3. Suppose you made exactly 72 cents of postage. Prove that you used at least 6 of one type of stamp.

5

Suppose that you would like to prove the following implication:

For all numbers $n\text{,}$ if $n$ is prime then $n$ is solitary.

Write out the beginning and end of the argument if you were to prove the statement,

1. Directly
2. By contrapositive
3. By contradiction

You do not need to provide details for the proofs (since you do not know what solitary means). However, make sure that you provide the first few and last few lines of the proofs so that we can see that logical structure you would follow.

6

Prove that $\sqrt 3$ is irrational.

Solution

Proof

Suppose $\sqrt{3}$ were rational. Then $\sqrt{3} = \frac{a}{b}$ for some integers $a$ and $b \ne 0\text{.}$ Without loss of generality, assume $\frac{a}{b}$ is reduced. Now

$$\begin{equation*} 3 = \frac{a^2}{b^2} \end{equation*}$$ $$\begin{equation*} b^2 3 = a^2 \end{equation*}$$

So $a^2$ is a multiple of 3. This can only happen if $a$ is a multiple of 3, so $a = 3k$ for some integer $k\text{.}$ Then we have

$$\begin{equation*} b^2 3 = 9k^2 \end{equation*}$$ $$\begin{equation*} b^2 = 3k^2 \end{equation*}$$

So $b^2$ is a multiple of 3, making $b$ a multiple of 3 as well. But this contradicts our assumption that $\frac{a}{b}$ is in lowest terms.

Therefore, $\sqrt{3}$ is irrational.

7

Consider the statement: for all integers $a$ and $b\text{,}$ if $a$ is even and $b$ is a multiple of 3, then $ab$ is a multiple of 6.

1. Prove the statement. What sort of proof are you using?
2. State the converse. Is it true? Prove or disprove.

8

Prove the statement: For all integers $n\text{,}$ if $5n$ is odd, then $n$ is odd. Clearly state the style of proof you are using.

Solution

We will prove the contrapositive: if $n$ is even, then $5n$ is even.

Proof

Let $n$ be an arbitrary integer, and suppose $n$ is even. Then $n = 2k$ for some integer $k\text{.}$ Thus $5n = 5\cdot 2k = 10k = 2(5k)\text{.}$ Since $5k$ is an integer, we see that $5n$ must be even. This completes the proof.

9

Prove the statement: For all integers $a\text{,}$ $b\text{,}$ and $c\text{,}$ if $a^2 + b^2 = c^2\text{,}$ then $a$ or $b$ is even.

10

Prove: $x=y$ if and only if $xy=\dfrac{(x+y)^2}{4}\text{.}$ Note, you will need to prove two “directions” here: the “if” and the “only if” part.

11

The game TENZI comes with 40 six-sided dice (each numbered 1 to 6). Suppose you roll all 40 dice.

1. Prove that there will be at least seven dice that land on the same number.
2. How many dice would you have to roll before you were guaranteed that some four of them would all match or all be different? Prove your answer.

Solution

1. This is an example of the pigeonhole principle. We can prove it by contrapositive.

   Proof

   Suppose that each number only came up 6 or fewer times. So there are at most six 1's, six 2's, and so on. That's a total of 36 dice, so you must not have rolled all 40 dice.

2. We can have 9 dice without any four matching or any four being all different: three 1's, three 2's, three 3's. We will prove that whenever you roll 10 dice, you will always get four matching or all being different.

   Proof

   Suppose you roll 10 dice, but that there are NOT four matching rolls. This means at most, there are three of any given value. If we only had three different values, that would be only 9 dice, so there must be 4 different values, giving 4 dice that are all different.

12

Prove that $\log(7)$ is irrational.

Solution

We give a proof by contradiction.

Proof

Suppose, contrary to stipulation that $\log(7)$ is rational. Then $\log(7) = \frac{a}{b}$ with $a$ and $b \ne 0$ integers. By properties of logarithms, this implies

$$\begin{equation*} 7 = 10^{\frac{a}{b}} \end{equation*}$$

Equivalently,

$$\begin{equation*} 7^b = 10^a \end{equation*}$$

But this is impossible as any power of 7 will be odd while any power of 10 will be even. Therefore, $\log(7)$ is irrational.

13

Prove that there are no integer solutions to the equation $x^2 = 4y + 3\text{.}$

14

Prove that every prime number greater than 3 is either one more or one less than a multiple of 6.

Hint

Prove the contrapositive by cases.

15

For each of the statements below, say what method of proof you should use to prove them. Then say how the proof starts and how it ends. Bonus points for filling in the middle.

1. There are no integers $x$ and $y$ such that $x$ is a prime greater than 5 and $x = 6y + 3\text{.}$
2. For all integers $n\text{,}$ if $n$ is a multiple of 3, then $n$ can be written as the sum of consecutive integers.
3. For all integers $a$ and $b\text{,}$ if $a^2 + b^2$ is odd, then $a$ or $b$ is odd.

Solution

1. Proof by contradiction. Start of proof: Assume, for the sake of contradiction, that there are integers $x$ and $y$ such that $x$ is a prime greater than 5 and $x = 6y + 3\text{.}$ End of proof: … this is a contradiction, so there are no such integers.
2. Direct proof. Start of proof: Let $n$ be an integer. Assume $n$ is a multiple of 3. End of proof: Therefore $n$ can be written as the sum of consecutive integers.
3. Proof by contrapositive. Start of proof: Let $a$ and $b$ be integers. Assume that $a$ and $b$ are even. End of proof: Therefore $a^2 + b^2$ is even.

16

A standard deck of 52 cards consists of 4 suites (hearts, diamonds, spades and clubs) each containing 13 different values (Ace, 2, 3, …, 10, J, Q, K). If you draw some number of cards at random you might or might not have a pair (two cards with the same value) or three cards all of the same suit. However, if you draw enough cards, you will be guaranteed to have these. For each of the following, find the smallest number of cards you would need to draw to be guaranteed having the specified cards. Prove your answers.

1. Three of a kind (for example, three 7's).
2. A flush of five cards (for example, five hearts).
3. Three cards that are either all the same suit or all different suits.

17

Suppose you are at a party with 19 of your closest friends (so including you, there are 20 people there). Explain why there must be least two people at the party who are friends with the same number of people at the party. Assume friendship is always reciprocated.

18

Your friend has given you his list of 115 best Doctor Who episodes (in order of greatness). It turns out that you have seen 60 of them. Prove that there are at least two episodes you have seen that are exactly four episodes apart.

19

Suppose you have an $n\times n$ chessboard but your dog has eaten one of the corner squares. Can you still cover the remaining squares with dominoes? What needs to be true about $n\text{?}$ Give necessary and sufficient conditions (that is, say exactly which values of $n$ work and which do not work). Prove your answers.

20

What if your $n\times n$ chessboard is missing two opposite corners? Prove that no matter what $n$ is, you will not be able to cover the remaining squares with dominoes.