SAMPLE QUESTIONS FOR MIDTERM EXAM

MATH1090O W22

Question 1. First show that (((p ≡ q) ∨ ⊥) → ¬(p ≡ q)) is a well-formed formula

and then give its truth table.
Solution. We can use either of “parse the string bottom-up” or “parse the string
up-down” or “formula-calculation” methods. Here is a formula-calculation.
p, q, (p ≡ q), ⊥, ¬(p ≡ q), (p ≡ q) ∨ ⊥, ((p ≡ q) ∨ ⊥) → ¬(p ≡ q))
Note that this sequence is not unique. It is correct as long as a formula is written
iff all of its subformulae are already written.
The truth table:

p q p≡q ¬(p ≡ q) (p ≡ q) ∨ ⊥ ((p ≡ q) ∨ ⊥) → ¬(p ≡ q))

t t t f t f
t f f t f t
f t f t f t
f f t f t f
□

Question 2. Prove the following statements.

(1) {A ∨ ⊥, B → C ∧ ¬A, C} is satisfiable.
(2) {A2n : n ∈ N} |=taut (A13 ∧ A24 ) → A56
Solution. (1) Every state v such that v(A) = t, v(B) = f and v(C) = t satisfies the
set, since for such v we have v(A ∨ ⊥) = v(B → C ∧ ¬A) = v(C) = t.
(2) Suppose v is a state such that v(A2n ) = t for every n. In particular, v(A56 ) =
t and therefore v((A13 ∧ A24 ) → A56 ) = t. □

Question 3. Prove the following statements.

(1) A ≡ ⊥ is tautologically equivalent to ¬A.
(2) If A, B |=taut C then |=taut A → (B → C).
Solution. (1) We have to show that A ≡ ⊥ |=taut ¬A and ¬A |=taut A ≡ ⊥.
For a state v if v(A ≡ ⊥) = t then v(A) = v(⊥) = f . Hence v(¬A) = t and
therefore A ≡ ⊥ |=taut ¬A.
For a state v if v(¬A) = t, then v(A) = f and therefore v(A) = v(⊥) which
means v(A ≡ ⊥) = t. Thus ¬A |=taut A ≡ ⊥.
(2) From A, B |=taut C it follows that if v is a state such that v(A) = v(B) = t
then v(C) = t. Now suppose v is an arbitrary state. v(A → (B → C)) = t

Date: February 2021.

1
2 SAMPLE QUESTIONS FOR MIDTERM EXAM MATH1090O W22

unless v(A) = t and v(B → C) = f and v(B → C) = t unless v(B) = t and

v(C) = f . Therefore v(A → (B → C)) = f if and only if v(A) = v(B) = t
and v(C) = f . But by our assumption if v(A) = v(B) = t then v(C) = f .
Therefore v(A → (B → C)) = t, for every state v, which means A → (B → C) is a
tautology. □

Question 4. Give Hilbert-style or Equational-style proofs for the following theo-

rems.
(1) ⊢ ¬¬p → p.
(2) (A ∧ B) ∨ ¬(A → B) ⊢ A.
Solution. (1)
¬¬p → p
⇐⇒ ⟨Leib., double negation, C-part q → p, q fresh⟩
p→p
⇐⇒ ⟨abs. thm⟩
¬p ∨ p
The last formula is an axiom, therefore the proof is complete.
(Another Solution:) By the deduction theorem it is enough to prove ¬¬p ⊢ p.
We have the theorem ⊢ ¬¬p ≡ p and therefore ¬¬p ⊢ ¬¬p ≡ p. Since ¬¬p ⊢ ¬¬p,
using equanimity we obtain ¬¬p ⊢ p.

(2) First note that since B ∨ ¬B is an axiom, we have ⊢ B ∨ ¬B ≡ ⊤ (by

redundant true).
(A ∧ B) ∨ ¬(A → B)
⇐⇒ ⟨Leib., thm, C-part (A ∧ B) ∨ ¬p, p fresh⟩
(A ∧ B) ∨ ¬(¬A ∨ B)
⇐⇒ ⟨Leib., thm, C-part (A ∧ B) ∨ p, p fresh⟩
(A ∧ B) ∨ (¬¬A ∧ ¬B)
⇐⇒ ⟨Leib., double negation, C-part (A ∧ B) ∨ (p ∧ ¬B), p fresh⟩
(A ∧ B) ∨ (A ∧ ¬B)
⇐⇒ ⟨distributivity of ∧ over ∨⟩
A ∧ (B ∨ ¬B)
⇐⇒ ⟨Leib., B ∨ ¬B ≡ ⊤ , C-part A ∧ p, p fresh⟩
A∧⊤
⇐⇒ ⟨A ∧ ⊤ ≡ A⟩
A
□

Question 5. Prove that if Γ ⊢ Ai for i ∈ {1, 2, . . . , n} then Γ ⊢ A1 ∧ A2 ∧ · · · ∧ An .

 SAMPLE QUESTIONS FOR MIDTERM EXAM MATH1090O W22 3

Solution. By n-times application of the theorem A, B ⊢ A ∧ B, we obtain that

A1 , A2 , . . . , An ⊢ A1 ∧ A2 ∧ · · · ∧ An . Then since Γ ⊢ Ai for every i = 1, 2, . . . , n, by
the transitivity of ⊢ we can conclude that Γ ⊢ A1 ∧ A2 ∧ · · · ∧ An . □

Question 4. Prove by induction on the complexity of formula that the last symbol
of any formula is never a connective.
Solution. (basis) Atomic formulae have no connectives therefore the statement
holds for atomic formulae.
(Inductive step) Suppose A is one of the formulae (¬B), (B ∨ C), (B ∧ C),
(B → C) or (B ≡ C), for some formulae B and C. In each of these cases the last
symbol is “)”, which is not a connective. Therefore by the inductive construction
of formulae the last symbol is never a connective. (We don’t even need to use the
Induction Hypothesis here) □

Question 5. Prove that if Γ ⊢ A → B and Γ ∪ {A} ⊢ ¬B then Γ ∪ {A} ⊢ ⊥.

Solution. By the deduction theorem Γ ⊢ A → B implies Γ ∪ {A} ⊢ B and by our
assumption Γ ∪ {A} ⊢ ¬B. Since Γ ∪ {A} ⊢ B and Γ ∪ {A} ⊢ ¬B, and ¬B, B ⊢ ⊥
(proved in the class), by the transitivity of ⊢ we conclude Γ ∪ {A} ⊢ ⊥. □

Question 8. Use either the soundness or the completeness (Post’s theorem) of the
propositional logic to prove ¬A ∨ (B ∧ C) |=taut (A → B) ∧ (A → C). Which one
did you use, soundness or completeness?

Solution. By the “soundness” theorem it is enough to show that ¬A ∨ (B ∧ C) ⊢

(A → B) ∧ (A → C). We have proved the absolute theorem ⊢ A → (B ∧ C) ≡
(A → B) ∧ (A → C) in the class which we can use.
¬A ∨ (B ∧ C)
⇐⇒ ⟨abs. thm⟩
A → (B ∧ C)
⇐⇒ ⟨the above abs. thm⟩
(A → B) ∧ (A → C)

This completes the proof.

(Another solution:)
(1) ¬A ∨ (B ∧ C) (hyp.)
(2) ¬A ∨ (B ∧ C) ≡ A → (B ∧ C) (abs. thm)
(3) A → (B ∧ C) ((1), (2)+ equanimity )
(4) A → (B ∧ C) ≡ (A → B) ∧ (A → C) (abs. thm)
(5) (A → B) ∧ (A → C) ((3), (4)+ equanimity )

(There are several ways to prove this.)

4 SAMPLE QUESTIONS FOR MIDTERM EXAM MATH1090O W22

Question 6. Let A denote the following string in the language of Boolean logic.
(r → ¬(r ∧ p)) → (q ≡ (r ∨ ¬q))

(a) Show that A is a formula (wff ) using the formula-calculation.

(b) What is the complexity of A?
(c) Find the value of A in the state v where v(p) = t, v(q) = f and v(r) = t.
Show your work.

Solution. (a)
p, q, r, r∧p, ¬(r∧p), r → ¬(r∧p), ¬q, (r∨¬q), q ≡ (r∨¬q), (r → ¬(r∧p)) → (q ≡ (r∨¬q))
(Note that the above formula calculation is not unique. The only rule is that we
write a formula as long as we have already written all of its subformulae.)

(b) 7

(c) We have v(r∧p) = t ⇒ v(¬(r∧p)) = f ⇒ v(r → ¬(r∧p)) = f and v(r∨¬q) =

t ⇒ v(q ≡ (r ∨ ¬q)) = f . Therefore v((r → ¬(r ∧ p)) → (q ≡ (r ∨ ¬q))) = t.
□

Question 7. Suppose A is a Boolean formula which is constructed using only the

two connectives ∨ and ∧. Let c(A) denote the complexity of A and s(A) denote the
number of subformuale of A. Prove using the induction on the complexity of the
formula A that s(A) = 2c(A) + 1.

Solution. (Basis) Suppose A is an atomic formula. The complexity of A is zero and

the only subformula of A is itself. Therefore s(A) = 2c(A) + 1 = 2 × 0 + 1 = 1.
(Inductive step) Suppose A is B ∧ C or B ∨ C, where B and C are formulae
which are constructed using only the two connectives ∧ and ∨. We have c(A) =
c(B) + c(C) + 1. By the Induction Hypothesis we have s(B) = 2c(B) + 1 and
s(C) = 2c(C) + 1. The subformulae of A are exactly itself, subformulae of B and
subformulae of C, therefore we have
s(A) = s(B) + s(C) + 1
= 2c(B) + 1 + 2c(C) + 1 + 1
= 2(c(B) + c(C) + 1) + 1
= 2c(A) + 1
□
 SAMPLE QUESTIONS FOR MIDTERM EXAM MATH1090O W22 5

Question 8. Do not use the Soundness Theorem.

(a) Decide whether each one of the following formula is a tautology, a contra-
diction, or neither? Prove your answers using the truth tables or the shortcuts of
truth tables.
(1) (p → ¬p) ≡ (¬p → p)
(2) (p ≡ q) ∨ (p ∨ ¬q)

(b) Is the set {p → q, p → ¬q} satisfiable? Justify your answer.

Solution. (a) (The tables below only contain the result. Please fill in the missing
columns yourself.)
1.
p (p → ¬p) ≡ (¬p → p)
t f
f f
So (p → ¬p) ≡ (¬p → p) is a contradiction.
2)
p q (p ≡ q) ∨ (p ∨ ¬q)
t t t
t f t
f t f
f f t
So (p ≡ q) ∧ (p ∨ ¬q) is neither a tautology nor a contradication.

(b) Yes, {p → q, p → ¬q} is satisfiable, because if v(p) = f then v(p → q) =

v(p → ¬q) = t.
□

Question 9. Do not use the Soundness Theorem.

(a) Suppose Γ is a set of Boolean formulae. Prove that Γ |=taut ⊥ if and only if
Γ is not satisfiable.
(b) Use the definition of tautological equivalence to prove that A ∨ B is tautolog-
ically equivalent to ¬A → B.

Solution. (a) Suppose Γ |=taut ⊥. If there is an state (truth assignment) v such

that v(A) = t for every A ∈ Γ, then Γ |=taut ⊥ implies that v(⊥) = t, which is
impossible. Therefore there is no such a state. That is, Γ is not satisfiable.
Now assume Γ is not satisfiable. That is, there is no state which assigns true (t)
to all the formula in Γ. By the definition, vacuously we have Γ |=taut ⊥.
6 SAMPLE QUESTIONS FOR MIDTERM EXAM MATH1090O W22

(b) We have to show that for any state v we have v(A ∨ B) = v(¬A → B).
We have v(A ∨ B) = f iff v(A) = v(B) = f . On the other hand v(¬A → B) = f
iff v(¬A) = t and v(B) = f . Therefore, v(¬A → B) = f iff v(A) = v(B) = f .
Hence, for any state v we have v(A ∨ B) = v(¬A → B).
(Alternatively, you can also show that the two formulas have the same truth
tables.) □

Question 10. Do not use the Completeness Theorem. Suppose Γ is a set of for-
mulae.

(a) Prove that if Γ + ¬A ⊢ B and Γ + ¬A ⊢ ¬B, then Γ ⊢ A.

(b) Suppose Γ ⊢ ¬B and ∆ ⊢ A → B for some ∆ ⊆ Γ. Prove that Γ ⊢ ¬A.

Solution. (a) Applying the deduction theorem we have Γ ⊢ ¬A → B and Γ ⊢ ¬A →

¬B.
(1) ¬A → B (Γ-theorem)
(2) ¬A → ¬B (Γ-theorem)
(3) ¬¬A ∨ B ((1), abs. thm.)
(4) A ∨ B ((3), Leib., double negation, C-part p ∨ B, fresh p)
(5) ¬¬A ∨ ¬B ((2), abs. thm)
(6) A ∨ ¬B ((5), Leib., double negation, C-part p ∨ ¬B, fresh p)
(7) (A ∨ B) ∧ (A ∨ ¬B) ((4,6), abs. thm.)
(8) A ((7), Cut Rule)

(b) By strengthening hypothesis we have Γ ⊢ A → B. Using the absolute

theorem ⊢ A → B ≡ ¬B → ¬A we have Γ ⊢ ¬B → ¬A. From this and the
assumption Γ ⊢ ¬B, using Modus Ponens we conclude Γ ⊢ ¬A. □

Problem 11. Prove that if Γ |=taut A then there is a finite subset ∆ ⊆ Γ such that
∆ |=taut A.
Solution. Suppose Γ |=taut A. By the completeness theorem Γ ⊢ A. So there is
a Γ-proof for A. Any Γ-proof for A uses only finitely many formula from Γ, say
C1 , . . . , Cn . Let ∆ = {C1 , . . . , Cn }. Then ∆ ⊢ A. Now by the soundness theorem
∆ |=taut A. □