A digitális számítógépeket a kettes számrendszer alapján építik, mivel egy számjegy egy kétállapotú egységgel megvalósítható. A digitális logikai szintet a kapuáramkörök alkotják, amik analóg alkatrészekből épülnek fel, de működésükkel a bináris rendszer alapját képezik. A két állapot megkülönböztetésére két jelszintet alkalmaznak: az alacsony a hamis vagy 0 értéket, a magas az igaz vagy 1 értéket jelenti.

Minden kapunak van egy vagy több digitális bemenete és egy kimenete. A kapuk kombinációjából felépített áramkörök leírására egy olyan algebrára van szükség, amiben a változók és a függvények csak 0 vagy 1 értéket vehetnek fel. A George Boole (1815-1864) által kitalált és róla elnevezett Boole-algebra ilyen. A Boole-algebrában összesen két szám van: a 0 és az 1. Itt már a szokásos összeadás műveletét sem definiálhatjuk, új műveletekre van szükség.

Egy n változós Boole-függvény bemeneti értékeinek 2ⁿ lehetséges kombinációja, 2ⁿ kimenete van, amik egy 2ⁿ soros táblázattal adható meg, amit igazságtáblának nevezünk. Az egyváltozós művelet, ami megfordítja a bemenet (A) értékét, azaz a kimenet (Q) 0-ra 1-et, 1-re 0-t ad, a negáció, NEM, vagy angolul NOT, függvény logikai áramköri rajzjele és igazságtáblája az alábbi:

A kétváltozós műveletek mindkét bemenete kétféle lehet. A bemenetek közötti műveletek az ÉS, VAGY és KIZÁRÓ VAGY. Az ÉS, vagy angolul AND művelet a konjunkció, ami csak akkor ad egyet, ha az egyik (A) és a másik (B) bemenete is egy.

A másik művelet a diszjunkció, a VAGY, vagy angolul OR, ami akkor ad egyet, ha vagy az egyik (A) vagy másik (B) bemenete egy.

Ezekkel az alapműveletekkel már a többi kétváltozós művelet is megadható. Például az előző műveletekkel kifejezve a KIZÁRÓ VAGY, vagy XOR művelet akkor ad 1-et, ha a két bemenete (A, B) különböző:

A XOR B = (A AND NOT B) OR (NOT A AND B).

Az XOR művelet jelentősége az összeadás műveletének logikai kapukkal történő megvalósításában mutatkozik meg. Ha összeadunk két egy-egy biten ábrázolt digitalis értéket x–et és y-t akkor az eredmény s (sum) megjelenik egy biten és kapunk még egy c (carry) továbbvivendő bitet. Az alábbi táblázat s oszlopa pontosan az XOR műveletnek felel meg.

Az alábbi ábra pedig mutatja a teljes összeadás egy lépését, amikor nemcsak a két összeadandó van hanem a korábbi összeadásból származó c is.

32 biten az összeadás a fenti áramkörök összefűzéséből végezhető el

Az utolsó sorban a c a túlcsordulás áldozata lesz. Ha c nem 0 akkor értékes jegy vész el és az eredmény természetesen hibás lesz.

Feladat:

1. Igaz-e, hogy A XOR B = (A+B)*NOT(A*B)

2. Adjuk meg a teljes összeadás logikai sémáját.