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

Es sei ${}G$ eine Menge und es seien ${}A_{i}\subseteq G$ , ${}i=1,\ldots ,n$ , endliche Teilmengen. Für eine Teilmenge ${}J\subseteq {\{1,\ldots ,n\}}$ sei
${}A_{J}=\bigcap _{i\in J}A_{i}\,.$

Dann ist

${}{\#\left(\bigcup _{i=1}^{n}A_{i}\right)}=\sum _{k=1}^{n}(-1)^{k+1}{\left(\sum _{J\subseteq \{1,\ldots ,n\},\,{\#\left(J\right)}=k}{\#\left(A_{J}\right)}\right)}\,.$
Jeder endliche boolesche Verband ${}B$ ist isomorph zur Potenzmenge einer endlichen Menge.
In einem bipartiten Graphen stimmt die Paarungszahl mit der Knotenüberdeckungszahl überein.

This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.