Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
I corsi di Ingegneria
 
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