szukanie zaawansowane
 [ Posty: 15 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 20 kwi 2016, o 23:30 
Użytkownik

Posty: 238
Lokalizacja: Polska
Chciałbym udowodnić uogólnioną łączność czyli inaczej mówiąc możliwość dowolności nawiasów w zapisie a_1 + a_2 + ... + a_n. Dochodzę do wniosku, że to wcale nie jest takie trywialne jak mi się na początku wydawało. Być może mylnie.

Jedyne co mi przychodzi do głowy to dowód "algorytmowo-indukcyjny". Nie wiem na ile jest poprawny, dlatego poniżej moja próba.

Weźmy dowolne n i załóżmy, że dla wszystkich k<n łączność została udowodniona. Musimy pokazać, że łączność zachodzi dla n. Musimy zatem pokazać, że dla n, dla dowolnego ułożenia nawiasów otrzymamy standardowy układ nawiasów, który zapisujemy po prostu bez nawiasów.

Wiemy, że w naszym dowolnym ułożeniu występuje bezspośrednio b:=(a_{i_1} + a_{i_2}). Do b dodawany jest z kolei element. Mamy tutaj dwie możliwośc:
1) Element ma postać a_{i}, wtedy korzystamy z założenia i otrzymujemy (a_{i_1} + a_{i_2} + a_{i_3}).
2) Element ma postać c:= (a_{i_3} + ... + a_{i_p}), gdzie p<n. Wtedy powołujemy się na założenie i usuwamy wszystkie nawiasy w c. Następnie dodajemy b i c korzystając z założenia idukcyjnego.

Następnie postępujemy analogicznie, aż znikną wszystkie nawiasy.

Tak nie do końca mi się podoba ten dowód, bo mam wrażenie, że jest dość opisowy. Pierw myślałem, żeby może zdefiniować taką łącznośc rekurencyjne, ale tutaj też mam pewne problemy.

-- 21 kwi 2016, o 01:00 --

Chyba jednak przekombinowałem, bo teraz dochodzą do wniosku, że:
Mam sumę z pewnymi nawiasami dla n, a_1 + ... +a_n. Wybieram b_j = a_j a_{j+1}. Mam więc sumę z pewnymi nawiasami a_1 + ... + a_{j-1} + b_k + a_{j+2} + ... + a_n. Teraz korzystam z założenia indukcyjnego, więc mogę sobie dowolnie ustawić nawiasy. Więc ustawiam (w sumie nawet nie muszę jakoś specjalnie ustawiać tylko korzystam z podstawowych nawiasów) (...(a_1 + a_2)+a_3)...)+a_{j-1})(a_{j} + a_{j+1})) + a_{j+2})...)+ a_n. I teraz z podstawowego prawa łączności przestawiam sobie nawiasy tak, że otrzymuje podstawową formę. Koniec dowodu.
Góra
Mężczyzna Offline
PostNapisane: 21 kwi 2016, o 02:14 
Moderator

Posty: 4299
Lokalizacja: Kraków PL
Przekombinowałeś.

W definicji:

    Działanie \circ jest łączne w zbiorze X gdy:

      \forall_{a, b, c\in X}\quad a\circ b\circ c=(a\circ b)\circ c=a\circ(b\circ c)

a, b i c mogą być wyrażeniami typu (p\circ q) (zawierające nawiasy). Innymi słowy, nie muszą to być „atomy” zbioru X.
Góra
Mężczyzna Offline
PostNapisane: 21 kwi 2016, o 19:33 
Użytkownik

Posty: 238
Lokalizacja: Polska
A gdzieś pisalem, ze to muszą być "atomy"? Nie wiem jak ta odpowiedź odnosi się do mojego posta.
Góra
Mężczyzna Offline
PostNapisane: 21 kwi 2016, o 21:31 
Moderator

Posty: 4299
Lokalizacja: Kraków PL
Moim zdaniem to, co chcesz udowodnić, bezpośrednio wynika z definicji własności łączności działań i mój post właśnie tego dotyczył.
Góra
Mężczyzna Offline
PostNapisane: 22 kwi 2016, o 22:16 
Użytkownik

Posty: 238
Lokalizacja: Polska
SlotaWoj napisał(a):
Moim zdaniem to, co chcesz udowodnić, bezpośrednio wynika z definicji własności łączności działań i mój post właśnie tego dotyczył.

Nie mogę się tutaj zgodzić. Przecież z góry założyłeś prawdziwość tych wyrażeń złożonych czego robić nie wolno. Z definicji wynika, owszem, to co napisałeś tylko Ty operaujsz na tych samych złożonych wyrażeniach po dwóch stronach, a ja mówię, że wcale nie wiem czy są takie same - to trzeba pierw udowodnić co też zrobiłem w pierwszym poście pod koniec.
Góra
Mężczyzna Offline
PostNapisane: 22 kwi 2016, o 22:48 
Moderator

Posty: 4299
Lokalizacja: Kraków PL
Definicja własności łączności działań jest niejawnie indukcyjna. Wynik działania o tej własności jest niezależny od jakiejkolwiek możliwej kolejności jego wykonania, wyznaczoną przez dowolnie rozbudowaną, w tym zagnieżdżoną strukturę nawiasów.
Góra
Mężczyzna Offline
PostNapisane: 22 kwi 2016, o 23:53 
Użytkownik

Posty: 238
Lokalizacja: Polska
Cytuj:
Wynik działania o tej własności jest niezależny od jakiejkolwiek możliwej kolejności jego wykonania, wyznaczoną przez dowolnie rozbudowaną, w tym zagnieżdżoną strukturę nawiasów.

Gdzie definicja o tym mówi?
Definicja mówi jedynie jak zachowywać się w przypadku trzech elementów (nieważne jak bardzo skomplikowanych). Natomiast, żeby mówić o równośc muszę wiedzieć, że są równe, a do tego muszę zbadać ich strukturę. Twoja podejście jest na zasadzie "muszą być równe, bo definicja tak mówi", jednak ja w deifnicji nic takiego nie odnajduję. Być może ja czegoś tu nie rozumiem...
Góra
Mężczyzna Offline
PostNapisane: 23 kwi 2016, o 16:16 
Użytkownik

Posty: 399
Lokalizacja: Rzeszów
novicjusz napisał(a):
Tak nie do końca mi się podoba ten dowód, bo mam wrażenie, że jest dość opisowy.

Dowód opisowy, to nie problem ogólnie rzecz biorąc. Mi też ten dowód się nie podoba, a to dlatego że nie wyrażasz się zbyt jasno.
novicjusz napisał(a):
Chyba jednak przekombinowałem, bo teraz dochodzą do wniosku, że:
Mam sumę z pewnymi nawiasami dla n, a_1 + ... +a_n. Wybieram b_j = a_j a_{j+1}. Mam więc sumę z pewnymi nawiasami a_1 + ... + a_{j-1} + b_k + a_{j+2} + ... + a_n. Teraz korzystam z założenia indukcyjnego, więc mogę sobie dowolnie ustawić nawiasy. Więc ustawiam (w sumie nawet nie muszę jakoś specjalnie ustawiać tylko korzystam z podstawowych nawiasów) (...(a_1 + a_2)+a_3)...)+a_{j-1})(a_{j} + a_{j+1})) + a_{j+2})...)+ a_n. I teraz z podstawowego prawa łączności przestawiam sobie nawiasy tak, że otrzymuje podstawową formę. Koniec dowodu.

Ten dowód też nie jest do końca jasny
SlotaWoj napisał(a):
Moim zdaniem to, co chcesz udowodnić, bezpośrednio wynika z definicji własności łączności działań i mój post właśnie tego dotyczył.

Też się nie zgodzę
Dla trzech elementów sprawę załatwia łączność działania, ale dla n :?:
Potrzebny jest dowód
novicjusz napisał(a):
Cytuj:
Wynik działania o tej własności jest niezależny od jakiejkolwiek możliwej kolejności jego wykonania, wyznaczoną przez dowolnie rozbudowaną, w tym zagnieżdżoną strukturę nawiasów.

Gdzie definicja o tym mówi?
Definicja mówi jedynie jak zachowywać się w przypadku trzech elementów (nieważne jak bardzo skomplikowanych).

Właśnie dla trzech elementów sprawę załatwia łączność, a dla n to też prawda, ale wymaga dowodu
Może przedstawie ten dowód, ale nie teraz, bo teraz czuje się zmęczony :|
Góra
Mężczyzna Offline
PostNapisane: 23 kwi 2016, o 21:42 
Użytkownik

Posty: 238
Lokalizacja: Polska
A co w tym dowodzie jest nie tak? Mogę rozpisać.

Udowodnijmy, że każdy wyraz (z daną konstelacją nawiasów) dla n \ge 3 można zapisać w formie (...(a_1 + a_2) + a_3)...) + a_n.

Początek indukcyjny:
n=3: Wynika wprost z definicji.

n  \rightarrow n+1:
Załóżmy, że dla n wszystkie wyrazy można zapisać w powyższej formie. Weźmy teraz wyraz dla n+1 i musimy pokazać, że można go sprowadzić do powyższej postaci. W tym wyrazie musi występować (a_j + a_{j+1}) (co jest oczywiste), a więc zdefiniujmy b:= (a_j + a_{j+1}). Zatem wyrażenie możemy zapisać w postaci n wyrazowej. Korzystając z założenia indukcyjnego mamy (...(a_1 + a_2) + a_3)...)+b})... + a_{n+1}, a więc mamy standardowy układ nawiasów dla n wyrazów, a to jest równe (...(a_1 + a_2) + a_3)...)+(a_j+a_{j+1}))... + a_{n+1}. Następnie wystarczy skorzystać tylko z prawa łączności i otrzymujemy standardowe ułożenia dla n+1 co mieliśmy pokazać.
Góra
Mężczyzna Offline
PostNapisane: 24 kwi 2016, o 14:25 
Użytkownik

Posty: 399
Lokalizacja: Rzeszów
novicjusz napisał(a):
W tym wyrazie musi występować (a_j + a_{j+1}) (co jest oczywiste)

Dla mnie nie jest to oczywiste, choć może to prawda, trudno mi powiedzieć

Możesz bowiem mieć a _{1}+\left( a _{2}+\left( a _{3}+\left( a _{4}+\left( a _{5}+a _{6}\right)  \right) \right)  \right)

Czytając od lewa do prawej dopiero na końcu masz a _{5}+a _{6} sumę dwóch elementów, w samym środku
Istnieje bowiem całe bogactwo możliwości ustawiania nawiasów
novicjusz napisał(a):
W tym wyrazie musi występować (a_j + a_{j+1}) (co jest oczywiste)

Jak mówiłem, trudno mi to jest rozstrzygnąć, z powyższych względów, ale przyjmijmy że tak jest, idźmy dalej
Ale dalej też nie dobrze
Cytuj:
(...(a_1 + a_2) + a_3)...)+b})... + a_{n+1}

Piszesz że b po prostu jest dodawane do sumy z lewej strony, a następnie po prostu jest dodawana suma z prawej strony
A możesz mieć np.
a_1 +\left( a _{2}+\left( a _{3}+\left( a _{4}+ a _{5}\right) \right)\right)
Wyróżnijmy a _{4}+a _{5}
Nie jest dodawane suma z lewej strony, tylko z lewej strony jest dodawany element a _{3}, do nowej sumy z lewej strony nie jest dodawana suma, lecz element a _{2}
i do powstałej sumy na koniec a _{1}
Twój dowód nie uwzględnia wszystkich możliwości ustawiania nawiasów A jest to bardzo bogata
rodzina :mrgreen:
Góra
Mężczyzna Offline
PostNapisane: 24 kwi 2016, o 15:30 
Użytkownik

Posty: 238
Lokalizacja: Polska
Jakub Gurak napisał(a):
Dla mnie nie jest to oczywiste, choć może to prawda, trudno mi powiedzieć

Wynika to z samej istoty używania nawiasów. Nawiasy służą temu, abyśmy znali kolejność wykonywania operacji. Możemy je usunąć tylko wtedy, gdy wiemy, że kolejność nie ma znaczenia. A w chwili obecnej wiemy jedynie, że kolejność nie ma znaczenia da n (założenie). Dla n+1 musimy to dopiero udowodnić, dlatego wyrażenie (a_j + a_{j+1}) musi występować.

Jakub Gurak napisał(a):
Możesz bowiem mieć a _{1}+\left( a _{2}+\left( a _{3}+\left( a _{4}+\left( a _{5}+a _{6}\right)  \right) \right)  \right)

Czytając od lewa do prawej dopiero na końcu masz a _{5}+a _{6} sumę dwóch elementów, w samym środku
Istnieje bowiem całe bogactwo możliwości ustawiania nawiasów.

W moim dowodzie kolejność jest nieistotna. Dowód nie bazuje na tym, że wyraz (a_j + a_{j+1}) jest w jakimś konkrentym miejscu. I jak sam widzisz u Ciebie również występuje (a_5 + a_6) czyli w Twoim wyrażeniu jest postać (a_j + a_{j+1}).

Jakub Gurak napisał(a):
Piszesz że b po prostu jest dodawane do sumy z lewej strony, a następnie po prostu jest dodawana suma z prawej strony
A możesz mieć np.
a_1 +\left( a _{2}+\left( a _{3}+\left( a _{4}+ a _{5}\right) \right)\right)
Wyróżnijmy a _{4}+a _{5}
Nie jest dodawane suma z lewej strony, tylko z lewej strony jest dodawany element a _{3}, do nowej sumy z lewej strony nie jest dodawana suma, lecz element a _{2}
i do powstałej sumy na koniec a _{1}
Twój dowód nie uwzględnia wszystkich możliwości ustawiania nawiasów A jest to bardzo bogata
rodzina :mrgreen:

Tego w ogóle nie rozumiem - w moim odczuciu te Twoje rozważania są zupełnie zbędne. Dzięki b mam wyraz n elementowy, a co za tym idzie mogę skorzystać z założenia i dowolnie przestawić sobie nawiasy. Po przestawianiu rozpisuje b i korzystam z prawa łączności i dostaję standardowe ułożenie nawiasów co kończy dowód.
Góra
Mężczyzna Offline
PostNapisane: 24 kwi 2016, o 23:28 
Moderator

Posty: 4299
Lokalizacja: Kraków PL
novicjusz napisał(a):
SlotaWoj napisał(a):
Definicja własności łączności działań jest niejawnie indukcyjna. Wynik działania o tej własności jest niezależny od jakiejkolwiek możliwej kolejności jego wykonania, wyznaczoną przez dowolnie rozbudowaną, w tym zagnieżdżoną strukturę nawiasów.
Gdzie definicja o tym mówi?
Definicja mówi jedynie jak zachowywać się w przypadku trzech elementów (nieważne jak bardzo skomplikowanych). ...
Ograniczmy się do własności łączności dodawania w (nieograniczonych) zbiorach liczb X:

    \forall_{a, b, c\in X}\quad a+b+c=(a+b)+c=a+(b+c)

Każdą liczbę można przedstawić jako sumę dwóch innych liczb i niech a=d+e. Z definicji mamy wtedy:

    \forall_{d, e, b, c\in X}\quad d+e+b+c=(d+e)+b+c=((d+e)+b)+c=(d+e)+(b+c)=...

ale też:

    ...=d+e+(b+c)=d+(e+(b+c))=...

oraz także:

    ...=d+(e+b)+c=(d+e+b)+c=d+(e+b+c)

Dla czterech składników (przy ustalonej ich kolejności, co musimy założyć, bo działanie nie musi być przemienne) to co napisałem wyczerpuje wszystkie możliwe struktury nawiasowe: bez nawiasów, tylko nawiasy 1-go poziomu, nawiasy 1-go i 2-go poziomu.

To co przedstawiłem powyżej ilustruje, co rozumiem jako niejawną indukcyjność definicji.

Definicja używa jedynie trzech składników i dzięki temu jest zwięzła, ale to nie oznacza, że wprowadzenie do niej dodatkowych składników zmienia jej istotę i trzeba czegoś dowodzić.

Trochę to koresponduje z definicją składnika, którą posługują się analizatory składni wyrażeń:

    składnik : czynnik
      lub
    składnik : składnik + czynnik

Gdy działanie „+” nie jest przemienne, jest jeszcze:

    składnik : czynnik + składnik

Tutaj składnik jest zdefiniowany przez czynnik, operator sumy i rekurencję.
Góra
Mężczyzna Offline
PostNapisane: 25 kwi 2016, o 00:24 
Użytkownik

Posty: 238
Lokalizacja: Polska
Niestety mam dalej z tym problem. Pokazałeś coś dla trzech składników, następnie dla czterech i piszesz, że dalej nie trzeba, bo tak przecież jest. Przynajmniej ja tak to widzę. Nie pokazałeś w ogóle czy łącznośc jest prawdziwa dla 20 czy 50 składników. Zawsze możemy argumentować na zasadzie, że coś działa dla określonych wartości to dla reszty też będzie działało i nawet gdy to jest fakt, to z formalnego punktu widzenia nic nie zostało pokazane.
Góra
Mężczyzna Offline
PostNapisane: 25 kwi 2016, o 03:23 
Moderator

Posty: 4299
Lokalizacja: Kraków PL
Bo właśnie na tym polega „indukcyjność” definicji (w wielu źródłach nazywana także rekurencyjnością, tzn. odwołującą się do samej siebie). Przecież z definicją indukcyjną ciągu arytmetycznego:

    a_{n+1}=a_n+r

nie ma żadnych problemów.

Problem jest tylko w tym, że w przypadku definicji własności łączności działań jej indukcyjność nie jest to wyrażona wprost, ale trzeba się jej domyślać, bo (w przypadku liczb) każdą liczbę można przedstawić jako sumę dwóch innych liczb. W przypadku innych obiektów, na których są wykonywane działania łączne będzie się to wyrażało inaczej, ale idea jest podobna lub wręcz taka sama.

Edit:
Oczywiście, z tym (w przypadku dodawania liczb): każdą liczbę można przedstawić jako sumę dwóch innych liczb trzeba trochę uważać, bo w zbiorze liczb naturalnych \NN=\{1,\,2,\,3,\,...\} jest kłopot z jedynką, ale wystarczy ów zbiór rozszerzyć o \{0\} i przyjąć: ... dwóch innych, niekoniecznie różnych od siebie i od sumy, i po problemie.
Oczywiście „puryści” matematyczni mogą uważać, że w związku z tym w klasycznym zbiorze liczb naturalnych (bez zera) to moje uzasadnienie niejawnej indukcyjności definicji własności łączności dodawania liczb nie jest wystarczające.
Góra
Kobieta Offline
PostNapisane: 25 kwi 2016, o 07:01 
Użytkownik
Avatar użytkownika

Posty: 2505
Niech działanie * na zbiorze X będzie łączne, to znaczy dla dowolnych a, b, c \in X zachodzi a*(b*c) = (a*b)*c. Wtedy dowolne rozmieszczenie nawiasów w wyrażeniu a_1 * a_2 * \ldots * a_n nie zmienia wartości wyrażenia.

Dowód. Skorzystamy z pewnego wariantu indukcji: jeżeli teza jest spełniona dla wszystkich m < n, to możemy ją udowodnić takżde dla n. Dla n = 1, 2 nie za bardzo jest co sprawdzać, dla n = 3 to jest po prostu zwykła łączność.

Pokażemy, że zawsze można nawiasy przesunąć w lewo, do postaci ((\ldots((a_1 * a_2) * a_3 ) * \ldots)*a_n) (\star).

Ustalmy n > 3 i załóżmy, że dla m < n teza rzeczywiście jest spełniona. Nieważne jak rozstawimy nawiasy w a_1 * \ldots * a_n, któreś mnożenie wykonujemy na końcu. Mamy więc do czynienia z A * B, gdzie A = a_1 * \ldots * a_m oraz B = a_{m+1} * \ldots * a_n (gdzie 0 < m < n). Z założenia indukcyjnego możemy uporządkować nawiasy w A i B do postaci \star.

Zauważmy, że skoro B = C * a_n, to A * (C * a_n) = (A*C) * a_n i tu właściwie dowód się kończy: to jest to samo, co w Twoim pierwszym poście, tylko sformalizowane, bo w skończenie wielu krokach powyciągamy tak wszystkie "ostatnie" czynniki.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 15 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Udowodnij uogólnioną nierówność Bernoulliego  wiecznie_pytajacy  2
 Suma uogólniona zbiorów, dowód indukcyjny  piotrekd4  0
 Uogólniona nierówność Bernoulliego  Anonymous  10
 Wykazać łączność działania  MakCis  3
 rentą uogólnioną nazywamy rentę, dla której:  spinka0  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl