The Austalian National University Research School of Computer Science Dirk Pattinson
Semester 2, 2018 Assignment 1
Released: Due: Mode: Submit:
Question 1
Foundations of Computation
Tue Aug 21 2018
Tue Sep 4 2018 (any time)
individual submissions only
hard copy with cover sheet, ground floor CSIT building
Truth Tables
[10 + 10 + 10 credits]
- a) For each of the following propositions, use truth tables to determine whether the proposition is valid, or is a contradiction, or is a contingency. In each case, show the entire truth table and state clearly whether the proposition is valid, or is a contradiction, or is a contingency.
1. p∧¬p
2. a∨b→a∧b 3. p→(q→p) - b) Consider the truth value assignment v that assigns the following truth values to the atomic propositions p, q and r: v(p) = F,v(q) = T,v(r) = T.
Which of the following formulae evaluate to T under the assignment v, i.e. when the truth values of p, q and r are given according to v? Show the line of the truth table that justifies your answer.
1. (p→¬q)∨¬(r∧q) 3. ¬(¬p→q)∧r 2. (¬p∨¬q)→(p∨¬r) 4. ¬(¬p→q∧¬r)
- c) Consider the boolean function given by the following truth table:
x y z f(x,y,z) x y z f(x,y,z) FTTF FFTT FFTT FTTTTT
Give a formula (in variables x, y and z) that represents the boolean function given above. Briefly argue why the formula indeed represents the boolean function.
(Parts b and c were part of the 2017 exam.)
Question 2 First Order Specification [10 credits] This question discusses a tram network, which consists of a number of segments. Segments consist of a
number of routes. Each route is used to service a number of stops. The following predicates are given:
|
F |
F |
|
F |
T |
|
T |
F |
|
T |
T |
|
F |
F |
|
F |
T |
|
T |
F |
• S(x) – x runs to schedule • L(x) – x runs late
1
• B(x,y) – x belongs to y
• T (x) – x is serviced within 2 minutes of the scheduled time
The following sentences describe the timeliness of the tram network and its components. Translate each of them into First-Order Logic:
- a) The tram route r runs to schedule if every stop belonging to the route is serviced within 2 minutes of the scheduled time.
- b) The tram segment s runs late if some tram route in the segment does not run to schedule.
- c) The tram network n runs to schedule unless some segment belonging to the network runs late.
Question 3 Natural Deduction [13 + 13 + 13 + 8 + 13 credits]
In the following questions, prove the derived rules using natural deduction. You may only use the rules given in the Appendix. Do not use algebraic laws, or any of the derived rules obtained in lectures. Number each line and include justifications for each step in your proofs.
a) Give a natural deduction proof of the derived rule q ∨ ¬q . q ∨ (q → p)
- b) Give a natural deduction proof of ¬a ∧ ¬b → ¬(a ∨ b)
- c) Give a natural deduction proof of the derived rule ¬(∃y.Q(y) ∧ T (y)) .
∀x.Q(x) → ¬T (x) d) Give a natural deduction proof of ∀x(P (x) → ∃y.P (y)).
e) Give a natural deduction proof of ∀z.((∀x.P (x) → Q(x)) ∧ ¬Q(z) → ¬P (z)). (Parts b, d and e were part of the 2017 exam.)
2
Appendix 1 — Natural Deduction Rules Propositional Calculus
(∧I )
(∨I )
(→I)
(¬I )
(PC)
pq p∧qp∧q (∧E )
p∧qpq
[p] [q] . .
ppp∨qrr
p∨q q∨p
[p] .
(∨E )
q pp→q (→ E)
p→q q
[p] .
F p ¬p (¬E )
¬p F
[¬p] .
F pT
r
(∀E )
(T)
Predicate Calculus
P(a) (a arbitrary) ∀x. P(x)
(∀I )
∀x. P(x)
(∃I )
∃xP (x)
(∃E )
[P (a)] .
P (a) P (a)
∃xP(x)
q (aisnotfreeinq)
q (a arbitrary) 3
Appendix 2 — Truth Table Values
p q p∨q p∧q p→q ¬p p↔q TTTTTFT TFTFFFF FTTFTTF FFFFTTT
4