Łączność działania- niepotrzebne nawiasy

Tutaj można wpisywać swoje propozycje tematów do kompendium oraz dyskutować na tematy, które później trafią do właściwego działu Kompendium.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 738
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 24 razy
Pomógł: 49 razy

Łączność działania- niepotrzebne nawiasy

Post autor: Jakub Gurak » 25 kwie 2016, o 02:05

Będę chciał uzasadnić że jeśli działanie jest łączne, to nie jest potrzebne dawanie nawiasów

Dokładniej, jeśli mamy działanie mnożenia, które jest łączne oraz ciąg elementów \(\displaystyle{ a _{1}a _{2}\ldots a_{n}}\) gdzie \(\displaystyle{ n \ge 2}\) to wynik mnożenia \(\displaystyle{ a _{1}a _{2}\ldots a_{n}}\) nie zależy od ustawienia nawiasów, tzn. dla dowolnych dwóch układów nawiasów w \(\displaystyle{ a _{1}a _{2}\ldots a_{n}}\) wynik mnożenia jest taki sam

Istota jest dla \(\displaystyle{ n \ge 4}\)

Dowód
Mamy zatem prawo \(\displaystyle{ a \left( bc\right)=\left( ab\right) c}\)

Dowód korzysta z indukcji porządkowej
Przez indukcję ze względu na długość ciągu (ilość zmiennych w ciągu )
Niech \(\displaystyle{ n=2}\) Wynik mnożenia \(\displaystyle{ a_{1}a_{2}}\) oczywiście nie zależy od ustawienia nawiasów
Niech \(\displaystyle{ n=3}\)
Wynik mnożenia \(\displaystyle{ a_{1}a_{2}a_{3}}\) nie zależy od ustawienia nawiasów na mocy prawa łączności \(\displaystyle{ \left( a_{1}a_{2}\right) a_{3}=a_{1}\left( a_{2}a_{3}\right)}\)

Niech \(\displaystyle{ n \ge 4}\) i załóżmy że dla każdego \(\displaystyle{ m}\) naturalnego od \(\displaystyle{ 2}\) w górę, ale mniejszego od \(\displaystyle{ n}\) oraz dowolnego ciągu \(\displaystyle{ a _{1}a _{2}\ldots a_{m}}\) wynik mnożenia \(\displaystyle{ a _{1}a _{2}\ldots a_{m}}\) nie zależy od ustawienia nawiasów
Weźmy dowolny ciąg \(\displaystyle{ a _{1}a _{2}\ldots a_{n}}\) Pokażemy że wynik mnożenia \(\displaystyle{ a _{1}a _{2}\ldots a_{n}}\) nie zależy od ustawienia nawiasów

Zdefiniujmy dla dowolnego \(\displaystyle{ k\in\left\{ 1,2,\ldots,n-1\right\}}\)
\(\displaystyle{ P _{k}=\Bigl (\left ( \left ( a _{1}a _{2} \right)a _{3}\right) \ldots a _{k}\Bigr ) \cdot \Bigl (a_{k+1}\bigl( a_{k+2} \bigl( \ldots \bigl( a_{n-2} \bigl( a_{n-1}a_{n}\bigr) \bigr ) \Bigr )}\)
I nazwijmy go \(\displaystyle{ k}\)-tym iloczynem wzorcowym
Natomiast \(\displaystyle{ P=P _{1}=a_{1} \cdot \Bigl( a_{2}\bigl ( a_{3}\bigl( \ldots \bigl( a_{n-2} \bigl ( a_{n-1}a_{n}\bigr )\Bigr)}\)
nazwijmy podstawowym iloczynem wzorcowym

Pokażemy że każdy iloczyn wzorcowy jest równy podstawowemu iloczynowi wzorcowemu, czyli każdy \(\displaystyle{ P_{k}=P=P_{1}}\)
Dowód jest indukcyjny( indukcja z ograniczeniem górnym)
Baza indukcji jest oczywiście spełniona \(\displaystyle{ P=P_{1}}\)
Załóżmy że \(\displaystyle{ P_{l}=P}\), ale dla \(\displaystyle{ l \le n-2}\)
Pokażemy że \(\displaystyle{ P_{l+1}=P=P_{l}}\)
Z definicji
\(\displaystyle{ P _{l}=\Bigl (\left ( \left ( a _{1}a _{2} \right)a _{3}\right) \ldots a _{l}\Bigr ) \cdot \Bigl (a_{l+1}\bigl( a_{l+2} \bigl( \ldots \bigl( a_{n-2} \bigl ( a_{n-1}a_{n}\bigr )\Bigr )}\)
\(\displaystyle{ P _{l+1}=\Bigl (\left ( \left ( a _{1}a _{2} \right)a _{3}\right) \ldots a _{l}\bigl) a_{l+1}\Bigr ) \cdot \Bigl (a_{l+2}\bigl( a_{l+3} \bigl( \ldots \bigl( a_{n-2} \bigl ( a_{n-1}a_{n}\bigr )\Bigr )}\)
I widać że z łączności \(\displaystyle{ P_{l}=P_{l+1}}\)
Na mocy indukcji (ograniczonej) każdy\(\displaystyle{ P_{k}=P}\)

Przy jakimkolwiek ustawieniu nawiasów, któreś mnożenie wykonujemy na końcu, wobec czego \(\displaystyle{ a _{1}a _{2}\ldots a_{n}}\) jest iloczynem dwóch ciągów o długościach silnie krótszych od \(\displaystyle{ n}\)
\(\displaystyle{ a _{1}a _{2}\ldots a_{n}=\Bigl (a_{1}\ldots a_{l} \Bigr ) \Bigl ( a_{l+1}\ldots a_{n}\ \Bigr )}\)

Teraz weźmy dwa ustawienia nawiasów w \(\displaystyle{ a _{1}a _{2}\ldots a_{n}}\)
Przy tych ustawieniach, mamy iloczyny dwóch ciągów silnie krótszych od \(\displaystyle{ n}\) o długościach odpowiednio \(\displaystyle{ s,n-s}\) i dla drugiego ustawienia o długościach odpowiednio \(\displaystyle{ r,n-r}\) gdzie \(\displaystyle{ s,r<n}\)
\(\displaystyle{ \Bigl (a_{1}\ldots a_{s} \Bigr ) \Bigl ( a_{s+1}\ldots a_{n}\ \Bigr )}\)
\(\displaystyle{ \Bigl (a_{1}\ldots a_{r} \Bigr ) \Bigl ( a_{r+1}\ldots a_{n}\ \Bigr )}\)
Ponieważ są to ciągi silnie krótsze od \(\displaystyle{ n}\) więc na mocy założenia indukcyjnego wynik każdego z tych czterech nawiasów nie zależy od dalszego głębszego ustawiania nawiasów
Ustawmy więc nawiasy tak aby \(\displaystyle{ \Bigl (a_{1}\ldots a_{s} \Bigr ) \Bigl ( a_{s+1}\ldots a_{n}\ \Bigr )}\) odpowiadał \(\displaystyle{ s}\)-owemu iloczynowi wzorcowemu, (dwa iloczyny dwóch wyrażeń równych odpowiednio są równe) Wobec czego \(\displaystyle{ \Bigl (a_{1}\ldots a_{s} \Bigr ) \Bigl ( a_{s+1}\ldots a_{n}\ \Bigr )=P_{s}}\)
Dla drugiego ustawienia \(\displaystyle{ \Bigl (a_{1}\ldots a_{r} \Bigr ) \Bigl ( a_{r+1}\ldots a_{n}\ \Bigr )}\)
podobnie zamieniamy na \(\displaystyle{ P_{r}}\) i podobnie otrzymujemy \(\displaystyle{ \Bigl (a_{1}\ldots a_{r} \Bigr ) \Bigl ( a_{r+1}\ldots a_{n}\ \Bigr )=P_{r}}\)
Ponieważ jednak udowodniliśmy \(\displaystyle{ P_{r}=P=P_{s}}\) to te dwa ustawienia nawiasów dają ten sam wynik i krok indukcyjny został dowiedziony
Na mocy indukcji porządkowej twierdzenie jest udowodnione Próba
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

ODPOWIEDZ