Förberedelsematerial 2.3

Inför seminariet ska du gå igenom materialet nedan, vilket bör ta ca en timme, samt genomföra det tillhörande quizet som testar dina kunskaper på materialet. Quizet finns endast till för att du ska kunna skatta dina egna kunskaper inför seminariet, och är inget du bedöms på eller ens sparas.

Diskret matematik

Diskret matematik är de delar av matematiken som behandlar diskreta matematiska strukturer. Diskret betyder i matematiska sammanhang inte lågmäld, förtegen, finkänslig eller undangömd. Istället betyder diskret i det här sammanhanget åtskild. På engelska tydliggörs detta genom att det stavas discrete mathematics, inte discreet mathematics.

Diskret matematik behandlar alltså åtskilda matematiska objekt. För att närma oss den traditionella matematiken så kan vi prata t.ex. om heltalen. Det finns inga heltal mellan talet $1$ och talet $2$, de är strikt åtskilda. Jämför vi heltalen med de reella talen så finns det oändligt många värden mellan $1$ och $2$, t.ex. $1.5$, $1.0000000000001$ och $1.999999999999$. Vi säger därför att de reella talen är kontinuerliga, inte diskreta.

Många av de fenomen vi stöter på i verkligheten är diskreta, men av olika skäl som vi inte ska gå in på här så fokuserar man i grundskolan och gymnasiet väldigt mycket på just kontinuerlig matematik. Geometri? Kontinuerlig matematik. Kurvor och koordinater? Kontinuerlig matematik. Sinus och cosinus? Kontinuerlig matematik. Derivator och integraler? Kontinuerlig matematik. Imaginära och komplexa tal? Kontinuerlig matematik. Fysikaliska fenomen som krafter, laddningar, o.s.v.? Kontinuerlig matematik.

Vad har vi då för fenomen som är diskreta? Tja, studenter som läser kursen 729G46 i år t.ex. Alla studenter är separata entiteter, de är åtskilda. Det finns ingen “Kim och ett halvt” som är halvvägs mellan Kim och Alex. Nästan alla fysiska objekt som vi interagerar med dagligen är diskreta. Vi kan prata om objekt av olika storlekar eller objekt som delats upp i mindre delar och komma tillbaka till kontinuerlig matematik bakvägen, men de faktiska objekten som existerar, de är fortfarande diskreta. Byggnader, telefoner, klädesplagg, möbler, fordon, osv.

Vi kan också prata om olika beslut eller handlingar som diskreta. “Jag tog cykeln till campus idag” kontra “Jag tog inte cykeln till campus idag”. Vi kanske kan tänka oss en variant där vi cyklade en del av vägen och gick resten av vägen, men det kan vi tänka på som ett tredje alternativ. Vi kan alltså skapa diskreta strukturer genom att dela upp kontinuerliga fenomen (hur stor andel av vägen till campus cyklade jag) i olika delar som vi betraktar som likvärdiga. T.ex. kan vi i det enklaste fallet säga att vi har två möjliga alternativ. Vi tog inte cykeln alls, eller vi tog cykeln någon bit av vägen. Utöver det kan vi ha ett eller flera alternativ beroende på vad vi egentligen är intresserade av att modellera.

All matematik handlar nämligen om att bygga modeller och diskret matematik är alltså de delar av matematiken som hjälper oss att bygga modeller över diskreta fenomen. När vi behandlar människor, föremål, beslut, interaktion, kommunikation, osv. så handlar det väldigt ofta just om diskreta fenomen.

Relevans för programmering

Ett annat sätt att bygga modeller är programmering. Programmering och matematik är alltså, oavsett hur mycket vi önskar något annat, nära besläktade fenomen. Båda är sätt att bygga modeller och vi kan ofta använda trick från den ena typen av modellbyggande i den andra.

Många typer av beräkningsmässigt komplexa matematiska problem kan bara lösas med hjälp av datorer. Vi ska dock inte ge oss in på dessa mer avancerade grenar av modern matematik, utan vi ska hålla oss till några grundläggande koncept som kan hjälpa oss framöver.

Vi kommer främst prata om tre typer av diskreta strukturer i den här kursen:

• Tupler, som vi redan stött på i Python. Dvs. en ordnad samling av objekt.
• Mängder, som vi ska titta närmare på nu.
• Grafer, som vi kommer till lite längre fram i kursen.

Vi kommer också att titta på två typer av matematiska strukturer som i strikt mening inte är diskreta, vektorer och matriser.

Mängdlära (eng. set theory)

Mängdläran betraktas av många som den mest fundamentala grenen av matematik och kan sägas ligga till grund för åtminstone alla andra grenar inom den diskreta matematiken.

Mängdbegreppet (eng. set)

En mängd (eng. set) är en väldefinierad och oordnad samling av unika objekt. Väldefinierad betyder här att vi för varje möjligt objekt kan avgöra huruvida det ingår i mängden eller ej. Oordnad innebär att det inom ramarna för mängdläran inte finns någon inbördes ordning mellan objekten. Att objekten är unika innebär att ett objekt antingen ingår eller inte ingår i mängden, det kan inte ingå flera gånger. Objekt kan i det här sammanhanget vara precis vad som helst (inklusive andra mängder, vilket vi återkommer till längre ner).

I det kanske mest traditionellt matematiska fallet kan vi prata om olika talmängder, t.ex. heltalen, de rationella talen, eller de reella talen. Även om de reella talen är kontinuerliga så betraktas mängdläran som en del av den diskreta matematiken eftersom mängder i sig betraktas som diskreta strukturer. Dvs. två olika mängder är strikt åtskiljda matematiska objekt, även om deras innehåll inte är det.

Det kan också vara lite förvirrande att mängder per definition är oordnade när det första exemplet vi nämner är talmängder. Tal har ju självklart en ordning (1 kommer före 2, o.s.v.). Den här ordningen är dock inte en del av mängderna i sig utan ett separat matematiskt koncept som kallas just ordning.

Detta blir snabbt väldigt abstrakt och krångligt så vi tittar istället på något lite mer verklighetsnära, människor. Tal och talmängderna kommer dock dyka upp här och där i de följande avsnitten.

Säg att vi vill arbeta med mängden lärare i kursen 729G46. Detta beskriver vi normalt sett i matematisk notation på följande sätt:

$$\{Alva, Charlie, Elvira, Johan, Kacper, Simon\}$$

Våra namn används här bara som en representation av de faktiska personerna och vi som ingår i mängden kallas för mängdens element eller medlemmar.

En mängd är som sagt alltid oordnad, dvs. ordningen som elementen står i spelar ingen roll, och alla element är unika. Dvs. samma ting kan inte förekomma två gånger i samma mängd, antingen ingår tinget i mängden, eller så gör det inte det. Alltså gäller att:

$$\{Kacper, Simon\} = \{Simon, Kacper\} = \{Simon, Kacper, Simon\}$$

Men den sista mängden är egentligen inte korrekt utskriven eftersom Simon förekommer två gånger.

Andra typer av mängder som är relevanta inom kognitionsvetenskapen är t.ex. mängder av mentala tillstånd, kategorier av koncept och operationer på de koncepten, semantiska kategorier eller ordklasser inom lingvistik, osv.

Mängdbyggare (eng. set builder)

Vi kan också beskriva mängden lärare i kursen med en så kallad mängdbyggare:

$$\{\space p\space|\text{ där }p\text{ är en lärare i kursen 729G46 }\}$$

Detta uttryck beskriver samma mängd som när vi listade alla element i mängden. Vi kan alltså säga:

$$\{\space p\space|\text{ där }p\text{ är en lärare i kursen 729G46 }\} = \{Alva, Charlie, Elvira, Johan, Kacper, Simon\}$$

Namngivna mängder

Oftast vill vi slippa att skriva ut hela mängden vi arbetar med och vi kan därför ge mängden ett lämpligt namn och arbeta med det namnet istället.

Vi behöver några lämpliga mängder att arbeta med och för det kan vi använda vilka LiU-program lärarna på kursen läser eller har läst. Alla utom Johan har läst Kognitionsvetenskap och ingår i mängden vi kallar $M_{kogvet}$. Charlie och Johan har båda läst Innovativ Programmering (IP) och ingår i mängden vi kallar $M_{ip}$. Vi kallar också mängden ovan, med alla lärare i kursen, för $M_{a}$

$$\begin{align*} M_{kogvet} &= \{Alva, Charlie, Elvira, Kacper, Simon\}\\ M_{ip} &= \{Charlie, Johan\}\\ M_{a} &= \{Alva, Charlie, Elvira, Johan, Kacper, Simon\} \end{align*}$$

Det är viktigt att inse att $M_{kogvet}$ bara är ett namn vi valt i vår matematiska modell. I en annan situation, en annan modell, hade $M_{kogvet}$ kunnat vara mängden av alla studenter som läser kogvet, alla som har examen från kogvet, eller alla som någon gång arbetat inom fältet. I våra exempel nedan så representerar dock $M_{kogvet}$ de personer som arbetar som lärare i kursen 729G46 i år som har läst på kogvet.

(Vi kan alltså tänka på $M_{kogvet}$ ungefär som en variabel i Python. Vi kan också jämföra det med $x$ som antagligen betytt nästan lika många olika saker som antalet ekvationer vi löst på högstadiet och gymnasiet.)

Namngivna talmängder

För talmängderna vi nämnde först finns också etablerade namn som ofta används i formella beskrivningar av algoritmer eller vetenskapliga experiment. Att vara bekant med dessa och inte få hjärtsnörp när de dyker upp i en publikation man förväntas läsa och förstå är alltså praktiskt även om vi inte kommer arbeta specifikt med talmängderna.

* Ibland också kallade whole numbers vilket orsakar den svensktalande matematikstudenten snudd på oändlig huvudvärk.

** Det händer att de naturliga talen inte inbegriper $0$, inom datavetenskapen och mängdläran betraktar vi dock $0$ som ett naturligt tal. De naturliga talen kallas ibland också för räknetalen eller kardinaltalen eftersom de används för att räkna antal.

Den universella mängden eller universum (eng. universal set eller universe): $U$

Mängden av alla ting, ofta uttryckt som $U$, $\mathbb{U}$ eller $\mathcal{U}$. Normalt sett är det opraktiskt att arbeta med en faktisk mängd som innehåller alla ting (och rent matematiskt är det också ganska skakigt). Istället definierar vi normalt sett $U$ som alla ting som förekommer i vår aktuella modell. Handlar vår modell om personer så representerar $U$ helt enkelt alla personer som skulle kunna förekomma i modellen.

Den tomma mängden (eng. empty set eller void set): $\emptyset$

Oftast skrivet som $\emptyset$ men ibland som $\{\}$. Mängden som inte innehåller några element alls. Tomma mängden är unik, dvs. det finns per definition bara en enda tom mängd, och därför pratar vi alltid om tomma mängden i bestämd form.

Det är härifrån vi programmerare lånat konventionen att säga t.ex. “tomma strängen” om "" och “tomma listan” om [] i bestämd form även om vi i strikt mening kan lagra en tom lista eller tom sträng på flera ställen i minnet.

Kardinalitet (eng. cardinality): $|M|$

En viktig egenskap hos mängder är deras kardinalitet eller “storlek” (jämför med kardinaltalen, ett annat namn för de naturliga talen, som används för att räkna antal). I det enklaste fallet, hur många element som finns i mängden. Vi kan t.ex. säga att mängden lärare i 729G46 som läst på kogvet har kardinaliteten $5$ eftersom det är just 5 lärare i kursen som läst på kogvet.

Detta uttrycks i matematisk notation som

$$|\{Alva, Charlie, Elvira, Kacper, Simon\}| = 5$$

Eller mer kortfattat: $|M_{kogvet}| = 5$

Notera att detta är samma notation som används för att uttrycka absolutvärde/belopp, t.ex. $|-1| = 1$. Det händer därför att vissa säger “beloppet av en mängd” men detta är inte standardterminologi.

(Kardinaliteten hos talmängderna är, kanske självklart, oändligheten. Ett lite förvirrande faktum är dock att inte alla talmängder är lika stora. Dvs. det finns olika stora oändligheter. Denna insikt, och beviset för att det är sant, kommer från Georg Cantor som också kan sägas vara mängdlärans ursprungsman.)

Medlemskap (eng. membership): $\in$

I många fall är de mängder vi arbetar med för stora för att vi ska kunna skriva ut dem som vi gjorde ovan. Samtidigt vill vi kunna säga huruvida ett visst objekt tillhör eller inte tillhör en mängd och för det finns en särskild matematisk symbol: $\in$.

T.ex. kan vi säga att $Johan$ ingår i mängden $M_{a}$ utan att behöva skriva ut alla element i $M_{a}$ genom att skriva:

$$Johan\in M_{a}$$

På motsvarande sätt kan vi uttryckligen säga att ett visst ting inte finns i en mängd med $\notin$. T.ex. ingår $Johan$ i mängden av alla lärare men inte i mängden lärare i kursen 729G46 som läst på kogvet:

$$\begin{align*}Johan&\in M_{a}\\ Johan&\notin M_{kogvet}\end{align*}$$

Vi kan kombinera medlemskapsnotationen med mängdbyggare och talmängderna vi introducerade ovan för att t.ex. beskriva alla naturliga tal större än 2:

$$\{\space x \space| x \gt 2 \text{ och } x \in N\}$$

Ibland ser man också följande notation:

$$\{x \in N | x \gt 2 \}$$

Det är dock mer ovanligt annat än när vi talar just om delmängder av talmängder.

Delmängder: $\subseteq$ och $\subset$

I många fall vill vi prata om specifika delmängder av en större mängd. Vi har ju introducerat $M_{kogvet}$, $M_{ip}$ och $M_{a}$. Eftersom man måste vara lärare i kursen för att kunna vara en lärare i kursen som läst på kogvet så kan vi säga att $M_{kogvet}$ är en delmängd av $M_{a}$. Detta uttrycker vi i matematisk notation som:

$$ M_{kogvet} \subseteq M_{a} $$

Detta innebär att alla element i $M_{kogvet}$ också finns i $M_{a}$. Uttrycket i sig säger däremot inget om huruvida det finns några element i $M_{a}$ som inte existerar i $M_{kogvet}$, dvs. uttrycket innebär att mängderna kan vara lika med varandra (Ett annat sätt att se på det är att vi kan tänka att delmängdsoperatorn $\subseteq$ fungerar på samma sätt som operatorn $\leq$, dvs. “mindre än eller lika med”.)

Man kan också tänka på det som “för alla $x \in M_{kogvet}$ gäller att $x \in M_{a}$”. Dvs. alla lärare i kursen som läst på kogvet är också lärare i kursen.

Oftast räcker det att veta om en mängd A är en delmängd av en annan mängd B (och alltså kan vara lika med B). Ibland vill vi dock säga att något är en strikt delmängd, dvs. att det finns minst ett element i den större mängden som inte existerar i den mindre mängden. Det kan vi uttrycka som:

$$M_{kogvet} \subset M_{a}$$

Båda delmängdsuttrycken ovan är dock sanna, det andra är bara lite mer specifikt.

Vi kan självklart också säga att en mängd inte är en delmängd av en annan mängd genom att använda $\not\subseteq$. T.ex. gäller att

$$ M_{ip} \not\subseteq M_{kogvet} $$

eftersom $Johan$ förekommer i $M_{ip}$ men inte i $M_{kogvet}$. Dvs. inte alla lärare i kursen som läst på IP har också läst på kogvet.

En viktig regel är att tomma mängden, $\emptyset$, är en delmängd av alla andra mängder.

Delmängdskonceptet är fundamentalt för många statistiska metoder som ni kommer stöta på i framtida kurser. Detta eftersom ett slumpvis utvalt sample utgör en delmängd av den population man studerar och detta grundantagande är vad allt annat vilar på.

Delmängdskonceptet är också centralt för hur mänsklig kognition fungerar, där vi ofta har mentala kategorier av koncept som kan delas in i mindre och mindre delmängder. Allt från mentala tillstånd till kategorier av objekt i vår omvärld.

Vi kan också uttrycka syllogismer i termer av mängdlära och då ofta i termer av medlemskap och delmängder. T.ex. är kanske den mest kända syllogismen av alla “Alla människor är dödliga. Sokrates är människa. Alltså är Sokrates dödlig.” Vi kan uttrycka det i termer av mängder som:

$$ Människor \subseteq Dödliga, Sokrates \in Människor \Rightarrow Sokrates \in Dödliga $$

Här ser vi förhoppningsvis hur mycket av det vi kallar för förnuft och logiskt tänkande som vilar på en informell och kanske till och med intuitiv mängdlära.

Potensmängd: $\mathcal{P}(M)$

Potensmängden $\mathcal{P}(M)$ (ibland $\mathbb{P}(M)$ eller $2^M$) av en mängd $M$ är mängden av alla delmängder till mängden. Dvs. det är en mängd vars medlemmar själva är mängder. Potensmängden av t.ex. $M_{ip}$ är:

$$ \mathcal{P}(M_{ip}) = \{\{\}, \{Charlie\}, \{Johan\}, \{Charlie, Johan\}\} $$

Notera att både tomma mängden $\emptyset$ och $M_{ip}$ själv ingår i potensmängden. Detta beror på att att det inte bara är strikta delmängder som ingår i potensmängden utan alla delmängder.

För kardinaliteten av potensmängden gäller följande samband:

$$|\mathcal{P}(M)| = 2^{|M|}$$

Kan du lista ut varför?

Potensmängden dyker upp inom områden som t.ex. symbolisk maskininlärning där vi kan prata om en hypotesrymd som består av potensmängden av alla möjliga regler systemet skulle kunna lära sig. Detta är om inte annat en bra förklaring till varför maskininlärning länge var ett beräkningsmässigt omöjligt problem. För varje ny potentiell regel dubbleras storleken av hypotesrymden så att lära sig den korrekta uppsättningen regler blir snabbt omöjligt.

Även inom beslutsfattande dyker potensmängden upp som mängden av möjliga kombinationer av delbeslut. Det blir snabbt omöjligt för en person att utvärdera alla alternativ och en viktig kompetens för kognitionsvetare är att förstå den här komplexiteten och hur system, digitala såväl som organisatoriska, kan byggas för att hjälpa människor att överkomma eller hantera den.

Venn-diagram

Ett vanligt sätt att illustrera mängder är med så kallade Venn-diagram. Ett Venn-diagram representerar varje mängd som en form, oftast cirklar, med element utritade på ett sådant sätt att det syns vilka mängder varje element tillhör. I bilden till höger kan vi se ett Venn-diagram över $M_{kogvet}$ och $M_{ip}$. Vi ser att Charlie är placerad så att han ingår både i cirkeln för kogvet och för IP.

Ofta används Venn-diagram för att indikera vilka delar som ett visst mängduttryck representerar. Detta är särskilt användbart när man arbetar med 3 eller 4 mängder. Vi kommer nedan använda detta Venn-diagram för att illustrera hur de olika mängdoperationerna fungerar.

Mängdoperationer

Precis som den vanliga aritmetiken har de fyra räknesätten så finns det olika “räknesätt” för mängder. Dessa kallas för mängdoperationer (eng. set operations).

Union (eng. union): $\cup$

Unionen av två mängder $A$ och $B$ uttrycks som $A \cup B$ och innehåller alla element som förekommer i någon av $A$ och $B$.

$$M_{kogvet} \cup M_{ip} = \{Alva, Charlie, Elvira, Kacper, Simon, Johan\}$$

Precis som med vanlig addition så spelar ordningen ingen roll. Formellt säger vi att union och addition båda är kommutativa operationer. Vi kan därför också ta unionen av flera mängder samtidigt utan att behöva oroa oss över vilken ordning vi skriver.

Mängdlärans union jämförs ofta med satslogikens och digitalteknikens OR-operator $\lor$ (den logiska operatorn or i Python). Vi kan uttrycka unionen mellan två mängder med hjälp av notationen vi sett ovan samt denna logiska operator:

$$A \cup B = \{ x\space|\space x \in A \lor x \in B\}$$

Unioner kan också betraktas som ett sätt att generalisera eller kombinera kategorier. Tidiga modeller av kognition antog att vi människor hanterade koncept på just det här sättet. Idag vet vi att vi människor tvärt om har förhållandevis svårt att hantera resonemang byggda på unioner. Varför och hur vi hanterar det är fortfarande ett öppet forskningsområde inom kognitiv psykologi och kognitiv modellering.

På en annan nivå kan vi också modellera perceptionsstörningar och missförstånd när vi skiftar uppmärksamheten från en sak till en annan i termer av unioner av orelaterade sinnesintryck som därför sammanblandas. Detta kan kontrasteras mot att vi också utnyttjar unioner av sinnesintryck av olika modaliteter, t.ex. syn och hörsel, för att göra så kallad “feature integration” och bilda koherenta tolkningar av vår omvärld.

Snitt (eng. intersection): $\cap$

Snittet av två mängder $A$ och $B$ uttrycks som $A \cap B$ och innehåller alla element som förekommer i både $A$ och $B$.

$$M_{kogvet} \cap M_{ip} = \{Charlie\}$$

dvs. eftersom bara Charlie har läst både Kognitionsvetenskap och Innovativ Programmering så är han den enda som ingår i snittet.

Snitt är också en kommutativ operation, dvs. ordningen spelar ingen roll och vi kan ta snittet av fler än 2 mängder samtidigt utan att oroa oss över ordningen.

Mängdlärans snitt jämförs ofta med satslogikens och digitalteknikens AND-operator $\land$ (den logiska operatorn and i Python). Vi kan uttrycka snittet mellan två mängder med hjälp av notationen vi sett ovan samt denna logiska operator:

$$A \cap B = \{ x\space |\space x \in A \land x \in B\}$$

Två mängder vars snitt är tomma mängden, dvs. som inte har några gemensamma element, kallas för disjunkta mängder (eng. disjoint sets). De delar av statistiken som inte vilar på antaganden om delmängdsförhållanden vilar ofta istället på antaganden om disjunkta data. Dvs. att inga mätpunkter/försöksdeltagare/etc. förekommer i flera mängder.

Vi kan också prata om disjunkta mängder när vi analyserar sociala nätverk (i verkligheten såväl som på internetplattformar). Om vi har en mängd som representerar person As bekantskapskrets och en mängd personer som utgör person Bs bekantskapskrets så är mängderna disjunkta om A och B inte har några gemensamma bekanta. Omvänt så utgörs ett eventuellt snitt mellan mängderna av As och Bs gemensamma bekanta som då också kan betraktas som ett gränssnitt mellan A och B genom vilket information kan flöda dem emellan.

Komplement (eng. complement): $M^\complement$ eller $\overline{M}$

Komplementet till en mängd $A$ uttrycks som $A^\complement$ eller $\overline{A}$ och består av alla element i universum som inte ingår i $A$.

$$\overline{M_{kogvet}} = {M_{kogvet}}^\complement = \{Johan\}$$

Eftersom Johan är den enda i vår modell som inte läst Kognitionsvetenskap. Notera dock att om det funnits ytterligare några personer i vår modell som inte ingick i någon av $M_{kogvet}$ eller $M_{ip}$ så hade de ingått i komplementet till $M_{kogvet}$. Vi kan se det illustrerat i bilden till höger där även utrymmet runt cirklarna är markerat.

Mängdlärans komplement jämförs ofta med satslogikens och digitalteknikens NOT-operator $\lnot$ (den logiska operatorn not i Python). Vi kan uttrycka komplementet till en mängd med hjälp av notationen vi sett ovan samt denna logiska operator:

$$\begin{align*} A^\complement &= \{ x\space |\space \lnot (x \in A)\}\\ &\text{ eller } \\ A^\complement &= \{ x\space |\space x \notin A\} \end{align*}$$

Differens (eng. difference): $\setminus$

Differensen, eller relativa komplementet, mellan två mängder $A$ och $B$ uttrycks som $A \setminus B$ är alla element som ingår i $A$ utom de som också ingår i $B$.

$$M_{kogvet} \setminus M_{ip} = \{Alva, Elvira, Kacper, Simon\}$$

dvs. Alva, Elvira, Kacper och Simon har läst Kognitionsvetenskap, men inte IP.

Differens, precis som den differens vi är vana vid från den vanliga aritmetikens subtraktion (minus), är inte en kommutativ operation. Dvs. vi måste vara noggranna med ordningen. Precis som i vanlig algebra eller i programmering så kan vi använda parenteser för att indikera i vilken ordning saker ska beräknas.

Symmetrisk differens (eng. symmetric difference): $\vartriangle$

Ibland är det meningsfullt att prata om den symmetriska differensen mellan två mängder. Den symmetriska differensen kan uttryckas på flera sätt men vi kan t.ex. se det som unionen av mängdernas differenser, eller som differensen mellan mängdernas union och snitt. Alltså:

$$ \begin{align*} M_{kogvet} &\vartriangle M_{ip} = \\ (M_{kogvet} \setminus M_{ip}) &\cup (M_{ip} \setminus M_{kogvet}) = \\ (M_{kogvet} \cup M_{ip}) &\setminus (M_{ip} \cap M_{kogvet}) = \\ \{Alva, Elvira, Jo&han, Kacper, Simon\} \end{align*} $$

Dvs. alla utom Charlie ingår i den symmetriska differensen.

I många vetenskapliga studier vill vi på ett eller annat sätt studera skillnader mellan mängder av datapunkter. De data vi då är mest intresserade av är ju just den symmetriska differensen av egenskaper mellan mängderna. Dvs. vi är mindre intresserade av vad mängderna har gemensamt än av vad som skiljer dem, så att vi kan studera varför.

Mer konkret kan det handla om att t.ex. studera vilka attityder och beteenden som skiljer mellan två grupper av försöksdeltagare.

Vi kan också prata om symmetrisk differens som ett sätt att forma mentala distinktioner mellan kategorier av föremål. Det som definierar skillnaden mellan koncepten är ju just den symmetriska diffferensen.

Mängder i python

I Python indikeras mängder på samma sätt som inom matematiken, dvs.inom “måsvingar”. Mängden

$\{1, 2, 3\}$

skrivs alltså precis likadant i Python, dvs.

{1, 2, 3}

Vi kan också skapa en mängd av en sekvens med hjälp av set , t.ex.:

>>> set([1, 2, 3, 1])
{1, 2, 3}
>>> set("abcba")
{'c', 'b', 'a'}

Notera att eventuella dubletter försvinner eftersom alla element i en mängd per definition är unika.

Vi måste alltid använda set() om vi vill skapa en tom mängd eftersom {} representerar något annat:

>>> type({})
<class 'dict'>
>>> type(set())
<class 'set'>
>>> type(set())
<class 'set'>

Vi kommer återvända till dict i tema 3.

När vi istället för numeriska värden har symboler, t.ex. namn, i mängden så kan dessa i Python uttryckas som strängar. Dvs. mängden

$\{Alva, Charlie, Elvira, Johan, Kacper, Simon\}$

skrivs i Python som

{'Alva', 'Charlie', 'Elvira', 'Johan', 'Kacper', 'Simon'}

Viktigt att inse dock är att detta bara är ett möjligt sätt att beskriva personer i kod. Om mängden egentligen representerar oss lärare som personer, inte bara våra förnamn, så kanske t.ex. personnummer hade varit en bättre representation.

En viktig begränsning i Python jämfört med matematiken är att vi inte på ett enkelt sätt kan beskriva mängder utan att räkna upp eller generera deras medlemmar. Vi kan alltså inte på ett enkelt sätt definiera t.ex. en mängd $M_P$, bestående av alla personer som är personal på LiU, utan en massa extra kod som läser in alla anställda från något personalregister.

De olika egenskaperna, relationerna och mängdoperationerna vi beskrev ovan hade ju speciell matematisk notation som vi i många fall inte hittar på ett vanligt tangentbord. Istället används andra symboler som oftast har ett beteende liknande det beteende de har för andra datatyper.

För att undersöka objekt och mängders relationer till varandra kan vi använda jämförelseoperatorer motsvarande delmängds- och medlemskapsrelationerna. Dessa evaluerar till ett sanningsvärde och kan användas t.ex. i en villkorssats:

För att bearbeta mängder:

* Notera att vi explicit måste säga vad universum är för att kunna beräkna ett komplement i Python:

Har vi ett uttryck som $(A \cap B) \cup C^C$ så måste vi alltså göra något i stil med följande i Python:

1
2
3
4
5

# Universe is union of all sets
U = A | B | C
C_complement = U - C
# The full expression
(A & B) | C_complement

Detta går såklart att slå ihop på en rad, men det blir väldigt krångligt att läsa och förstå:

(A & B) | ((A | B | C) - C)

OBS! Notera att eftersom mängder per definition är oordnade så är set i Python inte heller en sekvens. Vi kan iterera över elementen i en mängd men det är inte garanterat vilken ordning elementen kommer när vi gör en sådan iteration eller att vi får samma ordning varje gång. Vi kan inte heller använda subskript eller prata om index eller slice eftersom det inte finns någon egentlig ordning mellan elementen.

Exempel i Python

Skapa mängderna $M_{kogvet}$ och $M_{ip}$ och beräkna deras kardinaliteter (antalet element i dem):

>>> M_kogvet = {'Alva', 'Charlie', 'Elvira', 'Kacper', 'Simon'}
>>> M_ip = {'Charlie', 'Johan'}
>>> len(M_kogvet)
5
>>> len(M_ip)
2

Kontrollera ifall $M_{ip} \subseteq M_{kogvet}$, dvs. huruvida alla som läst på IP också har läst på Kogvet:

>>> M_ip <= M_kogvet
False

Kontrollera ifall $M_{ip} \subseteq M_{ip}$, dvs. är $M_{ip}$ en delmängd av sig själv:

>>> M_ip <= M_ip
True

Kontrollera ifall $M_{ip} \subset M_{ip}$, dvs. är $M_{ip}$ en strikt delmängd av sig själv:

>>> M_ip < M_ip
False

Beräkna snittet, $M_{kogvet} \cap M_{ip}$:

>>> M_ip & M_kogvet
{'Charlie'}

Beräkna unionen, $M_{kogvet} \cup M_{ip}$:

>>> M_ip | M_kogvet
{'Charlie', 'Simon', 'Elvira', 'Johan', 'Kacper', 'Alva'}

Beräkna differensen $M_{kogvet} \setminus M_{ip}$:

>>> M_kogvet - M_ip
{'Kacper', 'Alva', 'Simon', 'Elvira'}

Beräkna differensen $M_{ip} \setminus M_{kogvet}$, dvs. mängden av personer som läst på IP men inte på Kogvet:

>>> M_ip - M_kogvet
{'Johan'}

Quiz

Testa din förståelse av materialet med tillhörande quiz.