Beweisen mit struktureller Induktion

Aufrufe: 714     Aktiv: 20.11.2020 um 22:17
0

Wir definieren rekursiv die folgende Menge T der arithmetischen Terme:

Basiselemente: Fur alle ¨ i ∈ N ist das Zahlsymbol i ein arithmetischer Term, d. h., i ∈ T .

Rekursionsregeln: Wenn T1 und T2 arithmetische Terme aus T sind, dann sind

(T1 + T2), (T1 − T2) und (T1 · T2) auch arithmetische Terme in T .

Beweisen Sie mit struktureller Induktion:

In allen arithmetischen Termen aus T ist die Anzahl der Zahlsymbole um eins gr¨oßer als die Gesamtanzahl der Operationszeichen +, − und ·.

Dabei z¨ahlen wir fur jedes Symbol ¨ i ∈ N alle seine Vorkommen im gegebenen Term.

Zum Beipiel hat der Beispielterm T = ((1 + 2) − (2 · (3 − 4))) funf Zahlsymbole und vier Operationszeichen. 

Diese Frage melden
gefragt

Punkte: 10

 
Kommentar schreiben
1 Antwort
0

Für einen arithmetischen Term \( T_1 \) aus \(T\) definieren wir die Anzahl der Zahlsymbole durch \( z(T_1) \) und die Anzahl der Operationszeichen durch \( o(T_1) \).

Gezeigt werden soll nun \( z(T_1)=o(T_1)+1 \) für alle \( T_1 \) aus \( T \).

Induktionsanfang: Falls \( T_1 = i \) ist für ein Basiselemente \( i \in \mathbb{N} \), dann gilt

\( z(T_1) \) \( = z(i) \) \( =1 \) \( =0+1 \) \( =o(i)+1 \) \( = o(T_1)+1 \).

Induktionsschritt: Falls \( T_1 = T_2 * T_3 \) ist für \( * \in \{ + , - , \cdot \} \) und Terme \( T_2 \) und \( T_3 \) aus \( T \) mit \( z(T_2)=o(T_2)+1\) und \( z(T_3)=o(T_3)+1 \), dann gilt

\( z(T_1) = z(T_2 * T_3) = z(T_2)+z(T_3) = o(T_2)+1+o(T_3)+1 = o(T_2 * T_3) + 1 = o(T_1) + 1 \)

Diese Antwort melden
geantwortet

Student, Punkte: 7.02K

 
Wohin verschwindet die zweite 1 kurz vor dem Ende des Beweises?   ─   moinmeister 20.11.2020 um 20:10
Der Term \( T_2 * T_3 \) setzt sich ja zusammen aus den Termen \( T_2 \) und \( T_3 \) und aus dem Operationszeichen \( * \). Deshalb ist \( o(T_2 * T_3) = o(T_2) + 1 + o(T_3) \) (die Eins kommt von dem Operationszeichen).   ─   42 20.11.2020 um 22:16

Kommentar schreiben