Grundlagen der �Informatik (VO)

�Mengen

​

​

Christopher Pollin

​

Institut für Digitale Geisteswissenschaften,�https://digital-humanities.uni-graz.at

Folien wurden KI-assistiert erzeugt.

Lernziele

Grundkonzepte

• Eine Menge formal und umgangssprachlich definieren
• Mengenschreibweisen anwenden ({...}, {...|...})
• Zwischen Element- und Teilmengenbeziehung unterscheiden (∈, ⊆)

Mengenoperationen

• Vereinigung und Schnittmenge von Mengen bilden (∪, ∩)
• Differenz und Komplement von Mengen bestimmen
• Mengenoperationen in Venn-Diagrammen darstellen

“Eine Menge ist eine Ansammlung von wohl unterscheidbaren Objekten unserer Vorstellung oder der Realität.”

• Georg Cantor, Erfinder der Mengenlehre

Am Beispiel des Obstkorbs:

• Jede Frucht ist ein Element
• Jede Frucht ist eindeutig unterscheidbar
• Die Anordnung im Korb ist unwichtig

​

Grundlagen der Mengenlehre (Vorkurs Mathematik). https://youtu.be/AvVq2TfGQlg?si=HgFlwJfvKMtn1E9Z

Zwei Zugänge zur Mengenlehre

Naive Mengenlehre

Intuitive Vorstellung von Mengen als "Sammlung von Objekten"

​

Merkmale:

• Basiert auf Anschauung
• Einfach zu verstehen
• Direkt anwendbar
• Keine formalen Regeln nötig

�

Anwendung:

• Schulunterricht
• Grundlegende Mathematik
• Alltägliche Probleme

Axiomatische Mengenlehre

Formale Definition durch mathematische Axiome

​

Merkmale:

• Mathematisch präzise
• Widerspruchsfrei
• Auf Axiomen aufgebaut
• Formal beweisbar

​

Anwendung:

• Höhere Mathematik
• Mathematische Forschung
• Theoretische Grundlagen

Kann zu Widersprüchen führen (z.B. Russell'sches Paradoxon)

Komplexer und abstrakter, aber mathematisch korrekt

Das Russell'sche Paradoxon�Ein fundamentales Problem der naiven Mengenlehre

"Sei R die Menge aller Mengen, die sich nicht selbst als Element enthalten."

R = {M | M ∉ M}

​

Normale Mengen

• Die Menge aller Bücher ∉ sich selbst�(ist kein Buch)
• Die Menge aller Tische ∉ sich selbst�(ist kein Tisch)
• → Diese Mengen gehören zu R��

Der Widerspruch

Die zentrale Frage:

Enthält R sich selbst als Element?

• Fall 1: R ∈ R�Dann enthält sich R selbst und kann daher nicht in R sein
• Fall 2: R ∉ R�Dann enthält sich R nicht selbst und muss daher in R sein

​

Seltsame Mengen

• Die Menge aller Mengen�(enthält sich selbst)
• Die Menge aller abstrakten Konzepte�(ist selbst abstrakt)
• → Diese Mengen gehören nicht zu R

Konsequenzen

• Zeigt Grenzen der naiven Mengenlehre
• Führte zur axiomatischen Mengenlehre
• Wichtig für Grundlagen der Mathematik
• Ähnlich dem Barbier-Paradoxon:��"Der Barbier rasiert alle Männer im Dorf, die sich nicht selbst rasieren. Wer rasiert den Barbier?"

​

​

Mengenlehre in der Informatik

​

Beispiel (Python):

users_group_a = {'Alice', 'Bob', 'Charlie'}�users_group_b = {'Bob', 'David', 'Eve'}

# Alle Nutzer (Vereinigung)�all_users = users_group_a | users_group_b

# Nutzer in beiden Gruppen (Schnittmenge)�common_users = users_group_a & users_group_b

Datenbanken�

SELECT = Mengenselektion

UNION = Vereinigung

INTERSECT = Schnittmenge

JOIN = Mengenverknüpfung

Datenstrukturen�

Sets in Python

Eindeutige Elemente

Effiziente Suche

Praxisbeispiele�

Benutzergruppen

Berechtigungssysteme

Mengen

A = {Spielkarten, Trommel, � Gitarre, Kamera}

Spielkarten ∈ A�Trommel ∈ A�Gitarre ∈ A�Kamera ∈ A�Buch ∉ A�Ball ∉ A

|A| = 4 �Kardinalität

​

​

https://de.wikipedia.org/wiki/Menge_(Mathematik)

Mengen

T₁₂ = {3, 4, 12, 6, 2, 1}��A = {1, 2, 8, 42}��B = {1, 2, 8, 1, 1, 2, 42} = A

C = {8, 42, 1, 2,} = A = B

​

Mengen sind distinkt, ungeordnet und besitzen eine beliebige Anzahl von Elementen

Leere Menge

∅ = {} �|∅| = 0

Teilmengen vs. echte Teilmenge

A = {2, 20, 200}�B = {8, 2, 5, 20, 100, 200, 456}

Jedes Element von A ist auch Element von B.�2 ∊ A, 20 ∊ A, 200 ∊ A, 8 ∉ A

https://de.wikipedia.org/wiki/Teilmenge

A ⊆ B�A ist Teilmenge von B�A ⊆ B iff ∀x ∊ A, x ∊ B

A ist echte Teilmenge von B�A ⊂ B�A ≠ B (Operator ⊂)

Mengennotation = “set-builder notation”

Die Mengennotation erlaubt es, Kriterien festzumachen, die definieren, ob ein Element einer Menge zugehörig ist. So können auch unendliche Mengen definiert werden:

C = {x² | x ∈ N} … 1²,2²,3²,4² …

D = {x | x² mod 2 = 0, x∈N} … 4² mod 2 = 0, 4∈N

E = {x ∈ N |x ≤ 3 or x ≥ 5} … 3,4,5

http://gdi.ist.tugraz.at/skriptum.pdf ��https://www.youtube.com/watch?v=H1NoUBFv3FA

Vereinigung - UNION - Disjunktion

A∪B={x | x∈A ∨ x∈B}

Schnittmenge - INTERSECTION - Konjunktion

A∩B={x | x∈A ∧ x∈B}

VENN-Diagramm

Komplement und Differenz

T(12)\T(4)�A\B={x| (x∈A) ∧ (x ∉B) }

• T₁₂={3, 4, 12, 6, 2, 1}
• T₄ ={4, 1, 2}

3

​

12

​

6

​

Hands-On

A und B sind Mengen

Wir wissen A ⊆ B (A ist Teilmenge von B)��Was ist:

A∩B = ?

A∪B = ?

​

​

​

Hands-On

A und B sind Mengen

Wir wissen A ⊆ B (A ist Teilmenge von B)��Was ist:

A∩B = A

A∪B = B

​

​

​

B

A

Venn-Diagramme

Venn-Diagramme sind grafische Darstellungen von Mengen als Kreise oder Ellipsen. Sie zeigen mögliche logische Beziehungen zwischen verschiedenen Mengen.

Jeder Kreis repräsentiert eine Menge

Überlappungen zeigen gemeinsame Elemente

Bereiche außerhalb zeigen exklusive Elemente

Christian Spannagel. Beispiele zu Venn-Diagrammen. https://youtu.be/zSdKlTBwCGI?si=6w3T6DYDHjfk1j8H

Hands-On: Venn-Diagramme 1

Zeichne:

S ⋂ (A ∪ B)

https://www.wolframalpha.com/input/?i=S+intersect+%28A+union+B%29

​

S' ⋂ (A ∪ B)

https://www.wolframalpha.com/input/?i=%28complement+S%29+intersect+%28A+union+B%29&lk=3

​

��

Hands-On: Venn-Diagramme 2

Zeige mittels VENN-Diagramm, ob die folgenden zwei Terme, in denen Mengenoperationen auf 3 Mengen (A,B,C) angewandt werden, gleich sind. �Zeichne dazu die VENN-Diagramme (Kreise die sich schneiden) auf und schraffiere/färbe die Mengen, die durch die Operatoren definiert werden, ein.

​

A∪(B⋂C) = (A∪B)⋂(A∪C)

​

A

B

C

Lösung: https://www.wolframalpha.com/input/?i=A%E2%88%AA%28B%E2%8B%82C%29+%3D+%28A%E2%88%AAB%29%E2%8B%82%28A%E2%88%AAC%29+ �

Christian Spannagel. Beweis mit Venn-Diagrammen. https://youtu.be/an7PtSAi1dU?si=06KC3DiuA9T121RR

Abgrenzung von Begriffen

Liste … eine Liste ist eine geordnete Sammlung von beliebig � vielen Elementen. [10, 2, 2, 3, 56, 3, 3, 3, 10]

Sequenz … eine Sequenz ist eine geordnete Sammlung von � beliebig vielen Elementen, die meistens auf eine � endliche Größe beschränkt sind. [1, 2, 3, 4]

Tupel … eine geordnete Sammlung von homogenen Elementen � endlicher Anzahl. {name: “Christopher”, age:”30”}��Menge … ungeordnete Sammlung von unterschiedlichen Objekten� myset = {"apple", "banana", "cherry"}

http://gdi.ist.tugraz.at/skriptum.pdf

Abfragesprachen und Mengen

Das Ergebnis einer Abfrage (Query) ist eine Teilmenge des zugrundeliegenden Informationsbestandes. Man spricht daher auch von einer Filterung der Daten.

Es existieren Mengenoperationen in Abfragesprachen wie SQL, SPARQL etc.

https://glossar.hs-augsburg.de/Mengenoperatoren_in_SQL