Logik

up:: Mat1 MOC

Quelle:
20221028_TH_M1-Skript_v02-1.pdf

Aussage

Definition

Eine Aussage ist ein grammatikalischer Ausdruck, von dem es sinnvoll ist zu fragen, ob er wahr oder falsch ist. Eine Aussage kann wahr oder falsch sein, aber nicht beides zugleich oder irgendwas dazwischen.

„Der August hat 31 Tage“ ist eine Aussage.

Es gibt Aussagen, von denen wir nicht wissen ob sie wahr oder falsch sind:
„Es gibt unendlich viele Paare von Primzahlen, deren Abstand gleich 2 ist.“

Ausagen hängen vom Kontext ab.
$x>3$ ist keine Ausage.
$x=3,14345,x>3$ ist eine Ausage.

Aussagenform

Eine Aussageform ist ein Ausdruck in Variablen der zu einer Aussage wird wenn alle darin vorkommenden Variablen durch konkrete Objekte ersetzt werden. Diese Objekte müssen aus einer geeigneten Grundgesamtheit kommen.

Link to original

Link to original

Axiom

Definition

Ein Axiom ist eine Aussage, die für Wahr erklärt wird.

Im Aufbau der Mathematik nehmen Axiome das grundlegende Fundament ein.

z.B. (Axiom von der Geraden). Zu zwei beliebigen, voneinander verschiedenen Punkten gibt es genau eine Gerade, welche diese beiden Punkte enthält.

z.B. (Parallelenaxiom). Zu jeder Geraden, und jedem Punkt, welcher nicht auf dieser Geraden liegt, gibt es genau eine zu der Geraden parallele Gerade durch diesen Punkt.

Ein Satz (auch Lemma, Korollar, Theorem, Proposition) ist eine wahre Aussage.
Ein Satz wird üblicherweise aus anderen Sätzen oder aus Axiomen abgeleitet.

Axiom Beispiel 20221028_TH_M1-Skript_v02-6.pdf Seite 16

Ein Korollar ist etwas das man aus einem Satz mit Leichtigkeit gewinnt.

Link to original

Sprachen

Altagssprache nicht präzise genug. Daher formale Sprachen (Sufe 1)

Junktoren

Logisches Nicht

$$\begin{array}{cc}A& \neg A\\ W& F\\ F& W\end{array}$$Link to original

Logisches Und

$$\begin{array}{ccc}A& B& A\wedge B\\ W& W& W\\ W& F& F\\ F& W& F\\ F& F& F\end{array}$$Link to original

Logisches Oder

$$\begin{array}{ccc}A& B& A\vee B\\ W& W& W\\ W& F& W\\ F& W& W\\ F& F& F\end{array}$$Link to original

wenn dann

$$\begin{array}{ccc}A& B& A\to B\\ W& W& W\\ W& F& F\\ F& W& W\\ F& F& W\end{array}$$Link to original

genau dann wenn

Summary:

This table shows that A and B are equivalent if and only if they have the same truth value.

Full answer:

$$\begin{array}{ccc}A& B& A\leftrightarrow B\\ W& W& W\\ W& F& F\\ F& W& F\\ F& F& W\end{array}$$

Bei Beweisen

→ beide Richtungen müssen bewiesen werden

Link to original

exklusives oder

$$\begin{array}{ccc}A& B& A\text{xor}B\\ W& W& F\\ W& F& W\\ F& W& W\\ F& F& F\end{array}$$Link to original

Link to original

Äquivalenzen

∀ → für alle
∃ → es gibt
= → gleich
⇔ → logisch äquivalent

Negation von UND / Oder:
$\neg (A\wedge B)⟺\neg A\vee \neg B$
$\neg (A\vee B)⟺\neg A\wedge \neg B$

Assoziativgesetz:
$(A\wedge B)\wedge C⟺A\wedge (B\wedge C)$
$(A\vee B)\vee C⟺A\vee (B\vee C)$

Distributivgesetz:
$(A\wedge B)\vee C⟺(A\vee B)\wedge (B\vee C)$
$(A\vee B)\wedge C⟺(A\wedge B)\vee (B\wedge C)$

Kommutativgesetz:
$A\wedge B⟺B\wedge A$
$A\vee B⟺B\vee A$

Kontrapositionsregel:
$(A\to B)⟺(\neg A\to \neg B)$

$(A\leftrightarrow B)⟺(A\to B)\wedge (B\to A)$

Link to original

Beweisen

⇒ Durch zerlegen der Ausdrücke in einzelne Terme.

Tautologie

Ein logischer Term heißt Tautologie, wenn er stets wahr ist, unabhängig davon welche Aussagen eingesetzt werden.
Ein logischer Term heißt Kontradiktion, wenn er stets falsch ist, egal welche Aussagen eingesetzt werden.

Link to original

Logik Normalform

$Z=$ logischer Term $X_1,...,X_n$

Disjunktiver Normalform (DNF)
$Z=Z_1\vee \cdot \cdot \cdot \vee Z_k$
$Z_i=Y_1\wedge \cdot \cdot \cdot \wedge Y_n$ für alle $i=1,...,k$

Konjunktiver Normalform (KNF)
$Z=Z_1\wedge \cdot \cdot \cdot \wedge Z_k$
$Z_i=Y_1\vee \cdot \cdot \cdot \vee Y_n$ für alle $i=1,...,k$

z.B.
$Z=(A\wedge B\wedge C)\vee (\neg A\wedge B\wedge \neg C)$
DNF: $Z^{{}^{\prime }}=(A\vee B\vee C)\wedge (\neg A\vee \neg B\vee \neg C)\wedge (\neg A\vee B\vee C)$

Normalform Herleiten

Link to original

Logisches Schließen

Aus alten Ausagen neue neue erhalten.

Zwei grundsätliche Probleme:

• Sind die Prämissen wirklich wahr?
  • → man postuliert das bestimmte Präsmissen wahr sind (Axiome)
• Wie vermeidet man falsche Schlussfolgerungen?
  • → man löst Problme nach einem System von von bestimmten Regelen

Eine Belegung eines logischen Terms ist eine Zuweisung von Wahrheitswerten zu jeder Aussagenvariable des Terms.

Eine Interpretation eines logischen Termes ist eine Zuordnung von konkreten Aussagen zu jeder Aussagenvariable des Terms. Eine Interpretation erfüllt einen logischen Term, wenn der Term bei der Interpreation wahr wird.

⇒ Jede Interpretation liefert also eine Belegung des logischen Terms.

Notation

$\mathcal{K}$ bezeichnet eine Menge von logischen Termen.
$\{Q\}$ bezeichnet die Menge die nur $Q$ enthält.
$\{P,Q\}$ bezeichnet die Menge die nur $P$ und $Q$ enthält.
$K\cup \{Q\}$ bezeichnet die Menge die neben allen Termen aus $K$ auch $Q$ enthält.

Tertium non datur

(TND)

Ohne jegliche Voraussetzung gilt:

$$\begin{array}{r}P\vee \neg P\end{array}$$Link to original

Voraussetzungsregel

(Vor)

$$\begin{array}{ll}K\cup \{P\}& P\\ K& P\end{array}$$Link to original

Antezedenregel

(Ant)

$$\begin{array}{ll}K& P\\ K\cup \{Q\}& P\end{array}$$Link to original

V-Einführung im Sukzedenz

(V Suk)

\begin{alignat}{1} K & \>\> & P \\ \hline K && P \land Q \end{alignat} \begin{alignat}{1} K & \>\> & P \\ \hline K && Q \land P \end{alignat} Link to original

Fallunterscheidungsregel

(FU)

\begin{alignat}{1} K & \cup\{\neg Q\} \>\> & P \\ K & \cup\{Q\} & P \\ \hline K & &P \end{alignat} Link to original

Wiederspruchsregel

(Wid)

\begin{alignat}{1} K & \cup\{\neg P\} \>\> & Q \\ K & \cup\{\neg P\} & \neg Q \\ \hline K && P \end{alignat}

Modifizierte Wiederspruchsrege

\begin{alignat}{1} K & \>\> & Q \\ K && \neg Q \\ \hline K && P \end{alignat} Link to original

V-Einführung im Antezedenz

(V Ant)

\begin{alignat}{1} K & \cup\{ P \} & R \\ K & \cup\{ Q \} & R \\ \hline K & \cup\{ P \vee Q \} \>\> & R \end{alignat} Link to original

Kettenschlussregel

(KS)

\begin{alignat}{1} K & & P \\ K & \cup \{ P \} \> \ & Q \\ \hline K & & Q \end{alignat} Link to original

Knotrapositionsregel

(KP)

\begin{alignat}{1} K & \cup \{ \neg Q \} \>\> & \neg P \\ \hline K & \cup \{ P \} & Q \end{alignat} Link to original

Es gibt viele weitere Regeln

Wie z.B. :

\begin{alignat}{1} K & \>\> & P \vee Q \\ K & & \neg P \\ \hline K & & Q \end{alignat} Link to original

Beispiel

Eine natürliche Zahl $n$ heißt gerade, falls es eine natürliche Zahl $k$ gibt, so das $n=2\cdot k$ gilt. Andernfalls heißt die Zahl $n$ ungerade.

Ist n

Direckter Beweis

Eine natürliche Zahl n ist gerade genau dann ungerade, wenn es