Dr.Godfried-Willem RAES

Kursus Experimentele Muziek: Boekdeel 1: Algoritmische Kompositie

Hogeschool Gent : School of Arts

1041:

BOOLE-ALGEBRA

A:BINAIRE BOOLEAANSE ALGORITMEN

George Boole (1815-1864) was een wiskundige die de grondslag legde voor de formele fundering van de wiskunde in de logika. De logika -een klassiek onderdeel van de wijsbegeerte- is de discipline die zich bezighoudt met de studie van de voorwaarden waaronder het toelaatbaar is om van een of meer oordelen (beweringen) naar een of meer andere oordelen (beweringen) over te gaan. Zij houdt zich niet bezig met de inhoud van die beweringen zelf, maar slechts met de vorm en de geldigheid van de gehanteerde afleidingsregels. Vulgariserend wordt zij ook vaak omschreven als de teorie van het geldig denken of redeneren.

Booleaanse algoritmen hebben betrekking op louter binaire waarden, die je je kunt voorstellen als 'waar' of 'vals'. In komputer-logika staat 'vals' voor 0 , en 'waar' voor '-1' of niet-0. Deze waarden noemt men de waarheidswaarden van de variabelen in een funktie.

De elementaire Boole-funkties zoals zowat elke die naam waardige komputertaal en dus ook BASIC die kent, zijn en worden gedefinieerd alsvolgt:

1.De EN funktie (AND) ook genaamd 'konjunktie':

X AND Y is waar , dan en dan alleen als X waar is en ook Y waar is.

In de vorm van een waarheidstabel ziet dit eruit als:

2. De OF funktie ( OR ) ook genaamd 'disjunktie':

X OF Y is waar, dan en dan alleen als X waar is, of Y waar is. Ook wanneer beide waar zijn, is het resultaat van de funktie waar.

Waarheidstabel:

3. De NIET ( NOT ) funktie, ook genaamd 'negatie' of komplement.

Dit is een unaire operator. De definitie is :

NOT X is waar dan en dan alleen als X vals is.

Waarheidstabel:

4. De equivalentie (EQV) funktie , gelijkheid of identiteit.

X EQV Y is waar dan en dan alleen als beide dezelfde waarheidswaarde hebben.

Waarheidstabel:

5. De eksklusieve OF funktie (XOR):

X XOR Y is waar dan en dan alleen als X waar is of als Y waar is maar niet wanneer beide het zijn.

Waarheidstabel:

6. De impliklatie (IMP) , of de 'besluitregel'. (Als... Dan...)

X impliceert Y ( =uit X volgt Y) dan en dan alleen als wanneer X waar is ook Y waar is en wanneer X vals is Y zowel waar als vals mag zijn. Dit kan eenvoudiger worden uitgedrukt met een negatie: X impliceert Y is vals, dan en dan alleen als X waar is en Y vals is.

Waarheidstabel:

Deze relatie vormt de formele weergave van de stelling dat 'uit het absurde, eender wat kan worden afgeleid'. Over de geldigheid hiervan hebben filozofen en logici hele bibliotheken volgeschreven. Vooraleer je al te intuitief deze logische wet geneigd zou zijn te verwerpen, bedenk echter eerst even dat hij kan worden afgeleid uit op het eerste gezicht volkomen evident lijkende logische wetten, meer bepaald uit de wet van het uitgesloten derde! ( X OR NOT(X)) = True

Volgende waarheidswaardentabel omvat alle door de komputer (binnen Basic) verwerkbare Booleaanse algebraische funkties:

Parenthesis:

Hoewel het niet tot het onderwerp van deze kursus behoort, wil ik hier toch graag even enkele grondslagen van de klassieke formele logika (de basis voor de onlangs afgeschafte moderne wiskunde...) in herinnering brengen. De waarheidswaarden voor de Booleaanse funkties zoals hierboven beschreven en weergegeven zijn immers geheel hierop gesteund en eruit afleidbaar. Een diepgaand inzicht in deze formeel logische calculus komt trouwens ook het leren formuleren van kompositorische algoritmes in termen van logische samenhangen zeer sterk ten goede.

Axiomas van de Booleaanse Algebra:

Dit zijn beweringen waarvan de absolute (geldigheid) waarheid wordt aangenomen.

1. (X OR X) IMP X het idempotentie-axioma

2. X IMP (Y OR X) het toevoegings-axioma

3. (X OR Y) IMP (Y OR X) het verwisselbaarheids-axioma

4. (X IMP Y) IMP ((Z OR X) IMP (Z OR Y))

(merk op dat er slechts 2 operatoren gebruikt worden !)

Andere operatoren worden bij definitie bepaald :

1. X IMP Y = (NOT X) OR Y

2. X AND Y = NOT((NOT X) OR (NOT Y))

De algebraische calculus wordt doorgevoerd onder gebruikmaking van enkele eenvoudige afleidingsregels :

1. Subsitutie-regel: een variabele mag door een andere of een kombinatie van andere, vervangen worden mits dat overal gebeurt in de bewering, zonder dat dit afbreuk doet aan het logisch resultaat van de bewering.

2. Modus Ponens : als (X IMP Y) gegeven is dan mag , gegeven X, tot Y besloten worden.

Het is niet mogelijk de hier gegeven fundamentele Booleaanse funkties anders te definieren binnen een komputerprogramma. Komputers slikken zonder speciale maatregelen op het vlak van de software, alleen klassieke logikas. De axiomas die hier zijn weergeven zijn zelfs op chip-nivo in de hardware van de komputer zelf vastgelegd. Chips die de hier beschreven logische funkties rechtstreeks uitvoeren behoren tot de meest fundamentele komponenten waaruit komputers worden opgebouwd. Ook de naamgeving van die chips stemt overeen met het erdoor uitgevoerde booleaanse algoritme. Zo is de Logische schakeling met het nummer 7400 bvb. een viervoudig uitgevoerde NAND-funktie (OUT = NOT (X AND Y) ), de 7427 een drievoudige NOR-funktie met 3 input variabelen die volgende funktie uitvoert : OUT= NOT((X OR Y) OR Z).

Het 'bewijzen' van een formeel-logische propositie met behulp van de komputer, is betrekkelijk eenvoudig , omdat we de komputer erg gemakkelijk de waarheid van een bewering kunnen laten onderzoeken voor alle mogelijke kombinaties van de erin voorkomende variabelen.

Willen we echter ook met niet-klassieke logika's kunnen werken, dan dienen we eigen funkties te definieren en er de gewenste waarheidstabellen voor vast te leggen.

Bij het formuleren van axiomas voor alternatieve logika's kan je echter niet zomaar eender wat bepalen! Enkele fundamentele eisen die aan welkdanige logika ook kunnen worden gesteld zijn die van:

a. beslisbaarheid: van elke geldig geformuleerde formule moet de waarheidswaarde bepaalbaar zijn, m.a.w. de afleidbaarheid ervan in een eindig aantal stappen vanuit de axiomas moet kunnen nagegaan worden.

b. konsistentie: toepassing van het axiomasysteem en de afleidingsregels mag nooit tot tegenstrijdige beweringen leiden. (Kontradikties mogen niet bewezen kunnen worden).

c. volledigheid: elke ware bewering moet binnen het systeem kunnen bewezen worden en erin vervat liggen.

Dat het voldoen aan al deze eisen, zelfs voor de klassieke logika een onhoudbare zaak is, werd door Kurt Gödel bewezen, in een van de mooiste bewijsvoeringen uit de geschiedenis van de filozofie van deze eeuw. Hij bewees namelijk dat de formule die van zichzelf zegt dat ze niet bewijsbaar is, een geldige formule is...

B:HEXADECIMALE BOOLEAANSE ALGEBRA

Alle Booleaanse funkties kunnen door de komputer worden toegepast op numerieke waarden in het algemeen. Om dit te begrijpen moeten we het binaire en hexadecimale stelsel goed in het hoofd hebben en houden.

Wat de komputer immers in werkelijkheid doet wanneer we hem het resultaat vragen van 5 AND 7 verloopt alsvolgt :

5 is binair = 0 0 0 0 0 1 0 1

7 is binair = 0 0 0 0 0 1 1 1

de AND funktie per bit= 0 0 0 0 0 1 0 1 wat opnieuw 5 oplevert

Aangezien deze waarde niet 0 is , beschouwt de komputer het logisch resultaat van deze bewerking als WAAR ( = niet 0)

Stel dat we vragen 5 OR 7 te berekenen, dan krijgen we door bit per bit de hiervoor beschreven Booleaanse waarheidstabellen toe te passen, volgend resultaat :

5 = 0 0 0 0 0 1 0 1

7 = 0 0 0 0 0 1 1 1

5 OR 7 = 0 0 0 0 0 1 1 1 = 7

Ook dit resultaat is voor de komputer logisch WAAR.

We moeten dus steeds goed de logische waarheidswaarde onderscheiden van het numerieke resultaat van de Booleaanse bewerking. Alleen wanneer het resultaat 0 is ,stemt de logische waarde overeen met de numerieke!

Analyzeren we om dit te verduidelijken volgende Booleaanse bewerking :

85 = 0 1 0 1 0 1 0 1 (=&H55)

42 = 0 0 1 0 1 0 1 0 (=&H2A)

AND 0 0 0 0 0 0 0 0 = 0

Zolang we ons met positieve getallen bezighouden, is dit alles nogal eenvoudig in te zien. Vanzodra we echter de NOT funktie gebruiken, of gehele getallen groter dan 32767 (voor komputers of kompilers die de Booleaanse bewerkingen uitvoeren op getallen van niet meer dan 16 bit-posities), krijgen we te maken met de zgn. '2's complement' representatie van negatieve getallen in het binair of hexadecimaal systeem. (Zie vorige hoofdstukken over getalstelsels).

Alle Booleaanse bewerkingen worden in de komputer immers uitgevoerd op 'woord'-breedte (=2 bytes = 16 bits), tenzij ze werden gedeklareerd als 'long integer', in welks geval ze uit 4 bytes bestaan. Wanneer een 'word' begint met een binaire 1 op de plaats van het MSB, dan moet de waarde van het getal opgevat worden als zijnde negatief.

De binaire representatie van het getal -1 is, ter herinnering, immers &HFFFF.

Om in alle gevallen korrekt te zijn dienen we onze Booleaanse bewerkingen dan ook steeds in hun volle bit-breedte toe te passen. Enkele bewerkingsvoorbeelden mogen dit verduidelijken:

1 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

NOT 1 = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0

korrektie voor 2's Compl.: +1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

(1 optellen bij het resultaat)

In hexadecimale notatie is dit &HFFFF, wat decimaal overeenkomt met -1. Let echter op ! : NOT 1 levert -1 op , maar NOT -1 (wat je geneigd zou zijn te lezen als NIET WAAR, en dus vals) levert niet 0 op, zoals je zou verwachten:

-1 = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

omgekeerde korrektie = - 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0

NOT -1= 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

Enkele andere voorbeelden :

85 = 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1

NOT 85 = 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0

korrektie +1 = + 1

1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1

 

144 = 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0

199 = 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1

144 IMP 199= 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1

2's complement korrektie : + 1

Resultaat = 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0

, wat decimaal overeenkomt met -16 !

De komplikaties met de '2's complement' notatie treden zoals men kan merken pas op wanneer we beroep doen op hetzij getallen groter dan de helft van het bits-bereik, hetzij op funkties die negaties zijn of in hun waarheidstabel voor twee maal 0 in de input, WAAR opleveren in de output.

C:TOEPASSINGEN

Booleaanse algebra wordt zeer intensief gebruikt in komputerprogrammas die gericht zijn op bit-manipulaties. Wanneer we bijvoorbeeld de komputer inzetten om via uitgangspoorten instrumenten of andere schakelingen te sturen, dan zijn Booleaanse bewerkingen de snelste en meest geschikte die programmeertalen zoals Assembler en Basic ons te bieden hebben.

We willen dit graag in enkele voorbeelden illustreren :

1. 'Setting a bit'

Dit noemt men het 1 maken van een bepaald bit op een geheugenplaats of op een uitgangspoort.

Veronderstel dat we bit nr. 3 van poortadres &H3AF hoog (=1) willen maken, dan kan dit eenvoudig worden bereikt door volgende instruktiereeks :

A=INP(&H3AF) ' lees het byte op adres &H3AF

OUT(&H3AF,A OR 8)

Immers bit 3 komt overeen met : 0 0 0 0 1 0 0 0 binair

De waarde van A is variabel : x x x x x x x x

Resultaat : : x x x x 1 x x x

We weten dat de OR funktie steeds 1 oplevert wanneer een van beide inputs 1 is of, wanneer beide 1 zijn. Het is duidelijk dan wanneer we de funktie A OR 8 uitvoeren het resultaat noodzakelijkerwijze een 1 moet opleveren op de plaats van bit 3. Alle andere bits zullen na deze bewerking ongewijzigd zijn gebleven.

Verifieer zelf dat hetvolgende programma in een willekeurig byte overal waar nog geen binaire 1 stond, een 1 plaatst. Aan het einde van de lus is byte dan ook steeds 255:

FOR I% = 0 TO 7

BYTE% = BYTE% OR 2^I%

NEXT I%

2.'Resetting a bit'

Een bit resetten komt overeen met het 0 maken van een of meer bepaalde bits in het geheugen of I/O bereik.

Onderstel dat we bit 7 willen resetten op I/O adres &H760:

Eerst zoeken we een Booleaanse funktie die ons gegarandeerd 0 oplevert voor een tweede ingang die 1 ofwel 0 kan zijn. Het ligt nogal voor de hand hiervoor (zie tabel) de AND funktie te gebruiken. Immers de AND-funktie kan nooit 1 opleveren als niet beide (inputs) ingangen 1 zijn.

De instruktiereeks wordt dus:

A= INP(&H760)

OUT(&H760,A AND 127)

Immers bit 7=0 is binair : 0 1 1 1 1 1 1 1

De waarde van A is variabel: x x x x x x x x

A AND 127 = : 0 x x x x x x x

Verifieer zelf dat volgend programma , voor elke willekeurige waarde van byte (tussen 0 en 255) op elk plaats in de binaire voorstelling van die byte waar niet reeds een 0 stond, een nul schrijft. De eindwaarde bij het verlaten van de lus voor byte is dan ook 0.

FOR I% = 0 TO 7

BYTE% = BYTE% AND NOT 2^I%

NEXT I%

Verifieer ook dat volgend programma alle bit-posities voor de waarde van byte omkeert :

FOR I% = 0 TO 7

BYTE% = BYTE% XOR 2^I%

NEXT I%

3.'Check a bit'

Het hier gestelde probleem is na te gaan of een bepaald bit wel degelijk 1 is. Het antwoord op onze vraag moet niet-0 ( waar) zijn als het betreffende bit 1 is. M.a.w. de waarheidswaarde van beide dient gelijk te zijn.Een bruikbare Booleaanse instruktie die bit 6 van adres &H270 test ,zou hier dan ook kunnen zijn:

A= INP(&H270) AND 64

Laten we dit even nagaan :

64 is in binair : 0 1 0 0 0 0 0 0

het byte op &H270 is variabel: x x x x x x x x

&H270 AND 64 0 x 0 0 0 0 0 0

De waarde van A zal dan ook ofwel 0 zijn ( nml wanneer bit 6 op adres &H270 ook 0 is ) ofwel 64, wanneer bit 6 ook 1 is. In een konditioneel statement kunnen we dit zonder zelfs gebruik te maken van de tussenvariabele A, gebruiken:

vb: IF INP(&H270) AND 64 THEN PRINT "Bit 6 is HOOG"

Een in het kader van deze kursus wel bijzonder praktische en handige toepassing, is te vinden in programmas die binnenkomende midi-bytes moeten verwerken.

vb: IF BYTE AND 128 wanneer dit waar is, dan moet BYTE een midi-status byte zijn

4.Two's complement berekening

Willen we een getal via Booleaanse funkties omzetten naar zijn two's komplement representatie dan kunnen we volgend eenvoudig algoritme benutten:

Y = NOT(X) XOR 1

Hierin is Y het two's-komplement van een getal x. Merk op dat dit algoritme heel precies doet wat we ook met de hand doen wanneer we getallen naar hun two's komplement omzetten. Immers de NOT funktie keert alle binaire bits om, terwijl de XOR 1 funktie zorg voor draagt dat er een eenheid wordt opgeteld bij het resultaat.

Dit algoritme komt erg van pas, wanneer we een zgn. checksum moeten berekenen. Een checksum is immers niets anders dan het two's komplement van de som van een bekend aantal bytes. Dit wordt gebruikt om de juistheid van de overdracht van een pakket gegevens na te gaan. De verzender van het pakket geeft het resultaat van de checksum als laatste byte , terwijl de ontvanger de som narekent en vergelijkt met de waarde van de checksum zoals overgedragen. Uiteraard dienen beide waarden gelijk te zijn. Het nut van deze techniek zal later blijken wanneer we het hebben over midi-dumps en FM-synteze programmas. Ook bij het programmeren van Eproms worden checksums algemeen gebruikt.

5. Tellers opgebouwd met Boole-funkties

Vaak ontmoetten we in programmas luskonstrukties zoals deze:

DO

i%= (i% + 1) MOD 256

...

LOOP

Dit is een teller die i% laat tellen tot 255 en dan telkens opnieuw begint vanaf 0. Het nadeel aan deze konstruktie is dan telkens de lus wordt doorlopen een deling (vervat in de MOD instruktie) dient te worden uitgevoerd. Delingen nu vergen heel wat klokcycli van de processor, zodat door deze konstruktie heel wat nuttige komputertijd verloren gaat. De begrenzing van 0-255 voor deze teller kan ook worden geschreven als:

i%= i% AND &HFF

(bewijs dit zelf).

Maar, ook de +1 teller, kan met Boole-algebra sneller worden gekodeerd:

i%=ABS(NOT i%)

(bewijs ook dit).

Waardoor onze lus, gebruik makend van deze vertaling eruit komt te zien als:

DO

i%= ABS(NOT i%) AND &HFF

...

LOOP

De ontwikkelaars van Power Basic en van C++ hebben dit ook ingezien, en daarom voorzagen zij in instrukties zoals INCR i%, die door de kompiler in erg efficiente machinekode kunnen worden omgezet zonder dat de gebruiker daarom toch weinig leesbare konstrrukties zoals hier getoond hoeft te gebruiken.

6.Verwerkingssnelheid

Een van de grote voordelen in het gebruik van Booleaanse funkties boven de klassieke wiskundige bewerkingen, is dat zij op komputernivo zeer dicht bij de machine zelf staan en daarom niet alleen bijzonder weinig geheugen vragen, maar bovendien ook uiterst snel worden verwerkt. Wie ook maar even in een Assembler handleiding heeft gekeken, zal vlug alle Booleaanse funkties, naast heel wat andere handige bit-manipulaties (die we in hogere programmeertalen moeten derven), kunnen terugvinden, en dit onder zowat dezelfde namen als die gebruikt in Basic. In de 8086/80486 assembler kennen we zo de mnemonics : OR , AND ,NEG, NOT, XOR, naast ROL ,ROR instrukties die op bitnivo bijzonder nuttig zijn maar helaas in de meeste Basics ontbreken. Omwille van hun nut in komputerbesturingstoepassingen en algoritmes wil ik er echter toch ook binnen Basic wat aandacht aan besteden.

5. ROR en ROL : Rotate Left - Rotate Right

Deze instrukties die we zullen pogen te realizeren binnen Basic laten ons toe binnen een byte, of binnen een 'word' alle bits een positie respektievelijk naar links of naar rechts te verschuiven. De werking hiervan kan men zich het best voorstellen aan de hand van het model van een zgn.' running light' zoals toegepast in de lichtreklamesektor. Ook de gekende "lichtkrant" kan hier als model fungeren.

Analyze van het probleem:

- Rotatie naar links : 

gegeven een bitpatroon bvb,: 1 0 1 1 0 1 0 1

rotatie naar links (1)0 1 1 0 1 0 1(1)

|_______________|

Dit effect op bit-nivo kan worden bereikt door de waarde vervat in het door te schuiven byte te vermenigvuldigen met 2.

Vermenigvuldigen met 4 of volgende machten van 2, verschuift het bitpatroon met een aantal stappen overeenkomstig de exponent van 2 die gebruikt wordt.

Wanneer we de bits een stap naar links willen doorschuiven, zonder de bits langs rechts opnieuw te zien verschijnen kunnen we volgende code gebruiken:

BYTE=(BYTE *2)MOD 256

wanneer we deze operatie op 16-bit breedte willen doorvoeren wordt dit echter:

WORD=(WORD *2)MOD 65536

Willen we het bitpatroon opnieuw aan de rechterkant zien binnenkomen, dan moeten we alsvolgt tewerk gaan:

1. test of hoogste bit 1 of 0 is

IF BYTE AND 128 THEN BIT=1 ELSE BIT=0

ofwel

BIT= BYTE MOD 128

2. schuif een stap door naar links

BYTE = (BYTE * 2) MOD 256

3. voeg het hoogste bit rechts opnieuw toe

BYTE = BYTE OR BIT

Dit kan ook korter geformuleerd worden als:

BYTE =((BYTE * 2) MOD 256) OR (BYTE MOD 128)

Volgend programma laat alle mogelijke patronen, eenmaal doorheen de woord- sekwens lopen (16-bits patroon):

FOR WORD=0 TO 65536

FOR STAP=0 TO 15

WORD=((WORD*2) MOD 65536) OR (WORD MOD 32768)

NEXT STAP

NEXT WORD

Een voorbeeld met telkens andere willekeurige patronen op 8-bits:

START:

BYTE%=RND(1)*256

FOR STAP=0 TO 7

BYTE=((BYTE*2) MOD 256) OR (BYTE MOD 128)

NEXT STAP

GOTO START

- Rotatie naar rechts

Probeer dit nu zelf uit te werken voor rotaties naar rechts. Bedenk daarbij dat we nu alle vermenigvuldigen, die immers het patroon naar links doen opschuiven, nu zullen moeten vervangen door delingen door 2.

Power Basic beschikt over een heel arsenaal aan funkties waarmee bits in getallen kunnen worden verschoven en gemanipuleerd: ROTATE LEFT, ROTATE RIGHT, BIT() , HIWORD, LOWRD, HIBYT, LOBYT, SHIFT RIGHT x, n, SHIFT LEFT x, ... Maak er waar mogelijk gebruik van!

6. Gray kode

Wanneer we gewoon tellen -in het binaire systeem- dan is het aantal bits dat van waarde veranderd bij elke getalovergang ongelijk. Immers wanneer we bvb. van 7 naar 8 overgaan, krijgen 0111 => 1000 en veranderen alle 4 bits van waarde. Gray bedacht een telsysteem waarbij telkens slechts een enkel bit veranderd, een kode die heel wat minder storingen oplevert en ook -in een elektrrisch schakelende kontekst- heel wat minder energie vraagt. De regel, in woorden geformuleerd luidt dat we om de opvolger van een getal te vinden steeds het laagste bit omschakelen dat een niet eerder in de telreeks voorkomend getal oplevert.

Dit ziet er voor de eerste 18 getallen uit alsvolgt:

De omzetting van getallen naar hun Gray-gekodeerd equivalent kan heel eenvoudig gebeuren door gebruik te maken van boole algebra.

Een funktie waarin dit is gerealiseerd kan eruit zien alsvolgt:

FUNCTION Gray (n AS DWORD) AS DWORD

LOCAL b AS DWORD

b = n

SHIFT RIGHT b, 1

FUNCTION = b XOR n

END FUNCTION

Verdere aanbevolen lektuur:

(zie ook algemene bibliografie )

- HACK, Ulrich & HOFFMANN, Markus "Het GAL-Boek" Programmeerbare logika in theorie en praktijk

ed.: Elektuur, Beek, 1992 ISBN: 90-5381-033-1

Filedate: 840930 - last update:99-12-21