PFA
1. The half subtractor takes two binary bits ? and ? and calculates the difference ?, along with a “borrow bit” ? set to 1 when ? > ?. The full subtractor takes 3 inputs ?, ?, a “borrow in” bit ???, and produces a difference output ? and a “borrow out” bit, ????. ? ? ? ? 1 1 0 0 1 0 1 0 0 1 1 1 0 0 0 0 ? ? ??? ? ???? 1 1 1 1 1 1 1 0 0 0 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 0 (a) Explain the third row in the half subtractor table. (b) Write the formula for ???? (in the full subtractor) in disjunctive normal form, then find a minimal formula using Karnaugh maps. 2. Prove or disprove the equality ? + (? ⊕ ?) = (? + ?) ⊕ (? + ?) for the Boolean variables ?, ?, and ?. 3. Suppose that there are 5 members on a committee. Albert and Billy, for their own petty reasons, always vote the opposite of Charlie. Danielle and Evo vote how they please. Design a circuit that implements majority voting for this committee. 4. Let ? be the relation on integers with ? related to ? precisely when ? − ? is a multiple of 3. (a) Give 2 examples of integers that are related to 4. (b) Prove that the relation ? is an equivalence relation. (c) We denote the equivalence classes [0], [1] and [2] simply by the symbols 0, 1, and 2. Prove that 1 + 2 is well defined (in the sense that it is not ambiguous) and is equal to 0. [Note: what is meant by 1+2 is any element of the equivalence class 1 added to any element of the equivalence class 2.] 5. In lectures, we gave the following recursive definition of the function ?∶ ℕ → ℕ picking out the sequence of Fibonacci numbers 0,1,1,2,3,5,8,13,…: ?(0) = 0?(1) = 1and?(?) = ?(? − 1) + ?(? − 2) for ? ⩾ 2. The goal of this question is to prove that the following equality holds for every natural number ?: ?(0)2 + ?(1)2 + ⋯ + ?(?)2 = ?(?)?(? + 1) . (i) Verify that this equality holds for ? = 1,2,3,4. (You can use the values of ?(0),…,?(4) without needing to calculate them from scratch.) (ii) Write down a recursive definition of the function ?∶ ℕ → ℕ whose value at ? ∈ ℕ is ?(0)2 + ?(1)2 + ⋯ + ?(?)2. (iii) Use your answer to (ii) to give a careful proof by induction that ?(?) = ?(?)?(?+1) for all natural numbers ?. 6. In lectures, we considered the set ? of binary trees defined recursively by: · Base case: the trivial tree ? = • is in ?; · Recursive case: if ?1,?2 ∈ ? then so is the tree ?1 ∗ ?2 given by ?1 ∗ ?2 = ? 1 ? 2 We can define recursive functions ?∶ ? → ℕ and ?∶ ? → ℕ which respectively count the number of vertices and the number of edges of a binary tree. For ? we take: · Base case: ?(?) = 1; · Recursive case: ?(?1 ∗ ?2) = ?(?1) + ?(?2) + 1. For ? we take: · Base case: ?(?) = 0; · Recursive case: ?(?1 ∗ ?2) = ?(?1) + ?(?2) + 2. (i) Evaluate the functions ? and ? at the binary tree ? = (? ∗ ?) ∗ (? ∗ ?). Confirm your answers by drawing the binary tree represented by ?; it should have ?(?) vertices and ?(?) edges. (ii) [4 marks]. Prove by structural induction that, for all binary trees ?, we have ?(?) = ?(?) + 1.