\documentclass[12pt, oneside]{article}

\usepackage[letterpaper, scale=0.89, centering]{geometry}
\usepackage{fancyhdr}
\setlength{\parindent}{0em}
\setlength{\parskip}{1em}

\pagestyle{fancy}
\fancyhf{}
\renewcommand{\headrulewidth}{0pt}
\rfoot{\href{https://creativecommons.org/licenses/by-nc-sa/2.0/}{CC BY-NC-SA 2.0} Version \today~(\thepage)}

\usepackage{amssymb,amsmath,pifont,amsfonts,comment,enumerate,enumitem}
\usepackage{currfile,xstring,hyperref,tabularx,graphicx,wasysym}
\usepackage[labelformat=empty]{caption}
\usepackage{xcolor}
\usepackage{multicol,multirow,array,listings,tabularx,lastpage,textcomp,booktabs}

\lstnewenvironment{algorithm}[1][] {   
    \lstset{ mathescape=true,
        frame=tB,
        numbers=left, 
        numberstyle=\tiny,
        basicstyle=\rmfamily\scriptsize, 
        keywordstyle=\color{black}\bfseries,
        keywords={,procedure, div, for, to, input, output, return, datatype, function, in, if, else, foreach, while, begin, end, }
        numbers=left,
        xleftmargin=.04\textwidth,
        #1
    }
}
{}
\lstnewenvironment{java}[1][]
{   
    \lstset{
        language=java,
        mathescape=true,
        frame=tB,
        numbers=left, 
        numberstyle=\tiny,
        basicstyle=\ttfamily\scriptsize, 
        keywordstyle=\color{black}\bfseries,
        keywords={, int, double, for, return, if, else, while, }
        numbers=left,
        xleftmargin=.04\textwidth,
        #1
    }
}
{}

\newcommand\abs[1]{\lvert~#1~\rvert}
\newcommand{\st}{\mid}

\newcommand{\A}[0]{\texttt{A}}
\newcommand{\C}[0]{\texttt{C}}
\newcommand{\G}[0]{\texttt{G}}
\newcommand{\U}[0]{\texttt{U}}

\newcommand{\cmark}{\ding{51}}
\newcommand{\xmark}{\ding{55}}

 
\begin{document}
\begin{flushright}
    \StrBefore{\currfilename}{.}
\end{flushright} 
\subsection*{Week 5 at a glance}

\subsubsection*{We will be learning and practicing to:}
\begin{itemize}

\item Clearly and unambiguously communicate computational ideas using appropriate formalism. Translate across levels of abstraction.
\begin{itemize}
   \item Translating between symbolic and English versions of statements using precise mathematical language
    \item Using appropriate signpost words to improve readability of proofs, including 'arbitrary' and 'assume'
\end{itemize}

\item 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.
\begin{itemize}
    \item Judging logical equivalence of compound propositions using symbolic manipulation with known equivalences, including DeMorgan's Law
    \item Writing the converse, contrapositive, and inverse of a given conditional statement
    \item Determining what evidence is required to establish that a quantified statement is true or false
    \item Evaluating quantified statements about finite and infinite domains
\end{itemize}

\item Apply proof strategies, including direct proofs and proofs by contradiction, and determine whether a proposed argument is valid or not.
\begin{itemize}
    \item Identifying the proof strategies used in a given proof
    \item Identifying which proof strategies are applicable to prove a given compound proposition based on its logical structure
    \item Carrying out a given proof strategy to prove a given statement
    \item Carrying out a universal generalization argument to prove that a universal statement is true
    \item Using proofs as knowledge discovery tools to decide whether a statement is true or false
\end{itemize}
\end{itemize}

\subsubsection*{TODO:}
\begin{list}
   {\itemsep2pt}
    \item Test 1 Attempt 1 in the CBTF this week at your scheduled time!
    \begin{itemize}
    \item 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. 
    \item Pockets must be empty upon entry. Students may bring only their ID and a pen or pencil into the testing center. 
    \end{itemize}

    \item Review quiz based on Week 4 class material (due Friday 02/06/2026)
    \item Midquarter feedback: please let us know what's working well for you and what isn't.  \url{https://canvas.ucsd.edu/courses/71479/quizzes}
\end{list}
\newpage

\begin{comment}
Removed definition of insertion, deletion, mutation from Wednesday of Week 4 -- when do we need them?


Real-life representations are often prone to corruption.  Biological codes, like RNA, 
may mutate naturally\footnote{Mutations of specific RNA codons have been linked to many disorders and cancers.}
and during measurement; cosmic radiation and other ambient noise 
can flip bits in computer storage\footnote{This RadioLab podcast episode
goes into more detail on bit flips: \url{https://www.wnycstudios.org/story/bit-flip}}. 
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.
\begin{algorithm}[caption={Create redundancy by repeating each bit three times}]
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$
\end{algorithm}

\begin{algorithm}[caption={Decode sequence of bits using majority rule on consecutive three bit sequences}]
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$
\end{algorithm}

Give a recursive definition of the set of outputs of the $redun3$ procedure, $Out$,

\phantom{{\bf Basis step}: $000 \in Out$ and $111 \in Out$\\ {\bf Recursive step}: If $x \in Out$ then $x000 \in Out$ and $x111 \in Out$ (where $x000$ and $x111$ are the results of string concatenation).}


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.


{\it 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$.

\begin{center}
\begin{multicols}{2}\begin{tabular}{ccc|c}
$c_{3i}$ & $c_{3i+1}$ & $c_{3i+2}$ & $a_i$ \\
\hline
$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}$ \\\\
\end{tabular}
\columnbreak

Circuit 
\end{multicols}
\end{center} \newpage


{\bf Definition}: The {\bf 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 = \{\A,\U,\G,\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}
\]

\begin{algorithm}
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}\}$
\end{algorithm}

\begin{algorithm}
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}\}$
\end{algorithm}

\begin{algorithm}
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}\}$
\end{algorithm}
 

Trace the pseudocode to find the output of $\textit{mutation}(~ (\A\U\C, 3, \G) ~)$

\vspace{50pt}

Fill in the blanks so that $\textit{insertion}(~(\A\U\C, \underline{\phantom{3}}, \underline{\phantom{\G}})~) = \A\U\C\G$

\vspace{50pt}

Fill in the blanks so that $\textit{deletion}(~(\underline{\phantom{\G\G}}, \underline{\phantom{1}})~) =  \G$

\vspace{50pt}
 \end{comment}

\section*{Week 5 Monday: Nested Quantifiers}


{\it Recall the definitions}: The set of RNA strands $S$ is defined (recursively) by:
\[
\begin{array}{ll}
\textrm{Basis Step: } & \A \in S, \C \in S, \U \in S, \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 \textit{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 \textit{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}
\] 

{\bf Alternating nested quantifiers}



$$\forall s \in S ~\exists n \in \mathbb{N} ~(~basecount(~(s,\U)~) = n~)$$

In English: For each strand, there is a nonnnegative integer that counts the number of occurrences of $\U$ in that 
strand.\\

$$\exists n \in \mathbb{N} ~\forall s \in S ~(~basecount(~(s,\U)~) = n~)$$

In English: There is a nonnnegative integer that counts the number of occurrences of $\U$ in every 
strand.\\

\vfill

Are these statements true or false?

\newpage

$$\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).

\vspace{60pt}


Is the original statement {\bf True} or {\bf False}?

\vfill
 \subsection*{Proof strategies}


When a predicate $P(x)$ is over a {\bf finite} domain:
\begin{itemize}
\item 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 {\bf exhaustion}".
\item To show that $\forall x  P(x)$ is false: find a {\bf counterexample}, a domain element where $P(x)$~evaluates~to~$F$.
\item To show that $\exists x  P(x)$ is true: find a {\bf witness}, a domain element where $P(x)$ evaluates to $T$.
\item 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.
\end{itemize} 

\fbox{\parbox{\linewidth}{

{\bf New! Proof by universal generalization}: To prove that $\forall x \, P(x)$
is true, we can take an arbitrary element $e$ from the domain of 
quantification and show that $P(e)$ is true, without making any assumptions about $e$ 
other than that it comes from the domain.


An {\bf arbitrary} element of a set or domain is a fixed but unknown element from that set. 
}}
 \vfill
\newpage

Suppose $P(x)$ is  a predicate over a domain $D$.
\begin{enumerate}
    \item 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}})
    \]
    \vfill
    \item  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?
    \vfill
\end{enumerate} 
\newpage
\section*{Week 5 Wednesday: Proof Strategies and Sets}


{\bf Definitions}:

A {\bf 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 {\bf 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 {\bf proper subset} of $B$") means 
\[
    (A\subseteq B) \wedge  (A \neq B)
\] 

\fbox{\parbox{\linewidth}{

{\bf New! Proof of conditional by direct proof}: To prove that the conditional statement $p \to q$ is true, 
we can assume $p$ is true and use that assumption to show $q$ is true.
}}

\fbox{\parbox{\linewidth}{

{\bf New! Proof of conditional by contrapositive proof}: To prove that the implication $p \to q$ is true, 
we can assume $q$ is false and use that assumption to show $p$ is also false.
}}

\fbox{\parbox{\linewidth}{

{\bf New! Proof of disjuction using equivalent conditional}: To prove that the 
disjunction $p \lor q$ is true, we can rewrite it equivalently as $\lnot p \to q$ and
then use direct proof or contrapositive proof.
}} 

\fbox{\parbox{\linewidth}{{\bf New! Proof by Cases}: To prove $q$, we can 
work by cases by first describing all possible cases we might be in
and then showing that each one guarantees $q$.
Formally, if we know that $p_1 \lor p_2$ is true, 
and we can show that $(p_1 \to q)$ is true and we can show that $(p_2 \to q)$, 
then we can conclude $q$ is true.
}} 

\fbox{\parbox{\linewidth}{
{\bf New! Proof of conjunctions with subgoals}:
To show that $p \land q$ is true, we have two subgoals: subgoal (1) prove $p$ 
is  true; and, subgoal (2) prove $q$ is true.

\vspace{1em}

 To show that $p \land q$ is false, it's enough to prove that $\lnot p$.
 
 To show that $p \land q$ is false, it's enough to prove that $\lnot q$.
}} 

To prove that one set is a subset of another, e.g. to show $A \subseteq B$:

\vspace{50pt}

To prove that two sets are equal, e.g. to show $A = B$:

\vspace{50pt}
 \newpage


Example: $\{ 43, 7, 9 \} = \{ 7, 43, 9, 7\}$

\vspace{50pt}
 

{\bf Prove} or {\bf  disprove}: $\{ \A,  \C,  \U,  \G\} \subseteq \{ \A\A, \A\C, \A\U, \A\G \}$ 

\vspace{150pt}

{\bf Prove} or {\bf  disprove}: For some set $B$, $\emptyset \in B$.

\vspace{150pt}

{\bf Prove} or {\bf  disprove}: For every set $B$, $\emptyset \in B$.

\vspace{150pt}

{\bf Prove} or {\bf  disprove}: The empty set is a subset of every set.

\vspace{150pt}

{\bf Prove} or {\bf  disprove}: The empty set is a proper subset of every set.

\vspace{150pt}

{\bf Prove} or {\bf  disprove}: $\{ 4, 6 \} \subseteq \{ n \mid  \exists c \in \mathbb{Z} ( n = 4c) \} $

\vspace{150pt}

{\bf Prove} or {\bf  disprove}: $\{ 4, 6 \} \subseteq \{ n ~\textbf{mod}~10 \mid  \exists c \in \mathbb{Z} ( n = 4c) \} $

\vspace{150pt}

 \vfill


\fbox{\parbox{\textwidth}{

\vspace{10pt}

Consider \ldots, an {\bf arbitrary} \ldots.
{\bf Assume} \ldots, we {\bf want to show} that \ldots. Which is what was needed,
so the proof is complete $\square$.

\vspace{20pt} {\it or, in other words:} \vspace{20pt}

Let \ldots be an {\bf arbitrary} \ldots. {\bf Assume} \ldots, {\bf WTS} that \ldots {\bf QED}.

\vspace{10pt}

}} 
\newpage
\section*{Week 5 Friday: Proof Strategies and Sets}


{\bf 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  = $

{\bf 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  = $ 

{\bf 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  = $


{\bf 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  = $

    
{\bf 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

    

{\bf 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:
\vspace{20pt}


{\bf Prove} or {\bf  disprove}:  $\forall  A \in W\,  \forall B \in W\,  \left( A \subseteq B
~\to ~ \mathcal{P}(A) \subseteq \mathcal{P}(B) \right)$

\vfill
\vfill
\vfill

{\bf Prove} or {\bf  disprove}:  $\forall  A \in W\,  \forall B \in W\,  \left( \mathcal{P}(A)  =\mathcal{P}(B)
~\to ~ A = B \right)$

\vfill
\vfill

{\bf Prove} or {\bf  disprove}:  $\forall  A \in W\,  \forall B \in W\, \forall C  \in W\,  \left( A\cup B  = A \cup  C
~\to ~ B = C \right)$

\vfill
\vfill \end{document}
