The Foundations: Logic

and Proofs
Chapter 1
Propositional Logic
Section 1.1
 Propositions
A proposition is a declarative sentence that
is either true or false.

Examples of propositions:

b) 1 + 0 = 1
a) Dhaka is the capital of Bangladesh.

c) 0 + 0 = 2
Examples that are not propositions:
a) What time is it?
b) x + 1 = 2
 Propositional Logic
Constructing Propositions
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.
Compound Propositions: formed from existing
propositions using logical operators.
Negation ¬
 Conjunction ∧


 Disjunction ∨

Implication →
Bi-conditional ↔



 Compound Propositions: Negation
The negation of a proposition p is denoted by
¬p and has this truth table:

p ¬p
T F
F T

Example: If p
round.”, then ¬p
denotes “The earth is
denotes “The earth is not
round.”
 Conjunction
The conjunction of propositions p and q is
denoted by p ∧ q and has this truth table:
p q p∧q
T T T
T F F
F T F
F F F

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.”
 Disjunction
The disjunction of propositions p and q
denoted by p ∨q and has this truth table:
is

p q p ∨q
T T T
T F T
F T T
F F F

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.”
 Exclusive Or ( ⊕ )
p ⊕ q = pq’ + p’q
The truth table for ⊕ is:

p q p ⊕q
T T F
T F T
F T T
F F F
 Implication
 If p and q are propositions, then p →q is a conditional
statement or implication that is false when p is true and q

 p → q is read as “if p, then q ” and has this truth table:

is false and true otherwise.

p q p →q
T T T
T F F
F T T
F F T

 Example: If p denotes “It is winter.” and q denotes “It's

cold outside.” then p →q denotes “If it is winter then it's

 In p →q , p is the hypothesis and q is the conclusion.

cold outside.”
 Understanding Implication
Consider the following Sentence:
“If I am elected, then I will lower taxes.”

If the politician is elected and does not lower

taxes, then the voters can say that he or she
has broken the campaign pledge. Something

corresponds to the case where p is true and q

similar holds for the professor. This

is false.
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
 Converse, Contrapositive, and Inverse
From p →q we can form new conditional statements .
 q →p is the converse of p →q
 ¬q → ¬ p is the contrapositive of p →q
¬ p → ¬ q is the inverse of p →q

Example: Find the converse, inverse, and contrapositive of

“It raining is a sufficient condition for my not going to
town.”

Solution:
converse: ?
inverse: ?
contrapositive: ?
 Converse, Contrapositive, and Inverse
From p →q we can form new conditional statements

q →p is the converse of p →q
.

 ¬q → ¬ p is the contrapositive of p →q


¬ p → ¬ q is the inverse of p →q
Example: Find the converse, inverse, and
contrapositive of “It raining is a sufficient condition
for my not going to town.”
Solution:
converse: If I do not go to town, then it is raining.
inverse: If it is not raining, then I will go to town.
contrapositive: If I go to town, then it is not raining.
 Biconditional
 If p and q are propositions, then we can form the
biconditional proposition p ↔q that is true when p and q

 p ↔q is read as “p if and only if q .” Truth table:

have the same truth values and is false otherwise.

p q p ↔q
T T T
T F F
F T F
F F T

 p ↔q is true when both the implications

p → q & q → p are true.
 Expressing the Biconditional
Some alternative ways “p if and only if q” is
expressed in English:
p iff q
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.
 Truth Tables
For Compound Propositions
Construction of a truth table:
Rows
Need a row for every possible combination of
values for the atomic propositions.
Columns
Need a column for the compound proposition
Need a column for the truth value of each
expression that occurs in the compound
proposition as it is built up.
 Example Truth Table
Construct a truth table for

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
 Equivalent Propositions
Two propositions are equivalent if they
always have the same truth value.
Example: Show using a truth table that the
implication is equivalent to the
contrapositive.

p q ¬p ¬q ¬q → ¬
Solution:
p →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
Example: Show using truth tables that
neither the converse nor inverse of an
implication are not equivalent to the
implication.
p q ¬p ¬q p →q ¬ p →¬ q→p
Solution:
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
Problem
How many rows are there in a truth table
with n propositional variables?

Solution: ?
Problem
How many rows are there in a truth table
with n propositional variables?

Solution: 2n

propositional variables, we can construct 2n

Note that this means that with n

distinct (i.e., not equivalent) propositions.

 Applications of
Propositional Logic
Section 1.2
 Applications of Propositional Logic:
Summary
Translating English to Propositional Logic
System Specifications
Boolean Searching
Logic Puzzles
Logic Circuits
AI Diagnosis Method (Optional)
 Translating English Sentences
Steps to convert an English sentence to a
statement in propositional logic
Identify atomic propositions and represent
using propositional variables.
Determine appropriate logical connectives
Example: “If I go to Harry’s or to the
country, I will not go shopping.”
p: I go to Harry’s
q: I go to the country. If p or q then
r: I will go shopping. not r.
 Example
Problem: Translate the following sentence
into propositional logic:
“You can access the Internet from campus only
if you are a computer science major or you
are not a freshman.”
One Solution:
 Example
Problem: Translate the following sentence into
propositional logic:
“You can access the Internet from campus if you
are a
computer science major or you are not a freshman.”
Solution:
Let a, c, and f represent respectively “You can
access the internet from campus,” “You are a
computer
science major,” and “You are a freshman.”
(c ∨ ¬ f ) → a
 System Specifications
System and Software engineers take
requirements in English and express them in
a precise specification language based on
logic.
Example: Express in propositional logic:
“The automated reply cannot be sent when
the file system is full”
Solution: ?
 System Specifications
System and Software engineers take
requirements in English and express them in
a precise specification language based on
logic.
Example: Express in propositional logic:
“The automated reply cannot be sent when
the file system is full”
Solution: One possible solution: Let p
denote “The automated reply can be sent”

q→ ¬ p
and q denote “The file system is full.”
 Logic Puzzles
 An island has two kinds of inhabitants, knights, who always
tell the truth, and knaves, who always lie.
 You go to the island and meet A and B.
 A says “B is a knight.”
 B says “The two of us are of opposite types.”
Example: What are the types of A and B?
Solution: ?
 Logic Puzzles
 An island has two kinds of inhabitants, knights, who always
tell the truth, and knaves, who always lie.
 You go to the island and meet A and B.
 A says “B is a knight.”
 B says “The two of us are of opposite types.”

Solution: Let p and q be the statements that A is a knight

Example: What are the types of A and B?

and B is a knight, respectively. So, then p represents the

 If A is a knight, then p is true. Since knights tell the truth, q

proposition that A is a knave and q that B is a knave.

must also be true. Then (p ∧  q)∨ ( p ∧ q) would have to be

true, but it is not. So, A is not a knight and therefore p must
be true.
 If A is a knave, then B must not be a knight since knaves
always lie. So, then both p and q hold since both are knaves.
 Logic Circuits
 Electronic circuits; each input/output signal can be viewed as a 0 or 1.
 0 represents False
 1 represents True
 Complicated circuits are constructed from three basic circuits called gates.

 The inverter (NOT gate)takes an input bit and produces the negation of that bit.
 The OR gate takes two input bits and produces the value equivalent to the
disjunction of the two bits.
 The AND gate takes two input bits and produces the value equivalent to the
conjunction of the two bits.
 More complicated digital circuits can be constructed by combining these
basic circuits. For example:
Propositional
Equivalences
Section 1.3
 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 p ∨¬
nor a 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 values

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

agree.

p ¬p ¬p ∨ q p→ q

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 logically equivalent to
Solution:
Equivalence Proofs
Example: Show that
is a tautology.
Solution:
Equivalence Proofs
Example: Show that
is a tautology.
Solution: