
\section{Basic data types}

\forstudents{\reading{Velleman chapter 1, Rosen 1.1-1.6}}

First, we need to agree on some basic language of discourse
so we can say things to each other.  
We'll be using the standard basic data types used in programming:
numbers, Booleans (true/false)\.
(Also later strings, but skip for now.)
We'll also use other basic data types from mathematics, such as sets and 
functions\. 
These are used in reasoning about programs\.  
This is review for most of you, so I won't lecture about it\.  
I'll just list the basic notions:  definitions, operations, some properties\.
You will be expected to read this material carefully on your own, making sure 
you can do all the study exercises.

\subsection{Booleans}

\forstudents{\reading{Velleman 1.1--1.2, Rosen 1.1}}

Values: 1 (true), 0 (false)\.
Operations: and ($\wedge$), or ($\vee$), not ($\neg$), exclusive-or
($\oplus$)\. 
\\
These operations can be explained with tables:
\\
\begin{tabular}{cc}
  $x$ & $\neg x$ \\
  \hline 
  1   & 0 \\
  0   & 1 \\
\end{tabular}
\\
\\
\begin{tabular}{ccccc}
  $x$ & $y$ & $x \wedge y$ & $x \vee y$ & $x \oplus y$ \\
  \hline 
  1   & 1   & 1            & 1          & 0\\ 
  1   & 0   & 0            & 1          & 1\\
  0   & 1   & 0            & 1          & 1\\
  0   & 0   & 0            & 0          & 0\\
\end{tabular}

\subsection{Numbers}

\forstudents{\reading{Rosen, Section 1.4}}
These are just the standard number classes.
\begin{description}
\item[Natural numbers] $\naturals = \{ 0, 1, 2, \ldots \}$ 

  Most math books actually let $\naturals$ start at 1 rather than 0,
  but computer scientists like to start counting with 0\.  We'll stay
  consistent with the course texts and start with 0\.  We'll write
  $\naturals^+$ for the positive naturals.

  Operations: $+$, $-$ (a partial function), times, integer division (round
  down), remainder (mod), exponentiation

  \forstudents{Prime number: Natural number $\geq 2$ that has no
    divisors except for itself and $1$\.  Example: 7 is prime, 14 is
    not.  }

\item[Integers,] denoted by $\ints$: $\naturals$ and its negatives 
\item[Rationals,] denoted by $\rationals$ 

  These are all numbers that are expressible as a ratio of two integers
  $\frac{a}{b}$, where $b \neq 0$\.  A basic theorem (we might prove it
  later) says that we can write any rational number in lowest terms.
\item[Reals,] denoted by $\reals$
\end{description}

 \subsection{Strings}
 
 Strings are sequences of symbols drawn from some fixed alphabet\.  
 For example, if the alphabet consists of $a, b, c$, some examples of 
 strings are $abc$, $aaa$, $b$, and the empty string ($\lambda$, a shorthand 
 for no symbols)\.
 The main interesting operation is concatenation\. 
 Concatenating the two strings $abc$ and $bba$ gives the string $abcbba$.

\subsection{Sets}

\forstudents{\reading{Velleman 1.3--1.4, Rosen  1.4--1.5}}

Values: $\emptyset$, universal set $U$, singleton sets $\{ a \}$\.
Relationships:  Subset ($\subseteq$), proper subset ($\subset$)\.
Operations are:  Union ($\cup$), intersection ($\cap$), complement
(overbar)\.  

Venn diagrams are useful for reasoning about sets\.
There are many laws about how the operations behave---see Rosen p. 49\.
E.g.: $A \cup A = A$\.
                                %We'll come back to this later.

\subsection{Functions}

\forstudents{\reading{Rosen, Section 1.6}}

A function is a rule that assigns an element of one set (known as the range) 
to each element of another set (the domain)\.
Operations include function inverse and composition ($f \circ g(x) =
f(g(x))$)\.
We'll come back to this later.
