Mathematics-Online course: Prepcourse Mathematics-Basics-Sets-Laws for Operations on Sets

	[home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff]
	Mathematics-Online course: Prepcourse Mathematics - Basics - Sets
	Laws for Operations on Sets

[previous page] [next page]

[table of contents][page overview]

The following identities hold for operations on sets:

Assoziative Laws:

$\displaystyle (A\cap B)\cap C$ $\displaystyle =$ $\displaystyle A \cap (B \cap C)$

$\displaystyle (A\cup B)\cup C$ $\displaystyle =$ $\displaystyle A \cup (B \cup C)$
Kommutative Laws:

$\displaystyle A\cap B$ $\displaystyle =$ $\displaystyle B \cap A$

$\displaystyle A\cup B$ $\displaystyle =$ $\displaystyle B \cup A$
De Morgan's Laws:

$\displaystyle C\backslash(A\cap B)$ $\displaystyle =$ $\displaystyle (C\backslash A) \cup (C\backslash B)$

$\displaystyle C\backslash (A\cup B)$ $\displaystyle =$ $\displaystyle (C\backslash A) \cap (C\backslash B)$
Distributive Laws:

$\displaystyle (A\cap B)\cup C$ $\displaystyle =$ $\displaystyle (A\cup C) \cap (B\cup C)$

$\displaystyle (A\cup B)\cap C$ $\displaystyle =$ $\displaystyle (A\cap C) \cup (B\cap C)$

These laws correspond to the laws for logical operations, with $\cup,\cap$ being replaced by $\land,\lor$ and $C\backslash$ being replaced by $\lnot$ .

(Authors: Höllig/Hörner/Abele)

As an example we will prove the first of de Morgan's Laws here.

We have

$\displaystyle x\in C\backslash ( A\cap B)$	$\displaystyle \Leftrightarrow$	$\displaystyle x\in C\,\land x\notin (A\cap B)$
	$\displaystyle \Leftrightarrow$	$\displaystyle x\in C\,\land (x\notin A \lor x\notin B) \,.$

This term is (with application of distributive laws) equivalent to

$\displaystyle (x\in C\land x\notin A) \lor (x\in C \land x\notin B) \Leftrightarrow x \in (C\backslash A \cup C\backslash B) \,,$

which proves the asserted identity.

(Authors: Höllig/Abele)

[previous page] [next page]

[table of contents][page overview]

automatically generated 9/18/2007

$\displaystyle (A\cap B)\cap C$	$\displaystyle =$	$\displaystyle A \cap (B \cap C)$
$\displaystyle (A\cup B)\cup C$	$\displaystyle =$	$\displaystyle A \cup (B \cup C)$

$\displaystyle A\cap B$	$\displaystyle =$	$\displaystyle B \cap A$
$\displaystyle A\cup B$	$\displaystyle =$	$\displaystyle B \cup A$

$\displaystyle C\backslash(A\cap B)$	$\displaystyle =$	$\displaystyle (C\backslash A) \cup (C\backslash B)$
$\displaystyle C\backslash (A\cup B)$	$\displaystyle =$	$\displaystyle (C\backslash A) \cap (C\backslash B)$

$\displaystyle (A\cap B)\cup C$	$\displaystyle =$	$\displaystyle (A\cup C) \cap (B\cup C)$
$\displaystyle (A\cup B)\cap C$	$\displaystyle =$	$\displaystyle (A\cap C) \cup (B\cap C)$