Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

Exercises 2.5 Exercises

1.

Consider again the two collections of related conditional statements in Example 2.3.4.

(a)

For each of these collections, determine which two of the four related statements are true and which two are false. For the two false statements in each collection, demonstrate it by providing examples where the statements are false.

(b)

Give an example of a conditional statement involving mathematical objects for which all four of conditional, contrapositive, converse, and inverse are all true.

2.

Suppose \(U\) is a tautology and \(E\) is a contradiction.

(a)

Show that \(P \lgcand U \lgcequiv P\) for every statement \(P\text{.}\)

(b)

Show that \(P \lgcor E \lgcequiv P\) for every statement \(P\text{.}\)

3.

Consider the equivalence of statements \(p \lgccond (q_1 \lgcor q_2) \lgcequiv (p \lgcand \lgcnot q_1) \lgccond q_2\text{.}\)

(a)

Use a truth table to verify the equivalence.

(b)

Use propositional calculus to demonstrate the equivalence.

4.

Use truth tables to establish the double negation, idempotence, commutativity, associativity, distributivity, and DeMorgan’s Law equivalences presented in Proposition 2.2.1.

5.

This exercise asks you to demonstrate that the basic connective “if and only if” can be constructed out of the basic connectives “not”, “and”, and “or.”

(b)

Starting with Rule 10.b from Proposition 2.2.1, use propositional calculus to prove the equivalence
\begin{equation*} p \lgcbicond q \lgcequiv (\lgcnot p \lgcor q) \lgcand (p \lgcor \lgcnot q) \text{.} \end{equation*}

6.

Use Exercise 5 to demonstrate that exclusive or
\begin{equation*} (p \lgcor q) \lgcand \lgcnot (p \lgcand q) \end{equation*}
is equivalent to
\begin{equation*} p \lgcbicond \lgcnot q\text{.} \end{equation*}
<Prev^TopNext>