\documentclass{beamer}
%\includegraphics[height=6cm](full frame)
\usepackage{times}
\usetheme{JuanLesPins}
%\usetheme{Montpellier}
%\usetheme{Darmstadt}
%\usetheme{Frankfurt}
\logo{\includegraphics[height=30px]{JMM.PNG}}
\title{A Plaidoyer for Boolean Algebra}
\institute{{\large Helmut Knaust}\medskip\\Department of Mathematical Sciences\\The University of Texas at El Paso\medskip\\\tt{hknaust@utep.edu}}
\date{{\scriptsize San Diego CA\\January 11, 2013}}
\newcommand{\field}[1]{\mathbb{#1}}
\newcommand{\nat}{\field{N}}
\newcommand{\real}{\field{R}}
\newcommand{\rat}{\field{Q}}
\newcommand{\cpl}{\field{C}}
\newcommand{\pset}[1]{{\cal P}(#1)}
\newcommand{\atom}{\alpha}

\begin{document}
\begin{frame}
\titlepage
\end{frame}

\section{Introduction}
\subsection{Plaidoyer}
\begin{frame}
I propose that the basics of Boolean Algebra become a part of the standard \emph{Introduction to Proof} course.
\end{frame}

\subsection{Benefits}

\begin{frame}
\textbf{Benefits}
\begin{itemize}
\item<1-> ``Sets'' and ``Logic'', the two classical examples in Boolean Algebra, are \textbf{main topics} in an \emph{Introduction to Proof} course. 
\item<2-> Boolean Algebra provides a manageable and complete example of an \textbf{axiomatic system}.
\item<3-> Boolean Algebra is \textbf{abstract}. 
\item<4-> Boolean Algebra levels the playing field - students usually have had \textbf{no prior exposure} to Boolean Algebra.
\end{itemize}
\end{frame}


\subsection{How to?}
\begin{frame}
\textbf{How to integrate Boolean Algebra into the course?}
\begin{itemize}
\item<1-> I use a ``\textbf{Moore-style theorem sequence}'', leading to the finite version of \emph{Marshall Stone}'s Representation Theorem for Boolean Algebras.
\item<2-> I do not lecture on Boolean Algebra; instead the problems are part of the \textbf{written homework} assigned throughout the semester.
\end{itemize}
\end{frame}

\section{The axiomatic system}
\subsection{Introduction}
\begin{frame}
\begin{columns}[c]
\column{4cm}
\begin{figure}
\includegraphics[height=4cm]{Boole.jpg}\\
George Boole (1815--1864)
\end{figure}
\column{4cm}
\begin{figure}
\includegraphics[height=4cm]{Huntington.jpg}\\
Edward V.~Huntington (1874--1952)
\end{figure}
\end{columns}
\end{frame}

\subsection{Axioms}
\begin{frame}
\textbf{The Axiomatic System}\medskip\\
A \emph{Boolean Algebra} is a set ${\cal B}$ together with two ``connectives'' $\sqcap$ and $\sqcup$ satisfying the following properties:
\begin{itemize}
\item<1-> \textbf{Closure Laws}: 
\begin{enumerate} 
\item If A and B are two elements in ${\cal B}$, then $A\sqcap B$ is also an element in ${\cal B}$.
\item If A and B are two elements in ${\cal B}$, then $A\sqcup B$ is also an element in ${\cal B}$.
\end{enumerate}
\item<2-> \textbf{Commutative Laws}:
\begin{enumerate}
\item $A\sqcap B=B\sqcap A$\quad for all elements $A$ and $B$ in $\cal B$.
\item $A\sqcup B=B\sqcup A$\quad for all elements $A$ and $B$ in $\cal B$.
\end{enumerate}
\end{itemize}
\end{frame}

\begin{frame}
\textbf{The Axiomatic System II}\medskip\\
\begin{itemize}
\item<1-> \textbf{Distributive Laws}:
\begin{enumerate}
\item $A\sqcap (B\sqcup C)=(A\sqcap B)\sqcup (A\sqcap C)$\quad for all elements $A$, $B$ and $C$ in $\cal B$.
\item $A\sqcup (B\sqcap C)=(A\sqcup B)\sqcap (A\sqcup C)$\quad for all elements $A$, $B$ and $C$ in $\cal B$.
\end{enumerate}
\item<2-> \textbf{Associative Laws}:
\begin{enumerate}
\item $A\sqcap (B\sqcap C)=(A\sqcap B)\sqcap C$\quad for all elements $A$, $B$ and $C$ in $\cal B$.
\item $A\sqcup (B\sqcup C)=(A\sqcup B)\sqcup C$\quad for all elements $A$, $B$ and $C$ in $\cal B$.
\end{enumerate}
\item<3->Note: The Associative Laws can be deduced from the other five Boolean Algebra Laws.
\end{itemize}
\end{frame} 

\begin{frame}
\textbf{The Axiomatic System III}\medskip\\
\begin{itemize}
\item<1->\textbf{Identity Laws}:\medskip\\
There are elements $N\in{\cal B}$ (called the \emph{null element}) and $O\in{\cal B}$ (the \emph{one element}) such that
\begin{enumerate}
\item $A\sqcap N=N$ and $A\sqcap O=A$\quad for all elements $A$ in $\cal B$.
\item $A\sqcup O=O$ and $A\sqcup N=A$\quad for all elements $A$ in $\cal B$.
\end{enumerate}
\item<2->\textbf{Complement Law}:\medskip\\
For every element $A$ in $\cal B$ there is an element $B$ in $\cal B$ such that $A\sqcap B=N$ and $A\sqcup B=O$.
\end{itemize}
\end{frame} 

\section{Examples}
\subsection{Sets and Logic}
\begin{frame}
\textbf{The two classical examples:}\medskip\\
\begin{enumerate}
\item<1-> \textbf{Observation:} Let $X$ be an arbitrary set. Then its power set ${\cal P}(X)$ with the connectives $\cap$ (in the role of $\sqcap$) and $\cup$ (in the role of $\sqcup$) forms a Boolean Algebra.\bigskip
\item <2->
\textbf{Problem:} Show that \[{\cal S}_1=\{P\wedge\neg P;\ P,\ \neg P;\ P\vee \neg P\}\] forms a 
Boolean Algebra (with $\wedge$ and $\vee$). ${\cal S}_1$ is called the ``Boolean Algebra generated by the free statement $P$''.
\item<3-> \textbf{Problem:} Find the Boolean Algebra ${\cal S}_2$ generated by two free statements $P$ and $Q$. How many elements does ${\cal S}_2$ have?
\end{enumerate}
\end{frame} 


\subsection{A third example}
\begin{frame}
\textbf{A third elementary example:}\medskip\\

For a natural number $n$, let ${\cal D}_n$ denote the set of the divisors of $n$. For example, ${\cal D}_{42}=\{1,2,3,6,7,14,21,42\}$ and ${\cal D}_{12}=\{1,2,3,4,6,12\}$. For $m,n\in\nat$ let $m\sqcap n$ denote the greatest common divisor of $n$ and $m$, and $m\sqcup n$ their least common multiple. For instance $6\sqcap 4=2$ and $6\sqcup 4=12$. It turns out that ${\cal D}_{42}$ with these two operations $\sqcap$ and $\sqcup$ forms a Boolean Algebra, while ${\cal D}_{12}$ does \textbf{not}.

\begin{enumerate}\setcounter{enumi}{3}
\item \textbf{Problem:} Verify the Boolean Algebra Laws for ${\cal D}_{42}$. 
\item \textbf{Problem:} Show that ${\cal D}_{12}$ does not form a Boolean Algebra.
\item \textbf{Problem:} Conjecture for which values of $n$ the set ${\cal D}_{n}$ forms a Boolean Algebra.  
\end{enumerate}
\end{frame}

\section{Order and Atoms}
\subsection{Order for a Boolean Algebra}
\begin{frame}
The topic of Boolean Algebra can be revisited when the course ``covers'' partial orders:\medskip\\
\begin{enumerate}\setcounter{enumi}{6}
\item \textbf{Problem:} Consider the relation ``$\preceq$'' on a Boolean Algebra ${\cal B}$ defined by 
\[A\preceq B \quad\Leftrightarrow\quad A\sqcup B=B\] for $A,B\in{\cal B}$. Prove that $\preceq$ is reflexive, anti-symmetric and transitive. 
\item \textbf{Problem:} 
Consider the Boolean Algebra ${\cal S}_1$. Draw a \emph{Hasse diagram} for ${\cal S}_1$ endowed with the partial order $\preceq$.
\end{enumerate}
\end{frame} 

\subsection{Atoms in a Boolean Algebra}
\begin{frame}
The crucial definition needed to lead to the representation theorem for finite Boolean Algebras is the following:\medskip\\ 
\begin{quote}
Let ${\cal B}$ be a Boolean Algebra with null-element $N$, partially ordered by $\preceq$. We say that $A\in{\cal B}$ is an \textsc{atom} of ${\cal B}$ if $N$ is an immediate predecessor of $A$.
\end{quote}
\begin{enumerate}\setcounter{enumi}{8}
\item \textbf{Problem:} Find all atoms of ${\cal P}(\{1,2,3,4\})$.
\item \textbf{Problem:} Find all atoms of ${\cal D}_{42}$.
\item \textbf{Problem:} Find a Boolean Algebra with 8~elements that is a subset of ${\cal P}(\{1,2,3,4\})$, but \textbf{not} the power set of a three-element subset of $\{1,2,3,4\}$, then find its atoms and draw its Hasse diagram.
\end{enumerate}
\end{frame}

\subsection{Finite Boolean Algebras}
\begin{frame}
\begin{columns}
\column{4cm} 
A sequence of four more problems studying atoms in a Boolean Algebra is needed before students are ready for the ``big theorem'' at the end of the semester.
\column{4cm}
\begin{figure}
\includegraphics[height=4cm]{Stone.jpg}\\
Marshall H. Stone (1903--1989)
\end{figure}
\end{columns}
\end{frame}

\begin{frame}
Let ${\cal B}$ be a finite Boolean Algebra with $k$ atoms for some $k\in\nat$, and let ${\cal A}$ denote the power set of the set of all atoms of ${\cal B}$. 

Let 
 \[\atom(B)=\{A\in{\cal B}\ |\ A\preceq B \mbox{ and } A \mbox{ is an atom of } {\cal B}\}.\]
\begin{enumerate}\setcounter{enumi}{11}
\item<2-> \textbf{Problem:} Show that the function $\atom:{\cal B}\to{\cal A}$ is a bijection.
\item<3-> \textbf{Problem:} ${\cal B}$ has $2^k$ elements.
\item<4-> \textbf{Problem:} Show that the identities $\atom(B\sqcup B')=\atom(B)\cup \atom(B')$ and $\atom(B\sqcap B')=\atom(B)\cap \atom(B')$ hold for all $B,B'\in{\cal B}$.
\item<4->  \textbf{Problem:} Additionally, $\atom(N)=\emptyset$ and $\atom(O)$ is the set of all atoms of ${\cal B}$.
\end{enumerate}
\end{frame}


\section{References}
\begin{frame}
References:
\begin{itemize}
\item R.L. Goodstein, \emph{Boolean Algebra}. Dover Pub., 2007.
\item Edward V. Huntington, \emph{Sets of Independent Postulates for the Algebra of Logic}. Transactions of the American Mathematical Society 5 (1904), pp.~288-309.
%\item Franz Jehle, \emph{Boolesche Algebra}. Bayerischer Schulbuch Verlag, 1971.
\item Projektgruppe Fernstudium an der Universit\"at Bielefeld,\emph{ Mathematisches Vorsemester}. Springer-Verlag, 1974.
\item Marshall H.~Stone, \emph{The Theory of Representation for Boolean Algebras}. Transactions of the American Mathematical Society 40 (1936), pp.~37-111.
\item J.E. Whitesitt, Boolean Algebra and Its Applications. Dover~Pub., 1995
\end{itemize}\medskip
The complete \emph{Boolean Algebra theorem sequence} is available at \texttt{helmut.knaust.info/presentations/BA.pdf}
\end{frame}

\end{document}