\documentclass{scrartcl} 
\usepackage[latin1]{inputenc}
\usepackage[ngerman]{babel}
\usepackage{tabularx} 
\usepackage{multirow}
\usepackage{geometry}
\usepackage{lastpage}
\usepackage{graphicx}
\usepackage[automark]{scrpage2}
\pagestyle{scrheadings}
\ifoot{Julian Bergmann\\Florian Greiner\\Timo Grosch\\Julia Welsch}
\cfoot{12.10.2009}
\ofoot{\thepage / \pageref{LastPage}}
\chead[]{}
\geometry{a4paper,left=40mm,right=30mm, top=1cm, bottom=3cm} 
\fontsize{10}{16}\selectfont
\newcolumntype{C}[1]{>{\centering\arraybackslash}p{#1}} 
\newcolumntype{x}{>{\centering\arraybackslash}X} 
\newcolumntype{L}[1]{>{\raggedleft\arraybackslash}p{#1}} 
\renewcommand{\arraystretch}{1.4}

\begin{document}
\section{Übungen zu Mathematik für Physiker zum Dienstag, dem 20.10.2009}

\subsection{Zeigen Sie für beliebige Mengen A,B,C:}
\begin{quote}
$A \setminus (B \cup C)=(A \setminus B) \cap (A \setminus C)$:
\begin{quote} \parskip 0pt
sei $x\in A \setminus (B \cup C)$ beliebig, dann:

=$x\in A \wedge \neg(x\in B \vee x\in C)$

=$x\in A \wedge (\neg x\in B \wedge \neg x\in C)$

=$x\in A \wedge x\in A \wedge \neg x\in B \wedge \neg x\in C$

=$x\in A \wedge \neg x\in B \wedge x\in A \wedge \neg x\in C$

=$x\in (A \setminus B) \cap (A \setminus C)$

$\Rightarrow A \setminus (B \cup C) \subseteq (A \setminus B) \cap (A \setminus C)$

\parskip 12pt

sei $x\in (A \setminus B) \cap (A \setminus C)$ beliebig, dann:
\parskip 0pt

=$x\in A \wedge \neg x\in B \wedge x\in A \wedge \neg x\in C$

=$x\in A \wedge x\in A \wedge \neg x\in B \wedge \neg x\in C$

=$x\in A \wedge (\neg x\in B \wedge \neg x\in C)$

=$x\in A \wedge \neg(x\in B \vee x\in C)$

=$x\in A \setminus (B \cup C)$

$\Rightarrow A \setminus (B \cup C) \supseteq (A \setminus B) \cap (A \setminus C)$

\parskip 12pt
$\Longrightarrow A \setminus (B \cup C)=(A \setminus B) \cap (A \setminus C)$
\end{quote}

\parskip 0pt
$A \setminus (B \setminus C) = (A \setminus B) \cup (A\cap C)$
\begin{quote} \parskip 0pt
sei $x\in A \setminus (B \setminus C)$ beliebig, dann:

=$x\in A \wedge \neg(x\in B \wedge \neg x\in C)$

=$x\in A \wedge (\neg x\in B \vee x\in C)$

=$(x\in A \wedge \neg x\in B) \vee (x\in A \wedge x\in C)$

=$x\in (A \setminus B) \cup (A\cap C)$

$\Rightarrow A \setminus (B \setminus C) \subseteq (A \setminus B) \cup (A\cap C)$

\parskip 12pt
sei $x\in (A \setminus B) \cup (A\cap C)$ beliebig, dann:
\parskip 0pt

=$(x\in A \wedge \neg x\in B) \vee (x\in A \wedge x\in C)$

=$x\in A \wedge (\neg x\in B \vee x\in C)$

=$x\in A \wedge \neg(x\in B \wedge \neg x\in C)$

=$x\in A \setminus (B \setminus C)$

$\Rightarrow A \setminus (B \setminus C) \supseteq (A \setminus B) \cup (A\cap C)$

\parskip 12pt
$\Longrightarrow A \setminus (B \setminus C)=(A \setminus B) \cup (A \cap C)$
\parskip 0pt
\end{quote}

$A \setminus (A \setminus B) = A\cap B$
\begin{quote} \parskip 0pt
sei $x\in A \setminus (A \setminus B)$ beliebig, dann:

=$x\in A \wedge \neg(x\in A \wedge \neg x\in B)$

=$x\in A \wedge (\neg x\in A \vee x\in B)$

=$(x\in A \wedge \neg x\in A) \vee (x\in A \wedge x\in B)$

=$(x\in A \wedge x\in B)$

=$x\in (A\cap B)$

$\Rightarrow A \setminus (A \setminus B) \subseteq (A\cap B)$
\newpage
\parskip 12pt

sei $x\in (A\cap B)$ beliebig, dann:
\parskip 0pt

=$(x\in A \wedge x\in B)$

=$(x\in A \wedge \neg x\in A) \vee (x\in A \wedge x\in B)$

=$x\in A \wedge (\neg x\in A \vee x\in B)$

=$x\in A \wedge \neg(x\in A \wedge \neg x\in B)$

=$x\in A \setminus (A \setminus B)$

$\Rightarrow A \setminus (A \setminus B) \supseteq (A\cap B)$

\parskip 12pt
$\Longrightarrow A \setminus (A \setminus B)=(A \cap B)$
\parskip 0pt

\end{quote}
\end{quote}
\subsection{Übersetze in Mengeninklusion}
\begin{quote}
\begin{enumerate} \parskip 0pt
	\item i) $x \in Z \Rightarrow x \in M^C$
	\item ii) $x \in G \Rightarrow x \in T$
	\item iii) $x \in G^C \Rightarrow x \in H$
	\item iv) $x \in R^C \Rightarrow x \in Z$
	\item v) $x \in H \Rightarrow x \in R^C$
\end{enumerate}
Zu Zeigen: $x \in M \Rightarrow x \in T$
\begin{enumerate} \parskip 0pt
	\item $x \in R^C\Rightarrow x \in Z\Rightarrow x \in M^C$
	\item $x \in H\Rightarrow x \in R^C\Rightarrow x \in Z\Rightarrow x \in M^C$
	\item $x \in G^C\Rightarrow x \in H\Rightarrow x \in R^C\Rightarrow x \in Z\Rightarrow x \in M^C $
	\item $x \in G^C\Rightarrow x \in M^C = x \in M\Rightarrow x \in G$
	\item $x \in M\Rightarrow x \in G \Rightarrow x \in T$
\end{enumerate}
$\Longrightarrow x \in M\Rightarrow x \in T$
\end{quote}

\subsection{Zeichne eine NAND-Schaltung}
\begin{quote} \parskip 0pt

Regeln:
\begin{enumerate} \parskip 0pt
	\item aus Übersichtsgründen: "`NAND"'="`N"'
	\item $a\vee b=(aNa)N(bNb)$
	\item $a\wedge b=(aNb)N(aNb)$
	\item $\neg a=aNa$
\end{enumerate}
\parskip 0pt
Umformulierung:
$\Big[(a \vee b) \vee (c \vee \neg d)\Big] \wedge (c \wedge \neg a)\\
=\\
(((((aNa)N(bNb))N((aNa)N(bNb)))\\
N(((cNc)N((dNd)N(dNd)))N((cNc)N((dNd)N(dNd)))))\\
N(cN(aNa))N(cN(aNa)))\\
N(((((aNa)N(bNb))N((aNa)N(bNb)))\\
N(((cNc)N((dNd)N(dNd)))N((cNc)N((dNd)N(dNd)))))\\
N(cN(aNa))N(cN(aNa)))
$

Abstraktion in Ebenen zur Grafischen Darstellung:

Grundbausteine (1. Ebene):
$aNa\rightarrow A; bNb\rightarrow B; cNc\rightarrow C; dNd\rightarrow D\\
\\
(((((A)N(B))N((A)N(B)))N(((C)N((D)N(D)))\\
N((C)N((D)N(D)))))\\
N(cN(A))N(cN(A)))\\
N(((((A)N(B))N((A)N(B)))N(((C)N((D)N(D)))\\
N((C)N((D)N(D)))))\\
N(cN(A))N(cN(A)))$

2. Ebene:
$ANB\rightarrow F; DND\rightarrow G; cNA\rightarrow H\\
$\newpage$
(((FNF)N(((C)NG)N((C)NG)))\\
N(HNH))\\
N(((FNF)N(((C)NG)N((C)NG)))\\
N(HNH))$

3. Ebene:
$FNF\rightarrow I; CNG\rightarrow J; HNH\rightarrow K\\
\\
(((I)N((J)N(J)))NK)N(((I)N((J)N(J)))NK)$

4. Ebene:
$JNJ\rightarrow L\\
\\
(((I)N(L))NK)N(((I)N(L))NK)$

5. Ebene:
$INL\rightarrow M\\
\\
((M)NK)N((M)NK)$

6. Ebene:
$MNK\rightarrow O\\
\\
(O)N(O)$

Ergebnis:
$\Longrightarrow ONO$
\end{quote}

\includegraphics[width=1.1\textwidth]{MyPh3.png}

\parskip 12pt
\bfseries
Alternative: Vereinfachung
\normalfont

\parskip 0pt
\begin{quote}
Da der Term $a\vee b\vee c\vee \neg d$ dann wahr ist, wenn c wahr ist, c aber für den nachfolgenden Teil $\wedge (c\wedge \neg a)$ Immer wahr sein muss, damit dieser Teil wahr ist, und selbiges lediglich auch auf $\neg a$ zutrifft, lässt sich die Gleichung auf $c\wedge \neg a$, also auf den rechten Teil reduzieren. Zum weiteren Beleg eine Wahrheitstabelle:

\includegraphics[width=0.7\textwidth]{Wahrheit_Nand_Vereinfachung.png}
\newpage
Dies hätte den Vorteil, dass sich dadurch die NAND-Schaltung erheblich vereinfachen würde:

$(cn(ana))n(cn(ana))$

was folgende Schaltung ergeben würde:

\includegraphics[width=0.7\textwidth]{Vereinf_NAND.png}
\end{quote}
	\subsection{XOR-Verknüpfung}
	
\begin{quote}
a) 
	\begin{tabular}{|c|c|c|}
\hline
a&b&$(\neg a\wedge b)\vee (a\wedge \neg b)$\\ \hline
\hline

w&w&f\\ \hline
w&f&w\\ \hline
f&w&w\\ \hline
f&f&f\\ \hline
\end{tabular}

b)
Da das Byte b XOR c durch die bitweise Anwendung der Xor-Verknüpfung definiert ist, lässt sich das Problem des Zeigens auf einfache Bit-Aussagen zurückführen.

Folglich gilt:

Die Abbildung $f_b=c\rightarrow bXORc, b\in B$ ist invers, sofern gilt:

$c=f_b\rightarrow bXORf_b, b\in B$

Aufgrund der Zurückführung auf Bits lässt sich eine Wahrheitstabelle erstellen:

	\begin{tabular}{|c|c|c|c|}
\hline
b&c&$f_b: c\rightarrow bXORc$&$c: f_b\rightarrow bXORf_b$\\ \hline
\hline
w&w&f&w\\ \hline
w&f&w&f\\ \hline
f&w&w&w\\ \hline
f&f&f&f\\ \hline
\end{tabular}

Da hiermit gezeigt wurde, dass $c = f_b\rightarrow bXORf_b$, gilt, dass für beliebiges b und beliebiges c einer beliebig langen Kombination (bei bitweiser Anwendung der XOR-Verknüfung) die Abbildung zu sich selbst invers ist.
\end{quote}
\end{document}