%&LaTeX \documentclass{article} \newcommand{\tab}{\makebox[4em]{}} \begin{document} \begin{center} \textbf{ArsDigita University} \end{center} \begin{center} \textbf{Month 2: Discrete Mathematics - Professor Shai Simonson} \end{center} \begin{center} \textbf{Problem Set 1 -- Logic, Proofs, and Mathematical Reasoning} \end{center} \begin{enumerate} \item { Logic Proofs } \begin{enumerate} \item Prove that $a \rightarrow b$ is equivalent to $\neg b \rightarrow \neg a$ using a truth table. \\ \item Prove it using {\em algebraic} identities. \\ \item Prove that $a \rightarrow b$ is not equivalent to $ b \rightarrow a$. \end{enumerate} \item {Aristotle's Proof that the Square Root of Two is Irrational.}\\ \begin{enumerate} \item Prove the {\em lemma,} used by Aristotle in his proof, which says that if $n^{2}$ is even, so is $n$. (Hint: Remember that $a \rightarrow b$ is equivalent to $b \rightarrow \neg a$.\\ \item Prove that the square root of 3 is irrational using Aristotle's techniques. Make sure to prove the appropriate lemma.\\ \item If we use Aristotle's technique to {\em prove} the untrue assertion that the square root of 4 is irrational, where {\em exactly} is the hole in the proof?\\ \item Using the fact that the square root of two is irrational, prove that $\sin (\frac{\pi}{4})$ is irrational. \end{enumerate} \item In ADU-ball, you can score 11 points for a goal, and 7 for a near miss. \\ \begin{enumerate} \item Write a Scheme program that prints out the number of goals and the number of near misses to achieve a given total greater than 60.\\ \item Prove that you can achieve any score greater than 60. Think inductively and experiment. \end{enumerate} \item Prove by induction that there are 2$^{\mathit{n}}$ possible rows in a truth table with $ n$ variables. \item In the restroom of a fancy Italian restaurant in Mansfield, MA, there is a sign which reads: {\em Please do not leave valuables or laptop computers in your car.} \item Assuming that a laptop computer is considered a valuable, prove using formal logic, that the sentence {\em Please do not leave valuables in your car} is equivalent to the sign in the restroom. Prove that {\em Please do not leave laptops in your car} is not equivalent. \item Prove that $a | b$, $a$ nand $b$, which is defined to be $\neg (a \wedge b)$, is complete. Write $( a \rightarrow b) \rightarrow b$ using just $|$ (nand), then using just $\downarrow$ (nor). \item Show how to use a truth table in order to construct a conjunctive normal form for any Boolean formula $W$. Hint: Consider the disjunctive normal form for $\neg W$. \item Euclid proved that there are an infinite number of primes, by assuming that $ n$ is the highest prime, and exhibiting a number that he proved must either be prime itself, or else have a prime factor greater than $ n $. Write a scheme program to find the smallest $ n$ for which Euclid's proof does {\em not} provide an actual prime number. \item You have proved before that a truth table with $n$ variables has $2^{n}$ rows. \begin{enumerate} \item How many different Boolean functions with $n$ variables are there? \\ \item For $n = 2$, list all the functions and identify as many as you can by name. \end{enumerate} \item Prove by induction that for $n > 5 $ , $2^{n} > n^{2}$. \item Guess the number of different ways for $n$ people to arrange themselves in a straight line, and prove your guess is correct by induction. \item Use logic with quantifiers and predicates to model the following three statements: \begin{itemize} \item All students are taking classes. \item Some students are not motivated. \item Some people taking classes are not motivated. \end{itemize} Prove, using resolution methods, that the third statement follows logically from the first two. (Reminder: You must take the conjunction of the first two statements and the negation of the third, and derive a contradiction.) \item The following algebraic idea is central for Karnaugh maps. Karnaugh maps are a method of minimizing the size of circuits for digital logic design. \begin{enumerate} \item Using algebraic manipulation, prove that the two Boolean formulae below are equivalent. (Hint: $x(a+ \neg a)$ is equivalent to $x$.) \[ \neg yx + \neg zy + \neg xz \qquad \textrm{and} \qquad \neg xy + \neg yz + \neg zx \] \item Verify your results using a truth table. \end{enumerate} \item The exclusive-or operator $\oplus$, is defined by the rule that $a \oplus b$ is true whenever $a$ or $b$ is true but not both. \begin{enumerate} \item Calculate $x \oplus x$ , $x \oplus \neg x$ , $x \oplus 1$ , $x \oplus 0$.\\ \item Prove that $x + y \oplus z = (x+ y) \oplus (x+ z)$\\ \item Prove that $x \oplus (y + z) = ( x \oplus y) + ( x \oplus z)$\\ \item Write conjunctive normal form and disjunctive normal form formulae for $x \oplus y$\\ \item The exclusive-or operator is not {\em complete.} Which of the three operators \{and, or, not\} can be combined with exclusive-or to make a {\em complete} set. \end{enumerate} \item The n th triangle number $T_{n}$ is defined to be the sum of the first $n$ integers. \\ \begin{enumerate} \item Prove by induction that $T_{n} = n( n + 1)/2.$ \\ \item Prove algebraically using (a), that $n^{3} + (1+2+\cdots +(n - 1))^{2} = (1+2+\cdots (n-1) + n)^{2}$\\ \item Using (b) guess a formula for \[ 1^{3} + 2^{3} + 3^{3} + \cdots + n^{3}, \] and prove it by induction. \end{enumerate} \item Guess a formula for the sum below, and prove you are right by induction. \[ 1 + 1(2) + 2(3) + 3(4) + \cdots + n(n + 1) \] \end{enumerate} \end{document}