Logiske metoder

Boken min er endelig ute på engelsk 🎉 Her er mer informasjon om boken. Først de tre superkorte «fordelene» med denne boken:

Legger et solid fundament for begynnerstudenter i matematikk eller informatikk. Introduserer det grunnleggende innenfor mengdelære, logikk, matematiske bevis, kombinatorikk, grafteori, og mye mer, på en klar og forståelig måte. Inneholder mange fargerike figurer og illustrasjoner, så vel som hundrevis av oppgaver.

Springer International Publishing

Utallige timer og masse kjærlighet har gått inn i denne boken, og jeg håper at du liker den! I var så heldig å få lov til å bidra til designet av omslaget til boken, som du ser på denne siden, og du kjenner kanskje igjen mønsteret. Det er Six Perfect In-Shuffles With 125 Cards and Five Piles. Sjekk også ut innholdsfortegnelsen lenger ned.

Her er litt mer generell informasjon–på engelsk–om boken, tatt fra Springer-siden:

Many believe mathematics is only about calculations, formulas, numbers, and strange letters. But mathematics is much more than just crunching numbers or manipulating symbols. Mathematics is about discovering patterns, uncovering hidden structures, finding counterexamples, and thinking logically. Mathematics is a way of thinking. It is an activity that is both highly creative and challenging.

This book offers an introduction to mathematical reasoning for beginning university or college students, providing a solid foundation for further study in mathematics, computer science, and related disciplines. Written in a manner that directly conveys the sense of excitement and discovery at the heart of doing science, its 25 short and visually appealing chapters cover the basics of set theory, logic, proof methods, combinatorics, graph theory, and much more.

In the book you will, among other things, find answers to:

What is a proof? What is a counterexample?
What does it mean to say that something follows logically from a set of premises?
What does it mean to abstract over something?
How can knowledge and information be represented and used in calculations?
What is the connection between Morse code and Fibonacci numbers?
Why could it take billions of years to solve Hanoi's Tower?

Logical Methods is especially appropriate for students encountering such concepts for the very first time. Designed to ease the transition to a university or college level study of mathematics or computer science, it also provides an accessible and fascinating gateway to logical thinking for students of all disciplines.

Beskrivelse, Springer International Publishing, 2021

Innholdsfortegnelse

Kapittel 0: Kunsten å tenke abstrakt og matematisk

I dette kapitlet ser vi på noen grunnleggende begreper som vi møter igjen og igjen: sannhet, definisjoner, antakelser, bevis, språk, aksiomer og teoremer. Vi legger også noen rammer og begrepsavklaringer for veien videre.

Innhold Abstraksjon Resonnering om sannhet Antakelser Språk Definisjoner Bevis Problemløsning og Pólyas heuristikker

Kapittel 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

Kapittel 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

Kapittel 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

Kapittel 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

Kapittel 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

Kapittel 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

Kapittel 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

Kapittel 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

Kapittel 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

Kapittel 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

Kapittel 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

Kapittel 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

Kapittel 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

Kapittel 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

Kapittel 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

Kapittel 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

Kapittel 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

Kapittel 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

Kapittel 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

Kapittel 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

Kapittel 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

Kapittel 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

Kapittel 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

Kapittel 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

Innhold 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

Bokinformasjon

Tittel	Logiske metoder
Forfatter	Roger Antonsen
Forlegger	Springer International Publishing
Isbn	978-3-030-63776-7
År	2021
Url	Springer International Publishing

Omslag og illustrasjoner

Cover, Springer International Publishing, 2021

Illustrasjon fra kapittel 10 om rekursive funksjoner.

Illustrasjon fra kapittel 17 om abstraksjon, partisjoner og ekvivalensklasser.