Zbiory, relacje, zliczanie, kwantyfikatory - sprawdzenie

Marmite · Post autor: **Marmite** » 30 sie 2012, o 22:42

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

1. Mamy:
$\displaystyle{ 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:
$\displaystyle{ 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:
$\displaystyle{ L\left(x,y\right)}$ - $\displaystyle{ y}$ jest lubiany przez $\displaystyle{ x}$
$\displaystyle{ M\left(x\right)}$ - $\displaystyle{ x}$ lubi matematykę
$\displaystyle{ 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) $\displaystyle{ \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) $\displaystyle{ \forall s \in U \left(M\left(s\right) \rightarrow \forall x \in U \left(L\left(x,s\right)\right)\right)}$
c) $\displaystyle{ \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 $\displaystyle{ \left\{ 1,2,3 \right\}}$
b) Porządku liniowego w zbiorze $\displaystyle{ \left\{ 1,2,3,4,5,6 \right\}}$
c) Typu równoważności w zbiorze $\displaystyle{ \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ś:
$\displaystyle{ 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 $\displaystyle{ \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) $\displaystyle{ \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) $\displaystyle{ 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ź:
$\displaystyle{ {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:
$\displaystyle{ \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ą )

norwimaj · Post autor: **norwimaj** » 31 sie 2012, o 20:20

2.

Marmite pisze: a) $\displaystyle{ \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 pisze: a) 6

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

Marmite pisze: b) 30?

Za mało.

Marmite pisze: (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 pisze: 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

Marmite · Post autor: **Marmite** » 31 sie 2012, o 22:25

norwimaj pisze:2.
Marmite pisze: a) $\displaystyle{ \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ć:
$\displaystyle{ \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:

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 $\displaystyle{ \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 $\displaystyle{ t,s}$ ze zbioru $\displaystyle{ S}$ zachodzi albo $\displaystyle{ s \le t}$, albo $\displaystyle{ 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 $\displaystyle{ \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 $\displaystyle{ a^{2} + 3a = 100}$"?

norwimaj · Post autor: **norwimaj** » 1 wrz 2012, o 13:35

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 $\displaystyle{ \le}$. Ta relacja ma $\displaystyle{ 3}$ elementy, to znaczy są trzy pary elementów zbioru $\displaystyle{ \{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 $\displaystyle{ c)}$, twierdząc że $\displaystyle{ \le}$ jest relacją równoważności. Nie jest to relacja symetryczna, bo $\displaystyle{ 2\le3}$, ale nieprawda że $\displaystyle{ 3\le2}$.

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

Marmite · Post autor: **Marmite** » 3 wrz 2012, o 00:24

norwimaj pisze: 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.

W czwartym zapominasz o tym że rodzina klas abstrakcji stanowi podział uniwersum. W Twoim przykładzie liczba $\displaystyle{ 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?

norwimaj · Post autor: **norwimaj** » 3 wrz 2012, o 14:44

Na przykład jako klasy nieskończone możesz wziąć zbiór liczb parzystych większych od $\displaystyle{ 5}$ i zbiór liczb nieparzystych większych od $\displaystyle{ 13}$. Jeszcze musisz zbiór pozostałych liczb podzielić na dwa niepuste zbiory.

Marmite pisze: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:

$\displaystyle{ \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}}$

Marmite · Post autor: **Marmite** » 3 wrz 2012, o 15:31

norwimaj pisze:Na przykład jako klasy nieskończone możesz wziąć zbiór liczb parzystych większych od $\displaystyle{ 5}$ i zbiór liczb nieparzystych większych od $\displaystyle{ 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ż
$\displaystyle{ 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?

norwimaj · Post autor: **norwimaj** » 3 wrz 2012, o 19:49

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 $\displaystyle{ 5}$ i zbiór liczb nieparzystych większych od $\displaystyle{ 5}$. Definiujemy

$\displaystyle{ 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 $\displaystyle{ xRy}$ wtedy i tylko wtedy gdy $\displaystyle{ x}$ należy do tej samej klasy abstrakcji co $\displaystyle{ y}$.

Marmite · Post autor: **Marmite** » 3 wrz 2012, o 22:05

norwimaj pisze: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 $\displaystyle{ 5}$ i zbiór liczb nieparzystych większych od $\displaystyle{ 5}$. Definiujemy

$\displaystyle{ 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 $\displaystyle{ xRy}$ wtedy i tylko wtedy gdy $\displaystyle{ x}$ należy do tej samej klasy abstrakcji co $\displaystyle{ y}$.

A jak będę chciał dorzucić kolejne klasy abstrakcji to mam już po prostu użyć spójnika "lub"?

norwimaj · Post autor: **norwimaj** » 3 wrz 2012, o 22:31

Ogólnie jeśli mamy $\displaystyle{ n}$ klas abstrakcji: $\displaystyle{ C_1,C_2,\ldots, C_n}$, to

$\displaystyle{ 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).

Marmite · Post autor: **Marmite** » 4 wrz 2012, o 08:00

Bardzo dziękuję za pomoc

aussie · Post autor: **aussie** » 4 wrz 2012, o 15:07

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

Marmite · Post autor: **Marmite** » 4 wrz 2012, o 16:47

aussie pisze:Mam identyczne zadanie do zrobienia, z kombinatoryki, te zadanie nr 5. Według mnie powinno być w a)
$\displaystyle{ {12 \choose 4} \cdot {8 \choose 4} \cdot{ 4 \choose 4} = \frac{12!}{ 4^{3} }}$ a w c), nie powinno być $\displaystyle{ {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? co do tego co napisałaś:
$\displaystyle{ {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 $\displaystyle{ \frac{12!}{ 4^{3} }}$, a $\displaystyle{ \frac{12!}{ (4!)^{3} }}$

Co do przykłądu c) - to, co napisałaś, jest równe temu co ja napisałem w sensie
$\displaystyle{ {12 \choose 3} \cdot {9 \choose 3} = \frac{12!}{6! \cdot 3! \cdot 3!}}$

aussie · Post autor: **aussie** » 4 wrz 2012, o 17:01

Tak, na tą samą poprawkę się przygotowuję . Odnośnie zadań, to faktycznie mój błąd, wyniki się zgadzają

Marmite · Post autor: **Marmite** » 4 wrz 2012, o 17:06

W takim razie powodzenia! Oby to był nasz ostatni egzamin z dyskretnej