HW3 Circuits and Logic

In this assignment,

You will consider how circuits and logic can be used to represent mathematical and technical claims. You will use propositional and predicate logic to evaluate these claims.

Instructions and academic integrity reminders for all homework assignments in CSE20 this quarter are on the class website and on the hw1-definitions-and-notations assignment.

You will submit this assignment via Gradescope (https://www.gradescope.com) in the assignment called “hw3-circuits-and-logic”.

Resources: To review the topics you are working with for this assignment, see the class material from Week 3 and Week 4. We will post frequently asked questions and our answers to them in a pinned Piazza post.

Assigned questions

1. Imagine a friend suggests the following argument to you: “The compound proposition \[(x \to y) \to z\] is logically equivalent to \[x \to (y \to z)\] because I can transform one to the other using the following sequence of logical equivalences like distributivity and associativity and using that \((p \to q) \equiv (\lnot p \lor q)\): \[(x \to y) \to z \equiv \lnot (\lnot x \lor y) \lor z \equiv \lnot x \lor (\lnot y \lor z) \equiv x \to (\lnot y \lor z) \equiv x \to (y \to z)\] so conditionals are associative just like conjunctions and disjunctions".

   1. (Graded for correctness¹) Prove to your friend that they made a mistake by giving a truth assignment to the propositional variables where the two compound propositions \((x \to y) \to z\) and \(x \to (y \to z)\) have different truth values. Justify your choice by evaluating these compound propositions using the definitions of the logical connectives and include enough intermediate steps so that a student in CSE 20 who may be struggling with the material can still follow along with your reasoning.

   2. (Graded for fair effort completeness²) Help your friend find the problem in their argument by pointing out which step(s) were incorrect.

   3. (Graded for fair effort completeness) Give three different compound propositions that are actually logically equivalent to (and not the same as) \[x \to (y \to z)\] Justify each one of these logical equivalences either by applying a sequence of logical equivalences or using a truth table. Notice that you can use other logical operators (e.g. \(\lnot, \lor, \land, \oplus, \to, \leftrightarrow\)) when constructing your compound propositions.

      Bonus; not for credit (do not hand in): How would you translate each of the equivalent compound propositions in English? Does doing so help illustrate why they are equivalent?

2. For each part of this question you will use the following input-output definition table with four inputs \(x_3\), \(x_2\), \(x_1\), \(x_0\)

   \(x_3\)	\(x_2\)	\(x_1\)	\(x_0\)	\(out\)
   \(1\)	\(1\)	\(1\)	\(1\)	\(1\)
   \(1\)	\(1\)	\(1\)	\(0\)	\(0\)
   \(1\)	\(1\)	\(0\)	\(1\)	\(0\)
   \(1\)	\(1\)	\(0\)	\(0\)	\(0\)
   \(1\)	\(0\)	\(1\)	\(1\)	\(0\)
   \(1\)	\(0\)	\(1\)	\(0\)	\(1\)
   \(1\)	\(0\)	\(0\)	\(1\)	\(0\)
   \(1\)	\(0\)	\(0\)	\(0\)	\(0\)
   \(0\)	\(1\)	\(1\)	\(1\)	\(0\)
   \(0\)	\(1\)	\(1\)	\(0\)	\(0\)
   \(0\)	\(1\)	\(0\)	\(1\)	\(1\)
   \(0\)	\(1\)	\(0\)	\(0\)	\(0\)
   \(0\)	\(0\)	\(1\)	\(1\)	\(0\)
   \(0\)	\(0\)	\(1\)	\(0\)	\(0\)
   \(0\)	\(0\)	\(0\)	\(1\)	\(0\)
   \(0\)	\(0\)	\(0\)	\(0\)	\(1\)

   1. (Graded for fair effort completeness) Construct a compound proposition that implements this input-output table and draw a combinatorial circuit corresponding to this compound proposition. We recommend the following steps:

      • Draw symbols for the inputs on the left-hand-side and for the output on the right-hand side.

      • Construct an expression for \(out\) using (some of) the inputs \(x_3, x_2, x_1, x_0\) and the logic gates XOR, AND, OR, NOT. Hint: are normal forms helpful here? How do you choose which normal form to use?

      • Draw and label the gates corresponding to the expression you construct, and connect appropriately with wires.

   2. (Graded for correctness) For each of the following predicates, consider whether this input-output table (and the logic circuit from part (a)) implements the rule for the predicate. If yes, explain why using the definitions of the operations involved and consider all possible inputs. If no, explain why not by providing specific example input values and using the input-output definition table to compute the logic circuit’s output for this example input and then comparing with the value of the predicate in question to justify your example.

      1. \(P_1: \{0,1\}\times \{0,1\} \times \{0,1\} \times \{0,1\} \to \{T, F\}\) given by \[P_1(~(x_3,x_2,x_1,x_0)~) = \begin{cases} T \quad &\text{when~}(x_3x_2x_1x_0)_{2,4} \leq 5 \\ F &\text{otherwise}\end{cases}\]

      2. \(P_2: \{0,1\}\times \{0,1\} \times \{0,1\} \times \{0,1\} \to \{T, F\}\) given by \[P_2(~(x_3,x_2,x_1,x_0)~) = \begin{cases} T \quad &\text{when~} (x_3x_2x_1x_0)_{2,4} \textbf{ mod } 5 = 0 \\ F &\text{otherwise}\end{cases}\]

      3. \(P_3: \{0,1\}\times \{0,1\} \times \{0,1\} \times \{0,1\} \to \{T, F\}\) given by \[P_3(~(x_3,x_2,x_1,x_0)~) = \begin{cases} T \quad &\text{when~} (x_3x_2x_1x_0)_{2,4} = [x_3x_2x_1x_0]_{s,4} \\ F &\text{otherwise}\end{cases}\]

3. Recall the functions mutation, insertion, and deletion defined in class. We define the predicates:

   \(Mut\) with domain \(S \times S\) is defined by, for \(s_1 \in S\) and \(s_2 \in S\), \[Mut(~(s_1,s_2)~) = \exists k\in \mathbb{Z^+} \exists b \in B (~ mutation(~(s_1, k, b)~) = s_2~)\] \(Ins\) with domain \(S \times S\) is defined by, for \(s_1 \in S\) and \(s_2 \in S\), \[Ins(~(s_1,s_2)~) = \exists k\in \mathbb{Z^+} \exists b \in B (~ insertion(~(s_1, k, b)~) = s_2~)\] \(Del\) with domain \(\{ s\in S \mid rnalen(s) > 1\} \times S\) is defined by, for \(s_1 \in \{ s\in S \mid rnalen(s) > 1\}\) and \(s_2 \in S\), \[Del(~(s_1,s_2)~) = \exists k\in \mathbb{Z^+} (~ deletion(~(s_1, k)~) = s_2~)\]

   For each quantified statement below, first translate to an English sentence.

   Then, negate the whole statement and rewrite this negated statement so that negations appear only within predicates (that is, so that no negation is outside a quantifier or an expression involving logical connectives).

   The translations are graded for fair effort completeness.

   The negations are graded for correctness. For negations: You do not need to justify your work for this part of the question. However, if you include correct intermediate steps, we might be able to award partial credit for an incorrect answer.

   ---

   Sample response that can be used as reference for the detail expected in your answer: Consider the statement \[\hspace{-1in}\forall n \in \mathbb{Z}^+~ \exists s \in S~\left( ~L(~(s,n)~) \land F_\texttt{A}(s) \land BC(~(s,\texttt{A},n)~)~\right)\]

   Solution: English translation is

   For each positive integer there is some RNA strand of that length that starts with A  and all of its bases are A.

   We obtain the negation using multiple applications of De Morgan’s rule and logical equivalences. \[\begin{aligned} \lnot &\forall n \in \mathbb{Z}^+~ \exists s \in S~\left( ~L(~(s,n)~) \land F_\texttt{A}(s) \land BC(~(s,\texttt{A},n)~)~\right) \\ \equiv&\exists n \in \mathbb{Z}^+~ \lnot \exists s \in S~\left( ~L(~(s,n)~) \land F_\texttt{A}(s) \land BC(~(s,\texttt{A},n)~)~\right) \\ \equiv&\exists n \in \mathbb{Z}^+~ \forall s \in S~\lnot \left( ~L(~(s,n)~) \land F_\texttt{A}(s) \land BC(~(s,\texttt{A},n)~)~\right) \\ \equiv&\exists n \in \mathbb{Z}^+~ \forall s \in S~\left( ~\lnot L(~(s,n)~) \lor \lnot F_\texttt{A}(s) \lor \lnot BC(~(s,\texttt{A},n)~)~\right) \end{aligned}\]

   ---

   1. First statement: \[\forall s \in S ~\left( ~Mut(~(s,s)~) \leftrightarrow Ins(~(s,s)~) ~\right)\]

   2. Second statement \[\forall s_1 \in S ~ \forall s_2 \in S ~\forall s_3 \in S ~\left( ~\left(~Mut(~(s_1,s_2)~) \land Mut(~(s_2, s_3)~) ~\right) \to Mut(~(s_1,s_3)~)~\right)\]

   3. Third statement: we use \(S'\) to abbreviate \(\{ s\in S \mid rnalen(s) > 1\}\) \[\forall s_2 \in S' ~\exists s_1 \in S'~\left(~ Del(~(s_1,s_2)~)~\right) \land \lnot \forall s_1 \in S' ~\exists s_2 \in S'~\left(~ Del(~(s_1,s_2)~)~\right)\]

   Bonus; not for credit (do not hand in): For each statement above, is the statement or its negation true? How do you know?