Göm menyn

TDDC75 Diskreta strukturer

Temamål


Diskret matematik: Du skall veta vad en mängd är och behärska mängdnotationen. Du skall kunna de olika likhetsbegreppen för mängder (likhet, delmängd, äkta delmängd, disjunkta mängder) och de vanligaste mängdoperationerna, som union, snitt, differens, komplement, potensmängd. Du skall kunna visa mängdteoretiska lagar, samt ha kännedom om Venndiagram. Du skall kunna göra enkla induktiva definitioner av mängder. Du skall känna till vad som menas med en mängds kardinalitet.
     Du skall veta vad ett par och en tupel är, och kunna ta Kartesiska produkten av mängder. Du skall veta vad en relation är och behärska olika notationen för relationer. Du skall kunna utföra operationer som invers och sammansättning på relationer, och veta vad identitetsrelationen är. Du skall veta vad grundläggande egenskaper som reflexivitet, transitivitet, symmetri och anti-symmetri är och kunna visa att relationer har/inte har dessa egenskaper. Du skall kunna ta reflexiva/transtiva/symmetriska höljet av en relation. Du skall kunna känna igen en partialordning, totalordning och en ekvivalensrelation, samt känna till vad som menas med minimala/maximala element, minsta/största element, ekvivalensklass och partition. Du skall ha kännedom om Hassediagram samt riktade grafer.
     Du skall veta vad en funktion, domän och värdemängd är, samt behärska notationen för funktioner. Du skall kunna definiera en funktion induktivt. Du skall veta vad som menas med injektiv, surjektiv och bijektiv och inversen av en funktion. Du skall även veta vad som menas med kommutativ, associativ och distributiv, och kunna sätta samman två funktioner. Du skall ha kännedom om partiella funktioner.
     Du skall veta vad en boolesk algebra är; speciellt den binära booleska algebran. Du skall kunna utföra enkla beräkningar med hjälp av algebrans lagar och ska kunna ta fram konjunktiv och disjunktiv normalform för en boolesk funktion.
       Du skall veta vad en sträng och ett språk är, samt kunna utföra enkla operationer som konkatenering av strängar. Du förväntas  känna till vad ett talsystem är; speciellt decimala, binära och hexadecimala talsystemen för heltal. Du skall kunna översätta mellan de olika talsystemen och kunna addera binära tal och ta tvåkomplementet av ett naturligt tal.
       Du skall kunna göra enkla bevis av egenskaper för ovanstående begrepp inklusive utföra enkla induktiva bevis.

Digitalteknik: Digitalteknik är hur vi kan bygga nät med önskad funktionalitet med grindar och vippor. Grindarna implementerar logiska funktioner. I digitalteknik arbetar vi endast med digitala signaler ("ettor och nollor"). Verkligheten är dock ofta analog. Därför behöver vi omvandling från analoga signaler till digitala signaler och tvärt om (A/D och D/A omvandlare). Figuren nedanför visar hur ett digitalt system kan se ut.


Digitala system finns överallt i vår vardag, t.ex. i datorer, bilar, telefoner, kylskåp, fjärrkontroller och tv. I kombinatoriska nät beror utsignalerna endast av insignalernas ögonblicksvärden. I sekvensnät beror utsignalerna inte endast på insignalernas ögonblicksvärden utan även på insignalernas tidigare värden. För att sekvensnätet ska komma ihåg insignalernas tidigare värden måste vippor användas. För realisera kombinatoriska nät och sekvensnät kan följande algoritmer användas:
     För att realisera ett kombinatoriskt nät gör man på följande sätt:

  1. Ta fram ett logiskt uttryck från en verbal beskrivning.
  2. Förenkla det logiska uttrycket med hjälp av en grafisk förenklingsmetod.
  3. Rita det förenklade uttrycket med önskade grindar.
För att realisera ett sekvensnät gör man på följande sätt:
  1. Rita upp en tillståndsgraf över systemets beteende.
  2. Använd en metod för att från tillståndsgrafen ta fram ett logiskt uttryck.
  3. Använd en grafisk förenklingsmetod för att förenkla det logiska uttrycket.
  4. Rita upp det förenklade uttrycket med vippor och önskade grindar .

Efter kursen ska du utifrån en verbal beskrivning kunna realisera kombinatoriska nät, sekvensnät samt iterativa kombinatoriska nät på ett metodiskt sätt. Med metodisk menas bl.a. att:
  • Du ska kunna använda dig av metoderna för syntes av sekvensnät: tillståndsgraf (Mealy/Moore), tillståndstabell, kodning av tillstånd, flödestabell, tillståndsminimering.
  • Du ska kunna minimera booleska uttryck av upp till fem variabler med hjälp av Karnauhgdiagram. Du ska även kunna hantera karnaughdiagram med ofullständigt specificierade funktioner.
  • Du ska kunna minimera randcellarna i ett iterativt kombinatoriskt nät.

Du ska även kunna realisera kombinatorska nät med hjälp av grindtyperna OR, AND, NOT, EXOR, NAND och NOR, samt använda dig av olika speciella kombinatoriska nät,såsom adderare, komparator, avkodare, demultiplexer och multiplexer. Du ska kunna använda dig av klockade vippor av typerna D, JK, SR och T. Du ska även kunna realisera sekvensnät med användning av speciella sekvesnät, som t.ex. räknare och skiftregister. Du ska kunna analysera och verifiera kombinatoriska nät, sekvensnät samt iterativa kombinatoriska nät. Du ska känna till och kunna använda olika talkodningar samt även felupptäckande/felrättande kod. Du ska känna till vad programmerbar logik är och kunna skilja på vad PLA och PAL är. Du ska känna till grindutgångstyperna tristate, öppen kollektor samt totempole. Du ska kunna använda dig av NAND och inverterare med öppen kollektorutgång (trådade grindar). Du ska kunna konstruera en avstudsare samt en enpulsare med hjälp av grindar och vippor.

Sidansvarig: Mikael Asplund
Senast uppdaterad: 2023-06-29