09 Tillukninger og induktivt definerte mengder

Question 1

lukket mengde

Answer 1

At en mengde er lukket (eng: closed) 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 (eng: closure) av M under disse operasjonene.

Question 2

tillukning 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 (eng: closure) av R med hensyn til denne egenskapen.

Hvis egenskapen det er snakk om er refleksivitet, symmetri eller transitivtet, kalles tillukningen henholdsvis den refleksive (eng: reflexive), symmetriske (eng: symmetric) eller transitive (eng: transitive) tillukningen av R.

Question 3

induktivt definert mengde

Answer 3

En induktivt definert mengde (eng: inductively defined set) er den minste mengden som inneholder en gitt mengde - kalt en basismengde (eng: base set / initial set) - og som er lukket under gitte opreasjoner. En mengde defineres induktivt i følgende tre steg:

• Basissteget (eng: base case / basis): å spesifisere en basismengde
• Induksjonssteget (eng: induction step): å spesifisere operasjonene
• Tillukningen (eng: closure): å ta den minste mengden som inneholder basismengden og som er lukket under operasjonene

Question 4

mengden av utsagnslogiske formler

Answer 4

Mengden av utsagnslogiske formler (eng: propositional formulas) 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 (eng: atomic formulas).
• 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

liste

Answer 5

Mengden av lister (eng: lists) 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 (eng: empty list) over A.
• Hvis x ∈ A og L er en liste over A, er x::L en liste over A

Notasjon:
1 :: (2, 3, 4) = (1, 2, 3, 4)

Question 6

binært tre

Answer 6

Mengden av inære trær (eng: binary trees) 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 (eng: empty binary tree) eller bare det tomme treet (eng: empty tree).
• 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 (eng: node) i det binære treet. Når et binært tre er på formen ((), x, ()), kalles x en bladnode eller en løvnode (eng: leaf node).

Question 7

alfabet, tegn, streng

Answer 7

Anta at A er en mengde av tegn. Mengden A kalles et alfabet (eng: alphabet). Mengden av strenger (eng: strings) over A er den minste mengden A* slik at:
- Λ ∈ A, hvor symbolet Λ står for den tomme strengen (eng: empty string) 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 (eng: language) over A er en delmengde av A*.

Question 8

konkatenering

Answer 8

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

Question 9

bitstreng

Answer 9

Mengden av bitstrenger (eng: bit strings) 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å bitstrenger.