Disjunctieve normaalvorm

Omhoog Conjuctieve normaalvorm Disjunctieve normaalvorm Waarheidstabellen

Oefeningen 8-bit floating point

Een Booleaanse uitdrukking kan men steeds herleiden naar haar zogenaamde disjunctieve normaalvorm, dikwijls afgekort als DNV (SOP: Sum of Products). De DNV van een Booleaanse functie is uniek (zonder bewijs). Pas daarvoor volgende constructie (3 stappen) toe op om het even welke Booleaanse uitdrukking:

  1. zoek alle n-tupels (a1, a2, ..., an-1, an) waarvoor f(a1, a2, ..., an-1, an)= 1 ,
  2. stel voor elk n-tupel Ai= (a1, a2, ..., an-1, an) dat je gevonden hebt in stap 1) mi= y1 . y2 . ... yn-1 . yn waarbij yj= xj als aj= 1 en yj= xj' als aj= 0 , j neemt de waarden aan van 1 tot en met n voor elke i, waarbij i gaat van 0 tot en met k, dit is het aantal outputs dat waarde één (1) oplevert
  3. verbind alle mi's uit stap 2) door disjuncties

  1. 3 tripels waarvan F(Ai)=1
    K = 3
    A1 = (0, 0, 0) , A3 = (0, 1, 0) , A4 = (0, 1, 1)
  2. A1: m1 = x' . y' . z'
    A3: m2 = x' . y . z'
    A4: m3 = x' . y . z
  3. DNV ((z' + y') . x') = (x' . y' . z') + (x' . y . z') + (z' . y . z)

De DNV is niet altijd (zelfs meestal niet) de meest eenvoudige Booleaanse uitdrukking:

 

Oefeningen 8-bit floating point

De tweede methode noemt men de rechtstreekse methode en is een toepassing van wetten en eigenschappen van Boole-algebra's. Deze tweede methode kan korter uitvallen dan de eerste, vooral wanneer er tamelijk veel variabelen zijn. Het nadeel is evenwel dat het patroon van de berekeningen niet vastligt (want men weet niet vooraf welke wetten en, of eigenschappen bruikbaar zullen zijn)

Enkele tips:

 

Oefeningen 8-bit floating point

  (x1 + x2) . x3  
= (x1 . x3) + (x2 . x3) distributiviteit
= (x1 . x3 . 1) + (x2 . x3 . 1) identiteitswet (x2)
= (x1 . x3 . (x2 + x2')) + (x2 . x3 . (x1 + x1')) complementwet (x2)
= (x1 . x3 . x2) + (x1 . x3 . x2') + (x2 . x3 . x1) + (x2 . x3 . x1') distributiviteit (x2)
= (x1 . x2 . x3) + (x1 . x2' . x3) + (x1 . x2 . x3) + (x1' . x2 . x3) commutativiteit
= (x1 . x2 . x3) + (x1 . x2 . x3) + (x1 . x2' . x3) + (x1' . x2 . x3) commutativiteit
= (x1 . x2 . x3) + (x1 . x2' . x3) + (x1' . x2 . x3)