\documentclass[11pt]{beamer}
\usetheme{Madrid}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{setspace}
\author{Sebastiano Tronto}
\title{Elementary Logic (PrepCamp)}
%\setbeamercovered{transparent} 
%\setbeamertemplate{navigation symbols}{} 
\logo{\includegraphics[scale=0.065]{unilu.jpg}} 
\institute{uni.lu} 
\date{September 7-8, 2020} 
%\subject{}

\newtheorem {proposition}{Proposition}
\theoremstyle{definition}
\newtheorem {remark}{Remark}
\newtheorem {exercise}{Exercise}


\newcommand{\refgithub}{
    \textbf{Slides and exercises:} \\
    \hspace{20pt}\texttt{https://github.com/sebastianotronto/preplogic} \\
    \textbf{Email:} \\
    \hspace{20pt}\texttt{sebastiano.tronto@uni.lu}
}

\begin{document}

\begin{frame}
\titlepage
\end{frame}

\begin{frame}
    \tableofcontents
    \refgithub
\end{frame}


\section{Statements}
\begin{frame}{Statements}
\begin{itemize}
    \pause
 \item Unambiguous
   \pause
\begin{example}[A bad joke]
\textbf{Q:} How many months have 30 days?
\pause

\textbf{A:} 11, some of them have even more!
\pause

:-(
\end{example}
\pause
 \item Objective
   \pause
\begin{example}
\textbf{Good:} 3 is greater than 4

\textbf{Bad:} 3 is nicer than 4
\end{example}
\end{itemize}
\end{frame}

\begin{frame}{Statements}
  \begin{itemize}
 \item Mathematical: ``\emph{Three is greater than four}\,''
                    (or ``$3 > 4$'')
 \item ...or not: ``\emph{I am 26 years old}\,''
 \item \textbf{Key point:} staments can be \textbf{true} or
                     \textbf{false}
\end{itemize}
\end{frame}

%\begin{frame}[plain]
%\begin{center}
%\includegraphics[scale=0.4]{xkcd169.png}
%https://xkcd.com/169/
%\end{center}
%\end{frame}


\section{Logical operations}

\begin{frame}{Logical operations}
\begin{itemize}
\item We can combine statements to make new ones
\item Negation (\textbf{not}), conjunction (\textbf{and}), disjunction
      (\textbf{or})
\end{itemize}
\end{frame}

\begin{frame}{Negation (\textbf{not})}
\begin{center}
If $A$ is a statement, the statement ``not $A$'' (in symbols: $\neg A$) is
\textbf{true} when $A$ is \textbf{false}, and it is \textbf{false} when $A$ is
\textbf{true}.
\pause
\end{center}

\begin{example}
\begin{center}
$\neg (3>4)$ is equivalent to $3\leq 4$

``\emph{$3$ is \textbf{not} greater than $4$}'' is equivalent to
``\emph{$3$ is less or equal than $4$}''
\end{center}
\end{example}
\end{frame}

\begin{frame}{Conjunction (\textbf{and})}
\begin{center}
The statement ``$A$ and $B$'' (in symbols:
$A\land B$) is \textbf{true} when both $A$ and $B$ are \textbf{true}, and it is
\textbf{false} if at \emph{at least} one of them is \textbf{false}.
\pause

\begin{example}
``$(3<4)\land (5$ is an odd number$)$'' is \textbf{true}
\end{example}

\begin{example}
``(Today is Monday) $\land$ (we are in France)'' is \textbf{false}
\end{example}
\end{center}

\end{frame}

\begin{frame}{Disjunction (\textbf{or})}
\begin{center}
The statement ``$A$ or $B$'' (in symbols:
$A\lor B$) is \textbf{true} when at least one of $A$ and $B$ is \textbf{true},
and it is \textbf{false} if both of them are \textbf{false}.
\pause

\begin{example}
``$(3=4)\lor (5$ is an even number$)$'' is \textbf{false}
\end{example}

\begin{example}
``(Today is Monday) $\lor$ (we are in Luxembourg)'' is \textbf{true}
\end{example}
\end{center}

\end{frame}


\begin{frame}{Logical operations}
\begin{itemize}
  \item \textbf{Important:} $\lor$ is always \emph{inclusive}:
   \pause

\begin{center}
\begin{example}[Another bad joke]
Waiter: ``Would you like cheese or dessert?''

Mathematician: ``Yes.''
\end{example}
\end{center}
\pause
 \item $\neg$ has precedence over $\land$ and $\lor$:
    \begin{align*}
      \neg A\land B \text{ means } (\neg A)\land B,\qquad
      \neg A\lor B \text{ means } (\neg A)\lor B
    \end{align*}
    (or just use parenthesis)
\end{itemize}


\end{frame}

\begin{frame}{Properties}
  \begin{center}
    If $A$, $B$ and $C$ are statements:
  \end{center}
  {\fontsize{9}{17}\selectfont
  \begin{align*}
    \begin{array}{cc|c}
      A\land B = B\land A & A \lor B = B\lor A &\textbf{commutativity}\\
      \hline
      A\land (B\land C) = (A\land B)\land C \quad &
      A\lor (B\lor C) = (A\lor B)\lor C & \textbf{associativity}\\
      \hline
      A\land(B\lor C) = (A\land B)\lor(A\land C) & & \textbf{distributivity} \\
      A\lor(B\land C) = (A\lor B)\land(A\lor C) & &\textbf{distributivity*}  \\
      \hline
      \neg(\neg A) = A & & \textbf{double negation} \\
      \hline
      A \land \textbf{true} = A & A \land \textbf{false} = \textbf{false} \\
      A\lor \textbf{true} = \textbf{true} & A \lor \textbf{false} = A \\
      (\neg A) \land A = \textbf{false} & (\neg A) \lor A = \textbf{true} \\
      \hline
      \neg (A\land B) = (\neg A)\lor (\neg B) &
      \neg (A\lor B) = (\neg A)\land (\neg B) & \textbf{De Morgan's laws}
    \end{array}
  \end{align*}}
\end{frame}

%\subsection{Boolean algebra}

\begin{frame}{Boolean algebra}
  \begin{itemize}
    \item For simplicity: \textbf{true}\,$=1$, \textbf{false}\,$=0$
    \pause \item We have a set $\{0,1\}$ with some operations
                 $(\land,\lor,\neg)$
    \pause \item This is called a \textbf{Boolean algebra}
  \end{itemize}
\end{frame}

%\subsection{Truth tables}

\begin{frame}{Truth tables}
  A compact way of describing an operator, or a composition of operators
  \pause
  \vspace{4pt}
  Example:
\begin{align*}
  \begin{array}{|c|c|c|c|c|c|}
    \hline
    A & B & \neg A & A\land B & A\lor B & (A\lor B)\land (\neg A)  \\
    \hline
    0 & 0 & 1 & 0 & 0 & 0 \\
    0 & 1 & 1 & 0 & 1 & 1 \\
    1 & 0 & 0 & 0 & 1 & 0 \\
    1 & 1 & 0 & 1 & 1 & 0 \\
    \hline
  \end{array}
\end{align*}
\end{frame}

\begin{frame}{Truth tables}
  \begin{center}
    We can check that two statements are equivalent with truth tables
  \end{center}
\begin{align*}
  \begin{array}{|c|c|c|c|}
    \hline
    A & B & \neg(A\land B) & (\neg A)\lor (\neg B)\\
    \hline
    0 & 0 & 1 & 1 \\
    0 & 1 & 1 & 1 \\
    1 & 0 & 1 & 1 \\
    1 & 1 & 0 & 0 \\
    \hline
  \end{array}
\end{align*}
\end{frame}


\section{Implication}

\begin{frame}{Implication}
  \begin{itemize}
  \item ``$A\implies B$'' means \emph{``If $A$ (is true), then $B$ (is true)''}
  \end{itemize}
  \pause
  \begin{example}
    \emph{``If it rains, I will bring an umbrella''}

    (It rains)$\implies$(I will bring an umbrella)
  \end{example}
  \pause
  \begin{example}
    \emph{``If my grandpa had wheels, he would be a bike''}

    (My grandpa has wheels)$\implies$(My grandpa is a bike)
  \end{example}
\end{frame}


\begin{frame}{Implication}
    \begin{itemize}
    \item It is a logical operation: ``$A\implies B$'' means ``$B\lor(\neg A)$''
      \pause
    \end{itemize}
  \begin{align*}
    \begin{array}{|c|c|c|c|}
      \hline
      A & B & A\implies B & \\
      \hline
      0 & 0 & 1 & \text{No rain, I don't bring an umbrella} \\
      \hline
      0 & 1 & 1 & \text{No rain, I bring an umbrella anyway} \\
      \hline
      1 & 0 & 0 & \text{It rains, I don't bring an umbrella} \\
      \hline
      1 & 1 & 1 & \text{It rains, I bring an umbrella} \\
      \hline
    \end{array}
  \end{align*}
  \pause
  \begin{remark}
    ``\textbf{false} $\implies A$'' is always \textbf{true}, whatever $A$ is
    (\emph{ex falso quodlibet})
    ``$A\implies$\textbf{true}'' is always true, whatever $A$ is
  \end{remark}
\end{frame}


\begin{frame}{Notation}
  Sometimes we use the following symbols:
  \begin{itemize}
    \item ``$A\impliedby B$'' is the same as ``$B\implies A$''
    \item ``$A\iff B$ is the same as ``$(A\implies B)\land (B\implies A)$''.\\
        It is read ``$A$ is equivalent to $B$'' or ``$A$ if and only if $B$''.
  \end{itemize}
\end{frame}

\begin{frame}{Contrapositive}
  \begin{itemize}
    \item The statement $(\neg B)\implies (\neg A)$ is called
          \emph{contrapositive} of $A\implies B$
    \pause
    \item It is equivalent to ``$A\implies B$''
    \pause
    \item Two proofs:
      \begin{enumerate}
        \item Properties of logical operations
        \item Truth tables
      \end{enumerate}
  \end{itemize}
\end{frame}

\begin{frame}{End of part 1}
  \begin{center}
    \Huge See you tomorrow!
  \end{center}
  \vspace{10pt}
  \refgithub
\end{frame}

\begin{frame}{Elementary logic - part 2}
  \begin{center}
    \Huge Welcome Back!
  \end{center}
  \vspace{10pt}
  \refgithub
\end{frame}


\section{Quantifiers}

\begin{frame}{Quantifiers}
  Let $S$ be a set and let $A(x)$ be a ``variable statement'' that depends on
  $x\in S$ (for example $S=\mathbb{N}$ and $A(x)=$``x is an even number'').
  \pause
  \vspace{12pt}
  \begin{itemize}
    \item \textbf{Universal quantifier} ($\forall$ or ``for all''):
          ``$\forall x\in S,\,A(x)$'' means that if we replace ``$x$'' with any
          element of $S$, $A(x)$ is always \textbf{true}.
  \vspace{9pt}
    \item \textbf{Existential quantifier} ($\exists$ or ``there exists''):
          ``$\exists x\in S,\, A(x)$'' means that $A(x)$ is \textbf{true} for
          at least one value of $x$ is $S$.
  \end{itemize}
  \vspace{12pt}
  \pause
  \textbf{You always need a set $S$}
\end{frame}

\begin{frame}{Quantifiers - examples}
  \begin{example}
  $S=$``the set of all cars'', $A(x)$=``$x$ is red''

  $\forall x\in S,\, A(x)$ is \textbf{false}.

  $\exists x\in S,\, A(x)$ is \textbf{true}.
  \end{example}
  \begin{example}
    $S=\mathbb{N}$, $A(x)=x>5$

  $\forall x\in S,\, A(x)$ is \textbf{false}.

  $\exists x\in S,\, A(x)$ is \textbf{true}.
  \end{example}
\end{frame}

\begin{frame}{Negation of quantifiers}
  \begin{center}
    \textbf{Today's most important fact:}
  \end{center}
  \begin{align*}
    \neg(\forall x\in S,\, A(x))&=\only<1>{\quad?}
    \onslide<2->{\exists x\in S,\,\neg A(x)}\\
    \neg(\exists x\in S,\, A(x))&=\only<1-2>{\quad?}
    \onslide<3->{\forall x\in S,\,\neg A(x)}\\
  \end{align*}
  \onslide<2->{
  \begin{example}
    \begin{center}
  $\neg$``every number is even'' = ``there is at least one odd number''
    \end{center}
  \end{example}
  }
  \onslide<3->{
  \begin{example}
    \begin{center}
    $\neg$``$\exists x\in \mathbb N,\, x+3=9$'' =
    ``$\forall x\in \mathbb N,\, x+3\neq 9$''
    \end{center}
  \end{example}
  }
\end{frame}

\section{Proofs}

\begin{frame}{Proofs}
  \begin{itemize}
    \item A proof is a sequence of statements, each one logically deriving from
          the previous.
          \pause
    \item Proofs are used to derive new statements from statements that are
          known to be true.
          \pause
    \item If $A$ is known to be true and the implication $A\implies B$ is
          logically clear, then also $B$ must be true.
          \pause
    \item Every mathematical theorem must be justified with a proof.
  \end{itemize}
\end{frame}

%\subsection{Direct proofs}
\begin{frame}{Example: direct proof}
  \begin{theorem}
    The sum of two even numbers is even.
  \end{theorem}
  \pause
  \begin{proof}
    \begin{enumerate}
  \item Recall the definition: a natural number $x$ is called \emph{even}
        if there is some natural number $n$ such that $x=2n$.
    \pause
  \item If $x$ and $y$ are even numbers, then there are natural numbers $n$
    and $m$ such that $x=2n$ and $y=2m$.
    \pause
  \item Then $x+y=2n+2m=2(n+m)$.
    \pause
  \item Then $x+y$ is even.
    \end{enumerate} 
  \end{proof}
\end{frame}


%\subsection{Proofs by contradiction}

\begin{frame}{Proofs by contradiction}
  Idea: I want to show $A=\textbf{true}$. I show that the implication
  ``$(\neg A)\implies\textbf{false}$'' is \textbf{true}.
  Then $\neg A=\textbf{false}$, so $A=\textbf{true}$.
  \pause
\begin{definition}
  A natural number is called \emph{prime} if it is different from $1$ and it
  is only divisible by $1$ and itself.
\end{definition}
  \begin{theorem}
    There are infinitely many prime numbers.
  \end{theorem}

\end{frame}

\begin{frame}{Proofs by contradiction}
  \begin{theorem}
    There are infinitely many prime numbers.
  \end{theorem}
  \pause
  \begin{proof}
    \begin{enumerate}
    \item Assume that there are only finitely many prime numbers.
    \pause
    \item $\exists n\in \mathbb N$, there are $n$ prime numbers. Call them
          $p_1,p_2,\dots,p_n$.
    \pause
    \item Let $u=p_1\times p_2\times \dots \times p_n +1$.
    \pause
    \item $u$ is not divisible by any of the prime numbers $p_1,\dots,p_n$.
    \pause
    \item Therefore $u$ is only divisible by $1$ and itself. So $u$ is prime.
    \pause
    \item So $p_1,\dots,p_n$ are not the only prime numbers.
    \end{enumerate}
  \end{proof}

\end{frame}


%\subsection{Proofs by induction}

\begin{frame}{Proofs by induction}
  If I want to prove $\forall n\in \mathbb N,\, A(n)$:
  \begin{enumerate}
    \item Prove $A(0)$ (\emph{base step})
    \item Prove $\forall n\in \mathbb N,\, (A(n)\implies A(n+1))$
    (\emph{inductive step})
  \end{enumerate}
  \pause
  \begin{theorem}[Sum of natural numbers]
    $\forall n\in \mathbb N,\quad 0+1+\cdots + n=\frac{n(n+1)}{2}$
  \end{theorem}

\end{frame}


\begin{frame}
  \begin{proof}
  \begin{enumerate}
  \item Base case: $0=0$.
    \pause
  \item Let $n$ be any natural number.
    \pause
      
      If $A(n)=\textbf{false}$, then $A(n)\implies A(n+1)$ is \textbf{true}.
      \pause

      If $A(n)=\textbf{true}$, we have to show that $A(n+1)=\textbf{true}$.
      \pause
      
      \begin{align*}
        \begin{array}{rlr}
          0+\cdots +(n+1)& = (0+\cdots+ n)+(n+1)=\\
          & = \frac{n(n+1)}{2}+(n+1)= & \text{since }A(n)=\textbf{true}\\
          & = \frac{n^2+n+2n+2}{2}\\
          & = \frac{(n+1)(n+2)}{2}
        \end{array}
      \end{align*}
      so $A(n+1)=\textbf{true}$

  \end{enumerate}
  \end{proof}
\end{frame}

\begin{frame}{The end}
  What you have learned in this course:
  \begin{itemize}
    \item Basic logic operations and logic implication
    \item Quantifiers and \textbf{their negation}
    \item Some basic mathematical proofs
  \end{itemize}
  \vspace{10pt}
  \refgithub
\end{frame}


\end{document}