The Austalian National University School of Computing
Victor and
Semester 2, 2021 Assignment 1
Released: Due: Due: Mode: Submit:
Wednesday 11 August, 2021
Friday, 20 August, 2021, 23:55 AEST
Wednesday, 25 August, 2021, 23:55 AEST
individual submissions only
as single pdf file via Wattle (scans of legible handwritten solutions are perfectly acceptable), here.
Foundations of Computation
Pledge of Academic Integrity and Originality statement1
I am committed to being a person of integrity. I pledge, as a member of the Australian National University community, to abide by and uphold the standards of academic integrity outlined in the ANU statement on honesty and plagiarism. I understand that it is wrong to ever misrepresent another person’s work as my own.
I am aware of the relevant legislation, and understand the consequences of me breaching those rules. I have read the COMP1600/COMP6260 academic integrity and pledge to abide by it.
I declare that everything I have submitted in this assignment was entirely my own work.
Name: UID:
Signature:
1Submissions without your name, UID and signature will not be marked. 1
Question 1 A New Connective [2 + 2 + 6 + 4 + 6 Credits] The following truth table represents the boolean function m, which intuitively corresponds to “If p
then q else r”:
p q r m(p,q,r)
FFF F FFT T FTF F FTT T TFF F TFT F TTF T TTT T
a) Consider the truth value assignment v that assigns the following values to the atomic propositions p, q and r: situation v(p) = T , v(q) = F and v(r) = F . Determine whether the following formula evaluates to T or F under the assignment v:
m(p,q,r)∨m(r,p,q)∨m(q,r,p)
b) Express m using the connectives {¬, ∧, ∨}.
c) Express m using at most 4 connectives. You may use connectives from the set {¬, →, ∧, ∨}. Prove that your formula is equivalent to m using truth tables.
d) Show that the set {m, F } is not expressively complete.
e) Show that the set {m, F, T } is expressively complete.
a) It evaluates to T because m(q,r,p) gives m(F,F,T) = T.
b) Using the method presented in slides 17 – 19 of the Week 1 slides, we find
(¬p ∧ ¬q ∧ r) ∨ (¬p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r) ∨ (p ∧ q ∧ r)
Explanation: each of the four disjoints is a formula that is true at precisely one of the true rows
of the table. Joining them using “or” gives a formula corresponding to the table.
c) There are several possible solutions. One of them is (p → q) ∧ (p ∨ r). It is equivalent to m(p, q, r) because, as shown in the truth table below, it evaluates to the same truth value in each valuation.
p q r p→q p∨r (p→q)∧(p∨r)
FFFTFF FFTTTT FTFTFF FTTTTT TFFFTF TFTFTF TTFTTT
Other possible solutions are (p → q) ∧ (¬p → r) and (¬p ∧ r) ∨ (p ∧ q).
d) Let φ be any expression built from proposition letters p1, . . . , pn and the connective m. In the situation v where v(p1) = ··· = v(pn) = F, φ always evaluates to F, because m(F,F,F) = F. So we cannot construct the constant Boolean function that maps everything to T.
e) It suffices to show that we can construct ¬, ∨ and ∧ because the set {¬,∨,∧} is expressively complete. We have:
¬x = m(x,F,T) x ∧ y = m(x, y, F ) x ∨ y = m(x, T, y)
The truth of each of these equalities can easily be read off from the truth table of m. Therefore {m, F, T } is expressively complete.
Question 2 Boolean Equations [4 + 16 Credits]
Prove that the following equations are valid. You may only use the boolean equations presented in the lecture (associativity, commutativity, absorption, identity, distributivity and complements, given in Appendix 1), but not the De Morgan laws.
a) (a∨d)∨((a∧c)∨(c∧d))=a∨d
b) (a∨¬b)∧(¬a∨b)=(a∧b)∨(¬a∧¬b) Solution.
a) Compute:
(a∨d)∨((a∧c)∨(c∧d))
= (a∨d)∨((c∧a)∨(c∧d))
= (a ∨ d) ∨ (c ∧ (a ∨ d))
= (a ∨ d) ∨ ((a ∨ d) ∧ c)
b) Possible solution
(a ∨ ¬b)∧(¬a ∨ b)
= ((a ∨ ¬b) ∧ ¬a) ∨ ((a ∨ ¬b) ∧ b)
= ((a∧¬a)∨(¬b∧¬a))∨((a∧b)∨(¬b∧b)) = ((a∧¬a)∨(¬a∧¬b))∨((a∧b)∨(b∧¬b)) = (F ∨(¬a∧¬b))∨((a∧b)∨F)
= ((¬a ∧ ¬b) ∨ F) ∨ ((a ∧ b) ∨ F)
= (¬a ∧ ¬b) ∨ (a ∧ b) = (a ∧ b) ∨ (¬a ∧ ¬b)
(Commutativity) (Distributivity) (Commutativity) (Absorption)
(Distributivity)
(Distributivity) (Commutativity) (Complements) (Commutativity) (Identity) (Commutativity)
Alternative solution
(a ∨ ¬b)∧(¬a ∨ b)
= ((a∨¬b)∧T)∧((¬a∨b)∧T)
= ((a∨¬b)∧(b∨¬b))∧((¬a∨b)∧(a∨¬a)) = ((¬b∨a)∧(¬b∨b))∧((¬a∨b)∧(¬a∨a)) = (¬b ∨ (a ∧ b)) ∧ (¬a ∨ (b ∧ a))
= (¬b ∨ (a ∧ b)) ∧ (¬a ∨ (a ∧ b))
= ((a ∧ b) ∨ ¬b) ∧ ((a ∧ b) ∨ ¬a) = (a ∧ b) ∨ (¬b ∧ ¬a)
= (a ∧ b) ∨ (¬a ∧ ¬b)
(p → r) ∨ (q → r) and (p ∧ q) → r .
(Identity) (Complements) (Commutativity) (Distributivity) (Commutativity) (Commutativity) (Distributivity) (Commutativity)
[10 + 10 + 10 + 10 Credits] We would like to prove the formula ((p → r) ∨ (q → r)) ↔ ((p ∧ q) → r). That is, we wish to prove
Question 3
Propositional Natural Deduction
(p ∧ q) → r We will do this in several steps.
a) Give a proof of the derived rule
(p → r) ∨ (q → r)
(p → r) ∨ (q → r). p∧q→r
∧-E, 2 ∧-E, 2
∨-E, 1, 5–6, 7–8 →-I, 2–9
(p → r) ∨ (q → r) p∧q
p→r r q→r r
b) Prove the following derived rule, one half of De Morgans. ¬(p ∨ q) (DM)
c) Prove the following derived rule, “Negation of Implication”. ¬(p → q)(NoI)
1 ¬(p∨q) 2p
3 p∨q 4 ⊥ 5¬p 6q
7 p∨q 8 ⊥ 9¬q
∨-I, 2 ¬E, 3, 1 ¬I, 2–4
∨-I, 6 ¬E, 7, 1 ¬I, 6–8 ∧-I, 5, 9
1 ¬(p → q) 2 ¬p 3p
12 p 13 q 14 p→q 15 ⊥
7 q 8 p→q 9 ⊥
PC, 5–6 →-I, 3–7 ¬E, 8, 1 PC, 2–9
→-I, 12–13 ¬E, 14, 1 ¬I, 11–15 ∧-I, 10, 16
d) Finally, prove
p∧q→r . (p → r) ∨ (q → r)
Here, you may use the rules (DM) and (NoI) in addition to the standard deduction rules for this proof.
2 ¬((p→r)∨(q→r))
3 ¬(p→r)∧¬(q→r)
First Order Natural Deduction
(∀x.P (x) ∧ ¬Q(x)) ∧ (∃z.T ) ∃y.¬(P (y) → Q(y))
DM, 2 ∧-E, 3 ∧-E, 3 NoI, 4 NoI, 5 ∧-E, 6 ∧-E, 7
∧-I, 8, 9 →-E, 10, 1 ∧-E, 6
¬E, 11, 12 PC, 2–13
Question 4
[10 + 10 Credits]
14 (p → r) ∨ (q → r)
1 (∀x.P (x) ∧ ¬Q(x)) ∧ (∃z.T )
2 ∀x.P (x) ∧ ¬Q(x)
∧-E, 1 ∧-E, 1
∀-E, 2 ∧-E, 5 ∧-E, 5
→-E, 6, 8 ¬E, 9, 7
¬I, 8–10 ∃-I, 11
∃-E, 3, 4–12
P (a) ∧ ¬Q(a) P (a)
P(a) → Q(a) Q(a)
¬(P (a) → Q(a))
∃y.¬(P (y) → Q(y)) ∃y.¬(P (y) → Q(y))
b) In the previous question, ∃z.T looks like to be a useless statement. Could we prove (∀x.P (x) ∧ ¬Q(x))
∃y.¬(P (y) → Q(y))
instead? If so, give a proof. If not, specify a situation (U,θ) (consisting of a domain U and
predicates θ(P) and θ(Q)) and briefly justify that • ∀x.P (x) ∧ ¬Q(x) is true, but
• ∃y.¬(P (y) → Q(y) is false in this situation.
Solution. No, we need ∃z.T to ensure the domain is non-empty. A counterexample is as follows. Let U = ∅ and θ(P ) = θ(Q) = ∅. Then ∀x.P (x) ∧ ¬Q(x) is vacuously true, (as the domain is empty, so any property holds for all members of the domain) but ∃y.¬(P (y) → Q(y)) is vacuously false (as the domain is empty, so there cannot exist a member that satisfies any chosen property, and even if it wasn’t vacuously false, ¬(⊥ → ⊥) ≡ ⊥.)