Logik & Algebra
Logik
Logik
Was sind die Grundbausteine der Aussagenlogik?
Elementare Aussagen, die eindeutig als wahr oder falsch bewertet werden können.
Sowie deren Verknüpfung mit und / oder / nicht.
Was sind Aussagen?
sätze, denen eindeutig ein Wahrheitswert zugewiesen werden kann!
Sind folgende Sätze Aussagen?
Was gibt es für Verknüpfungsoperatoren (Junktoren) ?
Bild
Wahrheitstafel zur und-Verknüpfung
Bild
Wahrheitstafel zur oder-Verknüpfung
Bild
Wahrheitstafel zur Negation
Bild
Wahrheitstafel zur Implikation
Bild
Wahrheitstafel zur Äquivalenz
Bild
Was ist eine Tautologie?
Die Formel wird durch jede mögliche Belegung wahr/falsch.
Beispiel:
Morgen regnet es oder morgen regnet es nicht.
F=(a v ¬a)
Wann ist eine Formel wiederspruchsvoll?
Wenn es keine einzige Belegung gibt damit die Formel wahr/falsch wird.
Beispiel
Morgen regnet es und morgen regnet es nicht
F=(a ^ ¬a)
Merkspruch für Tautologie und Wiederspruch
Ist F eine Tautologie dann ist ¬F ein Wiederspruch
Vorgangsregeln für die Normalform:
- Klammerausdrücke zuerst entfernen
- Negation bindet stärker als und welches wiederum stärker als oder ist
- das Zeichen für und(^) kann weggelasen werden
- Folgen gleiche Verknüpfungen aufeinander, dann von links nach rechts
Beispiele:
a ^ b = ab
a v (b ^ c) = a v bc
(a ^ ¬b) v ¬(c ^ d) = a ¬b v ¬(cd)
(a v b) ^ (a v c) = (a v b) (a v c)
Äquivalenz logischer Therme:
Zwei logische Therme A & B sind äquivalent, wenn die bei gleicher Belegung von gemeinsamen Variablen stets das gleiche Resultat liefern
Was ist ein Literal?
Eine negierte oder nicht negierte logische Variable
konjunktive Normalform & disjunktive Normalform
Die konjunktive Normalform ist eine Verbindung von konjuktiven Disjunktionstermen
D1 v D2 v D3 v Dn konjunktive Normalform
Die disjunktive Normalform ist eine disjunktive Verbindung von Konjunktionsthermen
K1 ^ K2 ^ K3 ^ Kn disjunktive Normalform
Algorithmus zum erzeugen von disjunktiven oder konjunktiven Normalformen
- Anwendung von DeMorgan bis negationen nur noch vor Variablen stehen
- Anwendung eines der Ditributativgesetze
- Zusammenfassen nach den Idempotenzgesetzen
- Streichen von w oder f gemäß der Regeln für die Neutralelemente
Was ist die kanonische konjunktive/disjunktive Normalform?
Eine normalform ist dann kanonisch, wenn jeder Konjunktionstherm/Disjunktionstherm alle Variablen der entsprechenden Funktion enthält
f(a,b) = a
= a ^ (b v ¬b)
Was ist eine Menge?
Ist eine Zusammenfassung unterschiedlicher Objekte (Elemente)
Kein Element doppelt!
Was ist die Mächtigkeit von Mengen?
Gibt an wie viele Elemente die Menge besitzt.
|M| = 3
Zugehörigkeit eines Objektes zu einer Menge
a ∈ M !
Was sind Quantoren?
Gewisse Eigenschaften von Elementen.
Mindestens eins... (Existenzquantor)
Für alle.... (Allquantor)
Zeichen für Existenzquantor
∃
Gespiegeltes E
Zeichen für Allquantor?
∀
Umgedrehtes A
Was ist das Extensionalitätsprinzip?
Gleichheit von Mengen
Mengen sind genau dann gleich, wenn die sie dieselben Objekte als Elemente haben.
M = N ⇔ ∀x(x∈M⇔x∈N)
Zeichen für echte Teilmenge
⊂
Zeichen für unechte Teilmenge
⊆
Unechte Teilmenge kann auch gesammte Teilmenge enthalten
Was ist ein Mengensystem und wie wird es noch genannt?
Mengen deren Elemente selbst wieder Mengen sind.
Wird auch Potenzmenge gennant. ( P(M)= )
Formel für die Mächtigkeit der Potenzmenge
2|M|
Woraus besteht eine algebraische Struktur?
- Menge
- Verknüpfungen
- Gesetmäßigkeiten
Was ist eine Tupel?
Besteht aus einer Menge und Einer Verknüpfung
(M, +)
-
- 1 / 32
-
Cartes-fiches
Was sind die Grundbausteine der Aussagenlogik?
Elementare Aussagen, die eindeutig als wahr oder falsch bewertet werden können.
Sowie deren Verknüpfung mit und / oder / nicht.
Was sind Aussagen?
sätze, denen eindeutig ein Wahrheitswert zugewiesen werden kann!
Sind folgende Sätze Aussagen?
Was gibt es für Verknüpfungsoperatoren (Junktoren) ?
Bild
Wahrheitstafel zur und-Verknüpfung
Bild
Wahrheitstafel zur oder-Verknüpfung
Bild
Wahrheitstafel zur Negation
Bild
Wahrheitstafel zur Implikation
Bild
Wahrheitstafel zur Äquivalenz
Bild
Was ist eine Tautologie?
Die Formel wird durch jede mögliche Belegung wahr/falsch.
Beispiel:
Morgen regnet es oder morgen regnet es nicht.
F=(a v ¬a)
Wann ist eine Formel wiederspruchsvoll?
Wenn es keine einzige Belegung gibt damit die Formel wahr/falsch wird.
Beispiel
Morgen regnet es und morgen regnet es nicht
F=(a ^ ¬a)
Merkspruch für Tautologie und Wiederspruch
Ist F eine Tautologie dann ist ¬F ein Wiederspruch
Vorgangsregeln für die Normalform:
- Klammerausdrücke zuerst entfernen
- Negation bindet stärker als und welches wiederum stärker als oder ist
- das Zeichen für und(^) kann weggelasen werden
- Folgen gleiche Verknüpfungen aufeinander, dann von links nach rechts
Beispiele:
a ^ b = ab
a v (b ^ c) = a v bc
(a ^ ¬b) v ¬(c ^ d) = a ¬b v ¬(cd)
(a v b) ^ (a v c) = (a v b) (a v c)
Äquivalenz logischer Therme:
Zwei logische Therme A & B sind äquivalent, wenn die bei gleicher Belegung von gemeinsamen Variablen stets das gleiche Resultat liefern
Was ist ein Literal?
Eine negierte oder nicht negierte logische Variable
konjunktive Normalform & disjunktive Normalform
Die konjunktive Normalform ist eine Verbindung von konjuktiven Disjunktionstermen
D1 v D2 v D3 v Dn konjunktive Normalform
Die disjunktive Normalform ist eine disjunktive Verbindung von Konjunktionsthermen
K1 ^ K2 ^ K3 ^ Kn disjunktive Normalform
Algorithmus zum erzeugen von disjunktiven oder konjunktiven Normalformen
- Anwendung von DeMorgan bis negationen nur noch vor Variablen stehen
- Anwendung eines der Ditributativgesetze
- Zusammenfassen nach den Idempotenzgesetzen
- Streichen von w oder f gemäß der Regeln für die Neutralelemente
Was ist die kanonische konjunktive/disjunktive Normalform?
Eine normalform ist dann kanonisch, wenn jeder Konjunktionstherm/Disjunktionstherm alle Variablen der entsprechenden Funktion enthält
f(a,b) = a
= a ^ (b v ¬b)
Was ist eine Menge?
Ist eine Zusammenfassung unterschiedlicher Objekte (Elemente)
Kein Element doppelt!
Was ist die Mächtigkeit von Mengen?
Gibt an wie viele Elemente die Menge besitzt.
|M| = 3
Zugehörigkeit eines Objektes zu einer Menge
a ∈ M !
Was sind Quantoren?
Gewisse Eigenschaften von Elementen.
Mindestens eins... (Existenzquantor)
Für alle.... (Allquantor)
Zeichen für Existenzquantor
∃
Gespiegeltes E
Zeichen für Allquantor?
∀
Umgedrehtes A
Was ist das Extensionalitätsprinzip?
Gleichheit von Mengen
Mengen sind genau dann gleich, wenn die sie dieselben Objekte als Elemente haben.
M = N ⇔ ∀x(x∈M⇔x∈N)
Zeichen für echte Teilmenge
⊂
Zeichen für unechte Teilmenge
⊆
Unechte Teilmenge kann auch gesammte Teilmenge enthalten
Was ist ein Mengensystem und wie wird es noch genannt?
Mengen deren Elemente selbst wieder Mengen sind.
Wird auch Potenzmenge gennant. ( P(M)= )
Formel für die Mächtigkeit der Potenzmenge
2|M|
Woraus besteht eine algebraische Struktur?
- Menge
- Verknüpfungen
- Gesetmäßigkeiten
Was ist eine Tupel?
Besteht aus einer Menge und Einer Verknüpfung
(M, +)
