Fölérendelt lap:11.11. KövetkezményAsszociatív és kommutatív művelet tetszőleges sorrendje és zárójelezése

Bizonyítás

Először az átzárójelezhetőséget fogjuk igazolni. Nevezzük a $*$ műveletet "szorzásnak", és alkalmazzunk a "tényezők" számára – azaz $n$ -re – vonatkozó teljes indukciót. Indukciós feltételként tegyük fel, hogy az állítás igaz bármely legfeljebb $n-1$ tényezős szorzatra, vagyis hogy ezekre az átzárójelezés akárhogyan elvégezhető. Azt kell megmutatnunk, hogy ekkor egy tetszőleges $n$ tényezős szorzatot is akárhogyan tudunk zárójelezni. Legyen például $P$ egy ilyen tetszőlegesen zárójelezett $n$ tényezős szorzat. Ekkor $P$ a zárójelezése alapján legutolsóként elvégzendő szorzás művelete mentén két részre bontható:

P = L * R

Itt $L$ és $R$ egy-egy olyan kifejezés, amelyben a tényezők száma legfeljebb $n-1$ . Az indukciós feltétel miatt tehát őket akárhogyan zárójelezhetjük, ezért az általánosság megsértése nélkül feltételezhetjük, hogy ezek a zárójelezések balra vannak rendezve, azaz valamilyen $1 \leq k < n$ esetén:

P = \underbrace{( \dots ((a_1 * a_2) * a_3) * \dots ) * a_k}_{=L} * \underbrace{( \dots ((a_{k+1} * a_{k+2}) * a_{k+3}) * \dots ) * a_n}_{=R}

Ám ekkor a $*$ művelet asszociativitását $k$ -szor alkalmazva a $P$ kifejezést át tudjuk zárójelezni úgy, hogy az szintén egy balra rendezett zárójelezés legyen, azaz:

P = (\dots ((L * a_{k+1}) * a_{k+2}) * \dots ) * a_n

Az átzárójelezés technikai részletei

Jelöljük $R_i$ -vel azt a balra rendezett zárójelezésű kifejezést, amelyet az $R$ kifejezés első $i$ darab tényezőjéből kapunk, azaz:

\begin{aligned} R_1 &= a_{k+1} \\ R_2 &= a_{k+1} * a_{k+2} \\ R_3 &= (a_{k+1} * a_{k+2}) * a_{k+3} \\ &\vdots \\ R_i &= (\dots ((a_{k+1} * a_{k+2}) * a_{k+3}) * \dots ) * a_{k+i} \\ &\vdots \end{aligned}

Először megmutatjuk, hogy bármely $i$ index és az $S$ halmaz tetszőleges $x$ eleme esetén az $x$ tényező bevihető az $R_i$ kifejezés legbelső zárójelén belülre, azaz teljesül az alábbi:

x * R_i = (\dots (((x * a_{k+1}) * a_{k+2}) * a_{k+3}) * \dots ) * a_{k+i}

Ezt $i$ -re vonatkozó teljes indukcióval igazoljuk. Tegyük fel indukciós feltételként, hogy az állítás igaz $i-1$ -re, azaz:

x * R_{i-1} = (\dots (((x * a_{k+1}) * a_{k+2}) * a_{k+3}) * \dots ) * a_{k+i-1}

Most indukciós lépésként megmutatjuk, hogy ekkor ugyanez igaz lesz $i$ -re is. Vegyük észre, hogy az $R_i$ kifejezések fenti definíciója miatt tetszőleges $i$ index esetén $R_i$ = $R_{i-1} * a_{k+i}$ . Emiatt az $x * R_i$ kifejezést így is írhatjuk:

x * R_i = x * (\underbrace{R_{i-1} * a_{k+i}}_{=R_i}) = \dots

A $*$ művelet asszociativitása miatt:

\dots = (x * R_{i-1}) * a_{k+i} = \dots

Végül az indukciós feltétel miatt:

\dots = (\dots (((x * a_{k+1}) * a_{k+2}) * a_{k+3}) * \dots ) * a_{k+i}

Felállítottuk a dominósort, most döntsük is le. Az $i=1$ esetén nincs mit bizonyítani, hiszen $x * R_1 = x * a_{k+1}$ csak egyféleképpen zárójelezhető. Az $i=2$ esetén pedig a $*$ művelet asszociativitása miatt nyilván $x * R_2 = x * (a_{k+1} * a_{k+2}) = (x * a_{k+1}) * a_{k+2}$ .

Ezzel igazoltuk tehát az alábbi összefüggést:

x * R_i = (\dots (((x * a_{k+1}) * a_{k+2}) * a_{k+3}) * \dots ) * a_{k+i}

Ezt felhasználva az eredeti $P$ kifejezést fogjuk lépésenként átzárójelezni úgy, hogy az egy balra rendezett zárójelezés legyen. Ehhez az $R_i$ -hez hasonlóan vezessük be az $L_j$ jelölést is, amely tehát jelölje azt a kifejezést, amelyet az $L$ kifejezés első $j$ darab tényezőjéből kapunk, azaz:

\begin{aligned} L_1 &= a_{1} \\ L_2 &= a_{1} * a_{2} \\ L_3 &= (a_{1} * a_{2}) * a_{3} \\ &\vdots \\ L_j &= (\dots ((a_{1} * a_{2}) * a_{3}) * \dots ) * a_{j} \\ &\vdots \end{aligned}

Vegyük észre, hogy ez alapján tetszőleges $j$ index esetén $L_j$ = $L_{j-1} * a_j$ , így az eredeti $P$ kifejezés átzárójelezésének első lépése így néz ki:

\begin{aligned} P &= \underbrace{( \dots ((a_1 * a_2) * a_3) * \dots ) * a_k}_{=L=L_k=L_{k-1} * a_k} * \underbrace{( \dots ((a_{k+1} * a_{k+2}) * a_{k+3}) * \dots ) * a_n}_{=R=R_{n-k}} = \\ &= (L_{k-1} * a_k) * R_{n-k} = L_{k-1} * (a_k * R_{n-k}) = \\ &= L_{k-1} * (\dots (((a_k * a_{k+1}) * a_{k+2}) * a_{k+3}) * \dots ) * a_n) = \dots \end{aligned}

A baloldali $L=L_k$ kifejezés utolsó $a_k$ tényezőjét tehát sikerült átvinni a jobboldali $R$ kifejezés legbelső zárójelén belülre. Most ugyanezt a lépést végezzük el az eggyel rövidebb $L_{k-1}$ kifejezésre is:

\dots = L_{k-2} * (\dots (((a_{k-1} * a_{k}) * a_{k+1}) * a_{k+2}) * \dots ) * a_n) = \dots

Látható, hogy ez az eljárás mindaddig folytatható, amíg a baloldali kifejezés el nem fogy. Ezen a ponton a $P$ kifejezés valóban egy balra rendezett zárójelezésű kifejezés lesz:

\dots = (\dots (((a_1 * a_2) * a_3) * \dots ) * a_n)

Vagyis azt kaptuk, hogy amennyiben tetszőleges, legfeljebb $n-1$ tényezős szorzat átzárójelezhető, akkor ez igaz lesz az $n$ tényezős szorzatokra is. Felállítottuk tehát a dominósort, és beláttuk, hogy bármely dominó felborítása esetén a soron következő dominó is fel fog borulni. Az első dominó felborítása ebben az esetben triviális, hiszen $n=1$ és $n=2$ esetén nincs mit bizonyítani, a legfeljebb egy vagy két tényezős szorzatok ugyanis csak egyféleképpen zárójelezhetők, $n=3$ esetén pedig a $*$ művelet asszociativitása miatt nyilván $(a_1 * a_2) * a_3 = a_1 * (a_2 * a_3)$ .

Most igazoljuk a tetszőleges sorrendezhetőséget is. Vegyük észre, hogy a tényezők bármely sorrendje előáll egymás utáni szomszédos cserékből, tehát elég egyetlen ilyen cserére megmutatni, hogy az nem változtatja meg a szorzat értékét. Vegyük például az $a_i$ és az $a_{i+1}$ szomszédos elemeket. Ekkor a zárójelezés már bizonyított szabadsága miatt a teljes szorzatot így írhatjuk:

(\text{baloldali rész}) * (a_i * a_{i+1}) * (\text{jobboldali rész}) = \dots

Ám a kommutativitás miatt $a_i * a_{i+1} = a_{i+1} * a_i$ , és így:

\dots = (\text{baloldali rész}) * (a_{i+1} * a_i) * (\text{jobboldali rész})

∎

Alárendelt lap:Megjegyzés

Iratkozz fel a hírlevelünkre