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