MediaWiki - User contributions [en]

Funktionen: Definition, Notation & Beispiele

2025-10-27T09:03:32Z

Bfh-sts: Created page with "= Funktionen: Definition, Notation & Beispiele = Diese Seite führt den Funktionsbegriff (Abbildung) formal ein, klärt die Bezeichnungen und zeigt zentrale Beispiele – auch ausserhalb von ℝ. == Definition (Abbildung) == Seien A und B Mengen. Eine Funktion (Abbildung) f : A → B ist eine Vorschrift, die jedem Element x ∈ A genau ein Element f(x) ∈ B zuordnet. Wesentliche Punkte: * Eindeutigkeit: Zu jedem x ∈ A gibt es genau ein Bild f(x). * Totalität: Je..."

= Funktionen: Definition, Notation & Beispiele =
Diese Seite führt den Funktionsbegriff (Abbildung) formal ein, klärt die Bezeichnungen und zeigt zentrale Beispiele – auch ausserhalb von ℝ.

== Definition (Abbildung) ==
Seien A und B Mengen. Eine Funktion (Abbildung)
f : A → B
ist eine Vorschrift, die jedem Element x ∈ A genau ein Element f(x) ∈ B zuordnet.

Wesentliche Punkte:
* Eindeutigkeit: Zu jedem x ∈ A gibt es genau ein Bild f(x).
* Totalität: Jedes x ∈ A wird abgebildet (kein Element bleibt „ohne Bild“).

== Bezeichnungen und Notation ==
* f : A → B, x ↦ f(x)
* Definitionsbereich (Domain): A
* Zielbereich (Codomain): B
* Bild/Wertemenge (Image): Im(f) = f(A) = { f(x) : x ∈ A } ⊆ B
* Bild eines Elements: y = f(x)
* Urbild von y ∈ B: jedes x ∈ A mit f(x) = y (kann kein, ein oder mehrere Urbilder haben)
* In y = f(x) heisst y abhängige, x unabhängige Variable.

== Was ist *keine* Funktion? ==
Ein Zuordnungsschema g : A → B ist keine Funktion, wenn
* ein x ∈ A mehreren y ∈ B zugeordnet wird (Verstoss gegen Eindeutigkeit), oder
* ein x ∈ A gar keinem y ∈ B zugeordnet wird (Verstoss gegen Totalität).

== Beispiele ==
; (a) Quadratische Funktion
: A = B = ℝ, f(x) = x². Bild: Im(f) = ℝ⁺₀.
; (b) Anzahl der Primfaktoren
: A = ℕ \ {1}, B = ℕ, f(n) = Anzahl der Primfaktoren von n (mit Vielfachheiten).
: f(6)=2 (2·3), f(20)=3 (2·2·5), f(23 456 789)=1 (Primzahl).
; (c) Länge einer Zeichenkette
: A = {alle Strings}, B = ℕ₀, f(x) = Länge(x). Beispiel: f(„23x4a“) = 5.
; (d) Stückweise definierte Funktion
: f(x) = { 2x−4 für x ≥ 3; |x| für −2 < x < 3; 1+x für x ≤ −2 } mit A = ℝ.
: f(5)=6, f(−1)=1, f(−7)=−6.
; (e) Logischer Ausdruck als Funktion
: A = {W,F}³, B = {W,F}, f(X,Y,Z) = X ∧ (Y ∨ ¬Z).
: Beispiel: f(W,F,W) = F.

== Graph einer Funktion (Mengenauffassung) ==
Für f : A → B ist der Graph
G(f) = { (x, f(x)) : x ∈ A } ⊂ A × B.
Für reellwertige Funktionen f : ℝ → ℝ ist das der übliche Graph in der xy-Ebene.

== Reellwertige Funktionen einer reellen Variablen ==
In der Analysis betrachtet man vor allem f : ℝ → ℝ (oder Teilmengen davon).
Dann sind x, y reelle Zahlen und der Graph ist eine Kurve in der Ebene.

== Häufige Stolpersteine ==
* „Ein x mit zwei Pfeilen zu verschiedenen y“ → keine Funktion.
* Bildmenge Im(f) ist i. Allg. nicht gleich dem Zielbereich B.
* Urbilder können mehrfach sein (nicht-injektive Funktionen).

== Kurzer Blick voraus ==
Spezielle Eigenschaften wie Injektivität, Surjektivität, Bijektivität, die Komposition g∘f sowie die Umkehrfunktion f⁻¹ werden auf eigenen Seiten behandelt.

[[Category:Diskrete Mathematik I (BZG1155pa) 25/26]]

Category:Functions (Funktionen)

2025-10-27T08:45:45Z

Bfh-sts:

= Funktionen (Abbildungen): Überblick =
Diese Übersichtsseite führt in den Begriff der Funktion (Abbildung) ein und verlinkt auf die Detailseiten: Definition & Notation, Graph, Injektivität/Surjektivität/Bijektivität, Komposition und Umkehrfunktion. Die Beispiele orientieren sich an den Inhalten der Vorlesung „Diskrete Mathematik I (BZG1155pa) 25/26“.

== Was ist eine Funktion? ==
Eine Funktion (Abbildung) ordnet jedem Element x einer Menge A genau ein Element f(x) einer Menge B zu.
Notation:
f : A → B, x ↦ f(x)

* A heisst Definitionsbereich.
* B heisst Zielbereich (Codomain).
* Das Bild (Image) ist f(A) = { f(x) : x ∈ A } ⊆ B.
* y = f(x) heisst Bild von x; x heisst Urbild von y.

Beispiele:
* Flächeninhalt eines Kreises: A(r) = π r², r > 0
* Länge einer Zeichenkette: len("23x4a") = 5
* Stückweise definierte Funktion:
f(x) = { 2x−4 für x ≥ 3; |x| für −2 < x < 3; 1+x für x ≤ −2 }

== Wichtige Spezialfunktionen ==
* Abrundungsfunktion (floor): ⌊x⌋ = grösste ganze Zahl ≤ x
* Aufrundungsfunktion (ceiling): ⌈x⌉ = kleinste ganze Zahl ≥ x

== Weiterführende Seiten ==
* [[Funktionen: Definition, Notation & Beispiele]]
* [[Graph einer Funktion]]
* [[Injektiv, Surjektiv, Bijektiv]]
* [[Komposition (Verkettung) von Funktionen]]
* [[Umkehrfunktion (Inverse Abbildung)]]
* [[Spezielle Funktionen: Floor ⌊·⌋ und Ceiling ⌈·⌉]]

== Hinweise zur Praxis ==
* Bei reellwertigen Funktionen f : ℝ → ℝ ist y = f(x) eine Kurve in der xy-Ebene.
* Das Bild f(A) unterscheidet sich i. Allg. vom Zielbereich B.
* Ein y ∈ B kann kein, ein oder mehrere Urbilder haben (abhängig von f).

[[Category:Diskrete Mathematik I (BZG1155pa) 25/26]]

Category:Functions (Funktionen)

2025-10-27T08:45:19Z

Bfh-sts: Created page with "= Funktionen (Abbildungen): Überblick = Diese Übersichtsseite führt in den Begriff der Funktion (Abbildung) ein und verlinkt auf die Detailseiten: Definition & Notation, Graph, Injektivität/Surjektivität/Bijektivität, Komposition und Umkehrfunktion. Die Beispiele orientieren sich an den Inhalten der Vorlesung „Diskrete Mathematik I (BZG1155pa) 25/26“. == Was ist eine Funktion? == Eine Funktion (Abbildung) ordnet jedem Element x einer Menge A **genau ein** Elem..."

= Funktionen (Abbildungen): Überblick =
Diese Übersichtsseite führt in den Begriff der Funktion (Abbildung) ein und verlinkt auf die Detailseiten: Definition & Notation, Graph, Injektivität/Surjektivität/Bijektivität, Komposition und Umkehrfunktion. Die Beispiele orientieren sich an den Inhalten der Vorlesung „Diskrete Mathematik I (BZG1155pa) 25/26“.

== Was ist eine Funktion? ==
Eine Funktion (Abbildung) ordnet jedem Element x einer Menge A **genau ein** Element f(x) einer Menge B zu.
Notation:
f : A → B, x ↦ f(x)

* A heißt **Definitionsbereich**.
* B heißt **Zielbereich** (Codomain).
* Das **Bild** (Image) ist f(A) = { f(x) : x ∈ A } ⊆ B.
* y = f(x) heißt **Bild** von x; x heißt **Urbild** von y.

Beispiele:
* Flächeninhalt eines Kreises: A(r) = π r², r > 0
* Länge einer Zeichenkette: len("23x4a") = 5
* Stückweise definierte Funktion:
f(x) = { 2x−4 für x ≥ 3; |x| für −2 < x < 3; 1+x für x ≤ −2 }

== Wichtige Spezialfunktionen ==
* **Abrundungsfunktion (floor)**: ⌊x⌋ = größte ganze Zahl ≤ x
* **Aufrundungsfunktion (ceiling)**: ⌈x⌉ = kleinste ganze Zahl ≥ x

== Weiterführende Seiten ==
* [[Funktionen: Definition, Notation & Beispiele]]
* [[Graph einer Funktion]]
* [[Injektiv, Surjektiv, Bijektiv]]
* [[Komposition (Verkettung) von Funktionen]]
* [[Umkehrfunktion (Inverse Abbildung)]]
* [[Spezielle Funktionen: Floor ⌊·⌋ und Ceiling ⌈·⌉]]

== Hinweise zur Praxis ==
* Bei reellwertigen Funktionen f : ℝ → ℝ ist y = f(x) eine Kurve in der xy-Ebene.
* Das Bild f(A) unterscheidet sich i. Allg. vom Zielbereich B.
* Ein y ∈ B kann kein, ein oder mehrere Urbilder haben (abhängig von f).

[[Category:Diskrete Mathematik I (BZG1155pa) 25/26]]

Category:Diskrete Mathematik I (BZG1155pa) 25/26

2025-10-27T08:45:12Z

Bfh-sts: /* Topics */

= Overview =
This is the category of the BFH module Diskrete Mathematik I (BZG1155pa) 25/26.

= Topics =
* [[:Category: Propositional logic (Aussagenlogik)‎]]
* [[:Category: Set Theory (Mengenlehre)‎]]
* [[:Category: Functions (Funktionen)]]

== Propositional logic - Exercises ==
* [[Exercises - 01 Kontrollaufgaben]]
* [[Exercises - 02 Kontrollaufgaben]]

[[Category:Sidebar]]

Mengenlehre: Überblick & Notation

2025-10-27T08:22:04Z

Bfh-sts: /* Wichtige Symbole */

= Mengenlehre: Überblick & Bedeutung =
Die Mengenlehre ist ein grundlegendes Teilgebiet der Mathematik, das von Georg Cantor (1845–1918) im 19. Jahrhundert entwickelt wurde.
Sie bildet das Fundament nahezu aller modernen mathematischen Disziplinen.
Jede mathematische Struktur – von Zahlen über Funktionen bis zu geometrischen Objekten – kann in der Sprache der Mengenlehre formuliert werden.

== Ursprung und Idee ==
Cantor definierte den Begriff der Menge folgendermassen:
> Unter einer Menge verstehen wir jede Zusammenfassung von bestimmten, wohlunterschiedlichen Objekten unserer Anschauung oder unseres Denkens (welche Elemente der Menge genannt werden) zu einem Ganzen.

Diese Definition erlaubt es, sowohl konkrete als auch abstrakte Objekte als Elemente zu betrachten.
Beispiele für Mengen:
* Die Menge der Planeten im Sonnensystem
* Die Menge der geraden natürlichen Zahlen grösser als 2, die sich als Summe zweier Primzahlen schreiben lassen
* Die Menge aller reellen Zahlen x mit x > 5
* Die Menge der Studierenden an der BFH-TI Biel

== Notation ==
* Mengen werden mit Grossbuchstaben bezeichnet (A, B, C, …).
* Elemente werden mit Kleinbuchstaben bezeichnet (a, b, c, …).
* Die Aussage „a ist Element von A“ schreibt man als:
a ∈ A
Die Negation lautet:
a ∉ A

Eine Menge ist durch ihre Elemente vollständig bestimmt.
Dieses Prinzip wird als Extensionalitätsaxiom bezeichnet:
> Zwei Mengen A und B sind genau dann gleich, wenn sie dieselben Elemente enthalten.

Formal:
A = B ⇔ ∀x: (x ∈ A ⇔ x ∈ B)

== Arten der Mengendefinition ==
Es gibt zwei grundlegende Arten, Mengen zu definieren:

=== 1. Aufzählende (explizite) Definition ===
Alle Elemente werden direkt aufgelistet:
A = {a, b, x, y, z}
B = {1, 2, 3, 4, 5}

=== 2. Beschreibende (intensionale) Definition ===
Die Elemente werden durch eine Eigenschaft charakterisiert:
B = {n : n ∈ ℤ ∧ n > 5}
„B ist die Menge aller ganzen Zahlen n, für die n > 5 gilt.“

Der Doppelpunkt „:“ bedeutet „mit der Eigenschaft“ oder „so dass“.

== Wichtige Symbole ==
<syntaxhighlight lang='text'>
| Symbol | Bedeutung |
|--------|-------------------------|
| ∈ | ist Element von |
| ∉ | ist kein Element von |
| ⊆ | ist Teilmenge von |
| ⊂ | ist echte Teilmenge von |
| ∅ | leere Menge |
| U | Universalmenge |
</syntaxhighlight>

== Leere Menge und Universalmenge ==
* Leere Menge (∅): enthält keine Elemente.
∅ = {}
* Universalmenge (U): enthält alle in einem Kontext betrachteten Objekte.
Beispiele:
* In der Geometrie: alle Punkte der Ebene
* In der Analysis: alle reellen Zahlen

== Bedeutung in der Informatik ==
Mengen sind auch in der Informatik zentral:
* zur Beschreibung von Zustandsräumen
* zur Definition von Datenmengen und Relationen
* für logische Operationen (UND, ODER, NICHT) in Boolescher Algebra
* als Grundlage für Datenbanktheorie und Mengenoperationen (SELECT, UNION, INTERSECT)

== Zusammenfassung ==
* Die Mengenlehre ist das Fundament der Mathematik.
* Mengen sind Sammlungen von klar unterscheidbaren Objekten.
* Die Mitgliedschaft (∈) ist das zentrale Konzept.
* Mengen können durch Aufzählung oder Eigenschaft definiert werden.
* Leere Menge (∅) und Universalmenge (U) sind wichtige Spezialfälle.

[[Category:Set Theory (Mengenlehre)]]

Endliche Mengen & Einschluss-Ausschluss-Prinzip

2025-10-27T08:14:55Z

Bfh-sts: /* Beispiel */

= Endliche Mengen und das Einschluss-Ausschluss-Prinzip =
Viele praktische Probleme befassen sich mit endlichen Mengen, also Mengen mit abzählbarer Anzahl von Elementen.
Für solche Mengen spielt das Zählen von Elementen und Überschneidungen eine zentrale Rolle.

== Endliche und unendliche Mengen ==
Eine Menge heisst endlich, wenn sie genau *m* verschiedene Elemente enthält, wobei *m* eine natürliche Zahl ist.
Sonst heisst sie unendlich.

Beispiele:
* ∅ → endlich, da keine Elemente
* Alphabet = {A, B, …, Z} → endlich
* ℕ = {1, 2, 3, 4, …} → unendlich

Die Anzahl der Elemente einer endlichen Menge A wird mit |A| bezeichnet.

Beispiel:
A = {1, 2, 3, 4} → |A| = 4

== Vereinigung endlicher Mengen ==
Sind A und B endlich, so ist auch A ∪ B endlich.
Dabei gilt die Grundformel:

|A ∪ B| = |A| + |B| − |A ∩ B|

Diese Formel korrigiert die doppelte Zählung der Schnittmenge.

=== Beispiel ===
* A = {1, 2, 3, 4}, B = {3, 4, 5, 6}
* |A| = 4, |B| = 4, |A ∩ B| = 2
* → |A ∪ B| = 4 + 4 − 2 = 6
* A ∪ B = {1, 2, 3, 4, 5, 6}

== Herleitung der Formel ==
Die Mengen A und B können als drei disjunkte Teilmengen betrachtet werden:
* A \ (A ∩ B)
* A ∩ B
* B \ (A ∩ B)

Da diese drei Mengen keine Überschneidung haben, gilt:
|A ∪ B| = |A \ (A ∩ B)| + |A ∩ B| + |B \ (A ∩ B)|

Daraus folgt:
|A ∪ B| = |A| + |B| − |A ∩ B|

== Erweiterung auf drei Mengen ==
Für drei endliche Mengen A, B, C gilt die Einschluss-Ausschluss-Formel:

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

Diese Formel berücksichtigt alle Überschneidungen korrekt:
* Einfache Mengen: +
* Doppelte Schnittmengen: −
* Dreifache Schnittmenge: +

== Erweiterung auf vier Mengen ==
Für A, B, C, D gilt:

|A ∪ B ∪ C ∪ D| =
|A| + |B| + |C| + |D|
− (|A ∩ B| + |A ∩ C| + |A ∩ D| + |B ∩ C| + |B ∩ D| + |C ∩ D|)
+ (|A ∩ B ∩ C| + |A ∩ B ∩ D| + |A ∩ C ∩ D| + |B ∩ C ∩ D|)
− |A ∩ B ∩ C ∩ D|

== Beispiel: Anwendung auf Studierende ==
An einer Universität studieren 2’504 Studierende Informatik.
Davon belegen:
* 1’876 Java
* 999 C
* 345 Prolog
* 876 sowohl Java als auch C
* 231 C und Prolog
* 290 Java und Prolog
* 189 alle drei Kurse

(a) Wie viele Studierende belegen keinen der drei Kurse?

|U| = 2’504
|A ∪ B ∪ C| = 1’876 + 999 + 345 − 876 − 231 − 290 + 189 = 2’012
→ Studierende ohne Kurs = 2’504 − 2’012 = 492

(b) Wie viele belegen genau einen Kurs?

= |A| + |B| + |C| − 2·(|A ∩ B| + |A ∩ C| + |B ∩ C|) + 3·|A ∩ B ∩ C|
= 1’876 + 999 + 345 − 2·(876 + 231 + 290) + 3·189 = 1’002

== Bedeutung ==
Das Einschluss-Ausschluss-Prinzip ist ein zentrales Werkzeug:
* zur Bestimmung der Kardinalität von Vereinigungen
* in Kombinatorik, Statistik und Wahrscheinlichkeitstheorie
* für logische Vereinfachungen in der Informatik (z. B. Boolesche Algebra)

== Zusammenfassung ==
* Eine Menge ist endlich, wenn sie eine abzählbare Anzahl von Elementen hat.
* |A ∪ B| = |A| + |B| − |A ∩ B| korrigiert doppelte Zählung.
* Das Einschluss-Ausschluss-Prinzip erweitert diese Idee auf mehrere Mengen.
* In der Informatik hilft es beim Zählen von Zuständen, Kombinationen und logischen Fällen.

[[Category:Set Theory (Mengenlehre)]]

Endliche Mengen & Einschluss-Ausschluss-Prinzip

2025-10-27T08:14:11Z

Bfh-sts:

= Endliche Mengen und das Einschluss-Ausschluss-Prinzip =
Viele praktische Probleme befassen sich mit endlichen Mengen, also Mengen mit abzählbarer Anzahl von Elementen.
Für solche Mengen spielt das Zählen von Elementen und Überschneidungen eine zentrale Rolle.

== Endliche und unendliche Mengen ==
Eine Menge heisst endlich, wenn sie genau *m* verschiedene Elemente enthält, wobei *m* eine natürliche Zahl ist.
Sonst heisst sie unendlich.

Beispiele:
* ∅ → endlich, da keine Elemente
* Alphabet = {A, B, …, Z} → endlich
* ℕ = {1, 2, 3, 4, …} → unendlich

Die Anzahl der Elemente einer endlichen Menge A wird mit |A| bezeichnet.

Beispiel:
A = {1, 2, 3, 4} → |A| = 4

== Vereinigung endlicher Mengen ==
Sind A und B endlich, so ist auch A ∪ B endlich.
Dabei gilt die Grundformel:

|A ∪ B| = |A| + |B| − |A ∩ B|

Diese Formel korrigiert die doppelte Zählung der Schnittmenge.

=== Beispiel ===
A = {1, 2, 3, 4}, B = {3, 4, 5, 6}
|A| = 4, |B| = 4, |A ∩ B| = 2
→ |A ∪ B| = 4 + 4 − 2 = 6
A ∪ B = {1, 2, 3, 4, 5, 6}

== Herleitung der Formel ==
Die Mengen A und B können als drei disjunkte Teilmengen betrachtet werden:
* A \ (A ∩ B)
* A ∩ B
* B \ (A ∩ B)

Da diese drei Mengen keine Überschneidung haben, gilt:
|A ∪ B| = |A \ (A ∩ B)| + |A ∩ B| + |B \ (A ∩ B)|

Daraus folgt:
|A ∪ B| = |A| + |B| − |A ∩ B|

== Erweiterung auf drei Mengen ==
Für drei endliche Mengen A, B, C gilt die Einschluss-Ausschluss-Formel:

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

Diese Formel berücksichtigt alle Überschneidungen korrekt:
* Einfache Mengen: +
* Doppelte Schnittmengen: −
* Dreifache Schnittmenge: +

== Erweiterung auf vier Mengen ==
Für A, B, C, D gilt:

|A ∪ B ∪ C ∪ D| =
|A| + |B| + |C| + |D|
− (|A ∩ B| + |A ∩ C| + |A ∩ D| + |B ∩ C| + |B ∩ D| + |C ∩ D|)
+ (|A ∩ B ∩ C| + |A ∩ B ∩ D| + |A ∩ C ∩ D| + |B ∩ C ∩ D|)
− |A ∩ B ∩ C ∩ D|

== Beispiel: Anwendung auf Studierende ==
An einer Universität studieren 2’504 Studierende Informatik.
Davon belegen:
* 1’876 Java
* 999 C
* 345 Prolog
* 876 sowohl Java als auch C
* 231 C und Prolog
* 290 Java und Prolog
* 189 alle drei Kurse

(a) Wie viele Studierende belegen keinen der drei Kurse?

|U| = 2’504
|A ∪ B ∪ C| = 1’876 + 999 + 345 − 876 − 231 − 290 + 189 = 2’012
→ Studierende ohne Kurs = 2’504 − 2’012 = 492

(b) Wie viele belegen genau einen Kurs?

= |A| + |B| + |C| − 2·(|A ∩ B| + |A ∩ C| + |B ∩ C|) + 3·|A ∩ B ∩ C|
= 1’876 + 999 + 345 − 2·(876 + 231 + 290) + 3·189 = 1’002

== Bedeutung ==
Das Einschluss-Ausschluss-Prinzip ist ein zentrales Werkzeug:
* zur Bestimmung der Kardinalität von Vereinigungen
* in Kombinatorik, Statistik und Wahrscheinlichkeitstheorie
* für logische Vereinfachungen in der Informatik (z. B. Boolesche Algebra)

== Zusammenfassung ==
* Eine Menge ist endlich, wenn sie eine abzählbare Anzahl von Elementen hat.
* |A ∪ B| = |A| + |B| − |A ∩ B| korrigiert doppelte Zählung.
* Das Einschluss-Ausschluss-Prinzip erweitert diese Idee auf mehrere Mengen.
* In der Informatik hilft es beim Zählen von Zuständen, Kombinationen und logischen Fällen.

[[Category:Set Theory (Mengenlehre)]]

Geordnete Paare, n-Tupel & kartesische Produkte

2025-10-27T08:13:09Z

Bfh-sts:

= Geordnete Paare, n-Tupel und kartesische Produkte =
In der Mengenlehre spielt die Reihenfolge der Elemente normalerweise keine Rolle.
Doch in vielen Anwendungen – etwa bei Funktionen oder Datenstrukturen – ist sie entscheidend.
Dazu dienen geordnete Paare und Tupel.

== Geordnete Paare ==
Ein geordnetes Paar besteht aus zwei Elementen, bei denen die Reihenfolge eine Rolle spielt.
Notation:
(a, b)

Das erste Element ist a, das zweite ist b.
Zwei geordnete Paare (a, b) und (c, d) sind gleich, genau dann, wenn gilt:
a = c und b = d

Beispiel:
* (1, 2) ≠ (2, 1)
* (x, y) = (x, y)
* (a, b) ≠ (b, a), sofern a ≠ b

== Kartesisches Produkt ==
Das kartesische Produkt zweier Mengen A und B ist die Menge aller geordneten Paare (x, y) mit x ∈ A und y ∈ B.

Formale Definition:
A × B := {(x, y) : x ∈ A ∧ y ∈ B}

Beispiel:
A = {1, 2}
B = {a, b, c}

Dann gilt:
A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}
B × A = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}
A² = A × A = {(1, 1), (1, 2), (2, 1), (2, 2)}

== Anzahl der Elemente ==
Wenn A und B endlich sind, gilt:
|A × B| = |A| · |B|

Beispiel:
A = {1, 2, 3}, B = {a, b}
|A × B| = 3 · 2 = 6

== n-Tupel ==
Ein n-Tupel ist eine geordnete Liste von n Elementen:
(a₁, a₂, …, aₙ)

Die Reihenfolge der Elemente ist wesentlich.

Zwei n-Tupel (a₁, a₂, …, aₙ) und (b₁, b₂, …, bₙ) sind gleich, wenn:
a₁ = b₁ ∧ a₂ = b₂ ∧ … ∧ aₙ = bₙ

Beispiele:
* (a, b, c) → Tripel
* (a, b, c, d) → Quadrupel

== Kartesisches Produkt mehrerer Mengen ==
Für n Mengen A₁, A₂, …, Aₙ gilt:
A₁ × A₂ × … × Aₙ = {(a₁, a₂, …, aₙ) : aᵢ ∈ Aᵢ für alle i}

Beispiel:
A = {a, b}, B = {x}, C = {1, 2, 3}

A × B × C = {
(a, x, 1), (a, x, 2), (a, x, 3),
(b, x, 1), (b, x, 2), (b, x, 3)
}

== Kombinatorische Überlegungen ==
Wenn |A₁| = n₁, |A₂| = n₂, …, |Aₙ| = nₙ, dann gilt:
|A₁ × A₂ × … × Aₙ| = n₁ · n₂ · … · nₙ

Beispiel:
Drei Mengen:
* A = {rot, blau}
* B = {rund, eckig}
* C = {klein, gross}

→ |A × B × C| = 2 · 2 · 2 = 8 Kombinationen.

== Variation der Elemente ==
Bei einer Menge aus n Zahlen (1, 2, …, n):
* Wenn jede Zahl nur einmal vorkommen darf → n! mögliche Tupel (Permutationen)
* Wenn jede Zahl beliebig oft vorkommen darf → nⁿ mögliche Tupel

== Anwendung ==
Kartesische Produkte und Tupel bilden die Grundlage für:
* Funktionen: eine Funktion ist eine Teilmenge von A × B
* Datenbanken: Tabellenzeilen entsprechen n-Tupeln
* Vektorräume: Elemente sind n-Tupel reeller Zahlen

== Zusammenfassung ==
* Reihenfolge spielt bei geordneten Paaren und Tupeln eine Rolle.
* Das kartesische Produkt A × B kombiniert alle möglichen Paare (x, y).
* |A × B| = |A| · |B| bei endlichen Mengen.
* Das Konzept erweitert sich auf n-Tupel.
* Anwendungen: Funktionen, Datenstrukturen, Relationen, Kombinatorik.

[[Category:Set Theory (Mengenlehre)]]

Mengensysteme, Potenzmenge & Partitionen

2025-10-27T08:12:25Z

Bfh-sts:

= Mengensysteme, Potenzmenge und Partitionen =
Neben einzelnen Mengen betrachtet man oft Systeme von Mengen – also Mengen, deren Elemente wiederum Mengen sind.
Dazu gehören wichtige Begriffe wie Potenzmenge und Partition.

== Mengensystem ==
Eine Menge von Mengen heisst ein Mengensystem.
Beispiel:
S = { {1, 2}, {3, 4}, {5} }

Jedes Element von S ist selbst eine Menge.

== Potenzmenge ==
Die Potenzmenge einer Menge S ist die Menge aller Teilmengen von S.
Notation:
P(S) = {A : A ⊆ S}

Beispiel:
Sei S = {1, 2}
Dann gilt:
P(S) = {∅, {1}, {2}, {1, 2}}

Beispiel:
* A = ∅ → P(A) = {∅}
* B = {a} → P(B) = {∅, {a}}
* C = {a, b} → P(C) = {∅, {a}, {b}, {a, b}}

Allgemein gilt:
Eine Menge mit n Elementen besitzt 2ⁿ Teilmengen.

Beispiel:
D = {a, b, c, d} → |P(D)| = 2⁴ = 16

== Beispielaufgaben ==
1. Bestimme die Potenzmenge von E = {a, b, c, d}.
→ 16 Teilmengen
2. Wieviele Teilmengen besitzt eine Menge mit 5 Elementen?
→ 2⁵ = 32

== Partition ==
Eine Partition einer Menge S ist eine Aufteilung von S in nicht-leere, disjunkte Teilmengen, deren Vereinigung S ergibt.

Formal:
Eine Familie {Aᵢ} von Teilmengen von S ist eine Partition, wenn gilt:
1. Aᵢ ≠ ∅ für alle i
2. ⋃ Aᵢ = S
3. Aᵢ ∩ Aⱼ = ∅ für alle i ≠ j

Beispiel:
S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

(a) {∅, {1,2}, {3,4,5}, {6,7,8,9,10}} → keine Partition, da ∅ enthalten
(b) {{1,2,3,4}, {4,5,6}, {7,8,9,10}} → keine Partition, da sich {1,2,3,4} und {4,5,6} überschneiden
(c) {{2,3,4,5}, {6,7,8}, {9,10}} → Partition von {2,…,10}, nicht von S
(d) {{1,2,3}, {4,5,6}, {7,8,9,10}} → gültige Partition von S

== Zusammenhang zwischen Potenzmenge und Partition ==
* Die Potenzmenge enthält alle möglichen Kombinationen von Teilmengen.
* Eine Partition wählt aus diesen Teilmengen eine besondere Kombination, bei der:
- keine Schnittmenge entsteht
- die Vereinigung wieder die Ausgangsmenge ergibt

== Visualisierung ==
Ein Venn-Diagramm kann Partitionen als nicht überlappende Flächen innerhalb der Universalmenge darstellen.
Jede Teilmenge repräsentiert ein disjunktes „Teilgebiet“.

== Zusammenfassung ==
* Mengensystem: Menge von Mengen.
* Potenzmenge P(S): Menge aller Teilmengen von S, mit |P(S)| = 2ⁿ.
* Partition: disjunkte, nicht-leere Teilmengen, deren Vereinigung S ergibt.
* Potenzmengen und Partitionen sind zentrale Konzepte in Kombinatorik und Wahrscheinlichkeitsrechnung.

[[Category:Set Theory (Mengenlehre)]]

Mengenalgebra & Dualität: Gesetze und de Morgan

2025-10-27T08:12:03Z

Bfh-sts:

= Mengenalgebra und Dualität =
Die in der Mengenlehre definierten Operationen (Vereinigung, Durchschnitt, Komplement, Differenz) folgen bestimmten algebraischen Gesetzen.
Diese Gesetze erlauben es, Ausdrücke zu vereinfachen oder zu beweisen, dass zwei Mengenoperationen äquivalent sind.

== Grundlegende Gesetze der Mengenalgebra ==
Für beliebige Mengen A, B, C und die Universalmenge U gelten folgende Gesetze:

=== 1. Idempotenz ===
A ∪ A = A
A ∩ A = A

Das Zusammenfassen oder Schneiden einer Menge mit sich selbst ändert nichts.

=== 2. Assoziativgesetz ===
(A ∪ B) ∪ C = A ∪ (B ∪ C)
(A ∩ B) ∩ C = A ∩ (B ∩ C)

Die Reihenfolge der Ausführung spielt keine Rolle.

=== 3. Kommutativgesetz ===
A ∪ B = B ∪ A
A ∩ B = B ∩ A

Die Reihenfolge der Mengen kann vertauscht werden.

=== 4. Distributivgesetz ===
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

Dies erlaubt, Ausdrücke zu „verteilen“, ähnlich wie beim Distributivgesetz der Algebra.

=== 5. Identitätsgesetz ===
A ∪ ∅ = A
A ∩ U = A

∅ und U verhalten sich wie 0 und 1 in der Arithmetik.

=== 6. Null- und Einheitsgesetz ===
A ∪ U = U
A ∩ ∅ = ∅

Alles mit der Universalmenge vereinigt ergibt U;
alles mit der leeren Menge geschnitten ergibt ∅.

=== 7. Gesetz vom doppelten Komplement ===
(Aᶜ)ᶜ = A

Das Komplement des Komplements ergibt wieder die ursprüngliche Menge.

=== 8. Komplementgesetze ===
A ∪ Aᶜ = U
A ∩ Aᶜ = ∅

Eine Menge und ihr Komplement decken die Universalmenge vollständig ab, ohne sich zu überschneiden.

=== 9. Komplemente der Universal- und Leermenge ===
Uᶜ = ∅
∅ᶜ = U

=== 10. de Morgan’sche Gesetze ===
(A ∪ B)ᶜ = Aᶜ ∩ Bᶜ
(A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

Diese sind besonders wichtig, da sie eine enge Verbindung zur Aussagenlogik zeigen:
* Das Komplement einer Vereinigung ist der Durchschnitt der Komplemente.
* Das Komplement eines Durchschnitts ist die Vereinigung der Komplemente.

== Beispiel: Beweis des de Morgan Gesetzes ==
Beweise (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ mithilfe der Logik:

<syntaxhighlight lang='text'>
| Aussage | Logisches Pendant |
|--------------|------------------------|
| x ∈ (A ∩ B)ᶜ | ¬(x ∈ A ∧ x ∈ B) |
| | ⇔ (¬x ∈ A) ∨ (¬x ∈ B) |
| | ⇔ x ∈ Aᶜ ∨ x ∈ Bᶜ |
| ⇒ | x ∈ (Aᶜ ∪ Bᶜ) |
</syntaxhighlight>
Daraus folgt: (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

== Dualitätsprinzip ==
Die Gesetze der Mengenlehre treten paarweise auf.
Tauscht man überall
* ∪ ↔ ∩
* U ↔ ∅

so erhält man den dualen Ausdruck.

Beispiel:
* Gesetz A ∪ ∅ = A hat als Dual A ∩ U = A
* de Morgan’s Gesetz (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ hat als Dual (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

Dieses Prinzip zeigt die symmetrische Struktur der Mengenoperationen.

== Visualisierung ==
Venn-Diagramme verdeutlichen diese Gesetze grafisch:
* Die Vereinigungen und Durchschnitte entsprechen farblich markierten Bereichen.
* Komplementbereiche sind die Flächen ausserhalb der betrachteten Menge.

== Zusammenfassung ==
* Mengenoperationen folgen festen algebraischen Gesetzen.
* Diese Gesetze entsprechen den Regeln der Aussagenlogik.
* Das Dualitätsprinzip erlaubt, aus jedem Gesetz sein komplementäres Gegenstück zu bilden.
* Die de Morgan’schen Gesetze sind besonders zentral für logische und rechnerische Anwendungen.

[[Category:Set Theory (Mengenlehre)]]

Mengenalgebra & Dualität: Gesetze und de Morgan

2025-10-27T08:11:36Z

Bfh-sts: /* Beispiel: Beweis des de Morgan Gesetzes */

= Mengenalgebra und Dualität =
Die in der Mengenlehre definierten Operationen (Vereinigung, Durchschnitt, Komplement, Differenz) folgen bestimmten **algebraischen Gesetzen**.
Diese Gesetze erlauben es, Ausdrücke zu vereinfachen oder zu beweisen, dass zwei Mengenoperationen äquivalent sind.

== Grundlegende Gesetze der Mengenalgebra ==
Für beliebige Mengen A, B, C und die Universalmenge U gelten folgende Gesetze:

=== 1. Idempotenz ===
A ∪ A = A
A ∩ A = A

Das Zusammenfassen oder Schneiden einer Menge mit sich selbst ändert nichts.

=== 2. Assoziativgesetz ===
(A ∪ B) ∪ C = A ∪ (B ∪ C)
(A ∩ B) ∩ C = A ∩ (B ∩ C)

Die Reihenfolge der Ausführung spielt keine Rolle.

=== 3. Kommutativgesetz ===
A ∪ B = B ∪ A
A ∩ B = B ∩ A

Die Reihenfolge der Mengen kann vertauscht werden.

=== 4. Distributivgesetz ===
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

Dies erlaubt, Ausdrücke zu „verteilen“, ähnlich wie beim Distributivgesetz der Algebra.

=== 5. Identitätsgesetz ===
A ∪ ∅ = A
A ∩ U = A

∅ und U verhalten sich wie 0 und 1 in der Arithmetik.

=== 6. Null- und Einheitsgesetz ===
A ∪ U = U
A ∩ ∅ = ∅

Alles mit der Universalmenge vereinigt ergibt U;
alles mit der leeren Menge geschnitten ergibt ∅.

=== 7. Gesetz vom doppelten Komplement ===
(Aᶜ)ᶜ = A

Das Komplement des Komplements ergibt wieder die ursprüngliche Menge.

=== 8. Komplementgesetze ===
A ∪ Aᶜ = U
A ∩ Aᶜ = ∅

Eine Menge und ihr Komplement decken die Universalmenge vollständig ab, ohne sich zu überschneiden.

=== 9. Komplemente der Universal- und Leermenge ===
Uᶜ = ∅
∅ᶜ = U

=== 10. de Morgan’sche Gesetze ===
(A ∪ B)ᶜ = Aᶜ ∩ Bᶜ
(A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

Diese sind besonders wichtig, da sie eine enge Verbindung zur Aussagenlogik zeigen:
* Das Komplement einer Vereinigung ist der Durchschnitt der Komplemente.
* Das Komplement eines Durchschnitts ist die Vereinigung der Komplemente.

== Beispiel: Beweis des de Morgan Gesetzes ==
Beweise (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ mithilfe der Logik:

<syntaxhighlight lang='text'>
| Aussage | Logisches Pendant |
|--------------|------------------------|
| x ∈ (A ∩ B)ᶜ | ¬(x ∈ A ∧ x ∈ B) |
| | ⇔ (¬x ∈ A) ∨ (¬x ∈ B) |
| | ⇔ x ∈ Aᶜ ∨ x ∈ Bᶜ |
| ⇒ | x ∈ (Aᶜ ∪ Bᶜ) |
</syntaxhighlight>
Daraus folgt: (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

== Dualitätsprinzip ==
Die Gesetze der Mengenlehre treten **paarweise** auf.
Tauscht man überall
* ∪ ↔ ∩
* U ↔ ∅

so erhält man den **dualen Ausdruck**.

Beispiel:
* Gesetz A ∪ ∅ = A hat als Dual A ∩ U = A
* de Morgan’s Gesetz (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ hat als Dual (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

Dieses Prinzip zeigt die **symmetrische Struktur** der Mengenoperationen.

== Visualisierung ==
Venn-Diagramme verdeutlichen diese Gesetze grafisch:
* Die Vereinigungen und Durchschnitte entsprechen farblich markierten Bereichen.
* Komplementbereiche sind die Flächen ausserhalb der betrachteten Menge.

== Zusammenfassung ==
* Mengenoperationen folgen festen algebraischen Gesetzen.
* Diese Gesetze entsprechen den Regeln der Aussagenlogik.
* Das **Dualitätsprinzip** erlaubt, aus jedem Gesetz sein komplementäres Gegenstück zu bilden.
* Die **de Morgan’schen Gesetze** sind besonders zentral für logische und rechnerische Anwendungen.

[[Category:Set Theory (Mengenlehre)]]

Mengenalgebra & Dualität: Gesetze und de Morgan

2025-10-27T08:10:42Z

Bfh-sts:

= Mengenalgebra und Dualität =
Die in der Mengenlehre definierten Operationen (Vereinigung, Durchschnitt, Komplement, Differenz) folgen bestimmten **algebraischen Gesetzen**.
Diese Gesetze erlauben es, Ausdrücke zu vereinfachen oder zu beweisen, dass zwei Mengenoperationen äquivalent sind.

== Grundlegende Gesetze der Mengenalgebra ==
Für beliebige Mengen A, B, C und die Universalmenge U gelten folgende Gesetze:

=== 1. Idempotenz ===
A ∪ A = A
A ∩ A = A

Das Zusammenfassen oder Schneiden einer Menge mit sich selbst ändert nichts.

=== 2. Assoziativgesetz ===
(A ∪ B) ∪ C = A ∪ (B ∪ C)
(A ∩ B) ∩ C = A ∩ (B ∩ C)

Die Reihenfolge der Ausführung spielt keine Rolle.

=== 3. Kommutativgesetz ===
A ∪ B = B ∪ A
A ∩ B = B ∩ A

Die Reihenfolge der Mengen kann vertauscht werden.

=== 4. Distributivgesetz ===
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

Dies erlaubt, Ausdrücke zu „verteilen“, ähnlich wie beim Distributivgesetz der Algebra.

=== 5. Identitätsgesetz ===
A ∪ ∅ = A
A ∩ U = A

∅ und U verhalten sich wie 0 und 1 in der Arithmetik.

=== 6. Null- und Einheitsgesetz ===
A ∪ U = U
A ∩ ∅ = ∅

Alles mit der Universalmenge vereinigt ergibt U;
alles mit der leeren Menge geschnitten ergibt ∅.

=== 7. Gesetz vom doppelten Komplement ===
(Aᶜ)ᶜ = A

Das Komplement des Komplements ergibt wieder die ursprüngliche Menge.

=== 8. Komplementgesetze ===
A ∪ Aᶜ = U
A ∩ Aᶜ = ∅

Eine Menge und ihr Komplement decken die Universalmenge vollständig ab, ohne sich zu überschneiden.

=== 9. Komplemente der Universal- und Leermenge ===
Uᶜ = ∅
∅ᶜ = U

=== 10. de Morgan’sche Gesetze ===
(A ∪ B)ᶜ = Aᶜ ∩ Bᶜ
(A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

Diese sind besonders wichtig, da sie eine enge Verbindung zur Aussagenlogik zeigen:
* Das Komplement einer Vereinigung ist der Durchschnitt der Komplemente.
* Das Komplement eines Durchschnitts ist die Vereinigung der Komplemente.

== Beispiel: Beweis des de Morgan Gesetzes ==
Beweise (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ mithilfe der Logik:

| Aussage | Logisches Pendant |
|----------|--------------------|
| x ∈ (A ∩ B)ᶜ | ¬(x ∈ A ∧ x ∈ B) |
| | ⇔ (¬x ∈ A) ∨ (¬x ∈ B) |
| | ⇔ x ∈ Aᶜ ∨ x ∈ Bᶜ |
| ⇒ | x ∈ (Aᶜ ∪ Bᶜ) |

Daraus folgt: (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

== Dualitätsprinzip ==
Die Gesetze der Mengenlehre treten **paarweise** auf.
Tauscht man überall
* ∪ ↔ ∩
* U ↔ ∅

so erhält man den **dualen Ausdruck**.

Beispiel:
* Gesetz A ∪ ∅ = A hat als Dual A ∩ U = A
* de Morgan’s Gesetz (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ hat als Dual (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

Dieses Prinzip zeigt die **symmetrische Struktur** der Mengenoperationen.

== Visualisierung ==
Venn-Diagramme verdeutlichen diese Gesetze grafisch:
* Die Vereinigungen und Durchschnitte entsprechen farblich markierten Bereichen.
* Komplementbereiche sind die Flächen ausserhalb der betrachteten Menge.

== Zusammenfassung ==
* Mengenoperationen folgen festen algebraischen Gesetzen.
* Diese Gesetze entsprechen den Regeln der Aussagenlogik.
* Das **Dualitätsprinzip** erlaubt, aus jedem Gesetz sein komplementäres Gegenstück zu bilden.
* Die **de Morgan’schen Gesetze** sind besonders zentral für logische und rechnerische Anwendungen.

[[Category:Set Theory (Mengenlehre)]]

Vereinigung, Durchschnitt, Differenz und Komplement (inkl. Disjunktheit)

2025-10-27T08:10:19Z

Bfh-sts:

= Vereinigung, Durchschnitt, Differenz und Komplement =
In der Mengenlehre werden neue Mengen oft durch Operationen auf bestehenden Mengen gebildet.
Die wichtigsten sind Vereinigung, Durchschnitt, Komplement und Differenz.

== Vereinigung ==
Die Vereinigung zweier Mengen A und B, geschrieben A ∪ B, ist die Menge aller Elemente, die in A oder in B enthalten sind (oder in beiden).

Formale Definition:
A ∪ B := {x : x ∈ A ∨ x ∈ B}

Beispiel:
A = {1, 3, 5, 7}
B = {2, 4, 6, 8}
A ∪ B = {1, 2, 3, 4, 5, 6, 7, 8}

Bemerkung:
Das logische „oder“ (∨) ist einschliessend zu verstehen – also „und/oder“.

== Durchschnitt ==
Der Durchschnitt (oder Schnitt) zweier Mengen A und B, geschrieben A ∩ B, ist die Menge aller Elemente, die sowohl in A als auch in B enthalten sind.

Formale Definition:
A ∩ B := {x : x ∈ A ∧ x ∈ B}

Beispiel:
A = {α, β, γ, δ}
B = {γ, δ, ε}
A ∩ B = {γ, δ}

Wenn A ∩ B = ∅, heissen A und B disjunkt.

Beispiel:
A = {1, 3, 5, 7, …}, B = {0, 2, 4, 6, …}
A ∩ B = ∅ (ungerade und gerade Zahlen sind disjunkt)

== Komplement ==
Sei U die Universalmenge.
Das Komplement einer Menge A, geschrieben Aᶜ, besteht aus allen Elementen, die zu U gehören, aber nicht zu A.

Formale Definition:
Aᶜ := {x : x ∈ U ∧ x ∉ A}

Beispiel:
U = ℝ
A = {x : x² ≤ 4}
→ A = [−2, 2]
Dann gilt:
Aᶜ = (−∞, −2) ∪ (2, ∞)

Ein weiteres Beispiel:
U = ℝ
B = {x : x < 0}
→ Bᶜ = {x : x ≥ 0}

== Differenz ==
Die Differenz zweier Mengen A und B, geschrieben A \ B, ist die Menge aller Elemente, die in A, aber nicht in B sind.

Formale Definition:
A \ B := {x : x ∈ A ∧ x ∉ B}

Beispiel:
A = {1, 3, 5}
B = {1, 2, 3}
A \ B = {5}

== Übersicht der Operationen ==
| Operation | Bedeutung | Symbolische Schreibweise | Beispiel |
|------------|------------|--------------------------|-----------|
| Vereinigung | alle Elemente aus A oder B | A ∪ B | {1,2} ∪ {2,3} = {1,2,3} |
| Durchschnitt | nur gemeinsame Elemente | A ∩ B | {1,2,3} ∩ {2,3,4} = {2,3} |
| Komplement | alles, was nicht in A ist | Aᶜ | bei U=ℝ und A=[0,1]: Aᶜ = (−∞,0) ∪ (1,∞) |
| Differenz | A ohne Elemente aus B | A \ B | {1,2,3} \ {2,3} = {1} |

== Disjunkte Mengen ==
Zwei Mengen heissen disjunkt, wenn sie keine gemeinsamen Elemente besitzen:
A ∩ B = ∅

Beispiel:
* A = {1, 2, 3}
* B = {4, 5, 6}
→ disjunkt

== Venn-Diagramme ==
Mengenoperationen lassen sich grafisch darstellen.
Kreise, die sich überlappen, repräsentieren Vereinigungen und Durchschnitte.
Das Komplement wird durch den Bereich ausserhalb eines Kreises dargestellt.

== Zusammenfassung ==
* A ∪ B: alle Elemente, die in A oder B enthalten sind
* A ∩ B: alle Elemente, die in A und B enthalten sind
* Aᶜ: alle Elemente ausserhalb von A (relativ zu U)
* A \ B: alle Elemente in A, die nicht in B enthalten sind
* Zwei Mengen sind disjunkt, wenn ihr Durchschnitt leer ist

[[Category:Set Theory (Mengenlehre)]]

Teilmengen und Gleichheit von Mengen

2025-10-27T08:07:45Z

Bfh-sts:

= Teilmengen und Gleichheit von Mengen =
Neben der Zugehörigkeit von Elementen zu Mengen spielt auch die Beziehung zwischen Mengen selbst eine zentrale Rolle.
Dazu gehört insbesondere das Konzept der Teilmengen.

== Definition: Teilmenge ==
Eine Menge A heißt Teilmengen von B, wenn jedes Element von A auch ein Element von B ist.

Notation:
A ⊆ B ⇔ ∀x (x ∈ A ⇒ x ∈ B)

Wenn A keine Teilmenge von B ist, schreibt man:
A ⊈ B

Falls A ⊆ B gilt, aber A ≠ B, nennt man A eine echte Teilmenge von B:
A ⊂ B

== Beispiel ==
* {1, 2, 3} ⊆ {1, 2, 3, 4, 5}
* {1, 2, 3, 4} ⊆ {1, 2, 3, 4}
* {a, b} ⊂ {a, b, c, d}
* {a, b, c, d} ⊆ {a, b, c, d}
* {x} ⊄ {y, z}

== Grundlegende Eigenschaften von Teilmengen ==
Für beliebige Mengen A, B, C und die leere Menge ∅ gilt:

1. Reflexivität:
∅ ⊆ A und A ⊆ A

2. Transitivität:
Wenn A ⊆ B und B ⊆ C, dann gilt A ⊆ C

3. Antisymmetrie:
A = B ⇔ (A ⊆ B und B ⊆ A)

== Beispiele ==
=== Beispiel 1 ===
Welche der folgenden Aussagen sind richtig?

* (a) {1, 2, 3, 4} ⊆ {1, 2, 3, 4}
* (b) ∅ ⊆ ∅
* (c) {1, 2, 3} ⊆ {1, 2, 4}

Lösungen:
* (a) Wahr – jede Menge ist Teilmenge von sich selbst.
* (b) Wahr – die leere Menge ist Teilmenge jeder Menge, auch von sich selbst.
* (c) Falsch – 3 ∈ {1, 2, 3}, aber 3 ∉ {1, 2, 4}.

== Darstellung durch Venn-Diagramme ==
Das Teilmengenverhältnis kann anschaulich dargestellt werden:
* Wenn A ⊆ B, liegt die Fläche von A vollständig innerhalb von B.
* Wenn A und B disjunkt sind, überschneiden sich ihre Flächen nicht.

== Wichtige Sonderfälle ==
<syntaxhighlight lang='bash'>
| Situation | Bedeutung |
|-----------------|----------------------------------------------|
| ∅ ⊆ A | Leere Menge ist immer Teilmenge |
| A ⊆ U | Jede Menge ist Teilmenge der Universalmenge |
| A ⊆ B und B ⊆ A | Dann gilt A = B |
</syntaxhighlight>

== Zusammenhang mit Gleichheit ==
Das Teilmengenprinzip ist die Grundlage der Gleichheitsdefinition:
A = B ⇔ (A ⊆ B ∧ B ⊆ A)

Damit ist die Gleichheit zweier Mengen formal nichts anderes als gegenseitige Teilmengenbeziehung.

== Zusammenfassung ==
* A ⊆ B bedeutet: Alle Elemente von A sind in B enthalten.
* Die leere Menge ist Teilmenge jeder Menge.
* A = B gilt genau dann, wenn A ⊆ B und B ⊆ A.
* Teilmengen lassen sich visuell als vollständig enthaltene Bereiche darstellen.
* Das Teilmengenprinzip ist ein fundamentales Werkzeug in der Mengenlehre.

[[Category:Set Theory (Mengenlehre)]]

Mengen und Elemente: Mitgliedschaft, Extensionalität, Definitionen

2025-10-27T08:04:51Z

Bfh-sts:

= Mengen und Elemente =
Die Grundidee der Mengenlehre besteht darin, Objekte – genannt Elemente – zu einer Menge zusammenzufassen.
Diese Elemente können Zahlen, Buchstaben, Personen oder sogar andere Mengen sein.

== Elemente und Zugehörigkeit ==
Die Zugehörigkeit eines Elements zu einer Menge wird mit dem Symbol ∈ ausgedrückt.

Beispiele:
* 3 ∈ {1, 2, 3, 4, 5}
* a ∈ {a, b, c}
* 6 ∉ {1, 2, 3, 4, 5}

Die Zugehörigkeit ist immer eindeutig:
Ein Element ist entweder in einer Menge enthalten oder nicht.

== Das Extensionalitätsaxiom ==
Zwei Mengen sind gleich, wenn sie dieselben Elemente enthalten.
Formell:
A = B ⇔ ∀x: (x ∈ A ⇔ x ∈ B)

Beispiel:
A = {1, 2, 3}
B = {3, 2, 1}
Da beide Mengen dieselben Elemente enthalten, gilt:
A = B

== Definition von Mengen ==
Es gibt zwei grundlegende Arten, eine Menge zu definieren:

=== 1. Explizite (aufzählende) Definition ===
Die Elemente werden direkt angegeben:
A = {a, b}
B = {1, 2, 3, 4, 5}
C = {1, 2, a, b, c}

=== 2. Intensionale (beschreibende) Definition ===
Die Elemente werden durch eine Eigenschaft beschrieben:
B = {n : n ∈ ℤ ∧ n > 5}
Das liest man:
„B ist die Menge aller ganzen Zahlen n, für die n grösser als 5 ist.“

Hierbei:
* Der Buchstabe (z. B. n) steht für ein typisches Element.
* Der Doppelpunkt „:“ bedeutet „mit der Eigenschaft“.

== Beispiele ==
=== Beispiel 1 ===
Welche der folgenden Mengen sind gleich?
A = {a, b}
B = {b, a}
C = {a}
D = {1, 2, 3, 4, 5}
E = {n : n ∈ ℤ ∧ 1 ≤ n ≤ 5}
F = {x : x ∈ ℝ ∧ x² − 3x + 2 = 0}
G = {1, 4/2}

Lösungsidee:
* A und B enthalten dieselben Elemente → A = B
* D und E beschreiben dieselbe Menge → D = E
* F enthält die Nullstellen der Gleichung x² − 3x + 2 = 0 → F = {1, 2}
* G = {1, 2}
→ F = G

=== Beispiel 2 ===
A = {x : x ∈ ℝ ∧ x² + 1 = 0}
Da es keine reellen Zahlen gibt, deren Quadrat + 1 = 0 ergibt, ist:
A = ∅

== Leere Menge ==
Die leere Menge ist die Menge ohne Elemente.
Notation:
∅ oder {}

Eigenschaften:
* ∅ ⊆ A für jede Menge A
* |∅| = 0

== Universalmenge ==
Die Universalmenge (U) enthält alle in einem bestimmten Kontext relevanten Elemente.
Beispiele:
* In der Geometrie: alle Punkte einer Ebene
* In der Analysis: alle reellen Zahlen
* In der Informatik: alle möglichen Zustände oder Datenelemente

Wenn nichts anderes angegeben ist, bezeichnen wir die Universalmenge mit U.

== Zusammenfassung ==
* Elemente sind die Bausteine einer Menge.
* Eine Menge ist durch ihre Elemente eindeutig bestimmt (Extensionalitätsaxiom).
* Mengen können explizit oder durch Eigenschaften beschrieben werden.
* Die leere Menge (∅) enthält keine Elemente.
* Die Universalmenge (U) enthält alle betrachteten Elemente.

[[Category:Set Theory (Mengenlehre)]]

Mengenlehre: Überblick & Notation

2025-10-27T08:04:26Z

Bfh-sts:

= Mengenlehre: Überblick & Bedeutung =
Die Mengenlehre ist ein grundlegendes Teilgebiet der Mathematik, das von Georg Cantor (1845–1918) im 19. Jahrhundert entwickelt wurde.
Sie bildet das Fundament nahezu aller modernen mathematischen Disziplinen.
Jede mathematische Struktur – von Zahlen über Funktionen bis zu geometrischen Objekten – kann in der Sprache der Mengenlehre formuliert werden.

== Ursprung und Idee ==
Cantor definierte den Begriff der Menge folgendermassen:
> Unter einer Menge verstehen wir jede Zusammenfassung von bestimmten, wohlunterschiedlichen Objekten unserer Anschauung oder unseres Denkens (welche Elemente der Menge genannt werden) zu einem Ganzen.

Diese Definition erlaubt es, sowohl konkrete als auch abstrakte Objekte als Elemente zu betrachten.
Beispiele für Mengen:
* Die Menge der Planeten im Sonnensystem
* Die Menge der geraden natürlichen Zahlen grösser als 2, die sich als Summe zweier Primzahlen schreiben lassen
* Die Menge aller reellen Zahlen x mit x > 5
* Die Menge der Studierenden an der BFH-TI Biel

== Notation ==
* Mengen werden mit Grossbuchstaben bezeichnet (A, B, C, …).
* Elemente werden mit Kleinbuchstaben bezeichnet (a, b, c, …).
* Die Aussage „a ist Element von A“ schreibt man als:
a ∈ A
Die Negation lautet:
a ∉ A

Eine Menge ist durch ihre Elemente vollständig bestimmt.
Dieses Prinzip wird als Extensionalitätsaxiom bezeichnet:
> Zwei Mengen A und B sind genau dann gleich, wenn sie dieselben Elemente enthalten.

Formal:
A = B ⇔ ∀x: (x ∈ A ⇔ x ∈ B)

== Arten der Mengendefinition ==
Es gibt zwei grundlegende Arten, Mengen zu definieren:

=== 1. Aufzählende (explizite) Definition ===
Alle Elemente werden direkt aufgelistet:
A = {a, b, x, y, z}
B = {1, 2, 3, 4, 5}

=== 2. Beschreibende (intensionale) Definition ===
Die Elemente werden durch eine Eigenschaft charakterisiert:
B = {n : n ∈ ℤ ∧ n > 5}
„B ist die Menge aller ganzen Zahlen n, für die n > 5 gilt.“

Der Doppelpunkt „:“ bedeutet „mit der Eigenschaft“ oder „so dass“.

== Wichtige Symbole ==
| Symbol | Bedeutung |
|---------|------------|
| ∈ | ist Element von |
| ∉ | ist kein Element von |
| ⊆ | ist Teilmenge von |
| ⊂ | ist echte Teilmenge von |
| ∅ | leere Menge |
| U | Universalmenge |

== Leere Menge und Universalmenge ==
* Leere Menge (∅): enthält keine Elemente.
∅ = {}
* Universalmenge (U): enthält alle in einem Kontext betrachteten Objekte.
Beispiele:
* In der Geometrie: alle Punkte der Ebene
* In der Analysis: alle reellen Zahlen

== Bedeutung in der Informatik ==
Mengen sind auch in der Informatik zentral:
* zur Beschreibung von Zustandsräumen
* zur Definition von Datenmengen und Relationen
* für logische Operationen (UND, ODER, NICHT) in Boolescher Algebra
* als Grundlage für Datenbanktheorie und Mengenoperationen (SELECT, UNION, INTERSECT)

== Zusammenfassung ==
* Die Mengenlehre ist das Fundament der Mathematik.
* Mengen sind Sammlungen von klar unterscheidbaren Objekten.
* Die Mitgliedschaft (∈) ist das zentrale Konzept.
* Mengen können durch Aufzählung oder Eigenschaft definiert werden.
* Leere Menge (∅) und Universalmenge (U) sind wichtige Spezialfälle.

[[Category:Set Theory (Mengenlehre)]]

Endliche Mengen & Einschluss-Ausschluss-Prinzip

2025-10-27T08:00:00Z

Bfh-sts: Created page with "= Endliche Mengen und das Einschluss-Ausschluss-Prinzip = Viele praktische Probleme befassen sich mit **endlichen Mengen**, also Mengen mit abzählbarer Anzahl von Elementen. Für solche Mengen spielt das **Zählen** von Elementen und Überschneidungen eine zentrale Rolle. == Endliche und unendliche Mengen == Eine Menge heißt **endlich**, wenn sie genau *m* verschiedene Elemente enthält, wobei *m* eine natürliche Zahl ist. Sonst heißt sie **unendlich**. Beispie..."

= Endliche Mengen und das Einschluss-Ausschluss-Prinzip =
Viele praktische Probleme befassen sich mit **endlichen Mengen**, also Mengen mit abzählbarer Anzahl von Elementen.
Für solche Mengen spielt das **Zählen** von Elementen und Überschneidungen eine zentrale Rolle.

== Endliche und unendliche Mengen ==
Eine Menge heißt **endlich**, wenn sie genau *m* verschiedene Elemente enthält, wobei *m* eine natürliche Zahl ist.
Sonst heißt sie **unendlich**.

Beispiele:
* ∅ → endlich, da keine Elemente
* Alphabet = {A, B, …, Z} → endlich
* ℕ = {1, 2, 3, 4, …} → unendlich

Die Anzahl der Elemente einer endlichen Menge A wird mit |A| bezeichnet.

Beispiel:
A = {1, 2, 3, 4} → |A| = 4

== Vereinigung endlicher Mengen ==
Sind A und B endlich, so ist auch A ∪ B endlich.
Dabei gilt die Grundformel:

|A ∪ B| = |A| + |B| − |A ∩ B|

Diese Formel korrigiert die doppelte Zählung der Schnittmenge.

=== Beispiel ===
A = {1, 2, 3, 4}, B = {3, 4, 5, 6}
|A| = 4, |B| = 4, |A ∩ B| = 2
→ |A ∪ B| = 4 + 4 − 2 = 6
A ∪ B = {1, 2, 3, 4, 5, 6}

== Herleitung der Formel ==
Die Mengen A und B können als **drei disjunkte Teilmengen** betrachtet werden:
* A \ (A ∩ B)
* A ∩ B
* B \ (A ∩ B)

Da diese drei Mengen keine Überschneidung haben, gilt:
|A ∪ B| = |A \ (A ∩ B)| + |A ∩ B| + |B \ (A ∩ B)|

Daraus folgt:
|A ∪ B| = |A| + |B| − |A ∩ B|

== Erweiterung auf drei Mengen ==
Für drei endliche Mengen A, B, C gilt die **Einschluss-Ausschluss-Formel**:

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

Diese Formel berücksichtigt alle Überschneidungen korrekt:
* Einfache Mengen: +
* Doppelte Schnittmengen: −
* Dreifache Schnittmenge: +

== Erweiterung auf vier Mengen ==
Für A, B, C, D gilt:

|A ∪ B ∪ C ∪ D| =
|A| + |B| + |C| + |D|
− (|A ∩ B| + |A ∩ C| + |A ∩ D| + |B ∩ C| + |B ∩ D| + |C ∩ D|)
+ (|A ∩ B ∩ C| + |A ∩ B ∩ D| + |A ∩ C ∩ D| + |B ∩ C ∩ D|)
− |A ∩ B ∩ C ∩ D|

== Beispiel: Anwendung auf Studierende ==
An einer Universität studieren 2’504 Studierende Informatik.
Davon belegen:
* 1’876 Java
* 999 C
* 345 Prolog
* 876 sowohl Java als auch C
* 231 C und Prolog
* 290 Java und Prolog
* 189 alle drei Kurse

(a) Wie viele Studierende belegen **keinen** der drei Kurse?

|U| = 2’504
|A ∪ B ∪ C| = 1’876 + 999 + 345 − 876 − 231 − 290 + 189 = 2’012
→ Studierende ohne Kurs = 2’504 − 2’012 = **492**

(b) Wie viele belegen **genau einen Kurs**?

= |A| + |B| + |C| − 2·(|A ∩ B| + |A ∩ C| + |B ∩ C|) + 3·|A ∩ B ∩ C|
= 1’876 + 999 + 345 − 2·(876 + 231 + 290) + 3·189 = **1’002**

== Bedeutung ==
Das Einschluss-Ausschluss-Prinzip ist ein zentrales Werkzeug:
* zur Bestimmung der Kardinalität von Vereinigungen
* in Kombinatorik, Statistik und Wahrscheinlichkeitstheorie
* für logische Vereinfachungen in der Informatik (z. B. Boolesche Algebra)

== Zusammenfassung ==
* Eine Menge ist **endlich**, wenn sie eine abzählbare Anzahl von Elementen hat.
* **|A ∪ B| = |A| + |B| − |A ∩ B|** korrigiert doppelte Zählung.
* Das **Einschluss-Ausschluss-Prinzip** erweitert diese Idee auf mehrere Mengen.
* In der Informatik hilft es beim Zählen von Zuständen, Kombinationen und logischen Fällen.

[[Category:Set Theory (Mengenlehre)]]

Geordnete Paare, n-Tupel & kartesische Produkte

2025-10-27T07:58:57Z

Bfh-sts: Created page with "= Geordnete Paare, n-Tupel und kartesische Produkte = In der Mengenlehre spielt die **Reihenfolge** der Elemente normalerweise keine Rolle. Doch in vielen Anwendungen – etwa bei Funktionen oder Datenstrukturen – ist sie entscheidend. Dazu dienen **geordnete Paare** und **Tupel**. == Geordnete Paare == Ein **geordnetes Paar** besteht aus zwei Elementen, bei denen die Reihenfolge eine Rolle spielt. Notation: (a, b) Das erste Element ist **a**, das zweite ist *..."

= Geordnete Paare, n-Tupel und kartesische Produkte =
In der Mengenlehre spielt die **Reihenfolge** der Elemente normalerweise keine Rolle.
Doch in vielen Anwendungen – etwa bei Funktionen oder Datenstrukturen – ist sie entscheidend.
Dazu dienen **geordnete Paare** und **Tupel**.

== Geordnete Paare ==
Ein **geordnetes Paar** besteht aus zwei Elementen, bei denen die Reihenfolge eine Rolle spielt.
Notation:
(a, b)

Das erste Element ist **a**, das zweite ist **b**.
Zwei geordnete Paare (a, b) und (c, d) sind **gleich**, genau dann, wenn gilt:
a = c und b = d

Beispiel:
* (1, 2) ≠ (2, 1)
* (x, y) = (x, y)
* (a, b) ≠ (b, a), sofern a ≠ b

== Kartesisches Produkt ==
Das **kartesische Produkt** zweier Mengen A und B ist die Menge aller **geordneten Paare** (x, y) mit x ∈ A und y ∈ B.

Formale Definition:
A × B := {(x, y) : x ∈ A ∧ y ∈ B}

Beispiel:
A = {1, 2}
B = {a, b, c}

Dann gilt:
A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}
B × A = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}
A² = A × A = {(1, 1), (1, 2), (2, 1), (2, 2)}

== Anzahl der Elemente ==
Wenn A und B **endlich** sind, gilt:
|A × B| = |A| · |B|

Beispiel:
A = {1, 2, 3}, B = {a, b}
|A × B| = 3 · 2 = 6

== n-Tupel ==
Ein **n-Tupel** ist eine geordnete Liste von n Elementen:
(a₁, a₂, …, aₙ)

Die Reihenfolge der Elemente ist wesentlich.

Zwei n-Tupel (a₁, a₂, …, aₙ) und (b₁, b₂, …, bₙ) sind gleich, wenn:
a₁ = b₁ ∧ a₂ = b₂ ∧ … ∧ aₙ = bₙ

Beispiele:
* (a, b, c) → Tripel
* (a, b, c, d) → Quadrupel

== Kartesisches Produkt mehrerer Mengen ==
Für n Mengen A₁, A₂, …, Aₙ gilt:
A₁ × A₂ × … × Aₙ = {(a₁, a₂, …, aₙ) : aᵢ ∈ Aᵢ für alle i}

Beispiel:
A = {a, b}, B = {x}, C = {1, 2, 3}

A × B × C = {
(a, x, 1), (a, x, 2), (a, x, 3),
(b, x, 1), (b, x, 2), (b, x, 3)
}

== Kombinatorische Überlegungen ==
Wenn |A₁| = n₁, |A₂| = n₂, …, |Aₙ| = nₙ, dann gilt:
|A₁ × A₂ × … × Aₙ| = n₁ · n₂ · … · nₙ

Beispiel:
Drei Mengen:
* A = {rot, blau}
* B = {rund, eckig}
* C = {klein, groß}

→ |A × B × C| = 2 · 2 · 2 = 8 Kombinationen.

== Variation der Elemente ==
Bei einer Menge aus n Zahlen (1, 2, …, n):
* Wenn jede Zahl **nur einmal** vorkommen darf → n! mögliche Tupel (Permutationen)
* Wenn jede Zahl **beliebig oft** vorkommen darf → nⁿ mögliche Tupel

== Anwendung ==
Kartesische Produkte und Tupel bilden die Grundlage für:
* **Funktionen**: eine Funktion ist eine Teilmenge von A × B
* **Datenbanken**: Tabellenzeilen entsprechen n-Tupeln
* **Vektorräume**: Elemente sind n-Tupel reeller Zahlen

== Zusammenfassung ==
* Reihenfolge spielt bei geordneten Paaren und Tupeln eine Rolle.
* Das kartesische Produkt A × B kombiniert alle möglichen Paare (x, y).
* |A × B| = |A| · |B| bei endlichen Mengen.
* Das Konzept erweitert sich auf n-Tupel.
* Anwendungen: Funktionen, Datenstrukturen, Relationen, Kombinatorik.

[[Category:Set Theory (Mengenlehre)]]

Mengensysteme, Potenzmenge & Partitionen

2025-10-27T07:57:28Z

Bfh-sts: Created page with "= Mengensysteme, Potenzmenge und Partitionen = Neben einzelnen Mengen betrachtet man oft **Systeme von Mengen** – also Mengen, deren Elemente wiederum Mengen sind. Dazu gehören wichtige Begriffe wie **Potenzmenge** und **Partition**. == Mengensystem == Eine **Menge von Mengen** heißt ein **Mengensystem**. Beispiel: S = { {1, 2}, {3, 4}, {5} } Jedes Element von S ist selbst eine Menge. == Potenzmenge == Die **Potenzmenge** einer Menge S ist die Menge aller **T..."

= Mengensysteme, Potenzmenge und Partitionen =
Neben einzelnen Mengen betrachtet man oft **Systeme von Mengen** – also Mengen, deren Elemente wiederum Mengen sind.
Dazu gehören wichtige Begriffe wie **Potenzmenge** und **Partition**.

== Mengensystem ==
Eine **Menge von Mengen** heißt ein **Mengensystem**.
Beispiel:
S = { {1, 2}, {3, 4}, {5} }

Jedes Element von S ist selbst eine Menge.

== Potenzmenge ==
Die **Potenzmenge** einer Menge S ist die Menge aller **Teilmenge**n von S.
Notation:
P(S) = {A : A ⊆ S}

Beispiel:
Sei S = {1, 2}
Dann gilt:
P(S) = {∅, {1}, {2}, {1, 2}}

Beispiel:
* A = ∅ → P(A) = {∅}
* B = {a} → P(B) = {∅, {a}}
* C = {a, b} → P(C) = {∅, {a}, {b}, {a, b}}

Allgemein gilt:
Eine Menge mit **n Elementen** besitzt **2ⁿ Teilmengen.**

Beispiel:
D = {a, b, c, d} → |P(D)| = 2⁴ = 16

== Beispielaufgaben ==
1. Bestimme die Potenzmenge von E = {a, b, c, d}.
→ 16 Teilmengen
2. Wieviele Teilmengen besitzt eine Menge mit 5 Elementen?
→ 2⁵ = 32

== Partition ==
Eine **Partition** einer Menge S** ist eine Aufteilung von S in nicht-leere, disjunkte Teilmengen**, deren Vereinigung S ergibt.

Formal:
Eine Familie {Aᵢ} von Teilmengen von S ist eine Partition, wenn gilt:
1. Aᵢ ≠ ∅ für alle i
2. ⋃ Aᵢ = S
3. Aᵢ ∩ Aⱼ = ∅ für alle i ≠ j

Beispiel:
S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

(a) {∅, {1,2}, {3,4,5}, {6,7,8,9,10}} → keine Partition, da ∅ enthalten
(b) {{1,2,3,4}, {4,5,6}, {7,8,9,10}} → keine Partition, da sich {1,2,3,4} und {4,5,6} überschneiden
(c) {{2,3,4,5}, {6,7,8}, {9,10}} → Partition von {2,…,10}, nicht von S
(d) {{1,2,3}, {4,5,6}, {7,8,9,10}} → **gültige Partition** von S

== Zusammenhang zwischen Potenzmenge und Partition ==
* Die Potenzmenge enthält alle möglichen Kombinationen von Teilmengen.
* Eine Partition wählt aus diesen Teilmengen eine besondere Kombination, bei der:
- keine Schnittmenge entsteht
- die Vereinigung wieder die Ausgangsmenge ergibt

== Visualisierung ==
Ein Venn-Diagramm kann Partitionen als **nicht überlappende Flächen** innerhalb der Universalmenge darstellen.
Jede Teilmenge repräsentiert ein disjunktes „Teilgebiet“.

== Zusammenfassung ==
* **Mengensystem:** Menge von Mengen.
* **Potenzmenge P(S):** Menge aller Teilmengen von S, mit |P(S)| = 2ⁿ.
* **Partition:** disjunkte, nicht-leere Teilmengen, deren Vereinigung S ergibt.
* Potenzmengen und Partitionen sind zentrale Konzepte in Kombinatorik und Wahrscheinlichkeitsrechnung.

[[Category:Set Theory (Mengenlehre)]]

Mengenalgebra & Dualität: Gesetze und de Morgan

2025-10-27T07:57:16Z

Bfh-sts: Created page with "= Mengenalgebra und Dualität = Die in der Mengenlehre definierten Operationen (Vereinigung, Durchschnitt, Komplement, Differenz) folgen bestimmten **algebraischen Gesetzen**. Diese Gesetze erlauben es, Ausdrücke zu vereinfachen oder zu beweisen, dass zwei Mengenoperationen äquivalent sind. == Grundlegende Gesetze der Mengenalgebra == Für beliebige Mengen A, B, C und die Universalmenge U gelten folgende Gesetze: === 1. Idempotenz === A ∪ A = A A ∩ A = A D..."

= Mengenalgebra und Dualität =
Die in der Mengenlehre definierten Operationen (Vereinigung, Durchschnitt, Komplement, Differenz) folgen bestimmten **algebraischen Gesetzen**.
Diese Gesetze erlauben es, Ausdrücke zu vereinfachen oder zu beweisen, dass zwei Mengenoperationen äquivalent sind.

== Grundlegende Gesetze der Mengenalgebra ==
Für beliebige Mengen A, B, C und die Universalmenge U gelten folgende Gesetze:

=== 1. Idempotenz ===
A ∪ A = A
A ∩ A = A

Das Zusammenfassen oder Schneiden einer Menge mit sich selbst ändert nichts.

=== 2. Assoziativgesetz ===
(A ∪ B) ∪ C = A ∪ (B ∪ C)
(A ∩ B) ∩ C = A ∩ (B ∩ C)

Die Reihenfolge der Ausführung spielt keine Rolle.

=== 3. Kommutativgesetz ===
A ∪ B = B ∪ A
A ∩ B = B ∩ A

Die Reihenfolge der Mengen kann vertauscht werden.

=== 4. Distributivgesetz ===
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

Dies erlaubt, Ausdrücke zu „verteilen“, ähnlich wie beim Distributivgesetz der Algebra.

=== 5. Identitätsgesetz ===
A ∪ ∅ = A
A ∩ U = A

∅ und U verhalten sich wie 0 und 1 in der Arithmetik.

=== 6. Null- und Einheitsgesetz ===
A ∪ U = U
A ∩ ∅ = ∅

Alles mit der Universalmenge vereinigt ergibt U;
alles mit der leeren Menge geschnitten ergibt ∅.

=== 7. Gesetz vom doppelten Komplement ===
(Aᶜ)ᶜ = A

Das Komplement des Komplements ergibt wieder die ursprüngliche Menge.

=== 8. Komplementgesetze ===
A ∪ Aᶜ = U
A ∩ Aᶜ = ∅

Eine Menge und ihr Komplement decken die Universalmenge vollständig ab, ohne sich zu überschneiden.

=== 9. Komplemente der Universal- und Leermenge ===
Uᶜ = ∅
∅ᶜ = U

=== 10. de Morgan’sche Gesetze ===
(A ∪ B)ᶜ = Aᶜ ∩ Bᶜ
(A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

Diese sind besonders wichtig, da sie eine enge Verbindung zur Aussagenlogik zeigen:
* Das Komplement einer Vereinigung ist der Durchschnitt der Komplemente.
* Das Komplement eines Durchschnitts ist die Vereinigung der Komplemente.

== Beispiel: Beweis des de Morgan Gesetzes ==
Beweise (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ mithilfe der Logik:

| Aussage | Logisches Pendant |
|----------|--------------------|
| x ∈ (A ∩ B)ᶜ | ¬(x ∈ A ∧ x ∈ B) |
| | ⇔ (¬x ∈ A) ∨ (¬x ∈ B) |
| | ⇔ x ∈ Aᶜ ∨ x ∈ Bᶜ |
| ⇒ | x ∈ (Aᶜ ∪ Bᶜ) |

Daraus folgt: (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

== Dualitätsprinzip ==
Die Gesetze der Mengenlehre treten **paarweise** auf.
Tauscht man überall
* ∪ ↔ ∩
* U ↔ ∅

so erhält man den **dualen Ausdruck**.

Beispiel:
* Gesetz A ∪ ∅ = A hat als Dual A ∩ U = A
* de Morgan’s Gesetz (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ hat als Dual (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

Dieses Prinzip zeigt die **symmetrische Struktur** der Mengenoperationen.

== Visualisierung ==
Venn-Diagramme verdeutlichen diese Gesetze grafisch:
* Die Vereinigungen und Durchschnitte entsprechen farblich markierten Bereichen.
* Komplementbereiche sind die Flächen außerhalb der betrachteten Menge.

== Zusammenfassung ==
* Mengenoperationen folgen festen algebraischen Gesetzen.
* Diese Gesetze entsprechen den Regeln der Aussagenlogik.
* Das **Dualitätsprinzip** erlaubt, aus jedem Gesetz sein komplementäres Gegenstück zu bilden.
* Die **de Morgan’schen Gesetze** sind besonders zentral für logische und rechnerische Anwendungen.

[[Category:Set Theory (Mengenlehre)]]

Vereinigung, Durchschnitt, Differenz und Komplement (inkl. Disjunktheit)

2025-10-27T07:56:52Z

Bfh-sts: Created page with "= Vereinigung, Durchschnitt, Differenz und Komplement = In der Mengenlehre werden neue Mengen oft durch **Operationen** auf bestehenden Mengen gebildet. Die wichtigsten sind **Vereinigung**, **Durchschnitt**, **Komplement** und **Differenz**. == Vereinigung == Die **Vereinigung** zweier Mengen A und B, geschrieben **A ∪ B**, ist die Menge aller Elemente, die in **A** oder in **B** enthalten sind (oder in beiden). Formale Definition: A ∪ B := {x : x ∈ A ∨ x..."

= Vereinigung, Durchschnitt, Differenz und Komplement =
In der Mengenlehre werden neue Mengen oft durch **Operationen** auf bestehenden Mengen gebildet.
Die wichtigsten sind **Vereinigung**, **Durchschnitt**, **Komplement** und **Differenz**.

== Vereinigung ==
Die **Vereinigung** zweier Mengen A und B, geschrieben **A ∪ B**, ist die Menge aller Elemente, die in **A** oder in **B** enthalten sind (oder in beiden).

Formale Definition:
A ∪ B := {x : x ∈ A ∨ x ∈ B}

Beispiel:
A = {1, 3, 5, 7}
B = {2, 4, 6, 8}
A ∪ B = {1, 2, 3, 4, 5, 6, 7, 8}

Bemerkung:
Das logische „oder“ (∨) ist **einschließend** zu verstehen – also „und/oder“.

== Durchschnitt ==
Der **Durchschnitt** (oder **Schnitt**) zweier Mengen A und B, geschrieben **A ∩ B**, ist die Menge aller Elemente, die sowohl in **A** als auch in **B** enthalten sind.

Formale Definition:
A ∩ B := {x : x ∈ A ∧ x ∈ B}

Beispiel:
A = {α, β, γ, δ}
B = {γ, δ, ε}
A ∩ B = {γ, δ}

Wenn A ∩ B = ∅, heißen A und B **disjunkt**.

Beispiel:
A = {1, 3, 5, 7, …}, B = {0, 2, 4, 6, …}
A ∩ B = ∅ (ungerade und gerade Zahlen sind disjunkt)

== Komplement ==
Sei U die **Universalmenge**.
Das **Komplement** einer Menge A, geschrieben **Aᶜ**, besteht aus allen Elementen, die zu U gehören, aber **nicht** zu A.

Formale Definition:
Aᶜ := {x : x ∈ U ∧ x ∉ A}

Beispiel:
U = ℝ
A = {x : x² ≤ 4}
→ A = [−2, 2]
Dann gilt:
Aᶜ = (−∞, −2) ∪ (2, ∞)

Ein weiteres Beispiel:
U = ℝ
B = {x : x < 0}
→ Bᶜ = {x : x ≥ 0}

== Differenz ==
Die **Differenz** zweier Mengen A und B, geschrieben **A \ B**, ist die Menge aller Elemente, die in **A**, aber **nicht** in **B** sind.

Formale Definition:
A \ B := {x : x ∈ A ∧ x ∉ B}

Beispiel:
A = {1, 3, 5}
B = {1, 2, 3}
A \ B = {5}

== Übersicht der Operationen ==
| Operation | Bedeutung | Symbolische Schreibweise | Beispiel |
|------------|------------|--------------------------|-----------|
| Vereinigung | alle Elemente aus A oder B | A ∪ B | {1,2} ∪ {2,3} = {1,2,3} |
| Durchschnitt | nur gemeinsame Elemente | A ∩ B | {1,2,3} ∩ {2,3,4} = {2,3} |
| Komplement | alles, was nicht in A ist | Aᶜ | bei U=ℝ und A=[0,1]: Aᶜ = (−∞,0) ∪ (1,∞) |
| Differenz | A ohne Elemente aus B | A \ B | {1,2,3} \ {2,3} = {1} |

== Disjunkte Mengen ==
Zwei Mengen heißen **disjunkt**, wenn sie keine gemeinsamen Elemente besitzen:
A ∩ B = ∅

Beispiel:
* A = {1, 2, 3}
* B = {4, 5, 6}
→ disjunkt

== Venn-Diagramme ==
Mengenoperationen lassen sich grafisch darstellen.
Kreise, die sich überlappen, repräsentieren Vereinigungen und Durchschnitte.
Das Komplement wird durch den Bereich außerhalb eines Kreises dargestellt.

== Zusammenfassung ==
* **A ∪ B**: alle Elemente, die in A oder B enthalten sind
* **A ∩ B**: alle Elemente, die in A und B enthalten sind
* **Aᶜ**: alle Elemente außerhalb von A (relativ zu U)
* **A \ B**: alle Elemente in A, die nicht in B enthalten sind
* Zwei Mengen sind **disjunkt**, wenn ihr Durchschnitt leer ist

[[Category:Set Theory (Mengenlehre)]]

Teilmengen und Gleichheit von Mengen

2025-10-27T07:54:32Z

Bfh-sts: /* Beispiel 1 */

= Teilmengen und Gleichheit von Mengen =
Neben der Zugehörigkeit von Elementen zu Mengen spielt auch die Beziehung zwischen Mengen selbst eine zentrale Rolle.
Dazu gehört insbesondere das Konzept der **Teilmengen**.

== Definition: Teilmenge ==
Eine Menge **A** heißt **Teilmengen** von **B**, wenn jedes Element von **A** auch ein Element von **B** ist.

Notation:
A ⊆ B ⇔ ∀x (x ∈ A ⇒ x ∈ B)

Wenn A keine Teilmenge von B ist, schreibt man:
A ⊈ B

Falls A ⊆ B gilt, aber A ≠ B, nennt man A eine **echte Teilmenge** von B:
A ⊂ B

== Beispiel ==
* {1, 2, 3} ⊆ {1, 2, 3, 4, 5}
* {1, 2, 3, 4} ⊆ {1, 2, 3, 4}
* {a, b} ⊂ {a, b, c, d}
* {a, b, c, d} ⊆ {a, b, c, d}
* {x} ⊄ {y, z}

== Grundlegende Eigenschaften von Teilmengen ==
Für beliebige Mengen A, B, C und die leere Menge ∅ gilt:

1. **Reflexivität:**
∅ ⊆ A und A ⊆ A

2. **Transitivität:**
Wenn A ⊆ B und B ⊆ C, dann gilt A ⊆ C

3. **Antisymmetrie:**
A = B ⇔ (A ⊆ B und B ⊆ A)

== Beispiele ==
=== Beispiel 1 ===
Welche der folgenden Aussagen sind richtig?

* (a) {1, 2, 3, 4} ⊆ {1, 2, 3, 4}
* (b) ∅ ⊆ ∅
* (c) {1, 2, 3} ⊆ {1, 2, 4}

Lösungen:
* (a) Wahr – jede Menge ist Teilmenge von sich selbst.
* (b) Wahr – die leere Menge ist Teilmenge jeder Menge, auch von sich selbst.
* (c) Falsch – 3 ∈ {1, 2, 3}, aber 3 ∉ {1, 2, 4}.

== Darstellung durch Venn-Diagramme ==
Das Teilmengenverhältnis kann anschaulich dargestellt werden:
* Wenn A ⊆ B, liegt die Fläche von A vollständig innerhalb von B.
* Wenn A und B disjunkt sind, überschneiden sich ihre Flächen nicht.

== Wichtige Sonderfälle ==
<syntaxhighlight lang='bash'>
| Situation | Bedeutung |
|-----------------|----------------------------------------------|
| ∅ ⊆ A | Leere Menge ist immer Teilmenge |
| A ⊆ U | Jede Menge ist Teilmenge der Universalmenge |
| A ⊆ B und B ⊆ A | Dann gilt A = B |
</syntaxhighlight>

== Zusammenhang mit Gleichheit ==
Das Teilmengenprinzip ist die Grundlage der **Gleichheitsdefinition**:
A = B ⇔ (A ⊆ B ∧ B ⊆ A)

Damit ist die Gleichheit zweier Mengen formal nichts anderes als gegenseitige Teilmengenbeziehung.

== Zusammenfassung ==
* A ⊆ B bedeutet: Alle Elemente von A sind in B enthalten.
* Die leere Menge ist Teilmenge jeder Menge.
* A = B gilt genau dann, wenn A ⊆ B und B ⊆ A.
* Teilmengen lassen sich visuell als vollständig enthaltene Bereiche darstellen.
* Das Teilmengenprinzip ist ein fundamentales Werkzeug in der Mengenlehre.

[[Category:Set Theory (Mengenlehre)]]

Teilmengen und Gleichheit von Mengen

2025-10-27T07:54:19Z

Bfh-sts: /* Beispiele */

= Teilmengen und Gleichheit von Mengen =
Neben der Zugehörigkeit von Elementen zu Mengen spielt auch die Beziehung zwischen Mengen selbst eine zentrale Rolle.
Dazu gehört insbesondere das Konzept der **Teilmengen**.

== Definition: Teilmenge ==
Eine Menge **A** heißt **Teilmengen** von **B**, wenn jedes Element von **A** auch ein Element von **B** ist.

Notation:
A ⊆ B ⇔ ∀x (x ∈ A ⇒ x ∈ B)

Wenn A keine Teilmenge von B ist, schreibt man:
A ⊈ B

Falls A ⊆ B gilt, aber A ≠ B, nennt man A eine **echte Teilmenge** von B:
A ⊂ B

== Beispiel ==
* {1, 2, 3} ⊆ {1, 2, 3, 4, 5}
* {1, 2, 3, 4} ⊆ {1, 2, 3, 4}
* {a, b} ⊂ {a, b, c, d}
* {a, b, c, d} ⊆ {a, b, c, d}
* {x} ⊄ {y, z}

== Grundlegende Eigenschaften von Teilmengen ==
Für beliebige Mengen A, B, C und die leere Menge ∅ gilt:

1. **Reflexivität:**
∅ ⊆ A und A ⊆ A

2. **Transitivität:**
Wenn A ⊆ B und B ⊆ C, dann gilt A ⊆ C

3. **Antisymmetrie:**
A = B ⇔ (A ⊆ B und B ⊆ A)

== Beispiele ==
=== Beispiel 1 ===
Welche der folgenden Aussagen sind richtig?

* (a) {1, 2, 3, 4} ⊆ {1, 2, 3, 4}
* (b) ∅ ⊆ ∅
* (c) {1, 2, 3} ⊆ {1, 2, 4}

**Lösungen:**
* (a) Wahr – jede Menge ist Teilmenge von sich selbst.
* (b) Wahr – die leere Menge ist Teilmenge jeder Menge, auch von sich selbst.
* (c) Falsch – 3 ∈ {1, 2, 3}, aber 3 ∉ {1, 2, 4}.

== Darstellung durch Venn-Diagramme ==
Das Teilmengenverhältnis kann anschaulich dargestellt werden:
* Wenn A ⊆ B, liegt die Fläche von A vollständig innerhalb von B.
* Wenn A und B disjunkt sind, überschneiden sich ihre Flächen nicht.

== Wichtige Sonderfälle ==
<syntaxhighlight lang='bash'>
| Situation | Bedeutung |
|-----------------|----------------------------------------------|
| ∅ ⊆ A | Leere Menge ist immer Teilmenge |
| A ⊆ U | Jede Menge ist Teilmenge der Universalmenge |
| A ⊆ B und B ⊆ A | Dann gilt A = B |
</syntaxhighlight>

== Zusammenhang mit Gleichheit ==
Das Teilmengenprinzip ist die Grundlage der **Gleichheitsdefinition**:
A = B ⇔ (A ⊆ B ∧ B ⊆ A)

Damit ist die Gleichheit zweier Mengen formal nichts anderes als gegenseitige Teilmengenbeziehung.

== Zusammenfassung ==
* A ⊆ B bedeutet: Alle Elemente von A sind in B enthalten.
* Die leere Menge ist Teilmenge jeder Menge.
* A = B gilt genau dann, wenn A ⊆ B und B ⊆ A.
* Teilmengen lassen sich visuell als vollständig enthaltene Bereiche darstellen.
* Das Teilmengenprinzip ist ein fundamentales Werkzeug in der Mengenlehre.

[[Category:Set Theory (Mengenlehre)]]

Teilmengen und Gleichheit von Mengen

2025-10-27T07:51:38Z

Bfh-sts: /* Wichtige Sonderfälle */

= Teilmengen und Gleichheit von Mengen =
Neben der Zugehörigkeit von Elementen zu Mengen spielt auch die Beziehung zwischen Mengen selbst eine zentrale Rolle.
Dazu gehört insbesondere das Konzept der **Teilmengen**.

== Definition: Teilmenge ==
Eine Menge **A** heißt **Teilmengen** von **B**, wenn jedes Element von **A** auch ein Element von **B** ist.

Notation:
A ⊆ B ⇔ ∀x (x ∈ A ⇒ x ∈ B)

Wenn A keine Teilmenge von B ist, schreibt man:
A ⊈ B

Falls A ⊆ B gilt, aber A ≠ B, nennt man A eine **echte Teilmenge** von B:
A ⊂ B

== Beispiel ==
* {1, 2, 3} ⊆ {1, 2, 3, 4, 5}
* {1, 2, 3, 4} ⊆ {1, 2, 3, 4}
* {a, b} ⊂ {a, b, c, d}
* {a, b, c, d} ⊆ {a, b, c, d}
* {x} ⊄ {y, z}

== Grundlegende Eigenschaften von Teilmengen ==
Für beliebige Mengen A, B, C und die leere Menge ∅ gilt:

1. **Reflexivität:**
∅ ⊆ A und A ⊆ A

2. **Transitivität:**
Wenn A ⊆ B und B ⊆ C, dann gilt A ⊆ C

3. **Antisymmetrie:**
A = B ⇔ (A ⊆ B und B ⊆ A)

== Beispiele ==
=== Beispiel 1 ===
Welche der folgenden Aussagen sind richtig?

(a) {1, 2, 3, 4} ⊆ {1, 2, 3, 4}
(b) ∅ ⊆ ∅
(c) {1, 2, 3} ⊆ {1, 2, 4}

**Lösungen:**
* (a) Wahr – jede Menge ist Teilmenge von sich selbst.
* (b) Wahr – die leere Menge ist Teilmenge jeder Menge, auch von sich selbst.
* (c) Falsch – 3 ∈ {1, 2, 3}, aber 3 ∉ {1, 2, 4}.

== Darstellung durch Venn-Diagramme ==
Das Teilmengenverhältnis kann anschaulich dargestellt werden:
* Wenn A ⊆ B, liegt die Fläche von A vollständig innerhalb von B.
* Wenn A und B disjunkt sind, überschneiden sich ihre Flächen nicht.

== Wichtige Sonderfälle ==
<syntaxhighlight lang='bash'>
| Situation | Bedeutung |
|-----------------|----------------------------------------------|
| ∅ ⊆ A | Leere Menge ist immer Teilmenge |
| A ⊆ U | Jede Menge ist Teilmenge der Universalmenge |
| A ⊆ B und B ⊆ A | Dann gilt A = B |
</syntaxhighlight>

== Zusammenhang mit Gleichheit ==
Das Teilmengenprinzip ist die Grundlage der **Gleichheitsdefinition**:
A = B ⇔ (A ⊆ B ∧ B ⊆ A)

Damit ist die Gleichheit zweier Mengen formal nichts anderes als gegenseitige Teilmengenbeziehung.

== Zusammenfassung ==
* A ⊆ B bedeutet: Alle Elemente von A sind in B enthalten.
* Die leere Menge ist Teilmenge jeder Menge.
* A = B gilt genau dann, wenn A ⊆ B und B ⊆ A.
* Teilmengen lassen sich visuell als vollständig enthaltene Bereiche darstellen.
* Das Teilmengenprinzip ist ein fundamentales Werkzeug in der Mengenlehre.

[[Category:Set Theory (Mengenlehre)]]

Teilmengen und Gleichheit von Mengen

2025-10-27T07:48:48Z

Bfh-sts: Created page with "= Teilmengen und Gleichheit von Mengen = Neben der Zugehörigkeit von Elementen zu Mengen spielt auch die Beziehung zwischen Mengen selbst eine zentrale Rolle. Dazu gehört insbesondere das Konzept der **Teilmengen**. == Definition: Teilmenge == Eine Menge **A** heißt **Teilmengen** von **B**, wenn jedes Element von **A** auch ein Element von **B** ist. Notation: A ⊆ B ⇔ ∀x (x ∈ A ⇒ x ∈ B) Wenn A keine Teilmenge von B ist, schreibt man: A ⊈ B Falls..."

= Teilmengen und Gleichheit von Mengen =
Neben der Zugehörigkeit von Elementen zu Mengen spielt auch die Beziehung zwischen Mengen selbst eine zentrale Rolle.
Dazu gehört insbesondere das Konzept der **Teilmengen**.

== Definition: Teilmenge ==
Eine Menge **A** heißt **Teilmengen** von **B**, wenn jedes Element von **A** auch ein Element von **B** ist.

Notation:
A ⊆ B ⇔ ∀x (x ∈ A ⇒ x ∈ B)

Wenn A keine Teilmenge von B ist, schreibt man:
A ⊈ B

Falls A ⊆ B gilt, aber A ≠ B, nennt man A eine **echte Teilmenge** von B:
A ⊂ B

== Beispiel ==
* {1, 2, 3} ⊆ {1, 2, 3, 4, 5}
* {1, 2, 3, 4} ⊆ {1, 2, 3, 4}
* {a, b} ⊂ {a, b, c, d}
* {a, b, c, d} ⊆ {a, b, c, d}
* {x} ⊄ {y, z}

== Grundlegende Eigenschaften von Teilmengen ==
Für beliebige Mengen A, B, C und die leere Menge ∅ gilt:

1. **Reflexivität:**
∅ ⊆ A und A ⊆ A

2. **Transitivität:**
Wenn A ⊆ B und B ⊆ C, dann gilt A ⊆ C

3. **Antisymmetrie:**
A = B ⇔ (A ⊆ B und B ⊆ A)

== Beispiele ==
=== Beispiel 1 ===
Welche der folgenden Aussagen sind richtig?

(a) {1, 2, 3, 4} ⊆ {1, 2, 3, 4}
(b) ∅ ⊆ ∅
(c) {1, 2, 3} ⊆ {1, 2, 4}

**Lösungen:**
* (a) Wahr – jede Menge ist Teilmenge von sich selbst.
* (b) Wahr – die leere Menge ist Teilmenge jeder Menge, auch von sich selbst.
* (c) Falsch – 3 ∈ {1, 2, 3}, aber 3 ∉ {1, 2, 4}.

== Darstellung durch Venn-Diagramme ==
Das Teilmengenverhältnis kann anschaulich dargestellt werden:
* Wenn A ⊆ B, liegt die Fläche von A vollständig innerhalb von B.
* Wenn A und B disjunkt sind, überschneiden sich ihre Flächen nicht.

== Wichtige Sonderfälle ==
| Situation | Bedeutung |
|------------|------------|
| ∅ ⊆ A | Leere Menge ist immer Teilmenge |
| A ⊆ U | Jede Menge ist Teilmenge der Universalmenge |
| A ⊆ B und B ⊆ A | Dann gilt A = B |

== Zusammenhang mit Gleichheit ==
Das Teilmengenprinzip ist die Grundlage der **Gleichheitsdefinition**:
A = B ⇔ (A ⊆ B ∧ B ⊆ A)

Damit ist die Gleichheit zweier Mengen formal nichts anderes als gegenseitige Teilmengenbeziehung.

== Zusammenfassung ==
* A ⊆ B bedeutet: Alle Elemente von A sind in B enthalten.
* Die leere Menge ist Teilmenge jeder Menge.
* A = B gilt genau dann, wenn A ⊆ B und B ⊆ A.
* Teilmengen lassen sich visuell als vollständig enthaltene Bereiche darstellen.
* Das Teilmengenprinzip ist ein fundamentales Werkzeug in der Mengenlehre.

[[Category:Set Theory (Mengenlehre)]]

Mengen und Elemente: Mitgliedschaft, Extensionalität, Definitionen

2025-10-27T07:47:25Z

Bfh-sts: Created page with "= Mengen und Elemente = Die Grundidee der Mengenlehre besteht darin, Objekte – genannt **Elemente** – zu einer **Menge** zusammenzufassen. Diese Elemente können Zahlen, Buchstaben, Personen oder sogar andere Mengen sein. == Elemente und Zugehörigkeit == Die Zugehörigkeit eines Elements zu einer Menge wird mit dem Symbol **∈** ausgedrückt. Beispiele: * 3 ∈ {1, 2, 3, 4, 5} * a ∈ {a, b, c} * 6 ∉ {1, 2, 3, 4, 5} Die Zugehörigkeit ist immer eindeutig:..."

= Mengen und Elemente =
Die Grundidee der Mengenlehre besteht darin, Objekte – genannt **Elemente** – zu einer **Menge** zusammenzufassen.
Diese Elemente können Zahlen, Buchstaben, Personen oder sogar andere Mengen sein.

== Elemente und Zugehörigkeit ==
Die Zugehörigkeit eines Elements zu einer Menge wird mit dem Symbol **∈** ausgedrückt.

Beispiele:
* 3 ∈ {1, 2, 3, 4, 5}
* a ∈ {a, b, c}
* 6 ∉ {1, 2, 3, 4, 5}

Die Zugehörigkeit ist immer eindeutig:
Ein Element ist entweder in einer Menge enthalten oder nicht.

== Das Extensionalitätsaxiom ==
Zwei Mengen sind gleich, wenn sie dieselben Elemente enthalten.
Formell:
A = B ⇔ ∀x: (x ∈ A ⇔ x ∈ B)

Beispiel:
A = {1, 2, 3}
B = {3, 2, 1}
Da beide Mengen dieselben Elemente enthalten, gilt:
A = B

== Definition von Mengen ==
Es gibt zwei grundlegende Arten, eine Menge zu definieren:

=== 1. Explizite (aufzählende) Definition ===
Die Elemente werden direkt angegeben:
A = {a, b}
B = {1, 2, 3, 4, 5}
C = {1, 2, a, b, c}

=== 2. Intensionale (beschreibende) Definition ===
Die Elemente werden durch eine Eigenschaft beschrieben:
B = {n : n ∈ ℤ ∧ n > 5}
Das liest man:
„B ist die Menge aller ganzen Zahlen n, für die n größer als 5 ist.“

Hierbei:
* Der Buchstabe (z. B. n) steht für ein typisches Element.
* Der Doppelpunkt „:“ bedeutet „mit der Eigenschaft“.

== Beispiele ==
=== Beispiel 1 ===
Welche der folgenden Mengen sind gleich?
A = {a, b}
B = {b, a}
C = {a}
D = {1, 2, 3, 4, 5}
E = {n : n ∈ ℤ ∧ 1 ≤ n ≤ 5}
F = {x : x ∈ ℝ ∧ x² − 3x + 2 = 0}
G = {1, 4/2}

Lösungsidee:
* A und B enthalten dieselben Elemente → A = B
* D und E beschreiben dieselbe Menge → D = E
* F enthält die Nullstellen der Gleichung x² − 3x + 2 = 0 → F = {1, 2}
* G = {1, 2}
→ F = G

=== Beispiel 2 ===
A = {x : x ∈ ℝ ∧ x² + 1 = 0}
Da es keine reellen Zahlen gibt, deren Quadrat + 1 = 0 ergibt, ist:
A = ∅

== Leere Menge ==
Die **leere Menge** ist die Menge ohne Elemente.
Notation:
∅ oder {}

Eigenschaften:
* ∅ ⊆ A für jede Menge A
* |∅| = 0

== Universalmenge ==
Die **Universalmenge (U)** enthält alle in einem bestimmten Kontext relevanten Elemente.
Beispiele:
* In der Geometrie: alle Punkte einer Ebene
* In der Analysis: alle reellen Zahlen
* In der Informatik: alle möglichen Zustände oder Datenelemente

Wenn nichts anderes angegeben ist, bezeichnen wir die Universalmenge mit **U**.

== Zusammenfassung ==
* Elemente sind die Bausteine einer Menge.
* Eine Menge ist durch ihre Elemente eindeutig bestimmt (Extensionalitätsaxiom).
* Mengen können explizit oder durch Eigenschaften beschrieben werden.
* Die leere Menge (∅) enthält keine Elemente.
* Die Universalmenge (U) enthält alle betrachteten Elemente.

[[Category:Set Theory (Mengenlehre)]]

Mengenlehre: Überblick & Notation

2025-10-27T07:45:39Z

Bfh-sts: Created page with "= Mengenlehre: Überblick & Bedeutung = Die Mengenlehre ist ein grundlegendes Teilgebiet der Mathematik, das von **Georg Cantor (1845–1918)** im 19. Jahrhundert entwickelt wurde. Sie bildet das Fundament nahezu aller modernen mathematischen Disziplinen. Jede mathematische Struktur – von Zahlen über Funktionen bis zu geometrischen Objekten – kann in der Sprache der Mengenlehre formuliert werden. == Ursprung und Idee == Cantor definierte den Begriff der Menge f..."

= Mengenlehre: Überblick & Bedeutung =
Die Mengenlehre ist ein grundlegendes Teilgebiet der Mathematik, das von **Georg Cantor (1845–1918)** im 19. Jahrhundert entwickelt wurde.
Sie bildet das Fundament nahezu aller modernen mathematischen Disziplinen.
Jede mathematische Struktur – von Zahlen über Funktionen bis zu geometrischen Objekten – kann in der Sprache der Mengenlehre formuliert werden.

== Ursprung und Idee ==
Cantor definierte den Begriff der Menge folgendermaßen:
> Unter einer Menge verstehen wir jede Zusammenfassung von bestimmten, wohlunterschiedlichen Objekten unserer Anschauung oder unseres Denkens (welche Elemente der Menge genannt werden) zu einem Ganzen.

Diese Definition erlaubt es, sowohl konkrete als auch abstrakte Objekte als Elemente zu betrachten.
Beispiele für Mengen:
* Die Menge der Planeten im Sonnensystem
* Die Menge der geraden natürlichen Zahlen größer als 2, die sich als Summe zweier Primzahlen schreiben lassen
* Die Menge aller reellen Zahlen x mit x > 5
* Die Menge der Studierenden an der BFH-TI Biel

== Notation ==
* Mengen werden mit **Großbuchstaben** bezeichnet (A, B, C, …).
* Elemente werden mit **Kleinbuchstaben** bezeichnet (a, b, c, …).
* Die Aussage „a ist Element von A“ schreibt man als:
a ∈ A
Die Negation lautet:
a ∉ A

Eine Menge ist durch ihre Elemente vollständig bestimmt.
Dieses Prinzip wird als **Extensionalitätsaxiom** bezeichnet:
> Zwei Mengen A und B sind genau dann gleich, wenn sie dieselben Elemente enthalten.

Formal:
A = B ⇔ ∀x: (x ∈ A ⇔ x ∈ B)

== Arten der Mengendefinition ==
Es gibt zwei grundlegende Arten, Mengen zu definieren:

=== 1. Aufzählende (explizite) Definition ===
Alle Elemente werden direkt aufgelistet:
A = {a, b, x, y, z}
B = {1, 2, 3, 4, 5}

=== 2. Beschreibende (intensionale) Definition ===
Die Elemente werden durch eine Eigenschaft charakterisiert:
B = {n : n ∈ ℤ ∧ n > 5}
„B ist die Menge aller ganzen Zahlen n, für die n > 5 gilt.“

Der Doppelpunkt „:“ bedeutet „mit der Eigenschaft“ oder „so dass“.

== Wichtige Symbole ==
| Symbol | Bedeutung |
|---------|------------|
| ∈ | ist Element von |
| ∉ | ist kein Element von |
| ⊆ | ist Teilmenge von |
| ⊂ | ist echte Teilmenge von |
| ∅ | leere Menge |
| U | Universalmenge |

== Leere Menge und Universalmenge ==
* **Leere Menge (∅)**: enthält keine Elemente.
∅ = {}
* **Universalmenge (U)**: enthält alle in einem Kontext betrachteten Objekte.
Beispiele:
* In der Geometrie: alle Punkte der Ebene
* In der Analysis: alle reellen Zahlen

== Bedeutung in der Informatik ==
Mengen sind auch in der Informatik zentral:
* zur Beschreibung von Zustandsräumen
* zur Definition von Datenmengen und Relationen
* für logische Operationen (UND, ODER, NICHT) in Boolescher Algebra
* als Grundlage für Datenbanktheorie und Mengenoperationen (SELECT, UNION, INTERSECT)

== Zusammenfassung ==
* Die Mengenlehre ist das Fundament der Mathematik.
* Mengen sind Sammlungen von klar unterscheidbaren Objekten.
* Die Mitgliedschaft (∈) ist das zentrale Konzept.
* Mengen können durch Aufzählung oder Eigenschaft definiert werden.
* Leere Menge (∅) und Universalmenge (U) sind wichtige Spezialfälle.

[[Category:Set Theory (Mengenlehre)]]

Category:Set Theory (Mengenlehre)

2025-10-27T07:43:48Z

Bfh-sts: Created page with "Diese Kategorie deckt grundlegende Inhalte der Mengenlehre ab: Definitionen, Notation, Teilmengen, Vereinigungen/Schnitte/Komplemente, Mengenalgebra und Dualität, Potenzmengen und Partitionen, kartesische Produkte und Tupel sowie endliche Mengen und die Einschluss-Ausschluss-Formel. == Seiten == * Mengenlehre: Überblick & Notation * Mengen und Elemente: Mitgliedschaft, Extensionalität, Definitionen * Teilmengen und Gleichheit von Mengen * Vereinigung, D..."

Diese Kategorie deckt grundlegende Inhalte der Mengenlehre ab: Definitionen, Notation, Teilmengen, Vereinigungen/Schnitte/Komplemente, Mengenalgebra und Dualität, Potenzmengen und Partitionen, kartesische Produkte und Tupel sowie endliche Mengen und die Einschluss-Ausschluss-Formel.

== Seiten ==
* [[Mengenlehre: Überblick & Notation]]
* [[Mengen und Elemente: Mitgliedschaft, Extensionalität, Definitionen]]
* [[Teilmengen und Gleichheit von Mengen]]
* [[Vereinigung, Durchschnitt, Differenz und Komplement (inkl. Disjunktheit)]]
* [[Mengenalgebra & Dualität: Gesetze und de Morgan]]
* [[Mengensysteme, Potenzmenge & Partitionen]]
* [[Geordnete Paare, n-Tupel & kartesische Produkte]]
* [[Endliche Mengen & Einschluss-Ausschluss-Prinzip]]

[[Category:Diskrete Mathematik I (BZG1155pa) 25/26]]

Category:Diskrete Mathematik I (BZG1155pa) 25/26

2025-10-27T07:29:58Z

Bfh-sts:

= Overview =
This is the category of the BFH module Diskrete Mathematik I (BZG1155pa) 25/26.

= Topics =
* [[:Category: Propositional logic (Aussagenlogik)‎]]
* [[:Category: Set Theory (Mengenlehre)‎]]

== Propositional logic - Exercises ==
* [[Exercises - 01 Kontrollaufgaben]]
* [[Exercises - 02 Kontrollaufgaben]]

[[Category:Sidebar]]

Exercises - 02 Kontrollaufgaben

2025-10-20T13:57:18Z

Bfh-sts: Created page with "= Kontrollaufgaben Aussagenlogik Teil 2 = ''Achtung: detaillierte Lösungswege mit Zwischenresultaten werden erwartet. Ohne klar ersichtlichen Lösungsweg bzw. Begründung gibt es keine Punkte.'' == Aufgabe 1 == Max wird mit hohem Fieber und ausgeprägtem Gliederschmerzen in das Spital eingeliefert. Dr. House diskutiert die Diagnose mit einer Kollegin. * Dr. House: „Wenn der Patient Fieber hat, handelt es sich um Grippe oder Erkältung.” * Cameron: „Wenn er kein..."

= Kontrollaufgaben Aussagenlogik Teil 2 =

''Achtung: detaillierte Lösungswege mit Zwischenresultaten werden erwartet. Ohne klar ersichtlichen Lösungsweg bzw. Begründung gibt es keine Punkte.''

== Aufgabe 1 ==
Max wird mit hohem Fieber und ausgeprägtem Gliederschmerzen in das Spital eingeliefert. Dr. House diskutiert die Diagnose mit einer Kollegin.

* Dr. House: „Wenn der Patient Fieber hat, handelt es sich um Grippe oder Erkältung.”
* Cameron: „Wenn er keine starken Gliederschmerzen hat, dann hat er keine Grippe.”
* Dr. House: „Hohes Fieber und starke Gliederschmerzen weisen auf Grippe hin.”
* Cameron: „Er hat sicher nicht beide Krankheiten gleichzeitig.”

Verwenden Sie:
<syntaxhighlight lang='text'>
F = Patient hat Fieber
S = Patient hat Gliederschmerzen
G = Patient hat Grippe
E = Patient leidet unter einer Erkältung
</syntaxhighlight>

=== (a) Formalisierung (4 Punkte) ===
# F → (G ∨ E)
# ¬S → ¬G
# (F ∧ S) → G
# ¬(G ∧ E)

=== (b) Diagnose mit Begründung (4 Punkte) ===
Max hat F = wahr und S = wahr.

* Aus (3): (F ∧ S) → G. Da F und S wahr, folgt G = wahr.
* Aus (4): ¬(G ∧ E). Da G = wahr, muss E = falsch gelten.
* (1) ist erfüllt, da F → (G ∨ E) = wahr.
* (2) ist erfüllt, da ¬S = falsch ⇒ Implikation wahr.

'''Diagnose:''' Grippe (G = wahr), keine Erkältung (E = falsch).

Tabelle für F = w, S = w:

{| class="wikitable"
! F !! S !! G !! E !! Erfüllt alle 4 Bedingungen?
|-
| w || w || w || w || nein (verletzt 4)
|-
| w || w || w || f || '''ja'''
|-
| w || w || f || w || nein (verletzt 3)
|-
| w || w || f || f || nein (verletzt 3)
|}

== Aufgabe 2 ==
Brown, Jones und Smith werden verdächtigt.

<syntaxhighlight lang='bash'>
Brown: “Jones ist schuldig und Smith ist unschuldig.”
Jones: “Wenn Brown schuldig ist, ist es Smith auch.”
Smith: “Ich bin unschuldig, aber mindestens einer der anderen ist schuldig.”
</syntaxhighlight>

<syntaxhighlight lang='text'>
B = Brown ist unschuldig
J = Jones ist unschuldig
S = Smith ist unschuldig
(Schuldig = Negation)
</syntaxhighlight>

=== (a) Formeln und Wahrheitstabelle (6 Punkte) ===
* Brown: ¬J ∧ S
* Jones: (¬B) → (¬S)
* Smith: S ∧ (¬B ∨ ¬J)

{| class="wikitable"
! B !! J !! S !! Brown (¬J ∧ S) !! Jones ((¬B) → (¬S)) !! Smith (S ∧ (¬B ∨ ¬J))
|-
| f || f || f || f || t || f
|-
| f || f || t || t || t || t
|-
| f || t || f || f || t || f
|-
| f || t || t || f || t || t
|-
| t || f || f || f || f || f
|-
| '''t''' || '''f''' || '''t''' || '''t''' || '''t''' || '''t'''
|-
| t || t || f || f || t || f
|-
| t || t || t || f || t || f
|}

=== (b) Auswertung (je 1 Punkt) ===
<syntaxhighlight lang='text'>
(i) Konsistenz: Ja, z. B. B = t, J = f, S = t.
(ii) Aus Browns Aussage folgt Smiths Aussage.
(iii) Alle unschuldig (B = J = S = t): Brown = falsch, Jones = wahr, Smith = falsch → Brown und Smith lügen.
(iv) Alle Aussagen wahr: B = t, J = f, S = t → Brown und Smith unschuldig, Jones schuldig.
(v) „Wahrheit bei Unschuldigen, Lüge bei Schuldigen“ → Lösung: B = f (schuldig), J = t (unschuldig), S = f (schuldig).
</syntaxhighlight>

== Aufgabe 3 ==
<syntaxhighlight lang='text'>
A = Grizzlybären gesichtet
B = Wandern sicher
C = Beeren reif
</syntaxhighlight>

<syntaxhighlight lang='text'>
(a) Die Beeren entlang des Wanderwegs sind reif, aber es wurden keine Grizzlybären in der Gegend gesichtet.
(b) Falls die Beeren entlang des Wanderwegs reif sind, dann ist das Wandern auf dem Wanderweg genau dann sicher, wenn keine Grizzlybären in der Gegend gesichtet wurden.
(c) Damit das Wandern auf dem Wanderweg sicher ist, ist es notwendig, aber nicht hinreichend, dass die Beeren nicht reif sind, und dass keine Grizzlybären in der Gegend gesichtet wurden.
</syntaxhighlight>

<syntaxhighlight lang='text'>
(a) C ∧ ¬A
(b) C → (B ↔ ¬A)
(c) (B → (¬C ∧ ¬A)) ∧ ¬((¬C ∧ ¬A) → B)
</syntaxhighlight>

== Aufgabe 4 ==
<syntaxhighlight lang='text'>
(a) ( P → (Q → R) ) ↔ ( (P → Q) → R )
</syntaxhighlight>

<syntaxhighlight lang='text'>
(b) Falsch. Die Wahrheitstabellen der beiden Seiten sind nicht gleich.
Für P = f, Q = w, R = f stimmt das Gesetz nicht:
</syntaxhighlight>
{| class="wikitable"
! P !! Q !! R !! ( P → (Q → R) ) !! ( (P → Q) → R )
|-
| w || w || w || w || w
|-
| w || w || f || f || f
|-
| w || f || w || w || w
|-
| w || f || f || w || w
|-
| f || w || w || w || w
|-
| style='background-color:#ff6969' | f || style='background-color:#ff6969' | w || style='background-color:#ff6969' | f || style='background-color:#ff6969' | w || style='background-color:#ff6969'| f
|-
| f || f || w || w || w
|-
| f || f || f || w || w
|}

[[Category: Propositional logic (Aussagenlogik)‎]]

Exercises - 01 Kontrollaufgaben

2025-10-20T13:57:03Z

Bfh-sts: Created page with "= Kontrollaufgaben = == Aufgabe 1 == Wenden Sie in den folgenden logischen Ausdrücken die Verneinung auf die Einzelaussagen an: (a) <syntaxhighlight lang='text' inline>¬(¬A ᐯ B)</syntaxhighlight> (b) <syntaxhighlight lang='text' inline>¬(A ⇒ (B ⇒ C))</syntaxhighlight> === Aufgabe 1 - Lösung === a) <syntaxhighlight lang='text'> ¬(¬A ᐯ B) ≡ A ᐱ ¬B (7,10b) </syntaxhighlight> b) <syntaxhighlight lang='text'> (A => (B => C)) ≡ ¬(¬A ᐯ (B => C))..."

= Kontrollaufgaben =
== Aufgabe 1 ==
Wenden Sie in den folgenden logischen Ausdrücken die Verneinung auf die
Einzelaussagen an:

(a) <syntaxhighlight lang='text' inline>¬(¬A ᐯ B)</syntaxhighlight>

(b) <syntaxhighlight lang='text' inline>¬(A ⇒ (B ⇒ C))</syntaxhighlight>

=== Aufgabe 1 - Lösung ===
a)
<syntaxhighlight lang='text'>
¬(¬A ᐯ B) ≡ A ᐱ ¬B (7,10b)
</syntaxhighlight>
b)
<syntaxhighlight lang='text'>
(A => (B => C))
≡ ¬(¬A ᐯ (B => C))
≡ ¬(¬A ᐯ (¬B ᐯ C))
≡ A ᐱ ¬(¬B ᐯ C) (7, 10b)
≡ A ᐱ B ᐱ ¬C (7, 10b)
</syntaxhighlight>

== Aufgabe 2 ==
Aufgabe 2 Beweise Sie, dass <syntaxhighlight lang='text' inline>¬(A => B) => ¬B</syntaxhighlight> eine Tautologie ist.

(a) Beweisen Sie dies mit einer Wahrheitstabelle.

(b) Beweisen Sie dies durch Termumformung. Geben Sie an, welche logischen Gesetze
Sie verwenden.
=== Aufgabe 2 - Lösung ===
a)
{| class="wikitable"
! A !! B !! ¬A ᐯ B !! A ᐯ ¬B !! ¬B !! ¬(A => B) => ¬ B
|-
| w || w || w || f || f || w
|-
| w || f || f || w || w || w
|-
| f || w || w || f || f || w
|-
| f || f || w || f || w || w
|}

b)
<syntaxhighlight lang=text>
¬(A => B) => ¬B
≡ ¬(¬A ᐯ B) => ¬B
≡ ¬(¬(¬A ᐯ B) ᐯ ¬B)
≡ ¬(A ᐱ ¬B) ᐯ ¬B) (7, 10b)
≡ ¬A ᐯ B ᐯ ¬B (7, 10b)
≡ ¬A ᐯ T (8b)
≡ T (5b)
</syntaxhighlight>

== Aufgabe 3 ==
Aufgabe 3 Drei Kisten werden Ihnen präsentiert. Eine enthält Gold, die beiden anderen sind leer. Auf jeder Kiste ist ein Hinweis auf dessen Inhalt aufgedruckt:
* Hinweis auf Kiste 1: ”Das Gold ist nicht hier”
* Hinweis auf Kiste 2: ”Das Gold ist nicht hier”
* Hinweis auf Kiste 3: ”Das Gold ist in Kiste 2”

Nur eine dieser drei Aussage ist wahr, die beiden anderen sind falsch.

In welcher Kiste befindet sich das Gold? Formalisieren Sie das Rätsel in Aussagenlogik
und finden Sie die Lösung.

=== Aufgabe 3 - Lösungen ===
;G<sub>i</sub>: Gold ist in der <sub>i</sub>ten Kiste.
;H<sub>i</sub>: Hinweis i ist korrekt.

* G<sub>3</sub> => H<sub>1</sub> ᐱ H<sub>2</sub>
* G<sub>2</sub> => H<sub>1</sub> ᐱ H<sub>3</sub>
* G<sub>1</sub> => H<sub>2</sub>

Nur 1 Hinweis kann richtig sein. Somit ist das Gold in Kiste 1 (G<sub>1</sub>)

[[Category: Propositional logic (Aussagenlogik)‎]]

Main Page

2025-10-20T13:56:05Z

Bfh-sts:

= Welcome to the BFH BSCCS Documentation Wiki =

'''Bachelor of Science – Computer Science (BSCCS)'''
__NOTOC__

<div style="display:flex; gap:1em; align-items:flex-start;">


<div style="flex:0 0 35%; min-width:200px; border:1px solid #ccc; background-color:#f9f9f9; padding:1em; border-radius:8px;">

== Important Links ==
<div style="margin-bottom:1em;">
* [https://moodle.bfh.ch/ BFH Moodle]
* [https://gitlab.ti.bfh.ch BFH GitLab]
* [https://discord.gg/wAMseEVDcS BSCCS Discord Server]
* [https://campusapp.bfh.ch Camputs App]
* [https://is-a.bfh.ch IS-A]
* [https://www.bfh.ch/en/ Bern University of Applied Sciences]
* [[:Category:Modules|All Modules Overview]]
</div>

<hr style="margin:1em 0;">

== Create or Add Content ==
You can help expand the wiki by creating a new page.

Create a blank page.
<div style="float:left;">
<inputbox>
type=create
width=40
buttonlabel=Create blank page
break=no
</inputbox>
</div>
<br style="clear:both;">

For those unfamiliar with the MediaWiki Syntax:
* [[MediaWiki cheat sheet]]

<div style="margin-top:1em; font-size:90%; color:#555;">
Pages can also be created by visiting a non-existent link and selecting "Create this page".
</div>

<hr style="margin:1em 0;">

<div style="text-align:center; margin-top:1em;">
[[File:this is fine.jpg|link=|300px]]
</div>

</div>


<div style="flex:1;">

<div style="border:2px solid #4F81BD; background-color:#F5F9FF; padding:1em; border-radius:10px; margin-bottom:1em;">
'''Welcome!'''
This wiki serves as the central knowledge base for the '''Bern University of Applied Sciences – Bachelor of Science in Computer Science (BFH BSCCS)''' program.
Here you’ll find course summaries, module documentation, guides, and shared learning materials.

''This wiki is currently a work in progress (W.I.P.) – your contributions are encouraged and appreciated.''
</div>

== About This Wiki ==
This is a collaborative documentation project maintained by BSCCS students and staff.
Its goals include:
* Collecting resources, summaries, and notes for each BSCCS module
* Sharing experiences and study tips
* Building a living reference for future cohorts

== Modules ==
Below is a list of the BSCCS modules (placeholders – feel free to add content):

* [[:Category: Kommunikation 1 Deutsch für die Informatik (BZG3110p) 25/26]]
* [[:Category: Programming 1 with Java (BTI1001q) 25/26]]
* [[:Category: Diskrete Mathematik I (BZG1155pa) 25/26]]
* [[:Category: Computer Science Basics (BTI1021p) 25/26]]

> Click a module name to view or create its documentation page.

== Contributing ==
All students are invited to contribute.
Every edit improves the shared knowledge base for the BSCCS community.

<div style="border-left:4px solid #4F81BD; background:#EEF6FF; padding:0.8em; border-radius:5px;">
'''How to get started:'''
# Join the official Discord server – [https://discord.gg/wAMseEVDcS Join here]
# Find the wiki login credentials in the '''#wiki-access''' channel
# Log in and start editing or creating pages
</div>

== Work in Progress ==
This wiki is under continuous development.
Some pages may be incomplete or under review.
Contributions of any size are valuable and help make this a stronger resource for everyone.

<div style="text-align:center; margin-top:1em; font-size:110%; font-weight:bold;">
Your contributions benefit all BSCCS students — start today.
</div>

</div> 
</div> 

----

<small>Maintained by BFH Computer Science Students • Last updated: {{CURRENTDAY}} {{CURRENTMONTHNAME}} {{CURRENTYEAR}}</small>

Category:Numeral Systems

2025-10-20T13:52:12Z

Bfh-sts:

= Overview =
This category covers positional numeral systems used in computing (binary, octal, hexadecimal), conversions between bases, size prefixes, and byte order.

== Pages ==
* [[Numeral Systems: Overview & Positional Notation]]
* [[Binary: Bits, Grouping & Powers of Two]]
* [[Octal: Reading & Conversion]]
* [[Hexadecimal: Reading, Arithmetic & Shorthand for Binary]]
* [[Base Conversions: Decimal, Binary, Octal, Hex]]
* [[Memory Sizes & Binary Prefixes]]
* [[Endianness: Byte Order & Practice]]

[[Category:Computer Science Basics (BTI1021p) 25/26]]

Hands-on: Debugger Exercise for Register Parts (AX/BX/CX)

2025-10-20T13:49:00Z

Bfh-sts: Created page with "= Hands-on: Debugger Exercise for Register Parts (AX, BX, CX) = This exercise helps you understand how register hierarchies and partial register operations work in x86-64 assembly. It focuses on how smaller register portions (8-bit and 16-bit) affect and reflect values in their parent registers. == Background == <syntaxhighlight lang='text'> x86-64 registers are divided into accessible parts: | Register (64-bit) | 32-bit | 16-bit | 8-bit High | 8-bit Low | |----------..."

= Hands-on: Debugger Exercise for Register Parts (AX, BX, CX) =
This exercise helps you understand how register hierarchies and partial register operations work in x86-64 assembly.
It focuses on how smaller register portions (8-bit and 16-bit) affect and reflect values in their parent registers.

== Background ==
<syntaxhighlight lang='text'>
x86-64 registers are divided into accessible parts:
| Register (64-bit) | 32-bit | 16-bit | 8-bit High | 8-bit Low |
|--------------------|---------|---------|-------------|------------|
| RAX | EAX | AX | AH | AL |
| RBX | EBX | BX | BH | BL |
| RCX | ECX | CX | CH | CL |
| RDX | EDX | DX | DH | DL |
</syntaxhighlight>
When modifying a smaller register:
* The value also updates the corresponding part of the larger register.
* For 32-bit writes (e.g. `mov eax, value`), the upper 32 bits of the 64-bit register are cleared to 0.
* For 8-bit and 16-bit writes, only the corresponding bytes are affected.

== Exercise: Register Interaction ==
Assemble and run the following program step by step in a debugger (like GDB).

SECTION .text
global _start
_start:
mov ax, 67FEh ; AX = 67FEh
mov bx, ax ; BX = 67FEh
mov cl, bh ; CL = upper byte of BX = 67h
mov ch, bl ; CH = lower byte of BX = FEh

; Stop execution (infinite loop)
loop:
jmp loop

== Step-by-step in a Debugger ==
1. Set a breakpoint at `_start`.
2. Run the program and step through each instruction.
3. After each step, inspect register values:
- `info registers` (GDB)
- Observe AX, BX, CX and their 8-bit components (AH, AL, BH, BL, CH, CL).

You should see:
* AX = 0x67FE
* BX = 0x67FE
* CX = 0xFE67
- CH = 0xFE (from BL)
- CL = 0x67 (from BH)

== Explanation ==
Each register’s 16-bit portion (AX, BX, CX) is composed of two 8-bit halves:
* High byte (e.g., AH, BH, CH)
* Low byte (e.g., AL, BL, CL)

The instruction `mov cl, bh` copies only the upper 8 bits of BX (BH) into CL.
This behavior is key when dealing with partial data movement or I/O operations on specific bytes.

== Important Notes ==
* Writing to 32-bit registers clears the upper 32 bits of the 64-bit register.
* Writing to 8-bit or 16-bit registers only affects those parts.
* Be careful when mixing operations on different sizes — this can lead to unexpected values.

== Experiment Ideas ==
* Modify the code to use 32-bit registers (EAX, EBX, ECX) and observe clearing of upper bits.
* Add `mov eax, 0xFFFFFFFF` followed by `mov al, 0x10` to see how AL overwrites the low byte.
* Try using `movsx` to extend signed 8-bit values into 16-bit or 32-bit registers.

== Key Takeaways ==
* Registers are hierarchical — each smaller part reflects within its parent.
* High and low bytes allow efficient byte-level manipulation.
* Debugging at the register level builds intuition for assembly operations.

[[Category:Assembly Programming]]

Linux x86-64 Syscalls: syscall, Registers, sys write, sys exit

2025-10-20T13:48:43Z

Bfh-sts: Created page with "= Linux x86-64 Syscalls (syscall, Registers, sys_write, sys_exit) = System calls (syscalls) allow a program to interact directly with the operating system. They provide controlled access to privileged functions such as printing to the screen, reading files, or terminating the program. == What Is a Syscall? == In user mode, a program cannot directly access hardware or kernel resources. To perform privileged operations, it must **request** the kernel to do so on its b..."

= Linux x86-64 Syscalls (syscall, Registers, sys_write, sys_exit) =
System calls (syscalls) allow a program to interact directly with the operating system.
They provide controlled access to privileged functions such as printing to the screen, reading files, or terminating the program.

== What Is a Syscall? ==
In user mode, a program cannot directly access hardware or kernel resources.
To perform privileged operations, it must **request** the kernel to do so on its behalf.

A syscall is this request mechanism.

When the instruction `syscall` executes:
1. Control switches from user mode to kernel mode.
2. The CPU looks at specific registers to determine which system service to execute.
3. After completion, control returns to user mode.

== The syscall Instruction ==
`syscall` has no operands.
It uses the values in registers to know:
* which function to perform (via `rax`)
* which parameters to use (via other registers)

== Register Usage (System V AMD64 ABI) ==
<syntaxhighlight lang='text'>
| Register | Purpose |
|-----------|----------|
| rax | System call number |
| rdi | 1st argument |
| rsi | 2nd argument |
| rdx | 3rd argument |
| r10 | 4th argument |
| r8 | 5th argument |
| r9 | 6th argument |
</syntaxhighlight>
All other registers may be modified by the syscall.

== Common Syscall Numbers ==
<syntaxhighlight lang='text'>
| Syscall | rax Value | Description |
|----------|------------|-------------|
| sys_read | 0 | Read from a file descriptor |
| sys_write | 1 | Write to a file descriptor |
| sys_exit | 60 | Terminate the process |
</syntaxhighlight>
Syscall numbers are defined in `/usr/include/asm/unistd_64.h`.

== Example: sys_write ==
Writes data to a file descriptor (e.g., standard output).

Example:
<syntaxhighlight lang='asm'>
SECTION .data
Msg: db "Eat at Joe’s!", 10
MsgLen: equ $ - Msg

SECTION .text
global _start
_start:
mov rax, 1 ; syscall number for sys_write
mov rdi, 1 ; file descriptor (stdout)
mov rsi, Msg ; pointer to string
mov rdx, MsgLen ; length of string
syscall ; invoke kernel

The string is printed to the terminal.
</syntaxhighlight>
== Example: sys_exit ==
Ends the program cleanly and returns a status code to the OS.

Example:
<syntaxhighlight lang='asm'>
mov rax, 60 ; syscall number for sys_exit
xor rdi, rdi ; status code 0
syscall
</syntaxhighlight>
If `rdi` is nonzero, it becomes the program’s exit code.

== Full Example: eatsyscall64.asm ==
<syntaxhighlight lang='asm'>
SECTION .data
EatMsg: db "Eat at Joe’s!",10
EatLen: equ $ - EatMsg

SECTION .text
global _start
_start:
mov rax, 1 ; sys_write
mov rdi, 1 ; stdout
mov rsi, EatMsg
mov rdx, EatLen
syscall

mov rax, 60 ; sys_exit
mov rdi, 0
syscall
</syntaxhighlight>
== Syscall Workflow Summary ==
1. Load syscall number into `rax`.
2. Load arguments into `rdi`, `rsi`, `rdx`, etc.
3. Execute the `syscall` instruction.
4. Handle results or exit.

== Common Mistakes ==
* Forgetting to set `rax` correctly before syscall.
* Not passing valid pointers in `rsi` or `rdi`.
* Forgetting to call `sys_exit`, causing a crash after execution.

== Summary ==
* Syscalls are the interface between user code and the Linux kernel.
* The `syscall` instruction uses registers to pass parameters.
* `sys_write` outputs data, `sys_exit` terminates the program.
* Proper use of registers and syscall numbers is crucial for functional programs.

[[Category:Assembly Programming]]

Strings in Assembly: Buffers, Length with $ and equ, Concatenation

2025-10-20T13:48:28Z

Bfh-sts: Created page with "= Strings in Assembly (Buffers, Length with $, equ, Concatenation) = Strings in assembly language are simply sequences of bytes in memory. Each byte may represent a character depending on the encoding (commonly ASCII or UTF-8). == What Is a String in Assembly? == A string is not a special data type — it is an array of bytes. The assembler does not automatically track the string’s length or add an end marker. Example: SECTION .data Msg: db "Eat at Joe’s!", 10..."

= Strings in Assembly (Buffers, Length with $, equ, Concatenation) =
Strings in assembly language are simply sequences of bytes in memory. Each byte may represent a character depending on the encoding (commonly ASCII or UTF-8).

== What Is a String in Assembly? ==
A string is not a special data type — it is an array of bytes.
The assembler does not automatically track the string’s length or add an end marker.

Example:
SECTION .data
Msg: db "Eat at Joe’s!", 10 ; define bytes for text plus newline

Each character occupies one byte. The `10` adds a line feed (LF, '\n') at the end.

Important points:
* No automatic end-of-string marker (unlike C’s `0x00`).
* Length must be tracked manually or computed.
* Each byte can be accessed by its address in memory.

== Defining Strings ==
You can define strings using `db`:
db "Hello, world!", 10
db 'A', 'B', 'C', 0

You can also mix numeric and text data:
db "A=", 65, 10

== Uninitialized String Buffers ==
In the **.bss** section, you can reserve space for strings without giving them content yet.

Example:
SECTION .bss
Buffer: resb 32 ; reserve 32 bytes for a string

The memory is allocated but initialized to zero at runtime.

== Calculating String Length ==
Assembly provides a powerful special symbol `$`, meaning “the current address during assembly.”

If you subtract two labels, NASM computes the byte distance between them — useful for string lengths.

Example:
SECTION .data
Msg: db "Eat at Joe’s!"
MsgLen: equ $ - Msg ; calculates the length automatically

Equivalent to `mov rdx, 13`, but automatically updates if the string changes.

== The equ Directive ==
`equ` assigns a symbolic name to a value.
Used with `$`, it allows you to automatically define a string length constant.

Example:
Text: db "Assembly Rocks!", 10
TextLen: equ $ - Text

Later in your code:
mov rdx, TextLen

== String Concatenation ==
Multiple strings or values can be joined using commas in one `db` statement.

Examples:
db "Eat at Joe’s!", 10
db "Come again!", 10

Or combined:
TwoLine: db "Eat at Joe’s ...", 10, "... tonight!", 10

Output:
Eat at Joe’s ...
... tonight!

== Strings and Encodings ==
Remember that strings are just bytes.
How they are interpreted depends on the encoding (e.g., ASCII, UTF-8).
Always ensure your output mechanism (syscall, terminal, etc.) expects the same encoding.

== Example Program ==
SECTION .data
Greeting: db "Hello, world!", 10
GreetLen: equ $ - Greeting

SECTION .text
global _start
_start:
mov rax, 1 ; sys_write
mov rdi, 1 ; stdout
mov rsi, Greeting
mov rdx, GreetLen
syscall

mov rax, 60 ; sys_exit
xor rdi, rdi
syscall

== Summary ==
* Strings are arrays of bytes — no null terminator by default.
* `$ - Label` gives the number of bytes (string length).
* `equ` defines constants, such as lengths.
* Strings can be split or concatenated using commas.
* Always know your encoding when printing or processing strings.

[[Category:Assembly Programming]]

Data Definition Directives: db, dw, dd, dq, equ

2025-10-20T13:48:15Z

Bfh-sts: Created page with "= Data Definition Directives (db, dw, dd, dq, equ) = Assembly language provides directives to define data in memory. These specify how many bytes are allocated and what values they hold. == Overview == Data definition directives do not generate executable code — they reserve and optionally initialize memory. They are primarily used in the **.data** and **.bss** sections. == Common Directives == <syntaxhighlight lang='text'> | Directive | Meaning | Size..."

= Data Definition Directives (db, dw, dd, dq, equ) =
Assembly language provides directives to define data in memory. These specify how many bytes are allocated and what values they hold.

== Overview ==
Data definition directives do not generate executable code — they reserve and optionally initialize memory.
They are primarily used in the **.data** and **.bss** sections.

== Common Directives ==

<syntaxhighlight lang='text'>
| Directive | Meaning | Size per Element | Typical Use |
|------------|-------------------|------------------|--------------------------------------|
| db | Define Byte | 1 byte | Characters, small values |
| dw | Define Word | 2 bytes | 16-bit integers |
| dd | Define Doubleword | 4 bytes | 32-bit integers or floats |
| dq | Define Quadword | 8 bytes | 64-bit integers, pointers |
| equ | Define Constant | none | Named constant, no memory allocation |
</syntaxhighlight>

== Examples ==
SECTION .data
MyByte: db 0x07 ; single byte (7)
MyWord: dw 0x0FFFF ; 16-bit value
MyDouble: dd 0x0B8000000 ; 32-bit value
MyQuad: dq 0x0B800000011000000 ; 64-bit value
Text: db "Assembly Rocks!",10 ; string with newline
Len: equ $ - Text ; calculate string length

== db — Define Byte ==
Defines one or more bytes. Each element can be a value, character, or string.

Example:
db 72, 101, 108, 108, 111, 0
db "Hello", 0

Each character literal expands to its ASCII value.
Strings can include escape sequences such as `10` for newline (LF).

== dw, dd, dq — Define Larger Values ==
These define 2, 4, or 8-byte values respectively.

Example:
dw 0x1234 ; 2 bytes
dd 0x12345678 ; 4 bytes
dq 0x1122334455667788 ; 8 bytes

They are often used for integers, addresses, or floating-point constants.

== equ — Define Constant ==
equ (short for *equate*) defines a constant symbol.
It **does not** allocate memory, but replaces the symbol with a numeric value at assembly time.

Example:
Count: equ 10
mov ec

Program Structure: .data, .bss, .text, global start

2025-10-20T13:48:02Z

Bfh-sts: Created page with "= Program Structure (.data, .bss, .text, global _start) = Assembly programs are organized into well-defined sections that separate code and data. Understanding this structure is crucial for writing, linking, and debugging NASM programs. == Overview == A typical x86-64 assembly program for GNU/Linux contains: * A **comment block** describing metadata * A **.data** section for initialized data * A **.bss** section for uninitialized data * A **.text** section for executabl..."

= Program Structure (.data, .bss, .text, global _start) =
Assembly programs are organized into well-defined sections that separate code and data. Understanding this structure is crucial for writing, linking, and debugging NASM programs.

== Overview ==
A typical x86-64 assembly program for GNU/Linux contains:
* A **comment block** describing metadata
* A **.data** section for initialized data
* A **.bss** section for uninitialized data
* A **.text** section for executable code
* A **global _start** label marking the entry point

== Comment Block ==
The top of an assembly source file often contains documentation for readability and maintenance.

Example:
; Executable name : eatsyscall64
; Version : 1.0
; Author : E. Benoist
; Description : A simple NASM Linux 64-bit program
; Build with:
; nasm -f elf64 -g -F dwarf eatsyscall64.asm
; ld -o eatsyscall64 eatsyscall64.o

== .data Section ==
This section holds **initialized data**, such as constants and strings.
Values are stored directly in the assembled file.

Example:
SECTION .data
Msg: db "Hello, world!", 10
MsgLen: equ $ - Msg

Characteristics:
* Contents are included in the binary.
* Used for read-only or predefined data.

== .bss Section ==
The **Block Started by Symbol (BSS)** section reserves space for uninitialized data.
It allocates memory at runtime but does not increase the program’s file size.

Example:
SECTION .bss
Buffer: resb 64 ; reserve 64 bytes
Counter: resq 1 ; reserve one 64-bit integer

Characteristics:
* Space allocated at runtime.
* Initialized to zero by the OS loader.

== .text Section ==
Contains the actual **executable instructions**.
This is where your program’s logic resides.

Example:
SECTION .text
global _start
_start:
mov rax, 1 ; sys_write
mov rdi, 1 ; stdout
mov rsi, Msg ; pointer to message
mov rdx, MsgLen ; message length
syscall
mov rax, 60 ; sys_exit
xor rdi, rdi
syscall

== The global _start Label ==
Every standalone Linux assembly program must define a global entry point called `_start`.
It is where execution begins when the operating system loads the program.

Example:
global _start
_start:
; program entry point
mov rax, 60
xor rdi, rdi
syscall

== Summary ==
* **.data** — constants and initialized data
* **.bss** — uninitialized variables (space reserved)
* **.text** — program code
* **_start** — entry point required by the linker

A correct section layout ensures that your code assembles and runs properly under Linux.

[[Category:Assembly Programming]]

Multiplication and Division (mul, imul, div, idiv)

2025-10-20T13:47:50Z

Bfh-sts: Created page with "= Multiplication and Division (mul, imul, div, idiv) = This page explains how integer multiplication and division work in x86-64 assembly. It covers unsigned and signed arithmetic, implicit operands, and register usage. == Multiplication instructions == There are two main multiplication instructions: * **mul** — for unsigned multiplication * **imul** — for signed multiplication Syntax examples: mul rbx imul rbx Both multiply the accumulator register (a-regist..."

= Multiplication and Division (mul, imul, div, idiv) =
This page explains how integer multiplication and division work in x86-64 assembly. It covers unsigned and signed arithmetic, implicit operands, and register usage.

== Multiplication instructions ==
There are two main multiplication instructions:

* **mul** — for unsigned multiplication
* **imul** — for signed multiplication

Syntax examples:
mul rbx
imul rbx

Both multiply the accumulator register (a-register) by the operand.

== Implicit operands ==
The a-register is always one operand. The second operand is specified by the programmer.

Depending on the operand size, the product is stored in two registers:

| Operand Size | Multiplicand | Product (result) |
|---------------|---------------|------------------|
| 8-bit | AL | AX |
| 16-bit | AX | DX:AX |
| 32-bit | EAX | EDX:EAX |
| 64-bit | RAX | RDX:RAX |

Example (unsigned):
mov rax, 5
mov rbx, 10
mul rbx ; RDX:RAX = 50
; RAX contains lower 64 bits, RDX contains higher bits

== Signed multiplication ==
The imul instruction handles signed operands using two’s complement arithmetic.

Example:
mov rax, 56
mov rbx, -67
imul rbx ; signed multiply → result in RDX:RAX

== Overflow handling ==
Because the product can exceed the operand size, overflow is stored in the upper register (DX, EDX, or RDX).
If RDX = 0 after multiplication, no overflow occurred.

Example:
mov rax, 0xFFFFFFFFFFFFFFFF ; 2⁶⁴ − 1
mov rbx, 2
mul rbx ; RDX:RAX = 1_FFFFFFFE (overflow)

== Division instructions ==
Two division instructions mirror multiplication:

* **div** — unsigned division
* **idiv** — signed division

The dividend must be in the accumulator pair (RDX:RAX, EDX:EAX, DX:AX, or AH:AL).

After division:
* Quotient → stored in A-register (AL, AX, EAX, RAX)
* Remainder → stored in D-register (AH, DX, EDX, RDX)

== Example (unsigned division) ==
mov rdx, 0 ; clear upper part
mov rax, 100 ; dividend = 100
mov rbx, 7 ; divisor = 7
div rbx ; quotient = 14 (RAX), remainder = 2 (RDX)

== Example (signed division) ==
mov rax, -100
cqo ; extend sign bit from RAX into RDX
mov rbx, 7
idiv rbx ; quotient = -14, remainder = -2

The **cqo** instruction (convert quadword to octoword) copies the sign bit of RAX into all bits of RDX, preparing the correct signed dividend.

== Common pitfalls ==
* Before **div/idiv**, always set or extend the upper register correctly (e.g., `xor rdx, rdx` or `cqo`).
* Dividing by zero raises a CPU exception.
* Overflow in multiplication affects flags (CF and OF set).

== Summary ==
* **mul / div** — unsigned
* **imul / idiv** — signed
* Use **RDX:RAX** for 64-bit operations
* Use **cqo** before signed division
* Check RDX for overflow and remainders

Mastering these ensures correct arithmetic handling for both signed and unsigned integers in x86-64 assembly.

[[Category:Assembly Programming]]

Sign Extension and Negation (movsx, neg)

2025-10-20T13:47:37Z

Bfh-sts: Created page with "= Sign Extension and Negation (movsx, neg) = This page explains how to handle signed numbers of different sizes and how to change their sign in x86-64 assembly. == Copying signed numbers == When using mov to copy signed numbers, the sign bit is not automatically extended to the larger register size. This can lead to incorrect values when moving smaller signed values into larger registers. Example: mov ax, -42 mov bx, ax ; bx = -42 (ok, same size) mov ecx, bx..."

= Sign Extension and Negation (movsx, neg) =
This page explains how to handle signed numbers of different sizes and how to change their sign in x86-64 assembly.

== Copying signed numbers ==
When using mov to copy signed numbers, the sign bit is not automatically extended to the larger register size.
This can lead to incorrect values when moving smaller signed values into larger registers.

Example:
mov ax, -42
mov bx, ax ; bx = -42 (ok, same size)
mov ecx, bx ; ecx = 65494 (wrong!)
; the negative value was reinterpreted as an unsigned 16-bit number

== movsx — move with sign extension ==
movsx copies a smaller signed value into a larger register while preserving its sign.

Syntax:
movsx destination, source

Example:
mov ax, -42
movsx edx, ax ; edx = -42 (correct)
movsx rbx, edx ; rbx = -42 (sign extended again)

The CPU copies the sign bit from the source to fill the unused higher bits in the destination register.

== movzx — move with zero extension ==
For unsigned values, movzx fills the upper bits with zeros.

Example:
mov al, 0xFF
movzx eax, al ; eax = 0x000000FF = 255

movzx is the correct instruction when working with unsigned data.

== Negation (neg instruction) ==
neg changes the sign of a signed value (computes two’s complement).
It subtracts the operand from zero: 0 − operand.

Syntax:
neg operand

Example:
mov rax, 42
neg rax ; rax = −42
add rax, 42 ; rax = 0

neg affects these flags:
* CF – set if operand ≠ 0
* SF – set if result is negative
* OF – set if signed overflow occurs
* ZF – set if result is 0

== Example combining movsx and neg ==
mov ax, -10
movsx eax, ax ; correctly sign-extend to 32-bit
neg eax ; change sign → +10

== Summary ==
* mov copies raw bits without sign extension.
* movsx extends signed values correctly to larger registers.
* movzx is for unsigned zero-extension.
* neg inverts the sign using two’s complement arithmetic.

These instructions are essential for correctly handling mixed data sizes and signed arithmetic in low-level programming.

[[Category:Assembly Programming]]

Signed Integers and Flags (Two’s Complement)

2025-10-20T13:47:24Z

Bfh-sts: Created page with "= Signed Integers and Flags (Two’s Complement) = This page explains how signed integers are represented in x86 architecture using two’s complement and how arithmetic instructions affect CPU flags. == Unsigned vs signed integers == Unsigned integers represent only positive values. Signed integers represent both positive and negative values using two’s complement. Example with 8 bits: * 00000000₂ = 0 * 00000001₂ = +1 * 01111111₂ = +127 * 11111111₂ = −1..."

= Signed Integers and Flags (Two’s Complement) =
This page explains how signed integers are represented in x86 architecture using two’s complement and how arithmetic instructions affect CPU flags.

== Unsigned vs signed integers ==
Unsigned integers represent only positive values.
Signed integers represent both positive and negative values using two’s complement.

Example with 8 bits:
* 00000000₂ = 0
* 00000001₂ = +1
* 01111111₂ = +127
* 11111111₂ = −1
* 11111110₂ = −2
* 10000000₂ = −128

In two’s complement, the most significant bit (MSB) is the sign bit:
* 0 = positive
* 1 = negative

== How two’s complement works ==
To negate a binary number:
1. Invert all bits.
2. Add 1 to the result.

Example: Convert +5 (00000101₂) to −5:
Invert → 11111010₂
Add 1 → 11111011₂ = −5

== Overflow and wrapping ==
When signed arithmetic exceeds the representable range, it wraps around and sets the overflow flag (OF).

Example:
mov eax, 0x7FFFFFFF ; largest positive 32-bit signed number
inc eax ; eax becomes 0x80000000 (−2147483648)
; Overflow occurs, OF = 1, SF = 1 (sign bit set)

Decrementing below the smallest value (e.g., −128 for 8-bit) wraps around to the largest positive value.

== Example: continuous decrement ==
mov eax, 0
loop2:
dec eax
jmp loop2

EAX changes as follows:
0x00000000 → 0xFFFFFFFF (−1)
→ 0xFFFFFFFE (−2)
→ 0xFFFFFFFD (−3)
and so on.

== Flags relevant for signed arithmetic ==
* SF (Sign Flag): set when result is negative (MSB = 1)
* ZF (Zero Flag): set when result is zero
* OF (Overflow Flag): set when signed overflow occurs
* CF (Carry Flag): used for unsigned overflow, not sign interpretation

== Summary ==
* Two’s complement represents negative numbers naturally.
* Arithmetic wraps around automatically.
* Signed overflow is detected via the Overflow Flag (OF).
* Understanding these flags is essential for conditional branching and comparisons.

[[Category:Assembly Programming]]

Arithmetic: add, sub, inc, dec

2025-10-20T13:47:12Z

Bfh-sts: Created page with "= Arithmetic: add, sub, inc, dec = This page explains basic arithmetic instructions in x86-64 assembly language, including addition, subtraction, increment, and decrement. == Overview == Arithmetic instructions modify register or memory contents. Most of them follow this general pattern: instruction destination, source The result is stored in the destination operand. == Addition (add) == Adds the source value to the destination and stores the result in the destinat..."

= Arithmetic: add, sub, inc, dec =
This page explains basic arithmetic instructions in x86-64 assembly language, including addition, subtraction, increment, and decrement.

== Overview ==
Arithmetic instructions modify register or memory contents.
Most of them follow this general pattern:
instruction destination, source

The result is stored in the destination operand.

== Addition (add) ==
Adds the source value to the destination and stores the result in the destination.

Syntax:
add destination, source

Examples:
add rax, rbx ; rax = rax + rbx
add r10, 4 ; r10 = r10 + 4
add [rcx], rdx ; memory at rcx = memory[rcx] + rdx

The instruction affects several CPU flags:
* CF (Carry Flag) – set if result exceeds register size.
* ZF (Zero Flag) – set if result is 0.
* SF (Sign Flag) – set if result is negative.
* OF (Overflow Flag) – set if signed overflow occurs.

== Subtraction (sub) ==
Subtracts the source value from the destination and stores the result in the destination.

Syntax:
sub destination, source

Examples:
sub rax, 1 ; rax = rax - 1
sub [rbx], rcx ; memory[rbx] = memory[rbx] - rcx

Like add, sub modifies the condition flags.

== Increment (inc) and Decrement (dec) ==
These are special cases of add and sub that modify the operand by 1.

Examples:
mov eax, 0xFFFFFFFF
inc eax ; eax becomes 0, sets ZF, PF, AF
mov ebx, 0x2D
dec ebx ; ebx becomes 0x2C, clears most flags

Usage:
* inc increases by 1 → useful for counters and loops.
* dec decreases by 1 → useful for iteration and countdowns.

== Example: simple loop ==
mov ecx, 5
loop_start:
dec ecx
jnz loop_start ; continue looping until ecx = 0

This uses dec and the Zero Flag (ZF) to control the loop.

== Notes on performance ==
While add/sub and inc/dec behave similarly, inc and dec do not modify the Carry Flag (CF).
For arithmetic where CF matters (e.g., multiword addition), use add/sub instead.

[[Category:Assembly Programming]]

Labels and Entry Point ( start)

2025-10-20T13:46:52Z

Bfh-sts: Created page with "= Labels and Entry Point (_start) = This page explains how labels work in assembly programming and how the program’s entry point is defined. == What are labels == A label is a symbolic name for a memory address. It marks a location in code or data that can be referenced later. Syntax: LabelName: Example: SECTION .data EatMsg: db "Eat at Joe’s" SECTION .text mov rcx, EatMsg ; rcx ← address of the string mov rdx, [EatMsg] ; rdx ← first 8 bytes of the..."

= Labels and Entry Point (_start) =
This page explains how labels work in assembly programming and how the program’s entry point is defined.

== What are labels ==
A label is a symbolic name for a memory address.
It marks a location in code or data that can be referenced later.

Syntax:
LabelName:

Example:
SECTION .data
EatMsg: db "Eat at Joe’s"

SECTION .text
mov rcx, EatMsg ; rcx ← address of the string
mov rdx, [EatMsg] ; rdx ← first 8 bytes of the string

Here:
* EatMsg refers to the address of the string.
* [EatMsg] refers to the contents at that address.

== Why labels are needed ==
Labels replace hardcoded addresses and make programs relocatable:
* You don’t know where in memory your program will be loaded.
* The linker can adjust label references automatically.
* The code becomes modular and position-independent.

== Code labels ==
Labels can also be attached to code lines.
They mark destinations for jumps and branches, forming the basis for control flow.

Example:
mov eax, 5
loop_start:
dec eax
jnz loop_start ; jump back if eax ≠ 0

Here, loop_start marks the instruction to jump to.
Such code labels are essential for loops, branches, and function calls.

== The _start label ==
_start: defines the entry point of an assembly program on Linux.
It is the first instruction executed when the program runs.

Example:
global _start
_start:
mov rax, 60 ; system call for exit
xor rdi, rdi ; return code 0
syscall

* The keyword global makes _start visible to the linker.
* The operating system looks for this symbol to know where to begin execution.

Every NASM program for Linux must define exactly one entry point, usually called _start.

== Summary ==
* Labels are symbolic names for addresses.
* Data labels point to memory locations.
* Code labels mark positions for jumps.
* The _start label defines where execution begins.

[[Category:Assembly Programming]]

Memory Operands in Other Instructions (add, etc.)

2025-10-20T13:46:38Z

Addressing Modes: Direct, Indirect, Base+Index, Offsets

2025-10-20T13:46:23Z

Bfh-sts: Created page with "= Addressing Modes: Direct, Indirect, Base+Index, Offsets = This page explains how different addressing modes work in x86-64 assembly and how they apply beyond the mov instruction. == Overview == Addressing modes define how operands are interpreted by the CPU: * **Immediate** – The value is part of the instruction itself. * **Register** – The operand is stored in a CPU register. * **Memory** – The operand is located in RAM, referenced by an address. Understanding..."

= Addressing Modes: Direct, Indirect, Base+Index, Offsets =
This page explains how different addressing modes work in x86-64 assembly and how they apply beyond the mov instruction.

== Overview ==
Addressing modes define how operands are interpreted by the CPU:
* **Immediate** – The value is part of the instruction itself.
* **Register** – The operand is stored in a CPU register.
* **Memory** – The operand is located in RAM, referenced by an address.

Understanding addressing modes is essential for efficient data access and struct or array manipulation.

== Immediate addressing ==
The constant value is embedded directly into the instruction.

Example:
mov rax, 42 ; load 42 directly into rax

Useful for initializing values or setting counters.

== Direct memory addressing ==
The instruction refers to a fixed memory address.

Example:
mov rax, [100] ; load from memory at address 100

Used for accessing global or static data at a known location.

== Register indirect addressing ==
A register holds the memory address to read from or write to.

Example:
mov [rbx], rax ; write the value of rax to the address stored in rbx

Commonly used for pointer-like behavior.

== Direct offset addressing ==
Adds a fixed offset to a base register to access a specific location in a structure.

Example:
mov [rbx+8], rax ; write to the field at offset 8 from base address in rbx

Useful when working with data structures or objects.

== Base + index addressing ==
Uses one register as a base address and another as an index.

Example:
mov rax, [rbx + rdi] ; read an array element

If each element has a size larger than one byte, a scaling factor can be used:
mov rax, [rbx + rdi*8] ; access 8-byte (64-bit) elements

== Addressing with other instructions ==
Many instructions other than mov can access memory operands directly.

Example:
add [rax], 10 ; add 10 to the value stored at memory address in rax

This single instruction:
1. Loads the value from memory at [rax].
2. Adds 10 to it.
3. Stores the result back to [rax].

== CISC vs. RISC note ==
x86-64 is a Complex Instruction Set Computer (CISC).
It allows instructions that perform multiple steps (like load + operate + store).
Internally, however, modern x86 CPUs translate these into smaller RISC-like operations for efficiency.

Understanding addressing modes helps predict performance and design efficient code.

[[Category:Assembly Programming]]

mov Instruction: Registers, Immediates, Memory

2025-10-20T13:46:12Z

Bfh-sts: Created page with "= mov Instruction: Registers, Immediates, Memory = This page introduces the mov instruction — one of the most fundamental instructions in assembly — and explains the different addressing modes used with it. == The mov instruction == The mov instruction copies (moves) data from one location to another. Syntax: mov destination, source It can copy data: * From one register to another. * From an immediate (constant) value to a register. * From memory to a register (l..."

= mov Instruction: Registers, Immediates, Memory =
This page introduces the mov instruction — one of the most fundamental instructions in assembly — and explains the different addressing modes used with it.

== The mov instruction ==
The mov instruction copies (moves) data from one location to another.
Syntax: mov destination, source

It can copy data:
* From one register to another.
* From an immediate (constant) value to a register.
* From memory to a register (load).
* From a register to memory (store).

However, memory-to-memory moves are not allowed.

Example:
mov rax, 42 ; move the value 42 into the register rax

== Immediate addressing ==
The data is part of the instruction itself.
The value is encoded directly within the instruction bytes.

Examples:
mov rax, 42 ; b8 2a 00 00 00
mov rbx, 'Hello' ; 48 bb 48 65 6c 6c 6f 00 00 00
mov rcx, 0ABCDh ; b9 cd ab 00 00

Be careful with register size:
mov cl, 67EFh ; warning: byte data exceeds bounds

Immediate values must fit the destination register.

== Register addressing ==
Copies values directly between registers.
The register size defines the amount of data moved.

Examples:
mov bl, ch ; 8-bit
add dx, ax ; 16-bit
mov ebp, esi ; 32-bit

Most instructions operate on registers.
Example:
add ecx, edx ; ecx ← ecx + edx (32-bit addition)
add rax, rbx ; rax ← rax + rbx (64-bit addition)

== Memory addressing ==
The [] operator accesses memory at the specified address.
Inside the brackets, you can use:
* A direct address
* A register holding an address
* An offset added to a base register
* A base and index register combination

Examples:
mov rax, [Address] ; load 64 bits from memory at Address
mov rbx, Address ; copy the address itself into rbx
mov cx, [rbx] ; load 16 bits from memory pointed by rbx
mov edx, [rbx+3] ; load 32 bits from rbx + 3
mov [rbx+rcx], rax ; store 64 bits from rax into memory at rbx+rcx

== Practical register exercise ==
Try in a debugger:
mov ax, 67FEh
mov bx, ax
mov cl, bh
mov ch, bl

Inspect ax, bx, and cx step by step to observe how the 8-bit halves (AL/AH, BL/BH, etc.) affect the full registers.

== Addressing overview ==
Mode | Example | Typical Use
---- | -------- | ------------
Register | mov rax, rbx | Fast data copy
Immediate | mov rax, 42 | Load a constant
Direct memory | mov rax, [100] | Read a global variable
Register indirect | mov [rbx], rax | Write through a pointer
Direct offset | mov [rbx+8], rax | Access struct field
Base + index | mov rax, [rbx + rdi] | Access array element

[[Category:Assembly Programming]]

Assembly Programming: Overview & Conventions

2025-10-20T13:46:01Z

Bfh-sts: Created page with "= Assembly Programming: Overview & Conventions = This page introduces x86-64 assembly programming, the syntax conventions used in this course, and the tools involved. == Introduction == Assembly language (ASM) is a low-level programming language that provides direct access to the CPU’s instruction set. Unlike high-level languages, assembly operates on registers, memory addresses, and immediate values. In this course, we use NASM (Netwide Assembler) on GNU/Linux wit..."

= Assembly Programming: Overview & Conventions =
This page introduces x86-64 assembly programming, the syntax conventions used in this course, and the tools involved.

== Introduction ==
Assembly language (ASM) is a low-level programming language that provides direct access to the CPU’s instruction set.
Unlike high-level languages, assembly operates on registers, memory addresses, and immediate values.

In this course, we use NASM (Netwide Assembler) on GNU/Linux with Intel syntax.
Intel syntax is more readable for most beginners and aligns with documentation from Intel and AMD.

== Intel vs. AT&T syntax ==
There are two dominant syntaxes for x86 assembly:
* **Intel syntax** – used by NASM, MASM, and most documentation.
* **AT&T syntax** – used by GNU Assembler (GAS) and older Unix systems.

Main differences in AT&T syntax:
* Immediate values are prefixed with `$`, e.g. `push $4` instead of `push 4`.
* Registers are prefixed with `%`, e.g. `inc %eax` instead of `inc eax`.
* Source and destination are swapped: `add eax, 4` becomes `add $4, %eax`.
* Instruction size is suffixed to the opcode: `mov ax, bx` becomes `movw %bx, %ax`.

In this course we use **Intel syntax** exclusively.

== Example comparison ==
Intel syntax:
mov eax, 4
add eax, 2
mov ebx, eax

AT&T syntax:
movl $4, %eax
addl $2, %eax
movl %eax, %ebx

Intel syntax is generally easier to read, especially when addressing memory:
lea eax, [rcx + rax*8 - 0x30]
vs.
lea -0x30(%rcx, %rax, 8), %eax

== Why learn assembly ==
Learning assembly provides insight into how computers actually execute code:
* How registers, memory, and the stack interact.
* How arithmetic and logic are performed at CPU level.
* How operating system services are invoked through syscalls.

It builds a foundation for understanding compilers, reverse engineering, performance optimization, and embedded systems.

[[Category: Assembly Programming]]

Category:Assembly Programming

2025-10-20T13:45:53Z

Bfh-sts: Created page with "= Overview = This category covers x86-64 assembly programming with NASM on GNU/Linux: syntax, addressing, arithmetic, data definitions, program structure, strings, and syscalls. == Pages == * Assembly Programming: Overview & Conventions * mov Instruction: Registers, Immediates, Memory * Addressing Modes: Direct, Indirect, Base+Index, Offsets * Memory Operands in Other Instructions (add, etc.) * Labels and Entry Point (_start) * Arithmetic: add, sub..."

= Overview =
This category covers x86-64 assembly programming with NASM on GNU/Linux: syntax, addressing, arithmetic, data definitions, program structure, strings, and syscalls.

== Pages ==
* [[Assembly Programming: Overview & Conventions]]
* [[mov Instruction: Registers, Immediates, Memory]]
* [[Addressing Modes: Direct, Indirect, Base+Index, Offsets]]
* [[Memory Operands in Other Instructions (add, etc.)]]
* [[Labels and Entry Point (_start)]]
* [[Arithmetic: add, sub, inc, dec]]
* [[Signed Integers and Flags (Two’s Complement)]]
* [[Sign Extension and Negation (movsx, neg)]]
* [[Multiplication and Division (mul, imul, div, idiv)]]
* [[Program Structure: .data, .bss, .text, global _start]]
* [[Data Definition Directives: db, dw, dd, dq, equ]]
* [[Strings in Assembly: Buffers, Length with $ and equ, Concatenation]]
* [[Linux x86-64 Syscalls: syscall, Registers, sys_write, sys_exit]]
* [[Hands-on: Debugger Exercise for Register Parts (AX/BX/CX)]]

[[Category: Computer Science Basics (BTI1021p) 25/26]]

Assembly Playfield: Build, Run & Debug (NASM, LD, GDB)

2025-10-20T13:45:26Z

Bfh-sts: Created page with "= Assembly Playfield: Build, Run & Debug (NASM, LD, GDB) = This page provides a practical starting point for experimenting with assembly programming under Linux, using NASM for assembling, LD for linking, and GDB for debugging. == The playfield program == To learn assembly, we use a minimal “playfield” — a small skeleton program that runs correctly but does nothing by default. It provides a clean structure that you can modify freely. Basic structure of `playfie..."

= Assembly Playfield: Build, Run & Debug (NASM, LD, GDB) =
This page provides a practical starting point for experimenting with assembly programming under Linux, using NASM for assembling, LD for linking, and GDB for debugging.

== The playfield program ==
To learn assembly, we use a minimal “playfield” — a small skeleton program that runs correctly but does nothing by default.
It provides a clean structure that you can modify freely.

Basic structure of `playfield.asm`:
<syntaxhighlight lang='nasm'>
SECTION .data
SECTION .bss
SECTION .text
global _start

_start:
nop ; no operation - placeholder for experiments

; properly end program
mov rax, 60 ; syscall number for sys_exit
mov rdi, 0 ; exit code 0
syscall ; invoke kernel
</syntaxhighlight>

This structure defines:
* `.data` – initialized variables
* `.bss` – uninitialized variables
* `.text` – program instructions
* `_start` – the program’s entry point

== Assembling and linking ==
To build and link the playfield program manually:
<syntaxhighlight lang='bash'>
nasm -f elf64 -g -F dwarf playfield.asm -l playfield.lst
ld -o playfield playfield.o
</syntaxhighlight>

Or with a Makefile:
<syntaxhighlight lang='make'>
playfield: playfield.o
ld -o playfield playfield.o

playfield.o: playfield.asm
nasm -f elf64 -g -F dwarf playfield.asm -l playfield.lst
</syntaxhighlight>

This creates an executable called `playfield`.

== Running the program ==
Execute directly:
<syntaxhighlight lang='bash'>
./playfield
</syntaxhighlight>

Since it only runs a `nop` and then exits, nothing visible happens — but the environment is ready for experimentation.

== Debugging with GDB ==
Use the GNU Debugger (GDB) to step through instructions and inspect registers.

Start with the text interface:
<syntaxhighlight lang='bash'>
gdb --tui playfield
</syntaxhighlight>

Useful commands inside GDB:

Command | Description
-------- | ------------
l | List source code
b N | Set a breakpoint at line N
r | Run the program
s | Step one instruction
i r | Show register contents
layout regs | Display and update all registers
q | Quit GDB

Optional setup: create a `.gdbinit` file in your home directory with:
<syntaxhighlight lang='text'>
tui e
layout regs
</syntaxhighlight>

== Experiment ideas ==
Try editing `playfield.asm` and adding simple operations:
<syntaxhighlight lang='nasm'>
mov rax, 2
mov rbx, 3
add rax, rbx ; result: 5 in RAX
</syntaxhighlight>

Assemble, link, and debug again to observe register changes step-by-step.

== Summary ==
The assembly playfield is your testbed for learning CPU instructions.
With NASM, LD, and GDB, you can assemble, link, and inspect every part of the program execution cycle directly at the hardware level.

[[Category: Programming Model]]

Historical Context: Register Growth & Segment Registers

2025-10-20T13:45:13Z

Bfh-sts: Created page with "= Historical Context: Register Growth & Segment Registers = This page explains how CPU register design evolved over time and how early architectural choices still influence modern processors. == Register growth over time == The number and width of registers in CPUs have increased dramatically. In the early 1980s, accessing main memory was nearly as fast as using registers, so CPUs could work efficiently with only a few of them. * **1970s:** Typical CPUs had 3–8 gen..."

= Historical Context: Register Growth & Segment Registers =
This page explains how CPU register design evolved over time and how early architectural choices still influence modern processors.

== Register growth over time ==
The number and width of registers in CPUs have increased dramatically.
In the early 1980s, accessing main memory was nearly as fast as using registers, so CPUs could work efficiently with only a few of them.

* **1970s:** Typical CPUs had 3–8 general-purpose registers.
Example: The Texas Instruments TMS9900 (1976) had only three physical registers and stored most register data in RAM.
* **1980s:** The Intel 8086 introduced 8 general-purpose 16-bit registers.
IBM chose the 8086 for its PC, shaping today’s computing landscape.
* **1990s:** The Intel 80386 expanded registers to 32 bits and added more addressing capabilities.
* **2000s onward:** x86-64 doubled register width to 64 bits and added registers R8–R15.
Modern CPUs also include many internal physical registers invisible to programmers.

CPU speed has historically grown much faster than DRAM speed (about 60% vs 7% per year).
Having many registers helps reduce slow memory access and increases execution speed.

== Views on registers revisited ==
Different views (RAX, EAX, AX, AH, AL) originate from early physical design decisions.
When CPUs were small, it was efficient to divide a single register into smaller parts for flexible access.
Modern CPUs emulate this behavior logically, even though internally, registers are remapped dynamically.

== Segment registers ==
Older x86 CPUs used **segmented memory** to access more than 64 KiB of memory with 16-bit addresses.
Segments provided partial 20-bit addressing by combining a segment register with an offset.

Segment registers included:
* **CS** – Code Segment: points to executable instructions.
* **DS** – Data Segment: default for data access.
* **SS** – Stack Segment: used by the stack pointer.
* **ES**, **FS**, **GS** – additional or specialized data segments.

With the introduction of the 80386, CPUs moved to **flat memory models**, making segmentation mostly obsolete.
However, the registers remain available for compatibility and special uses such as:
* Thread-local storage (FS and GS on Linux).
* Special-purpose system structures.

== Legacy influence ==
Even though segmentation and 8-bit registers may seem outdated, they continue to define compatibility in modern 64-bit processors.
This persistence shows the layered evolution of computing — new designs are built atop the constraints of older architectures.

[[Category: Programming Model]]