Diskrete Mathematik/Gemischte Satzabfrage/1/Aufgabe/Lösung

1. Es sei $G$ eine Menge und es seien $A_i\subseteq G$, $i=1,\dots ,n$, endliche Teilmengen. Für eine Teilmenge  $J\subseteq \{1,\dots ,n\}$  sei

   $A_J=\bigcap _{i\in J}{A}_i.$

   Dann ist

   $\mathrm{\#}\left(\bigcup _{i=1}^n{A}_i\right)=\sum _{k=1}^n(-1{)}^{k+1}\left(\sum _{J\subseteq \{1,\dots ,n\},\mathrm{\#}\left(J\right)=k}\mathrm{\#}\left(A_J\right)\right).$

2. Jeder endliche boolesche Verband $B$ ist isomorph zur Potenzmenge einer endlichen Menge.
3. In einem bipartiten Graphen stimmt die Paarungszahl mit der Knotenüberdeckungszahl überein.

Zur gelösten Aufgabe