Solutions to Problem Set 4

Math 310-01/02

9-13-2017

1. In each case, negate the given statement, simplify so that only simple statements are negated, and write the answer in words.

Let $G(x)$ means "x likes garlic" and let $O(x)$ means "x likes onions".

(a) "Everyone who likes garlic also likes onions."

(b) "Someone likes garlic and onions."

(c) "There's someone who likes garlic but doesn't like onions."

(a) The given statement is $\forall x (G(x) \ifthen O(x))$ . Negate and simplify:

$$\matrix{\lnot \forall x (G(x) \ifthen O(x)) & \iff & \exists x \lnot (G(x) \ifthen O(x)) & \hbox{(Negating a quantifier)} \cr & \iff & \exists x \lnot(\lnot G(x) \lor O(x)) & \hbox{(Conditonal disjunction)} \cr & \iff & \exists x (G(x) \land \lnot O(x)) & \hbox{(DeMorgan)} \cr}$$

The last expression says "Someone likes garlic and doesn't like onions".

(b) The given statement is $\exists x (G(x) \land O(x))$ . Negate and simplify:

$$\matrix{\lnot \exists x (G(x) \land O(x)) & \iff & \forall x \lnot (G(x) \land O(x)) & \hbox{(Negating a quantifier)} \cr & \iff & \forall x (\lnot G(x) \lor \lnot O(x)) & \hbox{(DeMorgan)} \cr}$$

The last expression says "Everyone either does not like garlic or does not like onions".

(c) The given statement is $\exists x (G(x) \land \lnot O(x))$ . Negate and simplify:

$$\matrix{\lnot \exists x (G(x) \land \lnot O(x)) & \iff & \forall x \lnot (G(x) \land \lnot O(x)) & \hbox{(Negating a quantifier)} \cr & \iff & \forall x (\lnot G(x) \lor O(x)) & \hbox{(DeMorgan)} \cr}$$

The last statement says "Everyone either does not like garlic or likes onions".


2. In each part, determine the truth value of the statement.

If a universal ("$\forall$ ") statement is false, give a specific counterexample.

If an existential ("$\exists$ ") statement is true, give a specific example (of the thing whose existence is asserted).

(a) $\forall x \in \real (x^2 >
   0)$ .

(b) $\forall n \in \natural (n +
   2 > n + 1)$ .

(c) $\exists x \in \real (\sin
   x)^2 + (\cos x)^2 = 2$ .

(d) $\exists x \in \rational (20
   - 5 x^2 = 0)$ .

(a) The statement is false; $0^2
   \not> 0$ .

(b) The statement says that for every natural number n, it's true that $n + 2 \ge n + 1$ . Since $2 > 1$ , it follows that if n is a natural number, then $n +
   2 > n + 1$ . Hence, the statement is true.

(c) The statement is false, because for all $x \in \real$ , it's true that $(\sin x)^2 + (\cos x)^2 = 1$ .

(d) The statement says that there is a rational number x such that $20 - 5 x^2 = 0$ . Since 2 is rational and $20 - 5 \cdot 2^2 = 0$ , the statement is true.


3. Premises: $\displaystyle
   \left\{\matrix{A \iff B \cr B \land \lnot C \cr \lnot A \lor D
   \cr}\right.$ .

Prove: D.

$$\matrix{ \hfill 1. & A \iff B \hfill & \hbox{Premise} \hfill \cr \hfill 2. & B \land \lnot C \hfill & \hbox{Premise} \hfill \cr \hfill 3. & \lnot A \lor D \hfill & \hbox{Premise} \hfill \cr \hfill 4. & B \hfill & \hbox{Decomposing a conjunction (2)} \hfill \cr \hfill 5. & B \ifthen A \hfill & \hbox{Definition of biconditional} \hfill \cr \hfill 6. & A \hfill & \hbox{Modus ponens (4,5)} \hfill \cr \hfill 7. & D \hfill & \hbox{Disjunctive syllogism (3,6)} \quad\halmos \hfill \cr}$$


Perhaps the most valuable result of all education is the ability to make yourself do the thing you have to do, when it ought to be done, whether you like it or not. - Thomas Huxley


Contact information

Bruce Ikenaga's Home Page

Copyright 2017 by Bruce Ikenaga