Prova de propriedades simples sobre os termos, posição de subterremo e substituição de subterrrias
https://cs.stackexchange.com/questions/129839
-
29-09-2020 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu estou estudando Reescrevendo lendo Leitura de Livro de Baader / Nipkow: "Reescrevendo a termo e tudo o que".
Eu quero provar um lema sobre os termos, posição de subterremo e substituição de subterrrias. A notação é a seguinte:
.$ s | _ {p} $ denota o subtermo de $ s $ na posição $ P $ .
$ s [t] _ {p} $ denota o termo obtidos a partir de $ s $ , substituindo o subtermo na posição $ p $ por $ t $ .
O lema que quero provar é:
.Lema 3.1.4 Let $ s, t, r $ se termos e $ p, Q $ Seja cordas sobre os inteiros positivos.
.
Se $ pq \ em Pos (s) $ , em seguida, $ s | _ {pq}= (s | _ {p}) | _ {q} $ .
Se $ p \ em POS (s) $ e $ q \ in Pos (t) $ , então
2,1 $ (s [t] _ {p}) | _ {pq}= t | _ {q} $
2,2 $ (s [t] _ {p}) [r] _ {pq}= s [t [r] _ {q}] _ {p} $ < / span>
se $ pq \ em pos (s) $ , então
3,1 $ (s [t] _ {pq}) | _ {p}= (s | _ {p}) [t] _ {q} $
3,2 $ (s [t] _ {pq}) [r] _ {p}= s [r] _ {p} $ .
Se $ p $ e $ q $ são posições paralelas em $ s $ (isto é, $ p || Q $ ), em seguida,
4,1 $ (s [t] _ {p}) | _ {q}= s | _ {q} $
4,2 $ (s [t] _ {p}) [R] _ {q}= (s [R] _ {q}) [t] _ {p} $
O livro fornece provas para o primeiro item:
.Como um exemplo, vamos mostrar, por indução no comprimento de $ p $ que $ s | _ {pq }= (s | _ {p}) | _ {q} $ vale para todo $ pq \ em Pos (s) $
Para $ p=epsilon $ , temos $ pq= q $ , e assim < span class="contêiner matemática"> $ s | _ {pq}= s | _ {q} $ . Além disso, $ p=epsilon $ implica $ s | _ {p}= S $ , que mostra $ s | _ {q}= (s | _ {p}) | _ {Q} $ .
.Agora assuma que $ p= ip '$ . Porque $ ip'q \ em POS (s) $ , sabemos que $ s $ é do formulário $ s= f (s_1, \ ldots, s_n) $ com $ i \ leq n $ . Por definição, $ s | _ {pq}= s | _ {ip'q}= s_ {i} | _ {p'Q} $ , e por indução $ s_ {i} | _ {p'q}= (s_ {i} | _ {p '}) | _ {Q} $ . Novamente, por definição, obtemos $ s_ {i} | _ {p '}= s | _ {ip'}= s | _ {p} $ , que termina a prova do passo de indução.
Eu quero provar que os outros itens também são verdadeiros. Eu escrevi minha tentativa como uma resposta, mas, claro, recebo outras soluções ou feedback. Agradecemos antecipadamente.
Solução
Item 2. Se $ p \ em pos (s) $ e $ \ em pos ( t) $ :
2.1 $ (s [t] _ {p}) | _ {pq}= t | _ {q} $ .
Nós provamos por indução no comprimento da $ P $ :
caso $ p=epsilon $ :
$ (s [t] _ {\ epsilon}) | _ {\ epsilon q}= t | _ {\ epsilon q}= t | _ {q} $ .
caso $ 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} $ . Por hipótese de indução, $ (s_ {i} [t] _ {p '}) | _ {p'q}= t |. _ {Q} $ < / p >.
2.2 $ (s [t] _ {p}) [R] _ {pq}= s [t [r] _ {q}] _ {q}] _ {p } $ .
Nós provamos por indução no comprimento da $ P $ :
caso $ p=epsilon $ :
Observe que $ (s [t] _ {\ epsilon}) [r] _ {\ epsilon q}= t [r] _ {q} $ e também que : $ s [t [R] _ {q}] _ {\ epsilon}= t [r] _ {q} $ .
caso $ 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) $ . Por hipótese de indução,
$$ (s_ {i} [t] _ {p '}) [r] _ {p'q}= s_i [t [r] _ {q}] _ {p '} $$
e, portanto, $ 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'} $ .
item 3. Se $ pq \ em pos (s) $ , então:
3.1 $ (s [t] _ {pq}) | _ {p}= (s | _ {p}) [T] _ {p} $ .
Nós provamos por indução no comprimento da $ P $ :
caso $ p=epsilon $ :
aviso de que $ (s [t] _ {\ epsilon q}) | _ {\ epsilon}= s [t] _ {q} $ e também que $ (s | _ {\ epsilon}) [t] _ {q}= s [t] _ {q} $ .
caso $ 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'} $ . Por hipótese de indução:
$$ (s_ {i} [t] _ {p'q}) | _ {p '}= (s_ {i} | _ {p'}) [ t] _ {q} $$
mas $ (s | _ {ip '}) [t] _ {q}= (s_ {i} | _ {p'}) [T] _ {p '}) } $ e, portanto, o resultado detém.
3.2 $ (s [t] _ {pq}) [R] _ {p}= s [r] _ {p} $ .
Nós provamos por indução no comprimento da $ P $ :
caso $ p=epsilon $ :
$ (s [t] _ {\ epsilon q}) [r] _ {\ epsilon}= r= s [r] _ {\ epsilon} $ . < / p >.
caso $ 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) $ . Por hipótese de indução:
$$ (S_ {I} [T] _ {p'Q}) [R] _ {p '}= s_ {i} [r] _ {p' } $$
e, portanto, temos $ 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. Se $ P $ e $ q $ são posições paralelas em < span class="recipiente de matemática"> $ S $ (ou seja, $ p || q $ ), então
4.1 $ (s [t] _ {p}) | _ {q}= s | _ {} $ < BR> Nós provamos por indução no comprimento da $ P $ :
caso $ p=epsilon $ : Este caso não pode acontecer, como $ P $ e $ Q $ não seria posições paralelas.
caso $ p= ip '$ :
Agora provamos isso por indução no comprimento da $ Q $ .
Se $ Q=epsilon $ :
.Isso não pode acontecer, como $ P $ e $ Q $ não seria posições paralelas .
Se $ q= JQ '$ :
.forte>Existem duas possibilidades, de acordo com se $ i= j $ ou não.
caso $ i= j $ :
.$ (s [t] _ {ip '}) | _ {q'}= f (s_1, \ ldots, s_ {i} [t] _ {p ' }, \ lDOTs, s_ {n}) | _ {q '}= (s_ {i} [T] _ {p'}) | _ {} {q '} $ . Temos que $ p '$ $ e $ Q' $ são posições paralelas e, portanto, por hipótese de indução: $$ (S_ {I} [T] _ {p '}) | _ {q'}= s_ {i} | _ {q '}. $$ <}. Como também temos $ s | _ _ {q '}= s_ {i} | _ {q'} $ o resultado é válido.
caso $ i \ neq j $ :
.Vamos supor sem perda de generalidade que $ i> j $ . Então:
. $$ (s [T] _ {ip '}) | _ {JQ'}= f (s_1, \ ldots, s_ {j}, \ ldots, s_ {i} [ t] _ {p '}, \ ldots, s_ {n}) | _ {JQ'}= s_ {j} | _ {q '}. $$ Como também temos $ s | _ {JQ '}= s_ {j} | _ {q'} $ O resultado é válido.
4.2 $ (s [t] _ {p}) [r] _ {q}= (s [r] _ {q}) [T] _ {p} $ :
caso $ p=epsilon $ : Este caso não pode acontecer, como $ P $ e $ Q $ não seria posições paralelas.
caso $ p= ip '$ :
Agora provamos isso por indução no comprimento da $ Q $ .
Se $ Q=epsilon $ :
.Isso não pode acontecer, como $ P $ e $ Q $ não seria posições paralelas .
Se $ q= JQ '$ :
.Existem duas possibilidades, de acordo com se $ i= j $ ou não.
caso $ i= j $ :.$ (s [t] _ {ip '}) [R] _ {q'}= f (s_1, \ ldots, s_ {i} [t] _ { p '}, \ ldots, s_n) [r] _ {q'}= f (s_1, \ ldots (s_ {i} [t] _ {p '}) [r] _ {q'}, \ ldots, s_n) $ .
Temos que $ p '$ $ e $ Q' $ são posições paralelas e, portanto, por hipótese de indução: $$ (S_ {I} [T] _ {p '}) [r] _ {q'}= (s_ {i} [r] _ {q '}) [}) [ t] _ {p '} $$ e, portanto, $$ 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}. $$caso $ i \ neq j $ :
.Vamos supor sem perda de generalidade que $ i> j $ . Então:
. $$ (s [t] _ {ip '}) [R] _ {jq'}= f (s_1, \ ldots, s_ {j}, \ ldots, s_ {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 '}. $$
