Skip to main content\( \newcommand{\identity}{\mathrm{id}}
\newcommand{\notdivide}{{\not{\mid}}}
\newcommand{\notsubset}{\not\subset}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\gf}{\operatorname{GF}}
\newcommand{\inn}{\operatorname{Inn}}
\newcommand{\aut}{\operatorname{Aut}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\cis}{\operatorname{cis}}
\newcommand{\chr}{\operatorname{char}}
\newcommand{\Null}{\operatorname{Null}}
\def\Z{\mathbb Z}
\def\R{\mathbb R}
\def\Q{\mathbb Q}
\def\N{\mathbb N}
\def\C{\mathbb C}
\def\W{\mathbb W}
\def\ba{{\mathbf{a}}}
\def\bb{\mathbf{b}}
\def\bh{{\mathbf{h}}}
\def\bu{{\mathbf{u}}}
\def\bv{{\mathbf{v}}}
\def\bw{{\mathbf{w}}}
\def\bx{{\mathbf{x}}}
\def\by{\mathbf{y}}
\def\bone{{\mathbf{1}}}
\def\bzero{\mathbf{0}}
\def\var{{\mbox{var}}}
\def\P{{\mathbb{P}}}
\def\E{{\mathbb{E}}}
\def\cA{{\mathcal{A}}}
\def\cB{{\mathcal{B}}}
\def\cC{{\mathcal{C}}}
\def\cP{\mathcal P}
\def\cN{\mathcal N}
\def\cE{\mathcal E}
\def\cO{\mathcal O}
\def\cF{\mathcal F}
\def\cX{\mathcal X}
\def\nimsum{\, \oplus \,}
\def\mex{{\mathrm{mex}}}
\newcommand{\pile}[1]{\bullet{#1}}
\def\g{g}
\def\kin{k^{\mathrm{in}}}
\def\kout{k^{\mathrm{out}}}
\newcommand{\indeg}[1]{k^{\mathrm{in}}_{#1}}
\newcommand{\outdeg}[1]{k^{\mathrm{out}}_{#1}}
\tikzset{->-/.style={decoration={
markings,
mark=at position .5 with {\arrow{latex}}},postaction={decorate}}}
\newcommand{\nimbleboard}[1]{
\begin{scope}[shift={(.25, .4)}]
\draw (0,-.3) -- (#1,-.3) -- (#1+.45, .7) -- (#1+.45, 1);
\draw (0,0) -- (#1,0);
\draw (.45,1) -- (#1+.45,1);
\foreach \i in {0, ..., #1} {
\draw (\i, -.3) -- (\i, 0) -- (\i+.45,1);
}
\foreach \i in {1, ..., #1} {
\node[style={font=\sffamily\scriptsize}] at (\i - .5, -.15) {\i};
}
\end{scope}
}
\newcommand{\coin}[1]{
\begin{scope}[shift={#1}]
\draw[color=white, fill=white] (-.4, 0) -- (-.4, -.1) -- (.4,-.1) -- (.4,0) -- cycle;
\draw[thick, fill=white] (0,0) ellipse (0.4 and 0.10);
\draw[thick, fill=white] (.4,-.1) arc (0:-180:0.4 and 0.10);
\draw[thick] (0.4,0) -- (0.4, -.1);
\draw[thick] (-0.4,0) -- (-0.4, -.1);
\end{scope}
}
\newcommand{\bean}[2]{
\begin{scope}[shift={#1}, rotate={#2}]
\draw [very thick, fill=gray!50] plot [smooth cycle] coordinates {(-.2,0) (-.175, .07) (-.1,.1) (0,.075) (.1,.1) (.175, .07) (.2,0) (.15, -.07) (0,-.1) (-.15, -.07)};
\end{scope}
}
\newcommand{\heap}[2]{
\begin{scope}[shift={#1}]
\draw[very thick] (0,0) circle ({#2});
\end{scope}
}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\)
Chapter 3 Logical Connectors and Quantifiers
Exercises Practice Problems
1. Two Truth Tables.
-
Fill in this truth table.
\begin{equation*}
\begin{array}{c|c|c|c}
P & Q & P \wedge Q & \neg (P \wedge Q) \\
\hline
T & T & & \\
T & F & & \\
F & T & & \\
F & F & & \\
\end{array}
\end{equation*}
Solution.
\begin{equation*}
\begin{array}{c|c|c|c} %mathbook tabular
P & Q & P \wedge Q & \neg (P \wedge Q) \\
\hline
T & T & T& F\\
T & F & F & T\\
F & T & F & T\\
F & F & F & T\\
\end{array}
\end{equation*}
-
Now fill in this truth table.
\begin{equation*}
\begin{array}{c|c|c|c|c}
P & Q & \neg P & \neg Q & \neg P \vee \neg Q \\
\hline
T & T & & & \\
T & F & & & \\
F & T & & & \\
F & F & & & \\
\end{array}
\end{equation*}
Solution.
\begin{equation*}
\begin{array}{c|c|c|c|c}
P & Q & \neg P & \neg Q & \neg P \vee \neg Q \\
\hline
T & T & F& F& F \\
T & F & F & T & T\\
F & T & T & F & T\\
F & F & T & T & T \\
\end{array}
\end{equation*}
Look at the last column of each of the two tables above. What do you conclude? Write a mathematical statement (using symbols) that summarizes your observation. Solution.
These two statements are equivalent. In other words, \[ \neg (P \wedge Q) \Longleftrightarrow \neg P \vee \neg Q. \]
2. Truth Table for \(\neg (P \vee Q)\).
Fill in the following truth table. Using the previous problems as inspiration, find another compound statement that is equivalent to \(\neg (P \vee Q)\text{.}\) Add columns to your truth table to show that you are correct.
\begin{equation*}
\begin{array}{c|c|c|c}
P & Q & P \vee Q & \neg (P \vee Q) \\
\hline
T & T & & \\
T & F & & \\
F & T & & \\
F & F & & \\
\end{array}
\end{equation*}
Solution.
\begin{equation*}
\begin{array}{c|c|c|c|c|c|c} %mathbook tabular
P & Q & P \vee Q & \neg (P \vee Q) & \neg P & \neg Q & \neg P \wedge \neg Q \\
\hline
T & T & T & F & F & F & F \\
T& F & T& F & F & T& F \\
F & T& T& F & T & F & F \\
F & F & F & T & T & T & T \\
\end{array}
\end{equation*}
3. The Effect of Negation.
Look back at the last two problems. What is the effect of negation on the AND operator? The OR operator? Solution.
Under negation, AND becomes OR, while OR becomes AND.
4. 16 Compound Statements using \(P\) and \(Q\).
The table below shows that are 16 possible outcomes for a compound statement involving \(P\) and/or \(Q\text{.}\) Find a statement corresponding to each of these 16 possibilities! Most of your statements will depend on both \(P\) and \(Q\text{,}\) but some will only depend on one or the other.
You will need one final connector: the exclusive or \(P \oplus Q\) which is true when exactly one of \(P\) and \(Q\) is true.
\begin{equation*}
\begin{array}{c|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
P & Q & & & & & & & &
& & & & & & &
& \\
\hline
T&T&T&T&T&T&T&T&T&T&F&F&F&F&F&F&F&F\\
T&F&T&T&T&T&F&F&F&F&T&T&T&T&F&F&F&F\\
F&T&T&T&F&F&T&T&F&F&T&T&F&F&T&T&F&F\\
F&F&T&F&T&F&T&F&T&F&T&F&T&F&T&F&T&F
\end{array}
\end{equation*}
Solution.
I'll split this into two tables for readability. We have
\begin{equation*}
\begin{array}{c|c||c|c|c|c|c|c|c|c}
P & Q & P \vee \neg P & P \vee Q & P \vee \neg Q & P & \neg P \vee Q & Q & P \Leftrightarrow Q & P \wedge \neg Q \\
\hline
T&T&T&T&T&T&T&T&T&T\\
T&F&T&T&T&T&F&F&F&F\\
F&T&T&T&F&F&T&T&F&F\\
F&F&T&F&T&F&T&F&T&F
\end{array}
\end{equation*}
and
\begin{equation*}
\begin{array}{c|c||c|c|c|c|c|c|c|c}
P & Q & P \wedge \neg P & P \oplus Q & \neg Q & P \wedge \neg Q & \neg P & \neg P \wedge Q & \neg P \wedge \neg Q & P \wedge \neg P \\
\hline
T&T&F&F&F&F&F&F&F&F\\
T&F&T&T&T&T&F&F&F&F\\
F&T&T&T&F&F&T&T&F&F\\
F&F&T&F&T&F&T&F&T&F
\end{array}
\end{equation*}
Hopefully, you noticed that there is an "anti-symmetry" to this table. The first column is the negation of the last column. The second column is the negation of the second-to-last column, and so on! So you can negate the \(k\)th statement \(k\) to find the \((17-k)\)th statement.
5. Sets and Logic.
For \(x \in \mathbb Z\text{,}\) consider the statements
\begin{equation*}
P(x) = \mbox{" is even"} \qquad \qquad
Q(x) = \mbox{" is positive"}
\end{equation*}
and let \(A\) and \(B\) be the sets
\begin{equation*}
A = \{ x \in \mathbb{Z} \mid P(x) \mbox{ is true} \} \qquad \qquad
B = \{ x \in \mathbb{Z} \mid Q(x) \mbox{ is true} \}
\end{equation*}
Fill in the blanks using the symbols \(A\text{,}\) \(B\text{,}\) \(\cup\) and \(\cap\text{.}\)
\begin{equation*}
\begin{array}{rcl}
\underline{\phantom{asdasdasd}} = \{ x \in \mathbb{Z} \mid P(x) \wedge Q(x) \mbox{ is true} \} \\
\underline{\phantom{asdasdasd}} = \{ x \in \mathbb{Z} \mid P(x) \vee Q(x) \mbox{ is true} \}
\end{array}
\end{equation*}
You have just turned an expression about mathematical statements into an expression about sets! Solution.
\begin{equation*}
\begin{array}{rcl}
A \cap B = \{ x \in \mathbb{Z} \mid P(x) \wedge Q(x) \mbox{ is true} \} \\
A \cup B = \{ x \in \mathbb{Z} \mid P(x) \vee Q(x) \mbox{ is true} \}
\end{array}
\end{equation*}
6. Order of Quantifiers.
In this problem, we will see that the order of our quantifiers matters
-
Consider the statement
\begin{equation*}
\exists y \in \mathbb{R}, \forall x \in \mathbb{R}, x = y^3.
\end{equation*}
Restate the above in plain English (as well as you can). Is this statement true or false? Solution.
The statement is: "There exists a \(y \in \R\text{,}\) such that for all \(x \in \R\text{,}\) we have \(x=y^3\text{.}\)" This is false since this statement says that there is a single number \(y\) that works for every \(x\) simultaneously.
-
Now consider the statement
\begin{equation*}
\forall y \in \mathbb{R}, \exists x \in \mathbb{R}, x = y^3.
\end{equation*}
Restate the above in plain English (as well as you can). Is this statement true or false? Solution.
The statement is: "For each \(y \in \R\text{,}\) there exists an \(x \in \R\text{,}\) such that \(x=y^3\text{.}\)" This statement is true. This time, the choice of \(x\) depends on the given \(y\text{.}\) In particular, we take \(x = \sqrt[3]{y}\text{.}\)
7. Bounded and Unbounded.
Here is a mathematical definition for a bounded set.
"A set \(S \subset \mathbb{R}\) is bounded if there is an \(M \in \mathbb{R}\) such that \(|x| \leq M\) for all \(x \in S\text{.}\) A set is unbounded if no such \(M\) exists."
Rewrite the definition of bounded only using mathematical symbols and quantifiers. Solution.
\[ \exists M \in \R, \forall x \in S, |x| \leq M. \]
The definition of unbounded is the negation of your statement in part (a). Write an equivalent statement that does not use a negation sign. Then rewrite that statement in plain English. Solution.
\[ \forall M \in \R, \exists x \in S, |x| > M. \] For every \(M \in \R\text{,}\) there exists an \(x \in S\) such that \(|x| > M\text{.}\)