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.
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 in the CBTF this week at your scheduled time! You will be required to show a physical photo identification in order to test. Electronic IDs and photos of IDs are not accepted. Additionally, you will only be allowed to bring your ID and a writing utensil into the testing room. You will have to store away all of your other belongings before entering the room. Please see the Triton Testing Center’s website for more details.
Review quiz based on Week 4 class material (due Monday)
Midquarter feedback: please let us know what’s working well for you and what isn’t. https://canvas.ucsd.edu/courses/77744/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?
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 \underline{\phantom{\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?
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.
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 \(Y\), \(\emptyset \in Y\).
Prove or disprove: For every set \(Y\), \(\emptyset \in you\).
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)\)
We now have propositional and predicate logic that can help us express statements about any domain. We will develop proof strategies to craft valid argument for proving that such statements are true or disproving them (by showing they are false). We will practice these strategies with statements about sets and numbers, both because they are familiar and because they can be used to build cryptographic systems. Then we will apply proof strategies more broadly to prove statements about data structures and machine learning applications.
Addition and multiplication of real numbers are each commutative and associative.
The product of two positive numbers is positive, of two negative numbers is positive, and of a positive and a negative number is negative.
The sum of two integers, the product of two integers, and the difference between two integers are each integers.
For every integer \(x\) there is no integer strictly between \(x\) and \(x+1\),
When \(x, y\) are positive integers, \(xy \geq x\) and \(xy \geq y\).
Definition: When \(a\) and \(b\) are integers and \(a\) is nonzero, \(a\) divides \(b\) means there is an integer \(c\) such that \(b = ac\) .
Symbolically, \(F(~(a,b)~) = \phantom{\exists c\in \mathbb{Z}~(b=ac)}\) and is a predicate over the domain
Other (synonymous) ways to say that \(F(~(a,b)~)\) is true:
\(a\) is a factor of \(b\) \(a\) is a divisor of \(b\) \(b\) is a multiple of \(a\) \(a | b\)
When \(a\) is a positive integer and \(b\) is any integer, \(a | b\) exactly when \(b \textbf{ mod } a = 0\)
When \(a\) is a positive integer and \(b\) is any integer, \(a | b\) exactly when \(b = a \cdot (b \textbf{ div } a)\)
Translate these quantified statements by matching to English statement on right.
2 \(\exists a\in \mathbb{Z}^{\neq 0} ~(~F(~(a,a)~)~)\)
\(\exists a\in \mathbb{Z}^{\neq 0} ~(~\lnot F(~(a,a)~)~)\)
\(\forall a\in \mathbb{Z}^{\neq 0} ~(~F(~(a,a)~)~)\)
\(\forall a\in \mathbb{Z}^{\neq 0} ~(~\lnot F(~(a,a)~)~)\)
Every nonzero integer is a factor of itself.
No nonzero integer is a factor of itself.
At least one nonzero integer is a factor of itself.
Some nonzero integer is not a factor of itself.
Claim: Every nonzero integer is a factor of itself.
Proof:
Prove or Disprove: There is a nonzero integer that does not divide its square.
Prove or Disprove: Every positive factor of a positive integer is less than or equal to it.
Claim: Every nonzero integer is a factor of itself and every nonzero integer divides its square.
Definition: an integer \(n\) is even means that there is an integer \(a\) such that \(n = 2a\); an integer \(n\) is odd means that there is an integer \(a\) such that \(n = 2a+1\). Equivalently, an integer \(n\) is even means \(n ~\textbf{ mod }~2 = 0\); an integer \(n\) is odd means \(n ~\textbf{ mod }~2 = 1\). Also, an integer is even if and only if it is not odd.
Definition: An integer \(p\) greater than \(1\) is called prime means the only positive factors of \(p\) are \(1\) and \(p\). A positive integer that is greater than \(1\) and is not prime is called composite.
Extra examples: Use the definition to prove that \(1\) is not prime, \(2\) is prime, \(3\) is prime, \(4\) is not prime, \(5\) is prime, \(6\) is not prime, and \(7\) is prime.
True or False: The statement “There are three consecutive positive integers that are prime."
Hint: These numbers would be of the form \(p, p+1, p+2\) (where \(p\) is a positive integer).
Proof: We need to show
True or False: The statement “There are three consecutive odd positive integers that are prime."
Hint: These numbers would be of the form \(p, p+2, p+4\) (where \(p\) is an odd positive integer).
Proof: We need to show