09 Tillukninger og induktivt definerte mengder

Question 1

9.1 Lukket mengde

Answer 1

At en mengde er lukket under en gitt operasjon, betyr at når vi utfører denne operasjonen på ett eller flere elementer i mengden, er vi garantert at resultatet er et element i den samme mengden. Hvis M er en mengde, kalles den minste mengden som inneholder M og som er lukket under en eller flere operasjoner, tillukningen av M under disse operasjonene.

Question 2

9.2 Tillukningen av en binær relasjon

Answer 2

Hvis R er en relasjon, kalles den minste relasjonen som inneholder R og som har en gitt egenskap, tillukningen av R med hensyn til denne egenskapen. Hvis egenskapen det er snakk om er refleksivitet, symmetri eller transitivitet, kalles tillukningen henholsvis den refleksive, symmetriske eller transitive tillukningen av R.

Question 3

9.3 Induktivt definert mengde

Answer 3

En induktivt definert mengde er den minste mengden som inneholder en gitt mengde - kalt en basismengde - og som er lukket under gitte operasjoner. En mengde defineres induktivt i følgende tre steg:

• Basissteget: å spesifisere en basismengde.
• Induksjonssteget: å spesifisere operasjonene.
• Tillukningen: å ta den minste mengden som inneholder basismengden og som er lukket under operasjonene.

Question 4

9.4 Utsagnslogisk formel

Answer 4

Mengden av utsagnslogiske formler er den minste mengden X slik at følgende holder:

• Enhver utsagnsvariabel er med i X. Disse utgjør basismengden og kalles atomøre formler.
• Hvis F er med i X, er ¬F med i X.
• Hvis F og G er med i X, så er (F ∧ G), (F ∨ G) og (F → G) med i X.

Question 5

9.5 Liste

Answer 5

Mengden av lister over en mengde A er induktivt definert som den minste mengden slik at følgende holder:

• () er en liste over A. Dette er den tomme listen over A.
• Hvis x ∈ A og L er en liste over A, er x::L en liste over A.

Question 6

9.6 Binært tre

Answer 6

Mengden av binære trær over en mengde A er den minste mengden slik at følgende holder:

• () er et binært tre over A. Dette kalles det tomme binære treet eller bare det tomme treet.
• Hvis x ∈ A, og V og H er binære trær over A, er (V, x, H) et binært tre over A. Elementet x kalles en node i det binære treet. Når et binært tre er på formen ((), x, ()), kalles x en bladnode eller en løvnode.

Question 7

9.7 Alfabet, tegn, streng

Answer 7

Anta at A er en mengde av tegn. Mengden A kalles et alfabet. Mengden av strenger over A er den minste mengden A* slik at:

• Λ ∈ A*, hvor symbolet Λ står for den tomme strengen og
• hvis s ∈ A* og x ∈ A, er sx ∈ A*, hvor sx står for resultatet av å slå sammen s og x. Vi skriver s i stedet for Λs.

Et språk over A er en delmengde av A*.

Question 8

9.8 Konkatenering

Answer 8

Operasjonen som består av å slå to strenger s og t sammen til én, st, kalles konkatenering. Skrivemåten sⁿ brukes som en forkortelse for strengen s gjentatt n ganger etter hverandre; for eksempel er a³b³ det samme som aaabbb. Vi antar at s⁰ = Λ.

Question 9

9.9 Bitstreng

Answer 9

Mengden av bitstrenger er induktivt definert som den minste mengden som er slik at 0 og 1 er bitstrenger, og hvis b er en bitstreng, er b0 og b1 også bitgstrenger.