En delmengde av tilstandene i en endelig tilstandsmaskin.
En mengde sammen med en eller flere operasjoner på denne mengden.
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.
En binær relasjon er anti-symmetrisk dersom det er slik at hvis $xRy$ og $yRx$, så $x=y$, for alle $x$ og $y$.
Egenskap ved funksjons- og relasjonssymbol som forteller hvor mange termer som trengs for å lage henholdsvis termer og atomære formler.
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.
En binær relasjon er asymmetrisk dersom det er slik at hvis $xRy$, så er ikke $yRx$, for alle $x$.
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.
Utgangspunktet for å definere en induktivt definert mengde.
Det første steget i definisjonen av en induktivt definert mengde, en rekursiv funksjon eller i et bevis ved induksjon. Også kalt basistilfellet.
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.
En bevismetode hvor hvert enkelt tilfelle blir bevist hver for seg.
En funksjon som er injektiv og surjektiv, er bijektiv. Betyr det samme som en en-til-en korrespondanse.
Bildet av hele $A$ under $f$, $f[A]$, kalles bildemengden til $f$.
Mengden $\set{f(x)\mid x\in X}$ kalles bildet av $X$ under $f$, og skrives $f[X]$.
Tallene på formen $\binom{n}{k}=\frac{n!}{(n-k)!k!}$ («$n$ velg $k$»).
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.
Tall som kan skrives på formen $\frac{m}{n}$, hvor $m$ og $n$ er heltall og $n$ ikke er lik $0$.
En mengde $A$ er en delmengde av en mengde $B$ hvis alle elementer i $A$ også er elementer i $B$.
Et bevis for en påstand på formen «hvis $A$, så $B$», hvor man på en direkte måte viser hvordan $A$ leder til $B$.
I en disjunksjon $(F\lor G)$ kalles $F$ og $G$ for disjunktene.
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)$
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.
To formler er 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.
Funksjonen $s:\bbN\to\bbN$ som er slik at $s(x)=x+1$.
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.
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.
Tallrekken hvor hvert tall er summen av de to foregående: $0$, $1$, $1$, $2$, $3$, $5$, $8$, $13$, $21$ etc.
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$.
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.
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$.
En graf $G$ består av en endelig, ikke-tom mengde $V$ av noder og en mengde $E$ av kanter.
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.
En algebraisk struktur $\tuple{G,\bullet}$, som er slik at $\bullet$ er assosiativ, har et identitetselement og alle elementer har en invers.
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.
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.
Det er alltid et partall antall noder av odde grad i en graf.
Antall noder i den lengste grenen i et binært tre. Vanligvis rekursivt definert.
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$.
Funksjonen $id_A$ på $A$ som er slik at $id_A(x)=x$ for alle $x\in A$.
En relasjon som relaterer alle elementer til seg selv. Vanligvis symbolisert med likhetstegnet.
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.
En formel på formen $(F\imp G)$ som representerer utsagnet hvis $F$, så $G$. I noen tilfeller kalles også selve utsagnet en implikasjon.
En bevismetode for å bevise påstander om alle elementer i en induktivt definert mengde.
En antakelse i et induksjonsbevis; et ledd i å bevise induksjonssteget.
Det andre steget i definisjonen av en induktivt definert mengde eller i et bevis ved induksjon.
Den minste mengden som inneholder en basismengde, og som er lukket under gitte operasjoner.
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)$.
$|A\cup B|=|A|+|B|-|A\cap B|$
En deterministisk, endelig tilstandsmaskin defineres blant annet ved hjelp av en endelig mengde inputsymboler, også kalt et alfabet.
Naturlig deduksjon uten $\regel{RAA}$-regelen. Se konstruktiv logikk.
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 A$ 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$.
En binær relasjon er irrefleksiv dersom det ikke finnes noen $x$ slik at $xRx$.
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.
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.
En kant er en mengde av to noder; vi sier at kanten forbinder nodene, og at nodene ligger inntil kanten. Se graf.
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.
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$.
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.
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.$
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, 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.
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.
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}$.
De logiske konnektivene er $\land,\lor,\imp,\neg$, som brukes til å representerere de logiske bindeordene og, eller, ikke og hvis, så.
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$.
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.
Brukes i førsteordens språk for å representere elementer og angis i en signatur.
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.
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.
En kontradiktorisk formel er en formel som er usann for alle valuasjoner/modeller. Dette er det motsatte av oppfyllbar.
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)$.
Allkvantoren $\forall$ («for alle») og eksistenskvantoren $\exists$ («det finnes»).
Mengden, $S/\mathord{\sim}$, av alle ekvivalensklassene for en gitt mengden $S$ og ekvivalensrelasjon $\sim$.
Induktivt definert som den minste mengden som inneholder $\tomliste$ (tom liste), og som er lukket under det å legge inn i liste ved $\cns$.
Se: ekvivalens, kalkyle, konnektiv, konsekvens, språk.
En endelig eller uendelig samling av objekter der innbyrdes rekkefølge og antall forekomster av hvert objekt ignoreres.
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}$.
Mengdedifferansen mellom $A$ og $B$, eller $A$ minus $B$, er mengden av objekter som er element i $A$, men ikke i $B$.
En mengde sammen med tolkning av alle ikke-logiske symboler i et førsteordens språk.
To heltall $x$ og $y$ er like modulo $n$ dersom $x$ og $y$ har samme rest når vi deler på $n$.
Et bevis som begynner med antakelsen om at påstanden er usann, og som viser hvordan denne antakelsen fører til en motsigelse.
En graf hvor en kant er definert slik at flere kanter kan ligge inntil de samme nodene.
En samling objekter der rekkefølgen, men ikke antall forekomster av hvert element, ignoreres.
Hvis vi skal treffe en rekke uavhengige valg, er det totale antallet muligheter produktet av antall muligheter ved hvert valg.
Mengden av tall $0,1,2,3,\ldots$. Induktiv definert som den minste mengden som inneholder $0$, og som er lukket under suksessorfunksjonen.
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.
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.
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$.
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.
Å 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å.
Se partiell ordning, preordning, total ordning. Brukes også i kombinatorikk, synonymt med en permutasjon.
I en deterministisk, endelig tilstandsmaskin, en funksjon som tar to argumenter, en tilstand og et inputsymbol, og som returnerer en tilstand.
En streng er et palindrom dersom resultatet blir det samme om den leses forlengs eller baklengs.
To eller flere kanter som forbinder de samme nodene i en multigraf, kalles parallelle kanter.
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$.
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$.
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.
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.
En graf er planær hvis det går an å tegne den på en slik måte at ingen kanter krysser hverandre.
Et predikat er et uttrykk som inneholder en eller flere plassholdere, og som blir sant eller usant når vi erstatter plassholderne med verdier.
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.
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$
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.
En graf hvor en kant er definert slik at en kant kan forbinde en node med seg selv.
En reduksjon av noe til det absurde, en motsigelse, som brukes i motsigelsesbevis. I naturlig deduksjon er det en slutningsregel, RAA-regelen.
Mengden av tall som representerer punktene på en kontinuerlig tallinje.
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.
Mengden av regulære uttrykk er induktivt definert, og hvert regulære uttrykk definerer et regulært språk. Se grammatikk og språk.
En rekursiv funksjon er en funksjon som defineres via et basissteg og et rekursjonssteg, med utgangspunkt i en underliggende induktivt definert mengde.
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$.
Symbol i førsteordens språk som brukes til å representere relasjon. Angis i en signatur.
En graf hvor kantene er ordnede par $\tuple{u,v}$ i stedet for mengder $\set{u,v}$.
En rekursiv funksjon som returner en liste eller streng med de samme elementene, men i motsatt rekkefølge.
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.
En av de to grunnleggende sannhetsverdiene: sann og usann. En valuasjon eller en modell gjør en formel sann eller usann.
En tabell som forteller hva sannhetsverdien til en sammensatt utsagnslogisk formel er på bakgrunn av hvilke sannhetsverdier som er tilordnet utsagnsvariablene.
Angir mengden av konstant-, funksjons- og relasjonssymboler for et førsteordens språk.
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.
Skjema i naturlig deduksjon som angir hvordan utledninger konstrueres. Formlene over streken kalles premisser, og formelen under streken kalles konklusjonen.
Snittet av to mengder $A$ og $B$ er mengden som inneholder nøyaktig de elementer som er element i både $A$ og $B$.
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.
En av tilstandene i en deterministisk, endelig tilstandsmaskin. Tilsvarer startsymbolet i en formell grammatikk.
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.
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$.
En funksjon er surjektiv, eller på, dersom det for alle $y\in B$, finnes en $x\in A$ slik at $f(x)=y$.
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.
En binær relasjon er symmetrisk dersom det er slik at hvis $xRy$, så $yRx$, for alle $x$ og $y$. Den symmetriske tillukningen av en binær relasjon $R$, er den minste relasjonen som inneholder $R$, og som er symmetrisk. Den symmetriske differansen mellom to mengder $A$ og $B$, er $(A\setminus B)\union(B\setminus A)$.
Det finnes en en-til-en korrespondanse mellom elementene og de naturlige tallene.
Induktivt definert fra variabler, konstant- og funksjonssymboler, gitt et førsteordens språk. En term er lukket hvis den ikke inneholder noen variabler.
Et symbol i en formell grammatikk som brukes for å definere språk. Strengene som grammatikken definerer, skal kun inneholde terminalsymboler.
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$.
En funksjon fra mengden av utsagnsvariabler til $\set{\F,\T}$.
En deterministisk, endelig tilstandsmaskin er en abstrakt måte å definere språk på, definert ved en mangde tilstander, et alfabet og en overgangsfunksjon.
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.
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.
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$.
En partiell ordning er en total (eller lineær) ordning hvis den er slik at $xRy$ eller $yRx$, for alle $x$ og $y$.
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.
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.
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.
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.
Unionen av to mengder $A$ og $B$ er mengden som inneholder nøyaktig de elementer som er element i $A$ eller $B$.
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}$.
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.
En sekvens av noder og kanter i en graf. En vandring hvor den første og siste noden sammenfaller, kalles lukket.
En måte å visualisere mengder og de forskjellige måtene mengder kan kombineres på.