preplogic

Notes for the course "elementary logic"
git clone https://git.tronto.net/preplogic
Download | Log | Files | Refs | README

preplogic-exercises.tex (4576B)


      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 
     27 \begin{exercise}
     28   What is the negation of the sentence ``\emph{I payed attention in class and I
     29   did not do my homework}'' ?
     30 \end{exercise}
     31 
     32 \begin{exercise}
     33   Simplify the following logical expressions using the properties of logical
     34   operations (where $A,B$ and $C$ are statements):
     35   \begin{enumerate}
     36     \item $A\land(A\lor B)$
     37     \item $A\lor (B\land A)$
     38     \item $(A\lor B) \land \neg A$
     39     \item $A \lor (\neg A\land B)$
     40     \item $(\neg (A\lor \neg B))\land ((A\lor C) \land \neg C)$
     41   \end{enumerate}
     42 \end{exercise}
     43 
     44 \section{Implication}
     45 
     46 \begin{exercise}
     47   Fill in the following truth table:
     48   \begin{align*}
     49     \begin{array}{|c|c|c|c|c|}
     50       \hline
     51       A & B & C & \neg(A\implies B) & (A\implies B) \implies C \\
     52       \hline
     53       0 & 0 & 0 & & \\
     54       \hline
     55       0 & 0 & 1 & & \\
     56       \hline
     57       0 & 1 & 0 & & \\
     58       \hline
     59       0 & 1 & 1 & & \\
     60       \hline
     61       1 & 0 & 0 & & \\
     62       \hline
     63       1 & 0 & 1 & & \\
     64       \hline
     65       1 & 1 & 0 & & \\
     66       \hline
     67       1 & 1 & 1 & & \\
     68       \hline
     69     \end{array}
     70   \end{align*}
     71 \end{exercise}
     72 
     73 \begin{exercise}[Transitivity]
     74   Prove that the following statement is true for any statements $A,B$ and $C$:
     75   \begin{align*}
     76     ((A\implies B)\land (B\implies C))\implies (A\implies C)
     77   \end{align*}
     78 \end{exercise}
     79 
     80 \begin{exercise}
     81 What is the contrapositive of ``\emph{If this table is not reserved, we sit
     82 here}'' ?
     83 \end{exercise}
     84 
     85 \section{Quantifiers}
     86 
     87 \begin{exercise}
     88   Write the negation of the following statements:
     89   \begin{enumerate}
     90     \item $\exists x\in \mathbb N,\, x^2-2=0$
     91     \item ``Every prime number is odd''
     92     \item ``Every person I have met likes pizza''
     93     \item ``There is at least one number greater than $7$''
     94     \item $\forall x\in \mathbb N,\,x\geq 0$
     95     \item $\forall x\in \mathbb Z,\,(\exists y\in\mathbb Z,\,x+y=0)$
     96   \end{enumerate}
     97 \end{exercise}
     98 
     99 \begin{exercise}
    100   There is another quantifier that we did not cover in the lecture, namely
    101   $\exists!$ (read ``there exists exactly one''). For example, the sentence
    102   ``\emph{there exists exactly one natural number x such that x+2=5}'' can be
    103   written in symbols as ``$\exists!x\in \mathbb N,\,x+2=5$''.
    104 
    105   In this exercise, your task is to give a formal definition of this quantifier
    106   using the logical symbols that we have defined in class. In particular, you
    107   will need the following:
    108   \begin{itemize}
    109     \item the universal ($\forall$) and existential ($\exists$) quantifiers
    110     \item the conjunction $\land$
    111     \item the implication $\implies$
    112   \end{itemize}
    113   Moreover, you will need the equality symbol $=$ between two elements of a set
    114   (if $a$ and $b$ are two elements of the same set, ``$a=b$'' is a mathematical
    115   statement and it is \textbf{true} if and only if $a$ and $b$ are the same
    116   element).
    117   
    118   \emph{Warning: your definition must depend on a set $S$ and on a ``variable
    119   statement'' $A(x)$, as the existential and universal quantifiers.}
    120 \end{exercise}
    121 
    122 \section{Proofs}
    123 
    124 \begin{exercise}
    125   Prove by induction that
    126   \begin{align*}
    127     \forall n\in\mathbb N,\quad \sum_{k=1}^n(2k-1)=n^2
    128   \end{align*}
    129     (here $\sum_{k=1}^n(2k-1)$ means $1+3+5+\cdots+ (2n-1)$).
    130 \end{exercise}
    131 
    132 \begin{exercise}
    133   If $n\in \mathbb N$ the \emph{factorial} of $n$, denoted by $n!$ is defined
    134   as follows:
    135   \begin{align*}
    136     n!=\begin{cases}
    137       1&\text{if } n=0,\\
    138       n\times (n-1)! & \text{if } n> 0.
    139     \end{cases}
    140   \end{align*}
    141   Prove by induction that if $n\geq 4$ then $n!\geq 2^n$.
    142 \end{exercise}
    143 
    144 
    145 \begin{exercise}
    146   Is the following statement true or false? Give a proof of your answer.
    147   \begin{align*}
    148     \forall n\in \mathbb N,\, n^2 -4n +5>n
    149   \end{align*}
    150 \end{exercise}
    151 
    152 \begin{exercise}
    153   Do the last point of Exercise 1.1 again, but this time give a proof of your
    154   answer.
    155 \end{exercise}
    156 
    157 
    158 
    159 \end{document}