1. Avgör vilka av följande påståenden som är sanna:
(a) Utsagan $(p\rightarrow q) \vee (q\rightarrow p)$ är en tautologi.
(b) $\{-1,2,0\} \subseteq \mathbb{Q}$.
(c) Funktionen $f:\mathbb{R} \to \mathbb{R}$ som definieras av $f(x) = e^{\cos x}$ är surjektiv.
(d) \[\sum_{k=1}^5 k = 120.\]
2. Låt $A = \{1,3,5\}$ och $B = \{4,5,6,7\}$. Bestäm antalet element i mängderna
$A\cup B$, $A\cap B$, $A\times B$ och $A\setminus B$.
3. Vi definierar två relationer på $\mathbb{Z}\times \mathbb{Z}$:
$(a,b) R (c,d)$ betyder att $a\leq c$ och $b\leq d$, och
$(a,b) S (c,d)$ betyder att $a\leq c$ eller $b\leq d$.
Är någon av $R$ och $S$ en partiell ordning?
4. Lucastalen är en talföljd som startar $1, 3, 4, 7, 11,\dots$, där varje tal är summan av de två föregående. Bevisa med induktion att största gemensamma delaren till två konsekutiva Lucastal är 1.
5. Ange alla lösningar i positiva heltal till ekvationen \[70x + 49y = 679.\]
6. Visa att ekvationen $2x^2 - 11y = 4$ saknar heltalslösningar, genom att visa att motsvarande kongruend modulo 11 saknar lösningar.
7. Hur många stryktipsrader finns det (varje omgång) som har 11 (av 13) rätt?
8. Vilken av graferna $K_4$ och $K_5$ har en Eulercykel?
Svar / kommentarer (Obs! Nedanstående är inte fullständiga lösningar och skulle inte ge full päng på tentan!):
1 (a) Sant, uttrycket blir sant oavsett sanningsvärdena hos $p$ och $q$. (b) Sant, talen $-1$, 2, och 0 är rationella. (c) Falskt, funktionen antar inte alla värden, bara dem i intervallet $[1/e,e]$. (d) Falskt, summan är $1+2+3+4+5= 15$, däremot är motsvarande produkt lika med 120.
2. Antalet element är 6, 1, 12, respektive 2.
3. Kontrollera reflexivitet, antisymmetri och transitivitet. Relationen $R$ är en partiell ordning, medan relationen $S$ varken är antisymmetrisk eller transitiv, till exempel gäller $(1,0)S(0,1)$ och $(0,1)S(1,0)$ trots att $(0,1)\neq (1,0)$.
4. Kom ihåg att ange vad som är induktionshypotesen, hur den används i induktionssteget, och kom ihåg att kontrollera basfallet!
På den här uppgiften får man göra en numrering själv. Till exempel kan man kalla Lucastalen för $L_0,L_1,\dots$, med $L_0=1$ och $L_1=3$. Man kan låta utsagan $p_n$ vara att $sgd(L_n, L_{n+1})=1$. Basfallet blir då fallet $n=0$, som säger att sgd(1,3)=1.
5. Största gemensamma delare till 70 och 49 är 7, och ekvationen är ekvivalent med
$10x+7y = 97$. En lösning är $x=9$, $y=1$, och den allmänna lösningen kan skrivas som $x= 9+7n$, $y=1-10n$. Men mängden av lösningar kan också parametriseras på andra sätt.
6. Det räcker att kontrollera att kongruensen $2x^2\equiv 4$ modulo 11 inte har någon lösning, genom att kontrollera ett värde på $x$ från varje kongruensklass, till exempel $x=0,\dots,10$.
7. Antalet sådana rader är $\binom{13}2 \cdot 4= 312$. Det finns $\binom{13}2 = 78$ sätt att välja två matcher där det blir fel, och $2\cdot 2=4$ sätt att ha fel på dessa två matcher.
8. $K_5$ har en Eulercykel (går att rita eller hänvisa till att den är sammanhängande och alla noder har jämn grad). $K_4$ har fyra noder av udda grad, och har därmed ingen Eulercykel.
Monday, March 16, 2015
Monday, March 2, 2015
Gamla tentor och bokkapitel
Det finns tre gamla tentor med lösningar på en gammal kurshemsida.
Det vi har pratat om och som man bör ha läst inför tentan är:
1.1-1.8 (om det blir problem här, gå vidare!)
2
3.1-3.8
4
5
6 (samt notation från kapitel 9, alltså sannolikheter)
7.1, 7.2, 7.4, 7.7.
Innehållsförteckning (kan vara bra för dem som har gamla boken).
Sunday, March 1, 2015
Lite om Dugga 2
Uppgift 6 är en standardtillämpning av Euklides algoritm. Se till att ni kan detta inför tentan!
Uppgift 7 har lett till en del frågor och funderingar. På föreläsningen gick jag igenom ett liknande exempel, som visade att ekvationen \[x^3 - 13y^2 = 2\] saknar heltalslösningar.
Tricket är att använda kongruensräkning. Om ekvationen hade någon lösning, så skulle även kongruensen \[ x^3 - 13y^2 \equiv 2 \quad (\text{mod $n$})\] ha en lösning, oavsett vilket $n$ vi väljer. En strategi för att bevisa att ekvationen saknar lösningar (eller för att hitta dem om det finns!) är att välja några värden på $n$ och se om ekvationen (alltså motsvarande kongruens) har någon lösning modulo $n$.
Det fiffiga med moduloräkning är att det bara finns ett ändligt antal kongruensklasser. Skulle vi till exempel undersöka den här ekvationen modulo 3, finns det bara 9 olika fall. Det finns 3 kongruensklasser, och var och en av $x$ och $y$ måste tillhöra någon av dem. Nu visar det sig att ekvationen har lösningar modulo 3, till exempel $x\equiv 0$ och $y\equiv 1$. Då kan vi inte dra någon slutsats. Bara för att ekvationen har lösningar modulo 3 behöver det inte finnas någon "riktig" lösning.
Om vi i stället väljer att titta på ekvationen modulo 13, händer något intressant. Eftersom termen $13y^2$ då blir kongruent med 0, spelar det ingen roll vad $y$ är, utan vi får ett villkor på bara $x$, nämligen \[x^3 \equiv 2 \quad (\text{mod $n$}).\] Det finns bara 13 fall att testa, så vi kan göra en tabell och gå igenom alla. Enklast blir det om vi testar $x$ i intervallet $-6\leq x \leq 6$, eftersom $(-x)^3 = -x^3$. Men 13 konsekutiva tal vilka som helst går bra, vi måste bara få med ett tal i varje kongruensklass, så att vi täcker in alla fall.
Vi har
$0^3\equiv 0$, $1^3 \equiv 1$, $2^3 \equiv 8$, $3^3\equiv 1$, $4^3\equiv 12$, $5^3\equiv 8$, $6^3\equiv 8$.
Samt $(-1)^3\equiv -1 \equiv 12$, $(-2)^3 \equiv -8 \equiv 5$, $(-3)^3\equiv -1\equiv 12$, $(-4)^3 \equiv -12 \equiv 1$, $(-5)^3\equiv -8\equiv 5$, och $(-6)^3\equiv -8\equiv 5$.
Då har vi testat alla kongruensklasser, och ser att oavsett värde på $x$, så måste $x^3$ vara kongruent med något av talen 0, 1, 5, 8, och 12. Det blir alltså aldrig kongruent med 2, och därför kan ekvationen inte ha några heltalslösningar.
Jag såg också att någon har postat den här uppgiften på pluggakuten. Jag har ju sagt att ni får diskutera uppgifterna (och det är i själva verket ett pedagogiskt "trick" från min sida), så det här är inget som är förbjudet. I det här fallet har någon svarat på ett bra sätt utan att skriva en hel lösning. Så då kan jag lika gärna länka härifrån så blir det rättvist och bra!
På uppgift 8 krävs inte mycket motivering, men något litet nyckelord vill jag att ni skriver som förklaring.
Uppgift 9 verkar vara ganska "straightforward".
Uppgift 10 handlar om grafer, uppspännande träd, och isomorfi. Antalet uppspännande träd i $K_4$ efterfrågas även i uppgift 7.14 i boken. Notera att villkoret att grafen ska vara sammanhängande (som det står i uppgift 7.14) inte är nödvändigt för själva definitionen av begreppet uppspännande träd. Det är bara det att det inte finns några om grafen inte är sammanhängande. Det villkoret behöver ni således inte fundera över.
Isomorfi är en ekvivalensrelation, och de uppspännande träden i $K_4$ kan alltså delas in i klasser, där träd i samma klass är isomorfa, och träd i olika klasser inte är isomorfa.
Uppgift 7 har lett till en del frågor och funderingar. På föreläsningen gick jag igenom ett liknande exempel, som visade att ekvationen \[x^3 - 13y^2 = 2\] saknar heltalslösningar.
Tricket är att använda kongruensräkning. Om ekvationen hade någon lösning, så skulle även kongruensen \[ x^3 - 13y^2 \equiv 2 \quad (\text{mod $n$})\] ha en lösning, oavsett vilket $n$ vi väljer. En strategi för att bevisa att ekvationen saknar lösningar (eller för att hitta dem om det finns!) är att välja några värden på $n$ och se om ekvationen (alltså motsvarande kongruens) har någon lösning modulo $n$.
Det fiffiga med moduloräkning är att det bara finns ett ändligt antal kongruensklasser. Skulle vi till exempel undersöka den här ekvationen modulo 3, finns det bara 9 olika fall. Det finns 3 kongruensklasser, och var och en av $x$ och $y$ måste tillhöra någon av dem. Nu visar det sig att ekvationen har lösningar modulo 3, till exempel $x\equiv 0$ och $y\equiv 1$. Då kan vi inte dra någon slutsats. Bara för att ekvationen har lösningar modulo 3 behöver det inte finnas någon "riktig" lösning.
Om vi i stället väljer att titta på ekvationen modulo 13, händer något intressant. Eftersom termen $13y^2$ då blir kongruent med 0, spelar det ingen roll vad $y$ är, utan vi får ett villkor på bara $x$, nämligen \[x^3 \equiv 2 \quad (\text{mod $n$}).\] Det finns bara 13 fall att testa, så vi kan göra en tabell och gå igenom alla. Enklast blir det om vi testar $x$ i intervallet $-6\leq x \leq 6$, eftersom $(-x)^3 = -x^3$. Men 13 konsekutiva tal vilka som helst går bra, vi måste bara få med ett tal i varje kongruensklass, så att vi täcker in alla fall.
Vi har
$0^3\equiv 0$, $1^3 \equiv 1$, $2^3 \equiv 8$, $3^3\equiv 1$, $4^3\equiv 12$, $5^3\equiv 8$, $6^3\equiv 8$.
Samt $(-1)^3\equiv -1 \equiv 12$, $(-2)^3 \equiv -8 \equiv 5$, $(-3)^3\equiv -1\equiv 12$, $(-4)^3 \equiv -12 \equiv 1$, $(-5)^3\equiv -8\equiv 5$, och $(-6)^3\equiv -8\equiv 5$.
Då har vi testat alla kongruensklasser, och ser att oavsett värde på $x$, så måste $x^3$ vara kongruent med något av talen 0, 1, 5, 8, och 12. Det blir alltså aldrig kongruent med 2, och därför kan ekvationen inte ha några heltalslösningar.
Jag såg också att någon har postat den här uppgiften på pluggakuten. Jag har ju sagt att ni får diskutera uppgifterna (och det är i själva verket ett pedagogiskt "trick" från min sida), så det här är inget som är förbjudet. I det här fallet har någon svarat på ett bra sätt utan att skriva en hel lösning. Så då kan jag lika gärna länka härifrån så blir det rättvist och bra!
På uppgift 8 krävs inte mycket motivering, men något litet nyckelord vill jag att ni skriver som förklaring.
Uppgift 9 verkar vara ganska "straightforward".
Uppgift 10 handlar om grafer, uppspännande träd, och isomorfi. Antalet uppspännande träd i $K_4$ efterfrågas även i uppgift 7.14 i boken. Notera att villkoret att grafen ska vara sammanhängande (som det står i uppgift 7.14) inte är nödvändigt för själva definitionen av begreppet uppspännande träd. Det är bara det att det inte finns några om grafen inte är sammanhängande. Det villkoret behöver ni således inte fundera över.
Isomorfi är en ekvivalensrelation, och de uppspännande träden i $K_4$ kan alltså delas in i klasser, där träd i samma klass är isomorfa, och träd i olika klasser inte är isomorfa.
Subscribe to:
Posts (Atom)