The Australian National University Semester 2, 2020 Research School of Computer Science Tutorial 2 and
Foundations of Computation
The tutorial contains a number of exercises designed for the students to practice the course content. During the lab, the tutor will work through some of these exercises while the students will be responsible for completing the remaining exercises in their own time. There is no expectation that all the exercises will be covered in lab time.
Covers: Lecture Material Week 2
At the end of this tutorial, you will be able to
• determine whether a propositional formula is valid, a contradiction or a contingency; • apply natural deduction to prove (establish) the validity of formulae;
• understand First Order Logic formulae.
Exercise 1 Types of Propositional Formulae
Determine the nature of the following propositional formulae. Remember that a propositional formula is
• valid, if it evaluates to T under all truth value assignments.
• a contradiction, if it evaluates to F under all truth value assignments, and
• a contingency, if there are (necessarily different) truth value assignments for which it evaluates to T and to F .
Formulae:
1. a∧¬a
Solution. Using truth tables:
a ¬a a∧¬a TFF
FTF
It is a contradiction: the formula evaluates to F under all truth value assignments.
2. (a∧(a→b))→¬b Solution. Using truth tables:
a b a→b a∧(a→b) ¬b (a∧(a→b))→¬b
TTTTFF TFFFTT FTTFFT FFTFTT
It is a contingency: there are truth value assignments for which the formula evaluates to T and to F . We can use another method using Boolean Algebra:
(a ∧ (a → b)) → ¬b = (a ∧ (¬a ∨ b)) → ¬b = ¬(a∧(¬a∨b))∨¬b = ¬a∨¬(¬a∨b)∨¬b = ¬a∨(a∧¬b)∨¬b = ((¬a∨a)∧(¬a∨¬b))∨¬b = (T ∧(¬a∨¬b))∨¬b = ¬a∨¬b∨¬b =
¬a∨¬b
(Logical equivalence p → q = ¬p ∨ q) (Logical equivalence p → q = ¬p ∨ q) (De )
(De )
(Distributivity) (Complements) (Identity)
Clearly, the result is neither T nor F . So, the given formula is a Contingency. 1
3. ((a→b)∧(b→c))∧(a∧¬c) Solution. Using truth tables:
a b c a→b b→c (a→b)∧(b→c) a∧¬c ((a→b)∧(b→c))∧(a∧¬c)
TTTTTTFF TTFTFFTF TFTFTFFF TFFFTFTF FTTTTTFF FTFTFFFF FFTTTTFF FFFTTTFF
It is a contradition: the formula evaluates to F under all truth value assignments. We can use another method using Boolean Algebra:
((a → b) ∧ (b → c)) ∧ (a ∧ ¬c) = ((¬a∨b)∧(¬b∨c))∧(a∧¬c) = (((¬a∨b)∧¬b)∨((¬a∨b)∧c))∧(a∧¬c) = (((¬b∧¬a)∨(¬b∧b))∨((c∧¬a)∨(c∧b)))∧(a∧¬c) = ((¬b∧¬a)∨((c∧¬a)∨(c∧b)))∧(a∧¬c) = (a∧¬c∧¬b∧¬a)∨((a∧¬c)∧((c∧¬a)∨(c∧b))) = (a∧¬a∧¬c∧¬b)∨((a∧¬c)∧((c∧¬a)∨(c∧b))) = (F ∧¬c∧¬b)∨((a∧¬c)∧((c∧¬a)∨(c∧b))) = ((a∧¬c)∧((c∧¬a)∨(c∧b))) = (a∧¬c∧c∧¬a)∨(a∧¬c∧c∧b) = (a∧F ∧¬a)∨(a∧F ∧b) = F∧F=F=
The given formula is a Contradiction. 4. ¬(a→b)∨(¬a∨(a∧b))
(Logical equivalence p → q = ¬p ∨ q) (Distributivity)
(Distributivity)
(Complements, Identity) (Distributivity)
(Commutativity) (Complements) (Identity) (Commutativity) (Complements) (Identity)
Solution. Using truth tables:
a b ¬(a→b) a∧b ¬a∨(a∧b) ¬(a→b)∨(¬a∨(a∧b))
TTFTTT TFTFFT FTFFTT FFFFTT
It is valid: the formula evaluates to T under all truth value assignments. We can use another method using Boolean Algebra:
¬(a → b) ∨ (¬a ∨ (a ∧ b)) = ¬(¬a∨b)∨(¬a∨(a∧b)) = ¬(¬a∨b)∨((¬a∨a)∧(¬a∨b)) = ¬(¬a∨b)∨(¬a∨b) = (a∧¬b)∨(¬a∨b) = (¬a∨b∨a)∧(¬a∨b∨¬b) = (T ∨b)∧(T ∨¬a) =
T∧T=T
(Logical equivalence p → q = ¬p ∨ q) (Distributivity)
(Complements, Identity)
(De )
(Distributivity) (Complements) (Identity)
The given formula is Valid.
Exercise 2 Natural Deduction Problems
Construct a natural deduction proof for the following alleged propositional logic theorems. Use only the rules of natural
deduction.
2
1. p→(q→p) Solution.
1p
2q
3 p R,1
4 q → p
5 p → (q → p)
2. (p∧q)→(r→(q∧r))
Solution.
1 p∧q 2r
→-I, 2–3 →-I, 1–4
3 4 5 6
Exercise 3
q
q∧r
r → (q ∧ r)
∧-E, 1 ∧-I, 3, 2 →-I, 2–4 →-I, 1–5
the expression in each case suggests a rule to apply.
Natural Deduction Proofs
(p∧q)→(r→(q∧r))
These problems are simple because the form of
1. Establish that (p → q) → (¬q → ¬p) is
you should recognise that it is used in everyday reasoning. There is a simple proof using (¬-I) and (¬-E).
Solution.
1 p→q
2 ¬q 3p
valid using natural deduction. This is a well-known theorem of logic and
4 5 6 7 8
q
F ¬p
¬q → ¬p (p→q)→(¬q→¬p)
→-E, 1, 3 ¬E, 2, 4 ¬I, 3–5 →-I, 2–6 →-I, 1–7
2. Prove the derived rule p∨(q∧r) using natural deduction. This is a theorem which is easily proved using ∨-E. p∨q
Solution.
1 p ∨ (q ∧ r) 2p
3 p ∨ q
4 q∧r
5 q
6 p ∨ q
7 p∨ q
∨-I, 2
∧-E, 4
∨-I, 5
∨-E, 1, 2–3, 4–6
3
Exercise 4
More Natural Deduction Proofs
((p ∨ q) → q) 1. (p→(p∧q))
Solution.
1 (p ∨ q) → q 2p
p ∨ q q
p ∧ q
∨-I, 2 →-E, 1, 3 ∧-I, 2, 4
3 4 5 6
Solution.
1 (p → q) ∧ (p → r) 2 p→q
3 p→r 4p
p→(p∧q) →-I,2–5 2. ((p→q)∧(p→r))→(p→(q∧r))
5 6 7 8 9
Exercise 5
q
r q∧r
p → (q ∧ r) ((p→q)∧(p→r))→(p→(q∧r))
∧-E, 1 ∧-E, 1
→-E, 2, 4 →-E, 3, 4 ∧-I, 5, 6 →-I, 4–7 →-I, 1–8
Harder Natural deduction proofs
Establish the validity of the following formulae using natural deduction.
1. (p∧q→r)↔(p→(q→r)),thatisyouneedtoprove p∧q→r andp→(q→r).
Solution.
1 (p ∧ q) → r 2p 3q
p → (q → r)
p ∧ q → r
4 5 6 7
p ∧ q
r q → r
∧-I, 2, 3 →-E, 1, 4 →-I, 3–5
p→(q→r) →-I,2–6
4
1 2 3 4 5 6 7
Exercise 6
p → (q → r) p∧q
p q→r q
r
(p ∧ q) → r
∧-E, 2 →-E, 1, 3 ∧-E, 2 →-E, 4, 5 →-I, 2–6
Understanding FOL formulae
The following sentences talk about a solar power system, which consists of one or more installations of solar panels. Each installation of solar panels consists of one or more panels. Each panel consists of one or more cells.
The following predicates are given:
• L(x) – x receives less than 50% of expected light • E(x) – x is producing enough energy • S(x)–xisshaded • B(x,y)–xbelongstoy
• F (x) – x is fully operational
Translate the following sentences into first-order logic:
1. A system is producing enough energy if all its installations are fully operational
Solution. ∀s.(∀i.B(i, s) → F (i)) → E(s)
2. An installation is fully operational if no solar panel in that installation is shaded
Solution. ∀i.¬(∃p.B(p, i) ∧ S(p)) → F (i)
3. A solar panel is shaded if some cell of the panel receives less than 50 percent of expected light
Solution. ∀p.(∃c.B(c, p) ∧ L(c)) → S(p)
5
Appendix 1: Natural Deduction Rules Propositional Calculus
(∧I )
(∨I )
(→I)
(¬I )
(PC)
Predicate Calculus
pq p∧qp∧q (∧E )
p∧qpq
[p] [q] . .
ppp∨qrr
p∨q q∨p
[p] .
(∨E )
r
q pp→q (→ E)
p→q q
[p] .
F p ¬p (¬E )
¬p F
[¬p] .
F pT
(∀I )
∀x. P (x)
P (a) (a arbitrary) ∀x. P (x)
(T)
(∀E )
(∃I )
∃xP (x)
(∃E )
q (a arbitrary)
P (a) P (a)
[P (a)] .
∃xP (x)
q (aisnotfreeinq)
6
Appendix 2: Truth Table Values
p q p∨q p∧q p→q ¬p p↔q TTTTTFT TFTFFFF FTTFTTF FFFFTTT
Appendix 3: Valid Boolean Equations Associativity
a ∨ (b ∨ c) = (a ∨ b) ∨ c a ∧ (b ∧ c) = (a ∧ b) ∧ c Commutativity
a∨b=b∨a a∧b=b∧a Absorption.
a ∨ (a ∧ b) = a a ∧ (a ∨ b) = a Identity.
a∨F=a a∧T=a Distributivity.
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) Complements.
a ∨ ¬a = T
Appendix 4: De
De
¬(x ∨ y) = ¬x ∧ ¬y
a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) a ∧ ¬a = F
¬(x ∧ y) = ¬x ∨ ¬y
7