Booleaanse algebra

**Booleaanse algebra** is een verzameling **wetten** om booleaanse expressies te herschrijven. Elke wet zegt dat twee expressies **equivalent** zijn: ze hebben voor elke invoer dezelfde waarheidswaarde, dus je mag de ene altijd door de andere vervangen. Met de wetten kun je een expressie **vereenvoudigen** zonder telkens een nieuwe waarheidstabel te maken. We schrijven 1 voor waar en 0 voor onwaar (ook de interactieve waarheidstabellen gebruiken 1 en 0). Ingenieurs schrijven vaak $A \cdot B$ voor $A \land B$, $A + B$ voor $A \lor B$ en $\overline{A}$ voor $\neg A$: dat betekent precies hetzelfde. In deze les gebruiken we $\land$, $\lor$ en $\neg$. **De wetten** ($A$, $B$ en $C$ zijn booleaanse variabelen): | Wet | EN-vorm | OF-vorm | |:---|:---:|:---:| | Identiteitswet | $A \land 1 = A$ | $A \lor 0 = A$ | | Dominantiewet | $A \land 0 = 0$ | $A \lor 1 = 1$ | | Idempotentiewet | $A \land A = A$ | $A \lor A = A$ | | Complementwet | $A \land \neg A = 0$ | $A \lor \neg A = 1$ | | Dubbele negatie | $\neg\neg A = A$ | (maar één vorm) | | Commutatieve wet | $A \land B = B \land A$ | $A \lor B = B \lor A$ | | Associatieve wet | $(A \land B) \land C = A \land (B \land C)$ | $(A \lor B) \lor C = A \lor (B \lor C)$ | | Distributieve wet | $A \land (B \lor C) = (A \land B) \lor (A \land C)$ | $A \lor (B \land C) = (A \lor B) \land (A \lor C)$ | | Absorptiewet | $A \land (A \lor B) = A$ | $A \lor (A \land B) = A$ | | De Morgan | $\neg(A \land B) = \neg A \lor \neg B$ | $\neg(A \lor B) = \neg A \land \neg B$ | Let op het patroon: verwissel in de ene kolom $\land$ met $\lor$ en 0 met 1, en je krijgt de andere kolom. Dat heet **dualiteit**. **Stap voor stap vereenvoudigen:** gebruik per stap één wet en noem die. Controleer daarna het resultaat met een waarheidstabel: als de eindkolommen in elke rij gelijk zijn, is de vereenvoudiging juist.

Identiteitswet en dominantiewet

Vereenvoudig $(A \land 1) \lor (B \land 0)$.

Pas de identiteitswet toe op het eerste haakjesdeel: $A \land 1 = A$, want EN met waar verandert niets = $A \lor (B \land 0)$

Pas de dominantiewet toe op het tweede haakjesdeel: $B \land 0 = 0$, want EN met onwaar is altijd onwaar = $A \lor 0$

Pas de identiteitswet nog eens toe: $A \lor 0 = A$, want OF met onwaar verandert niets = $A$

Answer: $(A \land 1) \lor (B \land 0) = A$. De waarde van $B$ maakt helemaal niet uit.

De absorptiewet bewijzen

Laat met andere wetten zien dat $A \lor (A \land B) = A$.

Schrijf $A$ als $A \land 1$ (identiteitswet): $A \lor (A \land B) = (A \land 1) \lor (A \land B)$ = Beide haakjesdelen beginnen met $A$

Haal $A$ buiten haakjes (distributieve wet, van rechts naar links gelezen): $(A \land 1) \lor (A \land B) = A \land (1 \lor B)$ = $A \land (1 \lor B)$

Pas de commutatieve wet en de dominantiewet toe: $1 \lor B = B \lor 1 = 1$ = $A \land 1$

Pas de identiteitswet toe: $A \land 1 = A$ = $A$

Answer: $A \lor (A \land B) = A$. In woorden: als $A$ waar is, is de hele OF waar, en als $A$ onwaar is, is $A \land B$ ook onwaar. In beide gevallen is het resultaat gelijk aan $A$.

De Morgan en dubbele negatie

Vereenvoudig $\neg(\neg A \land B)$ en controleer het resultaat met een waarheidstabel.

Pas de wet van De Morgan toe: De NIET van een EN wordt een OF van de negaties: $\neg(\neg A \land B) = \neg\neg A \lor \neg B$ = $\neg\neg A \lor \neg B$

Pas de dubbele negatie toe: $\neg\neg A = A$ = $A \lor \neg B$

Maak de kolom van de oorspronkelijke expressie: Rijen $(A, B)$ = 00, 01, 10, 11: $\neg A \land B$ is 0, 1, 0, 0, dus $\neg(\neg A \land B)$ is 1, 0, 1, 1 = 1, 0, 1, 1

Maak de kolom van het resultaat: $\neg B$ is 1, 0, 1, 0, dus $A \lor \neg B$ is 1, 0, 1, 1 = Dezelfde kolom in elke rij

Answer: $\neg(\neg A \land B) = A \lor \neg B$. De twee kolommen zijn in alle 4 rijen gelijk, dus de vereenvoudiging is juist.

Buiten haakjes halen en de complementwet

Vereenvoudig $(A \land B) \lor (A \land \neg B)$ en controleer het met een waarheidstabel.

Haal $A$ buiten haakjes (distributieve wet): $(A \land B) \lor (A \land \neg B) = A \land (B \lor \neg B)$ = $A \land (B \lor \neg B)$

Pas de complementwet toe: $B \lor \neg B = 1$, want $B$ is waar of onwaar = $A \land 1$

Pas de identiteitswet toe: $A \land 1 = A$ = $A$

Controleer met een waarheidstabel: Rijen $(A, B)$ = 00, 01, 10, 11: $A \land B$ is 0, 0, 0, 1 en $A \land \neg B$ is 0, 0, 1, 0, dus de OF is 0, 0, 1, 1 = Gelijk aan kolom $A$: 0, 0, 1, 1

Answer: $(A \land B) \lor (A \land \neg B) = A$. Een schakeling met 4 poorten (twee EN, een NIET, een OF) wordt een gewone draad.

Minder poorten in een schakeling

Een schakeling berekent $\neg(A \lor B) \lor (\neg A \land B)$. Vereenvoudig haar en tel de bespaarde poorten (één poort voor elke $\land$, $\lor$ en $\neg$).

Tel de poorten van de oorspronkelijke expressie: Operatoren: $\neg$ en $\lor$ in het eerste deel, $\neg$ en $\land$ in het tweede deel, en de $\lor$ in het midden = 5 poorten

Pas de wet van De Morgan toe op het eerste deel: $\neg(A \lor B) = \neg A \land \neg B$ = $(\neg A \land \neg B) \lor (\neg A \land B)$

Haal $\neg A$ buiten haakjes (distributieve wet): $(\neg A \land \neg B) \lor (\neg A \land B) = \neg A \land (\neg B \lor B)$ = $\neg A \land (\neg B \lor B)$

Pas de complementwet en de identiteitswet toe: $\neg B \lor B = 1$ en $\neg A \land 1 = \neg A$ = $\neg A$

Tel de poorten opnieuw: $\neg A$ heeft maar één NIET-poort nodig: $5 - 1 = 4$ = 4 poorten bespaard

Answer: De schakeling is equivalent met $\neg A$: één NIET-poort in plaats van 5 poorten. Controle: de oorspronkelijke expressie is precies waar in de rijen 00 en 01, dat zijn de rijen met $A = 0$.

Elke $\land$, $\lor$ en $\neg$ in een expressie wordt in een schakeling een **logische poort**. Een kortere expressie betekent minder poorten, en minder poorten betekenen een chip die goedkoper, kleiner en sneller is en minder stroom gebruikt. - **Elektronica**: een processor bevat miljarden poorten, dus wie één poort bespaart in een schakeling die een miljoen keer wordt gekopieerd, bespaart een miljoen poorten - **Programmeren**: een voorwaarde als NIET (weekend OF feestdag) kun je herschrijven als (NIET weekend) EN (NIET feestdag), wat vaak makkelijker te lezen en te testen is - **Zoeken en databases**: een filter als wiskunde OF (wiskunde EN logica) geeft precies dezelfde resultaten als alleen wiskunde - **Bewijzen**: met de wetten kun je bewijzen dat twee schakelingen of twee voorwaarden hetzelfde doen zonder elke invoer te proberen In de les Waarheidstabellen controleerde je equivalenties rij voor rij, en in de les Logische poorten bouwde je schakelingen. Booleaanse algebra verbindt die twee: ze maakt van een grote schakeling een kleine, en een waarheidstabel bevestigt dat er niets veranderd is.

Mistake: $\neg(A \land B) = \neg A \land \neg B$ schrijven

Why: De wet van De Morgan verandert niet alleen de variabelen, maar ook de operator. Test $A = 1$, $B = 0$: de linkerkant is $\neg 0 = 1$, de rechterkant $0 \land 1 = 0$.

Correct: Breek de streep en wissel het teken: $\neg(A \land B) = \neg A \lor \neg B$ en $\neg(A \lor B) = \neg A \land \neg B$.

Mistake: Regels van de gewone algebra gebruiken, zoals $A \lor A = 2A$ of $A \land A = A^2$

Why: Booleaanse variabelen zijn alleen 0 of 1, en $1 \lor 1$ is 1, niet 2. Een variabele herhalen voegt niets nieuws toe.

Correct: Gebruik de idempotentiewet: $A \lor A = A$ en $A \land A = A$.

Mistake: $A \lor B \land C$ lezen als $(A \lor B) \land C$

Why: EN gaat voor OF, net zoals vermenigvuldigen voor optellen gaat. Met $A = 1$, $B = 0$, $C = 0$ is de juiste waarde $1 \lor 0 = 1$, maar de verkeerde lezing geeft $1 \land 0 = 0$.

Correct: Zet de haakjes neer voordat je een wet toepast: $A \lor B \land C = A \lor (B \land C)$.

Mistake: De complementwet toepassen op twee verschillende variabelen, zoals $A \land \neg B = 0$

Why: De complementwet werkt alleen voor een variabele en haar eigen negatie. Met $A = 1$, $B = 0$: $A \land \neg B = 1 \land 1 = 1$, niet 0.

Correct: Zoek dezelfde letter: $A \land \neg A = 0$ en $B \lor \neg B = 1$, maar $A \land \neg B$ kun je niet vereenvoudigen.

Goedkopere chips ontwerpen

Chipontwerpers vereenvoudigen elke schakeling met booleaanse algebra voordat die gebouwd wordt, want elke poort kost ruimte, stroom en geld.

Een schakeling voor $(A \land B) \lor (A \land C)$ gebruikt 3 poorten. Buiten haakjes gehaald, $A \land (B \lor C)$, zijn er maar 2 nodig.

Leesbare voorwaarden in een programma

Programmeurs gebruiken de wetten van De Morgan om verwarrende dubbele ontkenningen uit de voorwaarden in hun code te halen.

NIET (weekend OF feestdag) is hetzelfde als (NIET weekend) EN (NIET feestdag): de winkel is open op dagen die geen van beide zijn.

Zoekfilters

Zoekmachines en databases vereenvoudigen filters met de absorptiewet voordat ze die uitvoeren.

Het filter wiskunde OF (wiskunde EN logica) geeft precies dezelfde boeken als het filter wiskunde.

Booleaanse algebra gebruikt wetten om een expressie te herschrijven tot een equivalente, zonder telkens een nieuwe waarheidstabel

De identiteitswet, dominantiewet, idempotentiewet en complementwet verwijderen constanten en herhaalde variabelen: $A \land 1 = A$, $A \lor 1 = 1$, $A \lor A = A$, $A \land \neg A = 0$

De commutatieve, associatieve en distributieve wet verwisselen, hergroeperen en halen buiten haakjes; in de booleaanse algebra is ook OF distributief over EN

Absorptiewetten: $A \lor (A \land B) = A$ en $A \land (A \lor B) = A$

Wetten van De Morgan: breek de streep en wissel het teken, $\neg(A \land B) = \neg A \lor \neg B$ en $\neg(A \lor B) = \neg A \land \neg B$

Vereenvoudig met één wet per stap, noem elke wet en controleer het resultaat met een waarheidstabel; een eenvoudigere expressie betekent minder poorten

Q: Waarom is OF distributief over EN, terwijl $a + b \times c$ bij getallen niet gelijk is aan $(a + b) \times (a + c)$?

A: Omdat booleaanse variabelen alleen 0 of 1 zijn. Controleer beide gevallen: als $A = 1$, zijn beide kanten van $A \lor (B \land C) = (A \lor B) \land (A \lor C)$ gelijk aan 1; als $A = 0$, worden beide kanten $B \land C$. Met gewone getallen is $1 + 2 \times 3 = 7$, maar $(1 + 2) \times (1 + 3) = 12$, dus deze wet geldt alleen in de booleaanse algebra.

Q: Hoe weet ik welke wet ik daarna moet gebruiken?

A: Let op patronen: een NIET voor haakjes vraagt om De Morgan, een variabele die in twee haakjesdelen terugkomt vraagt om buiten haakjes halen (distributieve wet), en een variabele naast haar eigen negatie vraagt om de complementwet. De constanten 0 en 1 verdwijnen met de identiteitswet en de dominantiewet.

Q: Heb ik nog waarheidstabellen nodig als ik de wetten ken?

A: De wetten vinden de vereenvoudiging, de waarheidstabel bevestigt haar. Een tabel met 2 variabelen heeft maar 4 rijen, dus het is een snelle en betrouwbare controle, vooral als je twijfelt over een stap.

Q: Kan ik een wet controleren met gewoon rekenen?

A: Ja, met 0 en 1: $A \land B = A \times B$, $\neg A = 1 - A$ en $A \lor B = A + B - A \times B$. Bijvoorbeeld met $A = 1$ en $B = 1$: $1 + 1 - 1 \times 1 = 1$, dus $1 \lor 1 = 1$. De rekenmachine in deze les werkt met deze getallen.

Presentatie afsluiten

Booleaanse algebra

1 / 14

Logica & Verzamelingen / Booleaanse logica

Booleaanse algebra

Leer de wetten van de booleaanse algebra, ook de wetten van De Morgan, gebruik ze om expressies stap voor stap te vereenvoudigen en controleer het resultaat met een waarheidstabel.

Gevorderd30 min

Gebruik pijltjestoetsen of spatiebalk om te navigeren