Nedenstående opgaver er ekstra frivillige opgaver til dem som er færdig med de regulære opgaver, men har tid og lyst til mere.
Ekstra Opgaver – Store Dag#
Ekstra Opgave 1: Der findes uendeligt mange primtal#
Et naturligt tal \(d\) siges at gå op i et andet naturligt \(n\) hvis \(n/d\) er et naturligt tal. Et primtal er et naturligt tal \(n\) større end \(1\) således at kun \(1\) og \(n\) går op i \(n\). Primtal er af teoretisk interesse, men anvendes for eksempel også for at opnå sikkert internetbanking.
Målet med opgave er at vise at der findes uendeligt mange primtal. I opgaven må bruges uden bevis at hvert heltal kan skrives som produkt af primtal.
Spørgsmål a#
Vis at for hvert naturligt tal \(n\) større end \(1\), der findes mindst ét primtal som går op i \(n\).
Hint
Antag at der findes naturlige tal \(n\) større end \(1\) som ingen primdivisorer har. I så fald findes der et mindste naturlige tal \(N\) større end \(1\) som ingen primdivisorer har. Vis at det fører til en modstrid.
Spørgsmål b#
Antag at der kun findes endeligt mange primtal. Vis at i så fald, der findes et naturligt \(N\) større end \(1\) således at intet primtal går op i det.
Hint
Euklid (omkring 300 BCE) havde følgende idé: hvis der kun er endeligt mange primtal, lad os sige \(p_1,\dots,p_\ell\), hvilke primtal kan i så fald gå op i tallet \(1+p_1\cdot \cdots \cdot p_\ell\)?
Spørgsmål c#
Konkludér fra delopgaver a og b at der findes uendeligt mange primtal.
Ekstra Opgave 2: Lidt om Boolsk algebra#
Når logiske operationer bruges i en computer, bruges bits \(0\) og \(1\) for sandhedsværdier: \(1\) bruges i stedet for \(T\) og \(0\) i stedet for \(F\). Det giver nogle andre muligheder for at beskrive logiske operationer og er relatered til en struktur som kaldes Boolsk algebra.
Spørgsmål a#
Den almindelige multiplikation kan bruges på tallene \(0\) og \(1\). Det giver følgende multiplikationstabel for bits, som vi nu opfatter som en sandhedstabel:
\(P\) |
\(Q\) |
\(P\cdot Q\) |
|---|---|---|
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
Hvilke logiske operation beskrives vha. multiplikation?
Svar
\(\wedge\)
Spørgsmål b#
Den addition \(\oplus\) af \(0\) og \(1\) som bits er defineret som følger: \(0\oplus 0=0\), \(0\oplus1=1\), \(1\oplus 0=1\) og \(1\oplus 1=0\). Det giver følgende tabel, som vi igen opfatter som en sandhedstabel:
\(P\) |
\(Q\) |
\(P\oplus Q\) |
|---|---|---|
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
Hvilke logiske operation beskrives vha. addition?
Hint
Kig lige på Opgave 2 fra ugeprogrammet igen.
Svar
xor (exclusive or)
Spørgsmål c#
Hvordan kan \(1 \oplus P\) fortolkes?
Svar
som \(\neg P\)
Spørgsmål d#
Hvad er sandhedstabellen af udtrykket \(P\cdot (1 \oplus Q)\)? Kan du også finde et udtryk som giver \(1\) hvis \(P=1\) og \(Q=1\), men ellers \(0\)?
Spørgsmål e#
Lad \(a,b,c,d \in \{0,1\}\) være bits. Find et udtryk \(X\) i \(P\) og \(Q\) som har sandhedstabel
\(P\) |
\(Q\) |
\(X\) |
|---|---|---|
1 |
1 |
a |
0 |
1 |
b |
1 |
0 |
c |
0 |
0 |
d |
Hint
To udtryk kan altid lægges sammen ved hjælp af \(\oplus\). Bemærk at man kan skrive \(P \oplus P =0\), fordi \(P \oplus P\) kun tager \(0\) som sandhedsværdi.
Hvordan kan man for eksempel beskrive \(\vee\) ved hjælp af addition og multiplikation af bits?
Svar
\(P \vee Q\) kan beskrives som \(P\cdot Q \oplus (1\oplus P)\cdot Q \oplus P\cdot(1 \oplus Q)=P \oplus Q \oplus P \cdot Q.\)