Låtsastenta

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.