Foundations of Computation Released: Tue Aug 21 2018 Due: Tue Sep 4 2018 (any time) Mode: individual submissions only Submit: hard copy with cover sheet, ground floor CSIT building Question 1 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) 2. (¬p ? ¬q) ? (p ? ¬r) 3. ¬(¬p ? q) ? r 4. ¬(¬p ? q ? ¬r) c) Consider the boolean function given by the following truth table: x y z f(x, y, z) F F F T F F T F F T F F F T T T x y z f(x, y, z) T F F F T F T T T T F T T T T T 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.) Document Preview:

The Austalian National University Semester 2, 2018Research School of Computer Science Assignment 1Dirk PattinsonFoundations of ComputationReleased: Tue Aug 21 2018Due: Tue Sep 4 2018 (any time)Mode: individual submissions onlySubmit: hard copy with cover sheet, ground oor CSIT buildingQuestion 1 Truth Tables [10 + 10 + 10 credits]a) For each of the following propositions, use truth tables to determine whether the proposition isvalid, or is a contradiction, or is a contingency. In each case, show the entire truth table and stateclearly whether the proposition is valid, or is a contradiction, or is a contingency.1. p^:p2. a_b!a^b3. p! (q!p)b) Consider the truth value assignment v that assigns the following truth values to the atomicpropositions 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 valuesof p, q and r are given according to v? Show the line of the truth table that justies your answer.1. (p!:q)_:(r^q) 3. :(:p!q)^r2. (: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)F F F T T F F FF F T F T F T TF T F F T T F TF T T T T T T TGive a formula (in variables x, y and z) that represents the boolean function given above. Brie yargue why the formula indeed represents the boolean function.(Parts b and c were part of the 2017 exam.)Question 2 First Order Specication [10 credits]This question discusses a tram network, which consists of a number of segments. Segments consist of anumber of routes. Each route is used to service a number of stops. The following predicates are given: S(x) – x runs to schedule L(x) – x runs late1 B(x;y) – x belongs to y T (x) – x is serviced within 2 minutes of the scheduled timeThe following sentences describe the timeliness of the tram network and its components. Translateeach of them into First-Order Logic:a) The tram router runs to…

Attachments:

foundationsof….pdf