Section Exam 1 Study Guide

Peter is not tall and Robert is not skinny. You must be in row 6 in the truth table above.

Suppose you only had 5 coins of each denomination. This means you have 5 pennies, 5 nickels, 5 dimes and 5 quarters. This is a total of 20 coins. But you have more than 20 coins, so you must have more than 5 of at least one type.

You need 10 coins. You could have 3 pennies, 3 nickels, and 3 dimes. The 10th coin must either be a quarter, giving you 4 coins that are all different, or else a 4th penny, nickel or dime. To prove this, assume you don’t have 4 coins that are all the same or all different. In particular, this says that you only have 3 coin types, and each of those types can only contain 3 coins, for a total of 9 coins, which is less than 10.

Let \(G\) be an arbitrary graph. Assume \(G\) is \(3\)-connected. Etc, etc etc. Therefore \(G\) is Hamiltonian.

Let \(G\) be an arbitrary graph. Assume \(G\) is not Hamiltonian. Etc, etc, etc. Therefore \(G\) is not 3-connected.

Let \(G\) be an arbitrary graph. Assume \(G\) is 3-connected and also not Hamiltonian. Etc, etc, etc. This is a contradiction.

The negation is \(\exists x \forall y (x \ne y \wedge \neg P(x,y) \wedge \neg P(y,x))\text{.}\)

This is a true statement, but for a rather silly reason. In fact, if you look at the negation, it is claiming that there is some positive integer that is not equal to any positive integer. But every integer is equal to itself.

This makes a lot more sense. It is claiming that for every positive integers, there is some different integer that is either a multiple of it or it is a multiple of. In fact, we can prove this is true as follows: Let \(x\) be a positive integer. Pick \(y = 2 x\text{.}\) Then \(x \ne y\) and \(y\) is a multiple of \(x\) (so \(P(y,x)\) is true).

The original statement is true always, under any domain of discourse and any interpretation of \(P(x,y)\text{.}\) This is because we can always just let \(x = y\text{.}\) The second statement is not always true. For example, our domain of discourse could contain only a single number. Or, we could take the domain of discourse to be all positive integers but let \(P(x,y)\) mean \(x = y\text{.}\)

Another way to say this: the original statement is a law of logic, but the second statement is not.

Claiming that all prime numbers are odd is the same as claiming that for all number, if the number is prime, then the number is odd. So you would write this as \(\forall n (P(n) \imp O(n))\text{.}\)

To say that not all primes are odd means that some primes are not odd. This is written \(\exists n (P(n) \land \neg O(n))\text{.}\) This makes sense since the negation of an implication \(P \imp Q\) is the conjunction \(P \land \neg Q\text{.}\)

We have that \(P(6)\) is false and \(O(6)\) is false. This makes \(P(6) \imp O(6)\) true, \(P(6) \land O(6)\) false, \(P(6) \imp \neg O(6)\) true, and \(P(6) \land \neg O(6)\) false.

No matter what, you cannot prove a universal statement true with one example. To prove the negation, we would need to find an \(n\) for which \(P(n) \land \neg O(n)\) was true, and 6 is not such an \(n\text{,}\) so this doesn’t prove anything.

We have that \(P(2)\) is true and \(O(2)\) is false. This makes \(P(2) \imp O(2)\) false, \(P(2) \land O(2)\) false, \(P(2) \imp \neg O(2)\) true, and \(P(2) \land \neg O(2)\) true.

This does prove the negation, since the negation is an existential statement. To prove it, we only need to find one \(n\) that makes the negation true; an \(n\) for which \(P(n) \land \neg O(n)\) is true, and 2 is such an \(n\text{.}\) Note also that \(P(2) \imp O(2)\) is false, so it is not true that \(P(n) \imp O(n)\) is true for all \(n\)

We will use a direct proof. Let \(a,b \in A\) and suppose \(R(a,b)\text{.}\) Then \(\mid a - b \mid \lt 3\text{.}\) This means that \(a\) and \(b\) are less than 3 apart, so are not \(a = 1\) and \(b = 4\text{.}\) But then \(b\) and \(a\) are less than 3 apart. Put another way, we have \(\mid b - a \mid = \mid -(a - b) \mid = \mid a - b \mid \lt 3\text{,}\) so \(R(b,a)\text{.}\) Since \(a\) and \(b\) were arbitrary, this shows that \(R\) is symmetric.

If we take any domain of discourse with at least two elements and let \(R(x,y)\) be the relation \(x \lt y\text{,}\) then \(R\) is not symmetric. For example, \(1 \lt 2\) but \(2 \not \lt 1\text{.}\)

The converse: For all sets \(A\) and \(B\text{,}\) if \(\card{A \cup B} = 2\card{A}\text{,}\) then \(\card{A} = \card{B} \text{.}\)

The contrapositive: For all sets \(A\) and \(B\text{,}\) if \(|A \cup B| \ne 2|A|\) then \(|A| \ne |B|\text{.}\)

The original statement is false. That means that there \emph{exists} sets \(A\) and \(B\) such that \(\card{A} = \card{B} \) but \(\card{A \cup B} \ne 2\card{A}\text{.}\) We can prove this by giving an example of such sets: \(A = \{1,2\}\) and \(B= \{2,3\}\text{.}\) These sets have the same cardinality, but \(A \cup B = \{1,2,3\}\) has cardinality 3, not 4.

The converse is false as well. Take \(A = \{1,2\}\) and \(B = \{2,3,4\}\text{.}\) Now we have \(|A \cup B| = 4 = 2|A|\) but \(\card{A} = 2\) and \(\card{B} = 3\text{.}\)

The new statement is about specific sets. For these sets, \(|A| \ne |B|\text{,}\) so the hypothesis of the implication is false. That makes the entire statement true automatically (even though the conclusion is false). This one example does not prove that the original implication is true (after all, it is not). It also cannot prove that the original statement is false, as it is not a counterexample.