%--*- latex -*-----------------------------------------------------------------
%$Author: saulius $
%$Date: 2020-06-04 14:58:32 +0300 (Thu, 04 Jun 2020) $ 
%$Revision: 1524 $
%$URL: svn+ssh://saulius-grazulis.lt/home/saulius/svn-repositories/seminarai/2020-verifikacjos-seminarui/slides.tex $
%------------------------------------------------------------------------------

\documentclass[mathserif]{beamer}
\usetheme{Warwick}
\useoutertheme{infolines}
\setbeamertemplate{headline}{} % removes the headline the infolines inserts
%\setbeamertemplate{footline}[frame number]
\renewcommand\familydefault{\rmdefault}
% For XeLaTeX:
% https://tex.stackexchange.com/questions/452151/how-do-i-render-the-word-v%C7%ABlundarkvi%C3%B0a-with-bookman-and-xelatex
% "Use an OpenType clone of Bookman, for instance TeX Gyre Bonum":
\usepackage{fontspec}
\setmainfont{TeX Gyre Bonum}

\usepackage[style=authoryear,maxnames=1,doi=true,url=true,backend=biber]{biblatex}
\addbibresource{bibliography/citations.bib}
\newcommand{\mycite}{\parencite}


\usepackage{multirow}

\usepackage{colordvi}
\usepackage{graphicx}
\usepackage{tikz}
\usetikzlibrary{matrix}
\usepackage{verbatim}
\usepackage{listings}
\usepackage{chemfig}
\usepackage{listings}

% https://en.wikibooks.org/wiki/LaTeX/Algorithms
% http://mirror.datacenter.by/pub/mirrors/CTAN/macros/latex/contrib/algorithmicx/algorithmicx.pdf
\usepackage{algpseudocode}
\usepackage{algorithm}
\usepackage{amssymb}

\include{commands}

% https://tex.stackexchange.com/questions/595/how-can-i-get-bold-math-symbols:
\newcommand{\boldm}[1]{\mathversion{bold}#1\mathversion{normal}}

\newcommand{\RCSid}[1]{\fontsize{7pt}{7pt}\selectfont $#1$ \today}


%%BEGIN LANGUAGE en
\title{Transistors and logic gates}
%%END LANGUAGE en


\author{Saulius Gražulis}

\date{Vilnius, 2020}

\begin{document}

%------------------------------------------------------------------------------

\input{text-parts/recording-announcement.tex}

\begin{frame}
    \titlepage

\input{affiliation}
    
    \begin{center}
      \mbox{}
      \hfill\hfill\hfill
      \includegraphics[height=1.5cm]{images/sp_VU_zenklas.eps}
      \hfill
      \includegraphics[height=1.5cm]{images/2019-05-02_Melynas_MIF-zenklas242x244.png}
      \hfill\hfill\hfill
      \mbox{}
    \end{center}

    \vfill

    %% \tiny
    %% \RCSid{
    %%   $Id: slides.tex 1524 2020-06-04 11:58:32Z saulius $
    %% }
    \begin{flushright}
      \begin{minipage}[c]{0.67\textwidth}
        \tiny\raggedright
        %%BEGIN LANGUAGE en
        This set of slides may be copied and used as specified in the
        %%END LANGUAGE en
        \myhref{http://creativecommons.org/licenses/by-sa/4.0/}{Attribution-ShareAlike
          4.0 International}
license
      \end{minipage}
      %%
      \begin{minipage}[c]{1.5cm}
        \myhref{http://creativecommons.org/licenses/by-sa/4.0/}{
          \includegraphics[width=1.5cm]{images/CC-BY-SA.eps}
        }
      \end{minipage}
    \end{flushright}

\end{frame}

%==============================================================================

\begin{frame}
\frametitle{Transistor, a controlled electric switch}

  FET – Field-effect transistor

  MOSFET – Metal–oxide–semiconductor field-effect transistor
  
  \only<1>{
    \begin{center}
      \hfill
      \parbox[c]{5cm}{
        \begin{center}
\includegraphics[height=5cm]{drawings/transistors/transistor-marked-termini.eps}
        \end{center}
      }
      \hfill
      \parbox[c]{5cm}{
        \begin{center}
          \includegraphics[height=5cm]{drawings/mechanical-switches/switch.eps}
        \end{center}
      }
      \hfill
      \mbox{}
    \end{center}
  }
  \only<2>{
    \begin{center}
      \hfill
      \parbox[c]{5cm}{
        \begin{center}
\includegraphics[height=5cm]{drawings/transistors/transistor-marked-termini.eps}
        \end{center}
      }
      \hfill
      \parbox[c]{5cm}{
        \begin{center}
\includegraphics[width=5cm]{images/Lateral_mosfet.eps}\\
          \vspace{\baselineskip}
          \footnotesize\em
          \myhref{https://commons.wikimedia.org/wiki/File:Lateral_mosfet.svg}{
            Cyril Buttay}
          \myhref{https://creativecommons.org/licenses/by-sa/3.0/deed.en}{[CC
              BY-SA 3.0]}
        \end{center}
      }
      \hfill
      \mbox{}
    \end{center}
  }
  \only<3>{
    \begin{center}
      \hfill
      \parbox[c]{5cm}{
        \begin{center}
\includegraphics[height=5cm]{drawings/transistors/transistor-marked-termini.eps}
        \end{center}
      }
      \hfill
      \parbox[c]{5cm}{
        \begin{center}
          \includegraphics[width=5cm]{images/MOSFETs.jpg}\\
          \vspace{\baselineskip}
          \footnotesize\em
          \myhref{https://commons.wikimedia.org/wiki/File:MOSFETs.jpg}{Dick Lyon}
          [Public domain]
        \end{center}
      }
      \hfill
      \mbox{}
    \end{center}
  }
  
  
\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{FET vs bipolar transistor}

  \begin{center}
    \hfill
\includegraphics[height=4cm]{drawings/transistors/transistor-marked-termini.eps}
    \hfill
\includegraphics[height=4cm]{drawings/transistors/bipolar-n-p-n.eps}
    \hfill
\includegraphics[height=4cm]{drawings/transistors/bipolar-p-n-p.eps}
    \hfill
    \mbox{}
  \end{center}

\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Properties of a transistor}

  \only<1>{
    \begin{center}
      \hfill
      \includegraphics[height=5cm]{drawings/transistors/transistor-closed.eps}
      \hfill
      \includegraphics[height=5cm]{drawings/mechanical-switches/switch.eps}
      \hfill
      \mbox{}
    \end{center}
  }

  \only<2>{
    \begin{center}
      \hfill
      \includegraphics[height=5cm]{drawings/transistors/transistor-open.eps}
      \hfill
      \includegraphics[height=5cm]{drawings/mechanical-switches/switch-closed.eps}
      \hfill
      \mbox{}
    \end{center}
  }

  \only<3>{
    \begin{center}
      \hfill
      \includegraphics[height=5cm]{drawings/transistors/transistor-open-with-current.eps}
      \hfill
      \includegraphics[height=5cm]{drawings/mechanical-switches/switch-closed-with-current.eps}
      \hfill
      \mbox{}
    \end{center}
  }

\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Two types of transistors}

  \begin{center}
    \begin{tabular}{cccccc}
      \parbox[c]{2cm}{
        \begin{center}
          \includegraphics[height=5cm]{drawings/transistors/transistor.eps}
        \end{center}
      }
      &
      {\Large$\Leftrightarrow$}
      &
      \parbox[c]{2cm}{
        \begin{center}
          \includegraphics[height=5cm]{drawings/mechanical-switches/switch.eps}
        \end{center}
      }
      &
      \parbox[c]{2cm}{
        \begin{center}
          \includegraphics[height=5cm]{drawings/transistors/transistor-pmos.eps}
        \end{center}
      }
      &
      {\Large$\Leftrightarrow$}
      &
      \parbox[c]{2cm}{
        \begin{center}
          \includegraphics[height=5cm]{drawings/mechanical-switches/switch-normally-closed.eps}
        \end{center}
      }
      \\
      \multicolumn{2}{c}{
n-type transistor
      }
      &&
      \multicolumn{2}{c}{
p-type transistor
      }
      &
      \\
    \end{tabular}
  \end{center}

\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Comparison of n-type and p-type transistors}

  \only<1>{
    \begin{center}
      \includegraphics[height=5cm]{drawings/transistors/transistors-n-type-p-type-open-with-current.eps}
    \end{center}
  }
  \only<2>{
    \begin{center}
      \includegraphics[height=5cm]{drawings/transistors/transistors-n-type-p-type-closed.eps}
    \end{center}
  }

\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{An overview n-type and p-type transistors}

  \begin{center}
    \hfill
    \includegraphics[height=5cm]{drawings/transistors/transistors-n-type-p-type-open-with-current.eps}
    \hfill
    \includegraphics[height=5cm]{drawings/transistors/transistors-n-type-p-type-closed.eps}
    \hfill
    \mbox{}
  \end{center}

\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Transistor switch voltages}

  \only<1>{
    \begin{center}
      \hfill
\includegraphics[height=5cm]{drawings/transistors/transistor-switch-voltages.eps}
      \hfill
\includegraphics[height=5cm]{drawings/mechanical-switches/mechanical-switch-voltages.eps}
      \hfill
      \mbox{}
    \end{center}
  }
  \only<2>{
    \begin{center}
      \hfill
\includegraphics[height=5cm]{drawings/transistors/transistor-switch-voltages-off.eps}
      \hfill
\includegraphics[height=5cm]{drawings/mechanical-switches/mechanical-switch-voltages-off.eps}
      \hfill
      \mbox{}
    \end{center}
  }

\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Opposite voltages of a transistor switch}

  \begin{center}
    \hfill
\includegraphics[height=5cm]{drawings/transistors/transistor-switch-voltages-off-coloured.eps}
    \hfill
\includegraphics[height=5cm]{drawings/transistors/transistor-switch-voltages-coloured.eps}
    \hfill
    \mbox{}
  \end{center}

\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Inverter (the logic function NOT)}

  \begin{center}
    \hfill
    \begin{tabular}{ll}
      L: &
Ground voltage
      ($\approx$ 0V)
      \\
      H: &
Supply voltage
      (5V, 3.3V, ...)
      \\
    \end{tabular}
    \hfill
    \begin{tabular}{ll}
      L: & 0 \\
      H: & 1 \\
    \end{tabular}
    \hfill
    \begin{tabular}{ll}
      L: & False \\
      H: & True \\
    \end{tabular}
    \hfill
    \mbox{}
  \end{center}
  
  \begin{center}
    \hfill
    \begin{tabular}{c|c}
\textbf{Input} & \textbf{Output} \\
      \hline
      L & H \\
      H & L \\
    \end{tabular}
    \hfill
    \begin{tabular}{c|c}
\textbf{Input} & \textbf{Output} \\
      \hline
      0 & 1 \\
      1 & 0 \\
    \end{tabular}
    \hfill
    \begin{tabular}{c|c}
\textbf{Input} & \textbf{Output} \\
      \hline
      False & True \\
      True & False \\
    \end{tabular}
    \hfill
    \mbox{}
  \end{center}
  
  \begin{center}
    \hfill
\includegraphics[height=3.5cm]{drawings/transistors/transistor-switch-voltages-off-coloured.eps}
    \hfill
\includegraphics[height=3.5cm]{drawings/transistors/transistor-switch-voltages-coloured.eps}
    \hfill
    \mbox{}
  \end{center}

\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
  %%BEGIN LANGUAGE en
  \frametitle{Historic NOR gates – Apollo guidance computer}
  %%END LANGUAGE en

  \begin{center}
    \begin{tabular}{cc}
        \includegraphics[height=3cm]{images/Agc_nor2a_half.jpg} &
        \rule{0pt}{3.1cm}
        \hspace{0.8cm}
        \includegraphics[height=3cm]{images/Agc_nor2.jpg}
        \hspace{0.8cm}
        \\
        \includegraphics[height=3cm]{images/Agc_flatp.jpg} &
        \only<1>{
          \rule{0pt}{3.1cm}
          \includegraphics[height=3cm]{images/Agc_view.jpg}
        }
        \only<2>{
          \rule{0pt}{3.1cm}
          \includegraphics[height=3cm]{images/596px-Apollo_11_Lunar_Lander_-_5927_NASA_gimp.jpeg}
        }
    \end{tabular}
  \end{center}

  \scriptsize
  \only<1>{
    All AGC images:
    Wikipedia. \myhref{https://en.wikipedia.org/wiki/Apollo\_Guidance\_Computer}{Apollo
      guidance computer}, (viewed 2020-08-10).
    All images by NASA, public domain.
  }
  \only<2>{
    Lunar Landing Module image: by
    \myhref{https://commons.wikimedia.org/wiki/File:Apollo_11_Lunar_Lander_-_5927_NASA.jpg}{Neil
      Armstrong} \newline
    (viewed 2020-08-10). [Public domain]
  }

\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Power dissipation}

  \begin{center}
    \hfill
\includegraphics[height=5cm]{drawings/transistors/transistor-switch-voltages-heat.eps}
    \hfill
    \includegraphics[height=5cm]{drawings/transistors/transistor-totem-pole-switch.eps}
    \hfill
    \mbox{}
  \end{center}
  
\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{CMOS NOT gate}

  \begin{center}
    \hfill
    \includegraphics[height=5cm]{drawings/transistors/CMOS-NOT-gate.eps}
    \hfill
    \includegraphics[height=5cm]{drawings/transistors/CMOS-NOT-gate-input-low.eps}
    \hfill
    \mbox{}
  \end{center}
  
\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Logisim simulated NOT gate}

  \myhref{http://www.cburch.com/logisim/}{Logisim}
  %%BEGIN LANGUAGE en
  is a very nice program for designing and simulating digital logic
  circuits.
  %%END LANGUAGE en
  
  \begin{center}
    \includegraphics[width=5cm]{drawings/circuits/CMOS-NOT-gate-input-High.png}
    \hspace{0.5em}
    \includegraphics[width=5cm]{drawings/circuits/CMOS-NOT-gate-input-Low.png}
  \end{center}
  
\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{NOT gate revisited}

  \begin{center}
    \hfill
    \begin{tabular}{c|c}
\textbf{Input} & \textbf{Output} \\
      \hline
      L & H \\
      H & L \\
    \end{tabular}
    \hfill
    \begin{tabular}{c|c}
\textbf{Input} & \textbf{Output} \\
      \hline
      0 & 1 \\
      1 & 0 \\
    \end{tabular}
    \hfill
    \begin{tabular}{c|c}
\textbf{Input} & \textbf{Output} \\
      \hline
      False & True \\
      True & False \\
    \end{tabular}
    \hfill
    \mbox{}
  \end{center}

  \only<1>{
    \begin{center}
      \hfill
      \includegraphics[height=4.5cm]{drawings/transistors/CMOS-NOT-gate-input-low.eps}
      \hfill
      \includegraphics[height=4.5cm]{drawings/transistors/CMOS-NOT-gate.eps}
      \hfill
      \mbox{}
    \end{center}
  }

  \only<2>{
    \begin{center}
      \hfill
      \begin{minipage}[c]{0pt}
        \rule[-0.5cm]{0pt}{4.5cm}
      \end{minipage}
      \begin{minipage}[c]{3.5cm}
        \includegraphics[width=\textwidth]{drawings/circuits/CMOS-NOT-gate-input-Low.png}
      \end{minipage}
      \hspace{0.5em}
      \begin{minipage}[c]{3.5cm}
        \includegraphics[width=\textwidth]{drawings/circuits/CMOS-NOT-gate-input-High.png}
      \end{minipage}
      \hfill
      \mbox{}
    \end{center}
  }
  
  \only<3>{
    \begin{center}
      \hfill
      \begin{minipage}[c]{0pt}
        \rule[-0.5cm]{0pt}{4.5cm}
      \end{minipage}
      \begin{minipage}[c]{3.5cm}
        \includegraphics[width=\textwidth]{drawings/circuits/CMOS-NOT-gate-input-High.png}
      \end{minipage}
      \hspace{0.5em}
      \begin{minipage}[c]{3.5cm}
        \includegraphics[width=\textwidth]{images/gates/NOT-gate-both-states-Logisim.png}
      \end{minipage}
      \hfill
      \mbox{}
    \end{center}
  }
  
\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Boolean functions}

  %%BEGIN LANGUAGE en
  Based on the two-element Boolean algebra, or switching algebra.
  %%END LANGUAGE en

  \vspace{-2\baselineskip}
  \begin{center}
    $$
    \begin{array}{c}
      B = \left\{ 0, 1 \right\} \\
      B \times \dots \times B \mapsto B \\
    \end{array}
    $$
  \end{center}

  \hfill
  \begin{minipage}[t]{0.25\textwidth}
    \mbox{}
    
    \includegraphics[width=\linewidth]{images/De_Morgan_Augustus.jpg}
    \scriptsize
    \myhref{https://en.wikipedia.org/wiki/Augustus_De_Morgan}{Augustus De Morgan}
  \end{minipage}
  \hfill
  \begin{minipage}[t]{0.25\textwidth}
    \mbox{}

    \includegraphics[width=\linewidth]{images/ClaudeShannon_MFO3807.jpg}
    \scriptsize
    \myhref{https://en.wikipedia.org/wiki/Claude_Shannon}{Claude Shannon}

    \tiny
    \vspace{0.5\baselineskip}
    \rightline{
      \parbox{0.83\linewidth}{
        \raggedright\em
        Photo by Konrad Jacobs,
        reused \myhref{https://commons.wikimedia.org/wiki/File:ClaudeShannon_MFO3807.jpg}{with permission}
      }
    }
  \end{minipage}
  \hfill
  \begin{minipage}[t]{0.25\textwidth}
    \mbox{}
    
    \includegraphics[width=\linewidth]{images/George_Boole_color.jpg}
    \scriptsize
    \myhref{https://en.wikipedia.org/wiki/George_Boole}{George Boole}
  \end{minipage}
  \hfill
  \mbox{}

\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Number of one-input functions}

  %%\tiny
  %%\small
  
  \vspace{-1\baselineskip}
  \begin{center}
    % "When matrix is used in a frame environment, you need ampersand
    % replacement just as you would when the matrix is in the
    % argument to a command"
    % (https://tex.stackexchange.com/questions/208408/tikz-matrix-undefined-control-sequence):
    \begin{tikzpicture}[column sep=-2em, ampersand replacement=\&]
      \matrix {
        \node(table) {
          \begin{tabular}{c|c}
\textbf{Input} & \textbf{Output} \\
            \hline
            0 & 1 \\
            1 & 0 \\
          \end{tabular}
        };
        \&
        \node(formula) {
          \parbox{17em}{
            \vspace{\baselineskip}
            $$
            \left\}
            \begin{array}{l}
              \\
              \\
            \end{array}
            \right. \hspace{-1em} 2 \,\,\text{positions} \Rightarrow 2^2 = 4
            \,\,\text{combinations}
            $$
          }
        }; \\
      };
    \end{tikzpicture}

    %%\tiny
    \footnotesize
    \newcommand{\keeprowheight}{\rule{0pt}{2.5em}}
    \newlength{\logicbaselength}
    \setlength{\logicbaselength}{2.5cm}
    %\vspace{-0.5\baselineskip}
    \begin{tabular}{llll}
      \begin{tabular}{c|c}
\textbf{Input} & \textbf{Output} \\
        \hline
        0 & 0 \\
        1 & 1 \\
      \end{tabular}
      & identity
      & $f(x\,)=x$
      &
      \parbox[c]{\logicbaselength}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/identity-Boolean-function.png}
      }
      \\
      \keeprowheight
      \begin{tabular}{c|c}
\textbf{Input} & \textbf{Output} \\
        \hline
        0 & 1 \\
        1 & 0 \\
      \end{tabular}
      & NOT
      & $f(x\,)=\overline{x\,}$
      &
      \parbox[c]{\logicbaselength}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/NOT-Boolean-function.png}
      }
      \\
      \keeprowheight
      \begin{tabular}{c|c}
\textbf{Input} & \textbf{Output} \\
        \hline
        0 & 0 \\
        1 & 0 \\
      \end{tabular}
      & constant 0
      & $f(x\,)=0$
      &
      \parbox[c]{\logicbaselength}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/constant-0-Boolean-function.png}
      }
      \\
      \keeprowheight
      \begin{tabular}{c|c}
\textbf{Input} & \textbf{Output} \\
        \hline
        0 & 1 \\
        1 & 1 \\
      \end{tabular}
      & constant 1
      & $f(x\,)=1$
      &
      \parbox[c]{\logicbaselength}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/constant-1-Boolean-function.png}
      }
      \\
    \end{tabular}
    
  \end{center}
    
\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Logic NAND}

  \begin{center}
    \footnotesize

    $X = f(A,B) = \overline{A \cdot B} = \overline{AB}$

    \vspace{0.5\baselineskip}
    \begin{tabular}{c|c|c}
      \textbf{A} & \textbf{B} & \textbf{X}\\
      \hline
      \only<6>{\bf} 0 & \only<6>{\bf} 0 & \only<6>{\bf} 1 \\
      \only<7>{\bf} 0 & \only<7>{\bf} 1 & \only<7>{\bf} 1 \\
      \only<8>{\bf} 1 & \only<8>{\bf} 0 & \only<8>{\bf} 1 \\
      \only<9>{\bf} 1 & \only<9>{\bf} 1 & \only<9>{\bf} 0 \\
    \end{tabular}

    \vspace{\baselineskip}
    \newcommand{\keeprowheight}{\rule[-0.2cm]{0pt}{4cm}}

    \only<1>{
      \keeprowheight
      \includegraphics[width=4cm]{drawings/circuits/CMOS-NAND-gate-half-A1-B1.png}
    }

    \only<2>{
      \keeprowheight
      \includegraphics[width=4cm]{drawings/circuits/CMOS-NAND-gate-half-A1-B0.png}
    }

    \only<3>{
      \keeprowheight
      \includegraphics[width=4cm]{drawings/circuits/CMOS-NAND-gate-half-A0-B1.png}
    }

    \only<4>{
      \keeprowheight
      \includegraphics[width=4cm]{drawings/circuits/CMOS-NAND-gate-half-A0-B0.png}
    }
    
    \only<5,9>{
      \keeprowheight
      \includegraphics[width=4cm]{drawings/circuits/CMOS-NAND-gate-A1-B1.png}
    }
    
    \only<6>{
      \keeprowheight
      \includegraphics[width=4cm]{drawings/circuits/CMOS-NAND-gate-A0-B0.png}
    }
    
    \only<7>{
      \keeprowheight
      \includegraphics[width=4cm]{drawings/circuits/CMOS-NAND-gate-A0-B1.png}
    }
    
    \only<8>{
      \keeprowheight
      \includegraphics[width=4cm]{drawings/circuits/CMOS-NAND-gate-A1-B0.png}
    }
    
    \only<10>{
      \parbox[c]{4cm}{
        \keeprowheight
        \includegraphics[width=\linewidth]{drawings/circuits/CMOS-NAND-gate-A0-B0.png}
      }
      \hspace{2em}
      \parbox[c]{3cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/NAND-gate-A0-B0.png}
      }
    }
    
    \only<11>{
      \parbox[c]{4cm}{
        \keeprowheight
        \includegraphics[width=\linewidth]{drawings/circuits/CMOS-NAND-gate-A0-B0.png}
      }
      \hspace{2em}
      \parbox[c]{3cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/NAND-gate-A0-B0.png}
        \includegraphics[width=\linewidth]{drawings/logic-gates/NAND-gate-A0-B1.png}
        \includegraphics[width=\linewidth]{drawings/logic-gates/NAND-gate-A1-B1.png}
      }
    }
    
  \end{center}

\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Logic NOR}

  \begin{center}
    \footnotesize

    $X = f(A,B) = \overline{A \lor B}$

    \vspace{0.5\baselineskip}
    \begin{tabular}{c|c|c}
      \textbf{A} & \textbf{B} & \textbf{X}\\
      \hline
      \only<2>{\bf} 0 & \only<2>{\bf} 0 & \only<2>{\bf} 1 \\
      \only<3>{\bf} 0 & \only<3>{\bf} 1 & \only<3>{\bf} 0 \\
      \only<4>{\bf} 1 & \only<4>{\bf} 0 & \only<4>{\bf} 0 \\
      \only<5>{\bf} 1 & \only<5>{\bf} 1 & \only<5>{\bf} 0 \\
    \end{tabular}

    \vspace{\baselineskip}
    \newcommand{\keeprowheight}{\rule[-0.2cm]{0pt}{4cm}}

    \only<1-2>{
      \keeprowheight
      \includegraphics[width=4cm]{drawings/circuits/CMOS-NOR-gate-A0-B0.png}
    }

    \only<3>{
      \keeprowheight
      \includegraphics[width=4cm]{drawings/circuits/CMOS-NOR-gate-A0-B1.png}
    }

    \only<4>{
      \keeprowheight
      \includegraphics[width=4cm]{drawings/circuits/CMOS-NOR-gate-A1-B0.png}
    }

    \only<5>{
      \keeprowheight
      \includegraphics[width=4cm]{drawings/circuits/CMOS-NOR-gate-A1-B1.png}
    }

    \only<6>{
      \parbox[c]{4cm}{
        \keeprowheight
        \includegraphics[width=\linewidth]{drawings/circuits/CMOS-NOR-gate-A0-B0.png}
      }
      \hspace{2em}
      \parbox[c]{3cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/NOR-gate-A0-B0.png}
      }
    }
    
    \only<7>{
      \parbox[c]{4cm}{
        \keeprowheight
        \includegraphics[width=\linewidth]{drawings/circuits/CMOS-NOR-gate-A0-B0.png}
      }
      \hspace{2em}
      \parbox[c]{3cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/NOR-gate-A0-B0.png}
        \includegraphics[width=\linewidth]{drawings/logic-gates/NOR-gate-A0-B1.png}
        \includegraphics[width=\linewidth]{drawings/logic-gates/NOR-gate-A1-B1.png}
      }
    }
    
  \end{center}

\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Logic OR (disjunction)}

  \begin{center}
    \footnotesize

    $X = f(A,B) = A \lor B$

    \vspace{0.5\baselineskip}
    \begin{tabular}{c|c|c}
      \textbf{A} & \textbf{B} & \textbf{X}\\
      \hline
      \only<4>{\bf} 0 & \only<4>{\bf} 0 & \only<4>{\bf} 0 \\
      \only<5>{\bf} 0 & \only<5>{\bf} 1 & \only<5>{\bf} 1 \\
      \only<6>{\bf} 1 & \only<6>{\bf} 0 & \only<6>{\bf} 1 \\
      \only<7>{\bf} 1 & \only<7>{\bf} 1 & \only<7>{\bf} 1 \\
    \end{tabular}

    \vspace{\baselineskip}
    \newcommand{\keeprowheight}{\rule[-0.2cm]{0pt}{4cm}}

    \begin{tikzpicture}[column sep=-1em, ampersand replacement=\&]
      \only<1>{
        \node(image) {
          \keeprowheight
          \includegraphics[width=4cm]{drawings/circuits/CMOS-OR-gate-A0-B0.png}
        };
      }

      \only<2>{
        \node(image) {
          \keeprowheight
          \includegraphics[width=4cm]{drawings/circuits/CMOS-OR-gate-A0-B0.png}
        };
        \draw [red,thick] (2,2) to (-2,-2);
        \draw [red,thick] (2,-2) to (-2,2);
      }
    \end{tikzpicture}

    \only<3-4>{
      \keeprowheight
      \includegraphics[width=5cm]{drawings/circuits/CMOS-NOR-NOT-gates-A0-B0.png}
    }

    \only<5>{
      \keeprowheight
      \includegraphics[width=5cm]{drawings/circuits/CMOS-NOR-NOT-gates-A0-B1.png}
    }

    \only<6>{
      \keeprowheight
      \includegraphics[width=5cm]{drawings/circuits/CMOS-NOR-NOT-gates-A1-B0.png}
    }

    \only<7>{
      \keeprowheight
      \includegraphics[width=5cm]{drawings/circuits/CMOS-NOR-NOT-gates-A1-B1.png}
    }

    \only<8>{
      \parbox[c]{5cm}{
        \keeprowheight
        \includegraphics[width=\linewidth]{drawings/circuits/CMOS-NOR-NOT-gates-A0-B0.png}
      }
      \hspace{2em}
      \parbox[c]{3cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/OR-gate-A0-B0.png}
      }
    }
    
    \only<9>{
      \parbox[c]{5cm}{
        \keeprowheight
        \includegraphics[width=\linewidth]{drawings/circuits/CMOS-NOR-NOT-gates-A0-B0.png}
      }
      \hspace{2em}
      \parbox[c]{3cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/OR-gate-A0-B0.png}
        \includegraphics[width=\linewidth]{drawings/logic-gates/OR-gate-A0-B1.png}
        \includegraphics[width=\linewidth]{drawings/logic-gates/OR-gate-A1-B1.png}
      }
    }
    
  \end{center}

\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Two-argument Boolean functions}

  %%\tiny
  %%\small
  
  \vspace{-1\baselineskip}
  \begin{center}
    % "When matrix is used in a frame environment, you need ampersand
    % replacement just as you would when the matrix is in the
    % argument to a command"
    % (https://tex.stackexchange.com/questions/208408/tikz-matrix-undefined-control-sequence):
    \begin{tikzpicture}[column sep=-1em, ampersand replacement=\&]
      \matrix {
        \node(table) {
          \begin{tabular}{c|c|c}
            \textbf{A} & \textbf{B} & \textbf{X} \\
            \hline
            0 & 0 & 1 \\
            0 & 1 & 1 \\
            1 & 0 & 1 \\
            1 & 1 & 0 \\
          \end{tabular}
        };
        \&
        \node(formula) {
          \parbox{17em}{
            \vspace{\baselineskip}
            $$
            \left\}
            \begin{array}{l}
              \\
              \\
              \\
              \\
            \end{array}
            \right. \hspace{-1em} 4 \,\,\text{positions} \Rightarrow 2^{2^2} = 16
            \,\,\text{combinations}
            $$
          }
        }; \\
      };
    \end{tikzpicture}

    \parbox[c]{5cm}{
      \includegraphics[width=\linewidth]{drawings/circuits/CMOS-NOR-NOT-gates-A0-B0.png}
    }
    \parbox[c]{5cm}{
      \includegraphics[width=\linewidth]{drawings/logic-gates/NOR-NOT-A0-B0.png}
    }
    
  \end{center}

\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Multiple-input logic circuits}

  \vspace{-1\baselineskip}
  \begin{center}
    \begin{tabular}{cccc|c}
      \textbf{A} & \textbf{B} & \textbf{C} & \textbf{D} & \textbf{X} \\
      \hline
      0 & 0 & 0 & 0 & 0 \\
      0 & 1 & 0 & 0 & 0 \\
      \multicolumn{4}{c}{\dots} \\
      1 & 1 & 1 & 0 & 0 \\
      1 & 1 & 1 & 1 & 1 \\
    \end{tabular}

    \vfill
    \hfill
    \parbox[c]{1em}{
      \renewcommand{\arraystretch}{1.1}
      \begin{tabular}{r}
        \textbf{A} \\
        \textbf{B} \\
        \textbf{C} \\
        \textbf{D} \\
      \end{tabular}
    }
    \parbox[c]{0.3\textwidth}{
      \includegraphics[width=\linewidth]{drawings/logic-gates/4-input-AND-from-2input-gates-one-0.png}
    }
    \hfill
    \parbox[c]{0.3\textwidth}{
      \includegraphics[width=\linewidth]{drawings/logic-gates/4-input-AND-from-2input-gates-all-1.png}
    }
    \hfill
    \mbox{}
    \vfill

  \end{center}
  
\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Computing arbitrary logic function}

  \newcommand{\termOne}{\overline{x_1}\cdot\overline{x_2}\cdot ... \cdot\overline{x_n}}
  \newcommand{\termTwo}{\overline{x_1}\cdot x_2 \cdot ... \cdot\overline{x_n}}
  \newcommand{\termN}{x_1\cdot x_2 \cdot ... \cdot\overline{x_n}}
  \vspace{-1\baselineskip}
  \begin{center}
    \begin{tabular}{cccc|cc}
      \boldm{$x_1$} & \boldm{$x_2$} & \textbf{\dots} & \boldm{$x_n$} &
      \boldm{$f(x_1,x_2,\dots,x_n)$} &
\textbf{conjunction}
      \\
      \hline
      0 & 0 & \dots & 0 & 1 & $\termOne$ \\
      0 & 1 & \dots & 0 & 1 & $\termTwo$ \\
      0 & 1 & \dots & 0 & 0 & 0 \\
      0 & 1 & \dots & 0 & 0 & 0 \\
      \multicolumn{4}{c|}{\dots} & \multicolumn{2}{c}{\dots} \\
      1 & 1 & \dots & 0 & 1 & $\termN$ \\
      1 & 1 & \dots & 1 & 0 & 0 \\
    \end{tabular}

    \vfill
    \vfill
Disjunctive Normal Form (DNF):
    $$
    \begin{array}{rl}
      f( x_1, x_2, \dots, x_n )
        =  & \termOne \\
      \lor & \termTwo \\
      \lor & \dots \\
      \lor & \termN
    \end{array}
    $$

  \end{center}
  
\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Example: synthesis of the function XOR}

  \begin{center}
    \begin{tabular}{cc|cc}
      \textbf{A} & \textbf{B} & \textbf{X} &
\textbf{conjunction}
      \\
      \hline
      0 & 0 & 0 & \\
      0 & 1 & 1 & $\overline{A} \cdot B$ \\
      1 & 0 & 1 & $A \cdot \overline{B}$ \\
      1 & 1 & 0 & \\
    \end{tabular}

    \vspace{\baselineskip}
DNF:
    $ X = \overline{A} B \lor A \overline{B} $

    \vspace{\baselineskip}
    \only<2->{
      \parbox[c]{1em}{
        \footnotesize
        \renewcommand{\arraystretch}{1.7}
        \begin{tabular}{r}
          \textbf{A} \\
          \textbf{B} \\
          \\
          \\
        \end{tabular}
      }
    }
    \begin{minipage}{0.5\textwidth}
      \only<2,6->{
        \parbox[c]{\textwidth}{
          \includegraphics[width=\linewidth]{drawings/logic-gates/XOR-synthesis-A0-B0.png}
        }
      }

      \only<3>{
        \parbox[c]{\textwidth}{
          \includegraphics[width=\linewidth]{drawings/logic-gates/XOR-synthesis-A0-B1.png}
        }
      }

      \only<4>{
        \parbox[c]{\textwidth}{
          \includegraphics[width=\linewidth]{drawings/logic-gates/XOR-synthesis-A1-B0.png}
        }
      }

      \only<5>{
        \parbox[c]{\textwidth}{
          \includegraphics[width=\linewidth]{drawings/logic-gates/XOR-synthesis-A1-B1.png}
        }
      }
    \end{minipage}
    \only<6>{
      \parbox[c]{3cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/XOR-A0-B0.png}
      }
    }

  \end{center}
  
\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{NAND gate (revisited)}

  \newcommand{\keeprowheight}{\rule[-0.2cm]{0pt}{3.7cm}}

  \begin{center}
    $X = f(A,B) = \overline{AB}$
  
    \vspace{\baselineskip}
    \begin{tabular}{c|c|c}
      \textbf{A} & \textbf{B} & \textbf{X} \\
      \hline
      \only<2>{\bf} 0 & \only<2>{\bf} 0 & \only<2>{\bf} 1 \\
      \only<3>{\bf} 0 & \only<3>{\bf} 1 & \only<3>{\bf} 1 \\
      \only<4>{\bf} 1 & \only<4>{\bf} 0 & \only<4>{\bf} 1 \\
      \only<5>{\bf} 1 & \only<5>{\bf} 1 & \only<5>{\bf} 0 \\
    \end{tabular}

    \vspace{\baselineskip}
    \only<1>{
      \parbox[c]{5cm}{
        \keeprowheight
        \includegraphics[width=\linewidth]{drawings/circuits/CMOS-AND-NOT-gates-A0-B0.png}
      }
      \parbox[c]{5cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/AND-NOT-A0-B0.png}
      }
    }

    \only<2>{
      \parbox[c]{4cm}{
        \keeprowheight
        \includegraphics[width=\linewidth]{drawings/circuits/CMOS-NAND-gate-A0-B0.png}
      }
    }
    \only<2>{
      \parbox[c]{4cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/NAND-gate-A0-B0.png}
      }
    }
    
    \only<3>{
      \parbox[c]{4cm}{
        \keeprowheight
        \includegraphics[width=\linewidth]{drawings/circuits/CMOS-NAND-gate-A0-B1.png}
      }
    }
    \only<3>{
      \parbox[c]{4cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/NAND-gate-A0-B1.png}
      }
    }
    
    \only<4>{
      \parbox[c]{4cm}{
        \keeprowheight
        \includegraphics[width=\linewidth]{drawings/circuits/CMOS-NAND-gate-A1-B0.png}
      }
    }
    \only<4>{
      \parbox[c]{4cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/NAND-gate-A1-B0.png}
      }
    }
    
    \only<5>{
      \parbox[c]{4cm}{
        \keeprowheight
        \includegraphics[width=\linewidth]{drawings/circuits/CMOS-NAND-gate-A1-B1.png}
      }
    }
    \only<5>{
      \parbox[c]{4cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/NAND-gate-A1-B1.png}
      }
    }
    
  \end{center}

\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{NAND – a Universal Gate}

  \begin{center}
    \begin{tabular}{c|c|c}
      \textbf{A} & \textbf{B} & \textbf{X} \\
      \hline
      0 & 0 & 1 \\
      0 & 1 & 1 \\
      1 & 0 & 1 \\
      1 & 1 & 0 \\
    \end{tabular}

    \vfill
    \begin{tabular}{lcl}
      \parbox[c]{4cm}{
        \includegraphics[height=1cm]{drawings/logic-gates/NOT-from-NAND-input-0.png}
      }
      &
      $\Leftrightarrow$
      &
      \parbox[c]{3cm}{
        \includegraphics[width=0.7\linewidth]{drawings/logic-gates/NOT-Boolean-function.png}
      }
      \\
      \parbox[c]{4cm}{
        \includegraphics[height=1cm]{drawings/logic-gates/AND-from-NAND-A0-B0.png}
      }
      &
      $\Leftrightarrow$
      &
      \parbox[c]{3cm}{
        \includegraphics[height=1cm]{drawings/logic-gates/AND-gate-A0-B0.png}
      }
      \\
      \parbox[c]{4cm}{
        \includegraphics[height=1.5cm]{drawings/logic-gates/OR-from-NAND-A0-B0.png}
      }
      &
      $\Leftrightarrow$
      &
      \parbox[c]{3cm}{
        \includegraphics[height=1cm]{drawings/logic-gates/OR-gate-A0-B0.png}
      }
    \end{tabular}
  \end{center}

\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Dual gates}

  \begin{center}
    \begin{tabular}{cc|cc|c|c|c|c|c}
      \boldm{$A$} & \boldm{$B$} & \boldm{$\overline{A}$} &
      \boldm{$\overline{B}$} &
      \boldm{$\overline{A \cdot B}$} &
      \boldm{$\overline{A}\cdot\overline{B}$} &
      \boldm{$\overline{\overline{A}\cdot\overline{B}}$} &
      \boldm{$A \lor B$}\\
      \hline
      0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\
      0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 \\
      1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\
      1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\
    \end{tabular}
  \end{center}

  \begin{center}
    \parbox[c]{0pt}{
      \rule{0pt}{3.5cm}
    }
    \begin{minipage}[c]{0.7\textwidth}
      \begin{center}
        \only<1>{
          \parbox[c]{4cm}{
            \rightline{
              \includegraphics[height=1.5cm]{drawings/logic-gates/OR-from-NAND-A0-B0.png}
            }
          }
          \parbox[c]{3cm}{
            \includegraphics[height=1cm]{drawings/logic-gates/OR-gate-A0-B0.png}
          }
        }

        \only<2>{
          \parbox[c]{4cm}{
            \rightline{
              \includegraphics[height=1cm]{drawings/logic-gates/NOT-AND-NOT-A0-B0.png}
            }
          }
          \parbox[c]{3cm}{
            \includegraphics[height=1cm]{drawings/logic-gates/OR-gate-A0-B0.png}
          }
        }
        
        \only<3>{
          \parbox[c]{4cm}{
            \rightline{
              \includegraphics[height=1cm]{drawings/logic-gates/NOT-AND-NOT-A0-B1.png}
            }
          }
          \parbox[c]{3cm}{
            \includegraphics[height=1cm]{drawings/logic-gates/OR-gate-A0-B1.png}
          }
        }
        
        \only<4>{
          \parbox[c]{4cm}{
            \rightline{
              \includegraphics[height=1cm]{drawings/logic-gates/NOT-AND-NOT-A1-B0.png}
            }
          }
          \parbox[c]{3cm}{
            \includegraphics[height=1cm]{drawings/logic-gates/OR-gate-A1-B0.png}
          }
        }
        
        \only<5>{
          \parbox[c]{4cm}{
            \rightline{
              \includegraphics[height=1cm]{drawings/logic-gates/NOT-AND-NOT-A1-B1.png}
            }
          }
          \parbox[c]{3cm}{
            \includegraphics[height=1cm]{drawings/logic-gates/OR-gate-A1-B1.png}
          }
        }

        \only<6>{
          \parbox[c]{4cm}{
            \rightline{
              \includegraphics[height=1cm]{drawings/logic-gates/NOT-AND-NOT-A0-B0.png}
            }
          }
          \parbox[c]{3cm}{
            \includegraphics[height=1cm]{drawings/logic-gates/OR-gate-A0-B0.png}
          }
        }

        \only<6>{
          $$
          \begin{array}{rclcl}
            A \lor B
            &=&
            \overline{\overline{A} \cdot \overline{B}}
            \\
            \overline{\overline{A}}
            &=&
            A
            \\
            \overline{A \lor B}
            &=&
            \overline{\overline{\overline{A} \cdot \overline{B}}}
            &=&
            \overline{A} \cdot \overline{B}
          \end{array}
          $$
        }
      \end{center}
    \end{minipage}
  \end{center}

\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Dual gates, De Morgan laws}

  \newcommand{\ol}{\overline}
  
  \begin{center}
    \begin{tabular}{ccc}
      \parbox[c]{2.5cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/NOT-NAND-A0-B0.png}

      }
      &
      \parbox[c]{1em}{
        $\Leftrightarrow$
      }
      &
      \parbox[c]{2.5cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/OR-gate-A0-B0.png}
      }
      \\
      \\
      \parbox[c]{2.5cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/NOT-NOR-A0-B0.png}
      }
      &
      \parbox[c]{1em}{
        $\Leftrightarrow$
      }
      &
      \parbox[c]{2.5cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/AND-gate-A0-B0.png}
      }
    \end{tabular}

    \vspace{0.5\baselineskip}
    $$
    \left.
    \begin{array}{ccc}
      \ol{\ol{A} \cdot \ol{B}}
      &=&
      A \lor B
      \\
      \ol{\ol{A} \lor \ol{B}}
      &=&
      A \cdot B
    \end{array}
    \right\} \,\text{
dual functions
    }
    $$
    
    \vspace{-0.5\baselineskip}
    $$
    \left.
    \begin{array}{ccc}
      \ol{A \lor B}
      &=& \ol{A} \cdot \ol{B}
      \\
      \ol{A \cdot B}
      &=&
      \ol{A} \lor \ol{B}
    \end{array}
    \right\} \,\text{
De Morgan laws
    }
    $$

    \vspace{-\baselineskip}
    $$
    h \ \ \text{
is dual of
    }\ \  f
    \ \ \underset{\text{def}}{\Leftrightarrow}\ %
    h(x_1,x_2,\dots,x_n) = \ol{f(\ol{x_1},\ol{x_2},\dots,\ol{x_n})}
    $$
    
  \end{center}
  
\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Another universal gate: NOR}

  \begin{center}
    \begin{tabular}{ccc}
      \parbox[c]{3cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/NAND-gate-A0-B0.png}
      }
      &
dual to
      &
      \parbox[c]{3cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/NOR-gate-A0-B0.png}
      }
      \\
      \\
      \parbox[c]{3cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/AND-gate-A0-B0.png}
      }
      &
dual to
      &
      \parbox[c]{3cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/OR-gate-A0-B0.png}
      }
      \\
      \\
      \parbox[c]{3cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/NOT-Boolean-function.png}
      }
      &
dual to
      &
      \parbox[c]{3cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/NOT-Boolean-function.png}
      }
    \end{tabular}

  \end{center}

\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Complete systems of logic functions}

Superposition:

  $$h(x_1,\dots,x_n) = f(g_1(x_1,\dots,x_n),\dots,g_m(x_1,\dots,x_n))$$

Example:

  $$
  \text{NOT}(\text{AND}(x_1,\text{NOT}(x_2)) \,\underset{\text{def}}{\equiv}\,
  \overline{x_1\overline{x_2}} =
  \overline{x_1}\lor\overline{\overline{x_2}} =
  \overline{x_1} \lor x_2
  $$

Complete systems (examples):

  \begin{center}
    \small
    \begin{tabular}{cl}
      $\left\{ \text{AND}, \text{OR}, \text{NOT} \right\} = \left\{ \cdot, \lor,
      \overline{X\,} \right\}$
      &
(not minimal!)
      \\
      $\left\{ \text{AND}, \text{NOT} \right\} = \left\{ \cdot, \overline{X\,} \right\}$
      \\
      $\left\{ \text{OR}, \text{NOT} \right\} = \left\{ \lor, \overline{X\,} \right\}$
      \\
      $\left\{ \text{AND}, \text{XOR}, 1 \right\} = \left\{ \cdot, \oplus, 1 \right\}$
      \\
      $\left\{ \text{OR}, \text{XOR}, 1 \right\} = \left\{ \lor, \oplus, 1 \right\}$
      \\
      $\left\{ \text{NAND} \right\} = \left\{ \uparrow \right\}$
      &
      \myhref{https://en.wikipedia.org/wiki/Sheffer_stroke}{Sheffer
        stroke}
      \\
      $\left\{ \text{NOR} \right\} = \left\{ \downarrow \right\}$
      &
      \myhref{https://en.wikipedia.org/wiki/Logical_NOR}{Peirce's
        arrow/Quine's dagger}
    \end{tabular}
  \end{center}

\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Closed Boolean function classes}

  %%\footnotesize
  \small
Function classes closed under superposition:
  
  \newcommand{\ol}{\overline}
  \begin{enumerate}
  \item
    $T_0$:
zero-preserving:
    $$ f(0,0,\dots, 0) = 0 $$

  \item
    $T_1$:
one-preserving:
    $$ f(1,1,\dots, 1) = 1 $$
    
  \item
    $S$:
self-dual:
    $$
    f(x_1,x_2,\dots, x_n) =
    \ol{f(\ol{x_1},\ol{x_2},\dots,\ol{x_n})}
    $$
    
  \item
    $L$:
linear:
    $$
    f(x_1,x_2,\dots, x_n) = a_0 \oplus a_1 x_1 \oplus \dots \oplus a_n x_n
    $$
    
  \item
    $M$:
monotonic:
    $$
    \begin{array}{c}
      \vec{a} \underset{\text{def}}{\equiv} (a_1, a_2, \dots, a_n ) \\
      \vec{a} \leq \vec{b} \underset{\text{def}}{\Leftrightarrow}
      \forall i \in \{1,\dots,n\}: a_i \leq b_i \\
      f \in M \underset{\text{def}}{\Leftrightarrow}
      \vec{a} \leq \vec{b} \Rightarrow f(\vec{a}) \leq f(\vec{b})
    \end{array}
    $$
    
  \end{enumerate}
  
\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Post's theorem}

  \small
  %%BEGIN LANGUAGE en
  A Boolean function set $B = \{ f_1, f_2, \dots, f_n \}$ is
  complete under superposition \textbf{iff}:
  %%END LANGUAGE en

  \begin{enumerate}
  \item
it contains a function that does not preserve 0:
    $$ \exists\, f_i \in B: f_i \not\in T_0 $$
  \item
it contains a function that does not preserve 1:
    $$ \exists\, f_i \in B: f_i \not\in T_1 $$
  \item
it contains a function that is not self-dual:
    $$ \exists\, f_i \in B: f_i \not\in S $$
  \item
it contains a function that is not linear:
    $$ \exists\, f_i \in B: f_i \not\in L $$
  \item
it contains a function that is not monotonic:
    $$ \exists\, f_i \in B: f_i \not\in M $$
  \end{enumerate}
  
\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Apollo Guidance Computer gates}

  \begin{center}
    \includegraphics[height=3cm]{images/Agc_nor2a.jpg}

    \vspace{0.5\baselineskip}
    \parbox[c]{2.5cm}{
      \includegraphics[width=\linewidth]{images/Agc_flatp.jpg}
    }
    \hspace{2em}
    \parbox[c]{7cm}{
      \includegraphics[width=\linewidth]{drawings/logic-gates/3-input-NOR-RTL-gate-all-0.png}
    }
  \end{center}
  
\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Achievements so far ...}

  \begin{center}
    \begin{tabular}{cc}
      \parbox[c]{3cm}{
        \includegraphics[width=\linewidth]{drawings/transistors/transistor-switch-voltages-coloured.eps}
      }
      &
      \parbox[c]{4cm}{
        \includegraphics[width=\linewidth]{drawings/circuits/CMOS-NOT-gate-input-Low.png}
      }
      \\
      \parbox[c]{4cm}{
        \includegraphics[width=\linewidth]{drawings/circuits/CMOS-NAND-gate-A0-B1.png}
      }
      &
      \parbox[c]{4cm}{
        \includegraphics[width=\linewidth]{drawings/logic-gates/XOR-synthesis-A1-B0.png}
      }
      \\
    \end{tabular}
  \end{center}
  
\end{frame}

%------------------------------------------------------------------------------

\begin{frame}
\frametitle{Take home messages}

  \begin{itemize}
  \item
    %%BEGIN LANGUAGE en
    Digital circuits can be described using Boolean algebra;
    %%END LANGUAGE en
  \item
    %%BEGIN LANGUAGE en
    Any Boolean function can be implemented using a complete set of
    Boolean functions, as per Post's theorem; each of functions NAND and 
    NOR alone form a complete set and any digital circuit can be build
    from them; 
    %%END LANGUAGE en
  \item
    %%BEGIN LANGUAGE en
    All Boolean functions can be implemented as electric (e.g. CMOS
    FET) switches;
    %%END LANGUAGE en
  \item
    %%BEGIN LANGUAGE en
    All blocks of a computer can be built from controllable electric
    switches; modern computers use CMOS field effect transistors.
    %%END LANGUAGE en
  \end{itemize}
  
\end{frame}

%------------------------------------------------------------------------------

%% \begin{frame}[allowframebreaks]
%%   %%LANGUAGE en \frametitle{References}
%%   %%LANGUAGE lt \frametitle{Šaltiniai}
%%   %%LANGUAGE ru \frametitle{Источники}
%% 
%%   %%\scriptsize
%%   %%\bibliographystyle{plain}
%%   %%\bibliographystyle{apalike}
%%   %%\bibliography{bibliography/citations}
%%   \renewcommand{\bibfont}{\scriptsize}
%%   \printbibliography
%% 
%% \end{frame}

%------------------------------------------------------------------------------

\end{document}
% 2023-09-11 18:14:50 EEST
