cheat3.tex

\documentclass[a4paper,10pt]{article}
\usepackage{mypreamble}

%% Page setup
\geometry{
    margin=2cm,
    includehead,
    includefoot,
    headsep=8pt,
    footskip=16pt,
}
\pagestyle{fancy}
\MakeSingleHeader% {<l>}{<r>}
    {\TextCheatsheetEng: Boolean Algebra}%
    {\TextDiscreteMathEng, \IconFall~Fall 2024}
\fancyfoot{}
\fancyfoot[L]{\tiny Build time: \DTMnow}
\fancyfoot[R]{\tiny Source code can be found at \url{https://github.com/Lipen/discrete-math-course}}
% \fancyfoot[C]{\thepage\ of \zpageref{LastPage}}

%% Add custom setup below

% \titlespacing{\type}{left}{above}{below}[right]
\titlespacing{\section}{0pt}{*1}{*0.5}
\titlespacing{\subsection}{0pt}{*1}{*0.5}

\setlength{\tabcolsep}{0pt}

%% Autoscale missing font sizes
\usepackage{anyfontsize}

%% Theorem environmnet
\declaretheorem{theorem}

%% Post's Theorem
\declaretheoremstyle[
    name={Post's Functional Completeness Theorem\protect\Href{https://doi.org/10.1305/ndjfl/1093635508}},
    numbered=no,
    spaceabove=6pt,
    spacebelow=6pt,
]{poststyle}
\declaretheorem[style=poststyle]{posttheorem}


\begin{document}

\selectlanguage{english}

\setcounter{section}{2}% +1 = actual
\section{Boolean Algebra Cheatsheet}

\subsection{Definitions}

\begin{terms}
    \item \raggedright \textbf{Boolean function}\Href{https://en.wikipedia.org/wiki/Boolean_function} is a function of the form $f: \Bool^{n} \to \Bool$, where $n \geq 0$ is the \emph{arity} of the function and $\Bool =\nobreak \Set{0, 1} =\nobreak \Set{\bot, \top} =\nobreak \Set{\texttt{F}, \texttt{T}}$ is a Boolean domain.

    \item There are multiple ways to represent a Boolean function (all examples represent the same function):

    \begin{enumerate}[left=6pt .. 18pt]
        \item Truth table, \eg $f = (1010)$, where LSB corresponds to $\vvmathbb{1}$, MSB to $\vvmathbb{0}$.
        \hfill\href{https://en.wikipedia.org/wiki/Bit_numbering}{Least/Most Significant Bit}

        \item Analytically (as a sentence of propositional logic), \eg $f(A,B) = \neg B$.
        \hfill\href{https://en.wikipedia.org/wiki/Propositional_logic}{Propositional logic}

        \item Sum of minterms, \eg $f = \sum m(0,2) = m_0 + m_2$.
        \hfill\href{http://www.cs.ucr.edu/~ehwang/courses/cs120a/minterms.pdf}{Minterms}

        \item Product of maxterms, \eg $f = \prod M(1,3) = M_1 \cdot M_3$.
        \hfill\href{http://www.cs.ucr.edu/~ehwang/courses/cs120a/minterms.pdf#page=2}{Maxterms}

        \item Boolean function number\Href{https://mathworld.wolfram.com/BooleanFunction.html}, \eg $f^{(2)}_{10}$ is the 10-th 2-ary function.

        Note that Wolfram's \enquote{Boolean operator number} is a slightly different term, which uses the reversed truth table.
        10-th Boolean function $f^{(2)}_{10}$ with the truth table $(1010)$ can be obtained via the query \enquote{5th Boolean function of 2~variables} (note: not 10th!) in WolframAlpha\Href{https://bit.ly/3nFbad5}, since $\texttt{rev}(1010_2) = 0101_2 = 5_{10}$.
    \end{enumerate}

    % TODO: more Boolean algebra definitions
\end{terms}


\subsection{Normal Forms}

\begin{terms}
    \item \emph{Disjunctive} forms:
    \begin{terms}
        \item \textbf{Cube} is a conjunction of literals: $\mathcal{T} = \bigland\nolimits_{i} \mathcal{L}_i$.

        \item Formula is in \textbf{disjunctive normal form (DNF)}\Href{https://en.wikipedia.org/wiki/Disjunctive_normal_form} if it is a disjunction of terms: $\textrm{DNF} = \biglor\nolimits_{i} \mathcal{T}_i$.

        \item \textbf{Minterm} is conjunction of literals, where \emph{each} variable appears \emph{once}, \eg $m_6 = (A \land B \land \neg C)$.

        \item Formula is in \textbf{canonical DNF (CDNF)}\Href{https://en.wikipedia.org/wiki/Canonical_disjunctive_normal_form} if it is a disjunction of minterms: $\textrm{CDNF} = \biglor\nolimits_{i} m_i$.
    \end{terms}

    \item \emph{Conjunctive} forms:
    \begin{terms}
        \item \textbf{Clause}\Href{https://en.wikipedia.org/wiki/Clause_(logic)} is a disjunction of literals: $\mathcal{C} = \biglor\nolimits_{i} \mathcal{L}_i$

        \item Formula is in \textbf{conjunctive normal form (CNF)}\Href{https://en.wikipedia.org/wiki/Conjunctive_normal_form} if it is a conjunction of clauses: $\textrm{CNF} = \bigland\nolimits_{i} \mathcal{C}_i$.

        \item \textbf{Maxterm} is disjunction of literals, where \emph{each} variable appears \emph{once}, \eg $M_6 = (\neg A \lor \neg B \lor C)$.

        \item Formula is in \textbf{canonical CNF (CCNF)}\Href{https://en.wikipedia.org/wiki/Canonical_conjunctive_normal_form} if it is a conjunction of maxterms: $\textrm{CCNF} = \bigland\nolimits_{i} M_i$.
    \end{terms}

    \item Some other normal forms:
    \begin{terms}
        \item Formula is in \textbf{negation normal form (NNF)}\Href{https://en.wikipedia.org/wiki/Negation_normal_form} if the negation operator ($\neg$) is only applied to variables and the only other allowed Boolean operators are conjunction ($\land$) and disjunction ($\lor$).

        \item Formula $f$ is in \textbf{Blake canonical form (BCF)}\Href{https://en.wikipedia.org/wiki/Blake_canonical_form} if it is a disjunction of \emph{all} the \textit{prime implicants} of $f$.

        \item Formula is in \textbf{prenex normal form (PNF)}\Href{https://en.wikipedia.org/wiki/Prenex_normal_form} if it consists of \textit{prefix} \--- quantifiers and bound variables, and \textit{matrix} \--- quatifier-free part.

        \item Formula is in \textbf{Skolem normal form (SNF)}\Href{https://en.wikipedia.org/wiki/Skolem_normal_form} if it is in prenex normal form with only universal first-order quantifiers.

        \item \textbf{Zhegalkin polynomial}\Href{https://en.wikipedia.org//wiki/Zhegalkin_polynomial} is a formula in the following form (\textbf{algebraic normal form (ANF)}):
        \begin{terms}
            \item \(
                f(X_1, \dotsc, X_n) = a_0 \xor
                \bigxorclap{\substack{
                    1 \leq i_1 \leq \dotsb \leq i_k \leq n \\
                    1 \leq k \leq n }}
                (a_{i_1, \dotsc, i_k} \land X_{i_1} \land \dots \land X_{i_k}),
                \text{ where } a_0, a_{i_1, \dotsc, i_k} \in \Bool
            \)

            \item \(
                f(x_1, \dotsc, x_n) = a_0 \xor (a_1 x_1 \xor \dotsb \xor a_n x_n) \xor (a_{1,2} x_1 x_2 \xor \dotsb \xor a_{n-1,n} x_{n-1} x_n) \xor \dotsb \xor a_{1,\dotsc,n} x_1 \dots x_n
            \)
        \end{terms}
    \end{terms}
\end{terms}


% \newpage
\subsection{Conversion to CNF/DNF}

In order to convert \emph{arbitrary} (\ie \emph{any}) Boolean formula to \emph{equivalent} CNF/DNF:
\begin{enumerate}[topsep=2pt, itemsep=2pt]
    \item Eliminate equivalences, implications and other \enquote{non-standard} operations (\ie rewrite using only $\Set{\land, \lor, \neg}$):
    \par\(\openup-\jot\begin{aligned}[t]
        \mathcal{A} \iff \mathcal{B} &~\rightsquigarrow~ (\mathcal{A} \implies \mathcal{B}) \land (\mathcal{B} \implies \mathcal{A}) \\
        \mathcal{A} \implies \mathcal{B} &~\rightsquigarrow~ \neg\mathcal{A} \lor \mathcal{B}
    \end{aligned}\)

    \item Push negation downwards:
    \par\(\openup-\jot\begin{aligned}[t]
        \neg(\mathcal{A} \lor \mathcal{B}) &~\rightsquigarrow~ \neg\mathcal{A} \land \neg\mathcal{B} \\
        \neg(\mathcal{A} \land \mathcal{B}) &~\rightsquigarrow~ \neg\mathcal{A} \lor \neg\mathcal{B}
    \end{aligned}\)

    \item Eliminate double negation:
    \par$\neg\neg\mathcal{A} ~\rightsquigarrow~ \mathcal{A}$

    Note that after the recursive application of 1\==3 the formula is in NNF.

    \item Push disjunction (for CNF) / conjunction (for DNF) downward:
    \par\(\openup-\jot\begin{aligned}[t]
        (\mathcal{A} \land \mathcal{B}) \lor \mathcal{C} ~\rightsquigarrow_{\textrm{CNF}}~ (\mathcal{A} \lor \mathcal{C}) \land (\mathcal{B} \lor \mathcal{C}) \\
        (\mathcal{A} \lor \mathcal{B}) \land \mathcal{C} ~\rightsquigarrow_{\textrm{DNF}}~ (\mathcal{A} \land \mathcal{C}) \lor (\mathcal{B} \land \mathcal{C}) \\
    \end{aligned}\)

    \item Eliminate $\top$ and $\bot$:
    \par\(\openup-\jot\begin{aligned}[t]
        \mathcal{A} \land \top &~\rightsquigarrow~ \mathcal{A} &\qquad&&
        \mathcal{A} \land \bot &~\rightsquigarrow~ \bot \\
        \mathcal{A} \lor \top &~\rightsquigarrow~ \top &\qquad&&
        \mathcal{A} \lor \bot &~\rightsquigarrow~ \mathcal{A} \\
        \neg\top &~\rightsquigarrow~ \bot &\qquad&&
        \neg\bot &~\rightsquigarrow~ \top
    \end{aligned}\)
\end{enumerate}


\newpage
\subsection{Functional Completeness%
\texorpdfstring{\normalsize\protect\Href{https://en.wikipedia.org/wiki/Functional_completeness}}{}}

\begin{terms}
    \item A set $S$ is called \textbf{closed} under some operation~\enquote{\textbullet} if the result of the operation applied to any elements in the set is also contained in this set, \ie $\forall x,y \in S: (x \mathbin{\text{\textbullet}} y) \in S$.
    \hfill\href{https://mathworld.wolfram.com/ClosedSet.html}{Closed set}

    \item The \textbf{closure} $S^{*}$ of a set $S$ is the minimal \emph{closed} superset of $S$.
    \hfill\href{https://mathworld.wolfram.com/SetClosure.html}{Closure}

    % \item TODO: Composition (superposition) of Boolean functions.
    % \item TODO: Functional closure.

    \item A set of Boolean functions~$F$ is called \textbf{functionally complete} if it can be used to express all possible Boolean functions.
    Formally, $F^{*} = \mathbb{F}$, where $F^{*}$ is a \emph{functional closure} of~$F$, and $\mathbb{F} = \bigunion\nolimits_{n \in \Natural} \Set{ f \colon \Bool^{n} \to \Bool }$.

    \begin{posttheorem}
        A set of Boolean functions~$F$ is functionally complete iff it contains:
        \begin{itemize}[left=1pc]
            \item at least one function that does \textit{not} preserve zero, \ie $\exists f \in F: f \notin T_0$, and
            \item at least one function that does \textit{not} preserve one, \ie $\exists f \in F: f \notin T_1$, and
            \item at least one function that is \textit{not} self-dual, \ie $\exists f \in F: f \notin S$, and
            \item at least one function that is \textit{not} monotonic, \ie $\exists f \in F: f \notin M$, and
            \item at least one function that is \textit{not} linear function, \ie $\exists f \in F: f \notin L$.
        \end{itemize}
    \end{posttheorem}

    \item A function $f$ is \textbf{zero-preserving}\Href{https://en.wikipedia.org/wiki/Functional_completeness\#Characterization_of_functional_completeness} iff it is \texttt{False} on the zero-valuation ($\vvmathbb{0} = \Tuple{0,0,\dotsc,0}$):
    \par\quad$f \in T_0 \iff f(\vvmathbb{0}) = 0$

    \item A function $f$ is \textbf{one-preserving}\Href{https://en.wikipedia.org/wiki/Functional_completeness\#Characterization_of_functional_completeness} iff it is \texttt{True} on the one-valuation ($\vvmathbb{1} = \Tuple{1,1,\dotsc,1}$):
    \par\quad$f \in T_1 \iff f(\vvmathbb{1}) = 1$

    \item A function $f$ is \textbf{self-dual}\Href{https://en.wikipedia.org/wiki/Functional_completeness\#Characterization_of_functional_completeness} iff it is dual to itself:
    \par\quad$f \in S \iff \forall x_1,\dotsc,x_n \in \Bool : f(x_1, \dotsc, x_n) = \overline{f}(\overline{x}_1, \dotsc, \overline{x}_n)$.

    \item A function $f$ is \textbf{monotonic}\Href{https://en.wikipedia.org/wiki/Monotone_boolean_function} iff for every increasing valuations, the function does not decrease:
    \par\quad$f \in M \iff \forall a,b \in \Bool^n: a \preceq b \implies f(a) \leq f(b)$.

    Comparison of valuations $a,b \in \Bool^n$ is defined as follows:
    \par\quad$\displaystyle a \preceq b \iff \biglandclap{1 \leq i \leq n} (a_i \leq b_i)$

    \item A function $f$ is \textbf{linear} iff its Zhegalkin polynomial is linear (\ie has a degree at most 1):
    \par\quad$f \in L \iff \operatorname{deg} f_{\xor} \leq 1$

    % TODO: Post's lattice

    % \item
\end{terms}


% \subsection{Truth Tables}

% \begin{tabular}{
%     @{~}
%     C @{~} C
%     @{~~~} |
%     @{~~~} C @{\,} C
%     @{~~~} C @{\,} C @{\,} C
%     @{~~~} C @{\,} C @{\,} C
%     @{~~~} C @{\,} C @{\,} C
%     @{~~~} C @{\,} C @{\,} C
%     @{~~~} C @{\,} C @{\,} C
%     @{~}
% }
% \toprule
%     A & B &
%     \neg & A &
%     A & \land & B &
%     A & \lor & B &
%     A & \xor & B &
%     A & \implies & B &
%     A & \iff & B \BotStrut\\
% \hline\TopStrut
%     0 & 0 &
%     \textbf{1} & 0 &      % \neg
%     0 & \textbf{0} & 0 &  % \land
%     0 & \textbf{0} & 0 &  % \lor
%     0 & \textbf{0} & 0 &  % \xor
%     0 & \textbf{1} & 0 &  % \implies
%     0 & \textbf{1} & 0 \\ % \iff
%     0 & 1 &
%     \textbf{1} & 0 &      % \neg
%     0 & \textbf{0} & 1 &  % \land
%     0 & \textbf{1} & 1 &  % \lor
%     0 & \textbf{1} & 1 &  % \xor
%     0 & \textbf{1} & 1 &  % \implies
%     0 & \textbf{0} & 1 \\ % \iff
%     1 & 0 &
%     \textbf{0} & 1 &      % \neg
%     1 & \textbf{0} & 0 &  % \land
%     1 & \textbf{1} & 0 &  % \lor
%     1 & \textbf{1} & 0 &  % \xor
%     1 & \textbf{0} & 0 &  % \implies
%     1 & \textbf{0} & 0 \\ % \iff
%     1 & 1 &
%     \textbf{0} & 1 &      % \neg
%     1 & \textbf{1} & 1 &  % \land
%     1 & \textbf{1} & 1 &  % \lor
%     1 & \textbf{0} & 1 &  % \xor
%     1 & \textbf{1} & 1 &  % \implies
%     1 & \textbf{1} & 1 \\ % \iff
% \bottomrule
% \end{tabular}


% \subsection{Karnaugh map}

% \tikzset{mykarnaughstyle/.style={
%     karnaugh,
%     x=1\kmunitlength, y=1\kmunitlength,
%     enable indices,
%     % disable bars,
%     binary index,
%     kmindexpos={0.5}{0.15},
%     kmindex/.style={font=\tiny\itshape,blue},
%     kmcell/.style={
%         label={[font=\scriptsize,red,right,xshift=-0.45\kmunitlength,inner sep=1pt]\the\kmindexcounter},
%         font=\bfseries,
%     },
%     kmbar  top sep=0.7\kmunitlength,
%     kmbar left sep=0.7\kmunitlength,
%     grp/.style n args={3}{
%         draw,
%         rectangle,
%         ##1,
%         fill=##1!30,
%         fill opacity=0.3,
%         minimum width=##2\kmunitlength,
%         minimum height=##3\kmunitlength,
%         rounded corners=0.2\kmunitlength,
%     },
%     thick,
% }}

% \newcommand{\drawlabels}{%
%     \begin{scope}[font=\small]
%         \begin{scope}[xshift=0.5\kmunitlength]
%             \node[above] at (0,4) {00};
%             \node[above] at (1,4) {01};
%             \node[above] at (2,4) {11};
%             \node[above] at (3,4) {10};
%         \end{scope}
%         \begin{scope}[yshift=0.5\kmunitlength]
%             \node[left] at (0,3) {00};
%             \node[left] at (0,2) {01};
%             \node[left] at (0,1) {11};
%             \node[left] at (0,0) {10};
%         \end{scope}
%     \end{scope}
%     \draw[sloped,font=\scriptsize,inner sep=2pt] (0,4) -- node[above]{AB} node[below]{CD} +(-0.4,0.4);
% }

% The \textbf{Karnaugh map} is a heuristic method for simplifying Boolean formulas.

% % \begin{figure}[H]
% % \centering
% \begin{tikzpicture}[mykarnaughstyle]
%     \karnaughmapvert{4}%
%     % {$f(A,B,C,D)$}%
%     {}%
%     {{$A$}{$B$}{$C$}{$D$}}%
%     {0110 0110 0110 0110}%
%     {
%         \node[grp={blue}{0.9}{1.9}](n000) at (0.5,2) {};
%         \node[grp={blue}{0.9}{1.9}](n001) at (3.5,2) {};
%         % \draw[blue]
%         %     (n000.north) to [bend  left=25] (n001.north)
%         %     (n000.south) to [bend right=25] (n001.south) ;
%         \node[grp={red}{1.9}{0.9}](n100) at (2,3.5) {};
%         \node[grp={red}{1.9}{0.9}](n110) at (2,0.5) {};
%         % \draw[red]
%         %     (n100.west) to [bend right=25] (n110.west)
%         %     (n100.east) to [bend  left=25] (n110.east) ;
%     }
%     % \drawlabels
% \end{tikzpicture}
% % \end{figure}


\end{document}