Struktureller Induktionsbeweis < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Zeigen Sie durch Induktion, dass 2^|t| eine obere Schranke für die größte Zahl ist, die durch einen variablenfreien Term t über N dargestellt werden kann (|t| bezeichnet die Länge von t).
Hinweis: Machen Sie den Induktionsanfang und die Induktionsannahme explizit. |
Ich weiß wie ein Struktureller Induktionsbeweis prinzipell funktioniert. Nur hier kann ich keinen Induktionsanfang finden. Soweit ich es verstehe geht es hier um die länge desTerms also 2 würde bei unserer defintion als +(1,1) dargestellt das heißt der term is 6 zeichen lang also is |t| = 6 somit ist 6 < [mm] 2^6.. [/mm] was in dem fall zu einer wahren aussage führt... weiter weiß ich nicht...
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:12 Do 05.05.2016 | | Autor: | hippias |
![[willkommenvh]](/images/smileys/willkommenvh.png "[willkommenvh]")
> Zeigen Sie durch Induktion, dass 2^|t| eine obere Schranke
> für die größte Zahl ist, die durch einen variablenfreien
> Term t über N dargestellt werden kann (|t| bezeichnet die
> Länge von t).
> Hinweis: Machen Sie den Induktionsanfang und die
> Induktionsannahme explizit.
>
> Ich weiß wie ein Struktureller Induktionsbeweis prinzipell
> funktioniert. Nur hier kann ich keinen Induktionsanfang
> finden.
Das verstehe ich nicht ganz, denn Deine nachfolgenden Überlegungen stellen doch einen Induktionsanfang dar. Worin besteht also wirklich das Problem?
> Soweit ich es verstehe geht es hier um die länge
> desTerms also 2 würde bei unserer defintion als +(1,1)
> dargestellt das heißt der term is 6 zeichen lang also is
> |t| = 6 somit ist 6 < [mm]2^6..[/mm] was in dem fall zu einer wahren
> aussage führt... weiter weiß ich nicht...
Achtung: es wird nicht [mm] $|t|<2^{|t|}$ [/mm] behauptet.
Mein Tip: Induktion nach der Länge $|t|$ des Terms $t$.
1. Induktionsanfang: Man muss zeigen, dass wenn $t$ ein (variablenfreier) Term der Länge $1$ ist - denn einen solchen gibt es - dass dann die dargestellte Zahl [mm] $<2^{1}= [/mm] 2$ ist.
Versuche dies!
2. Induktionsvoraussetzung: Sei $t$ ein variablenfreier Term der Länge $n:= |t|>1$. Man nehme an, dass die Behauptung für jeden variablefreien Term $s$ mit $|s|<n$ gültig ist: d.h. die durch $s$ dargestellte Zahl ist [mm] $<2^{|s|}$.
[/mm]
3. Induktionsschritt: Zeige, dass auch die durch $t$ dargestellte Zahl $<2^ {n}$ ist.
Dazu überlege Dir, dass es Terme $s,r$ geben muss, sodass $t=+(s,r)$ gilt. Wende auf $s,r$ die Induktionsvoraussetzung an und begründe auch, weshalb dies überhaupt zulässig ist.
|
|
|
|
