Induktion Basics Logik Formelbau

Question

Eine Zeichenreihe R heißt ein Anfangsstück einer Zeichenreihe R', wenn RS = R' für
eine gewisse Zeichenreihe S. Dabei bezeichnet RS das Ergebnis der Verkettung
(d. h. des ,,Hintereinanderschalten") der beiden Zeichenreihen R und S. Die Zeichenreihe
R' entsteht also aus R durch Hinzufügen weiterer Symbole von rechts. Zum Beispiel
ist ) p ~ Anfangsstück von ) p -> q (∧ r). Man zeige, sind P und Q verschiedene
Anfangsstücke einer Zeichenreihe R, so ist P Anfangsstück von Q oder Q Anfangsstück
von P.
Hinweis. Vollständige Induktion über die Lange L (R) der Zeichenreihe R. Ist L (R) = 1,
ist nichts zu beweisen. Sei L (R) = n + 1 also R = R' a. Man beachte, dass die Anfangsstücke
von R außer R genau die Anfangsstücke von R' sind.

Problem:  Ich verstehe das Problem so, dass ich ein Anfangsstück hab und eine Länge ist meine länge z.B 20 und mein Anfangsstück 5 so ist L(S)=15, nun aber verstehe ich nicht warum, oder will man nur darauf hinaus dass es ein kleinstes Anfangsstück gibt?

Comments

diese definition hilft vielleicht. :(

Answer 1

Es seien P={p1,p2,...,pn} und Q={q1,q2,...,qn} Anfangsstücke einer Zeichenreihe R={r1,r2,...,rk}.

Ist L(R)=1 ist L (P)=0 oder L (Q)=0, da es jedoch keine leeren Zeichenketten gibt ist das ein Widerspruch. Somit L (R)>1, bzw.

L (R)=1+n.

Da P Anfangsstück von R ist, stimmen die ersten m Zeichen von P und R überein, d.h. p1=r1, p2=r2,... pm=rm.

Q ist jedoch ebenfalls ein Anfangsstück von R und kann als Zeichenkette per Definition nicht leer sein.

Ist Q ein Anfangsstück von R, so müssen die ersten l Zeichen von Q und R überein stimmen, d.h. q1=r1, q2=r2,...,ql=rl.

Setzt man die Terme für r1,r2,... gleich, so erhält man p1=q1, p2=q2,.... Da P und Q jedoch verschiedene Anfangsstücke von R sein sollen, stellt dies einen Widerspruch dar, solange nicht Teil von P als Anfang von Q (L (Q)>L (P)) oder Teil von Q als Anfang von P (L (P)>L (Q)) vorhanden ist.

-> Logische Schlussfolgerung: Entweder ist P Anfangsstück von Q oder Q ist Anfangsstück von P.

Gebe zwar keine Garantie auf Richtigkeit, aber ich hoffe ich konnte dir mit dieser Aussage behilflich sein.