CS 210 Discrete Structures I
Spring 2017
Chapter 1.5 Exercise

Section 1: Predicates

Implications are "if-then" statements, which utilize propositional variables (like p and q). An implication is generally written as: p → q, which can be read aloud as "if p is true, then q is true", or "p implies q", or "if p, then q".

In an implication p → q, p is called the hypothesis and q is called the conclusion.

The hypothesis and conclusion can each be more sophisticated propositional statements than just p and q, such as:
(p ∧ q) → r (just as an example.)

Example problem:

p represents the statement, "x's age is less than 13"
q represents the statement, "x receives a discounted ticket price".
Therefore, the statement p → q represents "If x's age is less than 13, then x will receive a discounted ticket price."

Exercise 1

15%

a. For the following statements given, assign a variable to each. The variable name can be any single-letter variable, so long as each statement has its own unique variable.

Collect 100 coins
Gain an extra life
Run into an enemy
Lose a life

Using the variables above, write out the following statements using these variables.

b. Collected 100 coins and ran into an enemy.
c. Gained an extra life, or lost a life.


d. If you collect 100 coins, then you gain an extra life.
e. If you collect 100 coins or if you run into an enemy, then you gain an extra life.
f. If you don't run into an enemy, then you gain an extra life.
g. If you don't collect 100 coins or if you run into an enemy, then you lose a life.

Truth values for implications

For a statement of the form, if HYPOTHESIS, then CONCLUSION to be false, it must be the case that the hypothesis is true, while the conclusion is false.
Otherwise, the statement is true.

The truth-table is as follows:

p q p → q
T T T
T F F
F T T
F F T

This might seem a little unintuitive.

The only way the result is false is when the hypothesis is true and the conclusion is false.

Think of this as: If the hypothesis is false, then our question is pointless anyway; if the hypothesis is false, then it doesn't affect the outcome of this implication because we can only derive the conclusion for a true hypothesis.


Exercise 2

30%

Complete the truth tables for the given compound expressions.

a. (p ∧ q) → p
b. (p ∨ q) → p
c. p ∧ (q → r)

Exercise 3

24%

Given the predicates:

p: x is even
q: y is even

Rewrite the following statements using these predicates, and the symbols ∨ ∧ ¬ → (as appropriate).

a. if x is even, then y is even.
b. is x is even, then y is odd.
c. if x is odd, then y is even.
d. if x is odd, then y is odd.

Section 2: Negations of Implications

The negation of the implication p → q is the statement p ∧ (¬q).
Notice that the negation is not also an implication.

We can see that they are logically equivalent via a truth-table:

p q p → q ¬(p → q) p ∧ (¬q)
T T T F F
T F F T T
F T T F F
F F T F F

This is one of the tricky things about implications, so make sure to pay attention!

Example problem:

"If Bob has an 8:00 class today, then it is a Tuesday."

p: Bob has an 8:00 class today
q: it is a Tuesday

The negation is: ¬(p → q) ≡ p ∧ (¬q), which would be read as "Bob has an 8:00 class today, AND it is not Tuesday."


Exercise 4

15%

Write the negation of each of the following statements.
Do this in English terms (remember that the negation of "if p then q" is "p and not q")

a. If nobody likes me, then I will eat worms.
b. If x > 2, then x · x > 4
c. If I read book 1 and I read book 2, then I will read book 3.

Section 3:Converse, Inverse, and Contrapositive

For some implication p → q...

  1. The converse is q → p.
  2. The inverse is ¬p → ¬q
  3. The contrapositive is ¬q → ¬p

Another way of stating this is, suppose we have quantified statements,
P(n) is "n ends in a digit 2" and Q(n) is "n is divisible by 2", then...:

  • The implication P(n) → Q(n) means "If n ends in a digit 2, then n is divisible by 2."
  • The converse Q(n) → P(n) means "If n is divisible by 2, then n ends in a digit 2."
  • The inverse ¬P(n) → ¬Q(n) means "If n does not end in a digit 2, then n is not divisible by 2."
  • The contrapositive ¬Q(n) → ¬P(n) means "If n is not divisible by 2, then n does not end in a 2."

Exercise 5

12%

With the statements given, write either the converse, inverse, or contrapositive.
You can use quantifiers like Q(x) and P(x), or just p and q (or whatever variables seem appropriate, just define them.)

a. Write the contrapositive: If x goes home, then x will watch Netflix all night.
b. Write the inverse: If x likes peanut butter cups, then x likes chocolate and x likes peanut butter.
c. Write the converse: If x is allergic to cats then x doesn't own a cat.