Obligatorisk oppgavesett nr. 1, MAT1030, våren 2005

Besvarelsene, tydelig merket med “Oblig 1, MAT1030, våren 2005” og ditt fullstendige navn, må leveres innen fredag 25. februar 2005 klokken 14.30 i ekspedisjonen for Matematisk institutt, i 7. etasje i N. H. Abels hus.

Det er tillatt å bruke alle hjelpemidler. Det er lov å samarbeide, men studenten skal selv ha skrevet den besvarelsen som leveres inn, og den skal gjenspeile studentens forståelse av stoffet. Studenten kan bli bedt om å redegjøre muntlig for innholdet i den obligatoriske oppgaven.

Oppgave 1

Studer følgende pseudokode for et program. Anta at input til programmet er et naturlig tall n som er større enn eller lik 2.

1. Input n

2. d ← 2

3. faktor ← 0

4. While (d < n) and (faktor = 0) do

4.1. If (n mod d = 0) then

4.1.1. faktor ← 1

4.2. d ← d+1

5. If (faktor = 0) then

5.1. Output “X”

else

5.2. Output “Y”

(a) Forklar hvorfor dette programmet alltid vil stoppe etter endelig mange trinn, slik at pseudokoden definerer en algoritme.

(b) Hvilken av følgende to meldinger passer som erstatning for “X”, og hvilken passer som erstatning for “Y”? Begrunn svaret.

P: “Tallet er et primtall.”

Q: “Tallet er ikke et primtall.”

Oppgave 2

(a) Skriv desimaltallet 2005 binært. Vis utregningen.

(b) Skriv så 2005 oktalt og heksadesimalt.

Oppgave 3

La p og q være utsagn. Vis at det logiske uttrykket

(p → q) ∨ (q → p)

(dvs. at p impliserer q, eller q impliserer p) er en tautologi på følgende to måter:

(a) ved å konstruere en sannhetstabell, og

(b) ved å forenkle uttrykket ved hjelp av de logiske lovene i Grossmann, tabell 4.12.

Oppgave 4

La n være et helt tall slik at n2 er delelig med 3. Bevis at n er delelig med 3.

(Skriv ut et argument som i avsnitt 4.8, i fullstendige setninger. Ikke bruk entydighet av primfaktorisering fra kapittel 12.)

Oppgavesettet er nå komplett.

John Rognes, 7. februar 2005

2005-01-25T10:37:59