Tallsystemer

Digitale systemer bruker binære tall (base 2) internt, men det er nyttig å representere binærverdier i oktal (base 8) og heksadesimal (base 16) for kompakthet. Konvertering mellom systemene følger enkle regler:

Binær → heks: Grupper biter fire og fire fra høyre. Eksempel: $1011\,1010_2 = \text{BA}_{16}$.
Binær → oktal: Grupper biter tre og tre fra høyre. Eksempel: $101\,110_2 = 56_8$.
Desimal → binær: Del gjentatte ganger på 2 og samle restene baklengs. Eksempel: $45_{10} = 101101_2$.
Binær → desimal: Summer $\text{bit}_i \cdot 2^i$. Eksempel: $1101_2 = 8+4+1 = 13_{10}$.

Toverkomplement (Two's complement)

Toverkomplement er den dominerende representasjonen av fortegnstall i digitale systemer. For et $n$-bits toverkomplement-tall:

Positivt tall: Representeres direkte i binær. Område: $0$ til $2^{n-1}-1$.
Negativt tall: Inverter alle biter (enerkomplement) og legg til 1. Eksempel for $n=8$: $-5 = \overline{00000101} + 1 = 11111010 + 1 = 11111011_2$.
Signbit: MSB (mest signifikante bit) angir fortegn: 0 = positivt, 1 = negativt.
Område for $n$ bits: $-2^{n-1}$ til $2^{n-1}-1$. For 8 bits: $-128$ til $127$.

Overflow skjer når summen av to like-fortegnstall gir et resultat med motsatt fortegn. Eksempel: $0111\ 1111 + 0000\ 0001 = 1000\ 0000$ tolkes som $-128$ i toverkomplement — overflow.

Boolsk algebra

Boolsk algebra opererer på verdiene 0 og 1 med tre grunnoperasjoner: AND ($\cdot$), OR ($+$) og NOT ($\overline{A}$). Sentrale aksiomer og lover:

Identitetslover: $A \cdot 1 = A$, $A + 0 = A$
Nulllover: $A \cdot 0 = 0$, $A + 1 = 1$
Idempotens: $A \cdot A = A$, $A + A = A$
Komplement: $A \cdot \overline{A} = 0$, $A + \overline{A} = 1$
De Morgans lover: $\overline{A \cdot B} = \overline{A} + \overline{B}$ og $\overline{A + B} = \overline{A} \cdot \overline{B}$
Absorpsjon: $A + A \cdot B = A$, $A \cdot (A + B) = A$
Distribuering: $A \cdot (B + C) = A \cdot B + A \cdot C$
Dobbel negasjon: $\overline{\overline{A}} = A$

Sannhetstabeller

En sannhetstabell lister alle mulige inngangskombinasjonar og tilhørende utgang for et logisk uttrykk. For $n$ innganger har tabellen $2^n$ rader. Standardpraksis er å nummerere radene fra 0 til $2^n - 1$ og la inngangsvariablene følge binærtelling.

Eksempel: Toverkomplement og boolsk forenkling

Oppgave: Representér $-37$ i 8-bits toverkomplement.
$37_{10} = 0010\ 0101_2$
Inverter: $1101\ 1010$
Legg til 1: $1101\ 1011_2$
Verifisering: $128 + 64 + 16 + 8 + 2 + 1 = 219$; $219 - 256 = -37$. Korrekt.

Forenkling: $F = AB + A\overline{B} + \overline{A}B$
$= A(B + \overline{B}) + \overline{A}B = A \cdot 1 + \overline{A}B = A + \overline{A}B$
Konsensusteorem: $A + \overline{A}B = A + B$.

Studieguide: Tallsystemer og Boolesk algebra

Studieguide: Tallsystemer og Boolesk algebra