egzamin z matematyki dyskretnej

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
snajper0208
Użytkownik
Użytkownik
Posty: 128
Rejestracja: 26 paź 2008, o 22:24
Płeć: Mężczyzna
Lokalizacja: Wawrzeńczyce
Podziękował: 11 razy
Pomógł: 14 razy

egzamin z matematyki dyskretnej

Post autor: snajper0208 »

1. Udowodnij równość: \(\displaystyle{ \sum_{i=1}^{n} i ^{3} = \left(\sum_{i=1}^{n} i\right)^{2}}\)
2. Wykazać (przekształcając warunek należenia do zbioru), że zachodzi prawo rachunku zbiorów
\(\displaystyle{ \matfrak{A}\backslash\left(\matfrak{B}\cup\matfrak{C}\right)=\left(\matfrak{A}\backslash \matfrak{B}\right)\backslash\matfrak{C}}\)
3. W zbiorze \(\displaystyle{ \mathrm{Z}_{2009}}\) rozwiązać równanie \(\displaystyle{ 7x\equiv3}\)
4. Znaleźć nwd(982,688) oraz takie liczby \(\displaystyle{ \matfrak{k,l}\in \matfrak{Z}}\), że \(\displaystyle{ \matfrak{k} \cdot 982+\matfrak{l}\cdot688=nwd(982,688)}\)
5. Na zbiorze \(\displaystyle{ \matfrak{S}=\{0,1,2,3,4\}}\) określono relację \(\displaystyle{ \matfrak{R}}\) następująco: \(\displaystyle{ \left(\matfrak{m,n}\right)\in\matfrak{R}}\) wtw. gdy \(\displaystyle{ \matfrak{m+n} \le 3}\)


EDIT:
polecenia do zadania 5
a) sprawdzić, które z własności: zwrotność, symetria, przechodniość, antysymetria spełnia relacja \(\displaystyle{ \matfrak{R}}\)
b) zapisać tę relację jako zbiór par uporządkowanych


Reszty nie daję do rozwiązania (było 15, wybrałem najtrudniejsze [wg mnie]), bo wstyd takich rzeczy nie umieć
Ostatnio zmieniony 25 lip 2009, o 20:29 przez snajper0208, łącznie zmieniany 1 raz.
Awatar użytkownika
czeslaw
Użytkownik
Użytkownik
Posty: 2156
Rejestracja: 5 paź 2008, o 22:12
Płeć: Mężczyzna
Lokalizacja: Politechnika Wrocławska
Podziękował: 44 razy
Pomógł: 317 razy

egzamin z matematyki dyskretnej

Post autor: czeslaw »

Wstyd to nie umieć się do tego przyznać, jak to ktoś mądry kiedyś powiedział.

1. Po prawej masz sumę ciągu arytmetycznego (podniesioną do kwadratu, ale to mniej istotne), po zapisaniu poleć indukcją i wychodzi.
2. Masz udowodnić, że:
\(\displaystyle{ x \in A\backslash (B \cup C) \Leftrightarrow x \in (A \backslash B)\backslash C}\)
Mam nadzieję że umiesz. Najpierw w jedną stronę (implikacja) i potem w drugą (implikacja odwrócona).
4. NWD liczyło się w przedszkolu chyba Robisz dwa takie słupeczki i w każdym wypisujesz po kolei dzielniki, dzieląc również liczbę. Jak sobie przypomnisz metodę to zrobisz.
5. Chyba polecenia zabrakło.

Jakby jeszcze coś to pisz, ktoś pomoże. Ewentualne problemy też zgłaszaj.
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

egzamin z matematyki dyskretnej

Post autor: Zordon »

czeslaw pisze: 4. NWD liczyło się w przedszkolu chyba Robisz dwa takie słupeczki i w każdym wypisujesz po kolei dzielniki, dzieląc również liczbę. Jak sobie przypomnisz metodę to zrobisz.
no, niestety drugiej części pytania tak nie zrobi, trzeba wykorzystać rozszerzony algorytm Euklidesa.
frej

egzamin z matematyki dyskretnej

Post autor: frej »

3. \(\displaystyle{ 7|2009}\), więc nie ma rozwiązań. Gdyby \(\displaystyle{ (7,2009)=1}\) to algorytm Euklidesa trzeba zastosować.
Wasilewski
Użytkownik
Użytkownik
Posty: 3921
Rejestracja: 10 gru 2007, o 20:10
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 36 razy
Pomógł: 1194 razy

egzamin z matematyki dyskretnej

Post autor: Wasilewski »

5) Nie jest zwrotna (para (2,2)), jest symetryczna (oczywiste, ponieważ dodawanie jest przemienne), nie jest przechodnia (pary (1,2) i (2,1)), nie jest antysymetryczna (znowu (2,1) i (1,2)). Zapisać relację jako zbiór par uporządkowanych to chyba nie problem.
snajper0208
Użytkownik
Użytkownik
Posty: 128
Rejestracja: 26 paź 2008, o 22:24
Płeć: Mężczyzna
Lokalizacja: Wawrzeńczyce
Podziękował: 11 razy
Pomógł: 14 razy

egzamin z matematyki dyskretnej

Post autor: snajper0208 »

frej pisze:3. \(\displaystyle{ 7|2009}\), więc nie ma rozwiązań. Gdyby \(\displaystyle{ (7,2009)=1}\) to algorytm Euklidesa trzeba zastosować.
a mógłbyś to trochę szerzej omówić ? bo niestety, ale ani na naszych ćwiczeniach, ani nigdy wcześniej nie spotkałem sie z takim typem zadań... no i postanowiłem poszukać na necie aż dotarłem tutaj
Wasilewski pisze:5) Nie jest zwrotna (para (2,2)), jest symetryczna (oczywiste, ponieważ dodawanie jest przemienne), nie jest przechodnia (pary (1,2) i (2,1)), nie jest antysymetryczna (znowu (2,1) i (1,2)). Zapisać relację jako zbiór par uporządkowanych to chyba nie problem.
no dobra, widzę rozwiązania, ale jak to zapisać ? chociaż pierwsze linijki, resztę już doliczę
Wasilewski
Użytkownik
Użytkownik
Posty: 3921
Rejestracja: 10 gru 2007, o 20:10
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 36 razy
Pomógł: 1194 razy

egzamin z matematyki dyskretnej

Post autor: Wasilewski »

Zatem na przykład uzasadnienie dlaczego nie jest zwrotna. Zaprzeczenie definicji zwrotności wygląda tak:
\(\displaystyle{ \exists_{x} \neg (x Rx)}\)
Jest to zdanie prawdziwe, co można pokazać, wskazując palcem x=2.
frej

egzamin z matematyki dyskretnej

Post autor: frej »

To powinno trochę wyjaśnić, mam nadzieję.
snajper0208
Użytkownik
Użytkownik
Posty: 128
Rejestracja: 26 paź 2008, o 22:24
Płeć: Mężczyzna
Lokalizacja: Wawrzeńczyce
Podziękował: 11 razy
Pomógł: 14 razy

egzamin z matematyki dyskretnej

Post autor: snajper0208 »

2. usiadłem, popróbowałem i zrobiłem coś takiego:

\(\displaystyle{ \matfrak{A} \backslash \left(\matfrak{B} \cup \matfrak{C} \right) = \left(\matfrak{A} \backslash \matfrak{B} \right) \backslash \matfrak{C}\\
\\
\matfrak{x} \in \left(\matfrak{B} \cup \matfrak{C} \right) \Leftrightarrow \matfrak{x} \in \matfrak{B} \vee \matfrak{x} \in \matfrak{C} \\
\matfrak{x} \in \matfrak{A} \backslash\left(\matfrak{B} \cup \matfrak{C} \right) \Leftrightarrow \matfrak{x} \in \matfrak{A} \wedge \matfrak{x} \notin \left(\matfrak{B} \cup \matfrak{C} \right)\\
\matfrak{x} \in \left(\matfrak{A} \backslash \matfrak{B} \right) \backslash \matfrak{C} \Leftrightarrow \left( \matfrak{x} \in \matfrak{A} \wedge \matfrak{x} \notin \matfrak{B}\right) \wedge \matfrak{x} \notin \matfrak {C}\\

\mathrm{L}=\matfrak{x} \in \matfrak{A} \wedge \matfrak{x} \notin \left(\matfrak{B} \cup \matfrak{C} \right)=\\
=\matfrak{x} \in \matfrak{A} \wedge \neg \left( \matfrak{x} \in \matfrak{B} \vee \matfrak{x} \in\matfrak{C}\right)=\\
\matfrak{x} \in \matfrak{A} \wedge \matfrak{x} \notin \matfrak{B} \wedge \matfrak{x} \notin \matfrak{C}=\\
=\mathrm{P}}\)


może ktoś sprawdzić czy to jest poprawne rozumowanie ?
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

egzamin z matematyki dyskretnej

Post autor: Zordon »

snajper0208 pisze:2. usiadłem, popróbowałem i zrobiłem coś takiego:

\(\displaystyle{ \matfrak{A} \backslash \left(\matfrak{B} \cup \matfrak{C} \right) = \left(\matfrak{A} \backslash \matfrak{B} \right) \backslash \matfrak{C}\\
\\
\matfrak{x} \in \left(\matfrak{B} \cup \matfrak{C} \right) \Leftrightarrow \matfrak{x} \in \matfrak{B} \vee \matfrak{x} \in \matfrak{C} \\
\matfrak{x} \in \matfrak{A} \backslash\left(\matfrak{B} \cup \matfrak{C} \right) \Leftrightarrow \matfrak{x} \in \matfrak{A} \wedge \matfrak{x} \notin \left(\matfrak{B} \cup \matfrak{C} \right)\\
\matfrak{x} \in \left(\matfrak{A} \backslash \matfrak{B} \right) \backslash \matfrak{C} \Leftrightarrow \left( \matfrak{x} \in \matfrak{A} \wedge \matfrak{x} \notin \matfrak{B}\right) \wedge \matfrak{x} \notin \matfrak {C}\\

\mathrm{L}=\matfrak{x} \in \matfrak{A} \wedge \matfrak{x} \notin \left(\matfrak{B} \cup \matfrak{C} \right)=\\
=\matfrak{x} \in \matfrak{A} \wedge \neg \left( \matfrak{x} \in \matfrak{B} \vee \matfrak{x} \in\matfrak{C}\right)=\\
\matfrak{x} \in \matfrak{A} \wedge \matfrak{x} \notin \matfrak{B} \wedge \matfrak{x} \notin \matfrak{C}=\\
=\mathrm{P}}\)


może ktoś sprawdzić czy to jest poprawne rozumowanie ?
dobrze, ale pisanie L=jakaś formuła=P nie jest zbyt ładne i nie ma większego sensu.
Twoje rozumowanie sprowadza się do tego, że \(\displaystyle{ x\in A \backslash (B \cup C)\Leftrightarrow x\in (A \backslash B) \backslash C}\), i to jest to co należało udowodnić.
snajper0208
Użytkownik
Użytkownik
Posty: 128
Rejestracja: 26 paź 2008, o 22:24
Płeć: Mężczyzna
Lokalizacja: Wawrzeńczyce
Podziękował: 11 razy
Pomógł: 14 razy

egzamin z matematyki dyskretnej

Post autor: snajper0208 »

więc jak mogę to zapisać po "matematycznemu" ?
Awatar użytkownika
alchemik
Użytkownik
Użytkownik
Posty: 285
Rejestracja: 8 kwie 2008, o 01:24
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 23 razy
Pomógł: 65 razy

egzamin z matematyki dyskretnej

Post autor: alchemik »

Dosyć łatwo rozwiązuję się równości za biorach wykorzystując funkcję charakterystyczną zbioru:

59332.htm
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

egzamin z matematyki dyskretnej

Post autor: Zordon »

Następujące zdania są równoważne:
\(\displaystyle{ x\in A \backslash (B \cup C)}\)
\(\displaystyle{ x\in A \wedge \neg x \in (B \cup C)}\)
\(\displaystyle{ x\in A \wedge \neg (x \in B \vee x \in C)}\)
z deMorgana:
\(\displaystyle{ x\in A \wedge (x \notin B \wedge x \notin C)}\)
\(\displaystyle{ x\in A \wedge x \notin B \wedge x \notin C}\)
\(\displaystyle{ (x\in A \wedge x \notin B ) \wedge x \notin C}\)
\(\displaystyle{ (x\in A \backslash B) \wedge x \notin C}\)
\(\displaystyle{ x \in ( A \backslash B ) \backslash C}\)

Stąd dla dowolnego x: \(\displaystyle{ x\in A \backslash (B \cup C) \Leftrightarrow x \in ( A \backslash B ) \backslash C}\)

więc te zbiory są równe. Jak widać, prawie to samo co napisałeś Ty, tylko troche uporządkowane.
ODPOWIEDZ