Logiske metoder

• Logiske metoder: Kunsten å tenke abstrakt og matematisk, Universitetsforlaget, 2014
• Studiebok til Logiske metoder, Universitetsforlaget, 2017

Innholdsfortegnelse

• 0. Kunsten å tenke abstrakt og matematisk
  Abstraksjon Resonnering om sannhet Antakelser Språk Definisjoner Bevis Problemløsning og Pólyas heuristikker
• 1. Grunnleggende mengdelære
  I dette kapitlet lærer du grunnleggende begreper og notasjon i mengdelære, hva en mengde er, hvilke operasjoner vi har på mengder, som snitt, union og mengdedifferanse, og hvordan mengder kan konstrueres og sammenliknes, samt hva tupler og kartesisk produkt er.

  Innhold Første steg Hva er en mengde? Konstruksjon av mengder Operasjoner på mengder Visualisering av mengder Sammenlikninger av mengder Tupler og produkter Multimengder
• 2. Utsagnslogikk
  I dette kapitlet lærer du om hva som ligger i begrepet utsagn, å kunne representere utsagn på en god måte ved hjelp av utsagnslogiske formler og å forstå sammenhengen mellom utsagn -- atomære utsagn som settes sammen ved hjelp av logiske bindeord -- og formler -- utsagnsvariabler som settes sammen ved hjelp av konnektiver. Du lærer også om begrepene nødvendig og tilstrekkelig og noen praktiske forkortelser.

  Innhold Hva er det som følger fra hva? Hva er et utsagn? Atomære og sammensatte utsagn Atomære og sammensatte formler Nødvendige og tilstrekkelige betingelser Parenteser, presedensregler og praktiske forkortelser
• 3. Semantikk for utsagnslogikk
  I dette kapitlet lærer du semantikk for utsagnslogikk, det vil si hvordan vi systematisk kan gi tolkninger av utsagnslogiske formler. En tilordning av sannhetsverdier til utsagnsvariabler gir opphav til en valuasjon, og denne gir sannhetsverdier til alle formler. Du lærer om sannhetsverditabeller, et verktøy for å utforske valuasjoner, om begrepet logisk ekvivalens og noen kjente logiske ekvivalenser.

  Innhold Tolkning av formler Valuasjoner og sannhetsverditabeller Egenskaper ved implikasjon Logisk ekvivalens Et studium i hva som er ekvivalent
• 4. Utsagnslogiske begreper
  I dette kapitlet lærer du mer semantikk for utsagnslogikk, blant annet begrepet logisk konsekvens. Et gyldig argument er et hvor konklusjonen er en logisk konsekvens av premissene. Du lærer også om begrepene oppfyllbar, falsifiserbar, gyldig og kontradiktorisk, og hvordan disse henger sammen.

  Innhold Logisk konsekvens Gyldige argumenter Oppfyllbarhet og falsifiserbarhet Tautologi/gyldighet og motsigelse/kontradiksjon Symboler for sannhetsverdiene Sammenhenger mellom begreper Uavhengighet av formler Avgjøre om en formel er gyldig eller oppfyllbar
• 5. Bevis, formodninger og moteksempler
  I dette kapitlet lærer du noen bevismetoder og blir kjent med sammenhengene mellom bevis, formodninger og moteksempler. Målet er å bli bedre til å bevise påstander selv. Flere vanlige bevismetoder diskuteres: direkte bevis, eksistensbevis, bevis for universelle påstander, kontrapositive bevis, motsigelsesbevis, bevis for at noe ikke er sant, bevis ved tilfeller, samt forskjellen mellom konstruktive og ikke-konstruktive bevis.

  Innhold Bevis Formodninger Tenke ut fra antakelser Direkte bevis Eksistensbevis Bevis ved tilfeller Bevis for universelle påstander Moteksempler Kontrapositive bevis Motsigelsesbevis Konstruktive versus ikke-konstruktive bevis Bevis for at noe ikke er sant
• 6. Relasjoner
  Målet med dette kapitlet er å forstå hva relasjoner er, samt bli kjent med de viktigste egenskapene relasjoner kan ha, som refleksivitet, symmetri, transitivitet, anti-symmetri og irrefleksivitet. Du lærer også om hva som gjør at en relasjon er en ekvivalensrelasjon, en partiell ordning og en total ordning.

  Innhold Abstraksjon over relasjoner Noen spesielle relasjoner Universet av relasjoner Refleksivitet, symmetri og transitivitet Anti-symmetri og irrefleksivitet Ordninger, partielle og totale Eksempler
• 7. Funksjoner
  I dette kapitlet lærer du om hva funksjoner er, samt om de viktigste begrepene knyttet til funksjoner, som at de kan være injektive, surjektive og bijektive. Du lærer også om funksjoner med flere argumenter, hvordan funksjoner kan settes sammen, hva operasjoner er, og hvordan funksjoner kan være objekter.

  Innhold Hva er en funksjon? Injektive, surjektive og bijektive funksjoner Funksjoner med flere argumenter Universet av funksjoner Sammensetning av funksjoner Operasjoner Funksjoner som objekter Partielle funksjoner
• 8. Litt mer mengdelære
  I dette kapitlet lærer du litt mer mengdelære. Du lærer om den universelle mengden, komplementet til mengder, potensmengder og mer om Venn-diagrammer. Til slutt snakker vi om uendelighet, kardinalitet og begrepene tellbar og overtellbar.

  Innhold Mengdelære Mengdekomplementet og den universelle mengden Regne med Venn-diagrammer Venn-diagrammer for flere mengder Potensmengder Uendelighet Kardinalitet Tellbarhet Overtellbarhet
• 9. Tillukninger og induktivt definerte mengder
  I dette kapitlet lærer du om tillukninger, både av mengder og relasjoner, og hvordan mengder kan konstrueres induktivt. Vi ser på hvordan en rekke mengder defineres induktivt på denne måten: tallmengder, bitstrenger, utsagnslogiske formler, lister og binære trær og programmeringsspråk. I tillegg blir vi kjent med alfabeter, strenger og hvordan formelle språk kan defineres induktivt.

  Innhold Definere mengder steg for steg Tillukninger av mengder Tillukninger av binære relasjoner Induktivt definerte mengder Tallmengder Utsagnslogiske formler Lister og binære trær Programmeringsspråk Alfabeter, tegn, strenger og formelle språk Bitstrenger To interessante konstruksjoner
• 10. Rekursive funksjoner
  I dette kapitlet lærer du om hva rekursive funksjoner er og hvordan disse er basert på induktivt definerte mengder. Vi definerer rekursive funksjoner på en rekke mengder: tallmengder, bitstrenger, utsagnslogiske formler, lister, binære trær og formelle språk.

  Innhold Et kraftig verktøy De triangulære tallene Induksjon og rekursjon Form, innhold og plassholdere Bytte likt med likt Rekursive funksjoner Tallmengder Bitstrenger Utsagnslogiske formler Lister Binære trær Formelle språk Rekursjon og programmering
• 11. Matematisk induksjon
  I dette kapitlet lærer du om matematisk induksjon, en kraftig og nyttig bevismetode for påstander om naturlige tall. Du får se mange eksempler på bruk av induksjonsbevis og lærer om hvordan rekursive funksjoner og induksjonbevis er relatert til hverandre. Du lærer også om det matematiske spillet Hanois tårn og hvordan dette kan analyseres ved hjelp av rekursive funksjoner og induksjonbevis.

  Innhold Et matematisk eksperiment Matematisk induksjon Tilbake til eksperimentet Et geometrisk bevis for den samme påstanden Hva er det egentlig som foregår i et induksjonsbevis? Trominoer Egenskaper ved rekursive funksjoner Hanois tårn Mer summering av tall Begrunnelser og sterk induksjon
• 12. Strukturell induksjon
  I dette kapitlet lærer du om strukturell induksjon, en generalisering av matematisk induksjon som fungerer for alle induktivt definerte mengder. Du lærer å bruke denne metoden til å bevise påstander om bitstrenger, utsagnslogiske formler, lister og binære trær.

  Innhold Strukturell induksjon Strukturell induksjon på bitstrenger Strukturell induksjon på utsagnslogiske formler Strukturell induksjon på lister Strukturell induksjon på binære trær
• 13. Førsteordens språk
  I dette kapitlet lærer du om syntaksen til førsteordens logikk. Du lærer om førsteordens språk, logiske og ikke-logiske symboler, konstant-, funksjons- og relasjonssymboler, signaturer, termer, formler og presedensregler.

  Innhold Språk med større uttrykkskraft Førsteordens språk og signaturer Førsteordens termer Prefiks-, infiks- og postfiksnotasjon Førsteordens formler Presedensregler
• 14. Representasjon av kvantifiserte utsagn
  I dette kapitlet lærer du om predikater, egenskaper knyttet til frie variabler og hvordan førsteordens språk kan brukes til å representere kvantifiserte utsagn.

  Innhold Representasjon av predikater Syntaktiske egenskaper knyttet til frie variabler Kunsten å uttrykke seg med et førsteordens språk Valg av førsteordens språk Mønstre som går igjen i representasjoner Repetisjon av førsteordens språk Uttrykkskraft og kompleksitet
• 15. Tolkning i modeller
  I dette kapitlet lærer du om semantikken til førsteordens logikk: hva modeller er og hvordan disse brukes til å tolke førsteordens termer og formler. Du lærer om hvordan substitusjoner brukes i tolkningen av kvantifiserte formler, samt om begrepene gyldig, oppfyllbar, kontradiktorisk og falsifiserbar.

  Innhold Semantikk for førsteordens logikk Definisjon av modeller Tolkning av termer Tolkning av atomære formler Substitusjoner Tolkning av sammensatte formler Oppfyllbarhet og gyldighet av førsteordens formler Førsteordens språk og likhet Litt repetisjon
• 16. Resonnering om modeller
  I dette kapitlet lærer du mer om modeller i førsteordens logikk. Du lærer om logisk ekvivalens og konsekvens, samspillet mellom kvantorene og konnektivene, modellering, teorier og aksiomatiseringer, samt litt om preneks normalform.

  Innhold Logisk ekvivalens og logisk konsekvens Samspillet mellom kvantorer og konnektiver Førsteordens logikk og modellering Teorier og aksiomatiseringer Noen tekniske spesialtilfeller Preneks normalform og flere ekvivalenser Avsluttende kommentarer
• 17. Abstraksjon med ekvivalenser og partisjoner
  I dette kapitlet lærer du om hvordan ekvivalensrelasjoner, ekvivalensklasser og partisjoner er relatert til hverandre, og hvordan disse kan brukes til å abstrahere.

  Innhold Abstrahere med ekvivalensrelasjoner Ekvivalensklasser Partisjoner Sammenhengen mellom ekvivalensklasser og partisjoner
• 18. Kombinatorikk
  I dette kapitlet lærer du grunnleggende kombinatorikk. Vi går gjennom noen grunnleggende regneprinsipper, som inklusjon-og-eksklusjonsprinsippet og multiplikasjonsprinsippet, og definerer permutasjoner, ordnet utvalg, kombinasjoner og binomialkoeffisientene.

  Innhold Kunsten å telle Inklusjon-og-eksklusjonsprinsippet Multiplikasjonsprinsippet Permutasjoner Ordnet utvalg Kombinasjoner Gjentakelser og overtelling
• 19. Litt mer kombinatorikk
  I dette kapitlet lærer du litt mer om kombinatorikk. Vi snakker mer om binomialkoeffisientene, og gjennomgår et eksempel i detalj som leder oss til Pascals trekant. Til slutt ser vi på hvordan opptellingsproblemer kan systematiseres.

  Innhold Pólyas eksempel og Pascals trekant Binomialkoeffisienter Systematisering av opptellingsproblemer
• 20. Litt abstrakt algebra
  I dette kapitlet lærer du noen begreper fra abstrakt algebra, spesielt litt mer om relasjoner og funksjoner. Vi snakker om inverse relasjoner og funksjoner, noen egenskaper ved operasjoner, som kommutativ, assosiativ og idempotent, og noen egenskaper ved elementer, som at de kan være identitetselementer og inverse elementer. Til slutt ser vi på hva en gruppe er.

  Innhold Abstrakt algebra Inverse relasjoner og funksjoner Noen egenskaper ved operasjoner Noen elementer med spesielle egenskaper Grupper
• 21. Grafteori
  I dette kapitlet lærer du grunnleggende grafteori. Her definerer vi grafer, kanter og noder, samt terminologi for å snakke om og kategorisere grafer på en presis måte. Du lærer litt om rettede grafer, komplette grafer og komplementet til grafer. Du lærer også om to grafteoretiske resultater som gjelder gradene til nodene i en graf. Til slutt ser vi på hva det vil si at grafer er isomorfe.

  Innhold Grafer er overalt Hva er en graf? Grafer som representasjoner Definisjoner og begreper om grafer Egenskaper ved grafer To grafteoretiske resultater Isomorfier
• 22. Vandringer i grafer
  I dette kapitlet lærer du mer om grafteori, spesielt om forskjellige måter å gå rundt i grafer på. Her defineres vandringer, stier, kretser, sykler og trær. Via disse begrepene lærer du mer om grunnleggende egenskaper grafer kan ha.

  Innhold Königsbergs broer Stier og kretser Euler-veier og Euler-kretser Hamilton-stier og Hamilton-sykler Avsluttende kommentarer
• 23. Formelle språk og grammatikker
  I dette kapitlet lærer du mer om formelle språk. Du lærer om forholdet mellom regulære språk og regulære uttrykk, hvordan deterministiske tilstandsmaskiner kan brukes til å karakterisere regulære språk, og til slutt litt om regulære og kontekstfrie grammatikker.

  Innhold Formell språkteori Operasjoner på språk Regulære språk Regulære uttrykk Tolkning av regulære uttrykk Deterministiske tilstandsmaskiner Tilstandsmaskiner og regulære språk Ikke-deterministiske tilstandsmaskiner Formelle grammatikker
• 24. Naturlig deduksjon
  I dette kapitlet lærer du en logisk kalkyle som kalles naturlig deduksjon. Denne kalkylen er en formalisering av logisk resonnering og kan brukes til å lage utledninger og bevis for utsagnslogiske formler. Du lærer også mer om forholdet mellom syntaks og semantikk via begrepene sunnhet, kompletthet og konsistens.

  Innhold Logiske kalkyler: fra semantikk til syntaks Slutningsreglene i naturlig deduksjon Lukking av antakelser Utledninger og bevis Negasjon og RAA Reglene for disjunksjon Sunnhet, kompletthet og konsistens
• Veien videre
  Takk for følget Noen boktips Klassikerne Introduksjonsbøker til matematisk tenkning Introduksjonsbøker til logikk Introduksjonsbøker til diskret matematikk Populærvitenskap, rekreasjonell matematikk og andre bøker

Universitetsforlagets lærebokpris

Les mer på nettsidene til Universitetsforlaget.

Bla i boken