1. Aksiomene for en boolsk algebra

En boolsk algebra er en mengde \(B\) med to binære operasjoner join \(+\) (ELLER) og meet \(\cdot\) (OG), en unær operasjon komplement \(\overline{\;}\) (NOT), og to utmerkede elementer \(0\) (null) og \(1\) (enhet). For alle \(x,y,z\in B\) gjelder aksiomene nedenfor. Legg merke til den fullstendige symmetrien mellom \(+\) og \(\cdot\) (dualitet).

Aksiomer (begge formene gjelder):

Kommutativitet: \(x+y=y+x\), \(\;x\cdot y=y\cdot x\)

Distributivitet: \(x\cdot(y+z)=xy+xz\), \(\;x+(y\cdot z)=(x+y)(x+z)\)

Identitet: \(x+0=x\), \(\;x\cdot 1=x\)

Komplement: \(x+\overline{x}=1\), \(\;x\cdot\overline{x}=0\)

Fra disse fire aksiomparene utleder man alle andre lover. Viktige avledede lover er idempotens (\(x+x=x\), \(x\cdot x=x\)), dominering (\(x+1=1\), \(x\cdot 0=0\)), involusjon (\(\overline{\overline{x}}=x\)), absorpsjon (\(x+xy=x\), \(x(x+y)=x\)) og De Morgan (\(\overline{x+y}=\overline{x}\,\overline{y}\), \(\overline{xy}=\overline{x}+\overline{y}\)). Assosiativitet (\((x+y)+z=x+(y+z)\)) følger også av aksiomene.

Eksempel 1: Bevis absorpsjonsloven \(x+xy=x\) direkte fra aksiomene.

\(x+xy = x\cdot 1 + x\cdot y\) (identitet på første ledd)

\(= x(1+y)\) (distributiv lov, faktoriser ut \(x\))

\(= x\cdot 1\) (dominering: \(1+y=1\))

\(= x\) (identitet)

2. Verifisere at en struktur er en boolsk algebra

For å vise at en konkret struktur er en boolsk algebra sjekker man at de fire aksiomparene holder. To sentrale familier av eksempler:

Potensmengden: \((\mathcal{P}(S),\cup,\cap,\overline{\;},\emptyset,S)\) er en boolsk algebra. Join = union, meet = snitt, komplement \(\overline{A}=S\setminus A\), null = \(\emptyset\), enhet = \(S\). Har \(2^{|S|}\) elementer.

Delelighetsgitteret: \(D_n=\{d:d\mid n\}\) med join = \(\mathrm{lcm}\), meet = \(\gcd\), null = \(1\), enhet = \(n\), er en boolsk algebra hvis og bare hvis \(n\) er kvadratfri. Komplementet er da \(\overline{a}=n/a\).

Eksempel 2: Er \(D_{30}=\{1,2,3,5,6,10,15,30\}\) en boolsk algebra? Sjekk komplementloven.

\(30=2\cdot 3\cdot 5\) er kvadratfri \(\Rightarrow\) kandidat for boolsk algebra.

Påstand: komplementet til \(a\) er \(30/a\). Sjekk \(a=6\): \(\overline{6}=30/6=5\).

Join: \(\mathrm{lcm}(6,5)=30=\) enhet. OK (\(a+\overline{a}=1\)).

Meet: \(\gcd(6,5)=1=\) null. OK (\(a\cdot\overline{a}=0\)).

Dette virker for alle 8 elementer \(\Rightarrow D_{30}\) er en boolsk algebra.

Eksempel 3: Vis at \(D_{12}=\{1,2,3,4,6,12\}\) IKKE er en boolsk algebra.

\(12=2^2\cdot 3\) er ikke kvadratfri \(\Rightarrow\) mistanke om svikt.

Se på \(a=6\). Trenger \(b\) med \(\mathrm{lcm}(6,b)=12\) og \(\gcd(6,b)=1\).

\(\gcd(6,b)=1\) krever \(b\) uten faktorene 2 og 3, dvs. \(b=1\) blant delerne.

Men \(\mathrm{lcm}(6,1)=6\neq 12\). Ingen \(b\) oppfyller begge krav.

\(\Rightarrow\) element 6 mangler komplement \(\Rightarrow D_{12}\) er ikke boolsk algebra.

Generelt har en endelig boolsk algebra \(2^k\) elementer, der \(k\) er antallet atomer (minimale elementer over 0). Enhver endelig boolsk algebra er isomorf med en potensmengde \(\mathcal{P}(\{1,\dots,k\})\).

3. Boolske funksjoner og logiske porter

En boolsk funksjon av \(n\) variabler er en avbildning \(f:\{0,1\}^n\to\{0,1\}\). Det finnes \(2^{2^n}\) slike funksjoner (for \(n=2\): 16 stykker). Hver funksjon kan skrives på sum-av-produkter-form (SOP): én minterm per rad i sannhetstabellen der \(f=1\).

Logiske porter: AND \(=x\cdot y\); OR \(=x+y\); NOT \(=\overline{x}\); NAND \(=\overline{x\cdot y}\); NOR \(=\overline{x+y}\); XOR \(=x\overline{y}+\overline{x}y\); XNOR \(=xy+\overline{x}\,\overline{y}\). NAND og NOR er hver for seg funksjonelt komplette – alle funksjoner kan bygges av dem alene.

4. Forenkling av boolske uttrykk

Målet er å redusere antall ledd/porter. Verktøykassen er absorpsjon, distributivitet, komplement, De Morgan og konsensus. To nyttige standardresultater er \(x+\overline{x}y=x+y\) og konsensus \(xy+\overline{x}z+yz=xy+\overline{x}z\).

Eksempel 4: Forenkle \((x+y)(x+\overline{y})\).

\((x+y)(x+\overline{y})\)

\(= x + y\cdot\overline{y}\) (distributiv: join over meet)

\(= x + 0\) (komplement \(y\overline{y}=0\))

\(= x\) (identitet)

Eksempel 5: Forenkle \(xy+\overline{x}\,\overline{y}+x\overline{y}\).

\(xy+x\overline{y}+\overline{x}\,\overline{y}\) (omordne ledd)

\(= x(y+\overline{y})+\overline{x}\,\overline{y}\) (faktoriser \(x\))

\(= x\cdot 1+\overline{x}\,\overline{y}=x+\overline{x}\,\overline{y}\) (komplement, identitet)

\(= (x+\overline{x})(x+\overline{y})\) (distributiv: \(x+\overline{x}y'\)-mønster)

\(= 1\cdot(x+\overline{y})=x+\overline{y}\)

Studieguide: Boolsk algebra

Studieguide: Boolsk algebra