preplogic-solutions.tex (10143B)
1 \documentclass[a4paper,oneside]{article} 2 \usepackage[utf8]{inputenc} 3 \usepackage{amsmath} 4 \usepackage{amsthm} 5 \usepackage{amssymb} 6 \usepackage[top=2cm]{geometry} 7 8 \theoremstyle{definition} \newtheorem{exercise}{Exercise}[section] 9 10 \author{Sebastiano Tronto (\texttt{sebastiano.tronto@uni.lu})} 11 \title{Elementary Logic exercises (Prep Camp 2020)} 12 13 \begin{document} 14 \maketitle 15 16 \section{Logical operations} 17 18 \begin{exercise} 19 Determine if the following statements are \textbf{true} or \textbf{false}: 20 \begin{enumerate} 21 \item ``Today is Tuesday or Germany has more inhabitants than Luxembourg'' 22 \item ``$7$ is odd and $2+2=5$'' 23 \item Every number of the form $2^{2^n}+1$, for $n=1,2,3...$, is prime. 24 \end{enumerate} 25 \end{exercise} 26 \begin{proof}[Solution] 27 \begin{enumerate} 28 \item \textbf{True}: regardless of when you solve this exercise, Germany 29 has more inhabitants than Luxembourg. 30 \item \textbf{True} 31 \item \textbf{False}: the number $2^{2^5}+1=4294967297=641\times 6700417$ 32 is not prime. 33 \end{enumerate} 34 \end{proof} 35 36 \begin{exercise} 37 What is the negation of the sentence ``\emph{I payed attention in class and I 38 did not do my homework}'' ? 39 \end{exercise} 40 \begin{proof}[Solution] 41 ``\emph{I did not pay attention in class \textbf{or} I did my homework}'' 42 \end{proof} 43 44 \begin{exercise} 45 Simplify the following logical expressions using the properties of logical 46 operations (where $A,B$ and $C$ are statements): 47 \begin{enumerate} 48 \item $A\land(A\lor B)$ 49 \item $A\lor (B\land A)$ 50 \item $(A\lor B) \land \neg A$ 51 \item $A \lor (\neg A\land B)$ 52 \item $(\neg (A\lor \neg B))\land ((A\lor C) \land \neg C)$ 53 \end{enumerate} 54 \end{exercise} 55 \begin{proof}[Solution] 56 They are equivalent to the following (you can check with truth tables): 57 \begin{enumerate} 58 \item $A$ 59 \item $A$ 60 \item $B\land \neg A$ 61 \item $A\lor B$ 62 \item Let's do this one in more steps: 63 \begin{align*} 64 (\neg (A\lor \neg B))\land ((A\lor C) \land \neg C)= 65 &(\neg A\land B)\land ((A\lor C)\land \neg C)=\\ 66 =&(\neg A\land B)\land ((A\land \neg C)\lor (C\land \neg C))=\\ 67 =&(\neg A\land B)\land ((A\land \neg C)\lor \textbf{false})=\\ 68 =&(\neg A\land B)\land (A\land \neg C)=\\ 69 =&A\land \neg A\land B\land \neg C=\\ 70 =&\textbf{false} 71 \end{align*} 72 \end{enumerate} 73 \end{proof} 74 75 \section{Implication} 76 77 \begin{exercise} 78 Fill in the following truth table: 79 \begin{align*} 80 \begin{array}{|c|c|c|c|c|} 81 \hline 82 A & B & C & \neg(A\implies B) & (A\implies B) \implies C \\ 83 \hline 84 0 & 0 & 0 & 0 & 0 \\ 85 \hline 86 0 & 0 & 1 & 0 & 1 \\ 87 \hline 88 0 & 1 & 0 & 0 & 0 \\ 89 \hline 90 0 & 1 & 1 & 0 & 1 \\ 91 \hline 92 1 & 0 & 0 & 1 & 1 \\ 93 \hline 94 1 & 0 & 1 & 1 & 1 \\ 95 \hline 96 1 & 1 & 0 & 0 & 0 \\ 97 \hline 98 1 & 1 & 1 & 0 & 1 \\ 99 \hline 100 \end{array} 101 \end{align*} 102 \end{exercise} 103 104 \begin{exercise}[Transitivity] 105 Prove that the following statement is true for any statements $A,B$ and $C$: 106 \begin{align*} 107 ((A\implies B)\land (B\implies C))\implies (A\implies C) 108 \end{align*} 109 \end{exercise} 110 \begin{proof}[Solution] 111 Let's rewrite the first part in terms of basic logical operations: 112 \begin{align*} 113 (A\implies B)\land (B\implies C)=&(B\lor \neg A)\land(C\lor \neg B) 114 \end{align*} 115 now we can write a truth table for the two parts 116 \begin{align*} 117 \begin{array}{|c|c|c|c|c|} 118 \hline 119 A & B & C & (B\lor\neg A)\land(C\lor\neg B) & A\implies C \\ 120 \hline 121 0 & 0 & 0 & 1 & 1 \\ 122 \hline 123 0 & 0 & 1 & 1 & 1 \\ 124 \hline 125 0 & 1 & 0 & 0 & 1 \\ 126 \hline 127 0 & 1 & 1 & 1 & 1 \\ 128 \hline 129 1 & 0 & 0 & 0 & 0 \\ 130 \hline 131 1 & 0 & 1 & 0 & 1 \\ 132 \hline 133 1 & 1 & 0 & 0 & 0 \\ 134 \hline 135 1 & 1 & 1 & 1 & 1 \\ 136 \hline 137 \end{array} 138 \end{align*} 139 With the help of the truth table we see that whenever the first part 140 ``$(\neg (A\lor \neg B))\land ((A\lor C) \land \neg C)$'' is true, also the 141 implication ``$A\implies C$'' is true. This shows that the ``big 142 implication'' is true. (If you are not convinced, you can add more details to 143 this proof, for example by writing more truth tables.) 144 \end{proof} 145 146 \begin{exercise} 147 What is the contrapositive of ``\emph{If this table is not reserved, we sit 148 here}'' ? 149 \end{exercise} 150 \begin{proof}[Solution] 151 ``\emph{If we do not sit here, this table is reserved}''. One could also say 152 this in another way, for example ``\emph{We do not sit here because this 153 table is reserved}''. 154 \end{proof} 155 156 \section{Quantifiers} 157 158 \begin{exercise} 159 Write the negation of the following statements: 160 \begin{enumerate} 161 \item $\exists x\in \mathbb N,\, x^2-2=0$ 162 \item ``Every prime number is odd'' 163 \item ``Every person I have met likes pizza'' 164 \item ``There is at least one number greater than $7$'' 165 \item $\forall x\in \mathbb N,\,x\geq 0$ 166 \item $\forall x\in \mathbb Z,\,(\exists y\in\mathbb Z,\,x+y=0)$ 167 \end{enumerate} 168 \end{exercise} 169 \begin{proof}[Solution] 170 \begin{enumerate} 171 \item $\forall x\in\mathbb N,\, x^2-2\neq 0$ 172 \item ``There is at least one prime number which is even'' 173 \item ``I have met at least one person that does not like pizza'' 174 \item ``Every number is less or equal than $7$'' 175 \item $\exists x\in\mathbb N,\, x<0$ 176 \item $\exists x\in \mathbb Z,\, (\forall y\in \mathbb Z,\, x+y\neq 0)$ 177 \end{enumerate} 178 \end{proof} 179 180 \begin{exercise} 181 There is another quantifier that we did not cover in the lecture, namely 182 $\exists!$ (read ``there exists exactly one''). For example, the sentence 183 ``\emph{there exists exactly one natural number x such that x+2=5}'' can be 184 written in symbols as ``$\exists!x\in \mathbb N,\,x+2=5$''. 185 186 In this exercise, your task is to give a formal definition of this quantifier 187 using the logical symbols that we have defined in class. In particular, you 188 will need the following: 189 \begin{itemize} 190 \item the universal ($\forall$) and existential ($\exists$) quantifiers 191 \item the conjunction $\land$ 192 \item the implication $\implies$ 193 \end{itemize} 194 Moreover, you will need the equality symbol $=$ between two elements of a set 195 (if $a$ and $b$ are two elements of the same set, ``$a=b$'' is a mathematical 196 statement and it is \textbf{true} if and only if $a$ and $b$ are the same 197 element). 198 199 \emph{Warning: your definition must depend on a set $S$ and on a ``variable 200 statement'' $A(x)$, as the existential and universal quantifiers.} 201 \end{exercise} 202 \begin{proof}[Solution] 203 The idea is that we want to write ``\emph{there is $x\in S$ such that $A(x)$ 204 is true, \textbf{and}, for any other $y\in S$, $A(y)$ is false}. From this 205 we see that the structure of the statement is 206 \begin{align*} 207 \exists x\in S,\,(\text{``something''}\land\text{``something else''}) 208 \end{align*} 209 The ``something'' part is just $A(x)$. The ``something else'' part can be 210 written in different ways, for example 211 \begin{align*} 212 \forall y\in S,\,(y\neq x\implies \neg A(y)) \quad \text{or} 213 \quad \forall y\in S,\,(A(y)\implies y=x) 214 \end{align*} 215 (notice that the two implications above are one the contrapositive of the 216 other); or also 217 \begin{align*} 218 \forall y\in S\setminus \{x\},\, \neg A(y) 219 \end{align*} 220 So in conclusion, one way to define ``$\exists!$'' is the following: 221 \begin{align*} 222 \exists!x\in S,\,A(x)\quad:=\quad\exists x\in S,\,(A(x)\land 223 (\forall y\in S,\,(A(y)\implies y=x))) 224 \end{align*} 225 226 \end{proof} 227 228 \section{Proofs} 229 230 \begin{exercise} 231 Prove by induction that 232 \begin{align*} 233 \forall n\in\mathbb N,\quad \sum_{k=1}^n(2k-1)=n^2 234 \end{align*} 235 (here $\sum_{k=1}^n(2k-1)$ means $1+3+5+\cdots+ (2n-1)$). 236 \end{exercise} 237 \begin{proof}[Solution] 238 \textbf{Base case:} for $n=0$ the sum is empty, so we have $0=0$ which is 239 true. (If you do not think that the formula makes sense for $n=0$, you can do 240 prove it for $n\geq 1$ and fo $n=1$ as a base case.) 241 242 \textbf{Inductive step:} we can assume that the formula works for a generic 243 (but fixed) $n\in\mathbb N$ and prove that then it also works for $n+1$. So: 244 \begin{align*} 245 \sum_{k=1}^{n+1}(2k-1)&=\left(\sum_{k=1}^{n}(2k-1)\right)+2(n+1)-1=\\ 246 &=n^2 +2(n+1)-1=\\ 247 &=n^2+2n+1=\\ 248 &=(n+1)^2 249 \end{align*} 250 which is the formula for $n+1$. 251 \end{proof} 252 253 \begin{exercise} 254 If $n\in \mathbb N$ the \emph{factorial} of $n$, denoted by $n!$ is defined 255 as follows: 256 \begin{align*} 257 n!=\begin{cases} 258 1&\text{if } n=0,\\ 259 n\times (n-1)! & \text{if } n> 0. 260 \end{cases} 261 \end{align*} 262 Prove by induction that if $n\geq 4$ then $n!\geq 2^n$. 263 \end{exercise} 264 \begin{proof}[Solution] 265 \textbf{Base case:} here the base case is $n=4$, and we have 266 $4!=24\geq 16=2^4$. 267 268 \textbf{Inductive step:} we can assume that the inequality is true for $n$, 269 and prove that it is also true for $n+1$. We have: 270 \begin{align*} 271 (n+1)!=(n+1)\times n!\geq (n+1)\times 2^n\geq 2^{n+1} 272 \end{align*} 273 \end{proof} 274 275 \begin{exercise} 276 Is the following statement true or false? Give a proof of your answer. 277 \begin{align*} 278 \forall n\in \mathbb N,\, n^2 -4n +5>n 279 \end{align*} 280 \end{exercise} 281 \begin{proof}[Solution] 282 The statement is \textbf{false}. Since it starts with a universal 283 quantifier, in order to prove that it is false we just need to provide one 284 example of $n\in \mathbb N$ which makes it false. In other words, we need to 285 prove that 286 \begin{align*} 287 \exists n\in \mathbb N,\, n^2-4n+5\leq n 288 \end{align*} 289 and a proof of this fact is very simple: for $n=2$ we have 290 $2^2-4\times 2+5=1\leq 2$. 291 \end{proof} 292 293 \begin{exercise} 294 Do the last point of Exercise 1.1 again, but this time give a proof of your 295 answer. 296 \end{exercise} 297 \begin{proof}[Solution] 298 Again, since we have to prove that the statement is false, we just need to 299 show one counterexample. for example, the number 300 $2^{2^5}+1=4294967297=641\times 6700417$ is not prime. 301 \end{proof} 302 303 304 305 306 \end{document}