vollständige Induktion < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Für alle i [mm] \in \IN [/mm] sei p(i) eine Aussage. Zeigen Sie durch vollständige Induktion, dass für alle n [mm] \in \IN [/mm] die folgende Aussage eine Tautologie ist.
[mm] \neg (\forall(k=1 [/mm] bis n): p(k)) [mm] \gdw \exists(k=1 [/mm] bis n): [mm] (\negp(k)) [/mm] |
Das ist meine Übungsaufgabe zu morgen.
Mein Problem ist nicht der Beweis dieser Aussage, denn indem ich die linke Seite verneine, kann man zeigen das sie äquivalent der verneinten rechten Seite ist. (Das sollte als Beweis legitim sein(?))
Meine Frage ist, wie ich den Beweis mithilfe der vollständigen Induktion handhaben soll.
Von vorn herein erstmal der Induktionsanfang: Ich habe da nur die gegebene Aussage hingeschrieben.
Und beim Induktionsbeweis:
Wenn ich n mit "n+1" ersetze und weiß das für n die Aussage eine Tautologie ist, dann würde ja reichen zu zeigen, dass p(n+1) äquivalent p(n+1) ist...(?) Das erscheint mir irgendwie sehr wenig...
Also ich bin echt schon lange am grübeln. Wir hatten bis jetzt nur vollständige Induktion bei Summen. Das ist auch nicht sonderlich schwer. Aber hier würde mir eine Lösung sehr helfen.
Ich bedanke mich schon mal im Voraus.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:03 Do 09.10.2008 | | Autor: | pelzig |
> Für alle i [mm]\in \IN[/mm] sei p(i) eine Aussage. Zeigen Sie durch
> vollständige Induktion, dass für alle n [mm]\in \IN[/mm] die
> folgende Aussage eine Tautologie ist.
>
> [mm]\neg (\forall(k=1[/mm] bis n): p(k)) [mm]\gdw \exists(k=1[/mm] bis n): [mm](\negp(k))[/mm]
Du meinst wohl [mm]\neg (\forall k\le n: p(k))\gdw (\exists k\le n: \neg p(k))[/mm]
> Mein Problem ist nicht der Beweis dieser Aussage, denn
> indem ich die linke Seite verneine, kann man zeigen das sie
> äquivalent der verneinten rechten Seite ist. (Das sollte
> als Beweis legitim sein(?))
Ja.
> Meine Frage ist, wie ich den Beweis mithilfe der
> vollständigen Induktion handhaben soll.
> Von vorn herein erstmal der Induktionsanfang: Ich habe da
> nur die gegebene Aussage hingeschrieben.
Naja, also es ist sicherlich [mm] $\neg (\forall k\le [/mm] 1: [mm] p(k))\gdw \neg [/mm] p(1) [mm] \gdw (\exists k\le [/mm] 1: [mm] \neg [/mm] p(k))$. Aber gut, da müssen wir nicht weiter drüber reden.
> Und beim Induktionsbeweis:
Du meinst wohl den Induktionsschritt.
> Wenn ich n mit "n+1" ersetze und weiß das für n die
> Aussage eine Tautologie ist, dann würde ja reichen zu
> zeigen, dass p(n+1) äquivalent p(n+1) ist...(?) Das
> erscheint mir irgendwie sehr wenig...
Ich verstehe nicht ganz wie du das meinst. Also es ist ja [mm] $\neg (\forall k\le [/mm] n+1: [mm] p(k))\gdw\neg (\forall k\le [/mm] n: [mm] p(k))\vee \neg [/mm] p(n+1)$. Jetzt kannst du die Induktionsvoraussetzung anwenden und noch weiter umformen. Mehr ist es nicht.
> Also ich bin echt schon lange am grübeln. Wir hatten bis
> jetzt nur vollständige Induktion bei Summen. Das ist auch
> nicht sonderlich schwer. Aber hier würde mir eine Lösung
> sehr helfen.
Bei vollständiger Induktion geht es eigentlich darum, dass man eine Menge von Aussagen beweist, und diese Menge hat die Form [mm] $\{A(n):n\in\IN\}$, [/mm] wobei $A(n)$ eine Aussage ist, die von einer natürlichen Zahl abhängt. Wie $A(n)$ konkret aussieht, spielt für das Beweisprinzip keine Rolle.
Gruß, Robert
|
|
|
| |
|
edit: ~Wurde überflüssig~
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:34 Do 09.10.2008 | | Autor: | pelzig |
Ich habe doch im wesentlichen dieselbe Notation wie du verwendet, der einzige Unterschied ist doch, dass du schreibst [mm] $\forall [/mm] k=1...n$ und ich [mm] $\forall k\le [/mm] n$.
Das [mm] $\vee$ [/mm] bedeutet bei mir übrigens "oder" und [mm] $\wedge$ [/mm] wäre "und".
> Alternativ zu [mm]\forall[/mm] haben dir auch noch ein langgezogenes
> [mm]\wedge[/mm] eingeführt. Das mit dem "k=1 bis n" meine ich das
> unter dem Zeichen das k=1 steht und darüber das n.
Dann meinst du wahrscheinlich [mm] $\bigwedge_{k=1}^n [/mm] p(k)$. Das geht auch, gefällt mir persönlich sogar am Besten.
Ist deine Frage jetzt eigentlich beantwortet?
Gruß, Robert
|
|
|
| |
|
Ja, meine Frage ist zu größter Zufriedenheit beantwortet.
Ich danke dir echt. Hat mir sehr geholfen.
lg und danke nochma!
|
|
|
| |
|
Ja, die Frage ist echt gut beantwortet. War fast einleuchtender als in der Vorlesung. ^^
Danke vielmals und lg Kai
|
|
|
|
