476 lines
21 KiB
Markdown
476 lines
21 KiB
Markdown
|
# Grundbegriffe und elementare Logik
|
||
|
|
## Aussagen, Prädikate, Junktoren und Quantoren
|
||
|
|
### Aussage
|
||
|
|
Eine Aussage beschreibt ein bestimmbares Objekt und deren Eigenschaften - diese lassen sich eindeutig bestätigen oder verneinen.
|
||
|
|
|
||
|
|
> **_Beispiel einer wahren Aussage:_**
|
||
|
|
> "Die Zahl $3$ ist eine Primzahl"
|
||
|
|
>
|
||
|
|
> **_Beispiel einer unwahren Aussage:_**
|
||
|
|
> "Die Zahl $4$ ist eine Primzahl"
|
||
|
|
|
||
|
|
#### Elementaraussagen und zusammengesetzte Aussagen
|
||
|
|
Eine spezielle Art von Aussage ist die sogenannte "Elementaraussage". Hierbei handelt es sich um eine Aussage, die nicht weiter aufgeteilt werden kann.
|
||
|
|
|
||
|
|
Alle anderen Aussagen lassen sich weiter aufteilen und sind somit "zusammengesetzte Aussagen".
|
||
|
|
|
||
|
|
> **_Zum Vergleich:_**
|
||
|
|
> - Elementaraussage:
|
||
|
|
> "Eine Woche hat 7 Tage" ist eine Elementaraussage
|
||
|
|
> - Zusammengesetzte Aussage:
|
||
|
|
> "ein Tag hat 24 Stunden **und** eine Woche hat 7 Tage" eine
|
||
|
|
>
|
||
|
|
> Mehr zu zusammengesetzten Aussagen unter [Junktoren](#junktoren)
|
||
|
|
|
||
|
|
### Prädikat
|
||
|
|
Falls das Objekt, über welches eine Aussage getätigt wird, ohne Einschränkungen frei wählbar ist, handelt es sich nicht um eine Aussage, sondern um ein Prädikat.
|
||
|
|
|
||
|
|
Prädikate, welche von einer Variable abhängen nennen sich "Einstelliges Prädikat".
|
||
|
|
|
||
|
|
> **_Beispiele:_**
|
||
|
|
> - $A(x)$ = "Die gegebene Zahl $x$ ist eine Primzahl"
|
||
|
|
> - $A(x) = x < 3$
|
||
|
|
|
||
|
|
Prädikate, welche von zwei Variablen abhängen nennen sich "Zweiteiliges Prädikat".
|
||
|
|
|
||
|
|
> **_Beispiel:_**
|
||
|
|
> $$A(x, y) = x < y$$
|
||
|
|
|
||
|
|
Mit Hilfe von Prädikaten können auch Aussagen erstellt werden:
|
||
|
|
|
||
|
|
> **_Beispiel:_**
|
||
|
|
>
|
||
|
|
> **_Prädikat:_** $A(x) = x > 100$
|
||
|
|
> **_Aussage:_** $A(10) = 10 > 100$
|
||
|
|
>
|
||
|
|
> Hierbei ist $A$ der Name einer Funktion.
|
||
|
|
|
||
|
|
### Junktoren
|
||
|
|
#### Zusammengesetzte Aussagen
|
||
|
|
Zusammengesetzte Aussagen sind Aussagen, die aus Elementaraussagen bestehen, die durch sogenannte [`Junktoren`](#junktoren) verknüpft werden.
|
||
|
|
|
||
|
|
> **_Beispiel:_**
|
||
|
|
> $$A:=\text{"78 ist keine Primzahl"}$$
|
||
|
|
> $$B:=\text{"15 ist keine Primzahl"}$$
|
||
|
|
> $$C:=\text{"78 ist keine Primzahl und 15 ist keine Primzahl"}$$
|
||
|
|
|
||
|
|
$A$ und $B$ sind Elementaraussagen, $C$ ist eine zusammengesetzte Aussage.
|
||
|
|
|
||
|
|
#### 1. Negation
|
||
|
|
Die Negation wird üblicherweise als "nicht" gesprochen. In Formeln wird die Negation mit dem Symbol $\neg$ geschrieben.
|
||
|
|
|
||
|
|
Als Beispiel - $f$ für "falsch" und $w$ für "wahr":
|
||
|
|
|
||
|
|
| $A$ | $\neg A$ |
|
||
|
|
| :---: | :------: |
|
||
|
|
| $f$ | $w$ |
|
||
|
|
| $w$ | $f$ |
|
||
|
|
|
||
|
|
Bzw. mit $0$ für "falsch" und $1$ für "wahr":
|
||
|
|
|
||
|
|
| $A$ | $\neg A$ |
|
||
|
|
| :---: | :------: |
|
||
|
|
| $0$ | $1$ |
|
||
|
|
| $1$ | $0$ |
|
||
|
|
|
||
|
|
> **_Beispiel:_**
|
||
|
|
> $$A:=\text{"Hans studiert an der ZHAW"}$$
|
||
|
|
> $$\neg A:=(\text{"Hans studiert nicht an der ZHAW"})$$
|
||
|
|
> $$\neg A:=\text{"Es trifft nicht zu, dass Hans an der ZHAW studiert"}$$
|
||
|
|
|
||
|
|
#### 2. Konjunktion
|
||
|
|
Die Konjunktion wird als "und" gesprochen und mit dem Zeichen $\wedge$ geschrieben.
|
||
|
|
|
||
|
|
> **_Beispiel:_**
|
||
|
|
> $$A:=\text{"6 ist durch 2 teilbar"}: wahr$$
|
||
|
|
> $$B:=\text{"8 ist durch 5 teilbar"}: falsch$$
|
||
|
|
> $$A \wedge B :=\text{"6 ist durch 2 teilbar und 8 ist durch 5 teilbar"}: falsch$$
|
||
|
|
|
||
|
|
| $A$ | $B$ | $A \wedge B$ |
|
||
|
|
| :---: | :---: | :----------: |
|
||
|
|
| $0$ | $0$ | $0$ |
|
||
|
|
| $0$ | $1$ | $0$ |
|
||
|
|
| $1$ | $0$ | $0$ |
|
||
|
|
| $1$ | $1$ | $1$ |
|
||
|
|
|
||
|
|
> **_Beispiel:_**
|
||
|
|
> Falls A und B wahr sind:
|
||
|
|
> $A$: w
|
||
|
|
> $B$: w
|
||
|
|
>
|
||
|
|
> 1. $A \wedge B$: w
|
||
|
|
> 2. $\neg A \wedge B$: f
|
||
|
|
> 3. $A \wedge \neg B$: f
|
||
|
|
> 4. $\neg A \wedge \neg B$: f
|
||
|
|
|
||
|
|
#### 3. Disjunktion
|
||
|
|
Die Disjunktion wird als "oder" gesprochen und mit dem Zeichen $\vee$ dargestellt.
|
||
|
|
|
||
|
|
**_Beispiel:_**
|
||
|
|
> $$A:=\text{"9 ist durch 3 teilbar"}: wahr$$
|
||
|
|
> $$B:=\text{"9 ist eine Quadratzahl"}: wahr$$
|
||
|
|
> $$A \vee \neg B:=\text{"9 ist durch 3 teilbar oder 9 ist keine Quadratzahl"}: wahr$$
|
||
|
|
|
||
|
|
Ist eine der Aussagen der Disjunktion wahr, so ist auch die Disjunktion wahr.
|
||
|
|
|
||
|
|
| $A$ | $B$ | $A \vee B$ |
|
||
|
|
| :---: | :---: | :--------: |
|
||
|
|
| $0$ | $0$ | $0$ |
|
||
|
|
| $0$ | $1$ | $1$ |
|
||
|
|
| $1$ | $0$ | $1$ |
|
||
|
|
| $1$ | $1$ | $1$ |
|
||
|
|
|
||
|
|
#### 4. Implikation
|
||
|
|
Die Implikation wird als "wenn $A$, dann $B$" ausgesprochen und in Formeln mit dem Zeichen $\Rightarrow$ geschrieben.
|
||
|
|
|
||
|
|
Sollte $A$ nicht zutreffen, ist das Ergebnis immer wahr ($w$ bzw. $1$).
|
||
|
|
|
||
|
|
> **_Beispiel:_**
|
||
|
|
> $$A:=\text{"Es regnet"}$$
|
||
|
|
> $$B:=\text{"Die Wiese ist nass"}$$
|
||
|
|
|
||
|
|
| $A$ | $B$ | $A \Rightarrow B$ |
|
||
|
|
| :---: | :---: | :---------------: |
|
||
|
|
| $0$ | $0$ | $1$ |
|
||
|
|
| $0$ | $1$ | $1$ |
|
||
|
|
| $1$ | $0$ | $0$ |
|
||
|
|
| $1$ | $1$ | $1$ |
|
||
|
|
|
||
|
|
> ***Merksätze:***
|
||
|
|
> - Wenn $A$ wahr ist, muss auch $B$ wahr sein.
|
||
|
|
> - Wenn $A$ falsch ist, kann $B$ wahr oder falsch sein.
|
||
|
|
|
||
|
|
> **_Beispiel 2:_**
|
||
|
|
> $$A:=\text{"Es gibt Einhörner"}: falsch$$
|
||
|
|
> $$B:=\text{"4 ist eine Primzahl"}: falsch$$
|
||
|
|
>
|
||
|
|
> $$C:=\text{"Wenn es Einhörner gibt, ist 4 eine Primzahl"}: wahr$$
|
||
|
|
|
||
|
|
> ***Note:***
|
||
|
|
> "Falls es Einhörner gibt, ist 4 eine Primzahl."
|
||
|
|
> Einhörner existieren nicht und 4 ist keine Primzahl - die Aussage ist also richtig... bis zum Fund des ersten Einhorns zumindest. :unicorn:
|
||
|
|
|
||
|
|
> **_Beispiel 3:_**
|
||
|
|
> $$A:=\text{"Spinat ist grün"}$$
|
||
|
|
> $$B:=\text{"2 ist eine Primzahl"}$$
|
||
|
|
|
||
|
|
> **_Beispiel 4:_**
|
||
|
|
> $$A:=\text{"Alle Fische leben im Ozean"}$$
|
||
|
|
> $$B:=\text{"Forellen leben im Ozean"}$$
|
||
|
|
> $$C:=\text{"Haie leben im Ozean"}$$
|
||
|
|
> $\underbrace{\text{Alle Fische leben im Ozean}}_{A\text{: falsch}} \Rightarrow \underbrace{\text{Haie leben im Ozean}}_{C\text{: wahr}}$: wahr
|
||
|
|
> $\underbrace{\text{Alle Fische leben im Ozean}}_{A\text{: falsch}} \Rightarrow \underbrace{\text{Forellen leben im Ozean}}_{\text{B: falsch}}$: wahr
|
||
|
|
|
||
|
|
> **_Note:_**
|
||
|
|
> _ex falso sequitur quodlibet_ (lateinisch für "aus Falschem folgt Beliebigest"), abgekürzt "e.f.q" oder eindeutiger _contradictione sequitur quodlibet_ (lateinisch für "aus einem Widerspruch folgt Beliebiges), bezeichnet im eigenen Sinn eines der beiden in vielen logischen Systemen gültigen Gesetze:
|
||
|
|
> 1. Aus einem logisch - nicht bloss faktisch - falschen Satz folgt jede beliebige Aussage.
|
||
|
|
> 2. Aus zwei widersprüchlichen Sätzen folgt jede beliebige Aussage.
|
||
|
|
|
||
|
|
#### 5. Äquivalenz
|
||
|
|
Die Äquivalenz wird "ist gleich" ausgesprochen und mit dem Zeichen $\Leftrightarrow$ geschrieben.
|
||
|
|
|
||
|
|
Dieser Junktor beschreibt, dass beide Aussagen äquivalent sind. In diesem Fall gilt:
|
||
|
|
|
||
|
|
$$A \Rightarrow B \wedge B \Rightarrow A$$
|
||
|
|
|
||
|
|
> **_Merksatz:_**
|
||
|
|
> "$A$ gilt genau dann, wenn $B$ gilt"
|
||
|
|
|
||
|
|
| $A$ | $B$ | $A \Leftrightarrow B$ |
|
||
|
|
| :---: | :---: | :-------------------: |
|
||
|
|
| $0$ | $0$ | $1$ |
|
||
|
|
| $0$ | $1$ | $0$ |
|
||
|
|
| $1$ | $0$ | $0$ |
|
||
|
|
| $1$ | $1$ | $1$ |
|
||
|
|
|
||
|
|
> **_Beispiel:_**
|
||
|
|
> $A(x):=x^2=4$ und $B(x):=x=2$
|
||
|
|
>
|
||
|
|
> in $\mathbb{Z}$:
|
||
|
|
> $$B(x) \Rightarrow A(x): wahr$$
|
||
|
|
>
|
||
|
|
> in $\mathbb{N}$:
|
||
|
|
> $$A(x) \Rightarrow B(x): wahr$$
|
||
|
|
> $$B(x) \Rightarrow A(x): wahr$$
|
||
|
|
> $$A(x) \Leftrightarrow A(x): wahr$$
|
||
|
|
|
||
|
|
#### Reihenfolge der Bindungen
|
||
|
|
Die Reihenfolge der Bindungen beschreibt, welcher Operator die höchste Priorität hat.
|
||
|
|
|
||
|
|
- $\neg$
|
||
|
|
- $\wedge$
|
||
|
|
- $\vee$
|
||
|
|
- $\Rightarrow$
|
||
|
|
- $\Leftrightarrow$
|
||
|
|
|
||
|
|
Wie zu sehen ist, hat $\neg$ die höchste Priorität. Schreibt man also eine Operation wie etwa $\neg A \wedge B$, muss $A$ negiert werden bevor die `AND` ($\wedge$)-operation berechnet wird: $(\neg A) \wedge B$.
|
||
|
|
|
||
|
|
Des weiteren hat `AND` ($\wedge$) eine höhere Priorität als `OR` ($\vee$). So muss also in der Rechnung $A \vee B \wedge C$ der Term $B \wedge C$ als erstes berechnet werden: $A \vee (B \wedge C)$.
|
||
|
|
|
||
|
|
#### Junktorenregeln
|
||
|
|
Junktorenregeln sind Regeln, wie man Aussagen umformen kann, sodass die Aussage (bzw. deren Bedingungen und Resultat) dieselbe ist.
|
||
|
|
|
||
|
|
##### Regel der doppelten Negation
|
||
|
|
$\neg\neg A \Leftrightarrow A$
|
||
|
|
|
||
|
|
##### Kommutativität
|
||
|
|
$A \wedge B \Leftrightarrow B \wedge A$ und $A \vee B \Leftrightarrow B \vee A$
|
||
|
|
|
||
|
|
##### Assoziativität
|
||
|
|
$(A \wedge B) \wedge C \Leftrightarrow A \wedge (B \wedge C)$
|
||
|
|
$(A \vee B) \vee C \Leftrightarrow A \vee (B \vee C)$
|
||
|
|
|
||
|
|
##### Distributivität
|
||
|
|
$A \wedge (B \vee C) \Leftrightarrow (A \wedge B) \vee (A \wedge C)$
|
||
|
|
$A \vee (B \wedge C) \Leftrightarrow (A \vee B) \wedge (A \vee C)$
|
||
|
|
|
||
|
|
> **_Note:_**
|
||
|
|
> Es kann helfen, sich beim Umformen der Rechenoperationen die herkömmlichen Operationen $\times$ (Mal) und $+$ (Plus) vorzustellen, um eine Idee davon zu bekommen, wie die Operation vereinfacht werden muss:
|
||
|
|
>
|
||
|
|
> $$\underbrace{A}_{x} \underbrace{\wedge}_{\times}(\underbrace{B}_{y} \underbrace{\vee}_{+} \underbrace{C}_{z})\\
|
||
|
|
> x \times (y + z) \Leftrightarrow (x \times y) + (x \times z)$$
|
||
|
|
> Verglichen mit:
|
||
|
|
> $$(\overbrace{A}^{x} \overbrace{\wedge}^{\times} \overbrace{B}^{y}) \overbrace{\vee}^{+} (\overbrace{A}^{x} \overbrace{\wedge}^{\times} \overbrace{C}^{z})$$
|
||
|
|
> Dieselbe Vorgangsweise lässt sich sowohl für Operationen mit $\wedge$ als auch mit $\vee$ anwenden:
|
||
|
|
> $$\overbrace{A}^{x} \overbrace{\vee}^{\times}(\overbrace{B}^{y} \overbrace{\wedge}^{+} \overbrace{C}^{z}) \overbrace{\Rightarrow}^{\Rightarrow}
|
||
|
|
> (\overbrace{A}^{x} \overbrace{\vee}^{\times} \overbrace{B}^{y}) \overbrace{\wedge}^{+} (\overbrace{A}^{x} \overbrace{\vee}^{\times} \overbrace{C}^{z})$$
|
||
|
|
|
||
|
|
##### Regeln von De Morgan
|
||
|
|
$\neg (A \wedge B) \Leftrightarrow \neg A \vee \neg B$
|
||
|
|
$\neg (A \vee B) \Leftrightarrow \neg A \wedge \neg B$
|
||
|
|
|
||
|
|
> **_Beispiel:_**
|
||
|
|
> | Rechnung | Nächster Vorgang |
|
||
|
|
> | ------------------------------------------------ | ----------------- |
|
||
|
|
> | $A \Rightarrow B$ | |
|
||
|
|
> | $\Leftrightarrow \neg A \vee B$ | |
|
||
|
|
> | $\Leftrightarrow \neg\neg(\neg A \vee B)$ | Doppelte Negation |
|
||
|
|
> | $\Leftrightarrow \neg(\neg\neg A \wedge \neg B)$ | De Morgan |
|
||
|
|
> | $\Leftrightarrow \neg(A \wedge \neg B)$ | |
|
||
|
|
> | $\Leftrightarrow \neg A \vee \neg\neg B$ | De Morgan |
|
||
|
|
> | $\Leftrightarrow \neg\neg B \vee \neg A$ | Kommutativ |
|
||
|
|
> | $\Leftrightarrow \neg B \Rightarrow \neg A$ | |
|
||
|
|
|
||
|
|
> **_In Worten:_**
|
||
|
|
> "Wenn es regnet, ist die Wiese nass" ($A \Rightarrow B$)
|
||
|
|
> "Wenn die Wiese nicht nass ist, regnet es nicht. ($\neg B \Rightarrow \neg A$)
|
||
|
|
|
||
|
|
> **_Hinweis:_**
|
||
|
|
> Diese Umformung ($\neg B \Rightarrow \neg A$) ist nicht dasselbe wie $\neg(A \Rightarrow B)$
|
||
|
|
>
|
||
|
|
> Weil:
|
||
|
|
> $$\neg(A \Rightarrow B)\\
|
||
|
|
> \Leftrightarrow \neg(\neg A \vee B)\\
|
||
|
|
> \Leftrightarrow \neg\neg A \wedge \neg B\\
|
||
|
|
> \Leftrightarrow A \wedge \neg B$$
|
||
|
|
|
||
|
|
##### Kontraposition
|
||
|
|
$$A \Rightarrow B \Leftrightarrow \neg B \Rightarrow \neg A$$
|
||
|
|
|
||
|
|
### Quantoren
|
||
|
|
Weg um ein Prädikat in eine Aussage umzuformen.
|
||
|
|
|
||
|
|
**_Beispiel:_**
|
||
|
|
$P(x):=\text{"x ist eine natürliche Zahl"}$: Prädikat
|
||
|
|
$P(5):=\text{"5 ist eine natürliche Zahl"}$: Aussage
|
||
|
|
|
||
|
|
In dieser Aussage ist die Variable $x$ gebunden ($x = 5$).
|
||
|
|
|
||
|
|
$\text{"Es gibt mindestens ein }x \in \mathbb{Z}\text{, so dass }P(x)\text{ gilt."}$: Aussage
|
||
|
|
$\text{"Für alle }x \in \mathbb{Z}\text{ gilt }P(x)$.": Aussage
|
||
|
|
|
||
|
|
Quantoren sind Symbole, anhand derer wir aus Prädikaten oder Aussagen gewinnen können. Wir betrachten das Beispiel des Prädikates:
|
||
|
|
|
||
|
|
$$A(x) := \text{"x ist eine Primzahl und x ist ein Teiler von 24"}$$
|
||
|
|
$$B:=\text{"es gibt eine Primzahl welche ein Teiler von 24 ist"}$$
|
||
|
|
|
||
|
|
mit anderen Worten:
|
||
|
|
|
||
|
|
$$B:= \text{"Es existiert ein x mit A(x)".}$$
|
||
|
|
|
||
|
|
Ein n-stelliges Prädikat wird durch Quantifizierung stets zu einem neuen $n-1$ stelligen Prädikat
|
||
|
|
|
||
|
|
> **_Beispiel:_**
|
||
|
|
> $$A(x, y):= x < y$$
|
||
|
|
> Bei der Funktion $A$ handelt es sich um ein 2-stelliges Prädikat. Die beiden Parameter heissen $x$ und $y$.
|
||
|
|
> $$B(y):= \forall x \in \mathbb{R} A(x, y)$$
|
||
|
|
> Anders als die Funktion $A$ hat die Funktion $B$ nur einen Parameter namens $y$. Das Prädikat $B$ ist somit 1-stellig.
|
||
|
|
|
||
|
|
#### Operatoren
|
||
|
|
Es gibt zwei verschiedene Quantoren, dessen Eigenschaften im Folgenden kurz aufgezeigt werden.
|
||
|
|
|
||
|
|
| Symbol | Bezeichnung | Beschreibung | Gesprochen |
|
||
|
|
| --------- | --------------- | ----------------------------- | --------------- |
|
||
|
|
| $\forall$ | Allquantor | universelle Quantifizierung | "für alle" |
|
||
|
|
| $\exists$ | Existenzquantor | existenzielle Quantifizierung | "für mind. ein" |
|
||
|
|
|
||
|
|
> **_Beispiele:_**
|
||
|
|
> $A(x, y) := x < y$
|
||
|
|
> $\forall x \in \mathbb{R}(\exists y \in \mathbb{R} A(x, y))$
|
||
|
|
> In Worten: "Für alle $x$ in den reellen Zahlen gibt es mindestens ein $y$, das grösser ist. Diese Aussage ist wahr.
|
||
|
|
>
|
||
|
|
> $B(x) := \text{"}x\text{ kann programmieren"}$
|
||
|
|
> $I := Menge der Informatiker$
|
||
|
|
> $A := \forall x \in I B(x) \Leftrightarrow \text{"Alle Informatiker können programmieren"}$
|
||
|
|
> $\text{"Alles, was ein Informatiker ist, kann programmieren"}$
|
||
|
|
> $\Leftrightarrow \forall x (x \in I \Rightarrow B(x))$
|
||
|
|
|
||
|
|
Ausdrücke wie $\forall_x \forall_y A(x, y)$ können zu $\forall_{x,y} A(x,y)$ gekürzt werden.
|
||
|
|
|
||
|
|
#### Regeln
|
||
|
|
1. Klammern
|
||
|
|
Quantoren binden stärker als Junktoren:
|
||
|
|
$\forall x \in M B(x) \wedge C(x) \Leftrightarrow (\forall x \in M B(x)) \wedge C(x)$
|
||
|
|
nicht dasselbe wie:
|
||
|
|
$\forall x \in M (B(x) \wedge C(x))$
|
||
|
|
|
||
|
|
2. Abkürzungen
|
||
|
|
$\forall x \in M (\forall y \in M A(x,y)) \Leftrightarrow \forall_{x,y} \in M A(x,y)$
|
||
|
|
$\exists x \in M (\exists y \in M A(x,y)) \Leftrightarrow \exists_{x,y} \in M A8x,y)$
|
||
|
|
Falls die Menge klar ist, kann diese von den Faktoren weggelassen werden:
|
||
|
|
$\forall x A(x)$ statt $\forall x \in M A(x)$
|
||
|
|
3. Negation
|
||
|
|
$\neg \exists_x \in M A(x) \Leftrightarrow \forall_x \in M \neg A(x)$
|
||
|
|
$\neg \forall_x \in M A(x) \Leftrightarrow \exists_in \in M \neg A(x)$
|
||
|
|
|
||
|
|
#### Beispielsätze
|
||
|
|
|
||
|
|
| In Worten | Operation |
|
||
|
|
| ---------------------------------- | ------------------------------------------------------------------------------------------------------ |
|
||
|
|
| Alle Prüfungen sind einfach | $\forall_x \in P E(x)$ |
|
||
|
|
| Eine Prüfung ist einfach | $\exists_x \in P E(x)$ |
|
||
|
|
| Keine Prüfung ist einfach | $\exists_x \in P E(x)$ |
|
||
|
|
| Alle Prüfungen sind nicht einfach | $\forall_x \in P \neg E(x)$ |
|
||
|
|
| Nur eine Prüfung ist einfach | $(\exists_x \in P E(x)) \wedge (\forall_{y,z} \in P (E(y) \wedge E(z) \Rightarrow y=z))$ |
|
||
|
|
| Nur eine Prüfung ist nicht einfach | $(\exists_x \in P \neg E(x)) \wedge (\forall_{y,z} \in P (\neg E(y) \wedge \neg E(z) \Rightarrow y=z)$ |
|
||
|
|
| Nicht alle Prüfungen sind einfach | $\neg \forall_x \in P E(x))$ |
|
||
|
|
| Eine Prüfung ist nicht einfach | $\exists_x \in P \neg E(x)$ |
|
||
|
|
|
||
|
|
#### Vereinfachungen
|
||
|
|
| Term | Vereinfachung |
|
||
|
|
| ------------------------------------ | ---------------------- |
|
||
|
|
| $\neg \exists_x \neg A(x)$ | $\forall_x A(x)$ |
|
||
|
|
| $\neg \exists_x \in K \neg A(x)$ | $\forall_x \in K A(x)$ |
|
||
|
|
| $\forall_x(x\in K \Rightarrow A(x))$ | $\forall_x \in K A(x)$ |
|
||
|
|
| $\exists_x (x \in K \wedge A(x))$ | $\exists_x \in K A(x)$ |
|
||
|
|
|
||
|
|
## Grundlegende Beweistechniken
|
||
|
|
### Direkter Beweis einer Implikation
|
||
|
|
Es gilt, eine Implikation zu beweisen:
|
||
|
|
$$A \Rightarrow B$$
|
||
|
|
|
||
|
|
Beweisen, dass in allen Fällen, in denen $A$ wahr ist, auch $B$ wahr ist.
|
||
|
|
|
||
|
|
Dies geschieht durch das Beweisen der Allgemeingültigkeit durch Nutzung von Variablen an Stelle von konkreten Werten.
|
||
|
|
|
||
|
|
> ***Beispiel:***
|
||
|
|
> - $A$: "$x$ und $y$ sind gerade."
|
||
|
|
> - $B$: "$x \cdot y$ ist gerade."
|
||
|
|
> - $A \Rightarrow B$: "Wenn $x$ und $y$ gerade sind, ist auch $x \cdot y$ gerade.
|
||
|
|
>
|
||
|
|
> ***Beweis:***
|
||
|
|
> $$x = 2 \cdot n_x$$
|
||
|
|
> $$y = 2 \cdot n_y$$
|
||
|
|
> $$x \cdot y = (2 \cdot n_x) \cdot (2 \cdot n_y)$$
|
||
|
|
> $$\Leftrightarrow 2 \cdot (n_x \cdot 2 \cdot n_y)$$
|
||
|
|
> $x \cdot y$ ist also durch 2 teilbar und ist somit gerade.
|
||
|
|
|
||
|
|
### Beweis durch Widerspruch
|
||
|
|
Es gilt zu beweisen, dass eine Aussage $A$ wahr ist.
|
||
|
|
|
||
|
|
Die Lösungsstrategie hierbei ist, zu beweisen, dass die Negation der Aussage falsch ist.
|
||
|
|
|
||
|
|
> ***Beispiel:***
|
||
|
|
> - $A$: "Es gibt keine grösste natürliche Zahl"
|
||
|
|
>
|
||
|
|
> Die negierte Annahme $A$, entspricht der, dass es eine grösste natürliche Zahl $m$ gibt.
|
||
|
|
>
|
||
|
|
> Für jede natürliche Zahl $n \in \mathbb{N}$ gilt, dass es einerseits eine nächstgrössere Natürliche Zahl $o = n + 1$ für die $o > n$ gilt.
|
||
|
|
>
|
||
|
|
> Da auch die angenommene grösste Zahl $m$ eine natürliche Zahl $n \in \mathbb{N}$ ist, gilt auch für $m$, dass es eine folgezahl $o$ gibt, die grösser ist. Dies kann als Beweis interpretiert werden, dass die Aussage $A$ wahr ist.
|
||
|
|
|
||
|
|
### Beweis durch (Gegen-)Beispiel
|
||
|
|
Es gilt zu zeigen, dass eine bestimmte bestimmte Aussage nicht auf alle Elemente zutrifft.
|
||
|
|
|
||
|
|
Dies geschieht, indem man ein Beispiel oder ein Gegenbeispiel für die vorliegende Aussage findet.
|
||
|
|
|
||
|
|
> ***Beispiele in Worte:***
|
||
|
|
> - $A$: "Alle Schweine sind rosa."
|
||
|
|
> - Gegenbeispiel $B$: "Die Schweine, die Kenny getötet haben, sind aber nicht rosa!"
|
||
|
|
>
|
||
|
|
> - $A$: "Es gibt Wochentage, die nicht mit '-tag' enden."
|
||
|
|
> - Beispiel $B$: "Mittwoch."
|
||
|
|
|
||
|
|
> ***Beispiel:***
|
||
|
|
> - $A$: "Nicht jede natürliche Zahl ist eine Quadratzahl einer natürlichen Zahl."
|
||
|
|
> oder in alternativer Ausdrucksweise:
|
||
|
|
> $A$: "Es gibt natürliche Zahlen, die keine Quadratzahl einer natürlichen Zahl sind."
|
||
|
|
>
|
||
|
|
> Um diese Aussage $A$ zu belegen, gilt es lediglich, ein geeignetes Beispiel zu finden.
|
||
|
|
>
|
||
|
|
> Aufzeigen kann man das bspw. anhand der Zahl $2$.
|
||
|
|
>
|
||
|
|
> $1^2 = 1$ ist kleiner als $2$ und $2^2 = 4$ ist grösser als $2$. $2$ ist also keine Quadratzahl einer natürlichen Zahl.
|
||
|
|
|
||
|
|
### Beweis durch Kontraposition
|
||
|
|
Es gilt zu beweisen, ob eine Aussage, welche eine Implikation in der Form $A \Rightarrow B$ (siehe [Implikation](#4-implikation)) ist, wahr oder falsch ist.
|
||
|
|
|
||
|
|
Dies kann erreicht werden, indem man, wie im Kapitel [Kontraposition](#kontraposition) beschrieben die Aussage von $A \Rightarrow B$ zu $\neg B \Rightarrow \neg A$ umformt.
|
||
|
|
|
||
|
|
> ***Beispiel in Worten:***
|
||
|
|
> - $A$: "Wenn es regnet ist die Wiese nass."
|
||
|
|
> - Beweisbare Kontraposition $B$: "Wenn die Wiese nicht nass ist, regnet es nicht."
|
||
|
|
|
||
|
|
> ***Beispiel:***
|
||
|
|
> - $A$: "Für jede natürliche Zahl $n$ gilt: $(n^2 + 1 = 1) \Rightarrow (n = 0)$
|
||
|
|
> - Kontraposition $B$: "Für jede natürliche Zahl $n$ gilt: $(n \not = 0) \Rightarrow (n^2 + 1 \not = 1)$
|
||
|
|
>
|
||
|
|
> Falls die Bedingung, dass $n \not = 0$ ist, gilt auch, dass $n^2 \not = 0$ ist.
|
||
|
|
> Somit ist also bewiesen, dass, im Falle, dass $n \not = 0$, auch $n^2 + 1 \not = 1$ zutrifft.
|
||
|
|
|
||
|
|
### Beweis einer Äquivalenz
|
||
|
|
Es ist eine Aussage der Form $A \Leftrightarrow B$ zu beweisen.
|
||
|
|
|
||
|
|
Erreicht werden kann das, indem man sowohl $A \Rightarrow B$ als auch $B \Rightarrow A$ beweist.
|
||
|
|
|
||
|
|
> ***Beispiel:***
|
||
|
|
> - $A$: "$(n\text{ ist gerade}) \Leftrightarrow (n^2\text{ ist gerade})$"
|
||
|
|
>
|
||
|
|
> Eine gerade Zahl kann jeweils bestimmt werden, indem man eine bestehende Zahl verdoppelt:
|
||
|
|
> $$n = 2 \cdot i$$
|
||
|
|
> $n$ ist also immer dann gerade, wenn es $2 \cdot i$ entspricht ($i$ ist hierbei eine beliebige, natürliche Zahl).
|
||
|
|
>
|
||
|
|
> Trifft dies zu, so entspricht $n^2$ folgendem: $(2 \cdot i) \cdot (2 \cdot i)$.
|
||
|
|
> Dies lässt sich, als Beweis, dass es durch $2$ teilbar ist, folgendermassen umformen:
|
||
|
|
> $$2 \cdot (i \cdot 2 \cdot i)$$
|
||
|
|
> Da $n^2$ immer dem Term $(2 \cdot i) \cdot (2 \cdot i)$ entspricht, ist diese Aussage nun in beide Richtungen bewiesen.
|
||
|
|
|
||
|
|
### Beispielübung
|
||
|
|
Jeder Geldbetrag von mindestens $4$ Cents lässt sich alleine mit $2$- und $5$-Centstücken bezahlen.
|
||
|
|
|
||
|
|
In algebraischer Form würde das in etwa so aussehen:
|
||
|
|
|
||
|
|
$$\forall x \in \left\{ \mathbb{N} | x \geq 4 \right\} x = 2a + 5b$$
|
||
|
|
|
||
|
|
An dieser Stelle steht $a$ für die Anzahl $2$-Centstücke und $b$ für die Anzahl $5$-Centstücke.
|
||
|
|
|
||
|
|
Dies kann mit Hilfe einer Fallunterscheidung (basierend darauf, ob der zu bezahlende Betrag gerade oder ungerade ist).
|
||
|
|
|
||
|
|
Eine natürliche Zahl kann nur entweder gerade oder ungerade sein. Aus diesem Grund müssen nur diese beiden Fälle behandelt werden.
|
||
|
|
|
||
|
|
#### Für gerade Zahlen
|
||
|
|
Gerade Zahlen können jeweils mit $2$-Centstücken bezahlt werden. Die Anzahl $2$-Centstücke ist hierbei jeweils der zu bezahlende Betrag geteilt durch $2$.
|
||
|
|
|
||
|
|
In algebraischer Form würde dies in etwa folgendermassen aussehen:
|
||
|
|
$$\forall x \in \left\{ \mathbb{N} | x \geq 4 | x \text{ ist gerade} \right\} = 2 \cdot \frac{x}{2}$$
|
||
|
|
|
||
|
|
#### Für ungerade Zahlen
|
||
|
|
Um ungerade Zahlen zu erreichen, muss ein Weg gefunden werden, zu einem bestehenden, geraden Betrag einen zusätzlichen Cent zu bezahlen.
|
||
|
|
|
||
|
|
Dies kann erreicht werden, indem man 2 $2$-Centstücke weniger als geplant und stattdessen ein zusätzliches $5$-Centstück auszahlt.
|
||
|
|
|
||
|
|
Algebraisch sieht das wiederum so aus:
|
||
|
|
$$\forall x \in \left\{ \mathbb{N} | x \geq 4 | x \text{ ist ungerade} \right\} = 2 \cdot \left(\frac{x}{2} - 2\right) + 5 \cdot 1$$
|
||
|
|
|
||
|
|
Damit ist nun die getätigte Aussage dieser Aufgabe bewiesen.
|