abdefghiklmnoprstuvå
abelsk(eng: abelian) 20
• gruppe

En abelsk gruppe er en kommutativ gruppe. Se gruppe.

aksepterende(eng: final / accepting) 23
• tilstand

En delmengde av tilstandene i en endelig tilstandsmaskin.

alfabet(eng: alphabet) 23

En mengde av tegn som brukes til å definere strenger i formelle språk.

algebraisk(eng: algebraic) 20
• struktur

En mengde sammen med en eller flere operasjoner på denne mengden.

antakelse(eng: assumption) 0 2 3 4 5 24
•, • i naturlig deduksjon

Et utsagn som tas for å være sant, og som er utgangspunktet for resonnering. I naturlig deduksjon er en antakelse en formel øverst i en gren i en utledning. Denne kan være åpen eller lukket, og reglene avgjør når antakelser kan lukkes.

anti-symmetrisk(eng: anti-symmetric) 6
• relasjon

En binær relasjon er anti-symmetrisk dersom det er slik at hvis $xRy$ og $yRx$, så $x=y$, for alle $x$ og $y$.

aritet(eng: arity) 13
• til funksjonssymbol, • til relasjonssymbol

Egenskap ved funksjons- og relasjonssymbol som forteller hvor mange termer som trengs for å lage henholdsvis termer og atomære formler.

assosiativ(eng: associative) 2 3 20
• operasjon, • lov, venstre•, høyre•

En binær operasjon $\ast $ på en mengde $S$ er assosiativ hvis det for alle $x,y,z\in S$ er slik at $x\ast (y\ast z)=(x\ast y)\ast z$. I utsagnslogikk har vi assosiative lover som er ekvivalenser på formen $A\land(B\land C)\Eqv(A\land B)\land C$. Det at $\bullet$ er venstre-assosiativ betyr at $P\bullet Q\bullet R$ står for $((P\bullet Q)\bullet R)$ og ikke $(P\bullet(Q\bullet R))$, og tilsvarende for høyre-assosiativ.

asyklisk(eng: acyclic) 22
• graf

En graf uten sykler kalles asyklisk.

asymmetrisk(eng: asymmetric) 6
• relasjon

En binær relasjon er asymmetrisk dersom det er slik at hvis $xRy$, så er ikke $yRx$, for alle $x$.

atomær(eng: atomic) 2 13
• utsagn, • formel

Et atomært utsagn er et utsagn som ikke blir analysert i sin interne struktur. En atomær formel er (i utsagnslogikk) en utsagnsvariabel eller (i førsteordens logikk) på formen $R(\tn)$ hvor $\tn$ er termer.

basismengde(eng: base set / initial set) 9 10 11 12

Utgangspunktet for å definere en induktivt definert mengde.

basissteg(eng: base case / basis) 9 10 11 12

Det første steget i definisjonen av en induktivt definert mengde, en rekursiv funksjon eller i et bevis ved induksjon. Også kalt basistilfellet.

bevis(eng: proof) 5 24
•, • i naturlig deduksjon

Et bevis er et resonnement som gjør at vi blir overbevist om at en påstand er sann under visse antakelser. I naturlig deduksjon er et bevis en utledning hvor alle antakelser er lukkede.

bevisbar(eng: provable) 24
• formel

Det finnes et bevis for formelen.

bevis ved tilfeller / uttømmelse(eng: proof by cases / exhaustion) 5

En bevismetode hvor hvert enkelt tilfelle blir bevist hver for seg.

bijektiv(eng: bijective) 7
• funksjon

En funksjon som er injektiv og surjektiv, er bijektiv. Betyr det samme som en en-til-en korrespondanse.

bildemengde(eng: range) 7
• til en funksjon

Bildet av hele $A$ under $f$, $f[A]$, kalles bildemengden til $f$.

bildet(eng: image) 7
• av en mengde under en funksjon

Mengden $\set{f(x)\mid x\in X}$ kalles bildet av $X$ under $f$, og skrives $f[X]$.

binomialkoeffisient(eng: binomial coefficient) 18

Tallene på formen $\binom{n}{k}=\frac{n!}{(n-k)!k!}$ («$n$ velg $k$»).

binær(eng: binary) 6 7 9
• relasjon, • operasjon, • tre
bipartitt(eng: bipartite) 22

Se todelt.

bitstreng(eng: bit string) 9

Induktivt definert som den minste mengden som inneholder $\str{0}$ og $\str{1}$, og som er lukket under det å legge til $\str{0}$ eller $\str{1}$ lengst til høyre.

bladnode(eng: leaf node) 9

Se node.

brøktall(eng: rational number / fraction) 1

Tall som kan skrives på formen $\frac{m}{n}$, hvor $m$ og $n$ er heltall og $n$ ikke er lik $0$.

bundet(eng: bound) 13
• variabel

Se skop.

definisjonsområde(eng: domain) 7
• til funksjon

Mengden som gir argumentene til en funksjon.

delmengde(eng: subset) 1
• av mengde

En mengde $A$ er en delmengde av en mengde $B$ hvis alle elementer i $A$ også er elementer i $B$.

direkte bevis(eng: direct proof) 5

Et bevis for en påstand på formen «hvis $A$, $B$», hvor man på en direkte måte viser hvordan $A$ leder til $B$.

disjunksjon(eng: disjunction) 2

En formel på formen $(F\lor G)$.

disjunkt(eng: disjunct) 2
• i disjunksjon

I en disjunksjon $(F\lor G)$ kalles $F$ og $G$ for disjunktene.

disjunkt(eng: disjoint) 13 17 6
• mengde

Mengder som ikke har noen elementer til felles.

distributiv(eng: distributive) 3
• lov

Ekvivalens mellom formler som forteller hvordan konjunksjon og disjunksjon oppfører seg i forhold til hverandre, for eksempel $\textcolor{okblue}{A~\land~}(B\lor C)\Eqv(\textcolor{okblue}{A~\land~}B)\lor(\textcolor{okblue}{A~\land~}C)$

domene(eng: domain) 15
• til en modell

Se modell.

eksistens(eng: existential) 5
•bevis, •kvantor, •påstand

En eksistenspåstand er en påstand som sier at noe eksisterer. Et eksistensbevis er det samme som å finne et objekt som gjør påstanden sann. Se kvantor.

ekvivalens(eng: equivalence) 3 4 6 16 17
logisk •, •relasjon, •klasse

To formler logisk ekvivalente hvis de alltid har samme sannhetsverdi. En binær relasjon er en ekvivalensrelasjon hvis den er refleksiv, symmetrisk og transitiv. En ekvivalensklasse er en mengde av alle elementer som er relaterte til hverandre via en ekvivalensrelasjon.

element(eng: element) 1
• i en mengde

Objektene i en mengde kalles elementer.

en-til-en(eng: one-to-one) 7
• funksjon
enkel(eng: simple) 21
• graf

En graf uten løkker eller parallelle kanter.

etterfølgerfunksjon(eng: successor function) 7

Funksjonen $s:\bbN\to\bbN$ som er slik at $s(x)=x+1$.

euler(eng: Euler) 22
•vei, •krets, •sk

En eulervei er en vandring som inneholder hver kant fra en graf nøyaktig én gang. En eulerkrets er en eulervei hvor den første og den siste noden sammenfaller. En graf er eulersk hvis den har en eulerkrets.

fakultetsfunksjonen(eng: factorial function) 10 18

Funksjonen $n!=1\cdot2\cdot3\cdots n$.

falsifiserbar(eng: falsifiable) 4 15
• formel, • mengde

En formel, i utsagnslogikk eller førsteordens logikk, som kan gjøres usann. En mengde formler er falsifiserbar hvis det finnes en valuasjon eller modell som gjør alle formlene usanne. Motsatt av gyldig.

Fibonacci-tall(eng: Fibonacci number) 10

Tallrekken hvor hvert tall er summen av de to foregående: $0$, $1$, $1$, $2$, $3$, $5$, $8$, $13$, $21$ etc.

forfining(eng: refinement) 17
• av partisjon

Hvis $X$ og $Y$ er partisjoner og ethvert element i $X$ er en delmengde av et element i $Y$, kalles $X$ en forfining av $Y$.

formel(eng: formula) 2 13
utsagnslogisk •, førsteordens •

En formel er et syntaktisk objekt, i utsagnslogikk og førsteordens logikk, som representerer et utsagn. Mengden av formler er induktivt definert, både i utsagnslogikk og førsteordens logikk.

formell(eng: formal) 23
• språk, • grammatikk
formodning(eng: conjecture) 5

Påstander som vi tror er sanne, men som vi ikke har funnet bevis for.

fri(eng: free) 14
• variabel

Se skop.

funksjon(eng: function) 7 10 19

En funksjon fra $A$ til $B$ er en binær relasjon $f$ fra $A$ til $B$ slik at for enhver $x\in A$, er det nøyaktig ett element $y\in B$ slik at $\tuple{x,y}\in f$.

funksjonssymbol(eng: function symbol) 13

En del av et førsteordens språk. Angis i en signatur.

førsteordens(eng: first-order) 13 14 15 16
• logikk, • språk, • term, • formel, • modell
grad(eng: degree) 21
• til en node

Antall kanter som ligger inntil noden.

graf(eng: graph) 21 22

En graf $G$ består av en endelig, ikke-tom mengde $V$ av noder og en mengde $E$ av kanter.

grammatikk(eng: grammar) 23
•, regulær •

En formell grammatikk er et sett med regler som beskriver et språk; dette språket er mengden av strenger som kan utledes fra startsymbolet, og som kun inneholder terminalsymboler.

gruppe(eng: group) 20

En algebraisk struktur $\tuple{G,\bullet}$, som er slik at $\bullet$ er assosiativ, har et identitetselent og alle elementer har en invers.

gyldig(eng: valid) 4 5 15
• formel, • argument, • resonnement

En gyldig formel er en formel som er sann for alle valuasjoner/modeller. Et gyldig argument/resonnement er et hvor konklusjonen er en logisk konsekvens av premissene.

hamilton(eng: Hamilton) 22
•sti, •sykel, •sk

En hamiltonsti er en sti som går over alle noder nøyaktig én gang. En hamiltionsykel er en sykel som inneholder hver node nøyaktig én gang. En graf er hamiltonsk hvis den har en hamiltonsykel.

Hasse-diagram(eng: Hasse diagram) 17

En visualisering av en partiell ordning.

heltall(eng: integer) 1

Mengden $\bbZ$ av tallene $\ldots,-3,-2,-1,0,1,2,3,\ldots$.

hovedkonnektiv(eng: principal connective) 2

Det «ytterste» konnektivet til en formel.

håndhilselemmaet(eng: handshaking lemma) 21

Det er alltid et partall antall noder av odde grad i en graf.

høyde(eng: height) 10

Antall noder i den lengste grenen i et binært tre. Vanligvis rekursivt definert.

høyereordens(eng: higher-order) 7
• funksjon

Funksjoner som tar funksjoner som argumenter.

høyre-assosiativ(eng: right-associative) 2
idempotent(eng: idempotent) 20
• operasjon

En unær operasjon $f$ på en mengde $S$ er idempotent hvis det for alle $x\in S$ er slik at $f(f(x))=f(x)$. En binær operasjon $\ast$ på en mengde $S$ er idempotent hvis det for alle $x\in S$ er slik at $x\ast x=x$.

identitetselement(eng: identity element) 20

Se nøytralt element.

identitetsfunksjon(eng: identity function) 6

Funksjonen $id_A$ på $A$ som er slik at $id_A(x)=x$ for alle $x\in A$.

identitetsrelasjon(eng: identity relation) 6 15

En relasjon som relaterer alle elementer til seg selv. Vanligvis symbolisert med likhetstegnet.

ikke-konstruktiv(eng: non-constructive) 5
• bevis, • logikk
ikke-terminalsymbol(eng: nonterminal symbol) 23
• i grammatikk

Et symbol i en formell grammatikk som brukes for å definere språk. Ikke-terminalsymbolene brukes til å definere produksjonsregler og forekommer ikke i strengene som grammatikken definerer.

implikasjon(eng: implication) 2 3
• mellom formler

En formel på formen $(F\imp G)$ som representerer utsagnet hvis $F$, så $G$. I noen tilfeller kalles også selve utsagnet en implikasjon.

induksjon(eng: induction) 11 12

En bevismetode for å bevise påstander om alle elementer i en induktivt definert mengde.

induksjonshypotese(eng: induction hypothesis) 11 12

En antakelse i et induksjonsbevis; et ledd i å bevise induksjonssteget.

induksjonssteg(eng: induction step) 9 10 11 12

Det andre steget i definisjonen av en induktivt definert mengde eller i et bevis ved induksjon.

induktivt definert mengde(eng: inductively defined set) 9

Den minste mengden som inneholder en basismengde, og som er lukket under gitte operasjoner.

infiksnotasjon(eng: infix notation) 13

Å sette funksjonssymbolet i midten: $(x+y)$

injektiv(eng: injective) 7
• funksjon

En funksjon er injektiv, eller en-til-en, dersom det for alle $x,y\in A$ er slik at hvis $x\neq y$, så $f(x)\neq f(y)$.

inklusjon-og-eksklusjonsprinsippet(eng: inclusion–exclusion principle) 18

$|A\cup B|=|A|+|B|-|A\cap B|$

inntil(eng: incident) 21

En kant ligger inntil nodene den forbinder. Se kant.

inputsymbol(eng: input symbol) 23

En deterministisk, endelig tilstandsmaskin defineres blant annet ved hjelp av en endelig mengde inputsymboler, også kalt et alfabet.

intuisjonistisk(eng: intuitionistic logic) 3 24
• logikk

Naturlig deduksjon uten $\regel{RAA}$-regelen. Se konstruktiv logikk.

invers(eng: inverse) 20
• element, • funksjon, • relasjon

Relasjonen $\set{\tuple{y,x}\mid\tuple{x,y}\in R}$ er den inverse relasjonen til $R$. Den inverse funksjonen til $f:A\to B$ er funksjonen $f^{-1}:B\to$ som er slik at $f^{-1}(b)=a$ hvis $f(a)=b$. To elementer $a$ og $a^{-1}$ er inverser for en gitt operasjon $\ast$, dersom $a\ast a^{-1}=a^{-1}\ast a=e$, hvor $e$ er identitetselement for $\ast$.

irrefleksiv(eng: irreflexive) 6 9
• relasjon

En binær relasjon er irrefleksiv dersom det ikke finnes noen $x$ slik at $xRx$.

isolert(eng: isolated) 21

En node med grad $0$.

isomorfi(eng: isomorphism) 21

En isomorfi mellom to grafer er en bijeksjon $f$ mellom nodene til grafene som er slik at nodene $u$ og $v$ er naboer hviss $f(u)$ og $f(v)$ er naboer.

kalkyle(eng: calculus) 24
logisk •

En syntaktisk formalisering av logisk resonnering som kan brukes til å lage utledninger og bevis. Består vanligvis av slutningsregler og måter å lage bevis på. Naturlig deduksjon er en logisk kalkyle.

kant(eng: edge) 21

En kant er en mengde av to noder; vi sier at kanten forbinder nodene, og at nodene ligger inntil kanten. Se graf.

kardinalitet(eng: cardinality) 8
• av mengder

Kardinalitet betyr intuitivt «størrelse». To mengder har lik kardinalitet hvis det finnes en bijeksjon mellom dem. Mindre kardinalitet betyr at det finnes en bijeksjon mellom en mengde og en delmengde av den andre.

kartesisk produkt(eng: cartesian product) 1

Det kartesiske produktet av mengdene $X_1$, $X_2$, $\ldots$, $X_n$ er mengden av alle $n$-tupler $\tuple{x_1,\ldots,x_n}$ hvor $x_i\in X_i$.

Kleene(eng: Kleene) 23
•tillukning, •stjerne

Samme som tillukning.

kombinasjon(eng: combination) 18

Et utvalg av elementer fra en mengde hvor rekkefølgen ikke spiller noen rolle. En $k$-kombinasjon av en mengde $A$ er en delmengde av $A$ med $k$ elementer.

kommutativ(eng: commutative) 3 20
• operasjon, • lov, • gruppe

En binær operasjon $\ast$ på en mengde $S$ er kommutativ hvis det for alle $x,y\in S$ er slik at $x\ast y=y\ast x$. En gruppe er kommutativ dersom operasjonen er kommutativ. I utsagnslogikk har vi kommutative lover, som er ekvivalenser på formen $A\land B\Eqv B\land A\text.$

komplement(eng: complement) 8 21
• av graf, • av mengde

Komplementet til en mengde $M$, skrevet $\kompl{M}$, er mengden av alle elementer i den universelle mengden som ikke er med i $M$. Komplementet til en graf $G$ er grafen som har de samme nodene som $G$, men hvor to noder er naboer hvis og bare hvis nodene ikke er naboer i $G$.

komplett(eng: complete) 11 21 24
• induksjon, • graf, • kalkyle

Komplett, eller sterk, induksjon er induksjonsbevis hvor vi i induksjonssteget antar at påstanden holder for alle foregående elementer. En graf er komplett hvis enhver node er nabo med enhver annen node. En kalkyle er komplett hvis enhver gyldig formel er bevisbar i kalkylen.

komponent(eng: component) 22

Sammenhengende grafer som utgjør en større ikke-sammenhengende graf.

kongruensklasse(eng: congruence class) 17

En mengde av heltall som har samme rest når vi deler på et gitt tall, det vil si en ekvivalensklasse av heltall; det samme som en restklasse.

konjunksjon(eng: conjunction) 2

En formel på formen $(F\land G)$.

konkatenering(eng: concatenation) 9 10 23
• av lister, • av strenger, • av språk

Operasjonen som består av å slå sammen lister, strenger eller språk: To strenger $s$ og $t$ slås sammen til én, $st$. To lister, $L$ og $M$, slås sammen med funksjonen $\appends$ til $\appendn{L}{M}$, for eksempel $\appendn{\liste{1,2,3}}{\liste{4,5,6}}=\liste{1,2,3,4,5,6}$. Hvis $L$ og $M$ er språk, er konkateneringen av $L$ og $M$, språket $LM=\set{st\mid s\in L\text{ og }t\in M}$.

konklusjon(eng: conclusion) 24
konnektiv(eng: connective) 2

De logiske konnektivene er $\land,\lor,\imp,\neg$, som brukes til å representerere de logiske bindeordene og, eller, ikke og hvis, så.

konsekvens(eng: consequence) 4 13
logisk •

La $M$ være en mengde av utsagnslogiske formler, og la $F$ være en utsagnslogisk formel. Hvis $F$ er sann for alle valuasjoner som gjør alle formlene i $M$ sanne samtidig, er $F$ en logisk konsekvens av formlene i $M$. Vi skriver $M\models F$ når $F$ er en logisk konsekvens av $M$.

konsistent(eng: consistent) 24
• teori

En mengde formler er konsistent hvis det ikke er mulig å utlede, i for eksempel naturlig deduksjon, både en formel og dens negasjon fra den.

konstantsymbol(eng: constant symbol) 13

Brukes i førsteordens språk for å representere elementer og angis i en signatur.

konstruktiv(eng: constructive) 5 24 3
• bevis, • logikk

Et konstruktivt bevis inneholder mer informasjon enn et ikke-konstruktivt bevis, og viser frem eller gir en konstruktiv metode for å finne et objekt. Dette er vanlig i intuisjonistisk logikk, hvor vi ikke bruker $\regel{RAA}$-regelen. I konstruktiv logikk er kravet for bevisbarhet strengere; for eksempel er ikke $(P\lor\neg P)$ bevisbar.

kontekstfri(eng: context-free) 23
• grammatikk, • språk

En kontekstfri grammatikk er en grammatikk hvor enhver produksjonsregel er på formen $A\imp X$, hvor $A$ er et ikke-terminalsymbol og $X$ en streng av terminal- og ikke-terminalsymboler. Et språk som defineres av en kontekstfri grammatikk, kalles et kontekstfritt språk.

kontradiksjon(eng: contradiction) 4 5 15

En kontradiktorisk formel er en formel som er usann for alle valuasjoner/modeller. Dette er det motsatte av oppfyllbar.

kontrapositiv(eng: contrapositive) 5
• formel, •t bevis

Et kontrapositivt bevis for en påstand på formen hvis $F$, så $G$, er et logisk gyldig resonnement som begynner med antakelsen om at $G$ er usann, og som konkluderer med at $F$ er usann. Den kontrapositive av formelen $(F\imp G)$ er formelen $(\neg G\imp\neg F)$.

krets(eng: circuit) 22

En lukket vandring hvor ingen kant forekommer mer enn én gang.

kryssprodukt(eng: cross product) 1
kvantor(eng: quantifier) 13

Allkvantoren $\forall$ («for alle») og eksistenskvantoren $\exists$ («det finnes»).

kvotientmengde(eng: quotient set) 17

Mengden, $S/\mathord{\sim}$, av alle ekvivalensklassene for en gitt mengden $S$ og ekvivalensrelasjon $\sim$.

lengde(eng: length) 10
• til en liste

Antall elementer i en liste; rekursivt definert.

lineær(eng: linear) 6
• ordning

Se total ordning.

liste(eng: list) 9

Induktivt definert som den minste mengden som inneholder $\tomliste$ (tom liste), og som er lukket under det å legge inn i liste ved $\cns$.

logikk(eng: logic) 2 3 4 5 13 14 15 16 24
utsagns•, førsteordens •

Kunsten å tenke fra antakelser.

logisk(eng: logical) 2–4 13
• bindeord, • ekvivalens, • kalkyle, • konnektiv, • konsekvens, • symbol

Se: ekvivalens, kalkyle, konnektiv, konsekvens, språk.

lukket(eng: closed) 9 14 22 24
• antakelse, • formel, • mengde, • sti, • term, • vandring

En mengde er lukket under en operasjon hvis vi ikke får noen nye elementer ved å anvende operasjonen på elementer i mengden. Se antakelse, skop, sti, term, vandring.

løkke(eng: loop) 21

En kant som går fra en node til seg selv i en pseudograf.

løvnode(eng: leaf node) 9

Se node.

mengde(eng: set) 1

En endelig eller uendelig samling av objekter der innbyrdes rekkefølge og antall forekomster av hvert objekt ignoreres.

mengdebygger(eng: set builder / comprehension / abstraction) 1

En definisjon på formen «mengden av alle elementer $x$ slik/gitt at $x$ har egenskapen $P$», som skrives $\set{x\mid x \text{ har egenskapen } P}$.

mengdedifferanse(eng: set difference) 1
• av mengder

Mengdedifferansen mellom $A$ og $B$, eller $A$ minus $B$, er mengden av objekter som er element i $A$, men ikke i $B$.

modell(eng: model) 15
førsteordens •

En mengde sammen med tolkning av alle ikke-logiske symboler i et førsteordens språk.

modulo(eng: modulo) 17

To heltall $x$ og $y$ er like modulo $n$ dersom $x$ og $y$ har samme rest når vi deler på $n$.

moteksempel(eng: counter example) 5

Noe som viser at en påstand ikke er sann.

motsigelse(eng: contradiction) 4 5 15

Samme som kontradiksjon.

motsigelsesbevis(eng: proof by contradiction) 5

Et bevis som begynner med antakelsen om at påstanden er usann, og som viser hvordan denne antakelsen fører til en motsigelse.

multigraf(eng: multigraph) 21

En graf hvor en kant er definert slik at flere kanter kan ligge inntil de samme nodene.

multimengde(eng: multiset / bag) 1

En samling objekter der rekkefølgen, men ikke antall forekomster av hvert element, ignoreres.

multiplikasjonsprinsippet(eng: multiplication principle / rule of product) 18

Hvis vi skal treffe en rekke uavhengige valg, er det totale antallet muligheter produktet av antall muligheter ved hvert valg.

nabo(eng: adjacent) 21

To noder kalles naboer hvis de forbindes av en kant.

naturlig deduksjon(eng: natural deduction) 24

En logisk kalkyle.

naturlig tall(eng: natural number) 1

Mengden av tall $0,1,2,3,\ldots$. Induktiv definert som den minste mengden som inneholder $0$, og som er lukket under suksessorfunksjonen.

negasjon(eng: negation) 2

En formel på formen $\neg F$.

node(eng: node / vertex) 9 21
• i binært tre, blad•, løv•, • i graf

I et binært tre $\tre{V,x,H}$ kalles $x$ en node. Hvis et tre er på formen $\bladnode{x}$, kalles $x$ en bladnode eller en løvnode. I grafteori består en graf av noder og kanter; her kalles en node med grad én i et tre, en løvnode. Se graf.

nullgraf(eng: null graph) 21

En graf uten kanter.

nøytralt(eng: neutral) 20
• element

Et element $e$ som er slik at $x\ast e=e\ast x=x$ for alle $x\in S$, for en gitt operasjon $\ast$ og mengde $S$. For eksempel er $0$ et nøytralt element for $+$. Samme som identitetselement.

operasjon(eng: operation) 1 7 20

En unær operasjon på en mengde $M$ er en funksjon fra $M$ til $M$. En $n$-ær operasjon på en mengde $M$ er en funksjon fra $M^n$ til $M$.

oppfyllbar(eng: satisfiable) 4 15
• formel, • mengde

En formel, i utsagnslogikk eller førsteordens logikk, som kan gjøres sann. En mengde formler er oppfyllbar hvis det finnes en valuasjon eller modell som gjør alle formlene sanne. Motsatt av kontradiktorisk.

ordnet utvalg(eng: ordered selection) 18

Å velge $k$ elementer i rekkefølge fra en mengde med $n$ elementer, kalles et ordnet utvalg eller en $k$-permutasjon av $n$ elementer. Det er $n(n-1)(n-2)\cdots(n-(k-1))$ måter å gjøre dette på.

ordning(eng: order) 6
partiell •, pre•, total •, lineær •, •

Se partiell ordning, preordning, total ordning. Brukes også i kombinatorikk, synonymt med en permutasjon.

overgangsfunksjon(eng: transition funksjon) 23

I en deterministisk, endelig tilstandsmaskin, en funksjon som tar to argumenter, en tilstand og et inputsymbol, og som returnerer en tilstand.

overtellbar(eng: uncountable) 8
• mengde

En mengde som ikke er tellbar.

palindrom(eng: palindrome) 19

En streng er et palindrom dersom resultatet blir det samme om den leses forlengs eller baklengs.

par(eng: pair) 1
ordnet •

Se tuppel.

parallell(eng: multiple / parallell) 21
• kant

To eller flere kanter som forbinder de samme nodene i en multigraf, kalles parallelle kanter.

partall(eng: even number) 5 9

Heltall på formen $2\cdot m$. Induktivt definert som den minste mengden som inneholder $0$, og som er lukket under det å legge til eller trekke fra $2$.

partiell(eng: partial) 6
• ordning, • funksjon

En binær relasjon er en partiell ordning hvis den er refleksiv, transitiv og anti-symmetrisk. En partiell funksjon fra $A$ til $B$ er en funksjon fra en delmengde av $A$ til $B$.

partisjon(eng: partition) 17

En partisjon av en mengde $S$ er en mengde $X$ av ikke-tomme delmengder av $S$ slik at unionen av alle mengdene i $X$ er lik $S$, og snittet mellom to forskjellige mengder fra $X$ er tomt.

Pascals trekant(eng: Pascal's triangle) 19

En måte å regne ut binomialkoeffisientene på.

permutasjon(eng: permutation) 18 19

En permutasjon av en mengde er en ordning av elementene i den. Hvis vi allerede har en ordning, er en permutasjon en endring av rekkefølgen. Samme som en bijeksjon på mengden.

planær(eng: planar) 21
• graf

En graf er planær hvis det går an å tegne den på en slik måte at ingen kanter krysser hverandre.

postfiksnotasjon(eng: postfix notation) 13

Å sette funksjonssymbolet bakerst: $(x,y)+$

potensmengde(eng: power set) 8

Mengden av alle delmengder av en mengde.

predikat(eng: predicate) 13

Et predikat er et uttrykk som inneholder en eller flere plassholdere, og som blir sant eller usant når vi erstatter plassholderne med verdier.

prefiksnotasjon(eng: prefix notation) 13

Å sette funksjonssymbolet foran: $+(x,y)$

premiss(eng: premise) 24
preneks normalform(eng: prenex normal form) 16

En formel på preneks normalform er på formen $\textcolor{okblue}{Q}_1x_1\textcolor{okblue}{Q}_2x_2\ldots\textcolor{okblue}{Q}_nx_n \varphi$ hvor hver $\textcolor{okblue}{Q}_i$ enten er $\forall$ eller $\exists$ og $\varphi$ er uten kvantorer.

preordning(eng: preorder) 6

En binær relasjon er en preordning hvis den er refleksiv og transitiv.

presedens(eng: precedence) 2 13 23
•regler

I utsagnslogikk gis konnektivene ulik presedens, det vil si hvilke som binder sterkest når det ikke er parenteser på plass. I førsteordens logikk gjøres det samme for kvantorene. Presedensregler brukes også for å gjøre regulære uttrykk uten parenteser, entydig. Vi leser for eksempel $\str{01}\xx$ som $\str{0(1)}\xx$, og ikke $\str{(01)}\xx$

produksjonsregel(eng: production rule) 23

Uttrykk i formelle grammatikker på formen $X\to Y$, hvor $X$ og $Y$ er strenger av terminal- og ikke-terminalsymboler og $X$ ikke kan være den tomme strengen.

pseudograf(eng: pseudograph) 21

En graf hvor en kant er definert slik at en kant kan forbinde en node med seg selv.

(eng: på) 7
• funksjon
rasjonalt tall(eng: rational number) 1
Reductio ad Absurdum(eng: Reductio ad Absurdum) 5 24
•, • i naturlig deduksjon

En reduksjon av noe til det absurde, en motsigelse, som brukes i motsigelsesbevis. I naturlig deduksjon er det en slutningsregel, RAA-regelen.

reelt tall(eng: real number) 1

Mengden av tall som representerer punktene på en kontinuerlig tallinje.

refleksiv(eng: reflexive) 6 9
• relasjon, • tillukning

En binær relasjon er refleksiv dersom $xRx$, for alle $x$. Den refleksive tillukningen av en binær relasjon $R$ er den minste relasjonen som inneholder $R$, og som er refleksiv.

regel(eng: rule) 23 24
produksjons•, slutnings•
regulær(eng: regular) 23
• grammatikk, • språk, • uttrykk

Mengden av regulære uttrykk er induktivt definert, og hvert regulære uttrykk definerer et regulært språk. Se grammatikk og språk.

rekursiv(eng: recursive) 10
• funksjon

En rekursiv funksjon er en funksjon som defineres via et basissteg og et rekursjonssteg, med utgangspunkt i en underliggende induktivt definert mengde.

rekursjonssteg(eng: recursion step) 10
relasjon(eng: relation) 6

En $n$-ær relasjon er en delmengde av $A_1\times\cdots\times A_n$. En $n$-ær relasjon på en mengde $A$ er en delmengde av $A^n$.

relasjonssymbol(eng: relation symbol) 13

Symbol i førsteordens språk som brukes til å representere relasjon. Angis i en signatur.

restklasse(eng: residue class) 17

Det samme som en kongruensklasse.

rettet(eng: directed) 21
• graf

En graf hvor kantene er ordnede par $\tuple{u,v}$ i stedet for mengder $\set{u,v}$.

reversere(eng: reverse) 12 23
• en liste, • en streng

En rekursiv funksjon som returner en liste eller streng med de samme elementene, men i motsatt rekkefølge.

sammenhengende(eng: connected) 22
• graf

At det finnes en sti mellom alle par av noder i en graf.

sammensetning(eng: composition) 7 10
• av funksjon, • av liste

Hvis $f:A\to B$ og $g:B\to C$ er funksjoner, er funksjonen $g\circ f:A\to C$ definert som funksjonen vi får ved å først anvende $f$, deretter anvende $g$ på verdien av dette, det vil si $(g\circ f)(a)=g(f(a))$. For lister, se konkatenering.

sann(eng: true) 3
•, • formel

En av de to grunnleggende sannhetsverdiene: sann og usann. En valuasjon eller en modell gjør en formel sann eller usann.

sannhetsverdi(eng: truth value) 3

Sann og usann, representert ved ${\T}$ og ${\F}$.

sannhetsverditabell(eng: truth table) 3

En tabell som forteller hva sannhetsverdien til en sammensatt utsagnslogisk formel er på bakgrunn av hvilke sannhetsverdier som er tilordnet utsagnsvariablene.

selv-komplementær(eng: self-complementary) 21
• graf

En graf som er identisk med sitt komplement.

signatur(eng: signature) 13

Angir mengden av konstant-, funksjons- og relasjonssymboler for et førsteordens språk.

skog(eng: forest) 22

En graf hvor alle komponentene er trær.

skop(eng: scope) 13 14
• til kvantor

I formlene $\forall x\varphi$ og $\exists x\varphi$ er alle forekomster av $x$ i $\varphi$ bundet og innenfor skopet til kvantoren. En variabel er fri hvis den ikke er bundet. En formel er lukket hvis den ikke inneholder noen frie variabler.

slutningsregel(eng: inference rule) 24

Skjema i naturlig deduksjon som angir hvordan utledninger konstrueres. Formlene over streken kalles premisser, og formelen under streken kalles konklusjonen.

snitt(eng: intersection) 1
• av mengder

Snittet av to mengder $A$ og $B$ er mengden som inneholder nøyaktig de elementer som er element i både $A$ og $B$.

språk(eng: language) 9 23
førsteordens •, formelt •, regulært •

Et førsteordens språk består av logiske symboler, som er konnektiver, kvantorer, variabler, parenteser og kommaer, og ikke-logiske symboler, som er konstant-, funksjons- og relasjonssymboler. Et formelt språk over $A$ er en delmengde av $A^\ast$, alle mulige strenger over $A$. Et regulært språk over et alfabet er den minste mengden som inneholder $\tomstreng$ og alle tegn fra alfabetet, og som er lukket under union, konkatenering og tillukningen.

startsymbol(eng: start symbol) 23

Ett av ikke-terminalsymbolene i en formell grammatikk.

starttilstand(eng: start state) 23

En av tilstandene i en deterministisk, endelig tilstandsmaskin. Tilsvarer startsymbolet i en formell grammatikk.

sti(eng: path) 22

En vandring hvor ingen node forekommmer mer enn én gang. En sti med minst tre noder, sammen med kanten som forbinder den første og siste noden, kalles en lukket sti eller en sykel.

streng(eng: string) 9 23

En endelig sekvens av tegn, tatt fra et underliggende alfabet.

strukturell induksjon(eng: structural induction) 12
substitusjon(eng: substitution) 12 15
• av formler, • av termer

Formelen $F\subst{\textcolor{okblue}{P}}{\textcolor{okgreen}{H}}$ er resultatet av å bytte ut alle forekomster av $\textcolor{okblue}{P}$ i $F$ med $\textcolor{okgreen}{H}$. Termen $s[x/t]$ er resultatet av å erstatte, eller substituere, alle forekomster av $x$ i $s$ med $t$.

sunn(eng: sound) 24
• kalkyle

En kalkyle er sunn hvis enhver bevisbar formel i kalkylen er gyldig.

surjektiv(eng: surjective) 7
• funksjon

En funksjon er surjektiv, eller på, dersom det for alle $y\in B$, finnes en $x\in A$ slik at $f(x)=y$.

sykel(eng: cycle) 22

En sti $v_1v_2\ldots v_n$ med minst tre noder, sammen med kanten som forbinder $v_n$ og $v_1$. Samme som en lukket sti.

symmetrisk(eng: symmetric) 6 8
• relasjon, • tillukning, • differanse

En binær relasjon er symmetrisk dersom det er slik at hvis $xRy$, så $yRx$, for alle $x$ og $y$. Den refleksive tillukningen av en binær relasjon $R$, er den minste relasjonen som inneholder $R$, og som er refleksiv. Den symmetriske differansen mellom to mengder $A$ og $B$, er $(A\setminus B)\union(B\setminus A)$.

tautologi(eng: tautology) 4

En utsagnslogisk formel som er sann for alle valuasjoner.

tellbar(eng: countable) 8
• mengde

Det finnes en en-til-en korrespondanse mellom elementene og de naturlige tallene.

teorem(eng: theorem) 0 16

En logisk konsekvens av en teori.

teori(eng: theory) 16

En mengde med formler.

term(eng: term) 13
førsteordens •, lukket •

Induktivt definert fra variabler, konstant- og funksjonssymboler, gitt et førsteordens språk. En term er lukket hvis den ikke inneholder noen variabler.

terminalsymbol(eng: terminal symbol) 23
• i grammatikk

Et symbol i en formell grammatikk som brukes for å definere språk. Strengene som grammatikken definerer, skal kun inneholde terminalsymboler.

Thue-Morse-ordet(eng: Thue-Morse sequence) 9
tillukning(eng: closure) 9 23
• av mengde, • av relasjon, • av språk

Tillukningen av en mengde under en eller flere operasjoner er den minste mengden som inneholder denne mengden, og som er lukket under operasjonene. Tillukningen av en relasjon er den minste relasjonen som utvider denne relasjonen, og som har en bestemt egenskap, for eksempel refleksiv, symmetrisk eller transitiv. Brukes for å definere induktivt definerte mengder. Tillukningen av et språk $L$ er språket $L^\ast=L^0\union L^1\union L^2\union L^3\union\cdots$, det vil si mengden av alle endelige strenger over $L$.

tilordning(eng: assignment) 3 4
• av sannhetsverdier

En funksjon fra mengden av utsagnsvariabler til $\set{\F,\T}$.

tilstand(eng: state) 23

En del av en deterministisk, endelig tilstandsmaskin.

tilstandsmaskin(eng: deterministic finite automaton, DFA) 23

En deterministisk, endelig tilstandsmaskin er en abstrakt måte å definere språk på, definert ved en mangde tilstander, et alfabet og en overgangsfunksjon.

todelt(eng: bipartite) 22
• graf

En graf som er slik at mengden av noder kan deles i to disjunkte delmengder $U$ og $V$ slik at enhver kant forbinder en node i $U$ med en node i $V$. Samme som bipartitt.

tolkning(eng: interpretation) 3 15
• av formler, • av termer

En måte å gi sannhetsverdier til formler på. I utsagnslogikk er en tolkning gitt ved en valuasjon. I førsteordens logikk gir en modell en tolkning av ikke-logiske symboler, det vil si alle konstant-, funksjons- og relasjonssymboler, og dermed alle formler.

tom(eng: empty) 1 6 9 21 23
• graf, • liste, • mengde, • relasjon, • tuppel, • tre, • streng

En tom graf er en graf uten kanter. Den tomme listen er $\tomliste$. Den tomme mengden, $\emptyset$, er mengden uten elementer. En tom relasjon er en tom mengde. Det tomme tuppelet er $\tuple{}$. Det tomme binære treet er $\tomttre$. En tom streng $\tomstreng$ har egenskapen $s\tomstreng=\tomstreng s=s$.

total(eng: total) 6
• ordning

En partiell ordning er en total (eller lineær) ordning hvis den er slik at $xRy$ eller $yRx$, for alle $x$ og $y$.

transitiv(eng: transitive) 6
• relasjon, • tillukning

En binær relasjon er transitiv dersom det er slik at hvis $xRy$ og $yRz$, så $xRz$, for alle $x$, $y$ og $z$. Den transitive tillukningen av en binær relasjon $R$, er den minste relasjonen som inneholder $R$, og som er transitiv.

tre(eng: tree) 9 21
binært •, perfekt binært •, tomt •, •

Binære trær er induktivt definert som den minste mengden som inneholder $\tomttre$ (tomt tre), og som er lukket under det å sette sammen trær ved $\tre{V,x,H}$. I et perfekt binært tre har alle trærne samme høyde. I grafteori er et tre en sammenhengende, asyklisk graf.

tuppel(eng: tuple) 1

Et tuppel med $n$ elementer, et $n$-tuppel, er en samling med $n$ objekter der både innbyrdes rekkefølge og antall forekomster av hvert objekt teller. Et $2$-tuppel er det samme som ordnet par.

tur(eng: walk) 22
uavhengig(eng: independent) 4
• formel, • mengde

En formel $F$ er uavhengig av en mengde formler $M$ hvis hverken $F$ eller $\neg F$ er en logisk konsekvens av $M$. En mengde formler er uavhengig hvis enhver formel er uavhengig av mengden av de andre formlene.

union(eng: union) 1
• av mengder

Unionen av to mengder $A$ og $B$ er mengden som inneholder nøyaktig de elementer som er element i $A$ eller $B$.

universell(eng: universal) 6 8
• mengde, • relasjon

Vi antar at vi har en underliggende universell mengde, slik at vi for eksempel kan ta komplementet av mengder. Den universelle relasjonen relaterer alt til alt, det vil si $\set{\tuple{x,x}\mid x\in U}$.

unær(eng: unary) 7
• operasjon, • funksjon

En funksjon/operasjon som tar ett argument.

utledbar(eng: derivable) 24
• formel

Det at det finnes et bevis for en formel i naturlig deduksjon.

utledning(eng: derivation) 23 24
• av en streng, • i naturlig deduksjon

Når en formell grammatikk er gitt, kan strenger utledes ved hjelp av produksjonsreglene. En utledning er en sekvens av anvendelser av produksjonsreglene. I naturlig deduksjon er mengden av utledninger induktivt definert fra formler via slutningsreglene.

utsagn(eng: proposition) 2

Noe som har en sannhetsverdi.

utsagnsvariabel(eng: propositional variable) 2

Samme som en atomær formel i utsagnslogikk.

valuasjon(eng: valuation) 3

En funksjon fra utsagnslogiske formler til sannhetsverdier.

vandring(eng: walk) 22

En sekvens av noder og kanter i en graf. En vandring hvor den første og siste noden sammenfaller, kalles lukket.

variabel(eng: variable) 13

Et av de logiske symbolene i førsteordens språk.

Venn-diagram(eng: Venn Diagram) 1 8

En måte å visualisere mengder og de forskjellige måtene mengder kan kombineres på.

venstre-assosiativ(eng: left-assosiative) 2
verdi(eng: value) 7

Hvis $f$ er en funksjon, kalles $f(x)$ verdien til funksjonen.

verdiområde(eng: codomain) 7
• til funksjon

Mengden som gir verdiene til en funksjon.

vilkårlig(eng: arbitrary) 5

Betyr at det ikke ligger noen føringer på hvilket objekt vi har valgt; det kunne like gjerne ha vært et annet objekt.

åpen(eng: open) 24
• antakelse

I naturlig deduksjon, en antakelse som ikke er lukket.