Chapter 1

Discrete structures
COE 253

P.A Kwabi

KNUST

October 12, 2024

1 / 45
Chapter 1

Outline

1 Chapter 1
Propositional and Predicate Logic
Rules of Inference
Proof Methods

2 / 45
Chapter 1

Propositional Logic

The rules of logic give precise meaning to mathematical

statements.
What is a Proposition?
A statement (or proposition) is a declarative sentence that is either
true or false, but not both.
We use letters like (p,q,r,s,...) to denote propositional variables (or
statement variables).
The truth value of a true proposition is denoted by T, and the
truth value of a false proposition is denoted by F.
This area of logic that deals with propositions is called the
propositional calculus or Propositional Logic. 3 / 45
Chapter 1

Logical Connectives

The elementary connectives include "and", "or", "not", "if-then",

and "if and only if".
Names of Connectives;
1 Conjunction (AND,∧)
2 Disjunction (OR, ∨)
3 Negation (NOT, ¬)
4 Implication (IF-THEN, →)
5 Bi-implication (IFF, ⇔)

4 / 45
Chapter 1

Cont’d

Let p and q be statement variables;

In ordinary language or is sometimes used in an exclusive sense
(p or q but not both) and sometimes in an inclusive sense (p or q
or both) named Exclusive Or and Inclusive Or respectively.
The symbol ∨ is used to define or in its inclusive sense.
To express the exclusive or, the phrase p or q but not both is used.

5 / 45
Chapter 1

Cont’d
Examples:

1 x is greater than 1 or x is less than 4

Math Translation: x>1 ∨ x <4
2 If a number is even, then it is divisible by 2.
Math Translation: x=2k → x mod 2=0
3 (x=3 ∨ x=5) ∧ ¬(x=3 ∧ x=5)
English Translation: "x is either 3 or 5, but not both."
4 ¬(x>5)→ ¬(y>10)
English Translation: "If x is not greater than 5, then y is not
greater than 10."
6 / 45
Chapter 1

Cont’d

Truth Table of Connectives

p q ¬p p∧q p∨q p⊕q p→q p⇔q
T T F T T F T T
T F F F T T F F
F T T F T T T F
F F T F F F T T

Basically, connectives connect propositions together.

Trial: Construct the truth table of compound propositions.
NB: Precedence of Logical Operators is important in forming a
compound proposition, that is (¬, ∧, ∨, →, ⇔)

7 / 45
Chapter 1

Conditional Statements

When you make a logical inference or deduction, you reason from a

hypothesis to a conclusion.
Let p and q be statements. A sentence of the form “If p then q” is
denoted symbolically by "p → q"; p is called the hypothesis and q
is called the conclusion.
Such a sentence is called conditional because the truth of
statement q is conditioned on the truth of statement p.
That is, p → q is false only when p is true and q is false.

8 / 45
Chapter 1

Cont’d

A variety of terminology is used to express p → q. You will

encounter most if not all of the following ways to express this
conditional statement:

if p, then q

p is sufficient for q

a necessary condition for p is q

p implies q

a sufficient condition for q is p

q is necessary for p
9 / 45
Chapter 1

Cont’d

Suppose a conditional statement of the form "If p then q" is given.

Then;

The contrapositive is If ¬q then ¬p

Symbolically, the contrapositive of p → q is ¬q → ¬p.

The converse is "If q then p".

Symbolically, the converse of p → q is q → p,

The inverse is "If ¬p then ¬q".

Symbolically, the inverse of p → q is ¬p → ¬q.

Examples: State the converse, inverse and the contrapositive of

each of the following statements. Be sure to label each.
10 / 45
Chapter 1

Cont’d

1 If life is a bowl of cherries, then I am not in the pits.

2 If wishes were horses, then beggars would ride.
3 In order for it to rain it is necessary that there be clouds.

Given statement variables p and q, the biconditional of p and q is

"p if, and only if, q" and is denoted p ⇔ q. It is true if both p and
q have the same truth values and is false if p and q have opposite
truth values. There are some other ways to express p ⇔ q:
"p is necessary and sufficient for q", "if p then q, and conversely",
and "p iff q".

11 / 45
Chapter 1

Logical Equivalence

The statements

6 is greater than 2 and 2 is less than 6

are two different ways of saying the same thing. Why?

Definition: Two statement forms are called logically equivalent if,
and only if, they have identical truth values for each possible
substitution of statements for their statement variables. The
logical equivalence of statement forms P and Q is denoted by
writing P ≡ Q.

12 / 45
Chapter 1

Cont’d

Examples:
It is neither hot nor sunny
To say it is neither hot nor sunny means that it is not hot and
it is not sunny.
Hence, It is neither hot nor sunny ≡ It is not hot and it is not
sunny
Truth Tables to prove that ¬p ∨ q ≡ p → q.
p q ¬p ¬p ∨ q p→q
T T F T T
T F F F F
F T T T T
F F T T T
13 / 45
Chapter 1

Cont’d

Equivalence Name
p∧T ≡p Identity laws
p∨F ≡p
p∨T ≡T Domination laws
p∧F ≡F
p∨p ≡p Idempotent laws
p∧p ≡p
¬(¬p) ≡ p Double negation law
p∨q ≡q∨p Commutative laws
p∧q ≡q∧p
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r ) Associative laws
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r )
p ∨ (q ∧ r ) ≡ (p ∨ q) ∧ (p ∨ r ) Distributive laws
p ∧ (q ∨ r ) ≡ (p ∧ q) ∨ (p ∧ r )
¬(p ∧ q) ≡ ¬p ∨ ¬q De Morgan’s laws
¬(p ∨ q) ≡ ¬p ∧ ¬q
p ∨ (p ∧ q) ≡ p Absorption laws
p ∧ (p ∨ q) ≡ p
p ∨ ¬p ≡ T Negation laws
p ∧ ¬p ≡ F

14 / 45
Chapter 1

Cont’d

The two logical equivalences known as De Morgan’s laws are

particularly important. Thus;
1 ¬(p ∧q) ≡ ¬p ∨ ¬q
2 ¬(p ∨q) ≡ ¬p ∧ ¬q

Trial: Use the Truth Table to prove the De Morgan’s Laws.

15 / 45
Chapter 1

Applications of Propositional Logic

Logic has many important applications to mathematics, computer

science, and numerous other disciplines. Here are some
applications;
Logic Puzzles
Puzzles that can be solved using logical reasoning are known
as logic puzzles.
Example: Inhabitants of an island of knights and knaves
created by Smullyan, where knights always tell the truth and
knaves always lie. You encounter two people, A and B.
Determine, if possible, what A and B are if they address you
in the ways described. 16 / 45
Chapter 1

Cont’d

If you cannot determine what these two people are, can you draw
any conclusions?
I. A says "At least one of us is a knave" and B says nothing.
II. A says "The two of us are both knights" and B says "A is a
knave".
III. Both A and B say "I am a knight".

System Specifications

Boolean Searches

Logic Circuits

17 / 45
Chapter 1

Predicate and Quantifiers

What then is Predicate?

A predicate is a sentence that contains a finite number of variables
and becomes a statement when specific values are substituted for
the variable.
The symbolic analysis of predicates and quantified statements is
called the Predicate Calculus.
The two basic Quantifiers, "for all (∀)" and "there exists (∃)"
come into play here.

18 / 45
Chapter 1

The sentences “x is a student at Knust” and “x is a student at y”

are symbolized as P(x) and as Q(x, y), respectively, where x and y
are predicate variables that take values in appropriate sets.
Example: Let Q(x, y) denote the statement "x = y + 3".
What are the truth values of the propositions Q(1, 2) and Q(3, 0)?
Solution:
To obtain Q(1, 2), set x = 1 and y = 2 in the statement Q(x, y).
Hence, Q(1, 2) is the statement "1 = 2 + 3", which is false. The
statement Q(3, 0) is the proposition "3 = 0 + 3", which is true.

19 / 45
Chapter 1

Universal Quantifier

Definition: Let Q(x) be a predicate and D the domain of x. A

universal statement is a statement of the form “∀x∈D, Q(x).” It is
defined to be true if, and only if, Q(x) is true for each individual x
in D. It is defined to be false if, and only if, Q(x) is false for at
least one x in D. A value for x for which Q(x) is false is called a
counterexample to the universal statement.

20 / 45
Chapter 1

Cont’d

Examples:
1 The assertion ∀x, x + 1 < x claims that for every x, the
number x + 1 is less than x.
Solution:
When x = 1, we have 1 + 1 < 1. Since this is false, 1 is a
counterexample.
2 Let D = {1, 2, 3, 4, 5}, and consider the statement
∀x ∈ D, x 2 ≥ x.
Write one way to read this statement out loud, and show that
it is true.
21 / 45
Chapter 1

Existential Quantifier

Definition: Let Q(x) be a predicate and D the domain of x. An

existential statement is a statement of the form "∃ x ∈ D such that
Q(x)." It is defined to be true if, and only if, Q(x) is true for at
least one x in D. It is false if, and only if, Q(x) is false for all x in D
Examples:
Let Q(x) denote the statement "x = x + 1".
What is the truth value of the quantification ∃xQ(x), where
the domain consists of all real numbers?
Solution:
Because Q(x) is false for every real number x, the existential
quantification of Q(x), which is ∃xQ(x), is false. 22 / 45
Chapter 1

Cont’d

Consider the statement ∃ m∈ Z + such that m2 = m.

Write one way to read this statement out loud, and show that
it is true.
Solution:
“There is at least one positive integer m such that m2 = m.”
Observe that 12 = 1. Thus “m2 = m” is true for a positive
integer m, and so “∃m ∈ Z + such that m2 = m” is true.

23 / 45
Chapter 1

Cont’d

More examples:
1 Translate from Formal to Informal Language
∀x ∈ R, x 2 ≥ 0
∀x ∈ R, x 2 ̸= -1
∃m ∈ Z + such that m2 = m.

2 Translate from Informal to Formal Language

All triangles have three sides
No dogs have wings.
Some programs are structured.

NB: The combination of ∀ and ∃ is called Nested

Quantifiers.

24 / 45
Chapter 1

Rules of Inference

Invalid and Valid Argument

Proofs in mathematics are valid arguments that establish the truth
of mathematical statements. By an argument, we mean a
sequence of statements that end with a conclusion. By valid, we
mean that the conclusion, or final statement of the argument,
must follow from the truth of the preceding statements, or
premises, of the argument.

25 / 45
Chapter 1

Cont’d

For Example: Consider the argument;

If Socrates is a man, then Socrates is mortal.
Socrates is a man.
∴ Socrates is mortal has the abstract form

p→q
p
∴q

Using this notation, the hypotheses are written in a column,

followed by a horizontal bar, followed by a line that begins with the
therefore symbol and ends with the conclusion.
26 / 45
Chapter 1

Cont’d

When considering the abstract form of an argument, think of p

and q as variables for which statements may be substituted. An
argument form is called valid if, and only if, whenever statements
are substituted that make all the premises true, the conclusion is
also true.
A rule of inference is a form of argument that is valid.
The tautology (p ∧ (p → q)) → q is the basis of the rule of
inference called modus ponens, or the law of detachment.

27 / 45
Chapter 1

Cont’d
Rule of Inference Tautology Name
p
p→q (p ∧ (p → q)) → q Modus ponens
∴q
¬q
p→q (¬q ∧ (p → q)) → ¬p Modus tollens
∴ ¬p
p→q
q→r ((p → q) ∧ (q → r )) → (p → r ) Hypothetical syllogism
∴p→r
p∨q
¬p ((p ∨ q) ∧ ¬p) → q Disjunctive syllogism
∴q
p
p → (p ∨ q) Addition
∴p∨q
p∧q
(p ∧ q) → p Simplification
∴p
p
q (p ∧ q) → (p ∧ q) Conjunction
∴p∧q
p∨q
¬p ∨ r ((p ∨ q) ∧ (¬p ∨ r )) → (q ∨ r ) Resolution
∴q∨r 28 / 45
Chapter 1

Proof Methods

A mathematical proof is a way to demonstrate that a statement is

verifiably true or false. Without proofs every mathematical
statement would be purely hypothesis.
Here are the proofs we would be dealing with:
1 Direct Proofs
2 Proof by Contraposition
3 Proofs by Contradiction
4 Proofs by Induction

29 / 45
Chapter 1

Direct Proof

A direct proof shows that a conditional statement p → q is true by

showing that if p is true, then q must also be true, so that the
combination p true and q false never occurs.
Examples:
Give a direct proof of the theorem “If n is an odd integer,
then n2 is odd.”
Proof
Assume that n is odd. Then n = 2m + 1 for some natural
number m. But then
n2 = n.n = (2m + 1).(2m + 1) = 4m2 + 4m + 1 =
2(2m2 + 2m) + 1 30 / 45
Chapter 1

Cont’d

We see that n2 is 2m′ + 1, where m′ = 2m2 + 2m.

In other words, according to our definition, n2 is odd.
Prove that, if n is a positive integer, then the quantity n2 +
3n + 2 is even.
Proof
Denote the quantity n2 + 3n + 2 by K. Observe that
K = n2 + 3n + 2 = (n + 1)(n + 2)
Thus K is the product of two successive integers:
n + 1 and n + 2. One of those two integers must be even. So
it is a multiple of 2. Therefore K itself is a multiple of 2.
Hence K must be even. 31 / 45
Chapter 1

Cont’d

Exercises:
1 Prove that every even integer may be written as the sum of
two odd integers.
2 Prove the proposition that "The sum of two even natural
numbers is even".
3 Prove that the sum of an even integer and an odd integer is
odd.
4 Give a direct proof that if m and n are both perfect squares,
then nm is also a perfect square.
(An integer a is a perfect square if there is an integer b such
that a = b 2 .) 32 / 45
Chapter 1

Proof by Contraposition

Direct proofs begin with the premises, continue with a sequence of

deductions, and end with the conclusion. However, we will see that
attempts at direct proofs often reach dead ends. We need other
methods of proving theorems of the form ∀x(P (x) → Q(x)) called
indirect proofs.
Proofs by contraposition make use of the fact that the
conditional statement p → q is equivalent to its contrapositive, ¬q
→ ¬p. This means that the conditional statement p → q can be
proved by showing that its contrapositive, ¬q → ¬p, is true.

33 / 45
Chapter 1

Cont’d

That is, we take ¬q as a premise, and using axioms, definitions,

and previously proven theorems, together with rules of inference,
we show that ¬p must follow.
Examples:
Let us show that, if n is an integer and n2 is even, then n is
even. We do so by contraposition.
Proof:
So suppose that n is odd. We shall then show that n2 is odd.
The hypothesis then is that n = 2k + 1 for some integer k.
Then n2 = (2k + 1)2 = 4k 2 + 4k + 1 = 2(2k 2 + 2k) + 1.
Thus we see explicitly that n2 is odd, and our result is proved. 34 / 45
Chapter 1

Cont’d

Let us prove that, if k is an integer and 3k + 1 is even, then k

is odd.
Proof:
Assume that k is even.
So k = 2m for some integer m.
Then 3k + 1 = 3(2m) + 1 = 2(3m) + 1, which is clearly odd.
That gives the result.

Let P(n) be "If a and b are positive integers with a ≥ b, then

an ≥ b n ," where the domain consists of all nonnegative
integers. Show that P(0) is true.
35 / 45
Chapter 1

Cont’d

Proof:
The proposition P(0) is "If a ≥ b, then a0 ≥ b 0 ". Because
a0 = b 0 = 1, the conclusion of the conditional statement "If a ≥ b,
then a0 ≥ b 0 " is true. Hence, this conditional statement, which is
P(0), is true. This is an example of a trivial proof.
Note that the hypothesis, which is the statement "a ≥ b", was not
needed in this proof.

36 / 45
Chapter 1

Proofs by Contradiction

One kind of indirect proof, argument by contradiction, is based on

the fact that either a statement is true or it is false but not both.
This method of proof is also known as reductio ad impossible or
reductio ad absurdum because it relies on reducing a given
assumption to an impossibility or absurdity.
Suppose we want to prove that a statement p is true.
Furthermore, suppose that we can find a contradiction q such that
¬p → q is true. Because q is false, but ¬p → q is true, we can
conclude that ¬p is false, which means that p is true.

37 / 45
Chapter 1

Cont’d

Example:
√
Prove that 2 is irrational by giving a proof by contradiction.
Proof:
√
Let p be the proposition “ 2 is irrational.” To start a proof by
contradiction, we suppose that ¬p is true. Note that ¬p is the
√
statement “It is not the case that 2 is irrational,” which says
√
that 2 is rational. We will show that assuming that ¬p is true
leads to a contradiction.
√ √
If 2 is rational, there exist integers a and b with 2 = a/b,
where b ̸= 0 and a and b have no common factors.
38 / 45
Chapter 1

Cont’d
√
Because 2 = a/b, when both sides of this equation are squared,
a2
it follows that; 2 = b2
, hence 2b 2 = a2
By the definition of an even integer it follows that a2 is even, so a
must also be even. Furthermore, because a is even, by the
definition of an even integer, a = 2c for some integer c.
Thus, 2b 2 = 4c 2
Dividing both sides of this equation by 2 gives; b 2 = 2c 2
By the definition of even, this means that b 2 is even. Again using
the fact that if the square of an integer is even, then the integer
itself must be even, we conclude that b must be even as well.
39 / 45
Chapter 1

Cont’d

We have now shown that the assumption of ¬p leads to the

√
equation 2 = a/b, where a and b have no common factors, but
both a and b are even, that is, 2 divides both a and b. Note that
√
the statement that 2 = a/b, where a and b have no common
factors, means, in particular, that 2 does not divide both a and b.
Because our assumption of ¬p leads to the contradiction that 2
divides both a and b and 2 does not divide both a and b, ¬p must
√
be false. That is, the statement p, “ 2 is irrational,” is true.
√
We have proved that 2 is irrational.

40 / 45
Chapter 1

Mathematical Induction

PRINCIPLE OF MATHEMATICAL INDUCTION

To prove that P(n) is true for all positive integers n, where P(n) is
a propositional function, we complete two steps:
1 BASIC STEP: We verify that P(1) is true.
2 INDUCTIVE STEP: We show that the conditional statement
P(k) → P(k + 1) is true for all positive integers k.

41 / 45
Chapter 1

Cont’d

Method of proof by Mathematical Induction.

Consider a statement of the form, “For every integer n ≥ a, a
property P(n) is true.”
To prove such a statement, perform the following two steps:
1 (basis step): Show that P(a) is true.
2 (inductive step): Show that for every integer k ≥ a, if P(k) is
true then P(k+1) is true. To perform this step,
suppose that P(k) is true, where k is any particular but
arbitrarily chosen integer with k ≥ a
Then;
show that P(k+1) is true. 42 / 45
Chapter 1

Cont’d

Examples:

Use mathematical induction to prove that

n(n+1)
1 + 2 + ··· + n = 2 for every integer n ≥ 1
Proof:
n(n+1)
Let P(n) = 1 + 2 + · · · + n = 2

Show that P(1) is true:

1(1+1)
To establish P(1), we must show that 1 = 2
1(1+1)
By solving the RHS, we have 2 = 1 also.
Hence, P(1) = 1

43 / 45
Chapter 1

Cont’d

Show that for every integer k ≥ 1, if P(k) is true then P(k+1) is

also true:
k(k+1)
P(k) = 1 + 2 + · · · + k = 2

We have to show that;

(k+1)(k+2)
P(k + 1) = 1 + 2 + · · · + (k + 1) = 2 is true
The left-hand side of P(k+1) is 1 + 2 + · · · + (k + 1), we have;

k(k+1)
1 + 2 + · · · + k + (k + 1) = 2 + (k + 1)
k(k+1) 2(k+1) k 2 +k k 2 +3k+2
2 + 2 = 2 + 2k+2
2 = 2

44 / 45
Chapter 1

Cont’d

And the right-hand side of P(k+1) is

(k+1)(k+2) k 2 +3k+2
2 = 2

Thus the two sides of P(k+1) are equal to the same quantity and
so they are equal to each other.
Therefore, the equation P(k+1) is true. Hence the proof.

45 / 45