Module-1

1.1 Basic Connectives and Truth Tables

What is Truth Table?
A truth table is a tabular representation of all the combinations of values for inputs and their
corresponding outputs
What is Connective?
A Logical Connective is a symbol which is used to connect two or more propositional or
predicate logics in such a manner that resultant logic depends only on the input logics and the
meaning of the connective used.
Generally there are five connectives which are −

1.1.1 Conjunction (AND) : If two statements are combined by the word “and” to form a
compound proposition (statement) is called the conjunction of the original
proposition.
Symbolically, if P & Q are two simple statements, then ‘ P Q ’ denotes the conjunction
of P and Q and is read as ‘P and Q.
Since, P Q is a proposition it has a truth value and this truth value depends only on the
truth values of P and Q.
Specifically, if P & Q are true then P Q is true; otherwise P Q is false.
The truth table for conjunction is as follows.

Example:
Let P : Monsoon is very good this year.
Q : The rivers are rising.
then
P Q : Monsoon is very good this year and rivers are rising.

1|Page
1.1.2 Disjunction (OR) : Any two statements can be connected by the word ‘or’ to form a
compound statement called disjunction.
Symbolically, if P and Q are two simple statements, then P Q denotes the disjunction of
P and Q and read as 'P or Q' .
The truth value of P Q depends only on the truth values of P and Q. specifically if P and
Q are false then P Q is false otherwise P Q is true.
The truth table for disjunction is as follows.

Example:
P : Paris is in France
Q : 2+ 3 =6
Then P Q : Paris is in France or 2 + 3 = 6.
Here, P Q is True since P is true & Q is False.
Thus, the disjunction P Q is false only when P and Q are both false.

1.1.3 Negation (NOT): Given any proposition P, another proposition, called negation of P,
can be formed by writing “It is not the case that…….. or”. “It is false that…….”
before P or, if possible, by inserting in P the word “not”.
Symbolically  P or  P read “not P” denotes the negation of P. the truth value of  P
depends on the truth value of P.
If P is true then  P is false and if P is false then  P is true. The truth table for Negation
is as follows :

Example:
Let P : 6 is a factor of 12.
Then Q =  P : 4 is not a factor of 12.
Here P is true &  P is false.

1.1.4 Conditional or Implication: (If……then): If two statements are combined by using

the logical connective ‘if….then’ then the resulting statement is called a conditional
statement.
If P and Q are two statements forming the implication “if P then Q” then we denotes this
implication P Q  .
In the implication P Q  ,
P is called antecedent or hypothesis

2|Page
 Q is called consequent or conclusion.
The statement P Q  is true in all cases except when P is true and Q is false.
The truth table for implication is as follows.

Since conditional statement play an essential role in mathematical reasoning a variety of

terminology is used to express P Q  .

i) If P then Q
ii) P implies Q
iii) P only if Q
iv) Q if P
v) P is sufficient condition for Q
vi) Q when P
vii) Q is necessary for P
viii) Q follows from P
ix) if P, Q
x) Q unless  P

Converse, Inverse and Contrapositive of a conditional statement : We can form some

new conditional statements starting with a conditional statements related conditional
statements that occur so often that they have special names  converse, contrapositive &
Inverse. Starting with a conditional statement P Q  that occur so often that they have special
names.
1. Converse : If P Q  is an implication then Q P  is called the converse of P Q  .
2. Contrapositive : If P Q  is an implication then the implication  Q P   is called
it’s contrapositive.
3. Inverse : If P Q  is an implication then  P Q   is called its inverse.

Example:
Let P : You are good in Mathematics.
Q : You are good in Logic.
Then, P Q  : If you are good in Mathematics then you are good in Logic.
1) Converse : Q P  
If you are good in Logic then you are good in Mathematics.
2) Contrapositive :  Q P
If you are not good in Logic then you are not good in Mathematics.

3|Page
 3) Inverse :  P Q   
If you are not good in Mathematics then you are not good in Logic.
1.1.5 Biconditional Statement : Let P and Q be propositions. The biconditional statement P
Q  is the proposition "P if and only if Q". The biconditional statement is true when P and Q
have same truth values and is false otherwise.
Biconditional statements are also called bi-implications. It is also read as p is necessary and
sufficient condition for Q.
The truth table for biconditional statement is as follows.

Example:
Let P : You can take the flight.
Q : You buy a ticket.
Then P Q  is the statement.
“You can take the flight iff you buy a ticket”.

Precedence of Logical Operators

We can construct compound propositions using the negation operator and the logical
operators defined so far. We will generally use parentheses to specify the order in
which logical operators in a compound proposition are to be applied. In order to avoid
an excessive number of parentheses.
We sometimes adopt an order of precedence for the logical connectives. The
following table displays the precedence levels of the logical operators.

1.2 Logical Equivalence

4|Page
 Logical equivalence is a type of relationship between two statements or sentences in
propositional logic or Boolean algebra. ... A proposition is a declarative sentence (a
sentence that declares a fact) that is either true or false.

Compound propositions that have the same truth values in all possible cases are called
logically equivalent.
The compound propositions P and Q are called logically equivalent if P Q  is a
tautology. The notation P Q denotes that P and Q are logically equivalent.
Some equivalence are useful for deducing other equivalence. The following table shows
some important equivalence.
Logic, logical thinking, and correct reasoning have wide applications in many fields,
including law, psychology, rhetoric, science, and mathematics. While an interesting
study can be made of logic in human lives, we shall restrict our attention mainly to logic
as it is used in mathematics. This logic was first studied systematically by Aristotle (384
B.C.-322 B.C.). Aristotle and his followers studied patterns of correct and incorrect
reasoning.
Medieval philosophers and theologians, who made an intimate study of logical
arguments, carried the work of Aristotle forward. A big advance in the study of
mathematical logic came with the work of Gottfried Wilhelm von Leibniz (1646-
1716),one of the inventors of calculus. Leibnitz introduced symbols to represent ideas in
logic- letters for statements and other symbols for the relations between statements.
Leibnitz hoped that logic would become a universal characteristic and unify all of
mathematics.
Logic is the tool for reasoning about the truth and falsity of statements. There are two
main directions in which logic develops.
 The first is the depth to which we explore the structure of statements. The study
of the basic level of structure is called propositional logic. First order predicate
logic, which is often called just predicate logic, studies structure on a deeper
level.
 The second direction is the nature of truth. For example, one may talk about
statements that are usually true or true at certain times.
“True” and “false” could be replaced by T and F (or any other two symbols) in our
discussions. Using T and F relates logic to Boolean functions. In fact, propositional logic
is the study of Boolean functions, where T plays the role of “true” and F the role of
“false”.
Our study is restricted to propositional and predicate logic only.

1.3 Logical Identities or Laws of Logic

5|Page
Note that while taking negation of compound statement ‘every’ or ‘All’ is interchanged by
‘some’ & ‘there exists’ is interchanged by ‘at least one’ & vice versa.
Example:
If P : “This book is good.”
Q : “This book is costly.”

Write the following statements in symbolic form.

a) This book is good & costly.
b) This book is not good but costly.
c) This book is cheap but good.
d) This book is neither good nor costly.

6|Page
e) If this book is good then it is costly.

1.3.1 Functionally complete set of Connectives : We know that there are five logical
connectives ,  ,,  and . But some of these can be expressed in terms of the
other & we get a smaller set of connectives.
The set containing minimum number of connectives which are sufficient to express any
logical formula in symbolic form is called as the functionally complete set of connectives.
There are following two functionally complete set of connectives.
(1) ,  is complete set connectives.
Here, the  can be expressed using  &  .
P  Q    PQ 
   P   Q
The  can be expressed in terms of , .
P Q   P Q
The  can be expressed in terms of , 

,  is a functionally complete set of connectives.

Similarly, you can prove that , is complete set of connectives.

7|Page
 1.4 Logical Implication Rules Of inference
A proposition P (p, q, ……..) is said to logically imply a proposition Q (p, q, …….) written,
P (p, q, ……..)  Q (p, q, …….) if Q (p, q, …….) is true whenever P (p, q, …….) is true.
Example :
P  (P  Q)
Solution:
Consider the truth table for this

Observe that if P is true (T) in rows 1 and 2 then P Q is also true (T) .  P P Q .
If Q (p, q, …….) is true whenever P (p, q, …….) is true then the argument. P (p, q, ...... ├ Q
(p, q, ...... is valid and conversely.
i.e. the argument P├Q is valid iff the conditional statement P Q is always true, i.e. a
tautology.
1.4.1 Logical Equivalence Involving Implications:
Let P & Q be two statements.
The following table displays some useful equivalences for implications involving conditional
and biconditional statements.

All these identities can be proved by using truth tables.

8|Page
The rules of inference (also known as inference rules) are a logical form or guide
consisting of premises (or hypotheses) and draws a conclusion.

A valid argument is when the conclusion is true whenever all the beliefs are true, and
an invalid argument is called a fallacy as noted by Monroe Community College .

In other words, an argument is valid when the conclusion logically follows from the truth
values of all the premises.

There are two ways to form logical arguments, as seen in the image below. We will be
utilizing both formats in this lesson to become familiar and comfortable with their
framework.

Basic Example

Now, before we jump into the inference rules, let’s look at a basic example to help us
understand the notion of assumptions and conclusions.

Is this argument valid?

Without using our rules of logic, we can determine its truth value one of two ways.

1. Surmising the fallacy of each premise, knowing that the conclusion is valid
only when all the beliefs are valid.
2. Construct a truth table and verify a tautology.

9|Page
From the above example, if we know that both premises “If Marcus is a poet, then he is
poor” and “Marcus is a poet” are both true, then the conclusion “Marcus is poor” must
also be true.

And using a truth table validates our claim as well.

Rules Of Inference Examples

But what if there are multiple premises and constructing a truth table isn’t feasible?

Thankfully, we can follow the Inference Rules for Propositional Logic !

10 | P a g e
Now, these rules may seem a little daunting at first, but the more we use them and see
them in action, the easier it will become to remember and apply them.

Let’s look at an example for each of these rules to help us make sense of things.
Let p be “It is raining,” and q be “I will make tea,” and r be “I will read a book.”

Example — Modus Ponens

Example — Modus Tollens

Example — Hypothetical Syllogism

Example — Disjunctive Syllogism

Example — Addition

11 | P a g e
Example — Simplification

1.5 Quantifier’s Propositional Logic

Quantifier is used to quantify the variable of predicates. It contains a formula, which is a type
of statement whose truth value may depend on values of some variables. When we assign a
fixed value to a predicate, then it becomes a proposition. In another way, we can say that if
we quantify the predicate, then the predicate will become a proposition. So quantify is a type
of word which refers to quantifies like "all" or "some".
There are mainly two types of quantifiers that are universal quantifiers and existential
quantifiers. Besides this, we also have other types of quantifiers such as nested quantifiers
and Quantifiers in Standard English Usages. Quantifier is mainly used to show that for how
many elements, a described predicate is true. It also shows that for all possible values or for
some value(s) in the universe of discourse, the predicate is true or not.
Example 1:
"x ≤ 5 ∧ x > 3"
This statement is false for x= 6 and true for x = 4. Now we will compare the above statement
with the following statement.
"For every x, x ≤ 5 ∧ x > 3"
This statement is definitely false. Now we will again define a statement.
"There exists an x such that "x ≤ 5 ∧ x > 3"

This statement is definitely true. The phrase "there exists an x such that" is known as the
existential quantifier, and "for every x" phrase is known as the universal quantifier. The
variables in a formula cannot be simply true or false unless we bound these variables by using
the quantifier.

12 | P a g e
Example 2: Suppose we have two statements that are ∀x : x2 +1 > 0 and ∀x : x2 > 2. For x =
1, the first statement ∀x : x2 +1 > 0 is true, but the second statement ∀x : x2 > 2 is false,

as ∃x : x 2 > 2, it will be true, because x = 2 is an example that satisfies it.

because it does not satisfy the predicate. On the other side, if we write the second statement

comes from some base set. If we specify x as a real number, then the statement ∀x : x2 +1 > 0
In the quantified expression, if there is a variable, then we always assume that the variable

will be true. But this statement will be false if we specify x as a complex number such as i. In
this case, the predicate will not satisfy by x = i because we don't specify the value of i.

1.5.1 Universal Quantifiers

Sometimes the mathematical statements assert that if the given property is true for all values
of a variable in a given domain, it will be known as the domain of discourse. Using the

is denoted by the ∀, which means "for all". Suppose P(x) is used to indicate predicate, and D
universal quantifiers, we can easily express these statements. The universal quantifier symbol

is used to indicate the domain of x. The universal statement will be in the form "∀x ∈ D,
P(x)". The main purpose of a universal statement is to form a proposition. In the quantifiers,
the domain is very important because it is used to decide the possible values of x. When we
change the domain, then the meaning of universal quantifiers of P(x) will also be changed.
When we use the universal quantifier, in this case, the domain must be specified. Without a
domain, the universal quantifier has no meaning.

The sentence ∀xP(x) will be true if and only if P(x) is true for every x in D or P(x) is true for
every value which is substituted for x. The statement ∀xP(x) will be false if and only if P(x)
is false for at least one x in D. The value for x for which the predicate P(x) is false is known
as the counterexample to the universal statement. If finite values such as {n 1, n2, n3, …, nk}
are contained by the universe of discovery, the universal quantifier will be the conjunction of
all elements, which is described as follows:

∀xP(x) ⇔ P(n1) ∧ P(n2) ∧ · · · ∧ P(nk)

Example 1: Suppose P(x) indicates a predicate where "x must take an electronics course" and
Q(x) also indicates a predicate where "x is an electrical student". Now we will find the
universal quantifier of both predicates.

Solution: Suppose the students are from ABC College. For both predicates, the universe of
discourse will be all ABC students.

The statements can be: "Every electrical student must take an electronics course". The
following syntax is used to define this statement:

∀x(Q(x) ⇒ P(x))

This statement can be expressed in another way: "Everybody must take an electronics course
or be an electrical student". The following syntax is used to define this statement:

∀x(Q(x) ∨ P(x))

13 | P a g e
Example 2: Suppose P(x) indicates a predicate where "x is a square" and Q(x) also indicates
a predicate where "x is a rectangle". Now we will find the universal quantifier of these
predicates.

Solution:

The statement must be:

∀x (x is a square ⇒ x is a rectangle), i.e., "all squares are rectangles.'' The following syntax
is used to describe this statement:

∀xP(x) ⇒Q(x)

Sometimes, we can use this construction to express a mathematical sentence of the form "if
this, then that," with an "understood" quantifier.

Universal conditional statement:

This statement has the form: ∀x, if P(x) then Q(x).

For example: In this example, we will rewrite the below statement in the form:

∀______, if______then______

If Jack is 18 years old or older, then he is eligible to vote.

1.5.2 Existential Quantifiers

Sometimes the mathematical statements assert that we have an element that contains some

existential quantifier symbol is denoted by the ∃, which means "there exists". Suppose P(x)
properties. Using existential quantifiers, we can easily express these statements. The

statement will be in the form "∃x ∈ D such that P(x)". The main purpose of an existential
is used to indicate predicate, and D is used to indicate the domain of x. The existential

statement is to form a proposition. The sentence ∃xP(x) will be true if and only if P(x) is true
for at least one x in D. The statement ∃xP(x) will be false if and only if P(x) is false for all x
in D. The value for x for which the predicate P(x) is false is known as the counterexample to
the existential statement.

If finite values such as {n 1, n2, n3, …, nk} are contained by the universe of discovery, the
universal quantifier will be the disjunction of all elements, which is described as follows:

∃xP(x) ⇔ P(n1) ∨ P(n2) ∨ P(n3) · · · ∨ P(nk)

Example 1: Suppose P(x) contains a statement "x > 4". Now we will find the truth value of
this statement.

14 | P a g e
Solution:

This statement is false for all real number which is less than 4 and true for all real numbers
which are greater than 4.

This statement is false for x= 6 and true for x = 4. Now we will compare the above statement
with the following statement. So

∃xP(x) is true

1.6 Equivalences
Two logical expressions are said to be equivalent if they have the same truth value in all
cases. Sometimes this fact helps in proving a mathematical result by replacing one
expression with another equivalent expression, without changing the truth value of the
original compound proposition.
Types of propositions based on Truth values
There are three types of propositions when classified according to their truth values

1. Tautology – A proposition which is always true, is called a tautology.

2. Contradiction – A proposition which is always false, is called a contradiction.
3. Contingency – A proposition that is neither a tautology nor a contradiction is
called a contingency.

Example
1. is a tautology.
2. is a contradiction.
3. is a contingency.

Definition of Logical Equivalence

Formally,
Two propositions and are said to be logically equivalent if is a Tautology. The
notation is used to denote that and are logically equivalent.
One way of proving that two propositions are logically equivalent is to use a truth table.
The truth table must be identical for all combinations for the given propositions to be
equivalent. But this method is not always feasible since the propositions can be increasingly
complex both in the number of propositional variables used and size of the expression.

15 | P a g e
In this case, there needs to be a better way to prove that the two given propositions are
logically equivalent. That better way is to construct a mathematical proof which uses
already established logical equivalences to construct additional more useful logical
equivalences.

Some basic established logical equiva

The above Logical Equivalences used only conjunction, disjunction and negation. Other
logical Equivalences using conditionals and bi-conditionals are-

16 | P a g e
Example,
Show that.

Another example,
Show that .

The above examples could easily be solved using a truth table. But this can only be done
for a proposition having a small number of propositional variables. When the number of
variables grows the truth table method becomes impractical.
For a proposition having 20 variables, rows have to be evaluated in the truth table.
This may be easy to do with a computer, but even a computer would fail in computing the
truth table of a proposition having 1000 variables.

1.6 Predicates and Quantifiers

Predicates: A predicate is a statement containing one or more variables.
Proposition: If values are assigned to all the variables in a predicate, the resulting
statement is a proposition.
e.g.
1. x  9 is a predicate
2. 4 < 9 is a proposition

17 | P a g e
 Propositional Function : Let a be a given set. A propositional function (or : on open
sentence or condition) defined on A is an expression P(x) which has the property that
P(a) is true or false for each a A  .
The set A is called domain of P(x) and the set Tp of all elements of A for which P (a) is
true is called the truth set of P(x).

Quantifiers : The expressions ‘ for all’ and ‘there exists’ are called quantifiers. The
process of applying quantifier to a variable is called quantification of variables.

Universal quantification: The universal quantification of a predicate P(x) is the

statement, “For all values of x, P(x) is true.”
The universal quantification of P(x) is denoted by v for all x P(x).
The symbol v is called the universal quantifier.
e.g.
1) The sentence P(x) : - (-x) = x is a predicate that makes sense for real numbers x.
The universal quantification of P(x), v x P(x) is a true statement because for all real
numbers, -(- x) = x.
2) Let Q(x) : x + 1 < 5, then v Q(x) : x + < 5 is a false statement, as Q(5) is not true.
Universal quantification can also be stated in English as “for every x”, “every x”, or “for
any x.”

Existential quantification - The existential quantification of a predicate P(x) is the

statement “There exists a value of x for which P(x) is true.”
The existential quantification of P(x) is denotedxP x( ) . The symbol  is called the
existential quantifier.

e.g.
1) Let Q x: 1 4   . The existential quantification of Q(x), xQ x( ) is a true statement,
because Q(2) is true statement.
2) The statement y, y + 2 = y is false. There is no value of y for which the
propositional function y+2=y produces a true statement.

18 | P a g e
 The result for universal and existential quantifiers is as follows.

Example: Express the statement using quantifiers. “Every student in your school has a
computer or has a friend who has a computer.”
Solution :
Let c(x) : “x has a computer”
F(x,y) : “x and y are friends”

19 | P a g e
Example:
Express following using quantifiers.
i) There exists a polar bear whose colour is not white.
ii) Every polar bear that is found in cold region has a white colour.

Solution :
Let
A(x): x has a white colour
B(x): x is a polar bear.
C(x): x is found in cold region.
Over the universe of animals.

1.9 Introduction to Proofs, Proof Methods

Mathematical proof is an argument we give logically to validate a mathematical statement.
In order to validate a statement, we consider two things: A statement and Logical
operators.
A statement is either true or false but not both. Logical operators are AND, OR, NOT, If
then, and If and only if. Coupled with quantifiers like for all and there exists. We apply
operators on the statement to check the correctness of it.
Proof Methods
Types of Proofs. Suppose we wish to prove an implication p → q. Here are some strategies
we have available to try.
1. Direct Proof:
Example.
Prove the statement: For all integers m and n, if m and n are odd integers, then m + n
is an even integer.
Proof.
Assume m and n are arbitrary odd integers. Then m and n can be written in the form
m = 2a + 1 and n = 2b + 1

20 | P a g e
 where a and b are also integers. Then
m + n = (2a + 1) + (2b + 1) (substitution)
= 2a + 2b + 2 (associative and commutative)
(Laws of addition)
= 2(a + b + 1) (distributive law)
Since m+n is twice another integer, namely, a+b+1, m+n is an even integer.

The first strategy you should try when attempting to prove any assertion is to give a
direct proof. That is, assume the hypotheses that are given and try to argue directly
that the conclusion follows. This is often the best approach when the hypotheses can
be translated into algebraic expressions (equations or inequalities) that can be
manipulated to give other algebraic expressions, which are useful in verifying the
conclusion.

Example:
shows a simple direct proof of a very familiar result. We are using the familiar
definitions of what it means for an integer to be even or odd: An integer n is even if n
= 2k for some integer k; an integer n is odd if n = 2k + 1 for some integer k. Study the
form of this proof. There are two hypotheses, “m is an odd integer,” and “n is an odd
integer”; and the conclusion is the statement “m + n is an even integer.” This
“theorem” is a quantified statement (“for all integers m and n”, or “for all odd integers
m and n”). In the proof we assumed the hypotheses held for arbitrarily integers m and
n, and then we wrote down equations that follow from the definition of what it means
for these integers to be odd. Although this looks like a pretty obvious thing to do, at
least when you see someone else do it, this step, in which you bring your knowledge
to the problem, may seem like a big one to take, and you may find yourself stalling
out at this point.

One possible reason this may happen is that you may be trying to do too much at
once. The cure for this is to be patient: take small steps, using the appropriate
definitions and previously proven facts, and see where they lead. When we wrote
down m = 2a + 1 and n = 2b + 1, we did a number of fairly sophisticated things. First,
we used our knowledge (definitions) of what it means for an integer to be odd.
Second, in order for this information to be useful, we needed to translate this
knowledge into a mathematical expression, or expressions in this case, that are subject
to manipulation. And third, in setting up these expressions, we needed to use
appropriate mathematical notation, so that we did not introduce any subtle or hidden
relationships into the picture that are unwarranted by the hypotheses.
A common mistake of this type might arise as follows:
“Well, m is an odd integer, so I can write m = 2k + 1, where k is an integer. Since n is
also an odd integer, I can write n = 2k + 1, where k is an integer.”

Do you see the mistake? By allowing the same letter k to represent what might be
different integers, we have inadvertently added another assumption, namely, that m =
n! Of course, we didn’t mean to do this, but, unfortunately, our intentions haven’t
been carried out, and so our proof breaks down at this point. In order to maintain the

21 | P a g e
 “arbitrariness” of m and n, we must allow, at the least, that they be different. We
accomplish this by choosing different letters a and b in our representations of m and n
as “twice an integer plus one.” There is nothing sacred about a and b; we could have
used k and `, or x and y, or α and β, or any pair of symbols that have not been
appropriated for some other use.

Upon closer scrutiny, this first step now starts to seem like a big one indeed!
Especially if we may not be sure just where it will lead. The rest of the proof,
however, proceeds fairly routinely. We add m and n and observe that the resulting
expression has a factor of 2. We now only have to get past the recognition problem:
observing that the resulting expression gives us what we were looking for. Since we
have expressed m + n as twice another integer, m + n is, by definition, an even
integer. By Universal Generalization we may now confidently declare “Q.E.D.” (the
abbreviation of quod erat demonstrandum or “which was to be demonstrated”). Often
a box at the end of a proof or the abbrviation “Q.E.D.” is used at the end of a proof to
indicate it is finished.

Exercise. Give a careful proof of the statement: For all integers m and n, if m is odd
and n is even, then m + n is odd.

2. Proof by Contrapositive
Example.
Prove the statement: For all integers m and n, if the product of m and n is even, then
m is even or n is even.
We prove the contrapositive of the statement: If m and n are both odd integers, then
mn is
odd.

Proof.
Suppose that m and n are arbitrary odd integers. Then m = 2a + 1 and n = 2b + 1,
where a and b are integers. Then
mn = (2a + 1)(2b + 1) (substitution)
= 4ab + 2a + 2b + 1 (associative, commutative, and distributive laws)
= 2(2ab + a + b) + 1 (distributive law)
Since mn is twice an integer (namely, 2ab + a + b) plus 1, mn is odd.

If a direct proof of an assertion appears problematic, the next most natural strategy to
try is a proof of the contrapositive. In Example 2.4.1 we use this method to prove that

has the form p → (r ∨s). If you take our advice above, you will first try to give a
if the product of two integers, m and n, is even, then m or n is even. This statement

direct proof of this statement: assume mn is even and try to prove m is even or n is
even. Next, you would use the definition of “even” to write mn = 2k, where k is an
integer. You would now like to conclude that m or n has the factor 2. This can, in fact,
be proved directly, but it requires more knowledge of number theory than we have
available at this point. Thus, we seem to have reached a dead-end with the direct
approach, and we decide to try an indirect approach instead.

22 | P a g e
 The contrapositive of p → (r ∨ s) is ¬(r ∨ s) → ¬p, or, by De Morgan’s Law, (¬r ∧
¬s) → ¬p.
This translates into the statement
“If m and n are odd, then mn is odd”
where “not even” translates to “odd”). This is a good illustration of how the symbolic
form of a proposition can be helpful in finding the correct statement we wish to prove.
In this particular example, the necessity of De Morgan’s Law may be more evident in
the symbolic form than in the “English version.”

Now we give a direct proof of the contrapositive: we assume m and n are arbitrary
odd integers and deduce mn is odd. This proof is carried out in very much the same
way as the direct proof in Example 2.3.1. The main difficulty we encounter with the
problem of proving the original assertion is to realize that a direct proof should be
abandoned in favor of some other strategy.

Exercise The following statement is a special case of the proposition proved in

Example Give a careful proof of this statement without assuming the result in
Example.

For every integer n, if n 2 is even, then n is even.

3. Proof by Contradiction.
Example. Prove the statement is true: Let x and y be real numbers. If 5x + 25y =
1723, then x or y is not an integer.

Proof
Assume x and y are real numbers such that 5x+25y = 1723, and assume that both x
and y are integers. By the distributive law,
5(x + 5y) = 1723
Since x and y are integers, this implies 1723 is divisible by 5. The integer 1723,
however, is clearly not divisible by 5. This contradiction establishes the result.

If we have tried unsuccessfully to find a direct proof of a statement or its

contrapositive, we might next try to give a proof by contradiction. In this method of
proof we assume the hypotheses are true and the conclusion is false and try to arrive

¬(p ∧ ¬q) is equivalent to p → q: if we can show that p ∧ ¬q is false, then ¬(p ∧ ¬q)
at a contradiction. The validity of proof by contradiction follows from the fact that

is true, so that the equivalent proposition p → q is also true.

In Example 2.5.1 we are asked to prove that if 5x + 25y = 1723, then x is not an
integer or y is not an integer. This has the same propositional form as the example in

p → (r ∨ s)
Example 2.4.1:

If we try to give a direct proof of this statement, then we are forced to “prove a
negative,” which can be difficult. If we try to prove the contrapositive, then knowing

23 | P a g e
 that x and y are integers doesn’t seem to be helpful in trying to show directly that 5x +
25y 6= 1723, since we are again trying to prove a negative.

On the other hand, if we assume p and ¬(r ∨ s), which is equivalent to ¬r ∧ ¬s, then

integers. After a couple of observations we arrive at the contradiction r ∧ ¬r, where r

we have two positive statements to work with: 5x+25y = 1723, and x and y are

is the statement “1723 is divisible by 5.” This contradiction establishes the truth of the
statement, and we are through.

Exercise Prove: For all real numbers x and y, if 35x + 14y = 253, then x is not an
integer or y is not an integer.

Here is another example of a proposition that is best proved by contradiction.

Example 2.5.2. For all positive real numbers a, b, and c, if ab = c, then a ≤ √ c or b ≤ √

c.

Proof. Suppose a, b, and c are positive real numbers such that ab = c, and suppose a >
√ c and b > √ c. (Notice the use of De Morgan’s Law again. Also, recall that the
symbol √ c represents the positive square root of c, not ± √ c.) By order properties of

b > √ c ⇔ ab > a√ c, since a > 0,

the real numbers.

a > √ c ⇔ a √ c > √ c · √ c = c, since √ c > 0.

and

Thus, ab > a√ c > √ c · √ c = c implies

ab > c.
But ab = c; hence, ab is not greater than c, a contradiction
This proves our assumption a > √ c and b > √ c cannot be true when a, b, and c are
positive real numbers such that ab = c. Therefore a ≤ √ c or b ≤ √ c.

Exercise 2.5.2. Consider the statement: For all nonnegative real numbers a, b, and c, if
a 2 + b 2 = c 2 , then a + b ≥ c.

(a) Give a proof by contradiction.

(b) Give a direct proof.
[Hint: The extra idea needed for a direct proof should emerge naturally from a proof
by contradiction.]

Let’s step back and compare direct proof, proof by contrapositive, and proof by
contradiction.

Fill in the blanks

If we are proving the implication p → q we assume. . .
(1) p for a direct proof.
(2) for a proof by contrapositive
(3) for a proof by contradiction.

24 | P a g e
 We are then allowed to use the truth of the assumption in 1, 2, or 3 in the proof.

After the initial assumption, we prove p → q by showing

(4) q must follow from the assumptions for a direct proof.

(5) must follow the assumptions for a proof by contrapositive.
(6) must follow the assumptions for a proof by contradiction.

4. Proof by Cases.
Example:
If x is a real number such that x 2 − 1 x + 2 > 0, then either x > 1 or −2 < x < −1.
Proof. Assume x is a real number for which the inequality
x 2 – 1/ x + 2 > 0
holds. Factor the numerator of the fraction to get the inequality

For this combination of x + 1, x − 1, and x + 2 to be positive, either all are positive or

two are negative and the other is positive. This gives four cases to consider:

Case 1. x + 1 > 0, x − 1 > 0, and x + 2 > 0. In this case x > −1, x > 1, and x > −2,
which implies x > 1.
Case 2. x + 1 > 0, x − 1 < 0, and x + 2 < 0. In this case x > −1, x < 1, and x < −2, and
there is no x satisfying all three inequalities simultaneously.
Case 3. x + 1 < 0, x − 1 > 0, and x + 2 < 0. In this case x < −1, x > 1, and x < −2, and
there is no x satisfying all three inequalities simultaneously.
Case 4. x + 1 < 0, x − 1 < 0, and x + 2 > 0. In this case x < −1, x < 1, and x > −2,
which implies that −2 < x < −1.

Thus, either x > 1 (Case 1) or −2 < x < −1 (Case 4).

Sometimes the hypothesis of a statement can be broken down into simpler cases that
may be investigated separately. The validity of a proof by cases rests on the
equivalence

[(p1 ∨ · · · ∨ pn) → q] ⇔ [(p1 → q) ∨ · · · ∨ (pn → q)].

In Example 2.6.1 this method is used to verify the “solution” to the inequality

Prove: For every real number x, √ x 2 = |x|. [Hint: Recall as above that √ x 2
represents the positive square root of x 2 , and look at two cases: x ≥ 0 and x < 0.]
A proof by cases can tend to be a little tedious. Here is an extreme example of such a
proof.
Prove that if n is a natural number less than 41, then n 2−n+41 is a prime number.

25 | P a g e
 Proof. Recall that a prime number is an integer greater than 1 that is only divisible by
itself and 1. It would be nice if there was some general line of argument that would
work, but, unfortunately, there doesn’t seem to be an obvious one. As a result, the
proof must be broken down into 41 cases corresponding to n = 0, 1, 2, ..., 40. In each
case we examine the integer n 2 − n + 41 to see if it is prime. For example, we can
observe:

n = 0: 02 − 0 + 41 = 41 is prime.
n = 1: 12 − 1 + 41 = 41 is prime.
n = 2: 22 − 2 + 41 = 43 is prime.
n = 3: 32 − 3 + 41 = 47 is prime.
n = 4: 42 − 4 + 41 = 53 is prime.

As n increases, it becomes increasingly more time-consuming to show that n 2−n+41

is, indeed, prime. For example, when n = 40, 402 − 40 + 41 = 1601. The simplest way
to show that 1601 is prime is to show that every prime number ≤ √ 1601 fails to be a
divisor of 1601. There are 12 such numbers to try, and you might as well check them
on your calculator. Alternatively, you could write a computer program or use a
symbolic program such as Maple or Mathematica that has a routine to test a number
for primality.

26 | P a g e