The Foundations: Logic

and Proofs
Chapter 1, Part I: Propositional Logic

With Question/Answer Animations

Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education.
Chapter Summary
Propositional Logic
The Language of Propositions
Applications
Logical Equivalences
Predicate Logic
The Language of Quantifiers
Logical Equivalences
Nested Quantifiers
Propositional Logic Summary
The Language of Propositions
Connectives
Truth Values
Truth Tables
Applications
Translating English Sentences
System Specifications
Logic Puzzles
Logical Equivalences
Showing Equivalence
Propositional Logic
Section 1.1
Section Summary
Propositions
Connectives
Negation
Conjunction
Disjunction
Implication; contrapositive, inverse, converse
Biconditional
Truth Tables
Propositions
A proposition is a declarative sentence (that is, a
sentence that declares a fact) that is either true
or false.
The basic building blocks of logic.
Which one of these is a Proposition ?
a) The Moon is made of green cheese.
b) What time is it?
c) Hargeisa is the capital of Somalia.
d) x+y=z

1+0=1
e) Toronto is the capital of Canada.
f)
g) 0+0=2
h) Sit down!
Propositions
Examples of propositions:
a) The Moon is made of green cheese.
b) Kismayo is the capital of Somalia.

d) 1 + 0 = 1
c) Toronto is the capital of Canada.

e) 0 + 0 = 2
Examples that are not propositions.
a) Sit down!
b) What time is it?
c) x+1=2
d) x + y = z
Propositional Logic
Constructing Propositions
We use letters to denote propositional variables (or
statement variables), that is, variables that
represent propositions, just as letters are used to
denote numerical variables.
 Propositional Variables: p, q, r, s, …
 The proposition that is always true is denoted by T and
the proposition that is always false is denoted by F.
Many mathematical statements are constructed
by combining one or more propositions. New
propositions, called compound propositions,
are formed from existing propositions using
logical operators.
Compound Propositions
Compound Propositions; constructed from
logical connectives and other propositions
Negation ¬ ¬p
 Conjunction ∧ p∧q


 Disjunction ∨ p∨q
Implication → p→q
Biconditional ↔ p↔q



Negation (not) ¬p
The negation of a proposition p is denoted by ¬p.
Example: If p denotes “The earth is round.”, then
¬p denotes “It is not the case that the earth is

B. p=The window is closed. ¬p=the window isn’t

round,” or more simply “The earth is not round.”

closed
A. p= Today is Monday. ¬p = Today is not
Monday

p
and has this truth table:
¬p
Combinations Connectives
T F
F T
The negation of a proposition can also be
considered the result of the operation of the
negation operator on a proposition.
The negation operator constructs a new
proposition from a single existing proposition.
We will now introduce the logical operators
that are used to form new propositions from
two or more existing propositions.
These logical operators are also called
connectives.
Truth Tables
Construction of a truth table:
Rows: Each row of a truth table gives us one
possibility for the truth values of our
propositions. Since each proposition has two
possible truth value, true or false, we will
have 2 rows for each proposition (or 2^n
where n = # of propositions)
p
Combinations
p
¬Connectives P Q
Combinations p∧q
Connectives

T F
T T T
F T
T F F
F T F
F F F
Conjunction (AND) ∧
The conjunction of propositions p and q is
denoted by p ∧ q
Example: If p denotes “I am at home.” and
q denotes “It is raining.” then p ∧q denotes
“I am at home and it is raining.”
The conjunction p ∧ q is true when both p
and q are true and is false otherwise. and has
p
this truth table: q p∧q
T T T
T F F
F T F
F F F
Disjunction (OR) ∨
The disjunction of propositions p and q
denoted by p ∨q
is

Example: If p denotes “I am at home.” and

q denotes “It is raining.” then p ∨q denotes
“I am at home or it is raining.”
The disjunction p ∨ q is false when both p
and q are false and is true otherwise. e.g;
Warsame &/ Ayaan.
p
disjunction p ∨q
q truth table:
has this
T T T
T F T
F T T
F F F
The Connective Or in English
In English “or” has two distinct meanings.
 “Inclusive Or” - In the sentence “Students who have taken
CS202 or Math120 may take this class,” we assume that

have taken both. This is the meaning of disjunction. For p ∨q

students need to have taken one of the prerequisites, but may

to be true, either one or both of p and q must be true.

 “Exclusive Or” - When reading the sentence “Soup or salad
comes with this meal,” we do not expect to be able to get both

⊕ q , one of p and q must be true, but not both. The truth table
soup and salad. This is the meaning of Exclusive Or (Xor). In p

for ⊕ is:p q p ⊕q
T T F
T F T
F T T
F F F
 Discussion
For each of the following, determine
whether inclusive OR or exclusive OR is
intended.
1. Coffee or Tea comes with dinner
2. A password must have at least 3 digits or be
at least 8 characters long
3. To take discrete mathematics, you must
have taken calculus or engineering
mathematics
4. you can pay using Somali shilling or dollars
Implication (IF, THEN) p →q
 If p and q are propositions, then p →q is a conditional
statement or implication which is read as “if p, then q ”
 Example: If p denotes “It is a holiday.” and q
denotes “The store is closed.” then p →q denotes “If

 In p →q , p is the hypothesis (antecedent or premise)

the store is closed then it is a holiday.”

and q is the conclusion (or consequence). and has

p q p →q
this truth table:
T T T
T F F
F T T
F F T
The statement p → q is called a conditional
statement because p → q asserts that q is true
on the condition that p holds. A conditional
statement is also called an implication
Understanding Implication
One way to view the logical conditional is to think
of an obligation or contract.
“If I am elected, then I will lower taxes.”
“If you get 100% on the final, then you will get
an A.”
If the politician is elected and does not lower taxes,
then the voters can say that he or she has broken

the professor. This corresponds to the case where p

the campaign pledge. Something similar holds for

is true and q is false.

CONVERSE, CONTRAPOSITIVE, AND
INVERSE
We can form some new conditional statements
starting with a conditional statement p → q.
In particular, there are three related conditional
statements that occur so often that they have special
names.
The proposition q → p is called the converse of p → q.
 The contrapositive of p → q is the proposition ￢ q →
￢ p.
The proposition ￢ p → ￢ q is called the inverse of p →
q.
We will see that of these three conditional statements
formed from p → q, only the contrapositive always has
the same truth value as p → q.
CONVERSE, CONTRAPOSITIVE, AND INVERSE
From our implication, p → q , we can
construct 3 new conditional statements.
Converse: q → p
Inverse: ￢ p → ￢ q.
Contrapositive: ￢ q → ￢ p.
For instance: It’s raining it’s sufficient
condition for me not going to the town.
IF it’s raining, then, I won’t go to the town
Different Ways of Expressing p →q
if p, then q p implies q
if p, q p only if q
q unless ¬p q when p
q if p
q whenever p p is sufficient for q
q follows from p q is necessary for p

a necessary condition for p is q

a sufficient condition for q is p
 Discussion
Determine whether each of these conditional statements
is true or false
 If 1+1 = 3, then people can fly

 If 1+1 = 2, then people can fly

 If monkeys can fly, then 1+1 = 3

 If 1+1 = 2, then 2+2 = 5

 If Mogadishu is the capital of Somalia, then Nairobi is the capital

of Kenya
Biconditional (IF AND ONLY IF) p ↔q
 If p and q are propositions, then we can form the
biconditional proposition p ↔q , read as “p if and only if
q .” The biconditional p ↔q denotes the proposition

 If p denotes “I am at home.” and q denotes “It is

with this truth table:

raining.” then p ↔q denotes “I am at home if and

only if it is raining.”

p q p ↔q
T T T
T F F
F T F
F F T
Cont.…
p ↔q = (p →q)^(q →p)

p q p →q q →p (p →q)^(q p ↔q
→p)
T T T T T T
T F F T F F
F T T F F F
F F T T T T
Expressing the Biconditional
Some alternative ways “p if and only if q” is
expressed in English:

 p is necessary and sufficient for q

 if p then q , and conversely
 p if q
Truth Tables For Compound Propositions
Construction of a truth table:
Rows
 Need a row for every possible combination of
truth values for the atomic propositions.
Columns
Need a column for the compound proposition
(usually at far right)
Need a column for the truth value of each
expression that occurs in the compound
proposition as it is built up.
Precedence of Logical Operators
Operator Precedence
 1
 2
 3
 4
 5

p q  r is equivalent to (p q)

If the intended meaning is p (q 

 r

r )
then parentheses must be used.
Example Truth Table
Construct a truth table for
Solution
p q r r pq pq→
r
T T T F T F
T T F T T T
T F T F T F
T F F T T T
F T T F T F
F T F T T T
F F T F F T
F F F T F T
Cont.…
Class Work (1)
Construct the Truth table for the following
compound Proposition.
(p ∨ q) ∧ ( ￢ r)
Cont.…
Class Work (2)
Construct the Truth table for the following
compound Proposition.
(p → q) ↔ (¬q → ¬p)
Homework
Q1 : Construct the Truth table for the following
compound Proposition.
P → ￢q ∧ ￢ p ↔ ￢ p
Homework
Q2 :
Logical Puzzles (1)
In an island, there are two kinds of
inhabitants, knights, who always tell the
truth, and their opposites, knaves, who
always lie. You encounter two people A and
B. What are A and B if A says “B is a knight”
and B says “The two of us are opposite
types?”
Logical Puzzles (solution)
Logical Puzzles (solution)
Equivalent Propositions
Two propositions are equivalent if they
always have the same truth value.
Example: Show using a truth table that the
p→q conditional is equivalent to the
contrapositive ￢ q → ￢ p.
Solution:
p q ¬p ¬q p →q ¬q → ¬
p
T T F F T T
T F F T F F
F T T F T T
F F T T T T
Using a Truth Table to Show Non-
Equivalence

neither the converse (q → p ) nor inverse

Example: Show using truth tables that

(¬ p →¬ q) of an implication are not

equivalent to the implication.
Solution:

p q ¬p ¬q p →q ¬ p →¬ q→p
q
T T F F T T T
T F F T F T T
F T T F T F F
F F T T T T T
Propositional
Equivalences
Section 1.3
Section Summary
Tautologies, Contradictions, and Contingencies.
Logical Equivalence
Important Logical Equivalences
Showing Logical Equivalence
Normal Forms (optional, covered in exercises in
text)
Disjunctive Normal Form
Conjunctive Normal Form
Propositional Satisfiability
Sudoku Example
Tautologies, Contradictions, and
Contingencies
A tautology is a proposition which is always

p ∨¬p
true.
Example:
A contradiction is a proposition which is

Example: p ∧¬p
always false.

A contingency is a proposition which is

P a tautology
neither ¬p nor ap ∨¬p p ∧¬p
contradiction, such
as p T F T F
F T T F
Logically Equivalent
equivalent if p↔q is a tautology.
 Two compound propositions p and q are logically

 We write this as p⇔q or as p≡q where p and q are

Two compound propositions p and q are equivalent if and

compound propositions.

only if the columns in a truth table giving their truth

This truth table shows that ¬p ∨ q is equivalent to p → q.

values agree.

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
De Morgan’s Laws
Augustus De
Morgan
1806-
1871

This truth table shows that De Morgan’s Second Law holds.

p q ¬p ¬q (p∨q) ¬(p∨q) ¬p∧¬q

T T F F T F F
T F F T T F F
F T T F T F F
F F T T F T T
Key Logical Equivalences
Identity Laws: ,

Domination Laws: ,

Idempotent laws: ,

Double Negation Law:

Negation Laws: ,
Key Logical Equivalences (cont)
Commutative Laws: ,

Associative Laws:

Distributive Laws:

Absorption Laws:
More Logical Equivalences
Constructing New Logical Equivalences
We can show that two expressions are logically
equivalent by developing a series of logically
equivalent statements.
To prove that we produce a series of
equivalences beginning with A and ending with B.

Keep in mind that whenever a proposition

(represented by a propositional variable) occurs in
the equivalences listed earlier, it may be replaced by
an arbitrarily complex compound proposition.
Equivalence Proofs
Example: Show that
is logically equivalent to
Solution:
Equivalence Proofs
Example: Show that
is a tautology.
Solution:
Equivalence Proofs
¬(¬p ∨q) ¬q ∧ p
Exercise : Use logical equivalences to show
 Homework
• Use truth tables to verify these equivalences