Quantified Logic

Videos (~50 mins)

Reading (~30 mins)

DMOI, “Beyond Propositions” (it’s a short section).
(Optional): How To Be Right by Dr. Eugenia Cheng

Warmup (~45 mins)

Problem 1

In his letter to a leading Roman agriculturist, the statesman and writer Marcus Tullius Cicero (106 BCE–43BCE) wrote:

If you have a garden and a library, then you have everything you need.

Let \(G\) be the set of all gardens, \(L\) be the set of all libraries, and \(N\) be the set of things that you need. Finally, let \(H(x)\) be the statement that you have \(x\).

Part A

Use quantifiers and logical operators to translate Cicero’s statement into symbols.

Part B

The contrapositive of the statement \(p \rightarrow q\) is the statement \(\lnot q \rightarrow \lnot p\). As you may remember, the contrapositive is logically equivalent to the original implication. Write the contrapositive of your translation from Part A. Simplify your answer so that negation symbols \(\lnot\) appear only directly in front of predicates.

Note: Part A of this problem relates directly to Learning Target L1. Part B relates directly to Learning Target L2.

Problem 2

Simplify the statements below (so negation appears only directly next to predicates). In order to simplify your calculations, it’s ok to use a notational shortcut. You can assume that the domain of quantification is always the set \(\mathbb{Z}\) of integers, and therefore write \(\exists x\) when what you really mean is \(\exists x \in \mathbb{Z}\). This kind of notational shortcut is usually ok as long as you explicitly say that you are using it!.

Please give your solution in standard form, as a sequence of logical equivalences with cited justifications given for each step on the righthand side.

Note that, when working with integers, \(\lnot(x < y)\equiv (y \leq x)\).

\(\lnot \exists x \in \mathbb{Z}: \forall y \in \mathbb{Z},(\lnot O(x) \lor E(y))\)
\(\lnot \forall x ,\lnot \forall y, \lnot ((x < y) \land \exists z((x < z)\lor (y < z)))\)

Note: this problem is the first two parts of 3.16 in DMOI, and it has an online solution. I recommend that you try this problem on your own first, carefully show all your steps, and then check against the solution.

Note: Both parts of this problem relate directly to Learning Target L2.