Skip to main content
Contents Index Dark Mode Prev Up Next \(\newcommand{\im}{{\mathrm{im}}}
\newcommand{\given}{{\, :\,}}
\newcommand{\hanoi}{\mathrm{hanoi}}
\newcommand{\lcm}{{\mathrm{lcm}}}
\newcommand{\ID}{{\mathrm{ID}}}
\newcommand{\chr}{{\mathtt{chr}}}
\newcommand{\ord}{{\mathtt{ord}}}
\newcommand{\set}[1]{\left\lbrace #1 \right\rbrace}
\newcommand{\seq}[2]{( #1 )_{#2}}
\newcommand{\gr}[1]{\left( #1 \right)}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\size}[1]{\# #1}
\newcommand{\id}[1]{\mathrm{id}_{#1}}
\newcommand{\ip}[1]{\left\langle #1 \right\rangle}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\ceiling}[1]{\left\lceil #1\right\rceil}
\newcommand{\indemph}[1]{{\textbf{\emph{#1}}\index{#1}}}
\renewcommand{\implies}{\to}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\lxor}{\oplus}
\newcommand{\cP}{\wp}
\newcommand{\pset}{\cP}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\barr}[1]{\overline{#1}}
\newcommand{\sage}{\textsc{Sage}}
\newcommand{\magma}{\textsc{Magma}}
\newcommand{\bob}{\text{Bob}}
\newcommand{\true}{\text{T}}
\newcommand{\false}{\text{F}}
\newcommand{\ahat}{\hat{a}}
\newcommand{\ah}{\ahat}
\newcommand{\bhat}{\hat{b}}
\newcommand{\abar}{\bar{a}}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cW}{\mathcal{W}}
\newcommand{\todo}[1]{{\color{red} TODO: #1}}
\renewcommand{\div}{\operatorname{div}}
\newcommand{\gexp}[3]{#1^{#2 #3}}
\newcommand{\gexpp}[3]{\displaystyle\left(#1\right)^{#2 #3}}
\newcommand{\glog}[3]{\log_{#1}^{#3}#2}
\def\dbend{{!!!}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Exercises 1.3.5 Exercises
1.
Give the definition for these terms. Be sure to set up any notation that is required.
universal quantification of a propositional function
existential quantification of a proposition function
logically equivalent statements involving predicates and quantifiers
2. State precisely De Morgan’s laws for quantifiers. Be sure to set up any notation that is required.
3.
Let \(P(x)\) denote the propositional function “\(x\leq 10\text{,}\) ” with domain \(\RR\text{.}\) What are these truth values?
\(\displaystyle \forall x \,P(x)\)
\(\displaystyle \exists x \,P(x)\)
4.
Let \(S(x)\) be the statement “\(x\) studies more than 30 hours per week,” where the domain for \(x\) consists of all students in MAT 253. Express each of these quantifications in English.
\(\displaystyle \exists x \,S(x)\)
\(\displaystyle \exists x\lnot S(x)\)
\(\displaystyle \forall x \,S(x)\)
\(\displaystyle \forall x\lnot S(x)\)
5.
Let \(B(x)\) be the statement “\(x\) has a bird,” let \(C(x)\) be the statement “\(x\) has a cat,” and let \(D(x)\) be the statement “\(x\) has a dog,” where the domain for \(x\) is all MAT 253 students. Express each of these statements in terms of \(B(x)\text{,}\) \(C(x)\text{,}\) \(D(x)\text{,}\) quantifiers, and logical operators.
There is a student in MAT 253 that has a bird, a cat, and a dog.
Every student in MAT 253 has a dog.
No student in MAT 253 has a bird.
Every student in MAT 253 that has a dog also has a bird.
Some student in MAT 253 has a bird, a cat, or a dog.
6.
Determine the truth value of each of these statements if the domain of all variables consists of all integers.
\(\displaystyle \forall n \,(n^2 \geq 0)\)
\(\displaystyle \forall n \,(n^2 \gt 0)\)
\(\displaystyle \exists n \,(n^2 \gt 0)\)
\(\displaystyle \forall n \,(n \ge 0\lor n \lt 0)\)
\(\displaystyle \exists n \,(n \ge 0\land n \lt 0)\)
7.
Translate each of these statements into logical expressions using predicates, quantifiers, and logical operators.
Some old dogs can learn new tricks.
8.
Prove each of these universally quantified statements false by providing a counterexample, where the domain for all the variables consists of all real numbers.
\(\displaystyle \forall x \,(x^2 \gt 0)\)
\(\displaystyle \forall x \,(x^2 \geq x)\)
\(\displaystyle \forall x \,((x + 3)^2 = x^2 + 3^2)\)
\(\displaystyle \forall x \,(\frac{x}{2}\text{ is rational})\)
\(\displaystyle \forall x \,(\sqrt{x^2} = x)\)
9.
Prove each of these existential statements true by providing a witness, where the domain for all the variables consists of all real numbers.
\(\displaystyle \exists x \,(3x \text{ is irrational})\)
\(\displaystyle \exists x \,(x^2\leq 0)\)
\(\displaystyle \exists x \,(1 \lt x \lt 2)\)
\(\displaystyle \exists x \,((x + 3)^2 = x^2 + 3^2)\)
\(\displaystyle \exists x \,(\pi x^2\text{ is an integer})\)
10. Let
\(D(x)\) be “
\(x\) is an odd duck”, and let
\(M(x)\) be “
\(x\) is a mathematician”, with domain consisting of all people.
Express the statement “Every mathematician is an odd duck” in terms of
\(D(x)\) ,
\(M(x)\) , quantifiers, and logical operators.
11. Let
\(Q(x)\) be the statement “
\(2x \lt 0.001\) ” with domain the set of all real numbers. What is the truth value of
\(\exists x \,Q(x)\) ? Explain.
12.
Express each of these statements using quantifiers. Use De Morgan’s laws for quantifiers to find the negation of each of these statements. Form the negation of the statement so that no negation is to the left of the quantifier. Finally, express the negation in simple English. (Do not simply use the phrase “It is not the case that \dots”)
Some students do not study every day.
Some integers are rational numbers.
All real numbers are integers.
13. Consider the propositional functions
\(M(x) =\) “
\(x\) is a mathematician”,
\(S(x) =\) “
\(x\) is silly”, and
\(C(x) =\) “
\(x\) drinks coffee”, with domain the set of all people.
Express each of the following sentences in terms of \(M(x)\) , \(S(x)\text{,}\) \(C(x)\) , quantifiers, and logical operators.
No mathematician is silly.
All mathematicians drink coffee.
Mathematicians that do not drink coffee are silly.
Some people that drink coffee are not silly.
Not all silly people are mathematicians.
14. Alice was overheard saying, “I will go out with Bob when pigs fly.” Rewrite this in the form “if
\(p\) , then
\(q\text{.}\) ” Assuming that Alice speaks the truth, use propositional logic to explain what, if any, implications this has for Alice and Bob.
15.
Suppose we have the following rules for Alice.
Taylor’s rule
Alice eats her veggies, or she can’t have dessert.
Leslie’s rule
If Alice eats her veggies, then she can have dessert.
Alex’s rule
Alice can have her dessert, when she eats her veggies.
Cameron’s rule
Alice can have her dessert, only if she eats her veggies.
Alice’s rule
Alice can have her dessert.
If Alice’s parents agree on a rule, what are their names ? (They do not have the same name. There may be more than one correct answer.)
