Chociaż jedno
1. Rozważmy poniższe rozumowanie:
Jeśli dostanę się na wymarzony kierunek i będę porządnie się uczył to go ukończę. Jeśli ukończę wymarzony kierunek to będę miał ciekawą pracę. Nie będę miał ciekawej pracy. Zatem albo nie dostanę się na wymarzony kierunek albo nie będę porządnie się uczył
(a) Zapisać je za pomocą symboliki logicznej i zbadać jego poprawność przy pomocy metody zero-jedynkowej
(b) Jeśli rozumowanie jest poprawne, to napisać dowód formalny.
2. Na zbiorze \(\displaystyle{ \{5,6,7,8\}}\) określono relację \(\displaystyle{ R}\) warunkiem: \(\displaystyle{ xRy \Leftrightarrow min(x,6)=y}\).
(a) Wypisać wszystkie pary należące do relacji \(\displaystyle{ R}\)
(b) Zbadać, czy \(\displaystyle{ R}\) jest zwrotna, symetryczna, przechodnia.
3. Rozważmy funkcję boole'owską \(\displaystyle{ f(x,y,z)}\) która przyjmuje wartość 1 wtedy i tylko wtedy, gdy dokładnie jedna z liczb \(\displaystyle{ x, y, z}\) ma wartość 1.
(a) Narysować tabelkę funkcji \(\displaystyle{ f}\).
(b) Przedstawić \(\displaystyle{ f(x,y,z)}\)przy pomocy \(\displaystyle{ \vee , \wedge , \neg}\)
(c) Naszkicować sieć boole'owską realizującą tę funkcję.
4. Załóżmy,że relacje \(\displaystyle{ R}\) i \(\displaystyle{ S}\) na tym samym zbiorze są symetryczne. Czy relacja \(\displaystyle{ R\cup S}\) musi być symetryczna. Wykazać i podać kontrprzykład.
5. Wykazać, że czterocyfrowa liczba o cyfrach \(\displaystyle{ a,b,c,d}\) jest podzielna przez 9 wtedy i tylko wtedy, gdy suma jej cyfr jest podzielna przez 9.
6. Rozwiązać równanie kongruencyjne \(\displaystyle{ 39x=1(mod1286)}\).
7. W zbiorze liczb całkowitych \(\displaystyle{ Z}\) określamy relację \(\displaystyle{ R}\) warunkiem\(\displaystyle{ mRn \Leftrightarrow m^{2}= n^{2}}\)
(a) Sprawdzić, że relacja \(\displaystyle{ R}\) jest relacją równoważności.
(b) Opisać klasy równoważności tej relacji. Ile ich jest?
8. Wyznaczyć: \(\displaystyle{ 2^{3948} \ i \ 2^{3941} mod 3942}\),wiedząc, że 3943 jest liczbą pierwszą.
Proszę o pomoc w rozwiązaniu tych zadań
Pozdrawiam!
Egzamin z matematyki dyskretnej - relacje, kongruencja
-
- Użytkownik
- Posty: 9
- Rejestracja: 25 paź 2009, o 10:38
- Płeć: Mężczyzna
- Lokalizacja: Jasło
- Podziękował: 1 raz
Egzamin z matematyki dyskretnej - relacje, kongruencja
Ostatnio zmieniony 12 wrz 2010, o 19:33 przez Crizz, łącznie zmieniany 1 raz.
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania.
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania.
- Konikov
- Użytkownik
- Posty: 497
- Rejestracja: 13 mar 2008, o 18:56
- Płeć: Mężczyzna
- Lokalizacja: z całki tego świata
- Podziękował: 66 razy
- Pomógł: 44 razy
Egzamin z matematyki dyskretnej - relacje, kongruencja
BTW. pierwsza połowa zadań i siódme są z działu logika ;]
1.
w - wymarzony kierunek
p - porządna nauka
u - ukończenie
c - ciekawa praca
Pierwsze zdanie:
\(\displaystyle{ w \wedge p \Rightarrow u}\)
dalej:
\(\displaystyle{ (w \wedge p \Rightarrow u) \Rightarrow c}\)
Jeśli się nie mylę (dawno robiłem takie zadania), a logicznie tak to wychodzi, to można pominąć etap "ukończenie", a zaimplikować od razu ciekawą pracę. Wtedy bezpośrednio wychodzi to, że musisz zawieść w \(\displaystyle{ w}\) lub \(\displaystyle{ p}\), by nie dostać pracy, a całe równanie będzie spełnione. Tak działa implikacja. Zauważ, że nie zakładasz, że do porządnej nauki nie jest wymagany wymarzony kierunek.
2.
(a) na chama
(b) z definicji...
3.
(a) powinieneś dać radę ;]
(b) \(\displaystyle{ f(x,y,z) = x\ XOR\ y\ XOR\ z}\), czyli: \(\displaystyle{ (x \wedge \neg y \wedge \neg z) \vee ( \neg x \wedge y \wedge \neg z) \vee ( \neg x \wedge \neg y \wedge z)}\)
(c) Otrzymujesz bezpośrednio z powyższego wzoru.
4.
Jeśli dobrze rozumiem (pomijając to, że zdanie: "Wykazać i podać kontrprzykład." jest sprzeczne ;]), pamiętając o tym, że relacja to zbiór par, możemy dowieść nie wprost.
Załóżmy, że istnieją takie relacje, które są symetryczne, a ich suma nie jest. Skoro ta suma nie jest, to weźmy jedną z par \(\displaystyle{ p = <x, y> \in R \cup S}\), t.że \(\displaystyle{ <y,x>\notin R \cup S}\) (z założeń musi taka istnieć, inaczej suma byłaby symetryczna lub zbiorem pustym). Mamy \(\displaystyle{ p=<x, y>}\), które musi pochodzić od \(\displaystyle{ R}\) lub \(\displaystyle{ S}\) (lub obu). Załóżmy (bez straty ogólności), że pochodzi od \(\displaystyle{ S}\). Ale \(\displaystyle{ S}\) jest relacją symetryczną, więc posiada w sobie także \(\displaystyle{ <y,x>}\), które występuje także w sumie: \(\displaystyle{ R \cup S}\) - sprzeczność!
5.
Wiki: ... 87_przez_9
6.
Faktoryzujemy i dostajemy:
\(\displaystyle{ \begin{cases} 39x \equiv 1 (mod\ 2) \\ 39x \equiv 1 (mod\ 643) \end{cases}}\)
Pierwsze równanie daje nam, że x musi być nieparzysty (parzysta*nieparzysta = parzysta).
7.
(a) Jest. To wynika z tego, że "=" jest relacją równoważności, a na obie strony podziałano tą samą funkcją.
(b) Zauważ, że:
Gdyby jednak było \(\displaystyle{ mod\ 3943}\), to z MTF się robi, sprowadzając pierwsze do bardzo małej potęgi, a drugie do ujemnej.
Czy 6. i 8. są poprawnie przepisane?
1.
w - wymarzony kierunek
p - porządna nauka
u - ukończenie
c - ciekawa praca
Pierwsze zdanie:
\(\displaystyle{ w \wedge p \Rightarrow u}\)
dalej:
\(\displaystyle{ (w \wedge p \Rightarrow u) \Rightarrow c}\)
Jeśli się nie mylę (dawno robiłem takie zadania), a logicznie tak to wychodzi, to można pominąć etap "ukończenie", a zaimplikować od razu ciekawą pracę. Wtedy bezpośrednio wychodzi to, że musisz zawieść w \(\displaystyle{ w}\) lub \(\displaystyle{ p}\), by nie dostać pracy, a całe równanie będzie spełnione. Tak działa implikacja. Zauważ, że nie zakładasz, że do porządnej nauki nie jest wymagany wymarzony kierunek.
2.
(a) na chama
(b) z definicji...
3.
(a) powinieneś dać radę ;]
(b) \(\displaystyle{ f(x,y,z) = x\ XOR\ y\ XOR\ z}\), czyli: \(\displaystyle{ (x \wedge \neg y \wedge \neg z) \vee ( \neg x \wedge y \wedge \neg z) \vee ( \neg x \wedge \neg y \wedge z)}\)
(c) Otrzymujesz bezpośrednio z powyższego wzoru.
4.
Jeśli dobrze rozumiem (pomijając to, że zdanie: "Wykazać i podać kontrprzykład." jest sprzeczne ;]), pamiętając o tym, że relacja to zbiór par, możemy dowieść nie wprost.
Załóżmy, że istnieją takie relacje, które są symetryczne, a ich suma nie jest. Skoro ta suma nie jest, to weźmy jedną z par \(\displaystyle{ p = <x, y> \in R \cup S}\), t.że \(\displaystyle{ <y,x>\notin R \cup S}\) (z założeń musi taka istnieć, inaczej suma byłaby symetryczna lub zbiorem pustym). Mamy \(\displaystyle{ p=<x, y>}\), które musi pochodzić od \(\displaystyle{ R}\) lub \(\displaystyle{ S}\) (lub obu). Załóżmy (bez straty ogólności), że pochodzi od \(\displaystyle{ S}\). Ale \(\displaystyle{ S}\) jest relacją symetryczną, więc posiada w sobie także \(\displaystyle{ <y,x>}\), które występuje także w sumie: \(\displaystyle{ R \cup S}\) - sprzeczność!
5.
Wiki: ... 87_przez_9
6.
Faktoryzujemy i dostajemy:
\(\displaystyle{ \begin{cases} 39x \equiv 1 (mod\ 2) \\ 39x \equiv 1 (mod\ 643) \end{cases}}\)
Pierwsze równanie daje nam, że x musi być nieparzysty (parzysta*nieparzysta = parzysta).
7.
(a) Jest. To wynika z tego, że "=" jest relacją równoważności, a na obie strony podziałano tą samą funkcją.
(b) Zauważ, że:
- Działamy na całkowitych
- W tej samej klasie abstrakcji są pary: <n, m>, <-n, m>, <n, -m>, <-n, -m>.
Gdyby jednak było \(\displaystyle{ mod\ 3943}\), to z MTF się robi, sprowadzając pierwsze do bardzo małej potęgi, a drugie do ujemnej.
Czy 6. i 8. są poprawnie przepisane?
-
- Użytkownik
- Posty: 9
- Rejestracja: 25 paź 2009, o 10:38
- Płeć: Mężczyzna
- Lokalizacja: Jasło
- Podziękował: 1 raz
Egzamin z matematyki dyskretnej - relacje, kongruencja
dzięki za pomoc, 6 i 8(zrobilem tak jak napisales) sa poprawnie przepisane i poradzilem sobie z nimi. Jak będę miał czas to wrzuce później rozwiązania bo narazie ucze się na ustny z dyskretnej
Pozdrawiam
Pozdrawiam