Syllogismen: Erlaubte Formen der Schlussfolgerung.
Ein Beispiel für einen Syllogismus ist der Modus Ponens.
Gib ein Beispiel dafür aus der Praxis.
Wenn A gilt, dann gilt auch B.
sowie
B gilt, kann man schließen, dass auch B gilt.
Einfaches Beispiel:
Aus der Kombination von „Wenn es regnet, ist die Straße nass“ und „Es regnet“ kann ich schlussfolgern, dass die Straße nass ist.
Die folgende Wahrheitstabelle zeigt die Wahrheitswerte von drei Formeln 𝜑1,𝜑2,𝜑3, die jeweils von den Aussagevariablen 𝐴, 𝐵, 𝐶 abhängen:
Entscheiden Sie für jede der drei Formeln, ob sie allgemeingültig, erfüllbar, falsifizierbar oder unerfüllbar ist.
• Die Formel 𝜑1 ist erfüllbar, denn die Wahrheitstabelle enthält Zeilen, in denen 𝜑1 den Wert W annimmt. Die Formel ist auch falsifizierbar, denn die Wahrheitstabelle enthält Zeilen, in denen 𝜑1 den Wert F annimmt.
• Die Formel 𝜑2 ist unerfüllbar, denn sie hat in allen Zeilen der Wahrheitstabelle den Wert F. Somit ist die Formel auch falsifizierbar.
• Die Formel 𝜑3 ist allgemeingültig, denn sie hat in allen Zeilen der Wahrheitstabelle den Wert W. Somit ist die Formel auch erfüllbar.
Dieses Beispiel zeigt auch schon die Kernidee der Logik:
Ziel ist es zu beschreiben, welche Schlussfolgerungen alleine aus der Struktur von Sätzen möglich sind, ohne den Inhalt als solchen zu verstehen. Die im Beispiel genannte Schlussfolgerung ist also „logisch“ und nachvollziehbar, auch ohne dass ich weiß, was beispielsweise Regen ist.
Ohne Frage.
Nach wem ist die Boolesche Algebra sowie der Datentyp Boolean bennant?
George Boole
Grundlage der Logik ist die Aussagenlogik.
Womit befasst sich diese und wie ist diese definiert?
Mit der Wahrheit von Aussagen.
Diese Aussage ist definiert als ein Satz
dem man den Wahrheitswert „wahr“ oder „falsch“ zuordnen kann, so wie den beiden Sätzen über Regen und nasse Straßen oben.
Wozu wird Mathematische Logik analog zu anderen Modellierungstechniken genutzt?
Um Probleme und Aufgabenstellungen der realen Welt zu lösen.
Dieses Prinzip wird in der folgenden Abbildung beschrieben. Eine Aufgabe der realen Welt wird durch Abstraktion in die Modellwelt überführt, dort (nach Möglichkeit) gelöst und die Lösung wieder zurücktransferiert in die reale Welt.
Besondere Bedeutung hat die mathematische Logik heute in der Informatik, wo sie an vielen verschiedenen Stellen genutzt wird, beispielsweise?
Bedeutung von Bedingungen in der Programmierung, z. B. if-then-else-Anweisungen,
komplexe Formeln in einer Tabellenkalkulation,
logische Schaltungen, Hardware-Design,
künstliche Intelligenz,
logische Programmierung (z. B. in Prolog) sowie
Programmverifikation, formale Spezifikation und formale Semantik.
Womit befasst sich die Aussagenlogik?
Mit der Kombination von Aussagen.
Darunter versteht man Sätze, deren Wahrheit, also ihre Übereinstimmung mit der Wirklichkeit, bewertet werden kann.
Wie lautet die Definition der Elementaraussage?
Eine Elementaraussage ist ein Satz, dessen Übereinstimmung mit der Wirklichkeit bewertet werden kann.
Diese Bewertung nennt man den Wahrheitswert der Aussage.
In der Aussagenlogik arbeitet man normalerweise mit den Wahrheitswerten wahr und falsch.
Beispiele für solche Elementaraussagen, deren Übereinstimmung mit der Wirklichkeit also als wahr oder falsch bewertet werden kann, sind?
Berlin ist die Hauptstadt von Deutschland.
Paris ist die Hauptstadt von Deutschland.
Zum Studiengang BWL an dieser Hochschule gehören auch Vorlesungen zur Mathematik.
1 + 1 = 3
Was sind KEINE Aussagen?
Nenne Varianten die diese Logik abdecken.
Sätze, die man nicht als wahr oder falsch bewerten kann, wie beispielsweise Fragen oder Sätze, deren Wahrheitsgehalt sich mit der Zeit ändert oder nur ungefähr bewertet werden kann.
temporale Logik bzw. die
Fuzzy Logik
, die wir hier aber nicht weiter betrachten werden.
Welche Operatoren nutzt die Aussagenlogik?
Welche sind die wichtigsten dieser Operatoren?
Boolesche Operatoren
Die wichtigsten dieser Booleschen Operatoren sind die
Und-Verbindung,
Oder-Verbindung,
Wenn-Dann-Verbindung
Nicht-Operator
Wie lautet die Definition “Aussage!?
Eine Aussage ist eine Elementaraussage oder eine zusammengesetzte Aussage.
Eine zusammengesetzte Aussage besteht aus einem Booleschen Operator mit der entsprechenden Anzahl von Aussagen als Operanden (rekursive Definition).
Wie sieht die Wahrheitstabelle für den NIcht-Operator aus?
Die Aussagenkonstanten W und F stehen hier für „wahr“ und „falsch“, wobei oft auch die englischen Versionen T und F, alternativ ausgeschrieben true und false, verwendet werden. In Programmiersprachen mit schwacher Typisierung setzt man sogar teilweise W gleich mit dem Integer-Wert 1 und F mit 0.
Die Und-Verbindung (engl. „And“), als Konjunktion bezeichnet,
entspricht dem „und“ der Alltagssprache
und verbindet zwei Aussagen, beispielsweise „Berlin ist die Hauptstadt von Deutschland und 1 + 1 = 3“.
Das Ergebnis wird als wahr bewertet, wenn beide Ausgangsaussagen als wahr bewertet wurden. Wenn mindestens eine der Ausgangsaussagen als falsch bewertet wurde, dann ist auch deren Und-Verbindung falsch.
In Formeln wird die Und-Verbindung meist durch das Symbol ∧ dargestellt, d. h., die Und-Verbindung zweier Aussagen A und B wird beschrieben als A ∧ B.
Wie sieht die Wahrheitstabelle dazu aus?
Die Oder-Verbindung (engl. „Or“), auch als
Disjunktion
Wie wird diese dargestellt?
Wann wird das Ergebnis als Wahr bewertet?
Sie wird mit dem Symbol ∨ dargestellt,
entspricht dem „oder“ der Alltagssprache,
darf aber nicht mit dem „entweder – oder“ verwechselt werden. Auch hier werden zwei Aussagen verbunden, beispielsweise „Berlin ist die Hauptstadt von Deutschland oder 1 + 1 = 3“.
Das Ergebnis wird als wahr bewertet, wenn mindestens eine der Ausgangsaussagen als wahr bewertet wurden. Nur wenn beide Ausgangsaussagen als falsch bewertet wurden, dann ist auch deren Oder-Verbindung falsch.
Die Wenn-Dann-Verbindung (engl. „If-Then“ oder „Implies“), auch als Implikation bezeichnet.
Wie wird diese Dargestellt?
Sie wird mit dem Symbol ⇒ dargestellt, entspricht annähernd dem Wenn-Dann in der Alltagssprache.
Dabei ist allerdings nicht erforderlich, dass es irgendeinen inhaltlichen Zusammenhang gibt, d. h. „Wenn Berlin die Hauptstadt von Deutschland ist, dann 1 + 1 = 3“ ist eine erlaubte, wenn auch falsche Aussage.
Das Ergebnis einer Implikation A ⇒ B ist wahr, wenn immer dann, wenn die sogenannte Prämisse A wahr ist, auch die Schlussfolgerung B wahr ist. Wenn die Prämisse bereits falsch ist, dann ist egal, ob die Schlussfolgerung wahr oder falsch ist, die Implikation ist in diesem Fall immer wahr.
Welche umkehrung der Implikation ist gültig?
Die Implikation A ⇒ B kann daher auch formuliert werden als ¬A ∨ B. Aus dieser Formulierung wird sehr deutlich, dass A ⇒ B nicht verwechselt werden darf mit B ⇒ A, auch wenn das in der Praxis ein verbreiteter Denkfehler ist.
Betrachten wir die Aussage „Wenn es regnet, ist die Straße nass“. Wenn wir nun zusätzlich wissen, dass es regnet, dann können wir daraus offensichtlich schließen, dass die Straße nass ist. Was können wir aber schließen, wenn wir stattdessen wissen, dass die Straße nass ist? Leider nichts, denn die Umkehrung „Wenn die Straße nass ist, regnet es“ gilt eben nicht. Es könnte ja beispielsweise auch sein, dass die Straßenreinigung gerade da war und die Straße deshalb nass ist.
Eine gültige Umkehrung von A ⇒ B ist dagegen ¬B ⇒ ¬A. Wenn aus AB folgt und wir wissen, dass B nicht gilt, dann kann auch A nicht gelten. Am Beispiel: Aus „Wenn es regnet, ist die Straße nass“ und der Tatsache, dass die Straße nicht nass ist, können wir schließen, dass es auch nicht regnet.
Wenn eine Implikation in beiden Richtungen gleichzeitig gilt, dann ist das eine Genau-Dann-Verbindung (Äquivalenz; engl. „equivalence“ oder „if and only if“, abgekürzt „iff“)
Wie wird diese Abgebildet?
Wann wird das Ergebnis als Wahrt bewertet?
Die Äquivalenz A ⇔ B erhält also dann den Wahrheitswert wahr, wenn A und B den gleichen Wahrheitswert haben.
Dies wird oft auch formuliert als „A gilt genau dann, wenn B gilt“. Die Bedeutung der Äquivalenz kann durch folgende Wahrheitstabelle dargestellt werden:
Was ist eine Vollständige Basis?
Eine Menge B von Booleschen Operatoren heißt vollständige Basis, wenn jeder andere Boolesche Operator durch Elemente von B ausgedrückt werden kann.
„oder“ und „nicht“ bilden gemeinsam eine vollständige Basis.
„nand“ (nicht-Und) bildet eine vollständige Basis.
Wodurch wird eine Sprache definiert?
Durch ihre Syntax:
Welche Ausdrücke sind erlaubt?
Durch ihre Semantik:
Was bedeuten Ausdrücke in der Sprache?
Welche Kurzformen nutzt Java für:
oder
Exklusives oder
und
nicht
?
A|B = oder
A^B = Exklusives oder
A&B = und
! = nicht
Was ist eine Elementaraussage?
Eine Aussage die keine weitere Struktur hatund mit einer Aussagenvariablebezeichnet wird.
Was ist ein Literal?
Ein Literal ist eine Aussagenvariable X oder deren Verneinung ¬X.
Enthält das Literal keine Negation, wird es auch als positives Literal bezeichnet, enthält es eine Negation, als negatives Literal.
In welcher Reihenfolge sollen Operatoren ausgewertet werden?
Die Reihenfolge lautet:
¬, ∧, ∨, ⇒ und ⇔
Ausdrücke in einer kontextfreien Sprache und damit auch aussagenlogische Formeln kann man wie im folgenden Beispiel auch als Bäume darstellen. Ausgehend von der
Formel ¬(y ∧ ¬z) ∨ ¬(¬y ∨ (z ∨ x)) erhalten wir den Baum:
Wie lauten die Umformungen für folge Formen?
Wie wird die disjunktive Normalform dargestellt?
Als eine Disjuntkion von Konjunktionen.
z. B. (x11 ∧ ¬x12 ∧ …) ∨ (¬x21 ∧ x22 ∧ …) ∨ ….
Wie wird eine konjunktive Normalform dargestellt?
als eine Konjunktion von Disjunktionen
z. B. (x11 ∨ ¬x12 ∨ …) ∧ (¬x21 ∨ x22 ∨ …) ∧ ….
Was versteht man unter Axiome?
Mithilfe der Umformungsregeln lässt sich die Korrektheit von Formeln beweisen.
Um aber eine Formel als korrekt zu beweisen, müssen wir mit irgendeiner Grundlage starten und Regeln festlegen, nach denen von dieser Grundlage aus weitere Formeln abgeleitet, d. h. bewiesen werden können. Als Grundlage verwendet man daher normalerweise Formeln, die „offensichtlich“ korrekt sind und bei denen man daher festlegt, dass diese als korrekt angenommen werden.
Derartige Formeln, deren Korrektheit als Grundlage für alle Beweise angenommen wird und die daher aber selbst nicht bewiesen werden können, bezeichnet man als Axiome.
Was versteht man unter einem Kalkül?
Ein formales Verfahren, mit dem man Formeln ableiten oder beweisen kann, bezeichnet man als einen Kalkül. Ein Kalkül in der hier beschriebenen Form, bestehend aus Axiomen und Regeln, wird auch als
Hilbert
-Kalkül bezeichnet.
Bitte vereinfachen Sie die Formel [¬(A∧¬C)∨¬(¬B∨(C∨A))]∧¬C durch Anwendung der oben genannten Umformungsregeln und vergleichen das Ergebnis mit der im Text beschriebenen Wahrheitstafel für diese Formel.
Anleitung: Verschieben Sie mithilfe der De-Morgan-Regeln die Negationen direkt vor die Aussagenvariablen. Wo immer möglich, wenden Sie die Regeln Idempotenz, Absorption, Komplement und doppelte Verneinung zur Vereinfachung der Formel an. Mehrfach geschachtelte Und- und Oder-Ausdrücke eliminieren Sie mithilfe der Distributionsregel.
Wir haben bereits gelernt, dass eine Aussage ein Satz ist, dem man einen Wahrheitswert zuweisen kann. Eine derartige Zuweisung nennt man?
Eine Interpretation.
Eine Interpretation entspricht also einer Zeile einer Wahrheitstabelle.
Eine aussagenlogische Formel heißt...
... allgemeingültig (oder wahr oder Tautologie), wenn?
... erfüllbar, wenn ?
... falsifizierbar, wenn ?
... unerfüllbar (oder falsch), wenn?
... allgemeingültig (oder wahr oder Tautologie), wenn die Formel unter jeder Interpretation wahr wird.
... erfüllbar, wenn eine Interpretation existiert, sodass die Formel wahr wird.
... falsifizierbar, wenn eine Interpretation existiert, sodass die Formel falsch wird.
... unerfüllbar (oder falsch), wenn die Formel unter jeder Interpretation falsch wird.
Diese Begriffe sind teilweise eng voneinander abhängig: Ist eine Formel allgemeingültig, dann ist sie auch erfüllbar, aber ihre Negation ist unerfüllbar (und umgekehrt). Ist eine Formel erfüllbar, dann ist ihre Negation falsifizierbar (und umgekehrt).
Was versteht man unter Dreiwertiger Logik?
Mit welchem Symbol wird dieser Wert oft bezeichnet?
Bisher sind wir immer davon ausgegangen, dass es zwei Wahrheitswerte gibt, eine Aussage also immer wahr oder falsch ist. Sehr hilfreich kann aber auch eine Erweiterung dieses Konzeptes um einen dritten Wahrheitswert sein, der dann für „unbekannt“ oder „undefiniert“ stehen kann.
Kommen wir jetzt zurück zur Betrachtung von unbekannten oder undefinierten Werten in der mathematischen Logik, dann führt das wie oben erwähnt zu einem dritten Wahrheitswert, der oft mit dem Symbol bezeichnet wird.
Gegeben sei eine Formel φφ mit den Variablen 𝐴 und 𝐵 sowie der Wahrheitstabelle
A
B
φ
W
F
Welche Modelle hat die Formelφφ?
Ist der Operator || in Java kommutativ?
nein
Wann ist die Implikation wahr?
Wenn A und B wahr sind oder wenn A falsch ist.
Den aus falschen folgt beliebiges.
Wie lautet die Definition der Klausel?
Eine Klausel ist eine logische Formel, die aus einer Disjunktion von Literalen besteht.
Wie lautet die Formel für das exklusive oder? (XOR)
Wie sieht die dazugehörige Wahrheitstabelle aus?
Wen A oder B wahr ist und wenn nicht A und B wahr sind.
( A oder B) und (-(A und B))
Wie lautet das erste De Mogansche Gesetz?
Wie könnte ein Beispiel dazu aussehen?
1.
Bei einer Lotterie habe ich genau dann nicht den ersten oder zweiten Preis gewonne, wenn ich nicht den ersten Preis und nicht den zweiten Preis gewonnen habe.
Wie lautet das zweite De Morgansche Gesetz?
Wie könnte dazu ein Beispiel lautet?
Bei einer Lotterie habe ich genau dann nicht den ersten und zweiten Preis geonnen, wenn ich nicht den ersten Preis oder nicht den zweiten Preis gewnonnen habe.
Welchen Bezug hat die Beweisregel Modus Ponens zum Resolutionsverfahren?
Modus Ponens beschreibt einen speziellen Fall des Resolutionsverfahrens, denn Modus Ponens besagt , dass man aus A folgt B, also -A oder B, zusammen mit A die Aussage B ableiten kann.
Benenne die 3 Kalküle der Aussagenlogik.
Kalkül der Wahrheitstabellen
Das Hilbertsche Kalkül mit Axiomen und Regelnd für die Aussagenlogik
Resolutionskalkül
All diese Kalküle sind korrekt und unter allen Interpretationnen wahr.
Alle Kalküle sind vollständig: Jede unter allen Interpretationen wahre Formel kann hergeleitet werden.
Betrachten Sie die folgenden Formeln:
a) 𝐴∨¬𝐵
b) ¬𝐴∨𝐵∨𝐶
c) ¬𝐴
d) 𝐴
e) F
Entscheiden Sie jeweils, inwieweit es sich bei den Ausdrücken um eine Aussagenkonstante, eine Aussagenvariable, ein Literal und/oder eine Klausel handelt.
Hinweis: Eine Klausel ist eine logische Formel, die aus einer Disjunktion von Literalen besteht (vgl. Abschnitt 1.4 des Skripts).
Lösungshinweis
Erinnern Sie sich an die folgenden Definitionen:
•
Aussagenkonstanten sind die Wahrheitswerte W (wahr) und F (falsch).
Aussagenvariablen entsprechen Elementaraussagen und werden häufig mit 𝐴,𝐵,𝐶,… bezeichnet.
Ein Literal ist eine Aussagenvariable 𝐴 oder deren Verneinung ¬𝐴.
Eine Klausel ist eine logische Formel, die aus einer Disjunktion von einem oder mehreren Literalen besteht.
Kurze Lösung
a)
Klausel
b)
c)
Klausel, negatives Literal
d)
Klausel, positives Literal, Aussagenvariable
e)
Aussagenkonstante
Ausführliche Lösung
Aussagenkonstanten sind die Wahrheitswerte W (wahr) und F (falsch). Somit handelt es sich bei F (Formel e)) um eine Aussagenkonstante.
Aussagenvariablen entsprechen Elementaraussagen und werden häufig mit 𝐴,𝐵,𝐶,… bezeichnet. Somit handelt es sich bei 𝐴 (Formel d)) um eine Aussagenkonstante.
6
Ein Literal ist eine Aussagenvariable 𝐴 oder deren Verneinung ¬𝐴. Somit handelt es sich bei 𝐴 (Formel d)) um ein positives Literal und bei ¬𝐴 (Formel c)) um ein negatives Literal.
Eine Klausel ist eine logische Formel, die aus einer Disjunktion von einem oder mehreren Literalen besteht. Somit handelt es sich bei 𝐴∨¬𝐵 (Formel a)), ¬𝐴∨𝐵∨𝐶 (Formel b)), ¬𝐴 (Formel c)) und bei 𝐴 (Formel d)) jeweils um Klauseln.
Frage 1.5.1 (L)
Gemäß Skript sind der Kalkül der Wahrheitstabellen und der Resolutionskalkül vollständig.
Kann man daraus schließen, dass jede allgemeingültige Aussage der Mathematik auch beweisbar ist?
Begründen Sie Ihre Antwort.
Lösung Frage 1.5.1 Lösungshinweis
Gemäß Skript ist zwar die Aussagenlogik vollständig, nicht aber die Prädikatenlogik mit einfacher Arithmetik.
Kurze Lösung Nein, denn die Prädikatenlogik mit einfacher Arithmetik ist nicht vollständig.
Ausführliche Lösung:
Der Kalkül der Wahrheitstabellen und der Resolutionskalkül beziehen sich beide auf die Aussagenlogik.
Mit der Aussagenlogik können zwar einfache mathematische Zusammenhänge dargestellt werden, für komplexere Aussagen der Mathematik benötigt man aber die Prädikatenlogik mit Arithmetik.
Diese ist gemäß dem Ersten Gödelschen Unvollständigkeitssatz nicht vollständig (wenn wir Widerspruchsfreiheit annehmen), d.h. es gibt mathematische Sätze, die wahr, aber nicht beweisbar sind.
Frage 1.5.2
a) Erläutern Sie, wie Erfüllbarkeit und Allgemeingültigkeit einer Formel zusammenhängen.
a) Ein Zusammenhang zwischen Erfüllbarkeit und Allgemeingültigkeit einer Formel lässt sich über die Negation der Formel herstellen.
Antwort:
a) Eine Formel ist genau dann allgemeingültig, wenn ihre Negation nicht erfüllbar ist
Frage 1.5.3 (M) Plausibilisieren Sie folgende Aussagen: a) Der Kalkül der Wahrheitstabellen ist korrekt
a) Ein Kalkül ist korrekt, wenn jede mit dem Kalkül abgeleitete Eigenschaft auch allgemeingültig ist, also für jede Interpretation wahr ist.
Antwort
Jede Interpretation einer Formel entspricht genau einer Zeile im Kalkül der Wahrheitstabellen.
Frage 1.5.3 (M) Plausibilisieren Sie folgende Aussagen:
b) Der Kalkül der Wahrheitstabellen ist vollständig
b) Ein Kalkül ist vollständig, wenn jede allgemeingültige Eigenschaft auch mit dem Kalkül abgeleitet werden kann.
b) Ein Kalkül ist vollständig, wenn jede allgemeingültige Eigenschaft auch mit dem Kalkül abgeleitet werden kann. Angenommen eine Formel ist für jede Interpretation wahr.
Dann ergeben alle Zeilen in der zugehörigen Wahrheitstabelle den Wert „wahr“, denn jede solche Zeile entspricht einer Interpretation. Also kann die Formel mit dem Kalkül der Wahrheitstabellen abgeleitet werden.
Frage 1.5.4 (M) Plausibilisieren Sie folgende Aussagen:
a) Der Resolutionskalkül ist korrekt.
Lösung Frage 1.5.4 Lösungshinweis
a) Ein Kalkül ist korrekt, wenn jede mit dem Kalkül abgeleitete Eigenschaft auch allgemeingültig ist, also für jede Interpretation korrekt ist.
Sind zwei Klauseln 𝐷1 ∨ 𝐿 und 𝐷2 ∨ ¬𝐿 unter einer Interpretation 𝐼 wahr, so ist auch die Resolvente 𝐷1 ∨ 𝐷2 unter 𝐼 wahr.
b) Der Resolutionskalkül terminiert.
b) Ein Kalkül terminiert, wenn er nach endlich vielen Schritten zu einem Ergebnis führt.
b) Zu jeder Formel gibt es nur endlich viele verschiedene Klauseln, welche aus den Aussagenvariablen der Formel zusammengesetzt sind. Spätestens wenn alle diese Klauseln im Resolutionskalkül abgeleitet sind, können keine weiteren Klauseln mehr generiert werden, so dass der Algorithmus schließlich terminiert.
Zuletzt geändertvor 21 Tagen
