Discrete Mathematics and Its Applications

Kenneth H. Rosen

Chapter 1: The Foundations:

Logic and Proofs
1.1 Propositional Logic
Introduction
 A proposition is a declarative sentence (a
sentence that declares a fact) that is either
true or false, but not both.
 Are the following sentences propositions?
Toronto is the capital of Canada. (Yes)
Read this carefully. (No)
1+2=3 (Yes)
x+1=2 (No)
What time is it? (No)

2
1.1 Propositional Logic

 Propositional Logic – the area of logic that

deals with propositions
 Propositional Variables – variables that
represent propositions: p, q, r, s
E.g. Proposition p – “Today is Friday.”
 Truth values – T, F

3
1.1 Propositional Logic
DEFINITION 1
Let p be a proposition. The negation of p, denoted by ¬p, is the statement
“It is not the case that p.”
The proposition ¬p is read “not p.” The truth value of the negation of p, ¬p
is the opposite of the truth value of p.

 Examples
 Find the negation of the proposition “Today is Friday.” and
express this in simple English.
Solution: The negation is “It is not the case that today is Friday.”
In simple English, “Today is not Friday.” or “It is not
Friday today.”
 Find the negation of the proposition “At least 10 inches of rain
fell today The
Solution: in Miami.”
negationand
is “Itexpress this
is not the in simple
case English.
that at least 10 inches
of rain fell today in Miami.”
4
In simple English, “Less than 10 inches of rain fell today in
Miami.”
1.1 Propositional Logic
 Note: Always assume fixed times, fixed places, and particular people
unless otherwise noted.
 Truth table: The Truth Table for the
Negation of a Proposition.
p ¬p
T F
F T

 Logical operators are used to form new propositions from two or more
existing propositions. The logical operators are also called
connectives.

5
1.1 Propositional Logic
DEFINITION 2
Let p and q be propositions. The conjunction of p and q, denoted by p
Λ q, is the proposition “p and q”. The conjunction p Λ q is true when
both p and q are true and is false otherwise.

 Examples
 Find the conjunction of the propositions p and q where p is the
proposition “Today is Friday.” and q is the proposition “It is
raining today.”, and the truth value of the conjunction.
Solution: The conjunction is the proposition “Today is Friday and it
is raining today.” The proposition is true on rainy Fridays.

6
1.1 Propositional Logic
DEFINITION 3
Let p and q be propositions. The disjunction of p and q, denoted by p ν
q, is the proposition “p or q”. The conjunction p ν q is false when both
p and q are false and is true otherwise.

 Note:
inclusive or : The disjunction is true when at least one of the two
propositions is true.
 E.g. “Students who have taken calculus or computer science can take
this class.” – those who take one or both classes.
exclusive or : The disjunction is true only when one of the
proposition is true.
 E.g. “Students who have taken calculus or computer science, but not
both, can take this class.” – only those who take one of them.
 Definition 3 uses inclusive or.

7
1.1 Propositional Logic
DEFINITION 4
Let p and q be propositions. The exclusive or of p and q, denoted by p  q,
is the proposition that is true when exactly one of p and q is true and is
false otherwise. 

The Truth Table for The Truth Table for The Truth Table for the
the Conjunction of the Disjunction of Exclusive Or (XOR) of
Two Propositions. Two Propositions. Two Propositions.
p q pΛq p q pνq p q p q
T T T T T T T T F
T F F T F T T F T
F T F F T T F T T
F F F F F F F F F
8
1.1 Propositional Logic
Conditional Statements
DEFINITION 5
Let p and q be propositions. The conditional statement p → q, is the
proposition “if p, then q.” The conditional statement is false when p is
true and q is false, and true otherwise. In the conditional
 statement p
→ q, p is called the hypothesis (or antecedent or premise) and q is
called the conclusion (or consequence).
 A conditional statement is also called an implication.
 Example: “If I am elected, then I will lower taxes.” p→q
implication:
elected, lower taxes. T T |T
not elected, lower taxes. F T |T
not elected, not lower taxes. F F |T
elected, not lower taxes. T F |F

9
1.1 Propositional Logic
 Example:
 Let p be the statement “Maria learns discrete mathematics.” and
q the statement “Maria will find a good job.” Express the
statement p → q as a statement in English.
Solution: Any of the following -
“If Maria learns discrete mathematics, then she will find a
good job.
“Maria will find a good job when she learns discrete
mathematics.”
“For Maria to get a good job, it is sufficient for her to learn
discrete mathematics.”
“Maria will find a good job unless she does not learn
discrete mathematics.”

10
1.1 Propositional Logic
 Other conditional statements:
 Converse of p → q : q → p
 Contrapositive of p → q : ¬ q → ¬ p
 Inverse of p → q : ¬ p → ¬ q

11
1.1 Propositional Logic
DEFINITION 6
Let p and q be propositions. The biconditional statement 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.

 p ↔ q has the same truth value as (p → q) Λ (q → p)

 “if and only if” can be expressed by “iff”
 Example:
 Let p be the statement “You can take the flight” and let q be the
statement “You buy a ticket.” Then p ↔ q is the statement
“You can take the flight if and only if you buy a ticket.”
Implication:
If you buy a ticket you can take the flight.
If you don’t buy a ticket you cannot take the flight.
12
1.1 Propositional Logic

The Truth Table for the

Biconditional p ↔ q.
p q p↔ q
T T T
T F F
F T F
F F T

13
1.1 Propositional Logic
Truth Tables of Compound Propositions
 We can use connectives to build up complicated compound
propositions involving any number of propositional variables, then
use truth tables to determine the truth value of these compound
propositions.
 Example: Construct the truth table of the compound proposition
(p ν ¬q) → (p Λ q).

The Truth Table of (p ν ¬q) → (p Λ q).

p q ¬q p ν ¬q pΛq (p ν ¬q) → (p Λ q)
T T F T T T
T F T T F F
F T F F F T
F F T T F F
14
1.1 Propositional Logic
Precedence of Logical Operators
 We can use parentheses to specify the order in which logical
operators in a compound proposition are to be applied.
 To reduce the number of parentheses, the precedence order is
defined for logical operators.

Precedence of Logical Operators. E.g. ¬p Λ q = (¬p ) Λ q

Operator Precedence p Λ q ν r = (p Λ q ) ν r
¬ 1 p ν q Λ r = p ν (q Λ r)
Λ 2
ν 3
→ 4
↔ 5

15
1.1 Propositional Logic
Translating English Sentences
 English (and every other human language) is often ambiguous.
Translating sentences into compound statements removes the
ambiguity.
 Example: How can this English sentence be translated into a logical
expression?
“You cannot ride the roller coaster if you are under 4 feet
tall unless you are older than 16 years old.”
Solution: Let q, r, and s represent “You can ride the roller coaster,”
“You are under 4 feet tall,” and “You are older than
16 years old.” The sentence can be translated into:
(r Λ ¬ s) → ¬q.

16
1.1 Propositional Logic
 Example: How can this English sentence be translated into a logical
expression?
“You can access the Internet from campus only if you are a
computer science major or you are not a freshman.”
Solution: Let a, c, and f represent “You can access the Internet from
campus,” “You are a computer science major,” and “You are
a freshman.” The sentence can be translated into:
a → (c ν ¬f).

17
1.1 Propositional Logic
Logic and Bit Operations
 Computers represent information using bits.
 A bit is a symbol with two possible values, 0 and 1.
 By convention, 1 represents T (true) and 0 represents F (false).
 A variable is called a Boolean variable if its value is either true or
false.
 Bit operation – replace true by 1 and false by 0 in logical
operations.

Table for the Bit Operators OR, AND, and XOR.

x y xνy x Λy x y
0 0 0 0 0
0 1 1 0 1
1 0 1 0 1
1 1 1 1 0
18
1.1 Propositional Logic
DEFINITION 7
A bit string is a sequence of zero or more bits. The length of this string
is the number of bits in the string.

 Example: Find the bitwise OR, bitwise AND, and bitwise XOR of the
bit string 01 1011 0110 and 11 0001 1101.
Solution:
01 1011 0110
11 0001 1101
-------------------
11 1011 1111 bitwise OR
01 0001 0100 bitwise AND
10 1010 1011 bitwise XOR

19
1.2 Propositional Equivalences
Introduction
DEFINITION 1
A compound proposition that is always true, no matter what the truth
values of the propositions that occurs in it, is called a tautology. A
compound proposition that is always false is called a contradiction. A
compound proposition that is neither a tautology or a contradiction is
called a contingency.

Examples of a Tautology and a Contradiction.

p ¬p p ν ¬p p Λ ¬p

T F T F
F T T F

20
1.2 Propositional Equivalences
Logical Equivalences
DEFINITION 2
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.

 Compound propositions that have the same truth values in all

possible cases are called logically equivalent.
 Example: Show that ¬p ν q and p → q are logically equivalent.

Truth Tables for ¬p ν q and 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 21
1.2 Propositional Equivalences
 In general, 2n rows are required if a compound proposition involves n
propositional variables in order to get the combination of all truth
values.
 See page 24, 25 for more logical equivalences.

22
 1.2 Propositional Equivalences
Constructing New Logical Equivalences
 Example: Show that ¬(p → q ) and p Λ ¬q are logically equivalent.
Solution:
¬(p → q ) ≡ ¬(¬p ν q) by example on slide 21
≡ ¬(¬p) Λ ¬q by the second De Morgan law
≡ p Λ ¬q by the double negation law
 Example: Show that (p Λ q) → (p ν q) is a tautology.
Solution: To show that this statement is a tautology, we will use logical
equivalences to demonstrate that it is logically equivalent to T.
(p Λ q) → (p ν q) ≡ ¬(p Λ q) ν (p ν q) by example on slide 21
≡ (¬ p ν ¬q) ν (p ν q) by the first De Morgan law
≡ (¬ p ν p) ν (¬ q ν q) by the associative and
communicative law for disjunction
≡TνT
≡T 23

 Note: The above examples can also be done using truth tables.