Due: Thursday, 26th November, 15:00 (AEDST) Submission is through WebCMS/give and should be a single pdf file, maximum size 2Mb. Prose should be typed, not handwritten. Use of LATEX is encouraged, but not required. Discussion of assignment material with others is permitted, but the work submitted must be your own in line with the University’s plagiarism policy. Problem 1 (12 marks) Prove the following results hold in all Boolean Algebras: (a) For all x: (x ∨ 00) ∧ (x0 ∨ 0) = x0 (4 marks) (b) For all x, y: (x ∨ y) ∧ x = x (4 marks) (c) For all x, y: y0 ∨ ((x ∧ y) ∨ x0 ) = 1 (4 marks) Problem 2 (12 marks) Prove or disprove the following logical equivalences: (a) ((p ∧ q) → r) ≡ (p → (q → r)) (4 marks) (b) ((p → q) → r) ≡ (p → (q → r)) (4 marks) (c) ((p ∨ (q ∨ r)) ∧ (r ∨ p)) ≡ ((p ∧ q) ∨ (r ∨ p)) (4 marks) Problem 3 (14 marks) In lectures it was discussed how to convert a formula ϕ into CNF. The procedure was described as follows: 1. Compute an equivalent DNF, ψ1, for ¬ϕ. 2. Let ψ2 be the dual of ψ1 (replace ∧ with ∨ and vice-versa, and > with ⊥ and vice-versa). 3. Let ψ3 be the result of replacing, in ψ2, all literals with their negations (replace p with ¬p and ¬p with p). This will be a formula in CNF that is equivalent to ϕ. Suppose F denotes the set of well-formed formulas over Prop. We can formally define the last step as ψ3 = flip(ψ2) where flip : F → F, is recursively defined as follows: • flip(>) = > • flip(⊥) = ⊥ • flip(p) = ¬p for all p ∈ Prop • flip(¬p) = p for all p ∈ Prop 1 • flip(¬ϕ) = ¬flip(ϕ) for all formulas ϕ which are not propositional variables • For all formulas ϕ and ψ: – flip (ϕ ∧ ψ)
= flip(ϕ) ∧ flip(ψ)
– flip (ϕ ∨ ψ)
= flip(ϕ) ∨ flip(ψ)
– flip (ϕ → ψ)
= flip(ϕ) → flip(ψ)
– flip (ϕ ↔ ψ)
= flip(ϕ) ↔ flip(ψ)
(a) Recursively define a function dual : F → F so that the last two steps above process can be formally defined as flip ◦ dual(ψ1). (4 marks) (b) Prove that if ψ is in DNF then flip ◦ dual(ψ) is in CNF. (4 marks) (c) Prove that for all ϕ ∈ F, flip ◦ dual(¬ϕ) is logically equivalent to ϕ. (6 marks) Problem 4∗ (6 marks) Show that there are no three element Boolean Algebras. Problem 5 (22 marks) Consider the following arrangement of five houses in a cul-de-sac: For the purpose of this question we assume that: • House 1’s neighbours are House 5 and House 2, • House 2’s neighbours are House 1 and House 3, • House 3’s neighbours are House 2 and House 4, • House 4’s neighbours are House 3 and House 5, and • House 5’s neighbours are House 4 and House 1. 2 The neighbourhood has decided that they are going to paint their houses, but the painting must be done subject to the following rules: • Every house is to be painted either all red or all blue. • If two houses have the same colour, then they must be neighbours. Your task is to prove in two different ways that this cannot be done. (a) Formulate the problem as a problem in propositional logic. Remember to: (i) Define any propositional variables you need and indicate what propositions they represent. Hint: One sensible approach uses 10 variables (4 marks) (ii) Define any propositional formulas that are appropriate and indicate what propositions they represent. (4 marks) (iii) Indicate how you would solve the problem (or show that it cannot be done) using propositional logic. It is sufficient to explain the method, you do not need to provide a solution. (4 marks) (b) Formulate the problem as a problem in graph theory. Remember to: (i) Clearly define the vertices and edges of your graph. (4 marks) (ii) State the associated graph problem that you need to solve. (2 marks) (iii) Provide an argument that shows it cannot be done. (4 marks) Problem 6 (14 marks) In the same neighbourhood of the previous question there lives a cat. Each night the cat chooses a house to sleep at, based on where he slept the previous night, subject to the following rules: • If the cat slept at House 1 (the cat’s owner’s house), then he has a probability of 12 of staying there the next night, and a probability of 12 of moving to a different house. • If the cat slept at any other house, then he has a probability of 13 of staying there the next night, and a probability of 23 of moving to a different house. • If the cat chooses to move to a different house, then he will choose one of the neighbouring houses with equal probability. • At night 0, the cat slept at House 1. Let p1(n), p2(n), p3(n), p4(n), p5(n) be the probability that the cat sleeps at House 1, 2, 3, 4, or 5 (respec￾tively) on night n. So p1(0) = 1 and p2(0) = p3(0) = p4(0) = p5(0) = 0. (a) Express p1(n + 1), p2(n + 1), p3(n + 1), p4(n + 1), and p5(n + 1) in terms of p1(n), p2(n), p3(n), p4(n), and p5(n). (5 marks) (b) As n gets larger, each pi(n) converges to a single value (called the steady state) which can be deter￾mined by setting pi(n + 1) = pi(n) in the above equations. Determine the steady state probabilities for all Houses. (5 marks) 3 (c) Assume there is a single fence between any two neighbours. The distance between any two houses is the smallest number of fences that need to be crossed to get between the houses: for example the distance between House 2 and House 5 is 2 (fence between House 1 and House 2, and fence between House 1 and House 5). What is the expected distance from House 1 in the steady state? (4 marks) Remark This is an example of a Markov chain – a very useful model for stochastic processes. Problem 7 (20 marks) Recall from Assignment 2 the definition of a binary tree data structure: either an empty tree, or a node with two children that are trees. Let T(n) denote the number of binary trees with n nodes. For example T(3) = 5 because there are five binary trees with three nodes: (a) Using the recursive definition of a binary tree structure, or otherwise, derive a recurrence equation for T(n). (8 marks) A full binary tree is a non-empty binary tree where every node has either two non-empty children (i.e. is a fully-internal node) or two empty children (i.e. is a leaf). (b) Using observations from Assignment 2, or otherwise, explain why a full binary tree must have an odd number of nodes. (4 marks) (c) Let B(n) denote the number of full binary trees with n nodes. Derive an expression for B(n), involving T(n0) where n0 ≤ n. Hint: Relate the internal nodes of a full binary tree to T(n). (4 marks) A well-formed formula is in Negated normal form if it consists of just ∧, ∨, and literals (i.e. propositional variables or negations of propositional variables). For example, (p ∨ (¬q ∧ ¬r)) is in negated normal form; but (p ∨ ¬(q ∨ r)) is not. Let F(n) denote the number of well-formed, negated normal form formulas1 there are that use precisely n propositional variables exactly one time each. So F(1) = 2, F(2) = 16, and F(4) = 15360. (d) Using your answer for part (c), give an expression for F(n). (4 marks) Remark The T(n) are known as the Catalan numbers. As this question demonstrates they are very useful for counting various tree-like structures. 1Note: we do not assume ∧ and ∨ are associative 4 Advice on how to do the assignment Collaboration is encouraged, but all submitted work must be done individually without consulting someone else’s solutions in accordance with the University’s “Academic Dishonesty and Plagiarism” policies. • Assignments are to be submitted via WebCMS (or give) as a single pdf file. • When giving answers to questions, we always would like you to prove/explain/motivate your answers. You are being assessed on your understanding and ability. • Be careful with giving multiple or alternative answers. If you give multiple answers, then we will give you marks only for your worst answer, as this indicates how well you understood the question. • Some of the questions are very easy (with the help of external resources). You may make use of external material provided it is properly referenced2 – however, answers that depend too heavily on external resources may not receive full marks if you have not adequately demonstrated ability/understanding.