Predicate Logic:
Logical Consequence
Alice Gao
Lecture 15
CS 245 Logic and Computation Fall 2019 1 / 12
Outline
The Learning Goals
Definition of Logical Consequence
Proving/Disproving a Logical Consequence
Revisiting the Learning Goals
CS 245 Logic and Computation Fall 2019 2 / 12
Learning goals
By the end of this lecture, you should be able to:
▶ Define logical consequence for predicate logic.
▶ Prove that a logical consequence holds.
▶ Prove that a logical consequence does not hold.
CS 245 Logic and Computation Fall 2019 3 / 12
Definition of Logical Consequence
Define the symbols.
▶ Σ is a set of predicate formulas.
▶ 𝐴 is a predicate formula.
Σ⊨𝐴
(Σ logically implies 𝐴)
(𝐴 is a logical consequence of Σ)
iff for every valuation 𝑣, if Σ𝑣 = 1, then 𝐴𝑣 = 1.
CS 245 Logic and Computation Fall 2019 4 / 12
Prove a logical consequence
Consider the logical consequence Σ ⊨ 𝐴.
To prove that the logical consequence holds, we need to consider
(A) Every valuation 𝑣 such that Σ𝑣 = 1.
(B) Every valuation 𝑣 such that Σ𝑣 = 0.
(C) One valuation 𝑣 such that Σ𝑣 = 1.
(D) One valuation 𝑣 such that Σ𝑣 = 0.
CS 245 Logic and Computation Fall 2019 5 / 12
Disprove a logical consequence
Consider the logical consequence Σ ⊨ 𝐴.
To prove that the logical consequence does NOT hold, we need to
consider
(A) Every valuation 𝑣 such that Σ𝑣 = 1 and 𝐴𝑣 = 1.
(B) Every valuation 𝑣 such that Σ𝑣 = 1 and 𝐴𝑣 = 0.
(C) One valuation 𝑣 such that Σ𝑣 = 1 and 𝐴𝑣 = 1.
(D) One valuation 𝑣 such that Σ𝑣 = 1 and 𝐴𝑣 = 0.
CS 245 Logic and Computation Fall 2019 6 / 12
Example: Prove/Disprove a logical consequence
Consider the logical consequence below.
∀𝑥 ¬𝐴(𝑥) ⊨ ¬(∃𝑥 𝐴(𝑥)).
If the logical consequence holds, prove it.
If it does not hold, provide a counterexample.
Answer: This logical consequence holds.
Proof: We prove this by contradiction. Assume that there exists a
valuation such that (∀𝑥¬𝐴(𝑥))𝑣 = 1 and (¬∃𝑥𝐴(𝑥))𝑣 = 0. Form
𝐴(𝑢) from 𝐴(𝑥), 𝑢 not occurring in 𝐴(𝑥).
By (∀𝑥¬𝐴(𝑥))𝑣 = 1, we obtain (¬𝐴(𝑢))𝑣(𝑢/𝛼) = 1 for every
𝛼 ∈ 𝐷. Therefore, 𝐴(𝑢)𝑣(𝑢/𝛼) = 0 for every 𝛼 ∈ 𝐷. (1)
By (¬∃𝑥𝐴(𝑥))𝑣 = 0, we obtain (∃𝑥𝐴(𝑥))𝑣 = 1. Thus, there exists
𝛽 ∈ 𝐷 such that 𝐴(𝑢)𝑣(𝑢/𝛽) = 1, which contradicts (1).
Hence, ∀𝑥¬𝐴(𝑥) ⊨ ¬∃𝑥𝐴(𝑥). QED
CS 245 Logic and Computation Fall 2019 7 / 12
Example: Prove/Disprove a logical consequence
Consider the logical consequence below.
∀𝑥(𝐴(𝑥) → 𝐵(𝑥)) ⊨ ∀𝑥𝐴(𝑥) → ∀𝑥𝐵(𝑥)
If the logical consequence holds, prove it.
If it does not hold, provide a counterexample.
Answer: This logical consequence holds.
Proof: We prove this by contradiction. Assume that there exists a
valuation such that (∀𝑥(𝐴(𝑥) → 𝐵(𝑥)))𝑣 = 1 and
(∀𝑥𝐴(𝑥) → ∀𝑥𝐵(𝑥))𝑣 = 0. By (∀𝑥𝐴(𝑥) → ∀𝑥𝐵(𝑥))𝑣 = 0,
(∀𝑥𝐴(𝑥))𝑣 = 1 and (∀𝑥𝐵(𝑥))𝑣 = 0. Form 𝐴(𝑢) and 𝐵(𝑢), 𝑢 not
occurring in 𝐴(𝑥) or in 𝐵(𝑥). By (∀𝑥𝐴(𝑥))𝑣 = 1, 𝐴(𝑢)𝑣(𝑢/𝛼) = 1
for every 𝛼 ∈ 𝐷. (1) By (∀𝑥𝐵(𝑥))𝑣 = 0, 𝐵(𝑢)𝑣(𝑢/𝛼) = 0 for every
𝛼 ∈ 𝐷. (2) By (∀𝑥(𝐴(𝑥) → 𝐵(𝑥)))𝑣 = 1,
(𝐴(𝑢) → 𝐵(𝑢))𝑣(𝑢/𝛼) = 1 for every 𝛼 ∈ 𝐷. (3) By (1) and (3),
we have that 𝐵(𝑢)𝑣(𝑢/𝛼) = 1 for every 𝛼 ∈ 𝐷, which contradicts
(2). Hence, the logical consequence holds. QED
CS 245 Logic and Computation Fall 2019 8 / 12
Example: Prove/Disprove a logical consequence
Consider the logical consequence below.
∀𝑥𝐴(𝑥) → ∀𝑥𝐵(𝑥) ⊨ ∀𝑥(𝐴(𝑥) → 𝐵(𝑥))
If the logical consequence holds, prove it.
If it does not hold, provide a counterexample.
Answer: This logical consequence does not hold.
Consider the valuation 𝑣: 𝐷 = {1, 2}. 𝐴𝑣 = {1}. 𝐵𝑣 = ∅. Form
𝐴(𝑢) and 𝐵(𝑢) for 𝑢 not occurring in 𝐴(𝑥) and 𝐵(𝑥).
Since 2 ∉ 𝐴𝑣 , 𝐴(𝑢)𝑣(𝑢/2) = 0. Thus, (∀𝑥𝐴(𝑥))𝑣 = 0 and
(∀𝑥𝐴(𝑥) → ∀𝑥𝐵(𝑥))𝑣 = 1.
Since 1 ∈ 𝐴𝑣 and 1 ∉ 𝐵𝑣 , 𝐴(𝑢)𝑣(𝑢/1) = 1 and 𝐵(𝑢)𝑣(𝑢/1) = 0.
Thus, (𝐴(𝑢) → 𝐵(𝑢))𝑣(𝑢/1) = 0. Therefore,
(∀𝑥(𝐴(𝑥) → 𝐵(𝑥)))𝑣 = 0.
Thus, the logical consequence does not hold. QED
CS 245 Logic and Computation Fall 2019 9 / 12
Example: Prove/Disprove the logical consequence
Prove the following
∃𝑥(𝐴(𝑥) ∧ 𝐵(𝑥)) ⊨ ∃𝑥𝐴(𝑥) ∧ ∃𝑥𝐵(𝑥).
We prove this by contradiction. Assume that there exists a
valuation 𝑣 such that (∃𝑥(𝐴(𝑥) ∧ 𝐵(𝑥)))𝑣 = 1 and
(∃𝑥𝐴(𝑥) ∧ ∃𝑥𝐵(𝑥))𝑣 = 0.
Form 𝐴(𝑢) and 𝐵(𝑢) for 𝑢 not occurring in 𝐴(𝑥) and 𝐵(𝑥).
By (∃𝑥(𝐴(𝑥) ∧ 𝐵(𝑥)))𝑣 = 1, (𝐴(𝑢) ∧ 𝐵(𝑢))𝑣(𝑢/𝛼) = 1 for a
particular 𝛼 ∈ 𝐷. (1)
By (∃𝑥𝐴(𝑥) ∧ ∃𝑥𝐵(𝑥))𝑣 = 0, (∃𝑥𝐴(𝑥))𝑣 = 0 and (∃𝑥𝐵(𝑥))𝑣 = 0.
By (∃𝑥𝐴(𝑥))𝑣 = 0, 𝐴(𝑢)𝑣(𝑢/𝛼) = 0 for every 𝛼 ∈ 𝐷. By
(∃𝑥𝐵(𝑥))𝑣 = 0, 𝐵(𝑢)𝑣(𝑢/𝛼) = 0 for every 𝛼 ∈ 𝐷. Therefore, for
every 𝛼 ∈ 𝐷, (𝐴(𝑢) ∧ 𝐵(𝑢))𝑣(𝑢/𝛼) = 0, which contradicts (1).
QED
CS 245 Logic and Computation Fall 2019 10 / 12
Example: Prove/Disprove the logical consequence
Prove the following
∃𝑥𝐴(𝑥) ∧ ∃𝑥𝐵(𝑥) ⊭ ∃𝑥(𝐴(𝑥) ∧ 𝐵(𝑥)).
Consider the valuation 𝑣: 𝐷 = {1, 2}. 𝐴𝑣 = {1}. 𝐵𝑣 = {2}. Form
𝐴(𝑢) and 𝐵(𝑢) for 𝑢 not occurring in 𝐴(𝑥) and 𝐵(𝑥).
Since 1 ∈ 𝐴𝑣 , 𝐴(𝑢)𝑣(𝑢/1) = 1. Thus, (∃𝑥𝐴(𝑥))𝑣 = 1. Since
2 ∈ 𝐵𝑣 , 𝐵(𝑢)𝑣(𝑢/2) = 1. Thus, (∃𝑥𝐵(𝑥))𝑣 = 1. Therefore,
(∃𝑥𝐴(𝑥) ∧ ∃𝑥𝐵(𝑥))𝑣 = 1.
Since 1 ∉ 𝐵𝑣 , (𝐴(𝑢) ∧ 𝐵(𝑢))𝑣(𝑢/1) = 0. Since 2 ∉ 𝐴𝑣 ,
(𝐴(𝑢) ∧ 𝐵(𝑢))𝑣(𝑢/2) = 0. Therefore, (∃𝑥(𝐴(𝑥) ∧ 𝐵(𝑥))𝑣 = 0.
CS 245 Logic and Computation Fall 2019 11 / 12
Revisiting the learning goals
By the end of this lecture, you should be able to:
▶ Define logical consequence for predicate logic.
▶ Prove that a logical consequence holds.
▶ Prove that a logical consequence does not hold.
CS 245 Logic and Computation Fall 2019 12 / 12
