I valori 0 e 1 che abbiamo visto nell'introduzione alla logica digitale non sono altro che delle ridenominazione delle variabili TRUE e FALSE dell'algebra di Boole. Vediamone alcune proprietà:
| Nome | Forma in AND | Forma in OR |
|---|---|---|
| Legge di identità | 1A = A | 0 + A = A |
| Legge di annullabilità | 0A = 0 | 1 + A = 1 |
| Legge dei complementi | AA = A | A + A = A |
| Legge di inversione | ||
| Legge di commutatività | AB = BA | A + B = B + A |
| Legge di associatività | (AB)C = A(BC) | (A + B) + C = A + (B + C) |
| Legge di distributività | A + BC = (A + B)(A + C) | A (B + C) = AB + AC |
| Legge di assorbimento | A (A + B) = A | A + AB = A |
| Legge di De Morgan |
La moltiplicazione tra due valori è il simbolo
Il simbolo generalmente usato per la moltiplicazione rappresenta l'AND logico.
Mentre il simbolo di addizione +, rappresenta l'OR logico.
Quando una variabile presenta una linea sopra
Una qualsiasi combinazione di varaibili e operatori logici, origina una espressione logica.
Esempio:
costruendo una tavola di verità si riesce a rendersi conto che tale espressione logica sarà vera solo se
Le espressioni logiche possono anche essere dimostrare senza l'uso di tavole di verità, modificando l'espressione in modo tale da provare a semplificarla.
Proviamo a dimostrare le due forme equivalenti per lo XOR e calcoliamo il numero di porte e di transistor.
per la legge di De Morgan possiamo scrivere
moltiplico tutto:
Se
Ciò che resta è:
dimostrato.
Funzioni booleane...
Una funzione booleana di n variabili
- tavole di verità
- formule algebriche
- mappe di Karnaug
- diagrammi binari decisionali (binary decision diagrams: BDDs)
Tavole di verità...
Una tavola di verità descrive il valore di una funzione Booleana attraverso tutte le combinaioni di input; n input corrispondono a
Due o più espressioni sono equivalenti se hanno tabelle di verità identiche.
Dalla tabella di verità si possono poi estrapolare delle formule attraverso due modalità:
- forma normale disgiuntiva: è la sommatoria (OR) di termini, ciascuno dei quali è un prodotto (AND) di letterali, ovvero dei nomi delle variabili o negazione dei nomi delle variabili in ingresso. La formula ottenuta è minimale quando, applicando le proprietà algebriche di equivalenza non è possibile ottenere una forma normale disgiuntiva equivalente con numero di letterali inferiore;
- forma normale congiuntiva: è l'opposto della forma precedente, ossia un prodotto (AND) di termini, ciascuno dei quali è una sommatoria (OR) di letterali.
Applicazione delle forme normali ad una tavola di verità...
Supponiamo di avere:
| A | B | C | M |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Diciamo che M è il risultato della combinazione dei letterali A, B, C.
Diciamo di prendere i casi in cui M = 1 e di applicare su quelle espressioni la forma normale disgiuntiva.
Allo stesso modo potremmo applicare la forma normale congiuntiva:
Forma normale disgiuntiva è la somma (OR) di termini in AND.
Forma normale congiuntiva è il prodotto (AND) di termini in OR.
Da tabella di verità a formula algebrica a circuito logico...
Passi:
- data una tabella di verità
- calcolare la formula algebrica (in forma normale congiuntiva o disgiuntiva)
- disporre le varaibili che partecipano alla formula in modo che abbiano un complementare, quindi disporre un invertitore per ogni variabile
- introdurre una porta AND per ogni risultato pari a 1 (M)
- collegare le porte agli input
- inviare l'output in una porta OR
Vediamo passo-passo come fare:
abbiamo già estrapolato le formule dalla tabella di verità, per questo esempio ci riferiamo alla formula in forma disgiuntiva, che era
Ogni variabile deve avere il suo complementare (grazie ad un inverter):
A questo punto aggiungiamo tante porte AND quanti sono gli 1 nel colonna risultante della tabella di verità:
Adesso possiamo effettuare i collegamenti come la nostra formula "dice":
Per finire, le porte AND, vanno collegate ad una porta OR:
Il nostro circuito digitale è completo.
Se due linee che si incrociano hanno un puntino, vuol dire che le due linee sono collegate.
Se si incrociano, ma nessun puntino evidenzia il loro incrocio, le linee non sono collegate tra di loro.
Implementazione di circuiti...
Per ottenere un certo output possono esistere diversi circuiti. Se diversi circuiti realizzano la stessa funzione booleana sono equivalenti.
Tra diversi circuiti equivalenti tra di loro è meglio utilizzare il circuito che implementa un numero inferiore di porte (anche dette gate in inglese) logiche.
Due circuiti logici equivalenti, il secondo usa un numero di porte logiche inferiore, ed è in questo senso considerata una implementazione migliore, in termini di costi e accessi.
I circuiti integrati nei componenti per computer, sono classificati in base al numero di transistor che usano:
- SSI: small scale integrated (1-10 transistor)
- MSI: medium scale integrated (10-100 transistor)
- LSI: large scale integrated (100-100.000 transistor)
- VLSI: very large scale integrated (più di 100.000 transistor)
- ULSI: ultra large scale integrated (fino a 10 milioni di transistor)
A questo punto della trattazione possiamo passare ai circuiti combinatori.