Verzamelingen/Inleiding in de booleaanse logica

Na het bestuderen van dit hoofdstuk:

Weet je wat er met booleaanse logica en booleaanse algebra bedoeld wordt.

Kun je de operatoren EN, OF en NIET gebruiken

Operatoren

In hoofdstuk 1 zagen we een verzameling voorbij komen met twee elementen, L={Waar, Onwaar}.

Hierop definiëren we een aantal operatoren, $\land$ en $\lor$, en $\lnot$.

De $\land$ is EN, terwijl $\lor$ de OF operator is. We bekijken ze een voor een.

In dit boek gebruiken we W=Waar en O=Onwaar. maar in veel boeken wordt de Engelse T=True en F=False gebruikt. Dat zien we soms ook in Nederlandstalige boeken. We kunnen ook Waar als 1 en Onwaar als 0 noteren.

De EN operator $\land$

In de Nederlandse taal gebruiken we het woord EN in zinnen als 'Jan zit op zijn kamer EN Marie is op de manage'. Die zin is alleen waar als beide onderdelen waar zijn, dus als het waar is dat Jan op zijn kamer zit en als Marie op de manage is.

Noem de eerste zin p en de tweede zin q. Er zijn dan 4 mogelijkheden:

p	q	p$\land$q
W	W	W
W	O	O
O	W	O
O	O	O

Hierbij staat W telkens voor waar en O voor Onwaar. Zodra een van de twee beweringen Onwaar is, is de samenstelling ook Onwaar.
De EN wordt ook wel inclusie genoemd.

De OF operator $\lor$

Het woordje OF geven we in de booleaanse logica een wat striktere betekenis dan in het gewone taalgebruik, maar de betekenis komt toch goed overeen. Wanneer we zeggen "Jan is naar de supermarkt of naar de drogist", dan is dat een combinatie van 2 beweringen, namelijk "Jan is naar de supermarkt" of "Jan is naar de drogist".

Ook dit kunnen we in een tabelletje onderbrengen. Noem de eerste bewerking weer p en de 2e bewering q. Er zijn weer 4 mogelijkheden:

p	q	p$\lor$q
W	W	W
W	O	W
O	W	W
O	O	O

Dus de samenstelling p$\lor$q is waar dan en alleen dan als een van de twee beweringen waar is.
De OF wordt ook wel disjunctie genoemd.

NIET
Ten slotte is er nog de negatie NIET.

p	$\neg$p
W	O
O	W

Dit waren de 3 basis operatoren. Hiermee kunnen we een aantal andere operatoren definiëren.

De XOR operator $\mathop {\underline {\lor }}$
De OF heeft in het gewone spraakgebruik een dubbele betekenis. De eerste betekenis hebben we hierboven gezien. Maar soms willen we dat mensen echt een keuze maken, zoals in "wil je thee of koffie?". Als we alleen de bovenstaande OF zouden hebben, zou iemand op de vraag "Wil je thee of koffie?" kunnen antwoorden met "ja, graag" als hij een van de twee wil drinken. Als we echt willen dat één van de twee ja is, kunnen we kiezen voor de Exclusieve disjunctie, oftwel de XOR, de exlusive OR.

p	q	p$\mathop {\underline {\lor }}$q
W	W	O
W	O	W
O	W	W
O	O	O

De Exclusieve OR wordt minder vaak gebruikt dan de gewone OF.

De Logische implicatie
De logische implicatie komt neer op 'uit p volgt q'.
Notatie: p → q of p ==> q of p$\Longrightarrow$q

We kunnen p → q uitschrijven als waarheidstabel:

p	q	p → q
W	W	W
W	O	O
O	W	W
O	O	W

We krijgen dezelfde waarheidstabel wanneer we definiëren: ${\textstyle p\rightarrow q=\neg {p}\vee q}$.

We kunnen daarom de logische implicatie p $\rightarrow$ q uitschrijven als p $\rightarrow q=\neg p\vee q$

Deze tabel verdient nog wel wat toelichting. Want in het gebruik hiervan gaat gemakkelijk iets fout.
Opmerking 1 Zoals je ziet is $(p\rightarrow q)$ waar als p onwaar is, onafhankelijk van q. Dat is een keuze. Maar het verschilt wel met wat we soms uit het gewone spraakgebruik ons voorstellen. Als iemand zegt: Als het morgen warm is, trakteer ik op ijs, bedoelt die persoon daarmee meestal 'als het niet warm is, trakteer ik niet op ijs.' Maar wanneer we 'het is morgen warm' p noemen, en 'ik trakteer op ijs' q noemen, dan krijgen we de volgende waarheidstabel:

het is morgen warm	ik trakteer op ijs	als het morgen warm is, trakteer ik op ijs
W	W	W
W	O	O
O	W	W
O	O	W

Dan zien we dat als het morgen niet warm is, de persoon zijn belofte in elk geval niet gebroken heeft, of hij nu op ijs trakteert of niet. Het is daarom niet onlogisch om deze definitie te hanteren.

Opmerking 2 Stel nu dat we twee beweringen hebben:

p="Ik heb een levende vuurspuwende draak in mijn broekzak"

q="Parijs ligt in Frankrijk"

p is niet waar, dus p-->q is waar.
Dan krijgen we als p--> q: "Als ik een levende vuurspuwende draak in mijn broekzak heb, dan ligt Parijs in Frankrijk." Dat is niet direct wat we als logisch zien.

Opmerking 3 Maar ook als we twee beweringen hebben die beiden waar zijn, moeten we oppassen. Stel:

p="Acht is een even getal"

q="Een driehoek heeft drie zijden"

Beiden zijn waar. Maar iedereen voelt wel aan dat we niet kunnen zeggen:
"Acht is een even getal, dus een driehoek heeft drie zijden"
Het woord "dus" veronderstelt een causale relatie, een oorzaak en gevolg. Maar dat ontbreekt hier.

Het verschil tussen beiden wordt wel aangeduid als het verschil tussen materiele implicatie en conversationele implicatie.

Equivalentie:
$(p\leftrightarrow q)$ betekent: $(p\to q)\land (q\to p)$.
De laatste operator die hier behandelen is de equivalentie. Deze spreken we vaak uit als "dan en slechts dan", waarmee we bedoelen "dan, en alleen dan".

Notatie:: $(p\leftrightarrow q)$ is gebruikelijk maar ook $\Longleftrightarrow$ wordt gebruikt.

Gebruik van de operatoren

We kunnen met deze operatoren rekenen. Dit wordt ook wel Booleaanse algebra genoemd. Net als bij gewoon rekenen kunnen we haakjes gebruiken om de voorrang aan te geven. Normaal gaat $\land$ voor $\lor$. We geven hier een paar voorbeelden:

W$\land$$\neg$O = W$\land$W=W

W$\land$O $\lor$ O = O $\lor$ O = O

W$\land ($O $\lor$ O) = W $\land$ O = O

Booleaanse algebra

Zoals hierboven getoond kunnen we met de operatoren $\land$, $\lor$ en $\neg$ 'rekenen'.

Ze hebben een aantal eigenschappen die we ook bij de gewone getallen tegenkomen: associativiteit

$a\lor (b\lor c)=(a\lor b)\lor c$ (eigenschap 6.1)

$a\land (b\land c)=(a\land b)\land c$ (eigenschap 6.2)

commutativiteit

$a\lor b=b\lor a$ (eigenschap 6.3)

$a\land b=b\land a$ (eigenschap 6.4)

distributiviteit

$a\lor (b\land c)=(a\lor b)\land (a\lor c)$ (eigenschap 6.5)

$a\land (b\lor c)=(a\land b)\lor (a\land c)$ (eigenschap 6.6)

Ontkenning

$a\lor \lnot a=Waar$ (eigenschap 6.7)

$a\land \lnot a=Onwaar$ (eigenschap 6.8)

En ja, deze eigenschappen kwamen we ook tegen bij de deelverzamelingen waar we werkten met de operatoren ∪, ∩ en Complement.

Wet van het uitgesloten midden of de wet van de dubbele ontkenning

$\lnot (\lnot a)=a$

Deze wet is niet af te leiden uit axioma's, zoals de vorige eigenschappen. De wet wordt binnen de wiskunde vrij algemeen geaccepteerd, maar niet binnen het w:constructivisme van de Nederlandse wiskundige Brouwer. Het constructivisme wordt ook wel Intuïtionisme genoemd. Het niet accepteren van deze wet betekent dat aan het bewijs uit het ongerijmde problemen kunnen kleven. Immers, als we stellen dat een bepaald concept niet bestaat, en we leiden hieruit een tegenspraak af, dan kunnen we niet meer concluderen dat dat concept wel bestaat.

Identiteitselement
Er is nog een overeenkomst: zowel $\land$ als $\lor$ hebben een identiteitselement. Laat W=Waar en O=Onwaar. Dan geldt

p$\land$Waar= p voor alle proposities (beweringen) p

p$\lor$Onwaar = p voor alle proposities p.

Notatie

Het is gebruikelijk om voor beweringen de hoofdletters P en Q te gebruiken. In dit wikibook gebruiken we de kleine letters p en q, en reserveren de hoofdletters P en Q voor de verzamelingen van alle logische beweringen.

Gebruik

• Booleaanse algebra wordt o.a. gebruikt in de elektronica. Hier zijn speciale symbolen voor de AND, OR en NOT schakelingen:
  

• In de Informatica worden waarheidsschema's en booleaanse algebra op grote schaal gebruikt bij het programmeren en bij het bevragen van databases zoals met SQL.

Een gefingeerd voorbeeld:
SELECT "Operationeel", salarisschaal, COUNT(distinct Medw_no), SUM(sal_bruto)
FROM Medewerker, Salaris, Medewerker_groep
WHERE medewerker.salarisschaal = Salaris.salarisschaal
AND medewerker.groepnr = Medewerker_groep.groepnr
AND NOT (Medewerker.groep = "Manager" OR Medewerker.groep = "Secretaris/Secretaresse")
GROUP BY salarisschaal
UNION
SELECT "Management", salarisschaal, COUNT(distinct Medw_no), SUM(sal_bruto)
FROM Medewerker, Salaris, Medewerker_groep
WHERE medewerker.salarisschaal = Salaris.salarisschaal
AND medewerker.groepnr = Medewerker_groep.groepnr
AND (Medewerker.groep = "Manager" OR Medewerker.groep = "Secretaris/Secretaresse")
GROUP BY salarisschaal

Ook zonder dit voorbeeld inhoudelijk te begrijpen zie je hoe in bovenstaand voorbeeld zowel de AND, de OR als de NOT operator gebruikt worden. Tevens wordt de UNION, oftewel de Vereniging gebruikt.

Meerwaardige logica

De Booleaanse algebra en de standaard propositielogica zijn tweewaardig. Er zijn ook meerwaardige logica's gedefinieerd. Meerwaardige logica worden in het Engels ook wel Fuzzy Logic genoemd.

Een voorbeeld van een 3-waardige logica zou zijn (True, False, Unknown}. Of {True, False, Undefined}. We gebruiken in deze paragraaf even de Engelse True en False, omdat we met Waar, Onwaar en Onbekend geen unieke 1-letterige afkortingen hebben.

Waarom zouden we naast True en False nog een waarde Undefined of Unknown willen hebben? Daar zijn minstens twee redenen voor te bedenken. De eerste, meest natuurlijke, is dat we in het dagelijks leven te maken hebben met onbekende zaken. Voor een zakenman kan dat de vraag zijn of zijn bank hem een nieuwe lening wil verschaffen. Voor een generaal kan dat de bewering zijn dat de vijand 50 tanks in reserve heeft. Etc. Een tweede reden vinden we in de logica zelf.

We hebben gedefinieerd dat p --> q waar is als p False is. Maar dat had wel iets kunstmatigs. We zouden ook kunnen definiëren dat de waarde dan ongedefinieerd is:

p	q	p --> q
T	T	T
T	F	F
F	T	U
F	F	U

Immers, als ik tegen een van mijn kinderen zou zeggen: "Als je slaagt voor je examen, mag je voor je vakantie naar Ibiza", en het kind slaagt, en ik geef hem/haar die vakantie, dan houdt ik mijn woord, maar als het kind niet slaagt, en in geef de vakantie niet, dan kun je niet zeggen dat ik mijn woord gebroken heb, maar het voelt ook niet gemakkelijk om te zeggen dat ik mijn woord gehouden heb.

Maar dat betekent dat U(nknown) ook als p of q kan voorkomen, dus moeten we de hele tabel uitbreiden.

p\q	T	F	U
T	T	F	U
F	U	U	U
U	U	U	U

Maar dan moeten we ook de andere operatoren zo definieren dat ze met "onbekend/ongedefinieerd" overweg kunnen.

We kunnen dan de EN definieren als:

p\q	T	F	U
T	T	F	F
F	F	F	F
U	F	F	U

Een verdere uitwerking valt buiten de scope van dit boek.

Engels

• Onwaar: False
• Waar: True

Opgaven

VI.1

Als gegeven is dat:

Rusland tussen de eerste en de tweede wereldoorlog een communistische regering had

Er in Rusland tussen de eerste en de tweede wereldoorlog een periode van honger was,

Welke van de volgende beweringen zijn dan waar:

1.a Tussen de eerste en tweede wereldoorlog had Rusland een communistische regering en er was een periode van honger.

1.b Tussen de eerste en tweede wereldoorlog had Rusland een communistische regering of er was een periode van honger.

1.c Tussen de eerste en tweede wereldoorlog had Rusland een communistische regering dus was er een periode van honger.

VI.2

Als gegeven is dat:

Het (fictieve) land Buzuruni een streng kapitalistisch land is

De lonen in Buzuruni laag zijn

Welke van de volgende beweringen zijn dan waar: 2a. Het (fictieve) land Buzuruni is een streng kapitalistisch land en de lonen in Buzuruni zijn laag. 2b. Het (fictieve) land Buzuruni is een streng kapitalistisch land of de lonen in Buzuruni zijn laag. 2c. Het (fictieve) land Buzuruni is een streng kapitalistisch land dus de lonen in Buzuruni zijn laag. 2d. Het (fictieve) land Buzuruni is een streng kapitalistisch land, en daardoor zijn de lonen in Buzuruni laag.

VI.3. Het Linda probleem

Linda is 31 jaar oud, single, extravert, goed opgeleid en scherp. Ze is afgestudeerd in filosofie. Als student hield ze zich bezig met voorvallen van discriminatie en sociale armoede. Ze nam ook deel aan anti-kernoorlog demonstraties.

Welke van de twee is waarschijnlijker:

a) "Linda is bankemployee"

b) "Linda is bankemployee en actief in de feministische beweging"

Daniel Kahneman formuleerde dit probleem in zijn boek "Thinking, Fast and Slow".

VI.4.1. De inheemse inwoner

Een ontdekkingsreiziger zet voet aan wal op een eiland waar twee soorten mensen leven: Knights, die altijd de waarheid spreken, en Knaves, die altijd liegen. Je kunt aan hun uiterlijk niet zien wie een knight en wie een knave is.

Op het strand kom de ontdekkingsreiziger een inwoner van het eiland tegen. Schiet de ontdekkingsreiziger er iets mee op als hij vraagt: "Bent u een knight?" Wordt hij iets wijzer als hij vraagt: "Bent u een knave?"

VI.4.2. Twee inheemse inwoners

Even later komt de ontdekkingsreiziger een tweede inwoner van het eiland tegen. Deze gaat naast de eerste inwoner staan en zegt: "wij zijn allebei knaves". Weet de ontdekkingsreiziger nu welke inwoner wat is?

VI.4.3. Twee andere inwoners

Onze ontdekkingsreiziger laat de twee inwoners achter op het strand. Aan de rand van het strand en het oerwoud komt hij twee andere inwoners van het eiland tegen. Een van hen zegt: "Een van ons is een knight, de ander is een knave". Wat is de andere inwoner?

Samenvatting: In dit hoofdstuk heb je geleerd dat:

wat de logische operatoren zijn

hoe je er mee kunt rekenen