Logik - Informatik Lernzettel

1. Boolesche Algebra

📖 Was ist Boolesche Algebra?

Die Boolesche Algebra (benannt nach George Boole) ist ein mathematisches System, das nur mit zwei Werten arbeitet: wahr (true, 1) und falsch (false, 0). Sie bildet die Grundlage für digitale Schaltungen und logische Operationen in der Programmierung.

🔢 Boolesche Werte

Bezeichnung	Logik	Java	Bedeutung
Wahr	1	`true`	Aussage ist wahr / Bedingung erfüllt
Falsch	0	`false`	Aussage ist falsch / Bedingung nicht erfüllt

2. Logische Operatoren

2.1 NICHT (NOT) – Negation

📖 Der NOT-Operator

Der NOT-Operator kehrt einen Wahrheitswert um. Aus wahr wird falsch und aus falsch wird wahr.

Symbole: ¬, !, NOT, ‾ (Überstrich)

📊 Wahrheitstabelle: NOT

A	NOT A (¬A)
0	1
1	0

// NOT in Java
boolean a = true;
boolean ergebnis = !a;  // ergebnis = false

boolean b = false;
boolean ergebnis2 = !b;  // ergebnis2 = true

2.2 UND (AND) – Konjunktion

📖 Der AND-Operator

Der AND-Operator liefert nur dann true, wenn beide Eingangswerte true sind. Sobald ein Wert false ist, ist das Ergebnis false.

Symbole: ∧, &&, AND, · (Punkt), &

📊 Wahrheitstabelle: AND

A	B	A AND B (A ∧ B)
0	0	0
0	1	0
1	0	0
1	1	1

// AND in Java
boolean a = true;
boolean b = false;
boolean ergebnis = a && b;  // ergebnis = false

// Praktisches Beispiel
int alter = 20;
boolean hatFuehrerschein = true;

if (alter >= 18 && hatFuehrerschein) {
    System.out.println("Darf Auto fahren");
}

Merkhilfe für AND:
"Beide müssen mitmachen!" – Nur wenn A und B wahr sind, ist das Ergebnis wahr.

2.3 ODER (OR) – Disjunktion

📖 Der OR-Operator

Der OR-Operator liefert true, wenn mindestens einer der Eingangswerte true ist. Nur wenn beide false sind, ist das Ergebnis false.

Symbole: ∨, ||, OR, +, |

📊 Wahrheitstabelle: OR

A	B	A OR B (A ∨ B)
0	0	0
0	1	1
1	0	1
1	1	1

// OR in Java
boolean a = false;
boolean b = true;
boolean ergebnis = a || b;  // ergebnis = true

// Praktisches Beispiel
boolean hatStudentenausweis = true;
boolean istUnter18 = false;

if (hatStudentenausweis || istUnter18) {
    System.out.println("Ermäßigung!");
}

Merkhilfe für OR:
"Einer reicht!" – Wenn A oder B (oder beide) wahr sind, ist das Ergebnis wahr.

2.4 Exklusiv-ODER (XOR)

📖 Der XOR-Operator

Der XOR-Operator (Exklusiv-ODER) liefert true, wenn genau einer der Eingangswerte true ist. Bei gleichen Werten ist das Ergebnis false.

Symbole: ⊕, ^, XOR

📊 Wahrheitstabelle: XOR

A	B	A XOR B (A ⊕ B)
0	0	0
0	1	1
1	0	1
1	1	0

// XOR in Java (mit ^)
boolean a = true;
boolean b = true;
boolean ergebnis = a ^ b;  // ergebnis = false (beide gleich)

boolean c = true;
boolean d = false;
boolean ergebnis2 = c ^ d;  // ergebnis2 = true (unterschiedlich)

Merkhilfe für XOR:
"Entweder-Oder!" – Genau einer muss wahr sein, nicht beide und nicht keiner.

3. Übersicht aller Operatoren

📊 Alle Operatoren im Vergleich

A	B	NOT A	A AND B	A OR B	A XOR B
0	0	1	0	0	0
0	1	1	0	1	1
1	0	0	0	1	1
1	1	0	1	1	0

💻 Logische Operatoren in Java

Operation	Java-Symbol	Beispiel	Beschreibung
NOT	`!`	`!a`	Negiert den Wert
AND	`&&`	`a && b`	Wahr, wenn beide wahr
OR	`\|\|`	`a \|\| b`	Wahr, wenn mind. einer wahr
XOR	`^`	`a ^ b`	Wahr, wenn genau einer wahr

4. Logik-Gatter (Schaltzeichen)

📖 Was sind Logik-Gatter?

Logik-Gatter sind elektronische Schaltungen, die logische Operationen durchführen. Sie sind die Grundbausteine digitaler Schaltungen und werden in Prozessoren, Speichern und anderen elektronischen Geräten verwendet. In Schaltplänen werden sie durch standardisierte Symbole dargestellt.

🔌 Die wichtigsten Logik-Gatter

NOT

Negation

AND

Und

Oder

NAND

Und-Nicht

NOR

Oder-Nicht

XOR

Exklusiv-Oder

XNOR

Äquivalenz

📊 Gatter-Symbole und ihre Bedeutung

Gatter	Symbol	Funktion	Formel
NOT	`1` + ○	Kehrt Eingang um	Y = ¬A
AND	`&`	Alle Eingänge = 1	Y = A ∧ B
OR	`≥1`	Mind. ein Eingang = 1	Y = A ∨ B
NAND	`&` + ○	Negiertes AND	Y = ¬(A ∧ B)
NOR	`≥1` + ○	Negiertes OR	Y = ¬(A ∨ B)
XOR	`=1`	Genau ein Eingang = 1	Y = A ⊕ B
XNOR	`=1` + ○	Eingänge gleich	Y = A ↔ B

Merkhilfe für Gatter-Symbole:
& = UND (AND) - "Ampersand" steht für "und"
≥1 = ODER - "Mindestens 1" muss wahr sein
=1 = XOR - "Genau 1" muss wahr sein
○ = Kreis am Ausgang bedeutet immer Negation

5. Wahrheitstabellen erstellen

📖 Was ist eine Wahrheitstabelle?

Eine Wahrheitstabelle zeigt alle möglichen Kombinationen von Eingangswerten und die daraus resultierenden Ausgangswerte eines logischen Ausdrucks. Bei n Eingangsvariablen gibt es 2ⁿ Zeilen.

📝 Schritt-für-Schritt: Wahrheitstabelle erstellen

Beispiel: (A AND B) OR C

Schritt 1: Anzahl Variablen = 3, also 2³ = 8 Zeilen

Schritt 2: Alle Kombinationen auflisten

Schritt 3: Schrittweise auswerten (erst Klammer, dann Verknüpfung)

A	B	C	A AND B	(A AND B) OR C
0	0	0	0	0
0	0	1	0	1
0	1	0	0	0
0	1	1	0	1
1	0	0	0	0
1	0	1	0	1
1	1	0	1	1
1	1	1	1	1

Tipp für die Eingangswerte:
Die letzte Spalte wechselt: 0,1,0,1,0,1...
Vorletzte Spalte wechselt: 0,0,1,1,0,0,1,1...
Drittletzte wechselt: 0,0,0,0,1,1,1,1...

6. Komplexe logische Ausdrücke

⚡ Priorität der Operatoren (von hoch nach niedrig)

( ) – Klammern (höchste Priorität)
! – NOT
&& – AND
|| – OR

Tipp: Im Zweifelsfall Klammern setzen!

Beispiel: A || B && !C auswerten

Gegeben: A = true, B = true, C = true

!C = !true = false
B && !C = true && false = false
A || (B && !C) = true || false = true

Ergebnis: true

Wahrheitstabelle: NOT A OR (B AND C)

A	B	C	NOT A	B AND C	NOT A OR (B AND C)
0	0	0	1	0	1
0	0	1	1	0	1
0	1	0	1	0	1
0	1	1	1	1	1
1	0	0	0	0	0
1	0	1	0	0	0
1	1	0	0	0	0
1	1	1	0	1	1

7. Logik in Java

💻 Short-Circuit Evaluation

Java wertet logische Ausdrücke "von links nach rechts" aus und bricht ab, sobald das Ergebnis feststeht:

// AND: Wenn erstes false, wird zweites nicht geprüft
boolean a = false;
boolean b = true;
if (a && b) {  // b wird nicht geprüft, da a bereits false
    // wird nie ausgeführt
}

// OR: Wenn erstes true, wird zweites nicht geprüft
boolean x = true;
boolean y = false;
if (x || y) {  // y wird nicht geprüft, da x bereits true
    // wird ausgeführt
}

// Praktischer Nutzen: Null-Check
String text = null;
if (text != null && text.length() > 0) {
    // Sicher: length() wird nur aufgerufen, wenn text nicht null ist
}

🔄 Logische Ausdrücke in Bedingungen

int alter = 25;
boolean istStudent = true;
boolean hatMitgliedskarte = false;

// Komplexe Bedingung
if ((alter < 18 || alter > 65) || (istStudent && !hatMitgliedskarte)) {
    System.out.println("Ermäßigung möglich");
}

// Bedingung mit Vergleichsoperatoren
int punkte = 75;
if (punkte >= 90) {
    System.out.println("Sehr gut");
} else if (punkte >= 80) {
    System.out.println("Gut");
} else if (punkte >= 70) {
    System.out.println("Befriedigend");
} else {
    System.out.println("Nicht bestanden");
}

8. Normalformen: DNF und KNF

📖 Was sind Normalformen?

Normalformen sind standardisierte Darstellungen von logischen Ausdrücken. Die zwei wichtigsten sind die Disjunktive Normalform (DNF) und die Konjunktive Normalform (KNF). Sie ermöglichen es, jeden beliebigen booleschen Ausdruck in einer einheitlichen Form darzustellen.

7.1 Disjunktive Normalform (DNF)

📊 DNF – ODER von UND-Termen

Die DNF ist eine ODER-Verknüpfung (∨) von Mintermen. Jeder Minterm ist eine UND-Verknüpfung aller Variablen.

                    Struktur: (Minterm₁) ∨ (Minterm₂) ∨ (Minterm₃) ∨ ...
                

📝 Minterm erstellen:

Schaue auf die Zeilen mit Y = 1 in der Wahrheitstabelle
Variable = 1 → Variable normal (z.B. A)
Variable = 0 → Variable negiert (z.B. ¬A)
Alle Variablen der Zeile mit UND (∧) verknüpfen

Beispiel: DNF aus Wahrheitstabelle

A	B	Y	Minterm
0	0	0	-
0	1	1	¬A ∧ B
1	0	0	-
1	1	1	A ∧ B

DNF: Y = (¬A ∧ B) ∨ (A ∧ B)

7.2 Konjunktive Normalform (KNF)

📊 KNF – UND von ODER-Termen

Die KNF ist eine UND-Verknüpfung (∧) von Maxtermen. Jeder Maxterm ist eine ODER-Verknüpfung aller Variablen.

                    Struktur: (Maxterm₁) ∧ (Maxterm₂) ∧ (Maxterm₃) ∧ ...
                

📝 Maxterm erstellen (⚠️ Achtung: Umgekehrt!):

Schaue auf die Zeilen mit Y = 0 in der Wahrheitstabelle
Variable = 1 → Variable negiert (z.B. ¬A) ← umgekehrt!
Variable = 0 → Variable normal (z.B. A) ← umgekehrt!
Alle Variablen der Zeile mit ODER (∨) verknüpfen

Beispiel: KNF aus Wahrheitstabelle

A	B	Y	Maxterm
0	0	0	A ∨ B
0	1	1	-
1	0	0	¬A ∨ B
1	1	1	-

KNF: Y = (A ∨ B) ∧ (¬A ∨ B)

Merkhilfe DNF vs. KNF:
DNF: Disjunktiv = Draußen ODER, drinnen UND → Zeilen mit 1 → normal übernehmen
KNF: Konjunktiv = außen UND, innen ODER → Zeilen mit 0 → umgekehrt übernehmen

7.3 Umwandlung: DNF ↔ KNF

🔄 Methode 1: Über Wahrheitstabelle (empfohlen)

Wahrheitstabelle aufstellen für den gegebenen Ausdruck
DNF ablesen: Zeilen mit Y=1, Variablen normal übernehmen (1→A, 0→¬A)
KNF ablesen: Zeilen mit Y=0, Variablen umgekehrt übernehmen (1→¬A, 0→A)

Vollständiges Beispiel: Beide Normalformen

A	B	C	Y	Minterm (DNF)	Maxterm (KNF)
0	0	0	0	-	A ∨ B ∨ C
0	0	1	1	¬A ∧ ¬B ∧ C	-
0	1	0	0	-	A ∨ ¬B ∨ C
0	1	1	1	¬A ∧ B ∧ C	-
1	0	0	0	-	¬A ∨ B ∨ C
1	0	1	1	A ∧ ¬B ∧ C	-
1	1	0	0	-	¬A ∨ ¬B ∨ C
1	1	1	1	A ∧ B ∧ C	-

DNF: Y = (¬A ∧ ¬B ∧ C) ∨ (¬A ∧ B ∧ C) ∨ (A ∧ ¬B ∧ C) ∨ (A ∧ B ∧ C)
KNF: Y = (A ∨ B ∨ C) ∧ (A ∨ ¬B ∨ C) ∧ (¬A ∨ B ∨ C) ∧ (¬A ∨ ¬B ∨ C)

🔄 Methode 2: Algebraische Umwandlung (De Morgan)

DNF und KNF sind dual zueinander. Man kann mit De Morgan und Doppelter Negation umwandeln:

DNF → KNF:
1. Gesamten Ausdruck zweimal negieren: ¬¬(DNF)
2. De Morgan auf innere Negation anwenden
3. Ausmultiplizieren mit Distributivgesetz

Beispiel: (¬A ∧ B) ∨ (A ∧ B) → KNF

Vereinfachen: (¬A ∧ B) ∨ (A ∧ B) = B ∧ (¬A ∨ A) = B ∧ 1 = B
KNF von B ist einfach: B (bereits in KNF)

Tipp: Oft ist die Wahrheitstabellen-Methode einfacher!

7.4 Minimierung mit KV-Diagramm

📊 Von DNF zur minimierten Form

Das KV-Diagramm ermöglicht die grafische Minimierung einer DNF:

DNF-Minterme als 1en ins KV-Diagramm eintragen
Gruppen bilden: Rechtecke mit 2ⁿ Einsen (1, 2, 4, 8...)
Minimierte DNF: Variablen die in der Gruppe konstant sind

KNF minimieren:
Gleiche Methode, aber mit den Nullen statt Einsen!
Oder: Minimierte DNF von ¬Y bilden, dann De Morgan anwenden.

Zusammenfassung DNF/KNF:

	DNF	KNF
Struktur	∨ von ∧-Termen	∧ von ∨-Termen
Ablesen	Y = 1 Zeilen	Y = 0 Zeilen
Variablen	Normal (1→A, 0→¬A)	Umgekehrt (1→¬A, 0→A)
KV-Diagramm	Einsen gruppieren	Nullen gruppieren

9. Wichtige logische Gesetze

📜 De Morgansche Gesetze

Diese Gesetze beschreiben, wie man NOT über AND/OR "verteilt":

NOT (A AND B) = (NOT A) OR (NOT B)
NOT (A OR B) = (NOT A) AND (NOT B)

// De Morgan in Java
// !(a && b) ist gleich (!a || !b)
// !(a || b) ist gleich (!a && !b)

boolean a = true, b = false;

// Diese sind äquivalent:
boolean r1 = !(a && b);      // true
boolean r2 = (!a || !b);     // true

// Diese sind auch äquivalent:
boolean r3 = !(a || b);      // false
boolean r4 = (!a && !b);     // false

📜 Weitere wichtige Gesetze

Gesetz	AND	OR
Identität	A AND 1 = A	A OR 0 = A
Dominanz	A AND 0 = 0	A OR 1 = 1
Idempotenz	A AND A = A	A OR A = A
Komplement	A AND (NOT A) = 0	A OR (NOT A) = 1
Doppelte Negation	NOT (NOT A) = A

📋 Zusammenfassung: Logik

Boolesche Werte: true (1) oder false (0)
NOT (!): Kehrt den Wert um
AND (&&): Wahr, wenn beide wahr
OR (||): Wahr, wenn mindestens einer wahr
XOR (^): Wahr, wenn genau einer wahr

Normalformen:

DNF: ODER von UND-Termen → Y=1 Zeilen → Variablen normal übernehmen
KNF: UND von ODER-Termen → Y=0 Zeilen → Variablen umgekehrt übernehmen
KV-Diagramm: DNF mit Einsen, KNF mit Nullen minimieren

Wahrheitstabelle erstellen:

Anzahl Zeilen = 2^(Anzahl Variablen)
Alle Kombinationen systematisch auflisten
Von innen nach außen auswerten (Klammern zuerst)

Priorität (hoch → niedrig):

Klammern → NOT → AND → OR

De Morgan:

!(A && B) = !A || !B
!(A || B) = !A && !B

← Zahlensysteme Weiter zu UML →