CmSc 180 Discrete mathematics
Homework 02: SOLUTIONS
1. Let P and Q be the propositions:
P: You drive over 65 miles per hour
Q: You get a speeding ticket
Write the following propositions using P and Q and logical connectives:
a. You do not drive over 65 miles per hour
~P
b. You drive over 65 miles per hour, but you do not get a speeding ticket
P L ~Q
c. You get a speeding ticket if you drive over 65 miles per hour
P ® Q
d. If you do not drive over 65 miles per hour then you will not get a speeding ticket
~P ® ~Q
e. You get a speeding ticket but you do not drive over 65 miles per hour
Q L ~P
2. Let P and Q be the propositions
P: I bought a lottery ticket this week
Q: I won the million dollar jackpot
A. Express each of the following propositions in English:
(time is not present in the logical expressions, so when translating you have to choose appropriate verb tense, e.g. ~P à Q might be translated as: "If I don't buy a lottery ticket, I will win the million dollar jackpot")
a. ~P
I have not bought a lottery ticket this week
b. P ® Q
If I buy a ticket, I will win the million dollar jackpot
c. ~P L ~Q
I did not buy a lottery ticket this week and I did not win the million dollar jackpot
d. P L Q
I bought a lottery ticket this week and I won the million dollar jackpot
e. ~P ® ~Q
If I don't buy a lottery ticket this week then I will not win the million dollar jackpot
B. Construct the truth table of each expression above
P / Q / ~P / ~Q / P ® Q / ~P L ~Q / P L Q / ~P ® ~QT / T / F / F / T / F / T / T
T / F / F / T / F / F / F / T
F / T / T / F / T / F / F / F
F / F / T / T / T / T / F / T
C. Write the negation of each expression in a) through E) above, and translate the negation in English
Hints: Use De Morgan's laws, represent implication as a disjunction in order to apply De Morgan's laws
Expression / Negation / Translation~P / P / I bought a lottery ticket this week
P ® Q / P L ~Q / I bought a ticket but I did not win
~P L ~Q / P v Q / I bought a ticket or I won the jackpot or both
P L Q / ~P v ~Q / I did not buy a ticket or I did not won
If I buy a ticket I will not win the jackpot
~P ® ~Q / ~P L Q / I did not buy a ticket but I won the jackpot
3. Consider the following statements:
a. If you miss the exam, then you fail the course
b. If you fail the course then you have missed the exam
c. If you don't miss the exam you don't fail the course
d. If you don't fail the course then you have not missed the exam
e. If you miss the exam then you don't fail the course
f. If you don't miss the exam then you fail the course
g. If you fail the course then you have not missed the exam
h. If you don't fail the course then you have missed the exam
A. Using P for "you miss the exam" and Q for "you fail the course", represent each statement as a logical expression
a. If you miss the exam, then you fail the course: P ® Q
b. If you fail the course then you have missed the exam Q ® P
c. If you don't miss the exam you don't fail the course ~P ® ~Q
d. If you don't fail the course then you have not missed the exam ~Q ® ~P
e. If you miss the exam then you don't fail the course P ® ~Q
f. If you don't miss the exam then you fail the course ~P ® Q
g. If you fail the course then you have not missed the exam Q ® ~P
h. If you don't fail the course then you have missed the exam ~Q ® P
B. For each statement in a) through f) indicate its contrapositive, its converse and its inverse. Write your findings in a table like this:
Statement / Contrapositive / Converse / Inversea. P ® Q / ~Q ® ~P (d) / Q ® P (b) / ~P ® ~Q (c)
b. Q ® P / ~P ® ~Q (c) / P ® Q (a) / ~Q ® ~P (d)
c. ~P ® ~Q / Q ® P (b) / ~Q ® ~P (d) / P ® Q (a)
d. ~Q ® ~P / P ® Q (a) / ~P ® ~Q (c) / Q ® P (b)
e. P ® ~Q / Q ® ~P (g) / ~Q ® P (h) / ~P ® Q (f)
f. ~P ® Q / ~Q ® P (h) / Q ® ~P (g) / P ® ~Q (e)
g. Q ® ~P / P ® ~Q (e) / ~P ® Q (f) / ~Q ® P (h)
h. ~Q ® P / ~P ® Q (f) / P ® ~Q (e) / Q ® ~P (g)
C. There are four pairs of equivalent statements. Which are they?
(a) and (d)
(b) and (c)
(e) and (g)
(f) and (h)
4. Consider the statement: Tax rates will be reduced if Anita wins the election
a. Identify atomic statements and represent the statement as a logical expression
P = Anita wins the election
Q = Tax rates will be reduces
P ® Q
b. Rephrase the sentence as “unless” sentence
Tax rates will not be reduces unless Anita wins the election
c. Rephrase the sentence as Winning the election by Anita is sufficient for tax rates to be reduced
d. Rewrite the logical expression as a disjunction and translate it in English
Either Anita will not win the elections or tax rates will be reduced
5. Consider the statement: A square has four equal sides
a. Rephrase the sentence as “if … then…” sentence, identify atomic statements and represent the statement as a logical expression
If a polygon is a square then it has four equal sides
P = a polygon is a square
Q = a polygon has four equal sides
P ® Q
b. Rephrase the sentence as “unless” sentence
A polygon is not a square unless it has for equal sides
A unless B is ~B ® A
P ® Q = ~Q ® ~P
Plugging Q in the position of B and ~P in the position of A we get ~P unless Q
c. Rephrase the sentence as “only if” sentence
A polygon is a square only if it has four equal sides
d. Rephrase the sentence as ……… is sufficient for …………
Being a square is sufficient to have four equal sides
e. Rephrase the sentence as ……… is necessary for …………
Having four equal sides is necessary to be a square
f. Write the contrapositive expression and translate it in English
~Q ® ~P
If a polygon does not have four equal sides then it is not a square
g. Rewrite the logical expression as a disjunction and translate it in English
~P V Q: Eithre a polygon is not a square or it has four equal sides
6. Using the equivalence laws show that (A V B) L (A V ~B) Û A
(A V B) L (A V ~B) = by distributive law
A V ( B L ~B) = A V F = A
4