1

Mathematical Logic

Module 1

Propositional
Logic

Introduction
Mathematical logic is the discipline that
mathematicians invented in the late
nineteenth and early twentieth centuries so
they could stop talking nonsense. It’s the
most powerful tool we have for reasoning
about things that we can’t really comprehend,
which makes it a perfect tool even for other
disciplines in science and technology.
 2

As you journey through this lesson, you are

expected to:

Learning
Write proofs for Outcome
mathematical statements
and arguments

Learning
Objectives
1. Define proposition and determine whether or
not a given expression is a proposition
2. Construct the truth table of a given proposition
and determine if it is a tautology, a contradiction,
or a contingency
3. Prove equivalences using the rules of
replacement
4. Determine the validity of an argument

Content
 3

1 The Language of Logic

The basis of mathematical logic is propositional logic, which was
essentially invented by Aristotle.

Propositional logic
Propositional logic is the simplest form of logic. Here the only
statements that are considered are propositions, which contain no variables.
Since propositions contain no variables, they are either always true or always
false.
Examples of propositions:
• 2 + 2 = 4. (Always true).
• 2 + 2 = 5. (Always false).
Examples of non-propositions:
• x + 2 = 4. (May be true, may not be true; it depends on the value of
x.)
• x · 0 = 0. (Always true, but it’s still not a proposition because of the
variable.)
• x · 0 = 1. (Always false, but not a proposition because of the
variable.)

As the last two examples show, it is not enough for a statement

to be always true or always false—whether a statement is a proposition
or not is a structural property. But if a statement doesn’t contain any
variables (or other undefined terms), it is a proposition, and as a side-
effect of being a proposition it’s always true or always false.

Example 1.1 Which of the following are propositions? Give the truth
value of the propositions.
a. The difference of two primes.
b. 2 + 2 = 4.
c. Washington D.C. is the capital of New York.
d. How are you?
 4

Solution.
a. Not a proposition.
b. A proposition with truth value (T).
c. A proposition with truth value (F).
d. Not a proposition

Operations on Propositions
Propositions by themselves are pretty boring. So boring, in fact,
that logicians quickly stop talking about actual statements and instead
haul out placeholder names for propositions like p, q, or r.

For example, we can use the notation p : 1 + 1 = 3 to define p

to be the proposition 1+1 = 3. But we can build slightly more
interesting propositions by combining propositions together using
various logical connectives, like:

1. Negation
The negation of p is written as ¬p, or sometimes p. It has the
property that it is false when p is true, and true when p is false.
2. Disjunction (Or )
The disjunction of two propositions p and q is written as p ∨ q,
and is true as long as at least one, or possibly both, of p and q is true.
This is not always the same as what “or” means in English; in English,
“or” often is used for exclusive or which is not true if both p and q are
true. For example, if someone says “You will give me all your money or
I will stab you with this table knife”, you would be justifiably upset if
you turn over all your money and still get stabbed. But a logician would
not be at all surprised, because the standard “or” in propositional logic
is an inclusive or that allows for both outcomes

3. Conjunction (And)
 5

The conjunction of p and q is written as p ∧ q, and is true only

when both p and q are true.2 This is pretty much the same as in
English, where “I like to eat ice cream and I own a private Caribbean
island” is not a true statement when made by most people even
though most people like to eat ice cream. The only complication in
translating English expressions into logical ands is that logicians can’t

but 3 + 3 = 6” becomes simply “(2 + 2 = 4) ∧ (3 + 3 = 6).”

tell the difference between “and” and “but”: the statement “2 + 2 = 4

4. Implication
This is the most important connective for proofs. An implication

p ⇒ q, depending on our typographic convention and the availability of

represents an “if. . . then” claim. If p implies q, then we write p → q or

arrow symbols in our favorite font. In English, p → q is usually rendered

as “If p, then q,” as in “If you step on your own head, it will hurt.” The
meaning of p → q is that q is true whenever p is true, and the
proposition p → q is true provided (a) p is false (in which case all bets
are off), or (b) q is true. In fact, the only way for p → q to be false is for

as ¬p ∨ q. So, for example, the statements “If 2 + 2 = 5, then I’m the

p to be true but q to be false; because of this, p → q can be rewritten

Pope”, “If I’m the Pope, then 2 + 2 = 4”, and “If 2 + 2 = 4, then 3 + 3
= 6”, are all true, provided the if/then is interpreted as implication.
Normal English usage does not always match this pattern; instead,
if/then in normal speech is often interpreted as the much stronger
biconditional (see below).

5. Biconditional
Suppose that p → q and q → p, so that either both p and q are
true or both p and q are false. In this case, we write p ↔ q and say
that p holds if and only if q holds. The truth of p ↔ q is still just a
function of the truth or falsehood of p and q; though there doesn’t
seem any connection between the two sides of the statement, “2 + 2
= 5 if and only if I am the Pope” is still true (provided it is not uttered
by the Pope). The only way for p ↔ q to be false is for one side to be
true and one side to be false.

Compound Proposition
 6

The result of applying any of these operations is called a

compound proposition. Here’s what all of this looks like when typeset
nicely. Note that in some cases there is more than one way to write a
compound expression. Which you choose is a matter of personal
preference, but you should try to be consistent.

NOT p ¬p
p OR q p∨q
p AND q p∧q
p implies q p→q
p iff q p↔q

We can think of each row of a truth table as a model for propositional

logic, since the only things we can describe in propositional logic are
whether particular propositions are true or not. Constructing a truth
table corresponds to generating all possible models. This can be useful
if we want to figure out when a particular proposition is true.

Example 1.2
Let p:5<9
q : 9 < 7.
Construct the propositions p ∧ q and p ∨ q.

Solution.
The conjunction of the propositions p and q is the proposition
p∧q: 5 < 9 and 9 < 7.
The disjunction of the propositions p and q is the proposition
p∨q: 5 < 9 or 9 < 7

Example 1.3 Consider the following propositions

 7

p : It is Friday
q : It is raining.

Construct the propositions p ∧ q and p ∨ q.

Solution.
The conjunction of the propositions p and q is the proposition
p ∧ q : It is Friday and it is raining.
The disjunction of the propositions p and q is the proposition
p ∨ q : It is Friday or It is raining.

Truth Tables
To define logical operations formally, we construct a truth table.
A truth table displays the relationships between the truth values of
propositions. This gives, for any combination of truth values (true or
false, or often written as 1 for true and 0 for false) of the inputs, the
truth value of the output. So, truth tables are to logic what addition
tables or multiplication tables are to arithmetic. Here is a truth table
for negation:

¬ p ¬
p
1 0
0 1

And here is a truth table for the rest of the logical operators:

p q p˅q p˄q p→ p↔
 8

q q
1 1 1 1 1 1
1 0 1 0 1 0
0 1 1 0 0 0
0 0 0 0 1 1

We can think of each row of a truth table as a model for

propositional logic, since the only things we can describe in
propositional logic are whether particular propositions are true or not.
Constructing a truth table corresponds to generating all possible
models. This can be useful if we want to figure out when a particular
proposition is true.

2 Tautologies and Logical Equivalence

A compound proposition that is true no matter what the truth-
values of the propositions it contains is called a tautology.
For example, p ⇒ p, p ∨ ¬p, and ¬(p ∧ ¬p) are all tautologies,
as can be verified by constructing truth tables. If a compound
proposition is always false, it’s a contradiction. The negation of a
tautology is a contradiction and vice versa. The most useful class of
tautologies are logical equivalences. This is a tautology of the form X
↔ Y , where X and Y are compound propositions. In this case, X and Y
are said to be logically equivalent and we can substitute one for the
other in more complex propositions. We write X ≡ Y if X and Y are
logically equivalent. To prove a logical equivalence, one either
constructs a truth table to show that X ↔ Y is a tautology, or
transforms X to Y using previously-known logical equivalences.
And if the proposition is neither a tautology nor a contradiction—that
is, if there is at least one row where it’s true and at least one row
where it’s false—then the proposition is a contingency.

Some examples:

• p ∧ ¬p ≡ 0: Construct a truth table

p ¬p p˄¬ 0
 9

p
1 0 0 0
0 1 0 0

and observe that the last two columns are always equal.

• p ∨ p ≡ p: Use the truth table

p p˅p
1 1
0 0

• p → q ≡ ¬p ∨ q

Again, construct a truth table

p q p→q ¬p ∨
q
1 1 1 1
1 0 0 0
0 1 1 1
0 0 1 1

same

p → q ≡ ¬p ∨ q is known as material implication.

Note: Here, symbols of grouping such as the parentheses, brackets,

braces and vinculums are used in the same way as they are used in
evaluating arithmetic expressions, that is, to prioritize an operation.
 10

Example 2.1 Construct the truth table of [¬(p ∧ q)] ∨ r.

Solution.
p q r p˄q ¬(p˄q) [¬(p˄q)]˅
r
1 1 1 1 0 1
1 1 0 1 0 0
1 0 1 0 1 1
1 0 0 0 1 1
0 1 1 0 1 1
0 1 0 0 1 1
0 0 1 0 1 1
0 0 0 0 1 1

Example 2.2 Find the negation of the proposition

p: −5 < x ≤ 0.
Solution.
The negation of p is the proposition
¬p: x > 0 or x ≤ −5

Example 2.3
a. Construct the truth table of the proposition (p ∧ q) ∨ (¬ p ∨ ¬ q).
Determine if this proposition is a tautology.
b. Show that p ∨ ∼ p is a tautology.

Solution.
a.

¬ ¬ p ˄ q ¬p ˅ ¬q (p ∧ q) ∨ (¬ p ∨
¬ q)
p q
p q
1 1 0 0 1 0 1
1 0 0 1 0 1 1
0 1 1 0 0 1 1
0 0 1 1 0 1 1
 11

Thus, the given proposition is a tautology.

b. By constructing the truth table of p ∨ ¬p, we can determine whether

or not it is a tautology. Thus,

Solution.

¬p
¬p
p p˅

1 0 1
0 1 1

Again, this proposition is a tautology.

Example 2.4 Show that the proposition p∧ ¬ p is a contradiction.

p ¬ p∧ ¬
p p
1 0 0
0 1 0

Since the last column is all false then p∧ ¬ p is a contradiction.

Example 2.5 Construct the truth table for (p˄q) →¬ p and classify it
as a tautology, contradiction, or a contingency.

Solution:

p q ¬ p˄q (p˄q)→¬
p p
1 1 0 1 0
1 0 0 0 1
0 1 1 0 1
0 0 1 0 1
 12

The truth table for (p˄q) →¬ p is a contingency as it contains one false

value.

Logical Equivalence

Two propositions are equivalent if they have exactly the same

truth values under all circumstances. We write p ≡ q.

Example 2.6

a. Show that ¬ (p ∨ q) ≡¬ p∧ ¬ q.
b. Show that ¬ (p ∧ q) ≡¬ p ∨ ¬ q.
c. Show that ¬ (¬ p) ≡ p.

a. and b. above are known as De Morgan’s laws while c. is

known as the Double Negation law.

Solution.

a. Constructing the truth table for a, we have

¬ ¬ p ˅ q ¬(p ˅ ¬p
¬q
p q ˄
p q q)
1 1 0 0 1 0 0
1 0 0 1 1 0 0
0 1 1 0 1 0 0
0 0 1 1 0 1 1

Therefore, ¬ (p ∨ q) ≡¬ p∧ ¬ q.
 13

b. Constructing the truth table for b, we have

¬ ¬ ˄ ¬(p ˄ ¬p
¬q
p q p ˅
p q q q)
1 1 0 0 1 0 0
1 0 0 1 0 1 1
0 1 1 0 0 1 1
0 0 1 1 0 1 1

Therefore, ¬ (p ∧ q) ≡¬ p ∨ ¬ q.

c.

p ¬p ¬(¬p
)
1 0 1
0 1 0

Therefore,

Therefore, ¬ (¬ p) ≡ p.

Example 2.7

a. Show that p ∧ q ≡ q ∧ p and p ∨ q ≡ q ∨ p.

b. Show that (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) and (p ∧ q) ∧ r ≡ p ∧ (q ∧ r).
c. Show that (p ∧ q) ∨ r ≡ (p ∨ r) ∧ (q ∨ r) and (p ∨ q) ∧ r ≡ (p ∧ r) ∨
(q ∧ r).

Solution.
 14

a. Using truth table, show p ∧ q ≡ q ∧ p and p ∨ q ≡ q ∨ p.

p q p∧ q∧
q p
1 1 1 1
1 0 0 0
0 1 0 0
0 0 0 0

Thus, p ∧ q ≡ q ∧ p. (Commutative Law)

p q p˅q q˅p
1 1 1 1
1 0 1 1
0 1 1 1
0 0 0 0

Thus, p ˅ q ≡ q ˅ p. (Proof that ˅ and ˄ are commutative)

b. Show (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) by using truth table.

p q r p ∨ (p ∨ q) ∨ q∨ p ∨ (q ∨
q r r r)
1 1 1 1 1 1 1
1 1 0 1 1 1 1
1 0 1 1 1 1 1
1 0 0 1 1 0 1
0 1 1 1 1 1 1
0 1 0 1 1 1 1
0 0 1 0 1 1 1
0 0 0 0 0 0 0

Show (p ∧ q) ∧ r ≡ p ∧ (q ∧ r).
 15

p q r p ˄q (p ˄ q) ˄ q˄r p ˄ (q ˄
r r)
1 1 1 1 1 1 1
1 1 0 1 0 0 0
1 0 1 0 0 0 0
1 0 0 0 0 0 0
0 1 1 0 0 1 0
0 1 0 0 0 0 0
0 0 1 0 0 0 0
0 0 0 0 0 0 0

(Proof that ˄ and ˅ are associative)

c. Show that (p ∧ q) ∨ r ≡ (p ∨ r) ∧ (q ∨ r) and (p ∨ q) ∧ r ≡ (p ∧

r) ∨ (q ∧ r).

First, we prove that (p ∧ q) ∨ r ≡ (p ∨ r) ∧ (q ∨ r).

p ˄ q (p ∧ q) ∨ p ˅ (p ∨ r) ∧ (q
∨ r)
p q r q˅
r r r
1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1
1 0 1 0 1 1 1 1
1 0 0 0 0 1 0 0
0 1 1 0 1 1 1 1
0 1 0 0 0 0 1 0
0 0 1 0 1 1 1 1
0 0 0 0 0 0 0 0

Second, we prove that (p ∨ q) ∧ r ≡ (p ∧ r) ∨ (q ∧ r).

 16

p q r p ˅ q (p ˅ q) ˄ p˄ q˄ (p ˄ r) ˅ (q ˄
r r r r)
1 1 1 1 1 1 1 1
1 1 0 1 0 0 0 0
1 0 1 1 1 1 0 1
1 0 0 1 0 0 0 0
0 1 1 1 1 0 1 1
0 1 0 1 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0

(Proof that the Law of Distribution holds for ˅ and ˄)

Conditional and Biconditional Propositions

Let p and q be propositions. The implication p → q is the
proposition that is false only when p is true and q is false; otherwise, it
is true. p is called the hypothesis and q is called the conclusion. The
connective → is called the conditional connective.

Let us recall that the truth table for implication, that is,

p q p→q
1 1 1
1 0 0
0 1 1
0 0 1

It follows from the truth table that the proposition p → q is always true
if the hypothesis p is false, regardless of the truth value of q. We say
that p → q is true by default or vacuously true. In terms of words
the proposition p → q also reads:
(a) if p then q.
(b) p implies q.
 17

(c) p is a sufficient condition for q.

(d) q is a necessary condition for p.
(e) p only if q.

Example 2.8 Use the if-then form to rewrite the statement “I am on

time for work if I catch the 8:05 bus.”
Solution.
If I catch the 8:05 bus then I am on time for work

In propositional functions that involve the connectives ¬, ∧, ∨, and →

the order of operations is that ¬ is performed first and → is performed
last.

Example 2.9
a. Show that ¬ (p → q) ≡ p∧ ¬ q.
b. Find the negation of the statement “ If my car is in the repair shop,
then I cannot go to class.”
Solution.
We can also use the rules of replacement in showing equivalence
between two propositions. The procedure is outlined as follows:
a. ¬ (p → q) ≡ ¬ (¬ p ∨ q) (by Material Implication)
≡ ¬ (¬ p) ∧ ¬ q (by De Morgan’s Law)
≡ p∧ ¬ q. (by Double Negation)
b. “My car is in the repair shop and I can get to class.”

inverse of p → q is the proposition ¬ p →¬ q. The contrapositive of p

The converse of p → q is the proposition q → p. The opposite or

→ q is the proposition ¬ q →¬ p.
 18

Example 2.10 Find the converse, opposite, and the contrapositive of

the implication: “ If today is Thursday, then I have a test today.”
Solution.
The converse: If I have a test today then today is Thursday.
The inverse: If today is not Thursday then I don’t have a test today.
The contrapositive: If I don’t have a test today then today is not
Thursday.

Example 2.11 Show that p → q ≡ ¬ q →¬ p.

Solution.
Using the rules of replacement, we have
p → q ≡ ¬ p ∨ q (by Material Implication)
≡ ¬ (p∧ ¬ q) (by De Morgan’s
Law)
≡ ¬ (¬ q ∧ p) (by Commutative
Law)
≡ ¬¬ q ∨ ¬ p (by De Morgan’s
Law)
≡ q ∨ ¬ p (by Double Negation)
≡ ¬ q →¬ p (by Material
Implication)

Example 2.12 Show that ¬ q →¬ p ≡ p → q

Solution.
We use De Morgan’s laws as follows.
¬ q →¬ p ≡ q∨ ¬ p
≡ ¬ (¬ q ∧ p)
≡ ¬ (p∧ ¬ q)
≡ ¬ p∨ ¬¬ q
≡¬p∨q
 19

≡p→q

The biconditional proposition of p and q, denoted by p ↔ q, is

the propositional function that is true when both p and q have the
same truth values and false if p and q have opposite truth values. Also
reads, “p if and only if q” or “p is a necessary and sufficient condition
for q.” Again, let us recall the truth table for the if and only if
statement. That is,

p q p↔
q
1 1 1
1 0 0
0 1 0
0 0 1

Example 2.13
Show that the biconditional proposition of p and q is logically
equivalent to the conjunction of the conditional propositions p → q and
q → p.

Solution.

p q p→q q→p p↔q (p → q)˄ (q →

p)
1 1 1 1 1 1
1 0 0 1 0 0
0 1 1 0 0 0
0 0 1 1 1 1

3 Rules of Inferential Logic

 20

The main concern of logic is how the truth of some propositions

is connected with the truth of another. Thus, we will usually consider a
group of related propositions. An argument is a set of two or more
propositions related to each other in such a way that all but one of
them (the premises) are supposed to provide support for the
remaining one (the conclusion). The transition from premises to
conclusion is the inference upon which the argument relies.

Example 3.1 Show that the propositions “The star is made of milk,
and strawberries are red. My dog has fleas.” do not form an argument.

Solution.
Indeed, the truth or falsity of each of the propositions has no bearing
on that of the others.

Example 3.2 Show that the propositions: “Mark is a lawyer. So, Mark
went to law school since all lawyers have gone to law school” form an
argument.

Solution.
This is an argument. The truth of the conclusion, “Mark went to law
school,” is inferred or deduced from its premises, “Mark is a lawyer”
and “all lawyers have gone to law school.”
The above argument can be represented as follows:
Let p: Mark is a lawyer.
q: All lawyers have gone to law school.
r: Mark went to law school.
Then p∧q
∴r

The symbol ' ∴ ' is to indicate the inferred conclusion.

 21

Now, suppose that the premises of an argument are all true.

Then the conclusion may be either true or false. When the conclusion
is true then the argument is said to be valid. When the conclusion is
false then the argument is said to be invalid. To test an argument for
validity we use the following rules of inference and proceed just as
writing proofs using the rules of replacement.

Rules of Inference
The following rules can be used to prove the validity of an
argument.
1. Modus Ponens or the Method of Affirming
p→q
p
∴q

Example 3.3 Show that the following argument is valid:

¬r∨s→t
¬r∨s
∴t
Solution.
It follows from Modus Ponens, that is, by replacing p with ¬ r ∨ s
and q with t. Hence the argument is valid.

2. Modus Tollens or the Method of Denial

p→q
¬q
∴ ¬p

3. Disjunctive Addition
a) p
 22

∴ p∨q
or b) q
∴ p∨q

4. Conjunctive Addition
a) p
q
∴ p˄q
or b) p
q
∴ q˄p
5. Conjunctive Simplification
a) p ∧ q
∴p

or b) p ∧ q
∴q
6. Disjunctive Syllogism
p∨q
¬q
∴p

7. Hypothetical Syllogism
p→q
q→r
∴p→r
 23

Example 3.4 Use modus ponens or modus tollens in the argument

below so as to produce a valid inference.
If √ 2 is rational, then √ 2 = a b for some integers a and b.
It is not true that √ 2 = a b for some integers a and b.
Solution.
First, we write the given argument in symbolic form. So, we let
p : √ 2 is rational
q : √ 2 = a b for some integers a and b

Since the first statement is an if-then (or an implication) statement

then its symbolic form is

p→q
The second statement is a negation statement. In fact, it is a negation
of q. Thus, its symbolic form is
¬q

We now write the symbolic form of the whole argument as

p→q
¬q

Therefore, the conclusion is ¬ p. Now we can infer the following:

Notice that the argument is a method of denial or a modus tollens.

If √ 2 is rational, then √ 2 = a b for some integers a and b.

It is not true that √ 2 = a b for some integers a and b.
Therefore, √ 2 is not rational.

Example 3.5 Use modus ponens or modus tollens in the argument

below so as to produce a valid inference.
 24

Solution.

Changing to its symbolic form by letting

r: Logic is easy.
s: I am a monkey’s uncle.

So, the symbolic form of the argument is:

r→ s
r

Based on Modus Ponens or the Method of Affirming the conclusion is

∴s

We can then write an inference as

If logic is easy, then I am a monkey’s uncle.

Logic is easy.
Therefore, I am a monkey’s uncle.

Note: Translation to symbols is useful for beginners. Once you

become familiar with the rules of inference, you will find it easy to
produce a valid inference even without changing to symbolic form.

Example 3.6 Use the rules of inference to determine whether the

argument below is valid.

p→q
q→p
 25

∴p ∨ q
Solution.
Statement Reason
1) p → q 1) Premise
2) ¬p ˅ q 2) Material Implication (1)
3) ∴ q 3) Disjunctive Addition (2)
4) q → p 4) Premise
5) ∴ p 5) Modus Ponens (4)(3)
6) ∴ p ˅ q 6) Disjunctive Addition (5)

Hence, the given argument is valid.

Example 3.7 Use the rules of inference to determine whether the

argument below is valid.
p
p→q
¬q∨r
∴r
Solution.
Statement Reason
1) p → q 1) Premise
2) p 2) Premise
3) ∴ q 3) Modus Ponens (1)(2)
4) ¬ q ∨ r 4) Premise
5) q→ r 5) Material Implication (4)
6) ∴ r 6) Modus Ponens (5)(3)

Hence, the given argument is valid.

 26

Example 3.8 Use the rules of inference to determine whether the

argument below is valid.

p∨r
r→q
s∨∼q
∼s
∴p

Solution:
Statement Reason
1) s ∨ ∼ q 1) Premise
2) ∼ s 2) Premise
3) ∼ q 3) 1, 2, Disjunctive Syllogism
4) r → q 4) Premise
5) ∼ r 5) 3, 4, Law of Contraposition
6) p ∨ r 6) Premise
7. ∴ p 7) 5, 6, Disjunctive Syllogism

4 Propositions and Quantifiers

Statements such as “x > 3” are often found in mathematical

assertions and in computer programs. These statements are not
propositions when the variables are not specified. However, one can
produce propositions from such statements.
A predicate is an expression involving one or more variables
defined on some domain, called the domain of discourse. Substitution
 27

of a particular value for the variable(s) produces a proposition which is

either true or false. For instance,
P(n) : n is prime is a predicate on the natural numbers.
Observe that P(1) is false, P(2) is true. In the expression P(x), x is
called a free variable. As x varies the truth value of P(x) varies as well.
The set of true values of a predicate P(x) is called the truth set and will
be denoted by TP.

Example 4.1 Let Q(x, y) : x = y+3 with domain the collection of

natural numbers (i.e. the numbers 0, 1, 2, · · ·). What are the truth
values of the propositions Q(1, 2) and Q(3, 0)?
Solution.
By substitution in the expression of Q we find:
Q(1, 2) is false since 1 = x 6= y + 3 = 5.
On the contrary, Q(3, 0) is true since x = 3 = 0 + 3 = y + 3
If P(x) and Q(x) are two predicates with a common domain D
then the notation P(x) → Q(x) means that every element in the truth
set of P(x) is also an element in the truth set of Q(x).

Example 4.2 Consider the two predicates P(x) : x is a factor of 4 and

Q(x) : x is a factor of 8. Show that P(x) → Q(x).
Solution.
Finding the truth set of each predicate we have:
TP = {1, 2, 4} and TQ = {1, 2, 4, 8}.
Since every number appearing in TP also appears in TQ we have
P(x) → Q(x)

TP = TQ then we use the notation P(x) ⇔ Q(x).

If two predicates P(x) and Q(x) with a common domain D are such that

Another way to generate propositions is by means of

quantifiers. For example,
 28

∀x ∈ D, P(x) is a proposition which is true if P(x) is true

for all values of x in the domain D of P.

P(k) : 2k is even is true for all k ∈ Z We write, ∀k ∈ Z

For example, if k is an nonnegative integer, then the predicate
+ ¿¿ + ¿¿
(2k is
even).
The symbol ∀ is called the universal quantifier.

The proposition ∀x ∈ D, P(x) is false if P(x) is false for at least

one value of x. In this case x is called a counterexample.

Example 4.3 Show that the proposition ∀x ∈ R, x > 1 x is false.

Solution.
1
1 1
A counterexample is x = . Clearly, < 2 = 1 .
2 2
2

Example 4.4 Write in the form ∀x ∈ D, P(x) the proposition : “every

real number is either positive, negative or 0.”
Solution.
∀x ∈ IR, x > 0, x < 0, or x = 0.

The notation ∃x ∈ D, P(x) is a proposition that is true if there is

at least one value of x ∈ D where P(x) is true; otherwise, it is false. The
symbol ∃ is called the existential quantifier.

value of the proposition ∃x ∈ R, P(x).

Example 4.5 Let P(x) denote the statement “x > 3.” What is the truth

Solution.
Since 4 ∈ R and 4 > 3, the given proposition is true.
 29

The proposition ∀x ∈ D, P(x) → Q(x) is called the universal

conditional proposition. For example, the proposition ∀x ∈ R, if x >
2 then x2 > 4 is a universal conditional proposition.

Example 4.6 Rewrite the proposition “if a real number is an integer

then it is a rational number” as a universal conditional proposition.
Solution.
∀x ∈ IR, if x is an integer then x is a rational number.

Example 4.7
a. What is the negation of the proposition ∀x ∈ D, P(x)?
b. What is the negation of the proposition ∃x ∈ D, P(x)?
c. What is the negation of the proposition ∀x ∈ D, P(x) → Q(x)?
Solution.
a. ∃x ∈ D, ¬ P(x).
b. ∀x ∈ D, ¬ P(x).
c. Since P(x) → Q(x) ≡ (¬ P(x)) ∨ Q(x) (by material implication), we
have ¬ (∀x ∈ D, P(x) → Q(x)) ≡ ∃x ∈ D, P(x)∧ ¬ Q(x)

Example 4.8 Consider the universal conditional proposition ∀x ∈ D, if

P(x) then Q(x).
a. Find the contrapositive.
b. Find the converse.
c. Find the inverse.
Solution.
a. ∀x ∈ D, if ¬ Q(x) then ¬ P(x).
b. ∀x ∈ D, if Q(x) then P(x).
c. ∀x ∈ D, if ¬ P(x) then ¬ Q(x)
 30

Example 4.9 Write the negation of each of the following propositions:

a. ∀x ∈ IR, x > 3 → x2 > 9.
b. Every polynomial function is continuous.
c. There exists a triangle with the property that the sum of angles is
greater than 180◦.
Solution.
a. ∃x ∈ IR, x > 3 and x2 ≤ 9.
b. There exists a polynomial that is not continuous everywhere.
c. For any triangle, the sum of the angles is less than or equal to 180◦

Assessment Tasks 1

1.1 Construct the truth table for the proposition: (p → r) ↔ (q → r).

 31

1.2 Write negations for each of the following propositions. (Assume

that all variables represent fixed quantities or entities, as appropriate.)
a. If P is a square, then P is a rectangle.
b. If today is Thanksgiving, then tomorrow is Friday.
c. If r is rational, then the decimal expansion of r is repeating.
d. If n is prime, then n is odd or n is 2. e. If x ≥ 0, then x > 0 or x = 0.
1.3 Use the contrapositive to rewrite the proposition “being divisible
by 3 is a necessary condition for this number to be divisible by 9” in
if−then form in two ways.
1.4 Rewrite the proposition “A sufficient condition for Hal’s team to win
the championship is that it wins the rest of the games” in if−then form.
1.5 Rewrite the proposition “A necessary condition for this computer
program to be correct is that it not produce error messages during
translation” in if−then form.
1.6 By finding a counterexample, show that the proposition: “For all
positive integers n and m, m.n ≥ m + n” is false.
1.7 Find a 2-column proof for the following argument:

a. p→q
∼q
p∨s
∴s

b. (q ∨ r) → p
∼p
s→r
∴∼ s

References
 32

1. [Link]
[Link]
2.
[Link]
[Link]
3.
[Link]
09/[Link]
4. [Link]

Prepared by:

Sharon M. Galicha, LPT, MS MATH ED

Asst Professor 2