The Foundations: Logic
and Proofs
Chapter 1, Part I: Propositional Logic
Chapter Summary
Propositional Logic
The Language of Propositions
Applications
Logical Equivalences
Predicate Logic
The Language of Quantifiers
Logical Equivalences
Nested Quantifiers
Proofs
Rules of Inference
Proof Methods
Propositional Logic Summary
The Language of Propositions
Connectives
Truth Values
Truth Tables
Applications
Translating English Sentences
Logical Equivalences
Important 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 either true or false.
Examples of propositions:
a) The Moon is made of green cheese.
b) Tokyo is the capital of Vietnam.
c) Toronto is the capital of Canada.
d) 1+0=1
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
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; constructed from logical connectives
and other propositions
Negation ¬
Conjunction ∧
Disjunction ∨
Exclusive or
Implication →
Biconditional ↔
Negation
The negation of a proposition p , denoted by ¬p is the
statement: “It is not the case that p”, and has the truth table:
p ¬p
T F
F T
Example: p : “The earth is round.”,
then ¬p : “It is not the case that the earth is round,”
or more simply “The earth is not round.”
Conjunction
The conjunction of propositions p and q, denoted by
p ∧ q , is the statement “p and q” and has this truth
table:
p q p∧q
T T T
T F F
F T F
F F F
Example: p: “I am at home.”
q: “It is raining.”
Then p ∧q : “I am at home and it is raining.”
Disjunction
The disjunction of propositions p and q, denoted by
p ∨q , is the proposition “p or q”, and has this truth
table:
p q p ∨q
T T T
T F T
F T T
F F F
Example: p: “I am at home.”
q: “It is raining.”
Then p ∨ q : “I am at home or it is raining.”
Exclusive Or
exclusive or of propositions p and q, denoted by p q , is
The
the proposition “p or q (but not both)”, and has this truth
table:
p q p ⊕q
T T F
T F T
F T T
F F F
Example: p: “I am at home.”
q: “It is raining.”
Then p q : “I am at home or it is raining but not both.”
Implication
If p and q are propositions, then p →q is a conditional statement or
implication which is read as “if p, then q ” and has this truth table:
p q p →q
T T T
T F F
F T T
F F T
Example: If p denotes “I am at home.” and q denotes “It is
raining.” then p →q denotes “If I am at home then it is raining.”
In p →q , p is the hypothesis (premise) and q is the conclusion
(or consequence).
Understanding Implication
In p →q there does not need to be any connection
between the antecedent or the consequent. The
“meaning” of p →q depends only on the truth values of p
and q.
These implications are perfectly fine, but would not be
used in ordinary English.
“If the moon is made of green cheese, then I have more
money than Bill Gates. ”
“If the moon is made of green cheese then I’m on welfare.”
“If 1 + 1 = 3, then your grandma wears combat boots.”
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
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 , read as “p if and only if q .” The biconditional
p ↔q denotes the proposition with this truth table:
p q p ↔q
T T T
T F F
F T F
F F T
If p denotes “I am at home.” and q denotes “It is raining.” then
p ↔q denotes “I am at home if and only if it is raining.”
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 iff q
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 (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.
Example Truth Table
Construct a truth table for
Example Truth Table
Construct a truth table for
p q r r pq 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
conditional is equivalent to the contrapositive.
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
Example: Show using truth tables that neither the
converse nor inverse of an implication are not
equivalent to the implication.
Solution:
p q ¬p ¬q p →q ¬ p →¬ q q→p
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?
Precedence of Logical Operators
Operator Precedence
1
2
3
4
5
p q r is equivalent to (p q) r
If the intended meaning is p (q r )
then parentheses must be used.
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
“If I go to the park or to the country, I will not go
shopping.”
p: I go to the park If p or q then not r.
q: I go to the country.
r: I will go shopping.
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.”
Solution:
Tautologies, Contradictions, and
Contingencies
A tautology is a proposition which is always true.
Example: p ∨¬p
A contradiction is a proposition which is always false.
Example: p ∧¬p
A contingency is a proposition which is neither a
tautology nor a contradiction, such as p
P ¬p p ∨¬p p ∧¬p
T F T F
F T T F
Logically Equivalent
Two compound propositions p and q are logically equivalent if p↔q
is a tautology.
We write this as p⇔q or as p≡q where p and q are compound
propositions.
Two compound propositions p and q are equivalent if and only if the
columns in a truth table giving their truth values agree.
This truth table shows that ¬p ∨ q is equivalent to 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
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:
Key terms
For next lesson
1. Tautology
2. Contradiction
3. Contingency
4. Logically equivalent
