szukanie zaawansowane
 [ Posty: 16 ]  Przejdź na stronę 1, 2  Następna strona
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 30 sie 2012, o 22:42 
Użytkownik
Avatar użytkownika

Posty: 57
Witajcie. Zbliża mi się powoli poprawka z dyskretnej, dlatego proszę o sprawdzenie kilku zadań z egzaminu podstawowego.

1. Mamy:
A=\left\{ 1,2,3, \left\{ 1,2,3 \right\} \right\} \\
B=\left\{ \left\{ 1,2 \right\} 1,2 \right\} \\
C=\left\{ \left\{ 1,2,3 \right\} 1,2 \right\}
Wyznaczyć moce poniższych zbiorów:
a) \left( A  \setminus B \right)  \cup C \\
b) \left( B  \setminus  A \right)   \setminus  (B  \times C) \\
c) \left( C  \cup  A \right)  \setminus \left( A  \setminus  B \right) \\
d) \left( A  \cup B \right)  \times C

Moje odpowiedzi to:
a) 4
b) 1
c) 2
d) 15
Na egzaminie schrzaniłem, bo uwzględniłem elementy które się powtarzały ;/

2. Uniwersum jest niepustym zbiorem studentów. Definiujemy następujące predykaty:
L\left(x,y\right) - y jest lubiany przez x
M\left(x\right) - x lubi matematykę
R\left(x,y\right) \Leftrightarrow x=y
Wyraź w języku predykatów pierwszego rzędu, korzystając wyłącznie ze zdefiniowanych powyżej predykatów następujące zdania:
a) Dokładnie jeden student lubi wszystkich studentów
b) Wszyscy lubią studentów, którzy lubią matematykę
c) Jest co najmniej jeden student, który lubi matematykę i nie lubi żadnego studenta poza sobą

Moje odpowiedzi:
a) \exists s \in U \left(M\left(s\right)\right)  \wedge \forall x \in U \left(M\left(x\right)  \rightarrow R\left(x,s\right)\right)
b) \forall s \in U \left(M\left(s\right) \rightarrow \forall x \in U \left(L\left(x,s\right)\right)\right)
c) \exists s \in U \left(M\left(s\right)  \wedge \left(\forall x \in U \left(L\left(s,x\right)  \rightarrow  R\left(s,x\right)\right)\right)

3. Wyznacz liczbę relacji
a) Porządku częściowego w zbiorze \left\{ 1,2,3 \right\}
b) Porządku liniowego w zbiorze \left\{ 1,2,3,4,5,6 \right\}
c) Typu równoważności w zbiorze \left\{ 1,2,3 \right\}

Moje odpowiedzi (tutaj żadnej nie jestem pewien bo nie jestem pewien czy dobrze rozumiem zadanie):
a) 6
b) 30? (bo jest 6 elementów i każdy jest w relacji z pozostałymi 5)
c) 12 albo 9 (zależy czy relacja zwrotna liczy się raz czy dwa razy)

4. Przedstaw przykład relacji równoważności w zbiorze liczb naturalnych, która ma dokładnie cztery kalsy abstrakcji - dwie skończone i dwie nieskończone.
Tutaj zupełnie nie byłem pewien co wpisać więc wpisałem takie coś:
xRy \Leftrightarrow x > y  \vee x = 2y  \vee x+y<100  \vee x+y=10
No właśnie, pierwsze 2 są nieskończone, następne skończone, tylko nie wiedziałem czy mam tam powstawiać "lub" czy jak to zapisać...

5. Na ile sposobów można ułożyć 12-literowe słowo z liter \left\{ a,b,c \right\} aby
a) każda litera wystąpiła dokładnie 4 razy
b) dokładnie jedna litera wystąpiła dokładnie jeden raz
c) litera "a" i litera "b" wystąpiły dokładnie 3 razy

Moje odpowiedzi:
a) \frac{12!}{4! \cdot 4! \cdot 4!}
To samo napisałem na egzaminie i wydaje się być słuszne. W końcu 12 literek mieszam na różne sposoby i wywalam powtarzające się słowa
b) 3 \cdot 12 \cdot 2^{11}
Wybieramy jedną z 3 literek, stawiamy ją na jednym z dwunastu miejsc, a pozostałe 11 możemy wypełnić każde na 2 sposoby. Na egzaminie w tym podpunkcie napisałem dokładnie to samo.
c) Tutaj mam trochę problem, bo na egzaminie zrozumiałem to zupełnie inaczej, niż rozwiązując dzisiaj. Dzisiaj założyłem, że w sumie mają liter "a" i/lub "b" ma być 3, stąd odpowiedź:
{12 \choose 3}  \cdot 2^{3}
Wybieramy 3 miejsca z 12 na których będą stać te literki, następnie każde z tych miejsc możemy wypełnić na 2 sposoby.
Na egzaminie natomiast zrozumiałem, że każda z tych liter ma się pojawić dokładnie 3 razy, co zaprowadziło do odpowiedzi:
\frac{12!}{3! \cdot 3! \cdot 6!}
stawiamy w słowie 3 litery "a", 3 "b", 6 "c" i permutujemy, pomijając powtarzające się wyrazy.


Proszę o sprawdzenie, ewentualnie udzielenie wskazówek, gdyby coś było źle. Zależy mi na zrozumieniu popełnionych przeze mnie błędów (jeśli takowe były - a raczej były, bo inaczej bym nie musiał martwić się poprawką ;))
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 31 sie 2012, o 20:20 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
2.
Marmite napisał(a):
a) \exists s \in U \left(M\left(s\right)\right)  \wedge \forall x \in U \left(M\left(x\right)  \rightarrow R\left(x,s\right)\right)

Tu napisałeś, że istnieje dokładnie jeden student lubiący matematykę. A jakie było polecenie?

3.
Marmite napisał(a):
a) 6

Za mało. Pokaż, jakie porządki znalazłeś, to Ci podpowiem co przeoczyłeś. Jest 5 takich porządków z dokładnością do izomorfizmu.

Marmite napisał(a):
b) 30?

Za mało.

Marmite napisał(a):
(bo jest 6 elementów i każdy jest w relacji z pozostałymi 5)

To relacja porządku polega na tym, że każdy element jest w relacji z każdym?

Marmite napisał(a):
c) 12 albo 9 (zależy czy relacja zwrotna liczy się raz czy dwa razy)

Za dużo. Tego co napisałeś w nawiasie, nie rozumiem. Pokaż, jakie relacje tu znalazłeś.

-- 31 sie 2012, o 20:25 --

Wiem już chyba, o co Ci chodziło w 3. To nie ma sensu. Musisz się dowiedzieć co to jest relacja, zanim zaczniesz rozwiązywać zadanie.


4. Najpierw ustal jakieś klasy abstrakcji a dopiero potem definiuj relację. To co napisałeś, nie ma związku z zadaniem.

1, 5. ok
Góra
Mężczyzna Offline
PostNapisane: 31 sie 2012, o 22:25 
Użytkownik
Avatar użytkownika

Posty: 57
norwimaj napisał(a):
2.
Marmite napisał(a):
a) \exists s \in U \left(M\left(s\right)\right)  \wedge \forall x \in U \left(M\left(x\right)  \rightarrow R\left(x,s\right)\right)

Tu napisałeś, że istnieje dokładnie jeden student lubiący matematykę. A jakie było polecenie?


Hmm, tu się jakiś chochlik wkradł przy przepisywaniu. Nie wiem dlaczego. Powinno być:
\exists s \in U \left(\forall t \in U \left(L\left(s,t\right)\right)\right) \wedge \forall v \in U \left(\left(\forall x \in U \left( L\left(v,x\right)\right)\right) \rightarrow R\left(x,s\right)\right)

Jeśli chodzi o relacje, to bez bicia przyznam się, że jestem noga i być może źle rozumiem te zadania. I od razu uprzedzam, że z tego powodu moje próby wyjaśnień "jak do tego doszedłem" mogą być troche bełkotem. Więc zadanie 3:

Cytuj:
Za mało. Pokaż, jakie porządki znalazłeś, to Ci podpowiem co przeoczyłeś. Jest 5 takich porządków z dokładnością do izomorfizmu.

Cóż, liczba 6 wynika stąd, że wg mojej książki (K.A. Ross, Charles R. B. Wright - Matematyka Dyskretna, 1996) relacja częściowego porządku, o jaką mnie tu proszą, to relacja zwrotna, antysymetryczna i przechodnia. Niestety nie powiedzieli tutaj dokładnie o jaką relację chodzi więc przyjąłem \le. Wtedy w relacji są 1 z 2, 1 z 3, 2 z 3 oraz każdy z elementów ze sobą (no bo w końcu zwrotna jest), co daje razem 6.

Co do następnego przykładu i wyniku 30 - ponownie wg książki, relacja porządku liniowego to relacja kiedy dla wszystkich elementów t,s ze zbioru S zachodzi albo s  \le t, albo t  \le s. No czyli wynikałoby że każdy element jest w relacji z każdym innym, bo dla każdej takiej pary zachodzi to, o czym książka pisze. Stąd 30 (ewentualnie 36, bo w końcu jest "mniejsze lub równe")

I następny przykład: Relacja typu równoważności. Czyli przechodnia, symetryczna, zwrotna. Ponownie nie wiem o jaką mnie pytają więc zakładam że chodzi o \le Wtedy w relacji są 1 z 2, 1 z 3, 2 z 3. Ponieważ relacja jest symetryczna, to znaczy że wtedy w relacji są także 2 z 1, 3 z 1 i 3 z 2. Doliczając jeszcze 3 zwrotne relacje wychodzi nam 9.


Jeśli chodzi o zadanie numer 4. no to właśnie myślałem, że tym co zapisałem ustalam klasy abstrakcji. Wygląda na to, że źle myślałem bo teraz to nawet sam nie mam pojęcia o co mi chodziło ;) więc czy klasą abstrakcji będą np. "liczby podzielne przez 3", "liczby o 1 mniejsze od potęg liczby 2", "liczby mniejsze od 10" i "liczby będące rozwiązaniami równania a^{2} + 3a = 100"?
Góra
Mężczyzna Offline
PostNapisane: 1 wrz 2012, o 13:35 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
No to teraz drugie chyba dobrze, chociaż zawsze przy takich przykładach bywają wątpliwości, bo języki naturalne nie są jednoznaczne.

W trzecim masz rację co do tego że nie rozumiesz treści zadania. Pytają o liczbę relacji a nie o liczbę elementów w relacji. W przykładzie a) jedną z takich relacji jest porządek liniowy \le. Ta relacja ma 3 elementy, to znaczy są trzy pary elementów zbioru \{1,2,3\} będących w tej relacji, ale to zupełnie nie ma znaczenia w tym zadaniu.

Mylisz się też w przykładzie c), twierdząc że \le jest relacją równoważności. Nie jest to relacja symetryczna, bo 2\le3, ale nieprawda że 3\le2.


W czwartym zapominasz o tym że rodzina klas abstrakcji stanowi podział uniwersum. W Twoim przykładzie liczba 3 należy do trzech klas abstrakcji, a powinna należeć do dokładnie jednej.
Góra
Mężczyzna Offline
PostNapisane: 3 wrz 2012, o 00:24 
Użytkownik
Avatar użytkownika

Posty: 57
norwimaj napisał(a):
W trzecim masz rację co do tego że nie rozumiesz treści zadania. Pytają o liczbę relacji a nie o liczbę elementów w relacji.


Aha, teraz przynajmniej rozumiem, dzięki :) chociaż obawiam się że i tak nie umiałbym znaleźć wszystkich możliwych relacji... Ale to już inna bajka.

Cytuj:
W czwartym zapominasz o tym że rodzina klas abstrakcji stanowi podział uniwersum. W Twoim przykładzie liczba 3 należy do trzech klas abstrakcji, a powinna należeć do dokładnie jednej.


Hm, ale jak to wtedy mam podzielić? Jak znaleźć 4 takie klasy abstrakcji żeby stanowiły podział uniwersum taki, żeby każdy element nalezał tylko do jednej z nich i w dodatku 2 były skończone? Bo nieskończone to łatwo, powiedzmy np. "liczby będące potęgami liczby pierwszej X" (i Y) - i szczerze mówiąc to jedyny pomysł, jaki mi przychodzi do głowy. A jeszcze mam znaleźć relację, która ma 4 klasy abstrakcji, 2 skończone i 2 nie - to już dla mnie za trudne. Jaka to mogłaby być relacja?
Góra
Mężczyzna Offline
PostNapisane: 3 wrz 2012, o 14:44 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
Na przykład jako klasy nieskończone możesz wziąć zbiór liczb parzystych większych od 5 i zbiór liczb nieparzystych większych od 13. Jeszcze musisz zbiór pozostałych liczb podzielić na dwa niepuste zbiory.

Marmite napisał(a):
obawiam się że i tak nie umiałbym znaleźć wszystkich możliwych relacji...

Próbuj. Najpierw policz, ile jest porządków liniowych, czyli takich:

\begin{picture}(0,0)
\multiput(0,0)(0,20){3}{\circle*{4}}
\put(0,0){\line(0,1){40}}
\put(-4,-4){$.$}
\put(-4,44){$.$}
\end{picture}
Góra
Mężczyzna Offline
PostNapisane: 3 wrz 2012, o 15:31 
Użytkownik
Avatar użytkownika

Posty: 57
norwimaj napisał(a):
Na przykład jako klasy nieskończone możesz wziąć zbiór liczb parzystych większych od 5 i zbiór liczb nieparzystych większych od 13. Jeszcze musisz zbiór pozostałych liczb podzielić na dwa niepuste zbiory.


Dobrze, to drugie zadanie na razie zostwamy. Cieszę się że chociaż zrozumiałem cala ideę klas abstrakcji za co dziękuję ;) jednak teraz postawmy problem w kontekście zadania. Znalezienie relacji, która ma 4 klasy abstrakcji. Polecenie było takie jak napisałem, a w miejscu do wypełnienia stało już
xRy \Leftrightarrow ....................................

No i teraz już ostatnie pytanie odnośnie tego zadania: wiem już co to są dokładnie klasy abstrakcji, wiem jakie mogę utworzyć 2 skończone i 2 nieskończone, żeby sie wzajemnie uzupełniały. A jak teraz stworzyć relację, która utworzy takie 4 klasy abstrakcji?
Góra
Mężczyzna Offline
PostNapisane: 3 wrz 2012, o 19:49 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
Może łatwiej będzie, jeśli weźmiemy te same liczby, czyli klasami nieskończonymi będą zbiór liczb parzystych większych od 5 i zbiór liczb nieparzystych większych od 5. Definiujemy

xRy\iff 2|(x-y) \land (x-5{,}5)(y-5{,}5)>0.

To akurat da się zdefiniować zwięzłym wzorem, ale równie dobrze można zrobić dłuższą definicję. A uniwersalna definicja jest, że xRy wtedy i tylko wtedy gdy x należy do tej samej klasy abstrakcji co y.
Góra
Mężczyzna Offline
PostNapisane: 3 wrz 2012, o 22:05 
Użytkownik
Avatar użytkownika

Posty: 57
norwimaj napisał(a):
Może łatwiej będzie, jeśli weźmiemy te same liczby, czyli klasami nieskończonymi będą zbiór liczb parzystych większych od 5 i zbiór liczb nieparzystych większych od 5. Definiujemy

xRy\iff 2|(x-y) \land (x-5{,}5)(y-5{,}5)>0.

To akurat da się zdefiniować zwięzłym wzorem, ale równie dobrze można zrobić dłuższą definicję. A uniwersalna definicja jest, że xRy wtedy i tylko wtedy gdy x należy do tej samej klasy abstrakcji co y.


A jak będę chciał dorzucić kolejne klasy abstrakcji to mam już po prostu użyć spójnika "lub"?
Góra
Mężczyzna Offline
PostNapisane: 3 wrz 2012, o 22:31 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
Ogólnie jeśli mamy n klas abstrakcji: C_1,C_2,\ldots, C_n, to

xRy\iff (x\in C_1 \land y\in C_1)\lor(x\in C_2 \land y\in C_2)\lor\ldots\lor(x\in C_n \land y\in C_n).

W ten sposób możesz zrobić każdy taki przykład (przynajmniej jeśli jest skończona liczba klas abstrakcji).
Góra
Mężczyzna Offline
PostNapisane: 4 wrz 2012, o 08:00 
Użytkownik
Avatar użytkownika

Posty: 57
Bardzo dziękuję za pomoc :)
Góra
Kobieta Offline
PostNapisane: 4 wrz 2012, o 15:07 
Użytkownik

Posty: 56
Lokalizacja: Gdansk
Mam identyczne zadanie do zrobienia, z kombinatoryki, te zadanie nr 5. Według mnie powinno być w a)
{12 \choose 4}  \cdot {8 \choose 4} \cdot{ 4 \choose 4} = \frac{12!}{ 4^{3} } a w c), nie powinno być {12 \choose 3} \cdot {9 \choose 3} \cdot 1 ^{6}?
Góra
Mężczyzna Offline
PostNapisane: 4 wrz 2012, o 16:47 
Użytkownik
Avatar użytkownika

Posty: 57
aussie napisał(a):
Mam identyczne zadanie do zrobienia, z kombinatoryki, te zadanie nr 5. Według mnie powinno być w a)
{12 \choose 4}  \cdot {8 \choose 4} \cdot{ 4 \choose 4} = \frac{12!}{ 4^{3} } a w c), nie powinno być {12 \choose 3} \cdot {9 \choose 3} \cdot 1 ^{6}?


To samo zadanie, jeszcze z Gdańska - widzimy się za tydzień na poprawce u Piwaka? :D co do tego co napisałaś:
{12 \choose 4} = \frac{12!}{8! \cdot 4!} \\
{8 \choose 4} = \frac{8!}{4! \cdot 4!} \\
{4 \choose 4} = \frac{4!}{4! \cdot 0!}

Zatem po wymnożeniu dostajemy nie \frac{12!}{ 4^{3} }, a \frac{12!}{ (4!)^{3} }

Co do przykłądu c) - to, co napisałaś, jest równe temu co ja napisałem :P w sensie
{12 \choose 3} \cdot {9 \choose 3} = \frac{12!}{6! \cdot 3! \cdot 3!}
Góra
Kobieta Offline
PostNapisane: 4 wrz 2012, o 17:01 
Użytkownik

Posty: 56
Lokalizacja: Gdansk
Tak, na tą samą poprawkę się przygotowuję :D. Odnośnie zadań, to faktycznie mój błąd, wyniki się zgadzają ;)
Góra
Mężczyzna Offline
PostNapisane: 4 wrz 2012, o 17:06 
Użytkownik
Avatar użytkownika

Posty: 57
W takim razie powodzenia! ;) Oby to był nasz ostatni egzamin z dyskretnej :D
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 16 ]  Przejdź na stronę 1, 2  Następna strona


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Relacje - zadania - zadanie 5  Piateczka  0
 Na ile sposobów z talii kart - sprawdzenie  Lukassz  1
 Zapisz relację binarną w postaci tabelki  omen2  4
 zliczanie bijekcji  tukanik  1
 relacje - zadanie 15  zedd5  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl