- May 15, 2020

The University of MelbourneSchool of Computing and Information SystemsCOMP30026 Models of ComputationAssignment 1, 2019Released: 27 August. Deadline: 15 September at 23:00PurposeTo improve your understanding of propositional logic, first-order predicate logic, mechanizedreasoning, and discrete mathematics. To develop skills in analysis and formal reasoning aboutcomplex concepts, and to practise writing down formal arguments with clarity.Challenge 1Consider the four first-order predicate formulasF = ∀x (¬P (x, x))G = ∀x ∀y ∀z (P (x, y) ∧ P (y, z)⇒ P (x, z))G′ = ∀x ∀y ∀z (P (x, y) ∧ P (y, z)⇒¬P (x, z))H = ∀x ∀y (P (x, y)⇒¬P (y, x))a. Show that F ∨G ∨G′ ∨H is not valid.b. Show that F ∧G′ ∧H is satisfiable.c. Show that (F ∧G)⇒H is valid.Challenge 2For this challenge use the following predicates:• F (x), which stands for “the force is with x”• J(x), which stands for “x is a Jedi master”• E(x, y), which stands for “x exceeds y”• P (x, y), which stands for “x is a pupil of y”• V (x), which stands for “x is venerated”and use the constant ‘a’ to denote Yoda.a. For each of the statements S1, . . . S4, express it as a formula in first-order predicatelogic (not clausal form):S1: “The force is with every Jedi master.”S2: “Yoda exceeds some Jedi master.”S3: “A Jedi master is venerated if (1) the force is with him/her and (2) all his/herpupils exceed him/her.”S4: “Every Jedi master without pupils is venerated.”(Be careful to get these translations right, including S3; most of the following dependson this.)b. Translate S1–S3 to clausal form.c. Translate the negation of S4 to clausal form.d. Give a proof by resolution to show that S4 follows from the other statements.Challenge 3Let B = {0, 1} be the set of Boolean values, so that Bn is the set of n-tuples of Boolean values(or Boolean vectors). We use a bold variable b to denote a Boolean vector of n Booleanvalues (b1, b2, . . . , bn)An n-dimensional Boolean vector function f : Bn → Bn is reversible iff for every Booleanvector y ∈ Bn there is exactly one vector x ∈ Bn such that f(x) = y. Intuitively, thefunction is reversible iff we can uniquely determine the input vector from an output vector,allowing us to reliably ‘reverse’ the evaluation of the function. For example, f(b1, b2) =(b2, b1) is a 2-dimensional reversible Boolean vector function, and g(b1, b2) = (b1 ∧ b2, b1 ∨ b2)is a 2-dimensional Boolean vector function that is not reversible (because, for example,(0, 1) = g(0, 1) = g(1, 0)).(This kind of logic function finds important applications in the theory of quantum compu-tation, where the laws of quantum mechanics constrain computations to proceed reversibly.)a. Consider the Boolean vector function fa(b1, b2) = (¬b1, b1⊕b2). Show that this functionis reversible.b. Consider the Boolean vector function fb(b1, b2, b3) = (b1 ⊕ b2, b2 ⊕ b3, b3 ⊕ b1). Showthat this function is not reversible.c. Is the Boolean vector function fc(b1, b2, b3) = (b1 ⊕ b3,¬b3, b1 ⊕ b2) reversible? Justifyyour answer.d. Give a formula, in terms of n, for the fraction of distinct n-dimensional Boolean vectorfunctions that are reversible.Note that two n-dimensional Boolean vector functions are considered distinct iff theyproduce different output vectors for some input vector. For example, we should notcount f(b1) = (¬b1) and g(b1) = (b1 ⊕ t) as two distinct functions—despite syntac-tic differences, f and g produce matching outputs for all inputs. Here we are onlyinterested in counting functions with differing behaviour.Challenge 4Find ways to avoid unnecessarily complex propositional formulas:a. Give the shortest possible formula that is equivalent to (P ⇒Q)⇒¬Q.b. Express P ⇒ ((P ∧Q)⇒R) using no connectives other than ⇒.c. Express (P ⇒ (Q ∨R)) ∧ (P ⇔Q) using no connectives other than ⇔.The answers to this challenge must be submitted through Grok. For each question, you areto submit the answer as a Haskell expression of type Exp, where Exp is the type of structuretrees used for propositional formulas in the second half of Worksheet 1 (see Grok). Forvariable names (of type Char), use ’P’, ’Q’, and ’R’, that is, use upper case.Challenge 5Consider the following light switching game. We begin with an n by n grid of square buttons,numbered 1–n2, initially dark, as shown below (left) for n = 4. Pressing any button will causethat button to light up, along with its immediate neighbours above, below, and to its left andright in the grid. For example, the result of pressing button 11 is depicted below (middle).Subsequent button presses will continue to light up nearby buttons, or switch them back offif they are already alight. For example, the result of pressing button 15 (after button 11) isshown below (right). Note that because buttons 15 and 11 were both alight, they becamedark again. Note also that the grid does not ‘wrap around’: button 15 has no effect onbutton 3. The aim of the puzzle, given a particular light configuration, is to find a sequence ofbutton-presses that will produce this configuration. To help you familiarise yourself with thispuzzle, we provide a grid for the n = 4 case at https://comp30026.far.in.net/puzzle.1 2 3 45 6 7 89 10 11 1213 14 15 161 2 3 45 6 7 89 10 11 1213 14 15 161 2 3 45 6 7 89 10 11 1213 14 15 16Your task is to write a Haskell program capable of solving this puzzle. Given a grid size nand a light configuration as input, your program must output a sequence of buttons which,when pressed in order, will produce the desired configuration.The answer to this challenge must be submitted through Grok, in the form of a functionlights of type Int -> [Int] -> [Int] The first input parameter provides the dimension-ality of the puzzle grid, n, and will always be a positive integer. The second input parameterrepresents the buttons to be switched on in the desired configuration (any buttons not listedare to be switched off). The return value should be a list representing the sequence of but-tons to press in your solution to the puzzle, or, in case the configuration is impossible toachieve, the return value should be an empty list. For example, the input/output pair belowcorresponds to a 4 by 4 puzzle in which the desired configuration is the one above (right),and to one possible solution to this puzzle:> lights 4 [7, 10, 12, 14, 16][11, 15]Hint 1 : Our suggested approach is for you to model the puzzle as a propositional satisfia-bility problem. In this way, the task becomes a simple translation from a puzzle descriptionto a propositional formula, and you can use tools like those you have constructed in as-sessed worksheets 1 and 2 to solve the formula itself (we provide similar tools on Grok).The code required for this approach is minor compared to the code required to implement apuzzle-specific search algorithm.Hint 2 : There are many ways to approach this modelling task. To get you started on theright track, consider the following questions (assume n = 4): (1) What light configurationresults from the sequence [15, 11]? How does this compare to the above example? (2)What light configuration results from the sequence [6, 1, 6]? How about [6, 1, 6, 6]?Is it ever useful to press a button more than once? (3) Could you determine the final stateof a single button by looking at a long sequence of button presses, without simulating thewhole sequence?Challenge 6Consider a single-digit display which will be used to show any decimal digit, or a dash:, , , , , , , , , ,Arrays of such displays are used to display numbers in digital clocks, washing machines andother devices. A seven-segment display is made up by seven LEDs (labelled a–g), as shownbelow on the right. For example, to show the digit 3, all display segments except b and eare lit up.Each of the seven display segments a–g can be considered a propositional function of fourpropositional variables W , X, Y and Z, with input WXY Z specifying the desired decimaldigit in binary notation (or 1010 for a dash). For example, input 3 is given by WXY Z = 0011(that is, W and X are false and Y and Z are true). For that input combination, the outputsb and e should be 0 (False) while the rest should be 1 (True). Given this, the truth tablesfor all the functions a–g are as shown in the table below.W X Y Z a b c d e f g0 0 0 0 1 1 1 0 1 1 10 0 0 1 0 0 1 0 0 1 00 0 1 0 1 0 1 1 1 0 10 0 1 1 1 0 1 1 0 1 10 1 0 0 0 1 1 1 0 1 00 1 0 1 1 1 0 1 0 1 10 1 1 0 1 1 0 1 1 1 10 1 1 1 1 0 1 0 0 1 01 0 0 0 1 1 1 1 1 1 11 0 0 1 1 1 1 1 0 1 11 0 1 0 0 0 0 1 0 0 01 0 1 1 ∗ ∗ ∗ ∗ ∗ ∗ ∗1 1 0 0 ∗ ∗ ∗ ∗ ∗ ∗ ∗1 1 0 1 ∗ ∗ ∗ ∗ ∗ ∗ ∗1 1 1 0 ∗ ∗ ∗ ∗ ∗ ∗ ∗1 1 1 1 ∗ ∗ ∗ ∗ ∗ ∗ ∗beadgcfAn asterisk (*) in the table marks an output that we don’t care about. It is assumed thatthe last five input combinations will never happen, so we are free to let the correspondingoutputs be whatever is convenient.The single-digit display must be implemented with logic circuitry. Here we assume thatonly three types of logic gates are available. An and-gate takes two inputs and produces, asoutput, the conjunction (∧) of the inputs. Similarly, an or-gate implements disjunction (∨).Finally, an inverter takes a single input and negates it.The task here is to design a circuit for all of a–g using as few gates as possible. We canspecify the circuit by writing down the Boolean equations for each of the outputs a–g. Forexample, we can define f = ¬(X ∧ ¬Y ∧ Z), which shows that we can implement f with aslittle as four gates. Since we want to use as few gates as possible, it is important to look forcases where outputs can be shared, or reused. For example, if we have already implementedb then we could define f = b ∨ Z, using just one gate. Note that for any sub-circuit thatyou want to share (that is, you want to direct its output to different places), the outputmust have a name. You can define as many “helper” functions as you please, to create thesmallest possible solution. For example, suppose you have implemented some function using¬(X ∨Y ) as a sub-circuit, and now you realise that there is another function that could alsouse that sub-circuit. Rather than duplicate the sub-circuit, you want the two functions toshare, so you name the output (say, u). Defining u = ¬(X∨Y ) and letting the two functionsrefer to u instead of ¬(X ∨ Y ) corresponds exactly to the sharing of the circuit.The answer to this challenge must be submitted through Grok. Submit a text file con-sisting of one line per definition. This file will be tested automatically, so it is importantthat you follow the notational conventions exactly. We write ¬ as – and ∨ as +. We write∧ as ., or, simpler, we just leave it out, so that concatenation of expressions denotes theirconjunction. Here is an example set of equations (for a different problem):# An example of a set of equations in the correct format:a = -Y Z + Y -Z + X -Y -Zb = u + X (Y + Z)c = X + -(Y Z)d = u + X au = -X -Y# u is an auxiliary function introduced to simplify b and dEmpty lines, and lines that start with ‘#’, are ignored. Input variables are in upper case.Negation binds tighter than conjunction, which in turn binds tighter than disjunction. Sothe equation for a says that a = (¬Y ∧ Z) ∨ (Y ∧ ¬Z) ∨ (X ∧ ¬Y ∧ ¬Z). Note the use of ahelper function u, allowing b and d to share some circuitry. Also note that we do not allowany feedback loops in the circuit. In the example above, d depends on a, so a is not allowedto depend, directly or indirectly, on d (and indeed it does not).Submission and assessmentSome of the problems are harder than others. All should be solved and submitted by studentsindividually. Your solution will count for 12 marks out of 100 for the subject. Each questionis worth 2 marks. Marks are primarily allocated for correctness, but elegance and how clearlyyou communicate your thinking will also be taken into account. For Challenge 6, there willbe 1 mark for a correct solution. After that, your mark depends on which quartile yoursolution sits in, when we order all solutions by increasing number of gates. If it falls in thebest quartile (that is, within the 25% of solutions that use the fewest gates), we add 1 mark.If you are in the next quartile, we instead add 0.5 marks. Otherwise no marks are added tothe mark for correctness.The deadline is 15 September at 23:00. Late submission will be possible, but a latesubmission penalty will apply: a flagfall of 1 mark, and then 1 mark per 12 hours late.For challenges 1–3, submit a PDF document via the LMS. This document should be nomore than 2 MB in size. If you produce an MS Word document, it must be exported andsubmitted as PDF, and satisfy the space limit of 2 MB. We also accept neat hand-writtensubmissions, but these must be scanned and provided as PDF, and again, they must respectthe size limit. If you scan your document, make sure you set the resolution so that thegenerated document is no more than 2 MB. The LMS site, from which you downloaded thisdocument, has advice to help you satisfy the 2 MB requirement while maintaining readability.Being neat is easier if you type-set your answers, but not all typesetting software doesa good job of presenting mathematical formulas. The best tool for this is LATEX, which isworth learning if you expect that you will later have to produce large technical documents.Admittedly, diagrams are tedious to do with LATEX, even when using sophisticated packagessuch as Tikz. You could, of course, mix typeset text with hand-drawn diagrams. In caseyou want to use the assignment to get some LATEX practice, we will leave the source for thisdocument in the content area where you find the PDF version.For challenge 4–6, submit files on Grok. The required format for submitted solutions willbe clear when you open the Grok modules, but as mentioned above, for Challenge 4 we wantexpressions of type Exp, for Challenge 5 we want a Haskell function, and for Challenge 6 wewant a text file in the format specified above.For Challenges 4 and 5 you will receive immediate feedback from some elementary tests.These merely check that your input has the correct format, so they should not be reliedupon for correctness. We will test comprehensively after the deadline. For Challenge 6,we provide feedback concerning both well-formedness and correctness. Note that on Grok,“saving” your file does not mean submitting it for marking. To submit, you need to click“mark”. You can submit as many times as you like. What gets marked is the last submissionyou have made before the deadline.Make sure that you have enough time towards the end of the assignment to present yoursolutions carefully. A nice presentation is sometimes more time consuming than solving theproblems. Start early; note that time you put in early usually turns out more productive thana last-minute effort. For Challenge 6 in particular, you don’t want to submit “improved”solutions a few minutes before the deadline, as they may turn out to be wrong and you won’thave time to fix this.Individual work is expected, but if you get stuck, email Harald or Matt a precise descrip-tion of the problem, bring up the problem at the lecture, or (our preferred option) use theLMS discussion board. The COMP30026 LMS discussion forum is both useful and appro-priate for this; soliciting help from sources other than the above will be considered cheatingand will lead to disciplinary action.Harald and Matt26 August 2019