Lecture 3:

Propositional Equivalence
Section 1.3
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
Logical Equivalence: Examples
● 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
Example: 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
Example: Distributive Laws

This truth table shows that distributive law of disjunction over conjunction holds.

p q r q∧r p ∨ (q ∧ r ) p∨q p∨r (p ∨ q) ∧ (p ∨ r)

T T T T T T T T
T T F F T T T T
T F T F T T T T
T F F F T T T T
F T T T T T T T
F T F F F T F F
F F T F F F T F
F F F F F F F F
Predicates and Quantifiers
Section 1.4
Section Summary
● Predicates
● Variables
● Quantifiers
○ Universal Quantifier
○ Existential Quantifier
● Negating Quantifiers
○ De Morgan’s Laws for Quantifiers
● Translating English to Logic
Introducing Predicate Logic
● Predicate logic uses the following new features:
○ Variables: x, y, z
○ Predicates: P(x), M(x)
○ Quantifiers (to be covered in a few slides):
● Propositional functions are a generalization of
propositions.
○ They contain variables and a predicate, e.g., P(x)
○ Variables can be replaced by elements from their
domain .
Propositional Functions
● Propositional functions become propositions (and
have truth values) when their variables are each
replaced by a value from the domain (or bound by a
quantifier, as we will see later).
● For example, let P(x) denote “x > 0” and the domain
be the integers. Then:
○ P(-3) is false.
○ P(0) is false.
○ P(3) is true.
● Often the domain is denoted by U. So in this example U
is the integers.
Examples of Propositional
Functions
● Let “x + y = z” be denoted by R(x, y, z) and U (for all
three variables) be the integers.
Find these truth values:
R(2,-1,5) Solution: F
R(3,4,7) Solution: T
R(x, 3, z) Solution: Not a Proposition

● Now let “x - y = z” be denoted by Q(x, y, z), with U as

the integers. Find these truth values:
Q(2,-1,3) Solution: T
Q(3,4,7) Solution: F
Q(x, 3, z) Solution: Not a Proposition
Compound Expressions
● If P(x) denotes “x > 0,” find these truth values:
P(3) ∨ P(-1) Solution : T
P(3) ∧ P(-1) Solution : F
P(3) → P(-1) Solution : F
P(3) → ¬P(-1) Solution : T
● Expressions with variables are not propositions and
therefore do not have truth values. For example,
P(3) ∧ P(y)
P(x) → P(y)
● When used with quantifiers (to be introduced next),
these expressions (propositional functions) become
propositions.
Quantifiers Charles Peirce (1839-1914)

● We need quantifiers to express the meaning of English

words including all and some:
○ “All men are Mortal.”
○ “Some cats do not have fur.”
● The two most important quantifiers are:
○ Universal Quantifier, “For all,” symbol: ∀
○ Existential Quantifier, “There exists,” symbol: ∃
● We write as in ∀x P(x) and ∃x P(x).
● ∀x P(x) means P(x) is true for every x in the domain.
● ∃x P(x) means P(x) is true for some x in the domain.
● The quantifiers are said to bind the variable x in these
expressions.
Universal Quantifier
○ ∀x P(x) is read as “For all x, P(x)” or “For every x, P(x)”
Examples :
■ If P(x) denotes “x > 0” and U is the integers, then ∀x P(x) is
false.
■ If P(x) denotes “x > 0” and U is the positive integers, then
∀x P(x) is true.
■ If P(x) denotes “x is even” and U is the integers, then ∀x
P(x) is false.
Existential Quantifier
● ∃x P(x) is read as “For some x, P(x)”, or as “There is an
x such that P(x),” or “For at least one x, P(x).”
Examples :
■ If P(x) denotes “x > 0” and U is the integers, then ∃x P(x) is
true. It is also true if U is the positive integers.
■ If P(x) denotes “x < 0” and U is the positive integers, then
∃x P(x) is false.
■ If P(x) denotes “x is even” and U is the integers, then ∃x
P(x) is true.
Thinking about Quantifiers
● When the domain is finite, we can think of quantification as
looping through the elements of the domain.
● To evaluate ∀x P(x) loop through all x in the domain.
○ If at every step P(x) is true, then ∀x P(x) is true.
○ If at a step P(x) is false, then ∀x P(x) is false and the loop
terminates.
● To evaluate ∃x P(x) loop through all x in the domain.
○ If at some step, P(x) is true, then ∃x P(x) is true and the loop
terminates.
○ If the loop ends without finding an x for which P(x) is true, then ∃x
P(x) is false.
● Even if the domains are infinite, we can still think of the
quantifiers this fashion, but the loops will not terminate in some
cases.
Properties of Quantifiers
● The truth value of ∃x P(x) and ∀ x P(x) depend on
both the propositional function P(x) and on the
domain U.
● Examples :
○ If U is the positive integers and P(x) is the statement
“x < 2”, then ∃x P(x) is true, but ∀x P(x) is false .
○ If U is the negative integers and P(x) is the statement
“x < 2”, then both ∃x P(x) and ∀x P(x) are true .
○ If U consists of 3, 4, and 5, and P(x) is the statement
“x > 2”, then both ∃x P(x) and ∀x P(x) are true .
○ But if P(x) is the statement “x < 2”, then both ∃x P(x)
and ∀ x P(x) are false .
Precedence of Quantifiers
● The quantifiers ∀ and ∃ have higher precedence than
all the logical operators.
● For example, ∀x P(x) ∨ Q(x) means (∀x P(x))∨ Q(x)
● ∀x (P(x) ∨ Q(x)) means something different.
● Unfortunately, often people write ∀x P(x) ∨ Q(x) when
they mean ∀x (P(x) ∨ Q(x)).
Translating from English to Logic
Example 1 : Translate the following sentence into
predicate logic: “Every student in this class has taken a
course in Java .”
Solution :
First decide on the domain U.
Solution 1 : If U is all students in this class, define a
propositional function J(x) denoting “x has taken a
course in Java” and translate as ∀x J(x).
Solution 2 : But if U is all people, also define a
propositional function S(x) denoting “x is a student in
this class” and translate as ∀x (S(x)→ J(x)).
∀x (S(x) ∧ J(x)) is not correct. What does it mean?
Translating from English to Logic
Example 2 : Translate the following sentence into
predicate logic: “Some student in this class has taken a
course in Java .”
Solution :
First decide on the domain U.
Solution 1 : If U is all students in this class, translate as
∃x J(x)
Solution 2 : But if U is all people, then translate as
∃x (S(x) ∧ J(x))
∃x (S(x)→ J(x)) is not correct. What does it mean?
Equivalences in Predicate Logic
● Statements involving predicates and quantifiers are
logically equivalent if and only if they have the same
truth value
○ for every predicate substituted into these statements and
○ for every domain of discourse used for the variables in
the expressions.
● The notation S ≡T indicates that S and T are logically
equivalent.
● Example : ∀x ¬¬S(x) ≡ ∀x S(x)
Thinking about Quantifiers as
Conjunctions and Disjunctions
● If the domain is finite, a universally quantified proposition
is equivalent to a conjunction of propositions without
quantifiers and an existentially quantified proposition is
equivalent to a disjunction of propositions without
quantifiers.
● If U consists of the integers 1,2, and 3:

● Even if the domains are infinite, you can still think of the
quantifiers in this fashion, but the equivalent expressions
without quantifiers will be infinitely long.
Negating Quantified Expressions
● Consider ∀x J(x)
“Every student in your class has taken a course in Java.”
Here J(x) is “x has taken a course in Java” and
the domain is students in your class.
● Negating the original statement gives “It is not the case
that every student in your class has taken Java.” This
implies that “There is a student in your class who has
not taken Java.”
Symbolically ¬∀x J(x) and ∃x ¬J(x) are equivalent
Negating Quantified Expressions
(continued)
● Now Consider ∃ x J(x)
“There is a student in this class who has taken a course in
Java.”
Where J(x) is “x has taken a course in Java.”
● Negating the original statement gives “It is not the case
that there is a student in this class who has taken Java.”
This implies that “Every student in this class has not
taken Java”
Symbolically ¬∃x J(x) and ∀x ¬J(x) are equivalent
De Morgan’s Laws for Quantifiers
● The rules for negating quantifiers are:

● The reasoning in the table shows that:

Translation from English to Logic
Examples :
1. “Some student in this class has visited Mexico.”
Solution : Let M(x) denote “x has visited Mexico” and S(x)
denote “x is a student in this class,” and U be all
people.
∃x (S(x) ∧ M(x))
2. “Every student in this class has visited Canada or
Mexico.”
Solution : Add C(x) denoting “x has visited Canada.”
∀x (S(x)→ (M(x)∨C(x)))
Some Translating from English into
Logical Expressions
● U = {fast, slow, turning}
F(x): x is fast
S(x): x is slow
T(x): x is turning
Translate “Everything is fast.”

Solution: ∀x F(x)
Translation (cont)
● U = {fast, slow, turning}
F(x): x is fast
S(x): x is slow
T(x): x is turning
“Nothing is slow.”

Solution: ¬∃x S(x) What is this equivalent to?

Solution: ∀x ¬ S(x)
Translation (cont)
● U = {fast, slow, turning}
F(x): x is fast
S(x): x is slow
T(x): x is turning
“All fast things are slow.”

Solution: ∀x (F(x)→ S(x))

Equivalent to: For all things, fast implies slow.
Translation (cont)
● U = {fast, slow, turning}
F(x): x is fast
S(x): x is slow
T(x): x is turning
“Some fast things are turning.”

Solution: ∃x (F(x) ∧ T(x))

Equivalent to: Some things are fast and turning
Translation (cont)
● U = {fast, slow, turning}
F(x): x is fast
S(x): x is slow
T(x): x is turning
“No slow thing is a turning.”

Solution: ¬∃x (S(x) ∧ T(x)) What is this equivalent to?

Solution: ∀x (¬S(x) ∨ ¬T(x))
Translation (cont)
● U = {fast, slow, turning}
F(x): x is fast
S(x): x is slow
T(x): x is turning
“If anything fast is a slow then it is also a turning.”

Solution: ∀x ((F(x) ∧ S(x))→ T(x))

 Charles Lutwidge Dodgson
Lewis Carroll Example (AKA Lewis Caroll)
(1832-1898)
● The first two are called premises and the third is called the
conclusion.
○ “All lions are fierce.”
○ “Some lions do not drink coffee.”
○ “Some fierce creatures do not drink coffee.”
● Here is one way to translate these statements to predicate
logic. Let P(x), Q(x), and R(x) be the propositional functions “x
is a lion,” “x is fierce,” and “x drinks coffee,” respectively.
○ ∀x (P(x)→ Q(x))
○ ∃x (P(x) ∧ ¬R(x))
○ ∃x (Q(x) ∧ ¬R(x))
● Later we will see how to prove that the conclusion follows from
the premises.