Skip to main content

Discrete Mathematical Structures

Dan Yasaki, Sebastian Pauli

Exercises 1.2.3 Exercises

1.

Give the definition for these terms. Be sure to set up any notation that is required.
  1. tautology
    🔗
    🔗
  2. contradiction
    🔗
    🔗
  3. contingency
    🔗
    🔗
  4. logically equivalent propositions
    🔗
    🔗
🔗
🔗

2.

State precisely De Morgan’s laws for propositions. Be sure to set up any notation that is required.
🔗
🔗

3.

Use De Morgan’s laws to find the negation of these statements.
  1. Alice will go to graduate school or get a job in industry.
    🔗
    🔗
  2. Bob majored in math and computer science.
    🔗
    🔗
  3. Carl is tall and thin.
    🔗
    🔗
  4. Dan has a laptop and a desktop.
    🔗
    🔗
  5. Eve or Frank will pick you up at the airport.
    🔗
    🔗
🔗
🔗

4.

Show that each of these conditional statements is a tautology by using truth tables.
  1. \(\displaystyle p \implies (p\lor q)\)
    🔗
    🔗
  2. \(\displaystyle (p\land q ) \implies p\)
    🔗
    🔗
  3. \(\displaystyle (p\land q) \implies (p \implies q)\)
    🔗
    🔗
  4. \(\displaystyle (\lnot p\land (p\lor q) ) \implies q\)
    🔗
    🔗
  5. \(\displaystyle \lnot p \implies (p \implies q)\)
    🔗
    🔗
🔗
🔗

5.

Complete the following truth table. Is \(p\implies q\) is logically equivalent to \(\lnot p\lor q\text{?}\) Justify. Be sure to say what portion of the computation explains your response.
\begin{equation*} \begin{array}{|c|c|c|c|c|} \hline p\amp q\amp \lnot p\amp \lnot p\lor q\amp p \implies q\\ \hline \true\amp \true\amp \amp \amp \\\hline \true\amp \false\amp \amp \amp \\\hline \false\amp \true\amp \amp \amp \\\hline \false\amp \false\amp \amp \amp \\\hline \end{array} \end{equation*}
🔗
🔗

6.

Verify these associative law using a truth table. Which columns show the logical equivalence?
  1. \(\displaystyle (p\lor q)\lor r \equiv p\lor (q\lor r)\)
    🔗
    🔗
  2. \(\displaystyle (p\land q)\land r \equiv p\land (q\land r)\)
    🔗
    🔗
🔗
🔗

7.

Verify these absorptions law using a truth table. Which columns show the logical equivalence?
  1. \(\displaystyle p\lor (p\land q) \equiv p\)
    🔗
    🔗
  2. \(\displaystyle p\land (p\lor q) \equiv p\)
    🔗
    🔗
🔗
🔗

8.

Show that \(\lnot (p\lxor q)\) and \(p \iff q\) are logically equivalent.
🔗
🔗

9.

Show that \((p \implies q)\lor (p \implies r)\) and \(p \implies (q\lor r)\) are logically equivalent.
🔗
🔗

10.

Show that \((p\land q) \implies r\) and \((p \implies r)\land (q \land r)\) are not logically equivalent.
🔗
🔗

11.

Show that \(p \iff q\) and \(\lnot p \iff\lnot q\) are logically equivalent.
🔗
🔗
🔗
PrevTopNext