MAT 125: DISCRETE MATHEMATICS II LECTURE NOTES
SUMMARY OF LOGICAL EQUIVALENCES
Page 1 of 10
EXAMPLE 2
Use logical equivalences to show that
Solution
CONDITIONAL STATEMENTS
Definition:
Remark:
The Truth Table for the Conditional statement p → q.
The statement p → q is true when both p and q are true and when
p is false (no matter what truth value q has).
Page 2 of 10
Remark:
A conditional statement that is true by virtue of the fact that its
hypothesis is false is often called vacuously true or true by
default.
Example: The statement “If you show up for work Monday
morning, then you will get the job” is vacuously true if you do
not show up for work Monday morning.
In general, when the “if” part of an if-then statement is false, the
statement as a whole is said to be true, regardless of whether the
conclusion is true or
false.
Order of operations
In expressions that include → as well as other logical operators
such as ∧, ∨, and ∼, the order of operations is that → is performed
last. Thus, according to the specification of order of operations, ∼
is performed first, then ∧ and ∨, and finally→.
Other terminologies that express conditional statements
Page 3 of 10
The following are different terminologies that are commonly used
in place of " if p then q"
“p implies q”
“if p, q”
“p only if q
“p is sufficient for q”
“a sufficient condition for q is p”
“q if p”
“q whenever p”
“q when p”
“q is necessary for p”
“a necessary condition for p is q”
“q follows from p”
“q unless ¬p”
Representation of Conditional as Disjunction
The conditional “if p then q” is logically equivalent to “not p or
q”
That is: p →q ≡ ∼p ∨ q. (verify this with a truth table)
Example: Rewrite the following statements without using the
conditional:
(a) If it is cold, he wears a hat.
(b) If productivity increases, then wages rise.
Recall that “If p then q” is equivalent to
“Not p or q;” that is, p → q ≡ ¬p ∨ q.
Hence, we have
(a) It is not cold or he wears a hat.
(b) Productivity does not increase or wages rise.
Page 4 of 10
The Negation of a Conditional Statement
The negation of "If p then q" is logically equivalent to "p and
not q."
Example
The Contrapositive of a Conditional Statement
Definition: The contrapositive of a conditional statement of the
form “If p then q” is "If ∼q then ∼p".
Symbolically, The contrapositive of p →q is ∼q →∼p.
A conditional statement is logically equivalent to its
contrapositive.(Verify)
Page 5 of 10
The Converse and inverse of a Conditional Statement
Definition: Suppose a conditional statement of the form “If p then
q” is given:
The converse is “If q then p.”
The inverse is “If ∼p then ∼q.”
Symbolically,
The converse of p →q is q → p, and
The inverse of p →q is ∼p →∼q.
Remark:
i. A conditional statement and its converse are not
logically equivalent.(Verify)
ii) A conditional statement and its inverse are not
logically equivalent.(Verify)
iii) The converse and the inverse of a conditional
statement are logically equivalent to each
other.(Verify)
EXAMPLE
What are the contrapositive, the converse, and the inverse of the
conditional statement: “The home team wins whenever it is
raining?”
Solution:
Page 6 of 10
Because “q whenever p” is one of the ways to express the
conditional statement p → q, the original statement can be
rewritten as
“If it is raining, then the home team wins.”
Consequently, the contrapositive of this conditional statement is
“If the home team does not win, then it is not raining.”
The converse is
“If the home team wins, then it is raining.”
The inverse is
“If it is not raining, then the home team does not win.”
The biconditional statement
DEFINITION
Let p and q be propositions.
The biconditional statement denoted p ↔ q is the proposition “p
if and only if q.”
The biconditional statement p ↔ q is true when p and q have the
same truth
values, and is false otherwise.
Biconditional statements are also called bi-implications.
There are some other common ways to express p ↔ q: These
include:
“p is necessary and sufficient for q”
Page 7 of 10
“if p then q, and conversely”
“p iff q.”
Truth table for the biconditional statement
In order of operations ↔ is coequal with→. As with ∧ and ∨, the
only way to indicate precedence between them is to use
parentheses.
Example:
Page 8 of 10
Converting a Sufficient Condition to If-Then Form
Example:
Rewrite the following statement in the form “If A then B”:
Pia’s birth on Kenyan soil is a sufficient condition for her to be a
Kenyan citizen.
Solution: If Pia was born on Kenyan soil, then she is a Kenyan
citizen.
Page 9 of 10
Converting a Necessary Condition to If-Then Form
Example:
Use the contrapositive to rewrite the following statement in two
ways:
George’s attaining age 35 is a necessary condition for his being
president of the United States.
Solution
Version 1: If George has not attained the age of 35, then he cannot
be president of the United States.
Version 2: If George can be president of the United States, then he
has attained the age of 35.
Exercise:
Prove that the negation of the biconditional “𝑝 if and only if 𝑞”
(~(𝑝↔𝑞)) is equivalent to the exclusive disjunctive form “Either 𝑝
or 𝑞, but not both” (𝑝⊕𝑞).
Page 10 of 10
