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}