\documentclass[12pt]{article}

\usepackage{fullpage,amsmath,amsfonts}
\usepackage{circuitikz}
\usetikzlibrary{positioning}

\begin{document}

\title{Foundations of Information Systems}
\author{Winter Semester 2026--27, Exercise 1}
\date{For discussion on Tuesday(!), October 27, 2026}
\maketitle

\begin{enumerate}

\item In class, we have proved a number of theorems consecutively,
each proof referring to some of the previous results.  We have also
learned that each theorem in Boolean algebra has a ``dual theorem'',
obtained by simultaneously exchanging $\wedge \leftrightarrow \vee$ and
$0 \leftrightarrow 1$.

Prove the following sequence of theorems dual to the ones proved in
class.  Here, the set of elements of the Boolean algebra is $B$ and
the statements are to be true for all $a, b \in B$.
\begin{enumerate}
\item Dual Theorem 1: $a \wedge a = a$
\item Dual Theorem 2: $a \wedge 0 = 0$
\item Dual ``Absorption Theorem'': $a \wedge (a \vee b) = a$
\item Dual ``De Morgan's Law'': $(a \wedge b)' = a' \vee b'$
\end{enumerate}
\emph{Note:} Write out the proofs from scratch without referring to
the dual symmetry principle.  If you get stuck, you can always look at
the lecture notes: each step you take should be the dual of one of the
steps taken in class.

\item Determine whether the following statements are true or false.
If true, state the name of the respective Boolean algebra axiom or
elementary theorem (a proof is not required).  If false, state a
counterexample.
\begin{enumerate}
\item $a \wedge (b \wedge c) = (a \wedge b) \wedge c$
\item $a \wedge (b \vee c) = (a \wedge b) \vee c$
\item $a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$
\item $a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)$
\item $(a \wedge b)' = a' \vee b'$
\end{enumerate}


\item Prove the following statements, referring to the axioms of
Boolean algebra and, if applicable, elementary theorems from class:
\begin{enumerate}
\item $(a \wedge b) \vee (a \wedge b') = a$
\item $(a \wedge b') \vee b = a \vee b$
\item $(a \vee b) \wedge (b \vee c) \wedge (a' \vee c) = (a \vee b) \wedge (a' \vee c)$
\end{enumerate}


\item Derive and simplify a Boolean algebra expression for the
following binary truth table:
\begin{center}
\begin{tabular}{|ccc|c|}
\hline
$a$ & $b$ & $c$ & $z$ \\
\hline
0 & 0 & 0 & 0\vphantom{$\int^1$}\\
0 & 0 & 1 & 1 \\
0 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 \\
1 & 1 & 1 & 0 \\
\hline
\end{tabular}
\end{center}

\item
\begin{enumerate}
\item Convert the following circuit diagram into a Boolean expression
and simplify, if possible:
\begin{center}
% Setup from https://latexdraw.com/draw-a-logic-circuit-in-circuitikz/
\begin{tikzpicture}
 
% Circuit style
\ctikzset{
    logic ports=ieee,
    logic ports/scale=0.8,
    logic ports/fill=lightgray
}
 
% Logic ports
\node[not port] (NOTa) at (0,0){};
\node[or port, right=of NOTa, anchor=in 1] (ORa) {};
\node[not port, below=of ORa] (NOTb) {};
\node[and port, right=of NOTb, anchor=in 2] (ANDa) {};

% Connection
\draw (NOTa.out) -- (ORa.in 1);
\draw (ORa.out) -| (ANDa.in 1);
\draw (NOTb.out) -- (ANDa.in 2);

\draw (NOTa.in) -- (-2,0) node[left](INa){$a$};
\draw (NOTb.in) -- (-2, 0 |- NOTb.in) node[left](INb){$b$};
\draw (ORa.in 2) -- (1, 0 |- ORa.in 2)  to[short, -*] (1, 0 |- NOTb.in);
\draw (ANDa.out) -- ++(1,0) node[right]{$z$};
\end{tikzpicture}
\end{center}

\item Draw a circuit diagram implementing the following Boolean
expression:
\[
  z = (a \wedge b' \wedge c) \vee (a' \wedge b) \vee (a \wedge c)'
\]

\end{enumerate}


\end{enumerate}
\end{document}