Lektion 1a: Aussagenlogikdpraesent.at/anatut20/praesentation_L01_-_Logik_und... · 2020. 10. 3. · Vorrangregeln der Aussagenlogik •Formale Aussagen werden prinzipiell von links

Lektion 1a: Aussagenlogik

Aussagen und Junktoren,

Prädikate und Quantoren

Tutorium zur Analysis 1 - David Präsent 20W – L01: Aussagenlogik und mathematische Beweise

Aussagen

• Definition: Eine Aussage ist ein Stück Information (z.B. ein deutscher Satz oder eine Gleichung),dem man eindeutig und objektiv einen Wahrheitswert zuordnen kann (wahr oderfalsch bzw. 1 oder 0)

• Beispiel: „Ulysses ist ein Roman von James Joyce“

• Hier handelt es sich klar um eine Aussage, die den Wahrheitswert „wahr“ besitzt

„Ulysses ist ein unlesbares Buch“

• Dieser Satz ist keine Aussage, da dessen Wahrheitsgehalt subjektiv ist

Tutorium zur Analysis 1 - David Präsent 20W – L01: Logik

Junktoren und Wahrheitstafeln (1)

• Die Negation einer Aussage 𝑃 (schreib: ¬𝑃, sprich: „nicht-𝑃”) ist genau dann wahr, wenn 𝑃 falsch ist und falsch, wenn 𝑃 wahr ist.

• Die Konjunktion zweier Aussagen (schreib: 𝑃 ∧ 𝑄, sprich „𝑃 und 𝑄“) ist genau dann wahr, wenn sowohl 𝑃, als auch 𝑄 wahr sind.

• Die Disjunktion zweier Aussagen (schreib: 𝑃 ∨ 𝑄, sprich „𝑃 oder 𝑄“) ist genau dann wahr, wenn mindestens eine der beiden Aussagen wahr ist.


𝑷 ¬𝑷

w f

f w

𝑷 𝑸 𝑷 ∧ 𝑸

w w w

w f f

f w f

f f f

𝑷 𝑸 𝑷 ∨ 𝑸

w w w

w f w

f w w

f f f

Junktoren und Wahrheitstafeln (2)

• Die Implikation bzw. Subjunktion (schreib: 𝑃 → 𝑄, sprich: „Aus 𝑃 folgt 𝑄“ oder „𝑃 impliziert 𝑄“ oder „wenn 𝑃, dann 𝑄“) ist nur dann falsch, wenn 𝑃wahr und 𝑄 falsch ist.

• Wenn 𝑃 falsch ist, dann kann Beliebiges folgen, weshalb hier 𝑃 → 𝑄 wahr ist

• Im Fall „𝑃 ist wahr“ schreibt man 𝑃 ⇒ 𝑄 („wenn 𝑃 wahr ist, dann folgt 𝑄“)

• Die Äquivalenz (schreib: 𝑃 ↔ 𝑄, sprich: „𝑃 und 𝑄 sind äquivalent“ oder auch „𝑃 genau dann, wenn 𝑄“) ist genau dann wahr, wenn beide Aussagen wahr oder beide falsch sind.

• Anders gesagt: Mit der Äquivalenz ist die Aussage 𝑃 → 𝑄 ∧ (𝑄 → 𝑃) gemeint

• Zwei Aussagen sind genau dann äquivalent, wenn sie dieselben Wahrheitswerte in der Wahrheitstafel aufweisen!


𝑷 𝑸 𝑷 → 𝑸

w w w

w f f

f w w

f f w

𝑷 𝑸 𝑷 ↔ 𝑸

w w w

w f f

f w f

f f w

Vorrangregeln der Aussagenlogik

• Formale Aussagen werden prinzipiell von links nach rechts gelesen

• Für die Junktoren gilt folgende Hierarchie:

• Die Negation ist hierbei rechtsbindend, d.h. sie

bezieht sich auf die Aussage rechts von ¬

• Mithilfe von Klammern kann Vorrang gegeben werden

• Beispiel: Seien 𝑃, 𝑄, 𝑅, 𝑆 und 𝑇 Aussagen und folgende Aussage gegeben: 𝑃 ∧ 𝑄 ⇒ 𝑅 ∨ ¬𝑆 ∧ 𝑇

Äquivalent wäre hierbei diese Aussage: 𝑃 ∧ 𝑄 ⇒ 𝑅 ∨ ¬𝑆 ∧ 𝑇

D.h. wenn 𝑃 ∧ 𝑄 gilt, dann gilt entweder 𝑅 oder es gilt nicht-𝑆 ∧ 𝑇, oder es gilt beides.


1. ¬

2. ∧

3. ∨

4. → , ↔

Grundgesetze der Ausagenlogik

• Doppelte Negation: ¬ ¬𝑃 ⇔ 𝑃

• Kommutativgesetze: 𝑃 ∧ 𝑄 ⇔ 𝑄 ∧ 𝑃 𝑃 ∨ 𝑄 ⇔ 𝑄 ∨ 𝑃

• Assoziativgesetze: 𝑃 ∧ 𝑄 ∧ 𝑅 ⇔ 𝑃 ∧ (𝑄 ∧ 𝑅) 𝑃 ∨ 𝑄 ∨ 𝑅 ⇔ 𝑃 ∨ 𝑄 ∨ 𝑅

• Distributivgesetze: 𝑃 ∨ 𝑄 ∧ 𝑅 ⇔ 𝑃 ∧ 𝑅 ∨ 𝑄 ∧ 𝑅 𝑃 ∧ 𝑄 ∨ 𝑅 ⇔ 𝑃 ∨ 𝑅 ∧ (𝑄 ∨ 𝑅)

• Absorptionsgesetze: 𝑃 ∧ 𝑃 ∨ 𝑄 ⇔ 𝑃 𝑃 ∨ 𝑃 ∧ 𝑄 ⇔ 𝑃

• Idempotenzgesetze: 𝑃 ∧ 𝑃 ⇔ 𝑃 𝑃 ∨ 𝑃 ⇔ 𝑃

• Ausgeschlossener Dritter: 𝑃 ∧ ¬𝑃 ist immer falsch 𝑃 ∨ ¬𝑃 ist immer wahr„tertium non datur“

Siehe auch: Bronstein et al. – Taschenbuch der Mathematik (6. Auflage), Kapitel 5: Algebra und Diskrete Mathematik


Überlegung zu einer ersten „Rechenregel“

Sei 𝑃 die Aussage „Der Mathematikprofessor kommt zu spät und hat seine Unterlagen vergessen“.

Martina wettet mit ihrer Kommilitonin Andrea, dass 𝑃 in der heutigen Vorlesung wahr ist. Was muss geschehen, damit Martina die Wette verliert?

Antwort: Martina verliert, wenn 𝑃 falsch ist bzw. wenn ¬𝑃 wahr ist.

Wenn 𝑍 die Aussage „Der Professor kommt zu spät“ und 𝑈 die Aussage „Der Professor hat die Unterlagen vergessen“ ist, dann gilt: 𝑃 ⇔ 𝑍 ∧ 𝑈

Die Konjunktion ist falsch, wenn 𝑍 falsch ist, 𝑈 falsch ist, oder beide falsch sind.

Martina verliert also die Wette, wenn der Professor nicht zu spät kommt, wenn er seine Unterlagen nicht vergessen hat, oder wenn beides zutrifft.

Daraus folgt anschaulich die Regel: ¬ 𝑍 ∧ 𝑈 ⇔ ¬𝑍 ∨ ¬𝑈

Analog gilt für die Negation vom „oder“: ¬ 𝑍 ∨ 𝑈 ⇔ ¬𝑍 ∧ ¬𝑈


„Gesetze von DeMorgan“

Die Implikation unter der Lupe (1)

• Wenn 𝑃 ⇒ 𝑄 wahr ist, dann sagt man 𝑃 ist hinreichend für 𝑄

• Mit Implikationen wird geschlussfolgert, d.h. aus bekannten (wahren) Aussagen und den Axiomen werden (im durch Definitionen geschaffenen Rahmen) neue Wahrheiten bewiesen.

• Beispiel: Wir wissen, dass der Genuss von Schlumpfeis die Zunge für einige Minuten blau färbt.

Weiters ist bekannt, dass Schlaubi gerade eben ein Schlumpfeis gegessen hat.

⇒ Folgerung: Schlaubis Zunge ist blau!

Aber Vorsicht! Wenn Schlaubis Zunge blau ist, dann hat er nicht zwingend ein Schlumpfeis gegessen. Eine mögliche andere Ursache wären z.B. eine Sauerstoffunterversorgung.


𝑷 𝑸 𝑷 ⇒ 𝑸

w w w

w f f

f w w

f f w

Die Implikation unter der Lupe (2)

• Äquivalent zu 𝑃 ⇒ 𝑄 ist die sog. Kontraposition der Implikation (*): ¬𝑄 ⇒ ¬𝑃

• Aus diesem Grund nennt man im Fall 𝑃 ⇒ 𝑄 die Aussage 𝑄 notwendig für 𝑃

• Beispiel: Wir wissen: Genuss von Schlumpfeis ⇒ blaue Zunge

Wenn Clumsy keine blaue Zunge hat, dann folgt daraus, dass er kein Schlumpfeis gegessen hat

• Die Kontraposition ist ein wichtiges Werkzeug für formale Beweise und Argumentationen!

• Bemerkung: - Zur Negation ¬(𝑃 ⇒ 𝑄) äquivalent ist 𝑃 ∧ ¬𝑄 (*)

- Die Implikation ist transitiv, d.h. aus 𝑃 → 𝑄 ∧ (𝑄 → 𝑅) folgt 𝑃 → 𝑅• „Kettenschluss“

• Wenn 𝑃 → 𝑄 ∧ 𝑄 → 𝑅 ∧ (𝑅 → 𝑃), dann sind 𝑃,𝑄 und 𝑅 sogar äquivalent!

• Das Prinzip ist verallgemeinerbar auf beliebig viele Aussagen

(*) Beweise durch Vergleich der entsprechenden Wahrheitswerte in einer Wahrheitstafel


𝑷 𝑸 𝑷 ⇒ 𝑸

w w w

w f f

f w w

f f w

Mit doppelter Negationund DeMorgan gilt dannauch Folgendes:

𝑃 ⇒ 𝑄 ⇔ ¬𝑃 ∨ 𝑄

Prädikate

• Definition: Ein Prädikat (oder Aussageform) ist Stück Information, das eine Variable enthält (oder auch mehrere Variablen) und zu einer Aussage wird, wenn man anstelle der Variable ein zulässiges Objekt einsetzt (z.B. eine Zahl)

• Beispiel: 𝑃 𝑥 ∶⇔ „𝑥 ist teilbar durch 5“

• Eine Aussage mit eindeutigem Wahrheitswert ist 𝑃(𝑥) nur, wenn man 𝑃(𝑥) für ein konkretes 𝑥 betrachtet• 𝑃(−10) wäre z.B. wahr, 𝑃(13) und 𝑃(0.5) wären hingegen falsche Aussagen

• Mit Prädikaten wird gearbeitet, wenn man Aussagen über eine ganze Klasse von Objekten betrachten möchte bzw. für diese Objekte beweisen will.

• Z.B.: „Wenn die Dezimaldarstellung der Zahl 𝑥 ∈ ℤ mit einer 5 oder 0 endet, dann gilt 𝑃(𝑥)“

∀𝑥 ∈ ℤ: 𝑥 =

𝑘=0

𝑛

𝑎𝑘 ⋅ 10𝑘 ∧ 𝑛 ∈ ℕ ∧ 𝑎𝑘 ∈ 0,1,… , 9 ∧ 𝑎0 ∈ 0,5 ⇒ 𝑃 𝑥


Quantoren (1)

• Für die Arbeit mit Prädikaten benötigt man noch zwei Zutaten:

• Den Allquantor: ∀𝑥 ∈ 𝑀: 𝑃(𝑥) Sprich: „Für alle 𝑥 aus 𝑀 gilt 𝑃(𝑥)“

und

• den Existenzquantor: ∃𝑥 ∈ 𝑀: 𝑃(𝑥) Sprich: „Es gibt ein 𝑥 in 𝑀, sodass 𝑃(𝑥) gilt“

• Bemerkungen:

• Es muss mindestens ein solches 𝑥 geben, damit die ganze Aussage gilt. Mehrere sind auch erlaubt.

• Für die Aussage „es gibt genau ein 𝑥 in 𝑀, sodass 𝑃(𝑥) gilt“ schreibt man: ∃! 𝑥 ∈ 𝑀: 𝑃(𝑥)

Notiz: 𝑥 ∈ 𝑀 können wir uns (ohne Mengenlehre) hier vorstellen wie „Objekt 𝑥, das die durch 𝑀 gegebenen Eigenschaften erfüllt“


Quantoren (2)

• Die Quantoren wirken immer auf das Objekt direkt rechts und die All- oder Existenzaussage auf alles, was daneben rechts auf der gleichen „Vorrangebene“ steht.

• Die Reihenfolge, in der Quantoren verwendet werden, spielt eine wichtige Rolle!

• Die Doppelpunkte („sodass“ bzw. „gilt“) müssen nicht angeschrieben werden.

• Beispiel: ∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 𝑥𝑦 < 0 „Für jedes 𝑥 in 𝐴 gilt: man kann ein 𝑦 in 𝐵 finden, sodass 𝑥𝑦 < 0 gilt

∃𝑦 ∈ 𝐵 ∀𝑥 ∈ 𝐴 𝑥𝑦 < 0 “Es gibt ein 𝑦 in 𝐵, sodass für alle 𝑥 in 𝐴 die Ungleichung 𝑥𝑦 < 0 gilt

Anschaulich gelten beide Aussagen für: 𝐴 = −1, 1 und 𝐵 = {−2, 2}

Bemerkung: Bei den beiden Ausdrücken handelt es sich um Prädikate 𝑃(𝐴, 𝐵) und 𝑄(𝐴, 𝐵) mit je zwei Variablen, nämlich Mengen 𝐴 und 𝐵. Im Beispiel werden für diese Variablen konkrete Objekte (Mengen) eingesetzt und die beiden Ausdrücke gehen in Aussagen über. Die erste Aussage hat sich als wahr herausgestellt und die zweite als falsch.


Quantoren (3)

• Negationen: ¬ ∀𝑥 ∈ 𝑀: 𝑃 𝑥 ⇔ ∃𝑥 ∈ 𝑀: ¬𝑃(𝑥)

¬ ∃𝑥 ∈ 𝑀: 𝑃 𝑥 ⇔ ∀𝑥 ∈ 𝑀: ¬𝑃(𝑥)

• Beispiel: Betrachte „Alle ÖsterreicherInnen essen gerne Wiener Schnitzel“ ⇔ ∀𝑥 ∈ Ö: 𝑊(𝑥)

Ein befreundeter Grazer, Hans-Jörg, ist strikter Vegetarier ⇔ ∃𝑥 ∈ Ö: 𝑉 𝑥

Tatsache: „Wenn 𝑥 Vegetarier ist, dann isst 𝑥 nicht gerne Schnitzel“ ⇔ 𝑉 𝑥 ⇒ ¬𝑊(𝑥)

Insgesamt gilt also die Negation der Allaussage: ∃𝑥 ∈ Ö:¬𝑊 𝑥

⇒ Die obige Aussage ist somit falsch, da ein Gegenbeispiel gefunden wurde


Lektion 1b: Beweise

Das mathematische Arbeiten

und Beweisstrategien

Tutorium zur Analysis 1 - David Präsent 20W – L01: Aussagenlogik und mathematische Beweise

Die axiomatische Methode und Grundbegriffe des mathematischen Arbeitens


AxiomensystemEnthält Grundbegriffe einer mathematischen Theorie, die aber unerklärt bleiben. Es werden lediglich Eigenschaften festgelegt, die die elementaren Objekte erfüllen sollen

DefinitionenMit ihnen wird die Bedeutung von Begriffen und

Objekten im Kontext der Axiome festgelegt

SätzeAussagen, die ausschließlich aus den Axiomen und bereits

bewiesenen Sätzen mit formal-logischen Methoden im Bedeutungsrahmen der Definitionen als wahr bestätigt wurden

Lemmata / Hilfssätze

KorollareEinfache Schlussfolgerungen aus

Sätzen (z.B. ein Spezialfall)

THEORIE

Bew

eis

Vorsicht: Vereinfachung

FORMALES SYSTEM (Logik)

Wid

ersp

ruch

sfre

ihei

t

Mathematische Beweise (1)

• Mathematische Fragestellungen sind meistens wie folgt aufgebaut:

• „Es gilt 𝑃“

• „Zu zeigen ist, dass unter diesen Voraussetzungen 𝑄 gilt“

• oder: „Zu zeigen ist, dass 𝑃 äquivalent zu 𝑄 ist

• 𝑃 ist eine Liste von Voraussetzungen mit Bedeutung lt. Definitionen.

• In 𝑃 sind streng genommen stets die Axiome und Wahrheiten des verwendeten Systems enthalten. Sie dürfen in einem gültigen Beweis, wie die explizit spezifizierten Voraussetzungen, natürlich auch nicht verletzt werden.

Je nachdem für welche Strategie man sich entscheidet, wird der Beweis unterschiedlich argumentiert.


Formalisiert:

z.z.: 𝑃 ⇒ 𝑄

bzw. 𝑃 ⇔ 𝑄

Mathematische Beweise (2)

• Mathematische Aussagen kann man grob in zwei Arten einteilen:

• All-Aussagen: „Für alle Objekte eines bestimmten Typs gilt unter den gegebenen Voraussetzungen ...“

• Existenzaussagen: „Es gibt ein Objekt bestimmten Typs, für das unter den Voraussetzungen gilt, dass, ...“

• Beweise können auch unter verschiedenen Gesichtspunkten kategorisiert werden:

• Art der Argumentation (siehe ‚Beweisstrategien‘)

• Konstruktive oder nicht-konstruktive Beweise


Beweisstrategien (1)

• Direkter Beweis: aus 𝑃 ∧ (𝑃 → 𝑄) folgt 𝑄(modus ponens)

• Indirekter Beweis via Kontraposition: aus ¬𝑄 ∧ (𝑃 → 𝑄) folgt ¬𝑃(modus tollens)

• Fallunterscheidungen: aus 𝑃 ∨ 𝑄 ∧ 𝑃 → 𝑅 ∧ (𝑄 → 𝑅) folgt 𝑅

• Kettenschluss aus 𝑃 → 𝑄 ∧ (𝑄 → 𝑅) folgt 𝑅

• Sonstige:• Vollständige Induktion

• Taubenschlagprinzip bzw. Schubfachprinzip

• Diagonalargument

• Prinzip des unendlichen Abstiegs

• ...


Beweisstrategien (2)

• Indirekter Beweis durch Widerspruch:(reductio ad absurdum)

• Bei Fragen vom Typ „gilt 𝑃 ⇒ 𝑄?“ kann oft das folgende Schema angewendet werden:

• Angenommen die Aussage stimmt nicht, d.h. ¬(𝑃 ⇒ 𝑄) ist wahr (was äquivalent ist zu 𝑃 ∧ ¬𝑄)

• Dann folgt (nach einiger Arbeit mit der Annahme) daraus ¬𝑃

• Insgesamt gilt also 𝑃 ∧ ¬𝑃, was aber einen Widerspruch zum „Ausgeschlossenen Dritten“ darstellt ↯

• Somit muss die Annahme falsch gewesen sein, also gilt 𝑃 ⇒ 𝑄


Eine Frage, zwei Beweise

Zu zeigen ist: Wenn 3𝑛 + 2 ungerade ist, dann ist auch 𝑛 ungerade Genauer: ∀𝑛 ∈ ℤ: 𝑃 𝑛 ⇒ 𝑄 𝑛

Direkter Beweis: Sei 3𝑛 + 2 ungerade. Folglich gilt für ein 𝑘 ∈ ℤ: 3𝑛 + 2 = 2𝑘 − 1

⇒ 3 𝑛 + 1 = 2𝑘 ⇒ 𝑘 =3(𝑛+1)

2⇒𝑛+1

2∈ ℤ ⇒ 𝑛 + 1 gerade ⇒ 𝑛 ungerade ∎ q.e.d

Indirekter Beweis: Wir zeigen, dass die Kontraposition gilt, also 𝑛 gerade ⇒ 3𝑛 + 2 gerade

(Kontraposition)

Sei 𝑛 gerade, d.h. 𝑛 = 2𝑚 für 𝑚 ∈ ℤ. ⇒ 3𝑛 + 2 = 3 2𝑚 + 2 = 2 (3𝑚 + 1) … gerade ∎ q.e.d

Übung: Gilt die Umkehrung, also ∀𝑛 ∈ ℤ: 𝑄 𝑛 ⇒ 𝑃(𝑛) ?


Ein eleganter Beweis

Zu zeigen ist: „Es gibt zwei irrationale Zahlen 𝑎 und 𝑏, sodass 𝑎𝑏 rational ist“

Formalisiert: ∃𝑎, 𝑏 ∈ ℝ ∖ ℚ ∶ 𝑎𝑏 ∈ ℚ

Beweis: Betrachte den Ausdruck 𝑋 ≔ 22. Vorausgesetzt wird hier das Wissen, dass 2 irrational ist.

Wenn 𝑋 rational ist, dann wählen wir 𝑎 = 𝑏 = 2 und die Aussage wäre bewiesen.

Wenn andernfalls 𝑋 irrational ist, dann wählen wir 𝑎 = 𝑋 und 𝑏 = 2.

Dann wäre 𝑎𝑏 = 222

= 22 ⋅ 2= 2

2= 2 =

2

1, also eine rationale Zahl. ∎ q.e.d.

Beobachtungen: Zu beweisen war eine Existenzaussage, die mit der Methode der Erschöpfung (Fallunterscheidung) als wahr bestätigt wurde. Interessant ist hierbei, dass man gar nicht wissen muss, ob die in der Argumentation verwendete Zahl 𝑋 irrational ist oder nicht.


Noch ein Klassiker unter den Beweisen

Zu zeigen ist: „Es gibt unendlich viele Primzahlen“

Beweis: Angenommen es gibt nur endlich viele Primzahlen, nämlich 𝑛 an der Zahl. Dann könnte man sie geordnet in eine (Euklid) Liste schreiben:

ℙ = {𝑝1, 𝑝𝑛, … , 𝑝𝑛}

Laut Definition hat eine Primzahl nur 1 und sich selbst als Teiler. Jede Nicht-Primzahl kann somit durch eine Primzahl geteilt werden (*).

Betrachte nun die Zahl 𝑞 ≔ 𝑝1 ⋅ 𝑝2 ⋅ … ⋅ 𝑝𝑛 + 1 > 𝑝𝑛

Die Zahl 𝑞 unterscheidet sich also um 1 von einem Vielfachen jeder Primzahl, kann deshalb durch keine der Zahlen in ℙ geteilt werden; wegen (*) folglich auch durch keine andere ganze Zahl.

⇒ 𝑞 ist eine weitere Primzahl ↯ ⇒ es gibt unendlich viele Primzahlen ∎ q.e.d.

Beobachtungen: Die Voraussetzungen für diesen Widerspruchsbeweis sind hier etwas versteckt: Es handelt sich hierbei vorrangig um Grundlagen zu natürlichen Zahlen, aus der Arithmetik und aus der Zahlentheorie.


Documents

Lektion 1a: Aussagenlogikdpraesent.at/anatut20/praesentation_L01_-_Logik_und... · 2020. 10. 3. · Vorrangregeln der Aussagenlogik •Formale Aussagen werden prinzipiell von links