Forma normale disgiuntiva Se nella pagina precedente abbiamo costruito i monomi qui possiamo dire molto intuitivamente che proviamo a costruire i polinomi; intendiamoci: saranno molto diversi dai polinomi che conosciamo dall' algebra elementare Per semplicita', d'ora in avanti, dove non vi siano dubbi, tralasciamo il segno del prodotto cioe' invece di scrivere x·y' scriveremo semplicemente xy' sottointendendo il · Consideriamo un'espressione composta dalla somma di uno o piu' prodotti fondamentali, tali che nessuno di essi sia contenuto in un altro: chiameremo tale espressione forma normale disgiuntiva od anche forma di somma-prodotti Esempi di espressione in forma normale disgiuntiva Espressione = xy'z Espressione = x'y + xyz' Espressione = xy'z + x'y + xyz' Vediamo anche un esempio di espressione non in forma normale disgiuntiva Espressione =xy'z + x'y + xy' qui l'ultimo termine xy' e' contenuto nel primo xy'z pero' se faccio xy'z + x'y + xy' = xy'z + xy' + x'y (legge commutativa) xy'z + xy' + x'y = (xy'z + xy') + x'y (legge associativa) (xy'z + xy') + x'y = (xy'·(1+z)) + x'y (legge distributiva) (xy'·(1+z)) + x'y = xy' + x'y (legge dei confini) il risultato xy' + x'y e' ora in forma normale disgiuntiva Cioe' possiamo dire: Un'espressione booleana diversa da 0 puo' essere sempre messa in forma normale disgiuntiva Per poterlo fare dobbiamo seguire queste regole Utilizzando le leggi di de Morgan e del doppio complemento possiamo spostare l'operazione di complemento verso l'interno delle parentesi fino ad applicarla alle lettere: allora l'espressione sara' formata solamente da somme e prodotti di termini Utilizzando la proprieta'distributiva del prodotto rispetto alla somma trasformiamo l'espressione in una somma di prodotti: cioe' possiamo eseguire le moltiplicazioni come se fossero "polinomi" ottenendo una somma di "monomi": e' possibile combinando proprieta' associativa e distributiva del prodotto rispetto alla somma Utilizziamo poi le proprieta' opportune (idempotenza,assorbimento, complemento,....) per trasformare ogni prodotto o in 0 oppure in un prodotto fondamentale Infine utilizzando la legge dei confini trasformiamo l'espressione in forma normale disgiuntiva Vediamo un esempio Esercizio: trasformare in forma normale disgiuntiva l'espressione ((xy')'z)'(x+y')(yz')' = Non indico "tutti" i passaggi, tipo la proprieta' commutativa ed associativa per ragioni di spazio, spero che sia chiaro lo stesso il procedimento ((xy')'z)'(x+y')(yz')' = porto il complementare da fuori a dentro le parentesi piu' esterne (ti ricordo che + diventa · e viceversa) = ((xy')'' + z')(x+y')(y' + z'') = applico la legge del doppio complemento = (xy' + z')(x+y')(y'+z) = applico la proprieta' distributiva (moltiplico i primi due) = (xy'x + xy'y' + z'x + z'y')(y'+z) = leggi dell'idempotenza per il prodotto = (xy' + xy'+ z'x + z'y')(y'+z)= ancora la legge dell'idempotenza per la somma = (xy'+z'x + z'y')(y'+z)= applico la proprieta' distributiva (moltiplico) = xy'y'+ xy'z +z'xy' + z'xz + z'y'y' +z'y'z = applico la legge dell'idempotenza e del complemento = xy'+ xy'z +z'xy' + 0x + z'y' + 0y' = per la legge dell'identita' = xy'+ xy'z +z'xy' + z'y' = applico la legge dellassorbimento (xy' e' contenuto in z'xy') = xy'z +z'xy' + z'y' = applico la legge dellassorbimento (z'y' e' contenuto in z'xy') = xy'z +z'xy' e questa e' la forma normale disgiuntiva