---
jupytext:
  formats: md:myst
  text_representation:
    extension: .md
    format_name: myst
    format_version: '0.8'
    jupytext_version: 1.4.1+dev
kernelspec:
  display_name: Python 3
  language: python
  name: python3
---

(section:uge1S)=

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}
:class: dropdown
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}
:class: dropdown
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?

```{admonition} Svar
:class: dropdown
$\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}
:class: dropdown
Kig lige på Opgave 2 fra ugeprogrammet igen.
```

```{admonition} Svar
:class: dropdown
xor (exclusive or)
```

### Spørgsmål c

+++

Hvordan kan $1 \oplus P$ fortolkes?

```{admonition} Svar
:class: dropdown
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}
:class: dropdown
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? 

```{admonition} Svar
:class: dropdown
$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.$
%$P \Rightarrow Q$ kan beskrives som $P\cdot Q \oplus (1\oplus P)\cdot Q \oplus (1 \oplus P)\cdot(1 \oplus Q)=1 \oplus P \oplus P \cdot Q.%$
```

---