Nachweis einfacher Eigenschaften über Begriffe, Position von Subtermen und Ersatz von Subtermen

Question

Ich studiere den Begriff des Umschreibens durch das Lesen des Buches Baader / Nipkow: "Term Rewriting und all das".

Ich möchte ein Lemma über Begriffe, Position von Subtermen und Austausch von Subtermen beweisen. Die Notation ist wie folgt:

$ S | _ {p} $ Bezeichnet den Subterm der $ s $ an der Position $ P $ .
$ s [t] _ {p} $ Bezeichnet den Begriff, der von $ S $ erhalten wird, indem Sie den Subtermin ersetzen An Position $ P $ von $ t $ .

Das Lemma, das ich beweisen möchte, ist:

lemma 3.1.4 let $ s, t, r $ Begriffe und $ p, q $ Seien Sie nach den positiven Ganzzahlen.

.

1. wenn $ pq \ in pos (s) $ , dann $ s | _ _ {pq}= (S | _ {p}) | _ {q} $ .

2. wenn $ p \ in pos (s) $ und $ q \ in pos (t) $ $ , dann

   2.1 $ (s [t] _ {p {p}) | _ {pq}= t | _ {q} $

   2.2 $ (s [t] _ {p}) [R] _ _ {pq}= s [t [r] _ {q}] _ {p} $ < / span>

3. wenn $ pq \ in pos (s) $ , dann

   3.1 $ (s [t] _ {pq {pq}) | _ {p}= (s | _ {p}) [t] _ {q} $

   3.2 $ (s [t] _ _ {pq}) [r] _ {p}= s [r] _ {p} $ . .

4. wenn $ p $ und $ q $ sind parallele Positionen in $ S $ (dh $ p || q $ ), dann

   4.1 $ (s [t] _ {p}) | _ {q}= s | _ {q} $

   4.2 $ (S [T] _ _ {P}) [R] _ {q}= (S [R] _ {q}) [T] _ {P} $

Das Buch bietet den Beweis für das erste Element:

Als Beispiel zeigen wir, durch Induktion in der Länge von $ p $ diese $ s | _ {pq }= (S | _ {P}) | _ {q} $ Hält für alle $ PQ \ in Pos (s) $ . .

für $ p=Epsilon $ , haben wir $ pq= q $ , und somit < Span-Klasse="Math-Container"> $ s | _ {pq}= S | _ {q} $ . Darüber hinaus impliziert $ P=Epsilon $ impliziert $ s | _ {p}= s $ , welches Zeigt $ S | _ {q}= (S | _ {p}) | _ {q} $ .

Nehmen Sie nun an, dass $ P= IP '$ . Denn $ IP'Q \ in Pos (s) $ , wissen wir, dass $ s $ von der ist Formular $ s= f (s_1, \ ldots, s_n) $ mit $ i \ leq n $ . Definition, $ S | _ {pq}= s | _ {ip'Q}= s_ {i} | _ {p'Q} $ und durch Induktion $ s_ {i} | _ {p'Q}= (s_ {i} | _ {p '}) | _ {q} $ . Wieder definitionsweise erhalten wir $ s_ {i} | _ {p '}= s | _ {ip'}= s | _ {p} $ , welche beendet den Nachweis des Induktionsschritts.

Ich möchte beweisen, dass auch die anderen Gegenstände ebenfalls wahr sind. Ich habe meinen Versuch als Antwort geschrieben, aber natürlich begrüße ich andere Lösungen oder Feedback. Vielen Dank im Voraus.

Answer 1

punkt 2. wenn $ p \ in pos (s) $ und $ q \ in pos ( t) $ :

2.1 $ (s [t] _ {p}) | _ {pq}= t | _ {q} $ . Kummer Wir beweisen durch Induktion in der Länge der $ P $ :

fall $ p=Epsilon $ :
$ (s [t] _ {\ Epsilon}) | _ _ \ Epsilon q}= t | _ {\ epsilon q}= t | _ {q} $ .

case $ p= IP '$ :
$ (S [T] _ {IP '}) | _ {IP'Q}= f (S_1, \ LDOTs, S_I [T] _ {p'}, \ ldots, s_n) | _ {ip'Q}= (s_ {i} [t] _ {p '}) | _ {p'Q} $ . Durch die Induktionshypothese, $ (s_ {i} [t] _ {p '}) | _ {p'Q}= t | _ {q} $ . < / p>

2.2 $ (s [t] _ {p}) [r] _ {pq}= s [t [r] _ {q}] _ _ p } $ .
Wir beweisen durch Induktion in der Länge der $ P $ :

fall $ p=Epsilon $ :
Beachten Sie, dass $ (S [T] _ {\ Epsilon}) [R] _ {\ Epsilon q}= T [R] _ {q} $ und auch das : $ S [T [R] _ {q}] _ {\ Epsilon}= T [R] _ {q} $ .

case $ p= IP '$ :
$ (S [T] _ _ {IP '}) [R] _ {IP'Q}= f (S_1, \ LDOTs, S_ {I} [t] _ {p' }, \ ldots, s_n) [r] _ {ip'Q}= f (s_1, \ ldots, (s_ {i} [t] _ _ {p '}) [r] _ {p'Q}, \ ldots , s_n) $ . Durch Induktionshypothese, $$ (S_ {I} [T] _ {p '}) [R] _ {P'Q}= S_I [T [R] _ {q}] _ _ _ _ '} $$ und daher $ f (s_1, \ ldots, (s_ {i} [t] _ _ {p '}) [r] _ {p'Q}, \ ldots, s_n)= f (s_1, \ ldots, s_i [t [r] _ {q}] _ {p '}, \ ldots, s_n)= s [t [r] _ {q}] _ _ {IP'} $ .

Artikel 3. Wenn $ PQ \ in Pos (s) $ , dann:

3.1 $ (s [t] _ {pq}) | _ {p}= (s | _ {p}) [t] _ {q} $ .
Wir beweisen durch Induktion in der Länge der $ P $ :

fall $ p=Epsilon $ :
Beachten Sie, dass $ (s [t] _ {\ Epsilon q}) | _ {\ epsilon}= s [t] _ {q} $ und auch diese $ (S | _ {\ Epsilon}) [t] _ {q}= s [t] _ {q} $ .

case $ p= IP '$ :
$ (s [t] _ {IP'Q}) | _ {IP '}= f (s_1, \ ldots, s_ {i} [t] _ {p'Q} , \ ldots, s_n) | _ {ip '}= (s_ {i} [t] _ {p'Q}) | _ {p'} $ . Durch Induktionshypothese:

$$ (s_ {i} [t] _ {p'Q}) | _ {p '}= (s_ {i} | _ _ {p'}) [ T] _ {q} $$

aber $ (S | _ {IP '}) [T] _ {q}= (S_ {I} | _ {p'}) [t] _ {q } $ und somit das Ergebnis gilt.

3.2 $ (s [t] _ {pq}) [r] _ {p}= s [r] _ {p} $ .
Wir beweisen durch Induktion in der Länge der $ P $ :

fall $ p=Epsilon $ :
$ (S [T] _ {\ Epsilon q}) [R] _ {\ Epsilon}= R= S [R] _ {\ \ epsilon} $ . < / p>

case $ p= IP '$ :
$ (s [t] _ {IP'Q}) [R] _ {IP '}= f (S_1, \ LDOTs, S_ {I} [t] _ {p' q}, \ ldots, s_n) [r] _ {ip'Q}= f (s_1, \ ldots, (s_ {i} [t] _ {p'Q}) [r] _ {p '}, \ ldots, s_n) $ . Durch Induktionshypothese:

$$ (s_ {i} [t] _ {p'Q}) [R] _ {p '}= s_ {i} [r] _ {p' } $$

und daher haben wir $ f (s_1, \ ldots, (s_ {i} [t] _ _ {p'Q}) [r] _ {p '}, \ ldots, s_n)= f (s_1, \ ldots, s_ {i} [r] _ {p '}, \ ldots, s_n)= s [r] _ {ip'} $ .

item 4. Wenn $ p $ und $ q $ parallel Positionen in < Span-Klasse="Math-Container"> $ s $ (dh $ P || q $ ), dann

4.1 $ (s [t] _ {p}) | _ {q}= s | _ {q} $ < Br> Wir beweisen durch Induktion in der Länge der $ P $ :

case $ p=Epsilon $ : Dieser Fall kann nicht passieren, da $ P $ und $ q $ Wären nicht parallele Positionen.

case $ p= IP '$ :
Wir beweisen das jetzt durch Induktion in der Länge der $ q $ .
Wenn $ q=Epsilon $ :

Dies kann nicht passieren, da $ p $ und $ q $ nicht parallele Positionen sein würde .

Wenn $ Q= JQ '$ :

Es gibt zwei Möglichkeiten, je nachdem, ob $ i= J $ oder nicht.
fall $ i= j $ :

stark>

$ (s [t] _ _ {IP '}) | _ {iQ'}= f (s_1, \ ldots, s_ {i} [t] _ {p ' }, \ ldots, s_ {n}) | _ {iQ '}= (s_ {i} [t] _ {p'}) | _ {q '} $ . Wir haben diese $ P '$ und $ q' $ sind parallele Positionen und somit durch Induktionshypothese: $$ (s_ {i} [t] _ {p '}) | _ {q'}= s_ {i} | _ {q '}. $$ Da wir auch $ s | _ {iQ '}= S_ {i} | _ {q'} $ das Ergebnis gilt.

case $ i \ neq j $ :

Nehmen wir an, ohne Verlust der Allgemeinheit, die $ i> J $ . Dann:
$$ (S [T] _ {IP '}) | _ {jq'}= f (s_1, \ ldots, s_ {j}, \ ldots, s_ {i} [ t] _ {p '}, \ ldots, s_ {n}) | _ {jq'}= s_ {j} | _ {q '}. $$ Da wir auch $ s | _ {jq '_ {q'} $ das Ergebnis gilt.

4.2 $ (s [t] _ {p}) [r] _ {q}= (s [r] _ {q}) [t] _ {p} $ :

case $ p=Epsilon $ : Dieser Fall kann nicht passieren, da $ P $ und $ q $ Wären nicht parallele Positionen.

case $ p= IP '$ :
Wir beweisen das jetzt durch Induktion in der Länge der $ q $ .
Wenn $ q=Epsilon $ :

Dies kann nicht passieren, da $ p $ und $ q $ nicht parallele Positionen sein würde .

Wenn $ Q= JQ '$ :

Es gibt zwei Möglichkeiten, je nachdem, ob $ i= J $ oder nicht.
case $ i= j $ :

$ (s [t] _ _ {IP '}) [R] _ {IQ'}= f (s_1, \ ldots, s_ {i} [t] _ _ P '}, \ ldots, s_n) [r] _ {iQ'}= f (s_1, \ ldots, (s_ {i} [t] _ {p '}) [r] _ {q'}, \ ldots, s_n) $ .
Wir haben diese $ P '$ und $ q' $ sind parallele Positionen und somit durch Induktionshypothese: $$ (S_ {I} [T] _ {p '}) [R] _ {Q'}= (S_ {I} [R] _ {Q '}) [ T] _ {p '} $$ und daher $$ F (S_1, \ LDOTs, (S_ {I} [T] _ _ {p '}) [R] _ {q'}, \ ldots, s_n)= f (s_1, \ ldots, (s_ {i} [r] _ {q '}) [t] _ _ {p'}, \ ldots, s_n)= f (s_1, \ ldots, s_ {i} [r] _ {q '}, \ ldots, s_n) [t] _ {IP'}= (S [R] _ {q}) [t] _ {p}. $$

case $ i \ neq j $ :

Nehmen wir an, ohne Verlust der Allgemeinheit, die $ i> J $ . Dann:
$$ (S [T] _ {IP '}) [R] _ {JQ'}= f (S_1, \ LDOTs, S_ {J}, \ ldots, s_ {i i } [t] _ {p '}, \ ldots, s_n) [r] _ {jq'}= f (s_1, \ ldots, s_ {j} [r] _ {q '}, \ ldots, s_ {i } [t] _ {p '}, \ ldots, s_n)= f (s_1, \ ldots, s_ {j} [r] _ {q'}, \ ldots, s_ {i}, \ ldots, s_n) [ t] _ {IP '}= (S [R] _ {JQ'}) [T] _ _ {IP '}. $$