preplogic-slides.tex (14094B)
1 \documentclass[11pt]{beamer} 2 \usetheme{Madrid} 3 \usepackage[utf8]{inputenc} 4 \usepackage{amsmath} 5 \usepackage{amsfonts} 6 \usepackage{amssymb} 7 \usepackage{setspace} 8 \author{Sebastiano Tronto} 9 \title{Elementary Logic (PrepCamp)} 10 %\setbeamercovered{transparent} 11 %\setbeamertemplate{navigation symbols}{} 12 \logo{\includegraphics[scale=0.065]{unilu.jpg}} 13 \institute{uni.lu} 14 \date{September 13-14, 2021} 15 %\subject{} 16 17 \newtheorem {proposition}{Proposition} 18 \theoremstyle{definition} 19 \newtheorem {remark}{Remark} 20 \newtheorem {exercise}{Exercise} 21 22 23 \newcommand{\refgithub}{ 24 \textbf{Slides and exercises:} \\ 25 \hspace{20pt}\texttt{https://github.com/sebastianotronto/preplogic} \\ 26 \textbf{Email:} \\ 27 \hspace{20pt}\texttt{sebastiano.tronto@uni.lu} 28 } 29 30 \begin{document} 31 32 \begin{frame} 33 \titlepage 34 \end{frame} 35 36 \begin{frame} 37 \tableofcontents 38 \refgithub 39 \end{frame} 40 41 42 \section{Statements} 43 \begin{frame}{Statements} 44 \begin{itemize} 45 \pause 46 \item Unambiguous 47 \pause 48 \begin{example}[A bad joke] 49 \textbf{Q:} How many months have 30 days? 50 \pause 51 52 \textbf{A:} 11, some of them have even more! 53 \pause 54 55 :-( 56 \end{example} 57 \pause 58 \item Objective 59 \pause 60 \begin{example} 61 \textbf{Good:} 3 is greater than 4 62 63 \textbf{Bad:} 3 is nicer than 4 64 \end{example} 65 \end{itemize} 66 \end{frame} 67 68 \begin{frame}{Statements} 69 \begin{itemize} 70 \item Mathematical: ``\emph{Three is greater than four}\,'' 71 (or ``$3 > 4$'') 72 \item ...or not: ``\emph{I am 26 years old}\,'' 73 \item \textbf{Key point:} staments can be \textbf{true} or 74 \textbf{false} 75 \end{itemize} 76 \end{frame} 77 78 %\begin{frame}[plain] 79 %\begin{center} 80 %\includegraphics[scale=0.4]{xkcd169.png} 81 %https://xkcd.com/169/ 82 %\end{center} 83 %\end{frame} 84 85 86 \section{Logical operations} 87 88 \begin{frame}{Logical operations} 89 \begin{itemize} 90 \item We can combine statements to make new ones 91 \item Negation (\textbf{not}), conjunction (\textbf{and}), disjunction 92 (\textbf{or}) 93 \end{itemize} 94 \end{frame} 95 96 \begin{frame}{Negation (\textbf{not})} 97 \begin{center} 98 If $A$ is a statement, the statement ``not $A$'' (in symbols: $\neg A$) is 99 \textbf{true} when $A$ is \textbf{false}, and it is \textbf{false} when $A$ is 100 \textbf{true}. 101 \pause 102 \end{center} 103 104 \begin{example} 105 \begin{center} 106 $\neg (3>4)$ is equivalent to $3\leq 4$ 107 108 ``\emph{$3$ is \textbf{not} greater than $4$}'' is equivalent to 109 ``\emph{$3$ is less or equal than $4$}'' 110 \end{center} 111 \end{example} 112 \end{frame} 113 114 \begin{frame}{Conjunction (\textbf{and})} 115 \begin{center} 116 The statement ``$A$ and $B$'' (in symbols: 117 $A\land B$) is \textbf{true} when both $A$ and $B$ are \textbf{true}, and it is 118 \textbf{false} if at \emph{at least} one of them is \textbf{false}. 119 \pause 120 121 \begin{example} 122 ``$(3<4)\land (5$ is an odd number$)$'' is \textbf{true} 123 \end{example} 124 125 \begin{example} 126 ``(Today is Monday) $\land$ (we are in France)'' is \textbf{false} 127 \end{example} 128 \end{center} 129 130 \end{frame} 131 132 \begin{frame}{Disjunction (\textbf{or})} 133 \begin{center} 134 The statement ``$A$ or $B$'' (in symbols: 135 $A\lor B$) is \textbf{true} when at least one of $A$ and $B$ is \textbf{true}, 136 and it is \textbf{false} if both of them are \textbf{false}. 137 \pause 138 139 \begin{example} 140 ``$(3=4)\lor (5$ is an even number$)$'' is \textbf{false} 141 \end{example} 142 143 \begin{example} 144 ``(Today is Monday) $\lor$ (we are in Luxembourg)'' is \textbf{true} 145 \end{example} 146 \end{center} 147 148 \end{frame} 149 150 151 \begin{frame}{Logical operations} 152 \begin{itemize} 153 \item \textbf{Important:} $\lor$ is always \emph{inclusive}: 154 \pause 155 156 \begin{center} 157 \begin{example}[Another bad joke] 158 Waiter: ``Would you like cheese or dessert?'' 159 160 Mathematician: ``Yes.'' 161 \end{example} 162 \end{center} 163 \pause 164 \item $\neg$ has precedence over $\land$ and $\lor$: 165 \begin{align*} 166 \neg A\land B \text{ means } (\neg A)\land B,\qquad 167 \neg A\lor B \text{ means } (\neg A)\lor B 168 \end{align*} 169 (or just use parenthesis) 170 \end{itemize} 171 172 173 \end{frame} 174 175 \begin{frame}{Properties} 176 \begin{center} 177 If $A$, $B$ and $C$ are statements: 178 \end{center} 179 {\fontsize{9}{17}\selectfont 180 \begin{align*} 181 \begin{array}{cc|c} 182 A\land B = B\land A & A \lor B = B\lor A &\textbf{commutativity}\\ 183 \hline 184 A\land (B\land C) = (A\land B)\land C \quad & 185 A\lor (B\lor C) = (A\lor B)\lor C & \textbf{associativity}\\ 186 \hline 187 A\land(B\lor C) = (A\land B)\lor(A\land C) & & \textbf{distributivity} \\ 188 A\lor(B\land C) = (A\lor B)\land(A\lor C) & &\textbf{distributivity*} \\ 189 \hline 190 \neg(\neg A) = A & & \textbf{double negation} \\ 191 \hline 192 A \land \textbf{true} = A & A \land \textbf{false} = \textbf{false} \\ 193 A\lor \textbf{true} = \textbf{true} & A \lor \textbf{false} = A \\ 194 (\neg A) \land A = \textbf{false} & (\neg A) \lor A = \textbf{true} \\ 195 \hline 196 \neg (A\land B) = (\neg A)\lor (\neg B) & 197 \neg (A\lor B) = (\neg A)\land (\neg B) & \textbf{De Morgan's laws} 198 \end{array} 199 \end{align*}} 200 \end{frame} 201 202 %\subsection{Boolean algebra} 203 204 \begin{frame}{Boolean algebra} 205 \begin{itemize} 206 \item For simplicity: \textbf{true}\,$=1$, \textbf{false}\,$=0$ 207 \pause \item We have a set $\{0,1\}$ with some operations 208 $(\land,\lor,\neg)$ 209 \pause \item This is called a \textbf{Boolean algebra} 210 \end{itemize} 211 \end{frame} 212 213 %\subsection{Truth tables} 214 215 \begin{frame}{Truth tables} 216 A compact way of describing an operator, or a composition of operators 217 \pause 218 \vspace{4pt} 219 Example: 220 \begin{align*} 221 \begin{array}{|c|c|c|c|c|c|} 222 \hline 223 A & B & \neg A & A\land B & A\lor B & (A\lor B)\land (\neg A) \\ 224 \hline 225 0 & 0 & 1 & 0 & 0 & 0 \\ 226 0 & 1 & 1 & 0 & 1 & 1 \\ 227 1 & 0 & 0 & 0 & 1 & 0 \\ 228 1 & 1 & 0 & 1 & 1 & 0 \\ 229 \hline 230 \end{array} 231 \end{align*} 232 \end{frame} 233 234 \begin{frame}{Truth tables} 235 \begin{center} 236 We can check that two statements are equivalent with truth tables 237 \end{center} 238 \begin{align*} 239 \begin{array}{|c|c|c|c|} 240 \hline 241 A & B & \neg(A\land B) & (\neg A)\lor (\neg B)\\ 242 \hline 243 0 & 0 & 1 & 1 \\ 244 0 & 1 & 1 & 1 \\ 245 1 & 0 & 1 & 1 \\ 246 1 & 1 & 0 & 0 \\ 247 \hline 248 \end{array} 249 \end{align*} 250 \end{frame} 251 252 253 \section{Implication} 254 255 \begin{frame}{Implication} 256 \begin{itemize} 257 \item ``$A\implies B$'' means \emph{``If $A$ (is true), then $B$ (is true)''} 258 \end{itemize} 259 \pause 260 \begin{example} 261 \emph{``If it rains, I will bring an umbrella''} 262 263 (It rains)$\implies$(I will bring an umbrella) 264 \end{example} 265 \pause 266 \begin{example} 267 \emph{``If my grandpa had wheels, he would be a bike''} 268 269 (My grandpa has wheels)$\implies$(My grandpa is a bike) 270 \end{example} 271 \end{frame} 272 273 274 \begin{frame}{Implication} 275 \begin{itemize} 276 \item It is a logical operation: ``$A\implies B$'' means ``$B\lor(\neg A)$'' 277 \pause 278 \end{itemize} 279 \begin{align*} 280 \begin{array}{|c|c|c|c|} 281 \hline 282 A & B & A\implies B & \\ 283 \hline 284 0 & 0 & 1 & \text{No rain, I don't bring an umbrella} \\ 285 \hline 286 0 & 1 & 1 & \text{No rain, I bring an umbrella anyway} \\ 287 \hline 288 1 & 0 & 0 & \text{It rains, I don't bring an umbrella} \\ 289 \hline 290 1 & 1 & 1 & \text{It rains, I bring an umbrella} \\ 291 \hline 292 \end{array} 293 \end{align*} 294 \pause 295 \begin{remark} 296 ``\textbf{false} $\implies A$'' is always \textbf{true}, whatever $A$ is 297 (\emph{ex falso quodlibet}) 298 ``$A\implies$\textbf{true}'' is always true, whatever $A$ is 299 \end{remark} 300 \end{frame} 301 302 303 \begin{frame}{Notation} 304 Sometimes we use the following symbols: 305 \begin{itemize} 306 \item ``$A\impliedby B$'' is the same as ``$B\implies A$'' 307 \item ``$A\iff B$ is the same as ``$(A\implies B)\land (B\implies A)$''.\\ 308 It is read ``$A$ is equivalent to $B$'' or ``$A$ if and only if $B$''. 309 \end{itemize} 310 \end{frame} 311 312 \begin{frame}{Contrapositive} 313 \begin{itemize} 314 \item The statement $(\neg B)\implies (\neg A)$ is called 315 \emph{contrapositive} of $A\implies B$ 316 \pause 317 \item It is equivalent to ``$A\implies B$'' 318 \pause 319 \item Two proofs: 320 \begin{enumerate} 321 \item Properties of logical operations 322 \item Truth tables 323 \end{enumerate} 324 \end{itemize} 325 \end{frame} 326 327 \begin{frame}{End of part 1} 328 \begin{center} 329 \Huge See you tomorrow! 330 \end{center} 331 \vspace{10pt} 332 \refgithub 333 \end{frame} 334 335 \begin{frame}{Elementary logic - part 2} 336 \begin{center} 337 \Huge Welcome Back! 338 \end{center} 339 \vspace{10pt} 340 \refgithub 341 \end{frame} 342 343 344 \section{Quantifiers} 345 346 \begin{frame}{Quantifiers} 347 Let $S$ be a set and let $A(x)$ be a ``variable statement'' that depends on 348 $x\in S$ (for example $S=\mathbb{N}$ and $A(x)=$``x is an even number''). 349 \pause 350 \vspace{12pt} 351 \begin{itemize} 352 \item \textbf{Universal quantifier} ($\forall$ or ``for all''): 353 ``$\forall x\in S,\,A(x)$'' means that if we replace ``$x$'' with any 354 element of $S$, $A(x)$ is always \textbf{true}. 355 \vspace{9pt} 356 \item \textbf{Existential quantifier} ($\exists$ or ``there exists''): 357 ``$\exists x\in S,\, A(x)$'' means that $A(x)$ is \textbf{true} for 358 at least one value of $x$ is $S$. 359 \end{itemize} 360 \vspace{12pt} 361 \pause 362 \textbf{You always need a set $S$} 363 \end{frame} 364 365 \begin{frame}{Quantifiers - examples} 366 \begin{example} 367 $S=$``the set of all cars'', $A(x)$=``$x$ is red'' 368 369 $\forall x\in S,\, A(x)$ is \textbf{false}. 370 371 $\exists x\in S,\, A(x)$ is \textbf{true}. 372 \end{example} 373 \begin{example} 374 $S=\mathbb{N}$, $A(x)=x>5$ 375 376 $\forall x\in S,\, A(x)$ is \textbf{false}. 377 378 $\exists x\in S,\, A(x)$ is \textbf{true}. 379 \end{example} 380 \end{frame} 381 382 \begin{frame}{Negation of quantifiers} 383 \begin{center} 384 \textbf{Today's most important fact:} 385 \end{center} 386 \begin{align*} 387 \neg(\forall x\in S,\, A(x))&=\only<1>{\quad?} 388 \onslide<2->{\exists x\in S,\,\neg A(x)}\\ 389 \neg(\exists x\in S,\, A(x))&=\only<1-2>{\quad?} 390 \onslide<3->{\forall x\in S,\,\neg A(x)}\\ 391 \end{align*} 392 \onslide<2->{ 393 \begin{example} 394 \begin{center} 395 $\neg$``every number is even'' = ``there is at least one odd number'' 396 \end{center} 397 \end{example} 398 } 399 \onslide<3->{ 400 \begin{example} 401 \begin{center} 402 $\neg$``$\exists x\in \mathbb N,\, x+3=9$'' = 403 ``$\forall x\in \mathbb N,\, x+3\neq 9$'' 404 \end{center} 405 \end{example} 406 } 407 \end{frame} 408 409 \section{Proofs} 410 411 \begin{frame}{Proofs} 412 \begin{itemize} 413 \item A proof is a sequence of statements, each one logically deriving from 414 the previous. 415 \pause 416 \item Proofs are used to derive new statements from statements that are 417 known to be true. 418 \pause 419 \item If $A$ is known to be true and the implication $A\implies B$ is 420 logically clear, then also $B$ must be true. 421 \pause 422 \item Every mathematical theorem must be justified with a proof. 423 \end{itemize} 424 \end{frame} 425 426 %\subsection{Direct proofs} 427 \begin{frame}{Example: direct proof} 428 \begin{theorem} 429 The sum of two even numbers is even. 430 \end{theorem} 431 \pause 432 \begin{proof} 433 \begin{enumerate} 434 \item Recall the definition: a natural number $x$ is called \emph{even} 435 if there is some natural number $n$ such that $x=2n$. 436 \pause 437 \item If $x$ and $y$ are even numbers, then there are natural numbers $n$ 438 and $m$ such that $x=2n$ and $y=2m$. 439 \pause 440 \item Then $x+y=2n+2m=2(n+m)$. 441 \pause 442 \item Then $x+y$ is even. 443 \end{enumerate} 444 \end{proof} 445 \end{frame} 446 447 448 %\subsection{Proofs by contradiction} 449 450 \begin{frame}{Proofs by contradiction} 451 Idea: I want to show $A=\textbf{true}$. I show that the implication 452 ``$(\neg A)\implies\textbf{false}$'' is \textbf{true}. 453 Then $\neg A=\textbf{false}$, so $A=\textbf{true}$. 454 \pause 455 \begin{definition} 456 A natural number is called \emph{prime} if it is different from $1$ and it 457 is only divisible by $1$ and itself. 458 \end{definition} 459 \begin{theorem} 460 There are infinitely many prime numbers. 461 \end{theorem} 462 463 \end{frame} 464 465 \begin{frame}{Proofs by contradiction} 466 \begin{theorem} 467 There are infinitely many prime numbers. 468 \end{theorem} 469 \pause 470 \begin{proof} 471 \begin{enumerate} 472 \item Assume that there are only finitely many prime numbers. 473 \pause 474 \item $\exists n\in \mathbb N$, there are $n$ prime numbers. Call them 475 $p_1,p_2,\dots,p_n$. 476 \pause 477 \item Let $u=p_1\times p_2\times \dots \times p_n +1$. 478 \pause 479 \item $u$ is not divisible by any of the prime numbers $p_1,\dots,p_n$. 480 \pause 481 \item Therefore $u$ is only divisible by $1$ and itself. So $u$ is prime. 482 \pause 483 \item So $p_1,\dots,p_n$ are not the only prime numbers. 484 \end{enumerate} 485 \end{proof} 486 487 \end{frame} 488 489 490 %\subsection{Proofs by induction} 491 492 \begin{frame}{Proofs by induction} 493 If I want to prove $\forall n\in \mathbb N,\, A(n)$: 494 \begin{enumerate} 495 \item Prove $A(0)$ (\emph{base step}) 496 \item Prove $\forall n\in \mathbb N,\, (A(n)\implies A(n+1))$ 497 (\emph{inductive step}) 498 \end{enumerate} 499 \pause 500 \begin{theorem}[Sum of natural numbers] 501 $\forall n\in \mathbb N,\quad 0+1+\cdots + n=\frac{n(n+1)}{2}$ 502 \end{theorem} 503 504 \end{frame} 505 506 507 \begin{frame} 508 \begin{proof} 509 \begin{enumerate} 510 \item Base case: $0=0$. 511 \pause 512 \item Let $n$ be any natural number. 513 \pause 514 515 If $A(n)=\textbf{false}$, then $A(n)\implies A(n+1)$ is \textbf{true}. 516 \pause 517 518 If $A(n)=\textbf{true}$, we have to show that $A(n+1)=\textbf{true}$. 519 \pause 520 521 \begin{align*} 522 \begin{array}{rlr} 523 0+\cdots +(n+1)& = (0+\cdots+ n)+(n+1)=\\ 524 & = \frac{n(n+1)}{2}+(n+1)= & \text{since }A(n)=\textbf{true}\\ 525 & = \frac{n^2+n+2n+2}{2}\\ 526 & = \frac{(n+1)(n+2)}{2} 527 \end{array} 528 \end{align*} 529 so $A(n+1)=\textbf{true}$ 530 531 \end{enumerate} 532 \end{proof} 533 \end{frame} 534 535 \begin{frame}{The end} 536 What you have learned in this course: 537 \begin{itemize} 538 \item Basic logic operations and logic implication 539 \item Quantifiers and \textbf{their negation} 540 \item Some basic mathematical proofs 541 \end{itemize} 542 \vspace{10pt} 543 \refgithub 544 \end{frame} 545 546 547 \end{document}