From 948b1ef72cafacede96563f21a3e2a5a5621cd9d Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Fri, 17 Sep 2021 10:44:04 +0200 Subject: Solutions available --- solutions/preplogic-solutions.tex | 306 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 306 insertions(+) create mode 100644 solutions/preplogic-solutions.tex (limited to 'solutions/preplogic-solutions.tex') diff --git a/solutions/preplogic-solutions.tex b/solutions/preplogic-solutions.tex new file mode 100644 index 0000000..86c9efe --- /dev/null +++ b/solutions/preplogic-solutions.tex @@ -0,0 +1,306 @@ +\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{proof}[Solution] + \begin{enumerate} + \item \textbf{True}: regardless of when you solve this exercise, Germany + has more inhabitants than Luxembourg. + \item \textbf{True} + \item \textbf{False}: the number $2^{2^5}+1=4294967297=641\times 6700417$ + is not prime. + \end{enumerate} +\end{proof} + +\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{proof}[Solution] + ``\emph{I did not pay attention in class \textbf{or} I did my homework}'' +\end{proof} + +\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} +\begin{proof}[Solution] + They are equivalent to the following (you can check with truth tables): + \begin{enumerate} + \item $A$ + \item $A$ + \item $B\land \neg A$ + \item $A\lor B$ + \item Let's do this one in more steps: + \begin{align*} + (\neg (A\lor \neg B))\land ((A\lor C) \land \neg C)= + &(\neg A\land B)\land ((A\lor C)\land \neg C)=\\ + =&(\neg A\land B)\land ((A\land \neg C)\lor (C\land \neg C))=\\ + =&(\neg A\land B)\land ((A\land \neg C)\lor \textbf{false})=\\ + =&(\neg A\land B)\land (A\land \neg C)=\\ + =&A\land \neg A\land B\land \neg C=\\ + =&\textbf{false} + \end{align*} + \end{enumerate} +\end{proof} + +\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 & 0 & 0 \\ + \hline + 0 & 0 & 1 & 0 & 1 \\ + \hline + 0 & 1 & 0 & 0 & 0 \\ + \hline + 0 & 1 & 1 & 0 & 1 \\ + \hline + 1 & 0 & 0 & 1 & 1 \\ + \hline + 1 & 0 & 1 & 1 & 1 \\ + \hline + 1 & 1 & 0 & 0 & 0 \\ + \hline + 1 & 1 & 1 & 0 & 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{proof}[Solution] + Let's rewrite the first part in terms of basic logical operations: + \begin{align*} + (A\implies B)\land (B\implies C)=&(B\lor \neg A)\land(C\lor \neg B) + \end{align*} + now we can write a truth table for the two parts + \begin{align*} + \begin{array}{|c|c|c|c|c|} + \hline + A & B & C & (B\lor\neg A)\land(C\lor\neg B) & A\implies C \\ + \hline + 0 & 0 & 0 & 1 & 1 \\ + \hline + 0 & 0 & 1 & 1 & 1 \\ + \hline + 0 & 1 & 0 & 0 & 1 \\ + \hline + 0 & 1 & 1 & 1 & 1 \\ + \hline + 1 & 0 & 0 & 0 & 0 \\ + \hline + 1 & 0 & 1 & 0 & 1 \\ + \hline + 1 & 1 & 0 & 0 & 0 \\ + \hline + 1 & 1 & 1 & 1 & 1 \\ + \hline + \end{array} + \end{align*} + With the help of the truth table we see that whenever the first part + ``$(\neg (A\lor \neg B))\land ((A\lor C) \land \neg C)$'' is true, also the + implication ``$A\implies C$'' is true. This shows that the ``big + implication'' is true. (If you are not convinced, you can add more details to + this proof, for example by writing more truth tables.) +\end{proof} + +\begin{exercise} +What is the contrapositive of ``\emph{If this table is not reserved, we sit +here}'' ? +\end{exercise} +\begin{proof}[Solution] + ``\emph{If we do not sit here, this table is reserved}''. One could also say + this in another way, for example ``\emph{We do not sit here because this + table is reserved}''. +\end{proof} + +\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{proof}[Solution] + \begin{enumerate} + \item $\forall x\in\mathbb N,\, x^2-2\neq 0$ + \item ``There is at least one prime number which is even'' + \item ``I have met at least one person that does not like pizza'' + \item ``Every number is less or equal than $7$'' + \item $\exists x\in\mathbb N,\, x<0$ + \item $\exists x\in \mathbb Z,\, (\forall y\in \mathbb Z,\, x+y\neq 0)$ + \end{enumerate} +\end{proof} + +\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} +\begin{proof}[Solution] + The idea is that we want to write ``\emph{there is $x\in S$ such that $A(x)$ + is true, \textbf{and}, for any other $y\in S$, $A(y)$ is false}. From this + we see that the structure of the statement is + \begin{align*} + \exists x\in S,\,(\text{``something''}\land\text{``something else''}) + \end{align*} + The ``something'' part is just $A(x)$. The ``something else'' part can be + written in different ways, for example + \begin{align*} + \forall y\in S,\,(y\neq x\implies \neg A(y)) \quad \text{or} + \quad \forall y\in S,\,(A(y)\implies y=x) + \end{align*} + (notice that the two implications above are one the contrapositive of the + other); or also + \begin{align*} + \forall y\in S\setminus \{x\},\, \neg A(y) + \end{align*} + So in conclusion, one way to define ``$\exists!$'' is the following: + \begin{align*} + \exists!x\in S,\,A(x)\quad:=\quad\exists x\in S,\,(A(x)\land + (\forall y\in S,\,(A(y)\implies y=x))) + \end{align*} + +\end{proof} + +\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{proof}[Solution] + \textbf{Base case:} for $n=0$ the sum is empty, so we have $0=0$ which is + true. (If you do not think that the formula makes sense for $n=0$, you can do + prove it for $n\geq 1$ and fo $n=1$ as a base case.) + + \textbf{Inductive step:} we can assume that the formula works for a generic + (but fixed) $n\in\mathbb N$ and prove that then it also works for $n+1$. So: + \begin{align*} + \sum_{k=1}^{n+1}(2k-1)&=\left(\sum_{k=1}^{n}(2k-1)\right)+2(n+1)-1=\\ + &=n^2 +2(n+1)-1=\\ + &=n^2+2n+1=\\ + &=(n+1)^2 + \end{align*} + which is the formula for $n+1$. +\end{proof} + +\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{proof}[Solution] + \textbf{Base case:} here the base case is $n=4$, and we have + $4!=24\geq 16=2^4$. + + \textbf{Inductive step:} we can assume that the inequality is true for $n$, + and prove that it is also true for $n+1$. We have: + \begin{align*} + (n+1)!=(n+1)\times n!\geq (n+1)\times 2^n\geq 2^{n+1} + \end{align*} +\end{proof} + +\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{proof}[Solution] + The statement is \textbf{false}. Since it starts with a universal + quantifier, in order to prove that it is false we just need to provide one + example of $n\in \mathbb N$ which makes it false. In other words, we need to + prove that + \begin{align*} + \exists n\in \mathbb N,\, n^2-4n+5\leq n + \end{align*} + and a proof of this fact is very simple: for $n=2$ we have + $2^2-4\times 2+5=1\leq 2$. +\end{proof} + +\begin{exercise} + Do the last point of Exercise 1.1 again, but this time give a proof of your + answer. +\end{exercise} +\begin{proof}[Solution] + Again, since we have to prove that the statement is false, we just need to + show one counterexample. for example, the number + $2^{2^5}+1=4294967297=641\times 6700417$ is not prime. +\end{proof} + + + + +\end{document} -- cgit v1.3