Beweis mit Kontraposition

25.11.2013, 14:26

decsis

Beweis mit Kontraposition

Hallo zusammen

Ich soll folgenden Satz mit der Prädikatenlogik beschreiben und mit der Kontraposition beweisen:
"Ist n eine natürliche Zahl und $\begin{eqnarray*} n^2 \end{eqnarray*}$ durch 3 teilbar, so ist auch n durch 3 teilbar."

Mein Versuch:

$\begin{eqnarray*} \forall n \in \mathbb{N} (n^2 \mbox{ mod } 3 = 0 \to n \mbox{ mod } 3 = 0) \end{eqnarray*}$

Beweis mit Kontraposition:

Behauptung:
$\begin{eqnarray*} \forall n \in \mathbb{N} (n \mbox{ mod } 3 \neq 0 \to n^2 \mbox{ mod } 3 \neq 0) \end{eqnarray*}$

Wie komme ich nun weiter? Da ich einfach nicht vorwärts kam, wollte ich den ersten Schritt der Lösung entnehmen. Dieser lautet

$\begin{eqnarray*} n \mbox{ mod } 3 \neq 0 \to ((n=3x + 1 \mbox{ xor } n=3y + 2) \land x,y \in \mathbb{N} ) \end{eqnarray*}$

Darunter verstehe ich nun lediglich, dass die Zahl, welche durch 3 teilbar ist, entweder gerade oder ungerade ist. Aber wie komme ich jetzt weiter?

25.11.2013, 14:59

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis mit Kontraposition

Zitat:

Original von decsis
Beweis mit Kontraposition:

Behauptung:
$\begin{eqnarray*} \forall n \in \mathbb{N} (n \mbox{ mod } 3 \neq 0 \to n^2 \mbox{ mod } 3 \neq 0) \end{eqnarray*}$

Das ist leider nicht das Gegenteil der gemachten Behauptung. Da steht ja nun, daß für alle n, die nicht durch 3 teilbar sind, auch n² nicht durch 3 teilbar ist. Das ist - wie gesagt - nicht das Gegenteil der zu beweisenden Aussage.

EDIT: war Unfug. Man braucht nicht das Gegenteil der Aussage, sondern nutzt $\begin{eqnarray*} A \Rightarrow B \Leftrightarrow \text{nicht } B \Rightarrow \text{nicht } A \end{eqnarray*}$

25.11.2013, 15:21

decsis

Auf diesen Beitrag antworten »

RE: Beweis mit Kontraposition

Zitat:

Original von klarsoweit

Zitat:

Original von decsis
Beweis mit Kontraposition:

Behauptung:
$\begin{eqnarray*} \forall n \in \mathbb{N} (n \mbox{ mod } 3 \neq 0 \to n^2 \mbox{ mod } 3 \neq 0) \end{eqnarray*}$

Also so wie ich das gemacht habe, steht es auch in der Lösung. Nur ohne " $\begin{eqnarray*} \forall n \in \mathbb{N} \end{eqnarray*}$ , meintest du das?

Ansonsten ist doch die Kontraposition einer Aussage, wenn beide Teilaussagen negiert und umgedreht werden. Was ist daran falsch?

25.11.2013, 15:29

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis mit Kontraposition
Sorry, ich hatte da was verwechselt. Also ignoriere, was ich gesagt hatte. Hammer

Zitat:

Original von decsis
Wie komme ich nun weiter? Da ich einfach nicht vorwärts kam, wollte ich den ersten Schritt der Lösung entnehmen. Dieser lautet

$\begin{eqnarray*} n \mbox{ mod } 3 \neq 0 \to ((n=3x + 1 \mbox{ xor } n=3y + 2) \land x,y \in \mathbb{N} ) \end{eqnarray*}$

Darunter verstehe ich nun lediglich, dass die Zahl, welche durch 3 teilbar ist, entweder gerade oder ungerade ist. Aber wie komme ich jetzt weiter?

Darunter ist eher zu verstehen, daß eine Zahl n, die nicht durch 3 teilbar die Darstellung n=3x + 1 oder n=3y + 2 haben muß, also den Rest 1 oder 2 hat. Jetzt quadriere mal diese Zahl.

25.11.2013, 16:04

decsis

Auf diesen Beitrag antworten »

RE: Beweis mit Kontraposition

Zitat:

Original von klarsoweit
Darunter verstehe ich nun lediglich, dass die Zahl, welche durch 3 teilbar ist, entweder gerade oder ungerade ist. Aber wie komme ich jetzt weiter?

Darunter ist eher zu verstehen, daß eine Zahl n, dir nicht durch 3 teilbar dir Darstellung n=3x + 1 oder n=3y + 2 haben muß, also den Rest 1 oder 2 hat. Jetzt quadriere mal diese Zahl.[/quote]

Ok, dann erhalte ich
$\begin{eqnarray*} n^2 = 9x^2 + 6x + 1 \mbox{ xor } n^2 = 9y^2 + 12x + 4 \land x,y \in \mathbb{N} \end{eqnarray*}$

$\begin{eqnarray*} n^2 = (3x + 1)^2 \mbox{ xor } n^2 = (3y+2)^2 \land x,y \in \mathbb{N} \end{eqnarray*}$

Und schon wieder bin ich am Anschlag verwirrt

26.11.2013, 08:40

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis mit Kontraposition

Zitat:

Original von decsis
Ok, dann erhalte ich
$\begin{eqnarray*} n^2 = 9x^2 + 6x + 1 \mbox{ xor } n^2 = 9y^2 + 12x + 4 \land x,y \in \mathbb{N} \end{eqnarray*}$

Damit kommen wir doch schon weiter. Überlege, ob n² durch 3 teilbar sein kann, indem du die einzelnen Summanden betrachtest.

26.11.2013, 10:01

decsis

Auf diesen Beitrag antworten »

RE: Beweis mit Kontraposition

Zitat:

Original von klarsoweit

Zitat:

Original von decsis
Ok, dann erhalte ich
$\begin{eqnarray*} n^2 = 9x^2 + 6x + 1 \mbox{ xor } n^2 = 9y^2 + 12x + 4 \land x,y \in \mathbb{N} \end{eqnarray*}$

Damit kommen wir doch schon weiter. Überlege, ob n² durch 3 teilbar sein kann, indem du die einzelnen Summanden betrachtest.

Da ich keine 3 ausklammern kann wohl eher nicht. verwirrt

PS: Nur so aus Interesse: Suchen wir nun nicht einen Widerspruch? Also ein Beweis mit Kontraposition ist doch eine logischer Schluss "Reductio Ad Absurdum", oder?

26.11.2013, 10:35

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis mit Kontraposition

Zitat:

Original von decsis
Da ich keine 3 ausklammern kann wohl eher nicht. verwirrt

Na ja, halb richtig. Bei 7x + 2x + 5 + 1 kann man im ersten Moment auch nicht eine 3 ausklammern. Besser ist folgendes Argument: alle Summanden außer dem letzten sind durch 3 teilbar. Man kann also das n² in die Form n² = 3m + 1 mit einem ganzzahligen m bringen.

Zitat:

Original von decsis
PS: Nur so aus Interesse: Suchen wir nun nicht einen Widerspruch? Also ein Beweis mit Kontraposition ist doch eine logischer Schluss "Reductio Ad Absurdum", oder?

Es gibt im Grunde 2 artverwandete Ansätze:

1. man verwendet die Äquivalenz $\begin{eqnarray*} A \Rightarrow B \Leftrightarrow \text{nicht } B \Rightarrow \text{nicht } A \end{eqnarray*}$
Wenn man also die Implikation rechts vom Doppelpfeil bewiesen hat, dann hat man auch die Implikation links vom Doppelpfeil bewiesen.

2. wir setzen voraus, daß n² durch 3 teilbar ist und nehmen das Gegenteil der Behauptung an, daß also n nicht durch 3 teilbar ist. Das führt man zu einem Widerspruch zur Voraussetzung.

Neue Frage »

Antworten »

Beweis mit Kontraposition

Verwandte Themen