Strategy#1 Reexpress the goal in some other form(possibly in a positive statement) and the use one of the other proof strategies. Its easy to do if the statement is more than just negation of a proposition but a complex statement involving logical connectives.
Stragety#2 This is called Proof By Contradiction. Suppose P and reach a contradiction. In many cases it can mean contradicting a given or contradicting an universal(or somehow known) fact.
Two very useful rules of inferences:
When $P \rightarrow Q$ is given
1. And also $P$. Then you can infer that $Q$ is also true. This is called modus ponens.
2. And also $\lnot Q$. Since $P \rightarrow Q$ $\equiv$ $\lnot Q \rightarrow \lnot P$, So by using modus ponens $\lnot P$ is also true. This is called modus tollens.
===========================================================================================
Ex-1(a)Suppose P is true; It is given that $P \rightarrow Q$ is true so Q is also true. It is also given that $Q \rightarrow R$ is true, so R is also true. Hence If P is true then R is also true, and Thus $P \rightarrow R$ is true.
Ex-1(b) Suppose P is true, and Q is also true. Now we want to prove that R is true too. We'll prove it by contradiction. Let say $\lnot R$ is true, then $P \rightarrow \lnot Q$ is also true because $\lnot R \rightarrow (P \rightarrow \lnot Q)$ is given to be true. Now since $P \rightarrow \lnot Q$ is true and P is assumed to be true, so $\lnot Q$ should also be true, but we assumed Q is true, so we reached a contradiction by assuming $\lnot R$ is true so R must be true. Hence $P \rightarrow (Q \rightarrow R)$ is true.
Ex-2(a) Suppose P is true, now we want to prove that $\lnot R$ is true.
Let us try to prove it by contradiction. Assume that R is also true. It is given that $P \rightarrow Q$ is true, so Q must be true. It is also given that $R \rightarrow \lnot Q$ is true and with our assumption R is also true so $\lnot Q$ must be true, which is a contradiction as we just proved Q to be true. And hence, R must be false, that is $\lnot R$ is true.
Ex-2(b) Suppose Q is true, we need to prove that $\lnot (Q \rightarrow \lnot P)$ is also true. We'll prove it by contradiction.
Let $Q \rightarrow \lnot P$ is true
=> $\lnot P$ is true(since Q is assumed to be true), but P is given to be true. So we reached a contradiction and hence $Q \rightarrow \lnot P$ must be false and thus $\lnot (Q \rightarrow \lnot P)$ is true.
Ex-3 Suppose $x \in A$, then $x \in C$ as $A \subseteq C$. Since B and C are disjoin so $x \notin B$.
Ex-4 Suppose $x \in C$. Since $A \setminus B$ is disjoint from C, so $x \notin A \setminus B$. That means $\lnot x \in A \setminus B$
=> $\lnot( x \in A \land \lnot x \in B)$
=> $x \notin A \lor x \in B$
=> $x \in A \rightarrow x \in B$
Since $x \in A$ is given so by modus ponens, $x \in B$
Ex-5 To prove it by contradiction, we'll assume the opposite that is $a \in A \setminus B$
=> $a \in A \land a \notin B$
It follows that $a \notin B$ and $a \in A$. It is given that $a \in C$ and it is also given that $A \cap C \subseteq B$, so $a \in A \cap C \rightarrow a \in B$
=> $a \in A \land a \in C \rightarrow a \in B$, so $a \in B$ and we have a contradiction.
Ex-6 Suppose $a \notin C$. Since $A \subseteq B$ and $a \in A$, so $a \in B$.
It is also given that $a \notin B \setminus C$
=> $\lnot a \in B \setminus C$
=> $\lnot (a \in B \land a \notin C)$
=> $a \notin B \lor a \in C$
=> $a \in B \rightarrow a \in C$
=> $a \notin C \rightarrow a \notin B$
Since we assumed $a \notin C$, therefore $a \notin B$ but we proved earlier that $a \in B$, and hence there is a contradiction, Thus $a \in C$.
Ex-7 Suppose y = 0; Substituting this in
y + x = 2y - x
=> 0 + x = 2(0) - x
=> x = -x
=> 2x = 0
=> x = 0
But x and y, both can not be zero; So $y \neq 0$.
Ex-8 Suppose $a < \frac{1}{a} < b < \frac{1}{b}$.
Since $a < \frac{1}{a}$, so it is easy enough to derive that $(a < -1) \lor (0 < a < 1)$ is True.
Now, if we prove that $0 < a < 1$ is False, then $a < -1$ has to be True.
We will prove by contradiction that $0 < a < 1$ is False.
Suppose $0 < a < 1$ and given that $\frac{1}{a} < b$
=> $b > 1$
However, since $b < \frac{1}{b}$, so $b > 1$ can not be True and we reached a contradiction.
Ex-9 Suppose $y \neq 0$, we want to prove that $x \neq 0$. Assume x = 0 and substituting it in
$x^2y = 2x + y$
=> $0 = 2(0) + y$
=> y = 0
which is a contradiction, Thus $x \neq 0$. So, If $y \neq 0$ then $x \neq 0$.
Ex-10 Suppose $y = \frac{3x^2 + 2y}{x^2 + 2}$.
=> $y(x^2 + 2) = 3x^2 + 2y$
=> $yx^2 + 2y = 3x^2 + 2y$
=> $yx^2 = 3x^2$
=> $yx^2 - 3x^2 = 0$
=> $(y - 3)x^2 = 0$
=> $y = 3 \lor x^2 = 0$
=> $x^2 \neq 0 \rightarrow y = 3$
Since $x \neq 0$, it follows that $x^2 \neq 0$ and therefore $y = 3$
Ex-11
(a) Assumption made, that is x = 3 and y = 8 is not negation of the goal to be proven which is $x \neq 3$ and $y \neq 8$
(b) x = 3 and y = 7 is a counterexample.
Ex-12
(a) The statement, "Since $x \notin B$ and $B \subseteq C$, $x \notin C$.", is not correct.
(b) One counterexample is
A = {1}
B = {2}
C = {1,2}
$1 \in A$ but $1 \notin B$
Ex-13
| P | Q | $\lnot Q$ | $P → Q$ | $(\lnot Q) \land (P → Q)$ | $\lnot P$ |
| T | T | F | T | F | F |
| F | T | F | T | F | T |
| T | F | T | F | F | F |
| F | F | T | T | T | T |
Notice, whenever $(\lnot Q) \land (P \rightarrow Q)$ is true, $\lnot P$ is also true. Hence, modus tollens is valid inference rule.
Ex-14
| P | Q | R | $Q → R$ | $P → (Q → R)$ | $P → \lnot Q$ | $\lnot R → (P → \lnot Q)$ |
| T | T | T | T | T | F | T |
| F | T | T | T | T | T | T |
| T | F | T | T | T | T | T |
| F | F | T | T | T | T | T |
| T | T | F | F | F | F | F |
| F | T | F | F | T | T | T |
| T | F | F | T | T | T | T |
| F | F | F | T | T | T | T |
Note that, truth values for $P \rightarrow (Q \rightarrow R)$ and $\lnot R \rightarrow (P \rightarrow \lnot Q)$ are exactly the same.
Ex-15,16 Trivial, passed
Ex-17 Let us try to replay the proof presented in example 3.2.2 with $y \neq 4$ and $x \neq 3$ interchanged. Here is how it looks...
Suppose $x^2 + y = 13$ and $x \neq 3$. Suppose $y = 4$. Substituting this into the equation $x^2 + y = 13$, we get $x^2 + 4 = 13$, so $x^2 = 9$, so $x = 3$ OR $x = -3$. Hence this modification can not be used to prove that If $x^2 + y = 13$ and $x \neq 3$ then $y \neq 4$.
This comment has been removed by the author.
ReplyDeleteEx-8
ReplyDeleteI'll give an alternative proof.
Proof: Suppose a < 1/a < b < 1/b, or in other words a < 1/a, 1/a < b, and b < 1/b. Since a < 1/a, it follows that a < -1 or 0 < a < 1. Suppose a >= -1. Since a < -1 or 0 < a < 1, and a >= -1, we can conclude 0 < a < 1. By exercise 6, p. 94, we get 1/a > 1. But then, since b > 1/a > 1, we conclude b > 1. Again, by exercise 6, p. 94, we get 1/b < 1. Then b < 1/b < 1, so b < 1. But this contradicts the fact that b > 1. Therefore, a < -1. Thus, if a < 1/a < b < 1/b then a < -1.
I did Q8 same as Stavros but I think this might be what the author was looking for.
ReplyDeleteSuppose a < 1/a < b < 1/b. Suppose a >= o. Clearly a cannot equal 0. So suppose a > 0. a < 1/a means 0 < a <1. Thus b > 1. But then 1/b < b, a contradiction. Therefore a < 0.
Suppose a < 0. Then for a < 1/a, only a < -1 satisfies this. Hence a < -1. Therefore if a < 1/a < b < 1/b then a < -1.
PS, how do I put latex on these posts?
Updating proof for Ex-8 as given by Stavros. Thanks.
ReplyDelete