Clearly and unambiguously communicate computational ideas using appropriate formalism. Translate across levels of abstraction.
Translating between symbolic and English versions of statements using precise mathematical language
Using appropriate signpost words to improve readability of proofs, including ‘arbitrary’ and ‘assume’
Know, select and apply appropriate computing knowledge and problem-solving techniques. Reason about computation and systems. Use mathematical techniques to solve problems. Determine appropriate conceptual tools to apply to new situations. Know when tools do not apply and try different approaches. Critically analyze and evaluate candidate solutions.
Judging logical equivalence of compound propositions using symbolic manipulation with known equivalences, including DeMorgan’s Law
Writing the converse, contrapositive, and inverse of a given conditional statement
Determining what evidence is required to establish that a quantified statement is true or false
Evaluating quantified statements about finite and infinite domains
Apply proof strategies, including direct proofs and proofs by contradiction, and determine whether a proposed argument is valid or not.
Identifying the proof strategies used in a given proof
Identifying which proof strategies are applicable to prove a given compound proposition based on its logical structure
Carrying out a given proof strategy to prove a given statement
Carrying out a universal generalization argument to prove that a universal statement is true
Using proofs as knowledge discovery tools to decide whether a statement is true or false
Test 1 Attempt 1 in the CBTF this week at your scheduled time!
You must present a physical university-issued or government-issued ID. Copies, photos, or digital IDs are not accepted, and students without verifiable ID will not be permitted to test.
Pockets must be empty upon entry. Students may bring only their ID and a pen or pencil into the testing center.
Review quiz based on Week 4 class material (due Friday 02/06/2026)
Midquarter feedback: please let us know what’s working well for you and what isn’t. https://canvas.ucsd.edu/courses/71479/quizzes
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}\]
Alternating nested quantifiers
\[\forall s \in S ~\exists n \in \mathbb{N} ~(~basecount(~(s,\texttt{U})~) = n~)\]
In English: For each strand, there is a nonnnegative integer that
counts the number of occurrences of \(\texttt{U}\) in that strand.
\[\exists n \in \mathbb{N} ~\forall s \in S
~(~basecount(~(s,\texttt{U})~) = n~)\]
In English: There is a nonnnegative integer that counts the number of
occurrences of \(\texttt{U}\) in every
strand.
Are these statements true or false?
\[\forall s \in S ~\exists b\in B ~(~basecount(~(s,b)~) = 3~)\]
In English: For each RNA strand there is a base that occurs 3 times
in this strand.
Write the negation and use De Morgan’s law to find a logically
equivalent version where the negation is applied only to the \(BC\) predicate (not next to a
quantifier).
Is the original statement True or False?
When a predicate \(P(x)\) is over a finite domain:
To show that \(\forall x P(x)\) is true: check that \(P(x)\) evaluates to \(T\) at each domain element by evaluating over and over. This is called “Proof of universal by exhaustion".
To show that \(\forall x P(x)\) is false: find a counterexample, a domain element where \(P(x)\) evaluates to \(F\).
To show that \(\exists x P(x)\) is true: find a witness, a domain element where \(P(x)\) evaluates to \(T\).
To show that \(\exists x P(x)\) is false: check that \(P(x)\) evaluates to \(F\) at each domain element by evaluating over and over. DeMorgan’s Law gives that \(\lnot \exists x P(x) ~~\equiv~~ \forall x \lnot P(x)\) so this amounts to a proof of universal by exhaustion.
Suppose \(P(x)\) is a predicate over a domain \(D\).
To translate the statement “There are at least two elements in \(D\) where the predicate \(P\) evaluates to true", we could write \[\exists x_1 \in D \, \exists x_2 \in D \, (P(x_1) \wedge P(x_2) \wedge \overline{\text{FILL IN BLANK}})\]
To translate the statement “There are at most two elements in \(D\) where the predicate \(P\) evaluates to true", we could write \[\forall x_1 \in D \, \forall x_2 \in D \, \forall x_3 \in D \, \left(~ (~P(x_1) \wedge P(x_2) \wedge P(x_3) ~) \to (~ x_1 = x_2 \vee x_2 = x_3 \vee x_1 = x_3~)~\right)\] Why?
Definitions:
A set is an unordered collection of elements. When \(A\) and \(B\) are sets, \(A = B\) (set equality) means \[\forall x ( x\in A \leftrightarrow x \in B)\]
When \(A\) and \(B\) are sets, \(A \subseteq B\) (“\(A\) is a subset of \(B\)") means \[\forall x (x \in A \to x \in B)\]
When \(A\) and \(B\) are sets, \(A \subsetneq B\) (“\(A\) is a proper subset of \(B\)") means \[(A\subseteq B) \wedge (A \neq B)\]
To prove that one set is a subset of another, e.g. to show \(A \subseteq B\):
To prove that two sets are equal, e.g. to show \(A = B\):
Example: \(\{ 43, 7, 9 \} = \{ 7, 43, 9, 7\}\)
Prove or disprove: \(\{ \texttt{A}, \texttt{C}, \texttt{U}, \texttt{G}\} \subseteq \{ \texttt{A}\texttt{A}, \texttt{A}\texttt{C}, \texttt{A}\texttt{U}, \texttt{A}\texttt{G}\}\)
Prove or disprove: For some set \(B\), \(\emptyset \in B\).
Prove or disprove: For every set \(B\), \(\emptyset \in B\).
Prove or disprove: The empty set is a subset of every set.
Prove or disprove: The empty set is a proper subset of every set.
Prove or disprove: \(\{ 4, 6 \} \subseteq \{ n \mid \exists c \in \mathbb{Z} ( n = 4c) \}\)
Prove or disprove: \(\{ 4, 6 \} \subseteq \{ n ~\textbf{mod}~10 \mid \exists c \in \mathbb{Z} ( n = 4c) \}\)
Cartesian product: When \(A\) and \(B\) are sets, \[A \times B = \{ (a,b) \mid a \in A \wedge b \in B \}\]
Example: \(\{43, 9\} \times \{9, \mathbb{Z}\} =\)
Example: \(\mathbb{Z} \times \emptyset =\)
Union: When \(A\) and \(B\) are sets, \[A \cup B = \{ x \mid x \in A \vee x \in B \}\]
Example: \(\{43, 9\} \cup \{9, \mathbb{Z}\} =\)
Example: \(\mathbb{Z} \cup \emptyset =\)
Intersection: When \(A\) and \(B\) are sets, \[A \cap B = \{ x \mid x \in A \wedge x \in B \}\] Example: \(\{43, 9\} \cap \{9,\mathbb{Z}\} =\)
Example: \(\mathbb{Z} \cap \emptyset =\)
Set difference: When \(A\) and \(B\) are sets,
\[A - B = \{ x \mid x \in A \wedge x \notin B \}\]
Example: \(\{43, 9\} - \{9, \mathbb{Z}\} =\)
Example: \(\mathbb{Z} - \emptyset =\)
Disjoint sets: sets \(A\) and \(B\) are disjoint means \(A \cap B = \emptyset\)
Example: \(\{43, 9\}, \{9, \mathbb{Z}\}\) are not disjoint
Example: The sets \(\mathbb{Z}\) and \(\emptyset\) are disjoint
Power set: When \(U\) is a set, \(\mathcal{P}(U) = \{ X \mid X \subseteq U\}\)
Example: \(\mathcal{P}(\{43, 9\}) =\)
Example: \(\mathcal{P}(\emptyset) =\)
Let \(W = \mathcal{P}( \{ 1,2,3,4,5\} )\)
Example elements in \(W\) are:
Prove or disprove: \(\forall A \in W\, \forall B \in W\, \left( A \subseteq B ~\to ~ \mathcal{P}(A) \subseteq \mathcal{P}(B) \right)\)
Prove or disprove: \(\forall A \in W\, \forall B \in W\, \left( \mathcal{P}(A) =\mathcal{P}(B) ~\to ~ A = B \right)\)
Prove or disprove: \(\forall A \in W\, \forall B \in W\, \forall C \in W\, \left( A\cup B = A \cup C ~\to ~ B = C \right)\)