szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 3 maja 2016, o 23:39 
Użytkownik

Posty: 344
Lokalizacja: Rzeszów
Napisze jeszcze raz, bo udało mi się uzyskać prostszy dowód
Temat ma trafić do kompendium ciekawostek

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} to wynik mnożenia a _{1}a _{2}\ldots a_{n} nie zależy od ustawienia nawiasów

Istota jest dla n \ge 4

Dowód
Łączność oznacza że mamy 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 )
Dla n=1 i n=2 Wynik a_{1} i odpowiednio 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 dodatniego 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}
Niech P=\left( \left( \left( \left( a _{1} a _{2}\right) a _{3}\right)a _{4}\right)\ldots a _{n} \right) (*)
Pokażemy że każde ustawienie nawiasów w a _{1}a _{2}\ldots a_{n} wyznacza iloczyn równy P
Aby to udowodnić zauważmy że 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 )
Zanotujmy jeszcze jedną postać:
\left (a_{m}  \left ( a_{m+1}\left( \ldots \left( a_{n-2} \left ( a_{n-1}a_{n}\right )\right) (**)
Ponieważ a _{1}a _{2}\ldots a_{n} jest iloczynem dwóch ciągów o długościach silnie krótszych od n więc na mocy założenia indukcyjnego możemy dowolnie ustawić nawiasy dla tych ciągów
Sprowadźmy pierwsze wyrażenie tego iloczynu do postaci (*), a drugie do postaci (**)
Tzn.
\Bigl (a_{1}\ldots a_{l} \Bigr ) \Bigl ( a_{l+1}\ldots a_{n}\ \Bigr )=\Bigl( \left( \left( \left( a _{1} a _{2}\right) a _{3}\right)a _{4}\right)\ldots a _{l} \Bigr) \Bigl (a_{l+1}  \bigl ( a_{l+2}\bigl( \ldots \bigl ( a_{n-2} \bigl ( a_{n-1}a_{n}\bigr )\bigr )\Bigr)=
=\Bigl( \bigl( \left( \left( a _{1} a _{2}\right) a _{3}\right)\right)\ldots a _{l}\bigr ) a _{l+1}\Bigr)  \Bigl (a_{l+2}  \bigl ( a_{l+3}\bigl( \ldots \bigl ( a_{n-2} \bigl ( a_{n-1}a_{n}\bigr )\bigr )\Bigr)= Skorzystaliśmy z łączności, kontynuując
=\Bigl( \bigl( \left( \left( a _{1} a _{2}\right) a _{3}\right)\right)\ldots a _{l+1}\bigr ) a _{l+2}\Bigr)  \Bigl (a_{l+3}  \bigl ( a_{l+4}\bigl( \ldots \bigl ( a_{n-2} \bigl ( a_{n-1}a_{n}\bigr )\bigr )\Bigr)=\ldots
=\Bigl (  \left( \left( a _{1} a _{2}\right) a _{3}\right) \ldots a _{n-2}\Bigr)
 \Bigl(  a_{n-1}a_{n}\Bigr )=\Bigl ( \bigl (\left( \left( a _{1} a _{2}\right) a _{3}\right) \ldots a _{n-2}\bigr )a_{n-1} \Bigr) a_{n}=P Korzystaliśmy z łączności
Zatem dowolne ustawienie nawiasów wyznacza tą samą wartość P i krok indukcyjny został dowiedziony
Na mocy indukcji porządkowej twierdzenie jest prawdziwe dla ciągów dowolnej długości

Jedno mnie niepokoi
W końcówce dowodu, robiąc rachunek, w pewnym momencie napisałem =\ldots
i zakończyłem rachunek. Niby widać że tak można zawsze przesunąć nawiasy, ale robiąc dowód
chyba nie powinienem tak pisać Czy komuś to będzie przeszkadzać??

Temat ma trafić do kompendium ciekawostek :)
Góra
Mężczyzna Offline
PostNapisane: 14 maja 2016, o 23:00 
Użytkownik

Posty: 322
Lokalizacja: Toruń
Drobna uwaga: jest problem z nawiasami. W drugim czynniku (w kilku miejscach) masz więcej otwierających nawiasów, niż zamykających. Jeśli chcesz to dopracować, aby gdzieś umieścić, warto to poprawić.
Jeśli chodzi o mnie, wielokropek mi nie przeszkadza. Wielokropek tłumaczę tak: ,,To można udowodnić prostą indukcją. Jest ona na tyle prosta, że pozwolę sobie zrobić krok indukcyjny jedynie dla pierwszego i ostatniego przejścia."
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Łączność działania- niepotrzebne nawiasy  Jakub Gurak  0
 Działania z sigmu jak zrobić?  jacov6  2
 Wyłącz wspólny czynnik przez nawiasy...  agrias5864  3
 Granica ciągu - działania na potęgach  Savannah  1
 działania na silniach  Scintilla_wwy  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl