The Austalian National University (compiled: 22:59, Tuesday 9th August, 2022) S2 2022
School of Computing Assignment 1
Convenor: Pascal Bercher
Lecturer of the respective content: Pascal Bercher and Dirk Pattinson
Foundations of Computation
Released: Wednesday 10 August, 2022
Due: Wednesday, 24 August, 2022, 23:55 AEST
Mode: individual submissions only
Submit: Question 4 and (depending on your answer) Question 6(c) must be typed and submitted
to Turnitin; all other questions as one PDF via Wattle
(scans of legible handwritten solutions are perfectly acceptable)
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 Boolean Functions [4 + 5 Credits]
a) Consider the boolean function f given by the following truth table:
p q r f(p, q, r)
T T T F
T T F T
T F T F
T F F F
F T T T
F T F T
F F T F
F F F T
Give a boolean formula for f . (I.e., you may use any of the connectives ¬, ∧, and ∨, but no others.)
b) We now define a new operator ≺ as follows:
x y x ≺ y
F F F
F T T
T F F
T T F
Demonstrate that the set {≺, T} is expressively complete. You may use the fact that {¬,∧,∨} is
an expressively complete set.
Question 2 Boolean Equations [7 + 9 Credits]
a) Prove the boolean equation (¬a ∨ b) ∧ a = b ∧ a (MP) using the valid boolean equations given
in the Appendix. Specifically, you may only use associativity, commutativity, absorption, identity,
distributivity, and complements; you may not use De Morgan’s Laws.
b) Prove ((¬p∨ q)∧ p)∧ (¬q ∨ (p∨ r)) = p∧ q using the derived equation MP. Again you may use the
rules in the Appendix but not DeMorgan’s Laws.
Question 3 Propositional Natural Deduction [13 + 17 Credits]
Prove the following in the natural deduction proof system, using the notation from the course.
a) (p ∧ q → r) ∧ ¬(p→ r)→ ¬(p→ q) b) (p ∨ q) ∧ (r ∧ ¬s→ ¬q)
p ∨ (r → s)
Question 4 Natural Deduction Rules [5 + 5 Credits]
Recall our new operator ≺ from Question 1. We now give natural deduction rules for this operator.
(≺ER)
p ≺ q
q
(≺EL)
p ≺ q p
F
(≺I)
[p]
...
F q
p ≺ q
Explain why the ≺EL and ≺I rules are appropriate. Specifically, argue why the rules are consistent
with the truth table for ≺ given in Question 1. We expect that approx. 70 words or less will be enough,
but you can also write more should you need more. Remember! This question must be submitted
separately to Turnitin as a typed (not handwritten) PDF.
2
Question 5 First Order Natural Deduction [12 Credits]
Prove the following in the natural deduction proof system, using the notation from the course:
∀x.P (x)→ Q(x) ∃x.P (x) ∨Q(x)
∃x.Q(x)
Question 6 Binary Relations [3 + 3 + 17 Credits]
Recall that an interpretation in first order logic needs a domain of objects D. Consider our domain
to be all the sets of natural numbers, i.e. U = P(N) (the power set of natural numbers). We define
a relation S(x, y) which relates sets of the same size. So for any two sets x and y, S(x, y) is true iff
|x| = |y|.
For example, S({0}, {1}) = T and S(∅, {0, 1}) = F .
a) A relation R is transitive iff it satisfies the following condition:
∀x∀y∀z.R(x, y) ∧R(y, z)→ R(x, z)
Is S transitive? State your answer and either
• explain in one to two sentences why it holds, or
• give a counter example (three sets x, y, z where this doesn’t hold for S).
b) A relation R is symmetric iff it satisfies the following condition:
∀x∀y.R(x, y)→ R(y, x)
Is S symmetric? State your answer and either
• explain in one to two sentences why it holds, or
• give a counter example (two sets x, y where this doesn’t hold for S).
c) Consider the inference below:
∀x∀y∀z.R(x, y) ∧R(y, z)→ R(x, z) ∀x∀y.R(x, y)→ R(y, x) ∀x∃y.R(x, y)
∀x.R(x, x)
Either:
• prove this in the natural deduction proof system, or
• show that it is not valid with a counter-example and an explanation in no more than 100
words (excluding any formulae/symbols you might need). Your counter-example must consist
of a situation (i.e., a domain/universe U and Θ, which defines the relation) that does not
satisfy the inference.
In this case, your answer must be typed up (just like Question 4) and submitted to Turnitin.
3
Appendix: 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) a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
Complements.
a ∨ ¬a = T a ∧ ¬a = F
4
Appendix: Natural Deduction Rules
Propositional Calculus
(∧I) p q
p ∧ q
(∧E) p ∧ q
p
p ∧ q
q
(∨I) p
p ∨ q
p
q ∨ p
(∨E)
[p] [q]
...
...
p ∨ q r r
r
(→ I)
[p]
...
q
p→ q
(→ E) p p→ q
q
(¬I)
[p]
...
F
¬p
(¬E) p ¬p
F
(PC)
[¬p]
...
F
p
(T )
T
Predicate Calculus
(∀I) P (a) (a arbitrary)
∀x. P (x)
(∀E) ∀x. P (x)
P (a)
(∃I) P (a)
∃xP (x)
(∃E) ∃xP (x)
[P (a)]
...
q (a arbitrary)
q (a is not free in q)
5