Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Bruno Fadini » 5.Rappresentazione di funzioni booleane - Modulo 1


Corso di Reti logiche

Rappresentazione di funzioni booleane

Argomenti

  • Tabelle di verità
  • Forme canoniche
  • Mappe di Karnaugh
  • Funzioni non completamente specificate

Tabelle di verità

Definizione

  • Essendo l’algebra finita…
    • una funzione può essere definita attraverso una tabella che per ogni combinazione di valori delle variabili indipendenti associa il corrispondente valore della funzione.
  • Tabella di verità (dall’algebra della logica)
    • Tabella che definisce la funzione
  • Tabelle di verità banali
    • AND, OR, NOT (lez.3)

Tabelle di verità e forma canonica

In figura si illustra come passare dalla tabella di verità alla forma algebrica

Forma normale P:

  • y = a·b·c + a·b·c + a·b·c

Altra forma elementare P:

  • y = a·b + a·b·c
Dalla tabella di verità alla forma algebrica

Dalla tabella di verità alla forma algebrica


Forme canoniche

Forma (normale) canonica di primo tipo (P)

  • È unica per ogni funzione, funzioni diverse hanno forma canonica diversa
  • Una funzione di n variabili ha 2n mintermini
  • Esistono 22n funzioni di n variabili
  • Il numero binario formato dalle ai è uno che identifica la funzione e ne è detto “numero caratteristico”
Forma (normale) canonica di primo tipo (P)

Forma (normale) canonica di primo tipo (P)


Forme canoniche

Forma (normale) canonica di secondo tipo (S)

  • Si ottiene per dualità dalla forma P
  • Applicativamente importante come la forma P
  • La dimostrazione in figura è utile per fissare le idee
Forma (normale) canonica di secondo tipo (S)

Forma (normale) canonica di secondo tipo (S)

Dimostrazione

Dimostrazione


Mappe di Karnaugh

  • Mezzi grafici per la rappresentazione e la manipolazione di funzioni booleane di poche variabili (in genere n ≤ 5).
  • Organizzazione topografica delle tabelle di verità
    • metodo “operativo” per il progetto e la sintesi di reti con poche variabili
  • Possono essere costruite a partire dall’espressione della funzione in forma elementare o canonica di tipo P o S.

Per trattare le forme per funzioni di n variabili

  • La mappa espone 2n quadratini, uno per ogni mintermine, riempiti da un “1″ se αi=1 – sono clausole di ordine n
  • Mintermini che generano consenso sono adiacenti – sono clausole di ordine n-1
  • Clausole n-1 adiacenti sono clausole di ordine n-2
  • … e così via
  • Le clausole sono dette anche sottocubi

Mappe di Karnaugh

Mappe di Karnaugh

Mappe di Karnaugh


Mappe di Karnaugh

Confronto tra funzioni: un esempio

Costruendone la mappa a partire dalle rispettive forme è possibile verificare se due forme algebriche corrispondono alla stessa funzione.

Confronto tra funzioni

Confronto tra funzioni


Funzioni incompletamente specificate

Definizioni

  • Punto di indifferenza (don’t care): punto in corrispondenza del quale non è specificato il valore della funzione (può indifferentemente assumere il valore 0 oppure 1).
    • Si indica con uno dei simboli- Φ
  • Funzione compatibile con una incompleta: ha gli stessi valori laddove specificati, valori qualsiasi laddove non specificati
  • Condizione di vincolo: indica i punti in cui la funzione è specificata
    • Attraverso una equazione booleana

Funzioni incompletamente specificate

Equazioni booleane

  • Un’equazione booleana si risolve facilmente se posta nella forma descritta in figura.
  • Ogni mintermine per il quale è αi = 1 è una soluzione
  • Se la forma della condizione di vincolo è diversa, la si riconduce a questa con banali passaggi
Equazione booleana

Equazione booleana


Funzioni incompletamente specificate

Un esempio

  • Condizione di vincolo: x·y=0
    • Negando e applicando De Morgan: x + y = 1
    • Sviluppando: x y + x y + x y = 1
    • Ne seguono i punti specificati: 00, 01, 10
  • Funzioni compatibili
    • x ⊕ y; x + y
Mappa di Karnaugh (esempio)

Mappa di Karnaugh (esempio)


Prossima lezione

Funzioni XOR, EQ, parità e disparità – Modulo 2

I materiali di supporto della lezione

B. Fadini, A. Esposito, Teoria e Progetto delle Reti Logiche, Napoli Liguori Ed., II ed, 1994. Cap. I

U. De Carlini, B. Fadini, Macchine per l'elaborazione delle informazioni, Napoli Liguori Ed., II ed., 1995 (Capitoli III e VII)

B. Fadini, N. Mazzocca, Reti Logiche – Complementi ed Esercizi, Napoli Liguori Ed. 1995

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion