Challenging Exercises

Chapter 4 Challenging Exercises

Checkpoint 4.0.1.

Statements (1) and (2) below are implicitly of the form \(\lnot (\forall x \in D [p(x) \implies q(x)])\text{.}\) In this exercise, you will rewrite them to be explicitly of this form.

Using logical notation, rewrite each of statements (1) and (2) in this form, with appropriate domain of discourse \(D\text{,}\) and appropriate propositional functions \(p(x)\) and \(q(x)\) (you may not want to use “\(x\)” as the variable). You answer will look like

\begin{equation*} \lnot \bigg(\forall \underline{\qquad} \in \underline{\qquad}\,\, [ \underline{\qquad\qquad\qquad} \implies \underline{\qquad\qquad\qquad}] \bigg) \end{equation*}

with the blanks filled in appropriately.
Use part (a) to rewrite the statement, with “\(\lnot\)” moved as far to the right as possible. (Your answer should still use formal logic notation.)
Express the statement in (b) in as simple an English sentence as possible; i.e., it should not sound like it was produced by a logical negation machine. In this answer, you should have no formal logic notation.

Statement (1). Being nonzero is not a sufficient condition for an \(n \times n\) matrix to be nonsingular.

Statement (2). A consistent linear system \(\ell\) doesn’t necessarily have a unique solution. (Use \(\mathcal{L}\) to denote the set of all linear systems.)

Checkpoint 4.0.2.

Are the following pairs of statements logically equivalent? If yes, simply state “Yes.” If no, give an example in which one statement is true and the other is false, where the domain of discourse \(A\) is the set of all Hamilton students. (You will have to decide what properties of students \(p(x)\) and \(q(x)\) represent. Be imaginative!)

\(\forall x \in A, [p(x) \land q(x)]; \quad (\forall x \in A, p(x)) \land (\forall x \in A, q(x))\)
\(\exists x \in A, [p(x) \land q(x)]; \quad (\exists x \in A, p(x)) \land (\exists x \in A, q(x))\)
\(\exists x \in A, [p(x) \lor q(x)]; \quad (\exists x \in A, p(x)) \lor (\exists x \in A, q(x))\)

Checkpoint 4.0.3.

The logical connective “exclusive-or” is defined by

\begin{equation*} p \oplus q \equiv \left[ p \lor q \right ] \land \left[ \lnot (p \land q) \right]. \end{equation*}

Prove that \(p \oplus q \equiv \lnot ( p \Leftrightarrow q)\text{,}\) by showing that both are logically equivalent to \([ p \land (\lnot q)] \lor [q \land (\lnot p) ]\text{.}\) Do not use truth tables! Cite any equivalence laws you use by name!