Real-life representations are often prone to corruption. Biological codes, like RNA, may mutate naturally1 and during measurement; cosmic radiation and other ambient noise can flip bits in computer storage2. One way to recover from corrupted data is to introduce or exploit redundancy.
Consider the following algorithm to introduce redundancy in a string of \(0\)s and \(1\)s.
procedure \(\textit{redun3}\)(\(a_{k-1} \cdots a_0\): a nonempty bitstring) for \(i\) := \(0\) to \(k-1\) \(c_{3i}\) := \(a_i\) \(c_{3i+1}\) := \(a_i\) \(c_{3i+2}\) := \(a_i\) return \(c_{3k-1} \cdots c_0\)
procedure \(\textit{decode3}\)(\(c_{3k-1} \cdots c_0\): a nonempty bitstring whose length is an integer multiple of \(3\)) for \(i\) := \(0\) to \(k-1\) if exactly two or three of \(c_{3i}, c_{3i+1}, c_{3i+2}\) are set to \(1\) \(a_i\) := 1 else \(a_i\) := 0 return \(a_{k-1} \cdots a_0\)
Give a recursive definition of the set of outputs of the \(redun3\) procedure, \(Out\),
Consider the message \(m = 0001\) so that the sender calculates \(redun3(m) = redun3(0001) = 000000000111\).
Introduce \(\underline{\phantom{~~4~~}}\) errors into the message so that the signal received by the receiver is \(\underline{\phantom{010100010101}}\) but the receiver is still able to decode the original message.
Challenge: what is the biggest number of errors you can introduce?
Building a circuit for lines 3-6 in \(decode\) procedure: given three input bits, we need to determine whether the majority is a \(0\) or a \(1\).
2
| \(c_{3i}\) | \(c_{3i+1}\) | \(c_{3i+2}\) | \(a_i\) |
|---|---|---|---|
| \(1\) | \(1\) | \(1\) | \(\phantom{1}\) |
| \(1\) | \(1\) | \(0\) | \(\phantom{1}\) |
| \(1\) | \(0\) | \(1\) | \(\phantom{1}\) |
| \(1\) | \(0\) | \(0\) | \(\phantom{0}\) |
| \(0\) | \(1\) | \(1\) | \(\phantom{1}\) |
| \(0\) | \(1\) | \(0\) | \(\phantom{0}\) |
| \(0\) | \(0\) | \(1\) | \(\phantom{0}\) |
| \(0\) | \(0\) | \(0\) | \(\phantom{0}\) |
Circuit
Definition: The Cartesian product of the sets \(A\) and \(B\), \(A \times B\), is the set of all ordered pairs \((a, b)\), where \(a \in A\) and \(b \in B\). That is: \(A \times B = \{(a, b) \mid (a \in A) \land (b \in B)\}\). The Cartesian product of the sets \(A_1, A_2, \ldots ,A_n\), denoted by \(A_1 \times A_2 \times \cdots \times A_n\), is the set of ordered n-tuples \((a_1, a_2,...,a_n)\), where \(a_i\) belongs to \(A_i\) for \(i = 1, 2,\ldots,n\). That is, \[A_1 \times A_2 \times \cdots \times A_n = \{(a_1, a_2,\ldots,a_n) \mid a_i \in A_i \textrm{ for } i = 1, 2,\ldots,n\}\]
Recall that \(S\) is defined as the set of all RNA strands, nonempty strings made of the bases in \(B = \{\texttt{A},\texttt{U},\texttt{G},\texttt{C}\}\). We define the functions \[\textit{mutation}: S \times \mathbb{Z}^+ \times B \to S \qquad \qquad \textit{insertion}: S \times \mathbb{Z}^+ \times B \to S\] \[\textit{deletion}: \{ s\in S \mid rnalen(s) > 1\} \times \mathbb{Z}^+ \to S \qquad \qquad \textrm{with rules}\]
procedure \(\textit{mutation}\)(\(b_1\cdots b_n\): \(\textrm{a RNA strand}\), \(k\): \(\textrm{a positive integer}\), \(b\): \(\textrm{an element of } B\)) for \(i\) := \(1\) to \(n\) if \(i\) = \(k\) \(c_i\) := \(b\) else \(c_i\) := \(b_i\) return \(c_1\cdots c_n\) \(\{ \textrm{The return value is a RNA strand made of the } c_i \textrm{ values}\}\)
procedure \(\textit{insertion}\)(\(b_1\cdots b_n\): \(\textrm{a RNA strand}\), \(k\): \(\textrm{a positive integer}\), \(b\): \(\textrm{an element of } B\)) if \(k > n\) for \(i\) := \(1\) to \(n\) \(c_i\) := \(b_i\) \(c_{n+1}\) := \(b\) else for \(i\) := \(1\) to \(k-1\) \(c_i\) := \(b_i\) \(c_k\) := \(b\) for \(i\) := \(k+1\) to \(n+1\) \(c_i\) := \(b_{i-1}\) return \(c_1\cdots c_{n+1}\) \(\{ \textrm{The return value is a RNA strand made of the } c_i \textrm{ values}\}\)
procedure \(\textit{deletion}\)(\(b_1\cdots b_n\): \(\textrm{a RNA strand with } n>1\), \(k\): \(\textrm{a positive integer}\)) if \(k > n\) \(m\) := \(n\) for \(i\) := \(1\) to \(n\) \(c_i\) := \(b_i\) else \(m\) := \(n-1\) for \(i\) := \(1\) to \(k-1\) \(c_i\) := \(b_i\) for \(i\) := \(k\) to \(n-1\) \(c_i\) := \(b_{i+1}\) return \(c_1\cdots c_m\) \(\{ \textrm{The return value is a RNA strand made of the } c_i \textrm{ values}\}\)
Trace the pseudocode to find the output of \(\textit{mutation}(~ (\texttt{A}\texttt{U}\texttt{C}, 3, \texttt{G}) ~)\)
Fill in the blanks so that \(\textit{insertion}(~(\texttt{A}\texttt{U}\texttt{C}, \underline{\phantom{3}}, \underline{\phantom{\texttt{G}}})~) = \texttt{A}\texttt{U}\texttt{C}\texttt{G}\)
Fill in the blanks so that \(\textit{deletion}(~(\underline{\phantom{\texttt{G}\texttt{G}}}, \underline{\phantom{1}})~) = \texttt{G}\)
In this question, we will consider how to build a logic circuit with inputs \(x_0\), \(y_0\), \(x_1\), \(y_1\) and output \(z\) such that \(z = 1\) exactly when \((x_1x_0)_{2,2} < (y_1y_0)_{2,2}\) and \(z = 0\) exactly when \((x_1x_0)_{2,2} \geq (y_1y_0)_{2,2}\).
The first step towards designing this logic circuit is to construct its input-output table. How many rows does this table have (not including the header row labelling the columns)?
What is the output for the row whose input values are \(x_0 = 0\), \(y_0 = 1\), \(x_1 = 1\), \(y_1 = 0\)?
What is the output for the row whose input values are \(x_0 = 0\), \(y_0 = 1\), \(x_1 = 0\), \(y_1 = 1\)?
Recall the procedures \(redun3\) and \(decode3\) from class.
Give the output of \(redun3(100)\).
If the output of running \(redun3\) is \(000000111000111\), what was its input?
Give the output of \(decode3(100)\).
How many distinct possible inputs to \(decode3\) give the output \(01\)?
Recall the procedures \(mutation\) and \(insertion\) and \(deletion\) from class.
Trace the pseudocode to find the output of \(\textit{mutation}(~ (\texttt{A}\texttt{U}\texttt{C}, 2, \texttt{U}) ~)\)
Trace the pseudocode to find the output of \(\textit{insertion}(~(\texttt{A}\texttt{U}\texttt{C}, 1, \texttt{G})~)\)
Trace the pseudocode to find the output of \(\textit{deletion}(~(\texttt{A}\texttt{U}\texttt{C}, 1)~)\)
Definition: A predicate is a function from a given set (domain) to \(\{T,F\}\).
A predicate can be applied, or evaluated at, an element of the domain.
Usually, a predicate describes a property that domain elements may or may not have.
Two predicates over the same domain are equivalent means they evaluate to the same truth values for all possible assignments of domain elements to the input. In other words, they are equivalent means that they are equal as functions.
To define a predicate, we must specify its domain and its value at each domain element. The rule assigning truth values to domain elements can be specified using a formula, English description, in a table (if the domain is finite), or recursively (if the domain is recursively defined).
| Input | Output | ||
| \(V(x)\) | \(N(x)\) | \(Mystery(x)\) | |
| \(x\) | \([x]_{2c,3} > 0\) | \([x]_{2c,3} < 0\) | |
| \(000\) | \(F\) | \(T\) | |
| \(001\) | \(T\) | \(T\) | |
| \(010\) | \(T\) | \(T\) | |
| \(011\) | \(T\) | \(F\) | |
| \(100\) | \(F\) | \(F\) | |
| \(101\) | \(F\) | \(T\) | |
| \(110\) | \(F\) | \(F\) | |
| \(111\) | \(F\) | \(T\) | |
The domain for each of the predicates \(V(x)\), \(N(x)\), \(Mystery(x)\) is .
Fill in the table of values for the predicate \(N(x)\) based on the formula given.
Definition: The truth set of a predicate is the collection of all elements in its domain where the predicate evaluates to \(T\).
Notice that specifying the domain and the truth set is sufficient for defining a predicate.
The truth set for the predicate \(V(x)\) is \(\underline{\phantom{\{ x ~\mid~ V(x) = T\} = \{ 001, 010, 011 \}}}\).
The truth set for the predicate \(N(x)\) is \(\underline{\phantom{\{ x ~\mid~ N(x) = T\} = \{ 101, 111 \}}}\).
The truth set for the predicate \(Mystery(x)\) is \(\underline{\phantom{\{ x ~\mid~ Mystery(x) = T\} = \{ 000, 001, 010, 101, 111 \}}}\).
The universal quantification of predicate \(P(x)\) over domain \(U\) is the statement “\(P(x)\) for all values of \(x\) in the domain \(U\)” and is written \(\forall x P(x)\) or \(\forall x \in U ~P(x)\). When the domain is finite, universal quantification over the domain is equivalent to iterated conjunction (ands).
The existential quantification of predicate \(P(x)\) over domain \(U\) is the statement “There exists an element \(x\) in the domain \(U\) such that \(P(x)\)” and is written \(\exists x P(x)\) for \(\exists x \in U ~P(x)\). When the domain is finite, existential quantification over the domain is equivalent to iterated disjunction (ors).
An element for which \(P(x) = F\) is called a counterexample of \(\forall x P(x)\).
An element for which \(P(x) = T\) is called a witness of \(\exists x P(x)\).
Statements involving predicates and quantifiers are logically equivalent means they have the same truth value no matter which predicates (domains and functions) are substituted in.
Quantifier version of De Morgan’s laws: \(\boxed{\neg \forall x P(x) ~\equiv~ \exists x \left( \neg P(x) \right)}\) \(\boxed{\neg \exists x Q(x) ~\equiv~ \forall x \left( \neg Q(x) \right)}\)
Examples of quantifications using \(V(x), N(x), Mystery(x)\):
True or False: \(\exists x~ (~V(x) \land N(x)~)\)
True or False: \(\forall x~ (~V(x) \to N(x)~)\)
True or False: \(\exists x~ (~N(x) \leftrightarrow Mystery(x)~)\)
Rewrite \(\lnot \forall x~(~V(x) \oplus Mystery(x)~)\) into a logical equivalent statement.
Notice that these are examples where the predicates have finite domain. How would we evaluate quantifications where the domain may be infinite?
Example predicates on \(S\), the set of RNA strands (an infinite set)
\(H: S \to \{T, F\}\) where \(H(s) = T\) for all \(s\).
Truth set of \(H\) is
\(F_{\texttt{A}}: S \to \{T, F\}\)
defined recursively by:
Basis step: \(F_{\texttt{A}}(\texttt{A}) = T\), \(F_{\texttt{A}}(\texttt{C}) = F_{\texttt{A}}(\texttt{G}) = F_{\texttt{A}}(\texttt{U}) = F\)
Recursive step: If \(s \in S\) and \(b \in B\), then \(F_{\texttt{A}}(sb) = F_{\texttt{A}}(s)\).
Example where \(F_{\texttt{A}}\) evaluates to \(T\) is
Example where \(F_{\texttt{A}}\) evaluates to \(F\) is
Recall the predicates \(V(x)\), \(N(x)\), and \(Mystery(x)\) on domain \(\{000,001,010,011,100,101,110,111\}\) from class. Which of the following is true? (Select all and only that apply.)
\(\left( \forall x ~V(x) \right) \lor \left( \forall x ~N(x) \right)\)
\(\left( \exists x ~V(x) \right) \land \left( \exists x~N(x) \right) \land \left( \exists x~Mystery(x)\right)\)
\(\exists x ~(~V(x) \land N(x) \land Mystery(x)~)\)
\(\forall x ~(~V(x) \oplus N(x)~)\)
\(\forall x ~(~Mystery(x) \to V(x)~)\)
Consider the following predicates, each of which has as its domain the set of all bitstrings whose leftmost bit is \(1\)
\(E(x)\) is \(T\) exactly when \((x)_{2}\) is even, and is \(F\) otherwise
\(L(x)\) is \(T\) exactly when \((x)_2 < 3\), and is \(F\) otherwise
\(M(x)\) is \(T\) exactly when \((x)_2 > 256\) and is \(F\) otherwise.
What is \(E(110)\)?
Why is \(L(00)\) undefined?
Because the domain of \(L\) is infinite
Because \(00\) does not have \(1\) in the leftmost position
Because \(00\) has length 2, not length 3
Because \((00)_{2,2} = 0\) which is less than \(3\)
Is there a bitstring of width (where width is the number of bits) \(6\) at which \(M(x)\) evaluates to \(T\)?
For this question, we will use the following predicate.
\(F_{\texttt{A}}\) with domain \(S\) is defined recursively by:
Basis step: \(F_{\texttt{A}}(\texttt{A}) = T\), \(F_{\texttt{A}}(\texttt{C}) = F_{\texttt{A}}(\texttt{G}) = F_{\texttt{A}}(\texttt{U}) = F\)
Recursive step: If \(s \in S\) and \(b \in B\), then \(F_{\texttt{A}}(sb) = F_{\texttt{A}}(s)\)
Which of the following is true? (Select all and only that apply.)
\(F_\texttt{A}( \texttt{A}\texttt{A})\)
\(F_\texttt{A}( \texttt{A}\texttt{C})\)
\(F_\texttt{A}( \texttt{A}\texttt{G})\)
\(F_\texttt{A}( \texttt{A}\texttt{U})\)
\(F_\texttt{A}( \texttt{C}\texttt{A})\)
\(F_\texttt{A}( \texttt{C}\texttt{C})\)
\(F_\texttt{A}( \texttt{C}\texttt{G})\)
\(F_\texttt{A}( \texttt{C}\texttt{U})\)
Recall the definitions: The set of RNA strands \(S\) is defined (recursively) by: \[\begin{array}{ll} \textrm{Basis Step: } & \texttt{A}\in S, \texttt{C}\in S, \texttt{U}\in S, \texttt{G}\in S \\ \textrm{Recursive Step: } & \textrm{If } s \in S\textrm{ and }b \in B \textrm{, then }sb \in S \end{array}\] where \(sb\) is string concatenation.
The function rnalen that computes the length of RNA strands in \(S\) is defined recursively by: \[\begin{array}{llll} & & \textit{rnalen} : S & \to \mathbb{Z}^+ \\ \textrm{Basis Step:} & \textrm{If } b \in B\textrm{ then } & \textit{rnalen}(b) & = 1 \\ \textrm{Recursive Step:} & \textrm{If } s \in S\textrm{ and }b \in B\textrm{, then } & \textit{rnalen}(sb) & = 1 + \textit{rnalen}(s) \end{array}\]
The function basecount that computes the number of a given base \(b\) appearing in a RNA strand \(s\) is defined recursively by: \[\begin{array}{llll} & & \textit{basecount} : S \times B & \to \mathbb{N} \\ \textrm{Basis Step:} & \textrm{If } b_1 \in B, b_2 \in B & \textit{basecount}(~(b_1, b_2)~) & = \begin{cases} 1 & \textrm{when } b_1 = b_2 \\ 0 & \textrm{when } b_1 \neq b_2 \\ \end{cases} \\ \textrm{Recursive Step:} & \textrm{If } s \in S, b_1 \in B, b_2 \in B &\textit{basecount}(~(s b_1, b_2)~) & = \begin{cases} 1 + \textit{basecount}(~(s, b_2)~) & \textrm{when } b_1 = b_2 \\ \textit{basecount}(~(s, b_2)~) & \textrm{when } b_1 \neq b_2 \\ \end{cases} \end{array}\]
Using functions to define predicates:
Example where \(L\) evaluates to \(T\): \(\underline{\phantom{(\texttt{A}, 1)\hspace{1in}}}\) Why?
Example where \(BC\) evaluates to \(T\): \(\underline{\phantom{(\texttt{A}, \texttt{A}1)\hspace{1in}}}\) Why?
Example where \(L\) evaluates to \(F\): \(\underline{\phantom{(\texttt{A}, 2)\hspace{1in}}}\) Why?
Example where \(BC\) evaluates to \(F\): \(\underline{\phantom{(\texttt{A}, \texttt{C}, 1)\hspace{1in}}}\) Why?
New predicates from old
Define the new predicate with
domain \(S \times B\) and rule \[basecount(~(s,b)~) = 3\] Example domain
element where predicate is \(T\):
Define the new predicate with
domain \(S \times \mathbb{N}\) and rule
\[basecount(~(s,\texttt{A})~) = n\]
Example domain element where predicate is \(T\):
Define the new predicate with
domain \(S \times B\) and rule \[\exists n \in \mathbb{N} ~(basecount(~(s,b)~) =
n)\] Example domain element where predicate is \(T\):
Define the new predicate with
domain \(S\) and rule \[\forall b \in B ~(basecount(~(s,b)~) =
1)\] Example domain element where predicate is \(T\):
Notation: for a predicate \(P\) with domain \(X_1 \times \cdots \times X_n\) and a \(n\)-tuple \((x_1, \ldots, x_n)\) with each \(x_i \in X\), we can write \(P(x_1, \ldots, x_n)\) to mean \(P( ~(x_1, \ldots, x_n)~)\).
Nested quantifiers
Alternating nested quantifiers
Recall the predicate \(L\) with domain \(S \times \mathbb{Z}^+\) from class, \(L(~(s,n)~)\) means \(rnalen(s) = n\). Which of the following is true? (Select all and only that apply.)
\(\exists s \in S ~\exists n \in \mathbb{Z}^+ ~L(~(s,n)~)\)
\(\exists s \in S ~\forall n \in \mathbb{Z}^+ ~L(~(s,n)~)\)
\(\forall n \in \mathbb{Z}^+ ~\exists s \in S ~L(~(s,n)~)\)
\(\forall s \in S ~\exists n \in \mathbb{Z}^+ ~L(~(s,n)~)\)
\(\exists n \in \mathbb{Z}^+ ~\forall s \in S ~L(~(s,n)~)\)
Recall the predicate \(BC\) with domain \(S \times B \times \mathbb{N}\) from class, \(BC(~(s,b,n)~)\) means \(basecount(~(s,b)~) = n\). Match each sentence to its English translation, or select none of the above.
\(\forall s \in S ~\exists n \in \mathbb{N} ~\forall b \in B ~basecount(~(s,b)~) = n\)
\(\forall s \in S ~\forall b \in B ~\exists n \in \mathbb{N} ~basecount(~(s,b)~) = n\)
\(\forall s \in S ~\forall n \in \mathbb{N} ~\exists b \in B ~basecount(~(s,b)~) = n\)
\(\forall b \in B ~\forall n \in \mathbb{N} ~\exists s \in S ~basecount(~(s,b)~) = n\)
\(\forall n \in \mathbb{N} ~\forall b \in B ~\exists s \in S ~basecount(~(s,b)~) = n\)
For each RNA strand and each possible base, the number of that base in that strand is a nonnegative integer.
For each RNA strand and each nonnegative integer, there is a base that occurs this many times in this strand.
Every RNA strand has the same number of each base, and that number is a nonnegative integer.
For every given nonnegative integer, there is a strand where each possible base appears the given number of times.
For every given base and nonnegative integer, there is an RNA strand that has this base occurring this many times.
Challenge: Express symbolically
There are (at least) two different RNA strands that have the same number of \(\texttt{A}\)s.
Mutations of specific RNA codons have been linked to many disorders and cancers.↩︎
This RadioLab podcast episode goes into more detail on bit flips: https://www.wnycstudios.org/story/bit-flip↩︎