%\documentclass[dvipdfmx,t,serif,mathserif,14pt]{beamer} % t: from top; serif: rmdefault
\documentclass[dvipdfmx,t,14pt]{beamer} % t: from top; serif: rmdefault
\usepackage{mybeamer}

\newcommand{\PDFTITLE}{論理回路入門（３）}
\newcommand{\PDFSUBJECT}{一年生秋学期}
\newcommand{\PDFAUTHOR}{法政大学情報科学部}
\newcommand{\PDFKEYWORDS}{ブール代数の定理、ド・モルガンの法則、完全系、NANDゲートのみで回路を構成、NOR ゲートのみで回路を構成}
\date{2023 年 10 月 10 日 (火)}

\title{\PDFTITLE} % bottom PDFTITLE
\subtitle{ブール代数と完全系}
\author[\PDFAUTHOR]{李　亜民} % bottom PDFAUTHOR; titlepage Yamin Li

\hypersetup{
  pdftitle=\PDFTITLE,
  pdfsubject=\PDFSUBJECT,
  pdfauthor=\PDFAUTHOR,
  pdfkeywords=\PDFKEYWORDS
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\everymath={\sf}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{\PDFTITLE}
\begin{frame}
  \titlepage
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%------------------------------------------------ SLIDE -
\input{mybackgroundcolor.tex}
%------------------------------------------------ SLIDE -
\section{ブール代数と完全系}
\begin{frame}\frametitle{\secname}
  \hspace*{-4mm}
  \textcolor{blue}{ポイント}

  \begin{itemize}
    \setlength{\itemsep}{1.1mm}
  \item\textcolor{blue}{ブール代数の定理}
  \item\textcolor{blue}{ド・モルガンの法則の理解と証明}
  \item\textcolor{blue}{ブール代数の定理を用いた証明}
  \item\textcolor{blue}{完全系}
    \begin{itemize}
    \item\textcolor{blue}{AND と OR、NOT ゲート}
    \item\textcolor{blue}{NAND ゲートのみ}
    \item\textcolor{blue}{NOR ゲートのみ}
    \end{itemize}
  \item\textcolor{blue}{NAND ゲートのみで回路を構成}
  \item\textcolor{blue}{NOR ゲートのみで回路を構成}
  \end{itemize}

\end{frame}
%------------------------------------------------ SLIDE -
\section{復習: 基本的な論理演算 1. AND}
\begin{frame}\frametitle{\secname}
  \begin{enumerate}
    \setcounter{enumi}{0}
  \item AND (アンド)

    論理積 (かつ) \hfill\textcolor{magenta}{(Verilog HDLの表現)}
    
    『例』 F $=$ A $\cdot$ B $=$ A \ B \hfill\textcolor{magenta}{({\tt{F = A \& B}})}

    \vspace{5mm}
    \renewcommand{\arraystretch}{1.1}
    \setlength{\tabcolsep}{1.5mm}
    \begin{tabular}[t]{cccccr}
      \textcolor{red} 0 & $\cdot$ & \textcolor{red} 0 & $=$ & \textcolor{red} 0 & \textcolor{red}{偽}\\
      \textcolor{red} 0 & $\cdot$ & 1 & $=$ & \textcolor{red} 0 & \textcolor{red}{偽}\\
      1 & $\cdot$ & \textcolor{red} 0 & $=$ & \textcolor{red} 0 & \textcolor{red}{偽}\\
      \textcolor{blue} 1 & $\cdot$ & \textcolor{blue} 1 & $=$ & \textcolor{blue} 1 &
      $\cdots\cdots\cdots\cdots\cdots$\textcolor{blue}{真} {\hspace*{2.43mm}}かつ{\hspace*{2.43mm}} \textcolor{blue}{真} $=$ \textcolor{blue}{真}\\
      & \phantom{$\oplus$}
    \end{tabular}

    \fontsize{13pt}{15}\selectfont

    論理積は、入力値がすべて１のときに１を出力する。

    \textcolor{red}{それ以外}の入力値のときは０を出力する。

  \end{enumerate}

\end{frame}
%------------------------------------------------ SLIDE -
\section{復習: 基本的な論理演算 2. OR}
\begin{frame}\frametitle{\secname}
  \begin{enumerate}
    \setcounter{enumi}{1}
  \item OR (オア)

    論理和 (または) \hfill\textcolor{magenta}{(Verilog HDLの表現)}

    『例』 F $=$ A $+$ B \hfill\textcolor{magenta}{({\tt{F = A | B}})}

    \vspace{5mm}
    \renewcommand{\arraystretch}{1.1}
    \setlength{\tabcolsep}{1.5mm}
    \begin{tabular}[t]{cccccr}
      \textcolor{red} 0 & $+$ & \textcolor{red} 0 & $=$ & \textcolor{red} 0 & $\cdots\cdots\cdots\cdots\cdots$\textcolor{red}{偽} または \textcolor{red}{偽} $=$ \textcolor{red}{偽}\\
      0 & $+$ & \textcolor{blue} 1 & $=$ & \textcolor{blue} 1 & \textcolor{blue}{真}\\
      \textcolor{blue} 1 & $+$ & 0 & $=$ & \textcolor{blue} 1 & \textcolor{blue}{真}\\
      \textcolor{blue} 1 & $+$ & \textcolor{blue} 1 & $=$ & \textcolor{blue} 1 & \textcolor{blue}{真}\\
      & \phantom{$\oplus$}
    \end{tabular}

    \fontsize{13pt}{15}\selectfont

    論理和は、入力値がすべて０のときに０を出力する。
    
    \textcolor{red}{それ以外}の入力値のときは１を出力する。

  \end{enumerate}

\end{frame}
%------------------------------------------------ SLIDE -
\section{復習: 基本的な論理演算 3. NOT}
\begin{frame}\frametitle{\secname}
  \begin{enumerate}
    \setcounter{enumi}{2}
  \item NOT (ノット)

    否定 \hfill\textcolor{magenta}{(Verilog HDLの表現)}

    『例』 F $=$ $\overline{\mbox{A}}$ \hfill\textcolor{magenta}{({\tt{F = \texttt{\~}A}})}

    \vspace{5mm}
    \renewcommand{\arraystretch}{1.1}
    \setlength{\tabcolsep}{1.5mm}
    \begin{tabular}[t]{cccr}
      $\overline{\mbox{\textcolor{red}  {0}}}$ & $=$ & \textcolor{blue} 1 & $\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots$\hspace{1.5mm}\textcolor{red}{偽}の否定 $=$ \textcolor{blue}{真}\\
      $\overline{\mbox{\textcolor{blue} {1}}}$ & $=$ & \textcolor{red}  0 & $\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots$\hspace{1.5mm}\textcolor{blue}{真}の否定 $=$ \textcolor{red}{偽}\\
    \end{tabular}

    \fontsize{13pt}{15}\selectfont

    \vspace{19.72mm}
    \scalebox{1}{論理否定は、入力された値が０なら１に、}

    \scalebox{1}{\hspace{57.13mm}１なら０に反転する。}

  \end{enumerate}

\end{frame}
%------------------------------------------------ SLIDE -
\section{ブール代数}
\begin{frame}\frametitle{\secname}
  \renewcommand\baselinestretch{1.5}
  ブール代数 (Boolean Algebra) とは、ジョージ・ブールが 19 世紀中頃に考案した代数系の一つである。

  \vspace{3mm}
  \begin{center}
    ブール代数と集合論と命題論理の関係
  \end{center}
  
  \fontsize{10pt}{12}\selectfont
  \renewcommand\baselinestretch{1.9}
  \setlength{\tabcolsep}{3.8pt}

  \begin{tabular}{lc|lc|lc|c}\hline
    \multicolumn{2}{c|}{集合論}  & \multicolumn{2}{c|}{命題論理} & \multicolumn{2}{c|}{\textcolor{blue}{ブール代数}} & \textcolor{blue}{Verilog HDL}\\\hline\hline
    積集合     & \textcolor{red}{$\mathsf{A\ \cap   \ B}$} &
    連言       & \textcolor{red}{$\mathsf{A\ \wedge \ B}$} &
    \textcolor{blue}{論理積 (AND)} & \textcolor{red}{$\mathsf{A\ \cdot  \ B}$} & \textcolor{red}{$\mathsf{A}$ \& $\mathsf{B}$}\\\hline
    %
    和集合     & \textcolor{red}{$\mathsf{A\ \cup   \ B}$} &
    選言       & \textcolor{red}{$\mathsf{A\ \vee   \ B}$} &
    \textcolor{blue}{論理和 (OR)}  & \textcolor{red}{$\mathsf{A  +        B}$} & \textcolor{red}{$\mathsf{A}$ $\mid$ $\mathsf{B}$}\\\hline
    %
    補集合       & \textcolor{red}{$\mathsf{A^c}$}           &
    否定         & \textcolor{red}{$\neg$$\mathsf{A}$}       &
    \textcolor{blue}{否定 (NOT)}   & \textcolor{red}{$\mathsf{\overline{A}}$} & \textcolor{red}{$\sim$$\mathsf{A}$}\\\hline
    %
    全体集合     & \textcolor{red}{$\mathsf{U}$}             &
    真          & \textcolor{red}{1 または $\mathsf{T}$}     &
    \textcolor{blue}{論理 1}      & \textcolor{red}{1}                        &  \textcolor{red}{1}\\\hline
    %
    空集合      & \textcolor{red}{$\varnothing$}     &
    偽          & \textcolor{red}{0 または $\mathsf{F}$}    &
    \textcolor{blue}{論理 0}      & \textcolor{red}{0}                        & \textcolor{red}{0}\\\hline
  \end{tabular}

\end{frame}
%------------------------------------------------ SLIDE -
\section{ブール代数の定理}
\begin{frame}\frametitle{\secname}

    \vspace{-2mm}
    \begin{enumerate}
      \setlength{\itemsep}{0.3em}

    \item $\mathsf{ A\ \cdot\ A = A}$ \cdotfill{冪等律}

    \item $\mathsf{ A + A = A}$ \cdotfill{冪等律}

    \item $\mathsf{ A \ \cdot \ B  = B \ \cdot \ A}$ \cdotfill{交換律}

    \item $\mathsf{ A +  B  = B  +  A}$ \cdotfill{交換律}

    \item $\mathsf{\mbox{(}A \ \cdot \ B\mbox{)} \ \cdot \ C  =  A \ \cdot \ \mbox{(}B \ \cdot \ C\mbox{)}}$ \cdotfill{結合律}

    \item $\mathsf{\mbox{(}A +  B\mbox{)} + C  =  A + \mbox{(}B  +  C\mbox{)}}$ \cdotfill{結合律}

    \item $\mathsf{ A \ \cdot \ \mbox{(}B  + C\mbox{)} = \mbox{(}A \ \cdot \ B\mbox{)} + \mbox{(}A \ \cdot \ C\mbox{)}}$ \cdotfill{分配律}

    \item $\mathsf{ A + \mbox{(}B \ \cdot \ C\mbox{)} = \mbox{(}A +  B\mbox{)} \ \cdot \ \mbox{(}A + C\mbox{)}}$ \cdotfill{分配律}

    \item $\mathsf{ A \ \cdot \ \mbox{(}A +  B\mbox{)} =  A}$ \cdotfill{吸収律}

    \item $\mathsf{ A + \mbox{(}A \ \cdot \ B\mbox{)} =  A}$ \cdotfill{吸収律}

    \end{enumerate}
\end{frame}
%------------------------------------------------ SLIDE -
\section{ブール代数の定理}
\begin{frame}\frametitle{\secname}

  \vspace{-2mm}
  \begin{enumerate}
    \setlength{\itemsep}{0.3em}
    \setcounter{enumi}{10}

  \item $\mathsf{A\ \cdot \ 0 = 0}$ \cdotfill{支配律}

  \item $\mathsf{A + 1 = 1}$ \cdotfill{支配律}

  \item $\mathsf{A\ \cdot \ 1 = A}$ \cdotfill{同一律}

  \item $\mathsf{A + 0 = A}$ \cdotfill{同一律}

  \item $\mathsf{A\ \cdot\ \overline{A} = 0}$ \cdotfill{補元律}

  \item $\mathsf{A + \overline{A} = 1}$ \cdotfill{補元律}

  \item $\mathsf{\overline{\overline{A}} = A}$ \cdotfill{対合律}

    \vspace{6.85mm}

  \item $\mathsf{\overline{A \ \cdot \ B} =  \overline{A}  +   \overline{B}}$ \cdotfill{ド・モルガンの法則}

  \item $\mathsf{\overline{A + B} =  \overline{A} \ \cdot \ \overline{B}}$ \cdotfill{ド・モルガンの法則}

  \end{enumerate}
\end{frame}
%------------------------------------------------ SLIDE -
\section{ブール代数の定理の証明}
\begin{frame}\frametitle{\secname}
\vspace{10mm}
\fontsize{28pt}{57}\selectfont
  \textcolor{blue}{すべてのブール代数の定理は真理値表で証明できる。}
\end{frame}
%------------------------------------------------ SLIDE -
\section{ブール代数の定理の証明（例）}
\begin{frame}\frametitle{\secname}
  証明: ~ \textcolor{red}{$\mathsf{A \cdot \mbox{(}B  + C\mbox{)} = \mbox{(}A \cdot B\mbox{)} + \mbox{(}A \cdot C\mbox{)}}$} \cdotfill{分配律}

  \vspace{3mm}
  \fontsize{12pt}{16}\selectfont
  \renewcommand{\arraystretch}{1}
  \setlength{\tabcolsep}{4pt}
  \begin{tabular}{ccc|c|c|c|c|c}\hline
    \multicolumn{3}{c|}{入力} & \multicolumn{2}{c|}{左辺} & \multicolumn{3}{c}{右辺}\\\hline
    $\mathsf{A}$          & $\mathsf{B}$           &  $\mathsf{C}$ &
    $\mathsf{\mbox{(}B+C\mbox{)}}$      & \textcolor{red}{$\mathsf{A\cdot\mbox{(}B+C\mbox{)}}$} &
    $\mathsf{\mbox{(}A\cdot B\mbox{)}}$ & $\mathsf{\mbox{(}A\cdot C\mbox{)}}$  &\textcolor{red}{$\mathsf{\mbox{(}A\cdot B\mbox{)}+\mbox{(}A\cdot C\mbox{)}}$}\\\hline\hline
      0 & 0 & 0 &   0 &\textcolor{red}{0} &   0 & 0 &\textcolor{red}{0}\\\hline
      0 & 0 & 1 &   1 &\textcolor{red}{0} &   0 & 0 &\textcolor{red}{0}\\\hline
      0 & 1 & 0 &   1 &\textcolor{red}{0} &   0 & 0 &\textcolor{red}{0}\\\hline
      0 & 1 & 1 &   1 &\textcolor{red}{0} &   0 & 0 &\textcolor{red}{0}\\\hline
      1 & 0 & 0 &   0 &\textcolor{red}{0} &   0 & 0 &\textcolor{red}{0}\\\hline
      1 & 0 & 1 &   1 &\textcolor{red}{1} &   0 & 1 &\textcolor{red}{1}\\\hline
      1 & 1 & 0 &   1 &\textcolor{red}{1} &   1 & 0 &\textcolor{red}{1}\\\hline
      1 & 1 & 1 &   1 &\textcolor{red}{1} &   1 & 1 &\textcolor{red}{1}\\\hline
  \end{tabular}

  \vspace{3mm}
  \resizebox{1.015\textwidth}{!}{入力の全てのパターンに対する左辺と右辺は出力が等しいであるため、分配律は成り立つ。}

\end{frame}
%------------------------------------------------ SLIDE -
\section{ブール代数の定理の証明（例）}
\begin{frame}\frametitle{\secname}
  証明: ~ \textcolor{red}{$\mathsf{A + \mbox{(}B \cdot C\mbox{)} = \mbox{(}A + B\mbox{)} \cdot \mbox{(}A + C\mbox{)}}$} \cdotfill{分配律}

  \vspace{3mm}
  \fontsize{12pt}{16}\selectfont
  \renewcommand{\arraystretch}{1}
  \setlength{\tabcolsep}{4pt}
  \begin{tabular}{ccc|c|c|c|c|c}\hline
    \multicolumn{3}{c|}{入力} & \multicolumn{2}{c|}{左辺} & \multicolumn{3}{c}{右辺}\\\hline
    $\mathsf{A}$ & $\mathsf{B}$ &  $\mathsf{C}$ &
    $\mathsf{\mbox{(}B \hspace{.444mm}\cdot\hspace{.444mm} C\mbox{)}}$ &\textcolor{red}{$\mathsf{A \hspace{-.444mm} + \hspace{-.444mm} \mbox{(}B \cdot C\mbox{)}}$} &
    $\mathsf{\mbox{(}A \hspace{-.444mm} + \hspace{-.444mm} B\mbox{)}}$ & $\mathsf{\mbox{(}A \hspace{-.444mm} + \hspace{-.444mm} C\mbox{)}}$ &
    \textcolor{red}{$\mathsf{\mbox{(}A \hspace{-.444mm} + \hspace{-.444mm} B\mbox{)} \cdot \mbox{(}A \hspace{-.444mm} + \hspace{-.444mm} C\mbox{)}}$}\\\hline\hline
    0 & 0 & 0 &   0 &\textcolor{red}{0} &   0 & 0 &\textcolor{red}{0}\\\hline
    0 & 0 & 1 &   0 &\textcolor{red}{0} &   0 & 1 &\textcolor{red}{0}\\\hline
    0 & 1 & 0 &   0 &\textcolor{red}{0} &   1 & 0 &\textcolor{red}{0}\\\hline
    0 & 1 & 1 &   1 &\textcolor{red}{1} &   1 & 1 &\textcolor{red}{1}\\\hline
    1 & 0 & 0 &   0 &\textcolor{red}{1} &   1 & 1 &\textcolor{red}{1}\\\hline
    1 & 0 & 1 &   0 &\textcolor{red}{1} &   1 & 1 &\textcolor{red}{1}\\\hline
    1 & 1 & 0 &   0 &\textcolor{red}{1} &   1 & 1 &\textcolor{red}{1}\\\hline
    1 & 1 & 1 &   1 &\textcolor{red}{1} &   1 & 1 &\textcolor{red}{1}\\\hline
  \end{tabular}

  \vspace{3mm}
  \resizebox{1.015\textwidth}{!}{入力の全てのパターンに対する左辺と右辺は出力が等しいであるため、分配律は成り立つ。}

\end{frame}
%------------------------------------------------ SLIDE -
\section{分配律の回路 (Verilog HDL)}
\begin{frame}[fragile]\frametitle{\secname}
  \textcolor{red}{$\mathsf{A \cdot \mbox{(}B  + C\mbox{)} = \mbox{(}A \cdot B\mbox{)} + \mbox{(}A \cdot C\mbox{)}}$} \cdotfill{Equ. 1}

  \textcolor{red}{$\mathsf{A + \mbox{(}B \cdot C\mbox{)} = \mbox{(}A + B\mbox{)} \cdot \mbox{(}A + C\mbox{)}}$} \cdotfill{Equ. 2}

  \vspace{4.22mm}
\fontsize{11pt}{11.5}\selectfont
\begin{code}
`timescale 1ns/1ns

module distributive_law (A, B, C, P, Q, S, T);
    input  A, B, C;
    output P, Q, S, T;

    assign P =  A & (B | C);      // Equ. 1's left  side
    assign Q = (A & B) | (A & C); // Equ. 1's right side

    assign S =  A | (B & C);      // Equ. 2's left  side
    assign T = (A | B) & (A | C); // Equ. 2's right side

endmodule
\end{code}

\vspace{-8mm}
\hfill
\href{https://yamin.cis.k.hosei.ac.jp/lectures/logic/distributive_law.v}{\color{blue}\underline{distributive\_law.v}}~~~

\end{frame}
%------------------------------------------------ SLIDE -
\section{分配律の回路 (テストベンチ)}
\begin{frame}[fragile]\frametitle{\secname}
\fontsize{11pt}{11.5}\selectfont
\begin{code}
`timescale 1ns/1ns
module distributive_law_tb;
    reg  A, B, C;
    wire P, Q, S, T;
    distributive_law i0 (A, B, C, P, Q, S, T);
    initial begin
        #0 A = 0; B = 0; C = 0;
        #8 $finish;
    end
    always #1 A = ~A;
    always #2 B = ~B;
    always #4 C = ~C;
    initial begin
        $dumpfile ("distributive_law.vcd");
        $dumpvars;
    end
endmodule
\end{code}

\vspace{-8mm}
\hfill
\href{https://yamin.cis.k.hosei.ac.jp/lectures/logic/distributive_law_tb.v}{\color{blue}\underline{distributive\_law\_tb.v}}~~~

\end{frame}
%------------------------------------------------ SLIDE -
\section{分配律の回路 (波形)}
\begin{frame}[fragile]\frametitle{\secname}
\vspace{-5mm}
\begin{verbatim}
% iverilog -Wall -o distributive_law \
  distributive_law_tb.v distributive_law.v
% ./distributive_law
% gtkwave distributive_law.vcd
\end{verbatim}

\vspace{-1mm}
  \includegraphics[width=.9\textwidth]{figs/distributive_law_vcd_crop.png}

  \fontsize{13pt}{13}\selectfont
  \white
  %\vspace{-4mm}
  \colorbox{blue}{\parbox{.882\textwidth}{$P=A \cdot \mbox{(}B  + C\mbox{)} \, === \, \mbox{(}A \cdot B\mbox{)} + \mbox{(}A \cdot C\mbox{)}=Q$\hfill 分配律}}

  \vspace{-1mm}
  \colorbox{blue}{\parbox{.882\textwidth}{$S=A + \mbox{(}B \cdot C\mbox{)} \, === \, \mbox{(}A + B\mbox{)} \cdot \mbox{(}A + C\mbox{)}=T$\hfill 分配律}}
\end{frame}
%------------------------------------------------ SLIDE -
\section{ド・モルガンの法則を理解}
\begin{frame}\frametitle{\secname}
  ド・モルガンの法則~1: ~$\mathsf{\overline{A \ \cdot \ B} =  \overline{A}  +   \overline{B}}$

  \fontsize{12pt}{15}\selectfont

  \vspace{3mm}
  『例』命題:

  \begin{tabular}{ll}
    $\mathsf{F =}$ \textcolor{blue}{単位修得}                 & $\mathsf{\overline{F} = }$ \textcolor{red}{単位非修得}\\
    $\mathsf{A =}$ \textcolor{blue}{試験の成績は６０点以上\ \ } & $\mathsf{\overline{A} = }$ \textcolor{red}{試験の成績は６０点以下}\\
    $\mathsf{B =}$ \textcolor{blue}{レポートを提出する}        & $\mathsf{\overline{B} = }$ \textcolor{red}{レポート未提出}\\
  \end{tabular}

  \vspace{4mm}

  $$\mathsf{\phantom{+}F = A \ \cdot \ B \ \ \ \ \ {{\Rightarrow}}\phantom{+}}$$

  \vspace{1mm}
  
  \textcolor{blue}{単位修得}~$=$ \textcolor{blue}{試験の成績は６０点以上}\hspace{2.03mm} かつ \hspace{2.03mm}\textcolor{blue}{レポートを提出する}

  \vspace{3mm}

  $$\mathsf{\phantom{+}\overline{F} = \overline{A \ \cdot \ B} =  \overline{A} + \overline{B}\ \ \ \ \ {{\Rightarrow}}\phantom{+}}$$

  \vspace{1mm}

  \textcolor{red}{単位非修得}~$=$ \textcolor{red}{試験の成績は６０点以下} または \textcolor{red}{レポート未提出}
\end{frame}
%------------------------------------------------ SLIDE -
\section{ド・モルガンの法則を理解}
\begin{frame}\frametitle{\secname}
  ド・モルガンの法則~2: ~$\mathsf{\overline{A + B} =  \overline{A} \ \cdot \ \overline{B}}$

  \fontsize{12pt}{15}\selectfont

  \vspace{3mm}
  『例』命題:

  \begin{tabular}{ll}
    $\mathsf{F =}$ \textcolor{blue}{単位修得}                 & $\mathsf{\overline{F} = }$ \textcolor{red}{単位非修得}\\
    $\mathsf{A =}$ \textcolor{blue}{試験の成績は６０点以上\ \ } & $\mathsf{\overline{A} = }$ \textcolor{red}{試験の成績は６０点以下}\\
    $\mathsf{B =}$ \textcolor{blue}{レポートを提出する}        & $\mathsf{\overline{B} = }$ \textcolor{red}{レポート未提出}\\
  \end{tabular}

  \vspace{4mm}

  $$\mathsf{F = A + B \ \ \ \ \ {{\Rightarrow}}}$$

  \vspace{1mm}
  \textcolor{blue}{単位修得}~$=$ \textcolor{blue}{試験の成績は６０点以上} または \textcolor{blue}{レポートを提出する}


  \vspace{3mm}
  
  $$\mathsf{\overline{F} = \overline{A + B} =  \overline{A} \ \cdot \ \overline{B}\ \ \ \ \ {{\Rightarrow}}}$$

  \vspace{1mm}
  
  \textcolor{red}{単位非修得}~$=$ \textcolor{red}{試験の成績は６０点以下}\hspace{2.03mm} かつ \hspace{2.03mm}\textcolor{red}{レポート未提出}
\end{frame}
%------------------------------------------------ SLIDE -
\section{ド・モルガンの法則の応用}
\begin{frame}\frametitle{\secname}

  \begin{itemize}
  \item $\mathsf{\overline{A \ \cdot \ B} = \overline{A} + \overline{B}}$

    \vspace{-6mm}
    \hfill\includegraphics[scale=1.3]{figs/nand_not_or.pdf}

    \vspace{9mm}
  \item $\mathsf{\overline{A + B} = \overline{A} \ \cdot \ \overline{B}}$

    \vspace{-6mm}
    \hfill\includegraphics[scale=1.3]{figs/nor_not_and.pdf}

    \vspace{9mm}
  \item $\mathsf{A \ \cdot \ B = \overline{\overline{A} + \overline{B}}}$

    \vspace{-6mm}
    \hfill\includegraphics[scale=1.3]{figs/and_not_nor.pdf}

    \vspace{9mm}
  \item $\mathsf{A + B = \overline{\overline{A} \ \cdot \ \overline{B}}}$

    \vspace{-6mm}
    \hfill\includegraphics[scale=1.3]{figs/or_not_nand.pdf}

  \end{itemize}

\end{frame}
%------------------------------------------------ SLIDE -
\section{ド・モルガンの法則の証明}
\begin{frame}\frametitle{\secname}
  \vspace{-5mm}
  \textcolor{red}{$$\mathsf{\overline{A \ \cdot \ B} = \overline{A} + \overline{B}}$$}

  \vspace{-5mm}
  \renewcommand{\arraystretch}{1.1}
  \setlength{\tabcolsep}{14.4pt}
  \begin{tabular}{cc|cc|ccc}\hline
    \multicolumn{2}{c|}{入力} & \multicolumn{2}{c|}{左辺} & \multicolumn{3}{c}{右辺}\\\hline
    \rule{0pt}{.85\normalbaselineskip}$\mathsf{A}$ & $\mathsf{B}$ & $\mathsf{A \cdot B}$ & \textcolor{red}{$\mathsf{\overline{A \cdot B}}$} &
    $\mathsf{\overline{A}}$ & $\mathsf{\overline{B}}$  & \textcolor{red}{$\mathsf{\overline{A}{\hspace{-1.08mm}}+{\hspace{-1.08mm}}\overline{B}}$}\\\hline\hline
    0 & 0 & 0 & \textcolor{red}{1} & 1 & 1 & \textcolor{red}{1}\\\hline
    0 & 1 & 0 & \textcolor{red}{1} & 1 & 0 & \textcolor{red}{1}\\\hline
    1 & 0 & 0 & \textcolor{red}{1} & 0 & 1 & \textcolor{red}{1}\\\hline
    1 & 1 & 1 & \textcolor{red}{0} & 0 & 0 & \textcolor{red}{0}\\\hline
    & \multicolumn{1}{c}{}  & $\uparrow$ & \multicolumn{1}{c}{$\uparrow$}  &&& $\uparrow$
  \end{tabular}

  \vspace{-1mm}
  \fontsize{8pt}{10}\selectfont
  \setlength{\tabcolsep}{3pt}
  \begin{tabular}{p{.6in}p{1.1in}p{1.6in}p{2in}}
    &
    A AND B なので、\newline
    A と B が 1 の時\newline
    に 1 を出力する
    &
    A AND B の否定なので、\newline
    左の A AND B の結果の\newline
    逆を出力する
    &
    左で求めた A の否定、\newline
    B の否定を用いて、\newline
    $\mathsf{\overline{A}}$ {\hspace{1.11mm}}OR{\hspace{1.11mm}} $\mathsf{\overline{B}}$ を出力する
  \end{tabular}

  \vspace{3mm}
  \textcolor{red}{\resizebox{1.015\textwidth}{!}{入力の全てのパターンに対する左辺と右辺は出力が等しいであるため、ド・モルガンの法則は成り立つ。}}

\end{frame}
%------------------------------------------------ SLIDE -
\section{ド・モルガンの法則の証明}
\begin{frame}\frametitle{\secname}
  \vspace{-5mm}
  \textcolor{red}{$$\mathsf{\overline{A + B} = \overline{A} \ \cdot \ \overline{B}}$$}

  \vspace{-5mm}
  \renewcommand{\arraystretch}{1.1}
  \setlength{\tabcolsep}{14.4pt}
  \begin{tabular}{cc|cc|ccc}\hline
    \multicolumn{2}{c|}{入力} & \multicolumn{2}{c|}{左辺} & \multicolumn{3}{c}{右辺}\\\hline
    \rule{0pt}{.85\normalbaselineskip}$\mathsf{A}$ & $\mathsf{B}$ & $\mathsf{A{\hspace{-1.08mm}}+{\hspace{-1.08mm}}B}$ & \textcolor{red}{$\mathsf{\overline{A{\hspace{-1.08mm}}+{\hspace{-1.08mm}}B}}$} &
    $\mathsf{\overline{A}}$     & $\mathsf{\overline{B}}$ & \textcolor{red}{$\mathsf{\overline{A} \cdot \overline{B}}$}\\\hline\hline
    0 & 0 & 0 & \textcolor{red}{1} & 1 & 1 & \textcolor{red}{1}\\\hline
    0 & 1 & 1 & \textcolor{red}{0} & 1 & 0 & \textcolor{red}{0}\\\hline
    1 & 0 & 1 & \textcolor{red}{0} & 0 & 1 & \textcolor{red}{0}\\\hline
    1 & 1 & 1 & \textcolor{red}{0} & 0 & 0 & \textcolor{red}{0}\\\hline
    & \multicolumn{1}{c}{}  & $\uparrow$ & \multicolumn{1}{c}{$\uparrow$}  &&& $\uparrow$
  \end{tabular}

  \vspace{-1mm}
  \fontsize{8pt}{10}\selectfont
  \setlength{\tabcolsep}{3pt}
  \begin{tabular}{p{.6in}p{1.1in}p{1.6in}p{2in}}
    &
    A {\hspace{1.11mm}}OR{\hspace{1.11mm}} B なので、\newline
    A, B いずれかが 1 の時\newline
    に 1 を出力する
    &
    A {\hspace{1.11mm}}OR{\hspace{1.11mm}} B の否定なので、\newline
    左の A {\hspace{1.11mm}}OR{\hspace{1.11mm}} B の結果の\newline
    逆を出力する
    &
    左で求めた A の否定、\newline
    B の否定を用いて、\newline
    $\mathsf{\overline{A}}$ AND $\mathsf{\overline{B}}$ を出力する
  \end{tabular}

  \vspace{3mm}
  \textcolor{red}{\resizebox{1.015\textwidth}{!}{入力の全てのパターンに対する左辺と右辺は出力が等しいであるため、ド・モルガンの法則は成り立つ。}}

\end{frame}
%------------------------------------------------ SLIDE -
\section{ド・モルガンの法則 (Verilog HDL)}
\begin{frame}[fragile]\frametitle{\secname}
  $\overline{A \ \cdot \ B} = \overline{A} + \overline{B}$ \cdotfill{Equ. 1}

  $\overline{A + B} = \overline{A} \ \cdot \ \overline{B}$ \cdotfill{Equ. 2}

  \vspace{4.21mm}
\fontsize{11pt}{11.5}\selectfont
\begin{code}
`timescale 1ns/1ns

module de_morgan_law (A, B, P, Q, S, T);
    input  A, B;
    output P, Q, S, T;

    assign P = ~(A & B); // Equ. 1's left  side
    assign Q =  ~A | ~B; // Equ. 1's right side

    assign S = ~(A | B); // Equ. 2's left  side
    assign T =  ~A & ~B; // Equ. 2's right side

endmodule
\end{code}

\vspace{-8mm}
\hfill
\href{https://yamin.cis.k.hosei.ac.jp/lectures/logic/de_morgan_law.v}{\color{blue}\underline{de\_morgan\_law.v}}~~~

\end{frame}
%------------------------------------------------ SLIDE -
\section{ド・モルガンの法則 (テストベンチ)}
\begin{frame}[fragile]\frametitle{\secname}
\fontsize{11pt}{11.5}\selectfont
\begin{code}
`timescale 1ns/1ns

module de_morgan_law_tb;
    reg  A, B;
    wire P, Q, S, T;
    de_morgan_law i0 (A, B, P, Q, S, T);
    initial begin
        #0 A = 0; B = 0;
        #4 $finish;
    end
    always #1 A = ~A;
    always #2 B = ~B;
    initial begin
        $dumpfile ("de_morgan_law.vcd");
        $dumpvars;
    end
endmodule
\end{code}

\vspace{-8mm}
\hfill
\href{https://yamin.cis.k.hosei.ac.jp/lectures/logic/de_morgan_law_tb.v}{\color{blue}\underline{de\_morgan\_law\_tb.v}}~~~

\end{frame}
%------------------------------------------------ SLIDE -
\section{ド・モルガンの法則 (波形)}
\begin{frame}[fragile]\frametitle{\secname}
\vspace{-5mm}
\begin{verbatim}
% iverilog -Wall -o de_morgan_law \
  de_morgan_law_tb.v de_morgan_law.v
% ./de_morgan_law
% gtkwave de_morgan_law.vcd
\end{verbatim}

\vspace{-1mm}
  \includegraphics[width=\textwidth]{figs/de_morgan_law_vcd_crop.png}

  \fontsize{13pt}{13}\selectfont
  \white
  %\vspace{-4mm}
  \colorbox{blue}{\parbox{.982\textwidth}{$P=\overline{A \ \cdot \ B} === \overline{A} + \overline{B}=Q$\hfill ド・モルガンの法則}}

  \vspace{-1mm}
  \colorbox{blue}{\parbox{.982\textwidth}{$S=\overline{A + B} \, === \, \overline{A} \ \cdot \ \overline{B}=T$\hfill ド・モルガンの法則}}

\end{frame}
%------------------------------------------------ SLIDE -
\section{ド・モルガンの法則の例}
\begin{frame}\frametitle{\secname}
  \renewcommand{\arraystretch}{1.6}
  \setlength{\tabcolsep}{5pt}
  \begin{tabular}{rclr}
    $\mathsf{F}$            & $=$ & $\mathsf{X + Y  \ \cdot \  \overline{Z}}$\\[10pt]
    $\mathsf{\overline{F}}$ & $=$ & $\mathsf{\overline{X + Y  \ \cdot \  \overline{Z}}}$ & \textcolor{blue}{\footnotesize  ド・モルガンの法則 $\mathsf{\overline{A+B}=\ ?}$} \onslide<2->\\
    
    & $=$ & $\mathsf{\overline{X}  \ \cdot \  \mbox{(}\overline{Y  \ \cdot \  \overline{Z}}\mbox{)}}$ & \textcolor{blue}{\footnotesize   $\Leftarrow$ ド・モルガンの法則 $\mathsf{\overline{A+B}=\overline{A}  \ \cdot \  \overline{B}}$}\\
    \par\pause
    &&& \textcolor{blue}{\footnotesize  ド・モルガンの法則 $\mathsf{\overline{A  \ \cdot \  B}=}$\ ?} \\
    \par\pause
    & $=$ & $\mathsf{\overline{X}  \ \cdot \  \mbox{(}\overline{Y} + \overline{\overline{Z}}\mbox{)}}$ & \textcolor{blue}{\footnotesize   $\Leftarrow$ ド・モルガンの法則 $\mathsf{\overline{A  \ \cdot \  B}=\overline{A}+\overline{B}}$}\\
    \par\pause
    & $=$ & $\mathsf{\overline{X}  \ \cdot \  \mbox{(}\overline{Y} + Z\mbox{)}}$\\
    \par\pause
    & $=$ & $\mathsf{\overline{X}  \ \cdot \  \overline{Y} + \overline{X}  \ \cdot \  Z}$\hspace*{-10mm}\\
  \end{tabular}
\end{frame}
%------------------------------------------------ SLIDE -
\section{ド・モルガンの法則の拡張}
\begin{frame}\frametitle{\secname}
  \begin{itemize}
    \setlength{\itemsep}{0.2em}

  \item $\mathsf{\overline{A \ \cdot \ B} =  \overline{A}  +   \overline{B}}$ \cdotfill{ド・モルガンの法則}
  \item $\mathsf{\overline{A + B} =  \overline{A} \ \cdot \ \overline{B}}$ \cdotfill{ド・モルガンの法則}

  \vspace{1mm}
  \item $\mathsf{\overline{A \ \cdot \ B \ \cdot \ C} =  \overline{A}  +   \overline{B}  +   \overline{C}}$
  \item $\mathsf{\overline{A + B + C} =  \overline{A} \ \cdot \ \overline{B} \ \cdot \ \overline{C}}$

  \vspace{1mm}
  \item $\mathsf{\overline{A \ \cdot \ B \ \cdot \ C \ \cdot \ D} =  \overline{A}  +   \overline{B}  +   \overline{C}  +   \overline{D}}$
  \item $\mathsf{\overline{A + B + C + D} =  \overline{A} \ \cdot \ \overline{B} \ \cdot \ \overline{C} \ \cdot \ \overline{D}}$

  \vspace{1mm}
  \item $\mathsf{\overline{A \ \cdot \ B \ \cdot \ C \ \cdot \ D \ \cdot \ E} =  \overline{A}  +   \overline{B}  +   \overline{C}  +   \overline{D}  +   \overline{E}}$
  \item $\mathsf{\overline{A + B + C + D + E} =  \overline{A} \ \cdot \ \overline{B} \ \cdot \ \overline{C} \ \cdot \ \overline{D} \ \cdot \ \overline{E}}$

  \vspace{1mm}
  \item $\cdots$ $\cdots$ 
  \item $\cdots$ $\cdots$ 

  \end{itemize}
\end{frame}
%------------------------------------------------ SLIDE -
\section{ブール代数の定理を用いた証明}
\begin{frame}\frametitle{\secname}
\fontsize{13pt}{14}\selectfont
  \renewcommand{\arraystretch}{1.82}
  \setlength{\tabcolsep}{5pt}
  \begin{tabular}{rlr}
    証明 & $\mathsf{\mbox{(}\mbox{(}A \cdot B\mbox{)} \cdot \overline{C}\mbox{)} + \mbox{(}A \cdot \mbox{(}\overline{B}+C\mbox{)}\mbox{)} = A}$ & \\

    \multicolumn{3}{r}{\pause \textcolor{blue}{\footnotesize 右辺が\,A\,なので、左辺を\,A\,でくくる}}\\
    
    &\pause $\mathsf{A \cdot \mbox{(}\mbox{(}B \cdot \overline{C}\mbox{)} + \mbox{(}\overline{B}+C\mbox{)}\mbox{)} = A}$ & \\

    \multicolumn{3}{r}{\pause \textcolor{blue}{\footnotesize $\mathsf{\mbox{(}B \cdot \overline{C}\mbox{)} + \mbox{(}\overline{B}+C\mbox{)}=1}$ を証明すればよい、とあたりを付ける}}\\

    &\pause $\mathsf{\mbox{(}B \cdot \overline{C}\mbox{)} + \mbox{(}\overline{B}+C\mbox{)}}$ & \\

    \pause $=$ & $\mathsf{\mbox{(}B \cdot \overline{C}\mbox{)} + \mbox{(}\overline{\overline{\overline{B}} \cdot \overline{C}}\mbox{)}}$ & 
    \textcolor{blue}{\footnotesize \hspace{-32mm}$\Leftarrow$ ド・モルガンの法則より右の項を変形}\\

    \pause $=$ & $\mathsf{\mbox{(}B \cdot \overline{C}\mbox{)} + \mbox{(}\overline{B \cdot \overline{C}}\mbox{)}}$ &

    \textcolor{blue}{\footnotesize \hspace{-28mm}\pause $\Leftarrow$ $\mathsf{\mbox{(}B \cdot \overline{C}\mbox{)}=D}$ とするならば、$\mathsf{\mbox{(}D+\overline{D}\mbox{)}}$ となる}\\

    $=$ & 1\\
  \end{tabular}
\end{frame}
%------------------------------------------------ SLIDE -
\section{ブール代数の定理を用いた証明}
\begin{frame}\frametitle{\secname}
\fontsize{13pt}{14}\selectfont
  \renewcommand{\arraystretch}{1.82}
  \setlength{\tabcolsep}{5pt}
  \begin{tabular}{rlr}
    証明 & $\mathsf{X \cdot \overline{Z} + Y \cdot Z + X \cdot Y  = X \cdot \overline{Z} + Y \cdot Z}$ & \\

    \multicolumn{3}{r}{\pause \textcolor{blue}{\footnotesize 左辺の $X \cdot Y$ をいじって消す方針}}\\
    \pause 左辺 & $\mathsf{X \cdot \overline{Z} + Y \cdot Z + X \cdot Y}$ & \\
    \pause $=$ & $\mathsf{X \cdot \overline{Z} + Y \cdot Z + X \cdot Y \cdot \mbox{(}\overline{Z} + Z\mbox{)}}$ & \textcolor{blue}{\footnotesize $\mathsf{\Leftarrow Z + \overline{Z}=1}$}\\
    \pause $=$ & $\mathsf{X \cdot \overline{Z} + Y \cdot Z + \textcolor{blue}{X \cdot Y \cdot \overline{Z}} + \textcolor{blue}{X \cdot Y \cdot Z}}$ & \textcolor{blue}{\footnotesize $\Leftarrow$ 分配律}\\
    \pause $=$ & $\mathsf{X \cdot \overline{Z} + \textcolor{blue}{X \cdot Y \cdot \overline{Z}} + Y \cdot Z + \textcolor{blue}{X \cdot Y \cdot Z}}$ & \textcolor{blue}{\footnotesize $\Leftarrow$ 交換律}\\
    \pause $=$ & $\mathsf{X \cdot \overline{Z} \cdot \mbox{(}1+Y\mbox{)}+ Y \cdot Z \cdot \mbox{(}1+X\mbox{)}}$ & \textcolor{blue}{\footnotesize $\Leftarrow$ 分配律} \\
    \pause $=$ & $\mathsf{X \cdot \overline{Z} + Y \cdot Z}$ \ \ 右辺 & \textcolor{blue}{\footnotesize {\hspace{-3mm}}$\Leftarrow$ $\mathsf{1+Y=1}$; \ $\mathsf{1+X=1}$}\\
  \end{tabular}
\end{frame}
%------------------------------------------------ SLIDE -
%\section{ブール代数の定理を用いた証明}
%\begin{frame}\frametitle{\secname}
%\renewcommand{\arraystretch}{1.5}
%\setlength{\tabcolsep}{5pt}
%\begin{tabular}{rlr}
%証明 & $\mathsf{A + \overline{A} \cdot B=A + B}$ & \\\pause
%&&\\[-11pt]
%左辺 & $\mathsf{A + \overline{A} \cdot B}$ & \textcolor{blue}{\footnotesize \pause $\mathsf{A=A \cdot \mbox{(}A + B\mbox{)}$\\
%\pause $=$ & $\mathsf{A \cdot \mbox{(}A + B\mbox{)} + \overline{A} \cdot B}$ &\textcolor{blue}{\footnotesize 吸収律\\
%\pause $=$ & $\mathsf{A \cdot A + A \cdot B + \overline{A} \cdot B}$ &\textcolor{blue}{\footnotesize \hspace{45.54mm}分配律\\
%\pause $=$ & $\mathsf{A \cdot A + \mbox{(}A + \overline{A}\mbox{)} \cdot B}$ &\textcolor{blue}{\footnotesize 分配律\\
%\pause $=$ & $\mathsf{A \cdot A + 1 \cdot B}$ &\textcolor{blue}{\footnotesize 補元律\\
%\pause $=$ & $\mathsf{A \cdot A + B}$ &\textcolor{blue}{\footnotesize 同一律\\
%\pause $=$ & $\mathsf{A + B}$ &\textcolor{blue}{\footnotesize 冪等律\\
%\end{tabular}
%\end{frame}
%------------------------------------------------ SLIDE -
\section{ブール代数の定理を用いた証明}
\begin{frame}\frametitle{\secname}
\fontsize{13pt}{14}\selectfont
  \renewcommand{\arraystretch}{1.82}
  \setlength{\tabcolsep}{5pt}
  \begin{tabular}{rlr}
    証明 & $\mathsf{A + \overline{A} \cdot B=A + B}$ & \\
    \pause 左辺 & $\mathsf{A + \overline{A} \cdot B= A \cdot 1                  + \overline{A} \cdot B}$ & \textcolor{blue}{\footnotesize 同一律}\\
    \pause $=$ & $\mathsf{A \cdot \mbox{(}\overline{B} + B\mbox{)} + \overline{A} \cdot B}$ & \textcolor{blue}{\footnotesize 補元律}\\
    \pause $=$ & $\mathsf{A \cdot \overline{B} + A \cdot B + \overline{A} \cdot B}$ & \textcolor{blue}{\footnotesize 分配律}\\
    \pause $=$ & $\mathsf{A \cdot \overline{B} + A \cdot B  + A \cdot B + \overline{A} \cdot B}$ & \hspace{29.00mm}\textcolor{blue}{\footnotesize 冪等律}\\
    \pause $=$ & $\mathsf{A \cdot \mbox{(}\overline{B} + B\mbox{)} + \mbox{(}A + \overline{A}\mbox{)} \cdot B}$ & \textcolor{blue}{\footnotesize 分配律}\\
    \pause $=$ & $\mathsf{A \cdot 1 + 1 \cdot B}$ & \textcolor{blue}{\footnotesize 補元律}\\
    \pause $=$ & $\mathsf{A + B}$ \ \ 右辺& \textcolor{blue}{\footnotesize 同一律}\\
  \end{tabular}
\end{frame}
%------------------------------------------------ SLIDE -
\section{完全系}
\begin{frame}\frametitle{\secname}
\fontsize{13pt}{15}\selectfont
  \begin{itemize}
    \setlength{\itemsep}{4mm}
  \item {\textcolor{magenta}{AND と OR、NOT}} ゲートがあれば、どんな論理回路でも設計できる。
  \item このようにどんな論理回路でも設計できるゲートの組み合わせを{\textcolor{magenta}{完全系}}と言う。
  \item 面白いことに、これら３つのゲートではなく、たった１つのゲートで完全系ができる。

  \item \scalebox{.92}{{\textcolor{magenta}{NAND}}\,ゲートがあれば、\hspace{-.5mm}どんな論理回路でも設計できる。}\hspace{-.5mm}%（否定論理積）
  \item \scalebox{.92}{{\textcolor{magenta}{NOR}}\phantom{A}\,ゲートがあれば、\hspace{-.5mm}どんな論理回路でも設計できる。}\hspace{-.5mm}%（否定論理和）

  \item このとき、\hspace{-.5mm}NAND\hspace{-.5mm}（もしくは\,NOR）\hspace{-.5mm}は{\textcolor{magenta}{完全系}}も言う。\hspace{-.5mm}

  \end{itemize}
\end{frame}
%------------------------------------------------ SLIDE -
\section{NANDゲートのみで回路を構成する}
\begin{frame}\frametitle{\secname}
  \scalebox{1}{任意の組合せ回路は\,{\textcolor{magenta}{NAND}}\,ゲートを用いて実現できる。}

  \vspace{5mm}
  \textcolor{magenta}{1. NOT: $\mathsf{\overline{A}=\overline{A \cdot A}}$}
  
  \vspace{2mm}
  \includegraphics[scale=1.25]{figs/nand-only-not.pdf}

  \vspace{5mm}
  \textcolor{blue}{2. AND: $\mathsf{A \cdot B=\overline{\overline{A \cdot B}}}$}

  \vspace{3mm}
  \includegraphics[scale=1.25]{figs/nand-only-and.pdf}

  \vspace{5mm}
  \textcolor{red}{3. OR: $\mathsf{A + B=\overline{\overline{A} \cdot \overline{B}}}$}

  \vspace{0mm}
  \includegraphics[scale=1.25]{figs/nand-only-or.pdf}
\end{frame}
%------------------------------------------------ SLIDE -
\section{NANDゲートのみで回路を構成する}
\begin{frame}\frametitle{\secname}
  \scalebox{1}{任意の組合せ回路は\,{\textcolor{magenta}{NAND}}\,ゲートを用いて実現できる。}

  \vspace{6mm}
  \includegraphics[scale=.88]{figs/nand_only.pdf}
\end{frame}
%------------------------------------------------ SLIDE -
\section{NANDのみで回路 (Verilog HDL)}
\begin{frame}[fragile]\frametitle{\secname}
\fontsize{11pt}{11.5}\selectfont
\begin{code}
`timescale 1ns/1ns
module nand_only (A, B, C, F1, F2);
    input  A, B, C;
    output F1, F2;

    wire   W1, W2, W3, W4, W5, W6;

    assign F1 = ~A & ~B | B & C | ~B & ~C;

    nand i1 (W1,  A,  A);
    nand i2 (W2,  B,  B);
    nand i3 (W3,  C,  C);
    nand i4 (W4, W1, W2);
    nand i5 (W5,  B,  C);
    nand i6 (W6, W2, W3);
    nand i7 (F2, W4, W5, W6);
endmodule
\end{code}

\vspace{-8mm}
\hfill
\href{https://yamin.cis.k.hosei.ac.jp/lectures/logic/nand_only.v}{\color{blue}\underline{nand\_only.v}}~~~

  \vspace{-60mm}
  \hspace*{66mm}
  \includegraphics[scale=.69]{figs/nand_only2.pdf}
\end{frame}
%------------------------------------------------ SLIDE -
\section{NANDのみで回路 (テストベンチ)}
\begin{frame}[fragile]\frametitle{\secname}
\fontsize{11pt}{11.5}\selectfont
\begin{code}
`timescale 1ns/1ns
module nand_only_tb;
    reg  A, B, C;
    wire F1, F2;
    nand_only i0 (A, B, C, F1, F2);
    initial begin
        #0 A = 0; B = 0; C = 0;
        #8 $finish;
    end
    always #1 A = ~A;
    always #2 B = ~B;
    always #4 C = ~C;
    initial begin
        $dumpfile ("nand_only.vcd");
        $dumpvars;
    end
endmodule
\end{code}

\vspace{-8mm}
\hfill
\href{https://yamin.cis.k.hosei.ac.jp/lectures/logic/nand_only_tb.v}{\color{blue}\underline{nand\_only\_tb.v}}~~~

\end{frame}
%------------------------------------------------ SLIDE -
\section{NANDのみで回路 (波形)}
\begin{frame}[fragile]\frametitle{\secname}
\vspace{-5mm}
\begin{verbatim}
% iverilog -Wall -o nand_only \
  nand_only_tb.v nand_only.v
% ./nand_only
% gtkwave nand_only.vcd
\end{verbatim}

\vspace{-1mm}
\includegraphics[width=\textwidth]{figs/nand_only_vcd_crop.png}

\magenta
%\vspace{-2mm}
$F1 === F2$

\end{frame}
%------------------------------------------------ SLIDE -
\section{NOR \hspace{5.678mm}ゲートのみで回路を構成する}
\begin{frame}\frametitle{\secname}
  \scalebox{1}{任意の組合せ回路は{\hspace{2.805mm}}{\textcolor{magenta}{NOR}}{\hspace{2.805mm}}ゲートを用いて実現できる。}

  \vspace{5mm}
  \textcolor{magenta}{1. NOT: $\mathsf{\overline{A}=\overline{A + A}}$}
  
  \vspace{2mm}
  \includegraphics[scale=1.25]{figs/nor-only-not.pdf}

  \vspace{5mm}
  \textcolor{blue}{2. OR: $\mathsf{A + B=\overline{\overline{A + B}}}$}

  \vspace{3mm}
  \includegraphics[scale=1.25]{figs/nor-only-or.pdf}

  \vspace{5mm}
  \textcolor{red}{3. AND: $\mathsf{A \cdot B=\overline{\overline{A} + \overline{B}}}$}

  \vspace{0mm}
  \includegraphics[scale=1.25]{figs/nor-only-and.pdf}
\end{frame}
%------------------------------------------------ SLIDE -
\section{NOR \hspace{5.678mm}ゲートのみで回路を構成する}
\begin{frame}\frametitle{\secname}
  \scalebox{1}{任意の組合せ回路は{\hspace{2.805mm}}{\textcolor{magenta}{NOR}}{\hspace{2.805mm}}ゲートを用いて実現できる。}

  \vspace{6mm}
  \includegraphics[scale=.88]{figs/nor_only.pdf}
\end{frame}
%------------------------------------------------ SLIDE -
\section{NORのみで回路 (Verilog HDL)}
\begin{frame}[fragile]\frametitle{\secname}
\fontsize{11pt}{11.5}\selectfont
\begin{code}
`timescale 1ns/1ns
module nor_only (A, B, C, F1, F2);
    input  A, B, C;
    output F1, F2;

    wire   W1, W2, W3, W4, W5, W6;

    assign F1 = ~A & ~B | B & C | ~B & ~C;

    nor i1 (W1,  B,  B);
    nor i2 (W2,  C,  C);
    nor i3 (W3,  A,  B);
    nor i4 (W4, W1, W2);
    nor i5 (W5,  B,  C);
    nor i6 (W6, W3, W4, W5);
    nor i7 (F2, W6, W6);
endmodule
\end{code}

\vspace{-8mm}
\hfill
\href{https://yamin.cis.k.hosei.ac.jp/lectures/logic/nor_only.v}{\color{blue}\underline{nor\_only.v}}~~~

  \vspace{-60mm}
  \hspace*{66mm}
  \includegraphics[scale=.69]{figs/nor_only2.pdf}
\end{frame}
%------------------------------------------------ SLIDE -
\section{NORのみで回路 (テストベンチ)}
\begin{frame}[fragile]\frametitle{\secname}
\fontsize{11pt}{11.5}\selectfont
\begin{code}
`timescale 1ns/1ns
module nor_only_tb;
    reg  A, B, C;
    wire F1, F2;
    nor_only i0 (A, B, C, F1, F2);
    initial begin
        #0 A = 0; B = 0; C = 0;
        #8 $finish;
    end
    always #1 A = ~A;
    always #2 B = ~B;
    always #4 C = ~C;
    initial begin
        $dumpfile ("nor_only.vcd");
        $dumpvars;
    end
endmodule
\end{code}

\vspace{-8mm}
\hfill
\href{https://yamin.cis.k.hosei.ac.jp/lectures/logic/nor_only_tb.v}{\color{blue}\underline{nor\_only\_tb.v}}~~~

\end{frame}
%------------------------------------------------ SLIDE -
\section{NORのみで回路 (波形)}
\begin{frame}[fragile]\frametitle{\secname}
\vspace{-5mm}
\begin{verbatim}
% iverilog -Wall -o nor_only \
  nor_only_tb.v nor_only.v
% ./nor_only
% gtkwave nor_only.vcd
\end{verbatim}

\vspace{-1mm}
\includegraphics[width=\textwidth]{figs/nor_only_vcd_crop.png}

\magenta
%\vspace{-2mm}
$F1 === F2$

\end{frame}
%------------------------------------------------ SLIDE -
\section{ブール代数と完全系}
\begin{frame}\frametitle{\secname}
  \hspace*{-4mm}
  \textcolor{blue}{まとめ}

  \begin{itemize}
    \setlength{\itemsep}{1.1mm}
  \item\textcolor{blue}{ブール代数の定理}
  \item\textcolor{blue}{ド・モルガンの法則の理解と証明}
  \item\textcolor{blue}{ブール代数の定理を用いた証明}
  \item\textcolor{blue}{完全系}
    \begin{itemize}
    \item\textcolor{blue}{AND と OR、NOT ゲート}
    \item\textcolor{blue}{NAND ゲートのみ}
    \item\textcolor{blue}{NOR ゲートのみ}
    \end{itemize}
  \item\textcolor{blue}{NAND ゲートのみで回路を構成}
  \item\textcolor{blue}{NOR ゲートのみで回路を構成}
  \end{itemize}

\end{frame}
%------------------------------------------------ SLIDE -
\section{課題 III (100 点)}
\begin{frame}\frametitle{\secname}
  問題１： 次式をブール代数の定理で証明して下さい。

  \vspace{3mm}
  (1) $\mathsf{\mbox{(}A+B\mbox{)} \cdot \mbox{(}A+\overline{B}\mbox{)}=A}\phantom{\overline{\overline{A}}}$

  \vspace{3mm}
  (2) $\mathsf{A\cdot B + \overline{A}\cdot B\cdot C=A\cdot B + B\cdot C}\phantom{\overline{\overline{A}}}$

\end{frame}
%------------------------------------------------ SLIDE -
\section{課題 III (100 点)}
\begin{frame}\frametitle{\secname}
  問題２： 次式を真理値表で証明して下さい。

  \vspace{3mm}
  (1) $\mathsf{A + B=\overline{\overline{A} \cdot \overline{B}}}$ \cdotfill{Equ. 1}

  \vspace{3mm}
  (2) $\mathsf{A \cdot B=\overline{\overline{A} + \overline{B}}}$ \cdotfill{Equ. 2}

  \vspace{3mm}
  さらに、Verilog HDL コードを書いて、シミュレーションして下さい (P18 - P22を参照)。

  \vspace{3mm}
  モジュール名：\href{https://yamin.cis.k.hosei.ac.jp/lectures/logic/demorganlaw.v}{\textcolor{blue}{\underline{demorganlaw}}}

  テストベンチ：\href{https://yamin.cis.k.hosei.ac.jp/lectures/logic/demorganlaw_tb.v}{\textcolor{blue}{\underline{demorganlaw\_tb.v}}}

\end{frame}
%------------------------------------------------ SLIDE -
\input{mybackground.tex}
%------------------------------------------------ SLIDE -
\section{発展：自由練習}
\begin{frame}\frametitle{\secname}

  分かりやすいために、NAND ゲートと NOR ゲートの電球を点灯させる回路を描画して下さい。

  \vspace{6mm}
  \includegraphics[width=\textwidth]{figs/nor-nand-switches.pdf}

  \vspace{6mm}
  真理値表で確認して下さい。ヒント:

  \vspace{3mm}
  
  (1) NAND: \ $\mathsf{\overline{A \cdot B} = \overline{A} + \overline{B}}$ \hfill{$\phantom{\overline{A} \cdot \overline{B}}$ド・モルガンの法則}

  \vspace{3mm}
  (2) NOR:  \ $\mathsf{\overline{A + B} = \overline{A} \cdot \overline{B}}$ \hfill{$\phantom{\overline{\overline{A} + \overline{B}}}$ド・モルガンの法則}

\end{frame}
%------------------------------------------------ SLIDE -
\end{document}
%------------------------------------------------ SLIDE -
