% Authors : the staff of CS70, Fall 2007, Berkeley % Acknowledgements : LaTeX source based on Chris Crutchfield's Spring 2006 % section notes. Borrowed material is cited in the text. \documentclass{amsart} \usepackage{fullpage} \setlength{\topmargin}{-0.25in} \setlength{\textheight}{9.5in} \usepackage{amsmath} \usepackage[mathscr]{eucal} \usepackage{amssymb} \usepackage{amsfonts} \usepackage{verbatim} \usepackage{enumerate} \newcommand\R{\mathbb{R}} \newcommand\N{\mathbb{N}} \newcommand\Z{\mathbb{Z}} \newcommand\setcond[2]{\left\{\,#1\,:\,#2\,\right\}} \newcommand{\solution}[1]{{\begin{tabular}{|p{5 in}|} \hline \textbf{Solutions:} \\ #1 \\ \hline \end{tabular}}} % THEOREMS ------------------------------------------------------- \newtheorem{thm}{Theorem} \newtheorem{cor}[thm]{Corollary} \newtheorem{lem}[thm]{Lemma} \newtheorem{prop}[thm]{Proposition} \theoremstyle{definition} \newtheorem{conj}[thm]{Conjecture} \newtheorem{thmnoproof}[thm]{Theorem} \newtheorem{defn}[thm]{Definition} \newtheorem{ex}[thm]{Exercise} \theoremstyle{remark} \newtheorem{rem}[thm]{Remark} \newtheorem{ques}[thm]{Question} \newtheorem{example}[thm]{Example} \numberwithin{equation}{section} \begin{document} \title{CS 70 Spring 2008 --- Discussion \#1}% \author{Luqman Hodgkinson, Aaron Kleinman, Min Xu} \date{\today} \thanks{\hfill The authors gratefully acknowledge the TA's of CS70 Past for the use of their previous notes: Assane Gueye, Vahab Pournaghshband, Alex Fabrikant, Chris Crutchfield, Amir Kamil, David Garmire, Lorenzo Orecchia, and Ben Rubinstein. Their notes form the basis for this handout.} \maketitle \section{Administrivia} \begin{enumerate} \item Course Information \begin{itemize} \item The first homework is {\bf due Thursday January 31st} at 5:00PM. You are encouraged to work on the homework in groups of 3-4, but write up your submission \emph{on your own}. Cite any external sources you use. \end{itemize} \item Discussion Information \begin{itemize} \item If you have a clash, it is ok to attend a section different to your enrolled/wait-listed one if you can get the permission of the new section's GSI. Just be sure to show up to one. \item Section notes like these will be posted on the course website. \item Feel free to contact the GSI's via e-mail, or the class staff and students through the newsgroup, ucb.class.cs70, if you have a question. \end{itemize} \end{enumerate} \section{Warm-up Exercises} \begin{ex} Write down the truth table for $\neg A \to B$. What else is this operation on A and B known as? \end{ex} \solution{ \begin{tabular}{|c|c|c|} \hline $A$ & $B$ & $\neg A \to B$ \\ \hline T & T & T \\ T & F & T \\ F & T & T \\ F & F & F \\ \hline \end{tabular} This is logically equivalent to $A \vee B$. } % END SOLUTION \begin{ex} Use a truth table to show that the negation of $P \Rightarrow Q$ is $P \wedge \neg Q$, in another words, $\neg (P \Rightarrow Q)$ is logically equivalent to $P \wedge \neg Q$. Keeping in mind that DeMorgan's rule says that $\neg (P \wedge Q) \equiv \neg P \vee \neg Q$, what is the negation of $P \Leftrightarrow Q$? \end{ex} \solution{ \begin{tabular}{|c|c|c|c|} \hline $P$ & $Q$ & $P \Rightarrow Q$ & $P \wedge \neg Q$ \\ \hline T & T & T & F \\ T & F & F & T \\ F & T & T & F \\ F & F & T & F \\ \hline \end{tabular} $P \Leftrightarrow Q$ is logically equivalent to $(P \Rightarrow Q) \wedge (Q \Rightarrow P)$. Thus, the negation is $(P \wedge \neg Q) \vee (Q \wedge \neg P)$, we can also re-write this using the distribution law as $(P \vee Q) \wedge (\neg P \vee \neg Q)$. } % END SOLUTION \section{Propositional Logic Applied} Knights are always truthful while knaves are consistent liars. With this in mind, consider the following conversation between Alice and Bob. \begin{center} Alice: At least one of us is a knight. Bob: At least one of us is a knight. \end{center} How might we determine whether Alice is a knight or a knave? As we're dealing with the truth of statements (i.e. that ''Alice is a knight'' and the same for Bob), propositional logic should come to mind! Let's begin by labeling the two propositions we're interested in: \begin{center} P = ''Alice is a knight'' Q = ''Bob is a knight'' \end{center} \begin{ex} Using the propositional machinery discussed in class, determine exactly what can be deduced from the above facts/statements. \begin{enumerate}[{(}i{)}] \item As a first step, write out the four distinct statements in terms of P and Q that must be true. (hint: what if Alice is/is not a knight, what about Bob?). \item P must be either true or false, as must be Q. Also your four logical propositions must be true. Using a truth table determine which truth assignments to P and Q are consistent with the truth of your four statements. From this deduce what can be said about the truth of P and Q. \end{enumerate} \end{ex} \solution{ \begin{enumerate}[{(}i{)}] \item $P \Rightarrow (P \vee Q)$, $Q \Rightarrow (P \vee Q)$, $\neg P \Rightarrow (\neg P \wedge \neg Q)$, $\neg Q \Rightarrow (\neg P \wedge \neg Q)$ \item With a truth table, it shouldn't be tricky to show that either $P \wedge Q$ or $\neg P \wedge \neg Q$. \end{enumerate} } \section{Quantifier Practice} Consider the false statement ``For each $x$ in $\R$. $x^2 \geq x$" (consider $01$). So what is going wrong here? Let $P(x)$ be the proposition ``$x^2 \geq x$" with $x$ taken from the universe of real numbers $\R$. Then our original statement is succinctly written as $\forall x. P(x)$. Using DeMorgan's laws, we get $\neg \forall x. P(x) \equiv \exists x. \neg P(x)$ or ``There exists a real $x$ for which $x^2 < x$." We can chain together quantifiers in any manner we please: $\forall x. \exists y. \forall z. P(x,y,z)$ and negate it using the same rules discussed above. By applying the rules in sequence, we get that \begin{eqnarray*} & \neg (\forall x. \exists y. \forall z. P(x,y,z)) \\ & \exists x. \neg (\exists y. \forall z. P(x,y,z)) \\ & \exists x. \forall y. \neg (\forall z. P(x,y,z)) \\ & \exists x. \forall y. \exists z, \neg P(x,y,z) \end{eqnarray*} The $\neg$ ``bubbles down", flipping quantifiers as it goes.The following problem comes from Question 14 in the Mathematics Subject GRE Sample Test: \begin{ex} Let $\R$ be the set of real numbers and let $f$ and $g$ be functions from $\R$ to $\R$. The negation of the statement \medskip \begin{center} ``For each $s$ in $\R$, there exists an $r$ in $\R$ such that if $f(r) > 0$, then $g(s) > 0$." \end{center} \medskip \noindent is which of the following? \begin{enumerate}[{(}A{)}] \item For each $s$ in $\R$, there exists an $r$ in $\R$ such that $f(r) \leq 0$ and $g(s) > 0$. \item There exists an $s$ in $\R$ such that for each $r$ in $\R$, $f(r) \leq 0$ and $g(s) \leq 0$. \item There exists an $s$ in $\R$ such that for each $r$ in $\R$, $f(r) \leq 0$ and $g(s) > 0$. \item There exists an $s$ in $\R$ such that for each $r$ in $\R$, $f(r) > 0$ and $g(s) \leq 0$. \item For each $s$ in $\R$, there exists an $r$ in $\R$ such that $f(r) \leq 0$ and $g(s) \leq 0$. \end{enumerate} Use the tools covered above. (\textbf{hint:} what happens when you negate an implication? Try rewriting the statements in propositional logic, e.g. replacing $f(r) > 0$ with $P(r)$ and $g(s) > 0$ with $Q(s)$). \end{ex} \solution{ $(D)$ } \section{We Hold These Truth To Be Self-Evident That $\forall x,y \in MEN.x=y$} \begin{ex} Suppose we're considering the set of just 2 numbers $S = \{0,1\}$. Try to re-state the following propositions without using any quantifiers. For example, $\forall x.P(x)$ can be re-formulated as $P(0) \wedge P(1)$. \begin{enumerate} \item $\exists x \in S.P(x)$ \item $\neg \exists x \in S. P(x)$ \item $\forall x \in S.\exists y \in S.P(x,y)$ \item $\exists x \in S.P(x)\vee(\forall y \in S.Q(x,y))$ \item $\neg (\forall x \in S. \exists y \in S. P(x)\Rightarrow Q(y))$ \end{enumerate} \end{ex} \solution{ \begin{enumerate} \item $P(0) \vee P(1)$ \item $(\neg P(0)) \wedge (\neg P(1))$ \item $(P(0,0) \vee P(0,1)) \wedge (P(1,0) \vee P(1,1))$ \item $(P(0) \vee (Q(0,0) \wedge Q(0,1))) \vee (P(1) \vee (Q(1,0) \wedge Q(1,1)))$ \item Let $W(x,y)$ be $(\neg Q(y) \wedge P(x))$. Then we get $(W(0,0) \wedge W(0,1)) \vee (W(1,0) \wedge W(1,1))$. \end{enumerate} } \begin{ex} Louis Reasoner, upon finishing CS61A, decided to take CS70. After the first lecture, he immediately made the conjecture that $\forall x. \exists y. P(x,y)$ is logically equivalent to $\exists y. \forall x. P(x,y)$. Use a counterexample from either basic mathematics or the everyday world to prove him wrong. What about $\forall x. \forall y. P(x,y)$ vs. $\forall y. \forall x. P(x,y)$? Or what about $\exists x. \exists y. P(x,y)$ vs. $\exists y \exists x. P(x,y)$? \end{ex} \solution{ No. $\forall$ and $\exists$ cannot be interchanged, consider ''For every person on earth, there is a day such that that day is his/her birthday'' vs. ''There is a day such that for every person on earth, that day is his/her birthday''. $\forall$ and $\forall$ can be interchanged if they're next to each other, since with $\exists$. } \begin{ex} The symbol ''$!$'' in predicate logic is the uniqueness quantifier. For example, ''$\exists !n \in \mathbb{Z}, -n = n$'' means that ''there exists a unique integer n such that $-n = n$'', or, in another word, ''there exists EXACTLY ONE integer n such that $-n = n$''. Consider the statement ''$\exists ! x.P(x)$'' where $P(x)$ is some proposition concerning the variable x. Various Stanford students tried to re-formulate this statement to preserve the meaning but not use the $!$ quantifier, consider each one and decide if it's correct or not (assume x,y refer to the same domain). \begin{enumerate} \item $\exists x, P(x)$ \item $\exists x,P(x) = P(y) \Rightarrow x=y$ \item $\forall y, \exists P(y) \Rightarrow x=y$ \item $\exists x, P(x) \wedge (\forall y, \neg (x=y))$ \item $\exists x, \forall y, P(y) \Rightarrow x=y$ \end{enumerate} If you think none of the above attempts are right, correctly re-write the original proposition yourself. \end{ex} \solution{ All the above attemps are wrong. A Berkeley student would write $\exists x. \forall y. P(y) \Leftrightarrow x=y$, or the logical equivalent, $\exists x. P(x) \wedge (\forall y, P(y) \Rightarrow x=y)$. } \section{Bad Proofs} Consider the following false statement and its (necessarily!) erroneous proof. \begin{thm} 2=1. \end{thm} \begin{proof} Take any $a,b\in\N=\{0,1,2,\ldots\}$ such that $a=b$ \begin{eqnarray} &\Rightarrow& a=b \\ &\Rightarrow& a^2 = a b \\ &\Rightarrow& a^2 - b^2 = a b - b^2 \\ &\Rightarrow& (a+b)(a-b) = (a-b) b \\ &\Rightarrow& a+b = b \\ &\Rightarrow& 2 b = b \\ &\Rightarrow& 2 = 1\enspace. \end{eqnarray} \end{proof} \begin{ex} What went wrong with this proof? What lessons can be learned? \end{ex} \solution{ We cannot divide both side by $(a-b)$ on line 4 $\Rightarrow$ line 5 since $(a-b)$ is 0. } \begin{ex} Given $a,b \in \R-\{0\}$ and $ab > 1$, a student concludes $a > 1/b$. Is this always true? If not, where did the student go wrong? \end{ex} \solution{ Not necessarily, b could be negative, in which case we might switch the greater than sign. } When you're a beginner at writing proofs, it is important to be as rigorous as you can. If you use even somewhat hand-wavy argument, insidiously subtle mistake can creep into your proof. Consider the following proof: \begin{thm} $\mathbb{Q}$, the set of all rational numbers is larger (contains more members) than $\mathbb{N}$, the set of all natural numbers. \end{thm} \begin{proof} First, we note that all natural numbers are already rational numbers. Now, we take the integer 0, and remove it from both $\mathbb{Q}$ and $\mathbb{N}$ since 0 is both a rational number and natural number. Then, we remove the integer 1, 2, 3 ... in the same manner. It is clear that if we do this infinitely many times, then we will have removed all natural numbers from $\mathbb{Q}$. However, $\mathbb{Q}$ still have infinitely many members left such as $\frac{1}{2}$, $\frac{1}{3}$, $\frac{1}{4}$, etc. Thus, $\mathbb{Q}$ contains more members than $\mathbb{N}$. \end{proof} The theorem stated is in fact wrong. There are exactly as many rational numbers as there are natural numbers, and we will learn rigorously why that is toward the end of the semester. Roughly speaking, the proof is wrong because when the two sets are infinite, different methods of removing members of one set from the other can create different results. %Comment on how to organize proofs. Write hypothesis on a side, thesis on the other. At every step look back and think if what you just argued makes sense under those hypothesis. Proof guidelines: 2)check each step throughly \section{Biconditional Proofs} The lectures introduced a number of types of proofs, including direct proofs and proof by contraposition which both aim to prove a statement of the form $P\Rightarrow Q$. Often our goal will \emph{additionally} be to prove the converse $Q\Rightarrow P$ -- that is we are to prove $P\Leftrightarrow Q$. \begin{thm}\label{thm:odd-squaredodd} $n$ is odd iff $n^2$ is odd, for each $n\in\N$. \end{thm} \begin{ex} Consider Theorem~\ref{thm:odd-squaredodd}. \begin{enumerate}[(i)] \item Begin by proving the forward direction ($n$ odd implies $n^2$ odd). easy proof by algebra \item Carefully prove the theorem with a simple modification to part (i). %use contrapositive of converse, if n is even \item Appeal to the equivalence of an implication and its contrapositive to prove the corollary\footnote{A `corollary' is a result that immediately follows from a proven result.} that ``$n$ is even iff $n^2$ is even, for each $n\in\N$. %Ask class \end{enumerate} \end{ex} \solution{ \begin{enumerate}[(i)] \item \begin{proof} Direct proof. Suppose that $n$ is odd, then we can write $n=2k+1$ where $k \in \N$. Thus, $n^2 = (2k+1)^2 = 4k^2 + 4k + 1$ is an odd number. \end{proof} \item \begin{proof} Proof by contradiction. Suppose that $n^2$ is odd and $n$ is even. Then $n=2k$ where $k\in \N$ and $n^2 = 4k^2$ is even. But we assumed that $n^2$ is odd. Contradiction, hence, $n$ cannot be even and must be odd. \end{proof} \item $A \Leftrightarrow B$ is logically equivalent to $B \Leftrightarrow A$. Thus, we get the corollary for free from the theorem. \end{enumerate} } %Show proof structure on higherblackboard: statement. Context. Hypothesis. Thesis. %one blackboard for proof \section{Different People, Different Proofs} Consider the following theorem. \begin{thm} Given a sequence of real numbers $x_0 = 1$ and $x_1, x_2, x_3, x_4, x_5 \geq 1$, the following holds true: if $x_5 > 35$, then $\exists i \in \{0,1,2,3,4\}$ such that $\frac{x_{i+1}}{x_{i}} > 2$. \end{thm} You can prove this in any of the three ways, you learnt in class: direct proof, proof by contrapositive and proof by contradiction. \begin{ex} Prove the theorem in each of the three ways. Which one was easier? Which one more natural to you? \end{ex} \solution{ \begin{enumerate} \item \begin{proof} Direct proof. Assume $x_0 = 1$, $x_1, x_2, x_3, x_4, x_5 \geq 1$, and $x_5 > 35$. Consider $x_1$, either $\frac{x_{1}}{x_{0}} > 2$ or $\frac{x_{1}}{x_{0}} <= 2$. Our proof is complete if the first case is true, hence, we assume that the second case is true and $x_1 <= 2$. Now, consider $x_2$; similarly, $\frac{x_{2}}{x_{1}} > 2$ or $\frac{x_{2}}{x_{1}} <= 2$. In the first case, we are done. Thus, we assume that the second case is true and $x_2 <= 4$. By the exact same logic, we can assume that $x_3 <= 8$ and $x_4 <= 16$. Since $\frac{x_{5}}{x_{4}} = \frac{35}{16} > 2$, our proof is complete. \end{proof} \item \begin{proof} Proof by contrapositive. Assume that $x_0 = 1$, $x_1, x_2, x_3, x_4, x_5 \geq 1$, and $\forall i\in \{0,1,2,3,4\}.\frac{x_{i+1}}{x_{i}} <= 2 $. Since $\frac{x_{1}}{x_{0}} <= 2$, we can conclude that $x_1 <= 2$. Similarly, we can say that $x_2 <= 4$, $x_3 <= 8$, $x_4 <= 16$, and $x_5 <= 32$. Since we have shown that $x_5 \neq 35$, our proof is complete. \end{proof} \item \begin{proof} Proof by contradiction. Assume that $x_0 = 1$, $x_1, x_2, x_3, x_4, x_5 \geq 1$, $x_5 > 35$, and $\forall i\in \{0,1,2,3,4\}.\frac{x_{i+1}}{x_{i}} <= 2$. Since $\frac{x_{1}}{x_{0}} <= 2$, we can conclude that $x_1 <= 2$. Similarly, we can say that $x_2 <= 4$, $x_3 <= 8$, $x_4 <= 16$, and $x_5 <= 32$. Contradiction, we assumed that $x_5 = 35$, hence, it must be that $\exists i\in \{0,1,2,3,4\}.\frac{x_{i+1}}{x_{i}} > 2 $ \end{proof} \end{enumerate} } \end{document}