(product set, cartesian product) FB Technologie und ...siol/DV1_Folien_WS0910/DVPT1_03.pdf · Kartesisches Produkt, Kreuzprodukt, Mengenprodukt, Produktmenge, bei den Mengen A und

(r.siol) 13.12.2009 Hochschule Ravensburg-Weingarten

Technik | Wirtschaft | Sozialwesen

1

FB Technologie und

Management

Datenverarbeitung 1

(Kapitel 3 Mengen)



2

Potenzmenge (power set)

Definition 3: Die Potenzmenge P(M) einer Menge M ist die Gesamtheit aller Teilmengen von M.

Die leere Menge ist immer ein Element der Potenzmenge!

Beispiel. Sei M = {a, b, c}.

Dann ist

P(M) = {Ø,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}

Satz 1: Hat eine Menge n Elemente, so hat ihre Potenzmenge 2n Elemente.

Für S={0,1} ist P(S) = {Ø,{0} ,{1} ,{0,1}} eine Menge mit 4 Teilmengen (Elementen).

Für T = {1,2,3} ist P(T) = {Ø,{1} ,{2} ,{3} ,{1,2} ,{1,3} ,{2,3} ,{1,2,3}} eine Menge

mit 23 = 8 Teilmengen (Elementen). Man sagt auch: Die Menge T hat die Kardinalität 8.

Definition: Die Anzahl der Elemente einer Menge M heißt Kardinalzahl |M|.



3

Kartesisches Produkt(product set, cartesian product)

Definition 5: Es seien S und T zwei Mengen. Das kartesische Produkt S x T von S und T ist

die Menge aller geordneten Paare (s, t) mit s S und t T, also

S x T = {(s, t) | s S und t T}

Beispiel. Ist S = {1, 2, 3} und T = {2, 3}, dann ist S x T={(1, 2),(1, 3),(2, 2),(2, 3), (3,2),(3,3)}

und T x S ={(2, 1),(2, 2),(2, 3),(3,1),(3,2),(3, 3)}

Kartesisches Produkt, Kreuzprodukt, Mengenprodukt, Produktmenge, bei den Mengen A

und B die Menge A x B (gelesen A kreuz B) aller geordneten Paare (a,b)

mit und .

!

a" A

!

b" B



4

Kartesisches ProduktBeispiel. Es seien S und T die folgenden Mengen reeller Zahlen:

S = {x | x reell , 0 ! x ! 1} und T = {y | y reell , 0 ! y ! 2}

Dann ist

S x T = {(x, y) | 0 ! x ! 1, 0 ! y ! 2}

Wenn man S und T als Intervalle auffaßt, dann ist ihr kartesisches Produkt das Rechteck, dessen

Eckpunkte in einem kartesischen Koordinatensystem die Koordinaten (0,0), (1,0), (1,2), (0,2) haben.

Allgemeiner ist die Ebene in diesem Sinne das kartesische Produkt zweier Geraden.

T

S S x T



5

Descartes, RenéDescartes [de'kart], René, latinisiert Renatus Cartesius, frz. Philosoph,Mathematiker und Naturwissenschaftler, *La Haye (heute La Haye-Descartes,Touraine) 31. 3. 1596, † Stockholm 11. 2. 1650.

Aus altem Adelsgeschlecht stammend, wurde D. 1604-14 amdamals renomierten Jesuitenkolleg in La Fleche in der scholast. Philosophieund Naturwissenschaft ausgebildet; danach Studium der Rechte in Poitiers (bis1616), seit 1618 Kriegsdienste in den Armeen MORITz' von Nassau und desKurfürsten MAXIMILIAN von Bayern; seine mathemat. und physikal.Fragestellungen wurden wesentlich angeregt durch die Begegnung mit J.BEEKMANN (1618/19).

Es folgten Reisen durch Europa und 1625-29 ein Aufenthalt inParis.D. emigrierte 1629 nach Holland, widmete sich dort wissenschaftl.Studien, verfaßte den größten Teil seiner mathemat., physikal., medizin. undmetaphysisch-philosoph. Werke und pflegte Kontakte zu vielenWissenschaftlern seiner Zeit, v. a. zu M. MERSENNE.

Im Herbst 1649 folgte er einer Einladung der Königin CHRISTINEnach Stockholm, wo er vier Monate später verstarb.



6

KomplementbildungDas Wort Komplement leitet sich aus dem lateinischen ab; complementum = Ergänzung.

In der Mengenlehre werden die Begriffe Komplementärmenge, Komplement, Ergänzungsmenge

verwendet.

Als Komplementärmenge einer Teilmenge A von der Grundmenge G bezeichnet man die

Differenzmenge G - A, d.h. die Menge aller Elemente von G, die nicht zu A gehören.

Man bezeichnet dann die Komplementärmenge als (sprich: >A quer<)

!

A

Dabei ist A eine echte Untermenge von G!

Das Komplement zu A wird bezüglich

der Menge G gebildet.

G-A

A



7

Boolesche Algebra der Teilmengen

!

R" S#T( ) = R" S( )# R"T( )

S T

R

S T

R

!

R" S#T( )

!

S"T( )

!

R" S( )

!

R"T( )

!

R" S( )# R"T( )



8

• Vereinigung der Mengen S und T

– Darstellung durch eine Formel

– Veranschaulichung mit Venn-Diagramm

Kardinalzahl

!

| S"T |= S + T # S$T

S

T

!

S"T

Im Durchschnitt für werden

die Elemente zweimal gezählt, daher

muss der Wert einmal subtrahiert

werden. !

S"T



9

• Vereinigung dreier Mengen R,S und T– Ab drei und mehr Mengen geht das mit Venn-Diagrammen, wird aber sehr unübersichtlich

Kardinalzahl

R

S

T

+|R|

+|S|

+|T|

!

R" S"T

!

R" S"T = R + S + T # R$ S # R$T # S$T + R$ S$T

-|RS|

-|ST|

-|RT|

+|RST|



10

• Vereinigung dreier Mengen R,S und T– Algebraische Lösung

Kardinalzahl

!

X"T = X + T # X$T

X = R" S

R" S"T = R" S + T # R" S( )$T

R" S"T = R + S # R$ S + T # R$T)" (S$T( )

R" S"T = R + S + T # R$ S # R$T + S$T # R$T$ S$T{ }R" S"T = R + S + T # R$ S # R$T # S$T + R$ S$T

Man geht davon aus, dass das Ergebnis für zwei Mengen

bekannt ist und substituiert.

Es fällt auf, dass in der letzten Zeile alle zugehörigen Teilmengen der

Potenzmenge von R, S und T verwendet werden; außer der Ø-Menge

deren Kardinalität aber 0 ist und die daher keinen Einfluss auf das Ergebnis hat.



11

Vergleich verschiedener Algebren

Boolesche Algebra (Axiomensystem von Huntington)

Name der Algebra Schaltalgebra Algebra der Aussagen Mengenalgebra

Elemente der Algebra Schaltvariable

(zweiertige Variable)

Aussagen Teilmengen einer

gegebenen Menge

Addition

+

Disjunktion

!

"

Vereinigung

!

#Multiplikation

.

Konjunktion

&

Durchschnitt

!

$

Benennung

und

Bezeichnung

der

Verknüpfungen Komplementierung Negation

¯

Bildung der

komplementären

Menge



12

• Vereinigung der Mengen A, B, C und D– Algebraische Lösung

Kardinalzahl

!

X"Y = X + Y # X$YFür zwei Mengen gilt:

Gesucht wird:

!

A" B"C"D

Wir substituieren :

!

X = A" B

Y = C"D

Und erhalten :

!

A" B( )" C"D( ) = A" B( ) + C"D( ) # A" B( )$ C"D( )

A" B( )" C"D( ) = A + B # AB + C + D # CD # AC" AD" BC" BD



13


Kardinalzahl

Betrachtung des Teilausdrucks :

!

AC" AD" BC" BD = AC" AD( )" BC" BD( )

= AC" AD( ) + BC" BD( ) # AC" AD( )$ BC" BD( )

= AC + AD # ACD + BC + BD # BCD # ABC" ABCD" ABCD" ABD( )

= AC + AD # ACD + BC + BD # BCD # ABC" ABCD" ABD( )

= AC + AD # ACD + BC + BD # BCD # ABC" ABD( )" ABCD

= AC + AD # ACD + BC + BD # BCD # ABC" ABD( ) + ABCD # ABCD ABC" ABD( )( )= AC + AD # ACD + BC + BD # BCD # ABC + ABD # ABCD + ABCD # ABCD" ABCD( )

= AC + AD # ACD + BC + BD # BCD # ABC + ABD # ABCD + ABCD # ABCD( )

= AC + AD # ACD + BC + BD # BCD # ABC + ABD # ABCD( )= AC + AD # ACD + BC + BD # BCD # ABC # ABD + ABCD

= AC + AD + BC + BD # ACD # BCD # ABC # ABD + ABCD



14


Kardinalzahl

Und erhalten :

!

A" B( )" C"D( )

= A + B # AB + C + D # CD # AC + AD + BC + BD # ACD # BCD # ABC # ABD + ABCD( )= A + B # AB + C + D # CD # AC # AD # BC # BD + ACD + BCD + ABC + ABD # ABCD

= A + B + C + D # AB # CD # AC # AD # BC # BD + ACD + BCD + ABC + ABD # ABCD

Es fällt auf, dass in der letzten Zeile alle zugehörigen Teilmengen der

Potenzmenge von {A, B, C, D} verwendet werden; außer der Ø-Menge

deren Kardinalität aber 0 ist und die daher keinen Einfluss auf das Ergebnis hat.

Zusammen mit den vorhergehenden Beispielen besteht nun die Vermutung, dass

immer dann, wenn der Durchschnitt einer geradzahligen Anzahl von Mengen

gebildet wird das Vorzeichen negativ ist.



15

B

A

!

A

!

A

!

B

!

B

!

A" B = A# BSatz von de Morgan

M

!

A" B



16

B

A

!

A

!

B

!

B

!

A" B = A# B

!

A" B

!

A" B

Satz von de Morgan

!

A



17

Verallgemeinerung der Sätze von De Morgan• Wir gehen davon aus, dass die Gültigkeit der Sätze von de Morgan für je zwei

Mengen gezeigt wurde.

!

A" B = A# B

B = C"D

A"C"D = A#C"D

C"D = C#D

A"C"D = A#C#D

Dies sei gegeben.

Wir substituieren für B den Durchschnitt

von C und D und wenden darauf

wieder die ursprüngliche Formel an.

Dies lässt sich sinngemäß

beliebig fortsetzten.

Das verallgemeinerte Gesetz lautet also:

!

Ii=1

n

Mi= U

i=1

n

Mi



18

Verallgemeinerung der Sätze von De Morgan• Wir gehen davon aus, dass die Gültigkeit der Sätze von de Morgan für je zwei

Mengen gezeigt wurde.

!

A" B = A# B

B = C"D

A"C"D = A#C"D

C"D = C#D

A"C"D = A#C#D

Dies sei gegeben.

Wir substituieren für B die Vereinigung

von C und D und wenden darauf

wieder die ursprüngliche Formel an.

Dies lässt sich sinngemäß

beliebig fortsetzten.

Das verallgemeinerte Gesetz lautet also:

!

Ui=1

n

Mi= I

i=1

n

Mi



19

B

A

!

A

!

A

!

B

!

B

Differenz A - B

M!

A " B = A# B



20

B

A

!

A

!

A

!

B

!

B

Differenz B - A

M!

B " A = B# A

Documents

(product set, cartesian product) FB Technologie und ...siol/DV1_Folien_WS0910/DVPT1_03.pdf · Kartesisches Produkt, Kreuzprodukt, Mengenprodukt, Produktmenge, bei den Mengen A und