szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 25 kwi 2016, o 02:05 
Użytkownik

Posty: 384
Lokalizacja: Rzeszów
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 a _{1}a _{2}\ldots a_{n} gdzie n  \ge  2 to wynik mnożenia 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 a _{1}a _{2}\ldots a_{n} wynik mnożenia jest taki sam

Istota jest dla n \ge 4

Dowód
Mamy zatem prawo 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 n=2 Wynik mnożenia a_{1}a_{2} oczywiście nie zależy od ustawienia nawiasów
Niech n=3
Wynik mnożenia a_{1}a_{2}a_{3} nie zależy od ustawienia nawiasów na mocy prawa łączności \left( a_{1}a_{2}\right) a_{3}=a_{1}\left( a_{2}a_{3}\right)

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

Zdefiniujmy dla dowolnego k\in\left\{ 1,2,\ldots,n-1\right\}
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 k-tym iloczynem wzorcowym
Natomiast 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 P_{k}=P=P_{1}
Dowód jest indukcyjny( indukcja z ograniczeniem górnym)
Baza indukcji jest oczywiście spełniona P=P_{1}
Załóżmy że P_{l}=P, ale dla l \le n-2
Pokażemy że P_{l+1}=P=P_{l}
Z definicji
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 )
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 P_{l}=P_{l+1}
Na mocy indukcji (ograniczonej) każdyP_{k}=P

Przy jakimkolwiek ustawieniu nawiasów, któreś mnożenie wykonujemy na końcu, wobec czego a _{1}a _{2}\ldots a_{n} jest iloczynem dwóch ciągów o długościach silnie krótszych od n
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 a _{1}a _{2}\ldots a_{n}
Przy tych ustawieniach, mamy iloczyny dwóch ciągów silnie krótszych od n o długościach odpowiednio s,n-s i dla drugiego ustawienia o długościach odpowiednio r,n-r gdzie s,r<n
\Bigl (a_{1}\ldots a_{s} \Bigr ) \Bigl ( a_{s+1}\ldots a_{n}\ \Bigr )
\Bigl (a_{1}\ldots a_{r} \Bigr ) \Bigl ( a_{r+1}\ldots a_{n}\ \Bigr )
Ponieważ są to ciągi silnie krótsze od 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 \Bigl (a_{1}\ldots a_{s} \Bigr ) \Bigl ( a_{s+1}\ldots a_{n}\ \Bigr ) odpowiadał s-owemu iloczynowi wzorcowemu, (dwa iloczyny dwóch wyrażeń równych odpowiednio są równe) Wobec czego \Bigl (a_{1}\ldots a_{s} \Bigr ) \Bigl ( a_{s+1}\ldots a_{n}\ \Bigr )=P_{s}
Dla drugiego ustawienia \Bigl (a_{1}\ldots a_{r} \Bigr ) \Bigl ( a_{r+1}\ldots a_{n}\ \Bigr )
podobnie zamieniamy na P_{r} i podobnie otrzymujemy \Bigl (a_{1}\ldots a_{r} \Bigr ) \Bigl ( a_{r+1}\ldots a_{n}\ \Bigr )=P_{r}
Ponieważ jednak udowodniliśmy 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 :D



Próba
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Łączność działania- niepotrzebne nawiasy, prościej  Jakub Gurak  1
 prawdopodobieństwo działania urządzenia  Flower  9
 Matematyka dyskretna: wykazywanie, działania na zbiorach  drag311  1
 łączność; element nętralny  tres_amusant  0
 wykonaj działania. (uprość wielomiany)  maillo93  9
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl