Undflyende inom teorin om booleska funktioner

Abstract

Aanderaa-Karp-Rosenberg förmodan är en förmodan angående hur vissa egenskaper hos booleska funktioner relaterar till undflyende. Även om förmodan inte bevisats än har man lyckats visa att förmodan är sann om man antar vissa ytterligare krav på funktionen. Denna uppsats kommer presentera den relevanta teorin kring förmodan samt simplicialtopologi som ett tillvägagångssätt att angripa problemet. Förkunskaperna arbetet antar av läsaren är de som man lär sig under de första tre åren på matematikprogrammet. Därav förväntas ingen kunskap inom grafteori samt endast grundläggande kunskap inom topologi och därmed kommer dessa ämnen presenteras med detta i åtanke. Efter den relevanta teorin presenterats kommer teorin tillämpas på ett antal booleska funktioner i en resultatdel. Resultaten som presenteras kommer till största del bestå av att visa att en boolesk funktion agerande på en graf är undflyende eller icke-undflyende.