Circuiti digitali - Algebra booleana
Boolean Algebraè un'algebra, che si occupa di numeri binari e variabili binarie. Quindi, è anche chiamato come algebra binaria o algebra logica. Un matematico, di nome George Boole, aveva sviluppato questa algebra nel 1854. Le variabili usate in questa algebra sono anche chiamate variabili booleane.
L'intervallo di tensioni corrispondenti a "Alto" logico è rappresentato con "1" e l'intervallo di tensioni corrispondenti a "Basso" logico è rappresentato con "0".
Postulati e leggi fondamentali dell'algebra booleana
In questa sezione, discutiamo dei postulati booleani e delle leggi di base utilizzati nell'algebra booleana. Questi sono utili per ridurre al minimo le funzioni booleane.
Postulati booleani
Considera i numeri binari 0 e 1, la variabile booleana (x) e il suo complemento (x '). La variabile booleana o il suo complemento è nota comeliteral. I quattro possibililogical OR le operazioni tra questi letterali e numeri binari sono mostrate di seguito.
x + 0 = x
x + 1 = 1
x + x = x
x + x '= 1
Allo stesso modo, i quattro possibili logical AND le operazioni tra questi letterali e numeri binari sono mostrate di seguito.
x.1 = x
x.0 = 0
xx = x
x.x '= 0
Questi sono i semplici postulati booleani. Possiamo verificare facilmente questi postulati, sostituendo la variabile booleana con "0" o "1".
Note- Il complemento del complemento di qualsiasi variabile booleana è uguale alla variabile stessa. cioè, (x ')' = x.
Leggi fondamentali dell'algebra booleana
Di seguito sono riportate le tre leggi fondamentali dell'algebra booleana.
- Diritto commutativo
- Diritto associativo
- Legge distributiva
Diritto commutativo
Se una qualsiasi operazione logica di due variabili booleane dà lo stesso risultato indipendentemente dall'ordine di queste due variabili, allora si dice che l'operazione logica sia Commutative. Le operazioni OR logico e AND logico di due variabili booleane x e y sono mostrate di seguito
x + y = y + x
xy = yx
Il simbolo "+" indica l'operazione logica OR. Allo stesso modo, il simbolo "." indica un'operazione AND logica ed è facoltativa rappresentare. La legge commutativa obbedisce alle operazioni OR logico e AND logico.
Diritto associativo
Se viene eseguita prima un'operazione logica di due variabili booleane e poi la stessa operazione viene eseguita con la variabile rimanente dà lo stesso risultato, allora si dice che l'operazione logica sia Associative. Le operazioni OR logico e AND logico di tre variabili booleane x, y & z sono mostrate di seguito.
x + (y + z) = (x + y) + z
x. (yz) = (xy) .z
Il diritto associativo obbedisce alle operazioni OR logico e AND logico.
Legge distributiva
Se qualsiasi operazione logica può essere distribuita a tutti i termini presenti nella funzione booleana, allora si dice che l'operazione logica sia Distributive. La distribuzione delle operazioni OR logico e AND logico di tre variabili booleane x, y & z è mostrata di seguito.
x. (y + z) = xy + xz
x + (yz) = (x + y). (x + z)
La legge distributiva obbedisce alle operazioni OR logico e AND logico.
Queste sono le leggi fondamentali dell'algebra booleana. Possiamo verificare facilmente queste leggi, sostituendo le variabili booleane con "0" o "1".
Teoremi dell'algebra booleana
I seguenti due teoremi sono usati in algebra booleana.
- Teorema di dualità
- Teorema di DeMorgan
Teorema di dualità
Questo teorema afferma che il dualdella funzione booleana si ottiene scambiando l'operatore AND logico con l'operatore OR logico e gli zeri con uno. Per ogni funzione booleana, ci sarà una funzione Dual corrispondente.
Facciamo le equazioni (relazioni) booleane che abbiamo discusso nella sezione dei postulati booleani e delle leggi fondamentali in due gruppi. La tabella seguente mostra questi due gruppi.
| Gruppo 1 | Group2 |
|---|---|
| x + 0 = x | x.1 = x |
| x + 1 = 1 | x.0 = 0 |
| x + x = x | xx = x |
| x + x '= 1 | x.x '= 0 |
| x + y = y + x | xy = yx |
| x + (y + z) = (x + y) + z | x. (yz) = (xy) .z |
| x. (y + z) = xy + xz | x + (yz) = (x + y). (x + z) |
In ogni riga ci sono due equazioni booleane e sono duali tra loro. Possiamo verificare tutte queste equazioni booleane di Gruppo1 e Gruppo2 utilizzando il teorema di dualità.
Teorema di DeMorgan
Questo teorema è utile per trovare il complement of Boolean function. Afferma che il complemento dell'OR logico di almeno due variabili booleane è uguale all'AND logico di ciascuna variabile completata.
Il teorema di DeMorgan con 2 variabili booleane x e y può essere rappresentato come
(x + y) '= x'.y'
Il duale della funzione booleana di cui sopra è
(xy) '= x' + y '
Pertanto, il complemento dell'AND logico di due variabili booleane è uguale all'OR logico di ciascuna variabile completata. Allo stesso modo, possiamo applicare il teorema di DeMorgan anche per più di 2 variabili booleane.
Semplificazione delle funzioni booleane
Finora abbiamo discusso i postulati, le leggi fondamentali ei teoremi dell'algebra booleana. Ora, semplifichiamo alcune funzioni booleane.
Esempio 1
Lasciateci simplify la funzione booleana, f = p'qr + pq'r + pqr '+ pqr
Possiamo semplificare questa funzione in due metodi.
Method 1
Data la funzione booleana, f = p'qr + pq'r + pqr '+ pqr.
Step 1- In primo e secondo termine r è comune e in terzo e quarto termine pq è comune. Quindi, prendi i termini comuni usandoDistributive law.
⇒ f = (p'q + pq ') r + pq (r' + r)
Step 2- I termini presenti nella prima parentesi possono essere semplificati al funzionamento Ex-OR. I termini presenti nella seconda parentesi possono essere semplificati in "1" utilizzandoBoolean postulate
⇒ f = (p ⊕q) r + pq (1)
Step 3- Il primo termine non può essere ulteriormente semplificato. Ma il secondo termine può essere semplificato in pq usandoBoolean postulate.
⇒ f = (p ⊕q) r + pq
Pertanto, la funzione booleana semplificata è f = (p⊕q)r + pq
Method 2
Data la funzione booleana, f = p'qr + pq'r + pqr '+ pqr.
Step 1 - Usa il file Boolean postulate, x + x = x. Ciò significa che l'operazione OR logico con qualsiasi variabile booleana 'n' volte sarà uguale alla stessa variabile. Quindi, possiamo scrivere l'ultimo termine pqr altre due volte.
⇒ f = p'qr + pq'r + pqr '+ pqr + pqr + pqr
Step 2 - Usa Distributive lawper 1 ° e 4 th termini, 2 ° e 5 th termini, 3 ° e 6 th termini.
⇒ f = qr (p '+ p) + pr (q' + q) + pq (r '+ r)
Step 3 - Usa Boolean postulate, x + x '= 1 per semplificare i termini presenti in ciascuna parentesi.
⇒ f = qr (1) + pr (1) + pq (1)
Step 4 - Usa Boolean postulate, x.1 = x per semplificare i tre termini precedenti.
⇒ f = qr + pr + pq
⇒ f = pq + qr + pr
Pertanto, la funzione booleana semplificata è f = pq + qr + pr.
Quindi, abbiamo ottenuto due diverse funzioni booleane dopo aver semplificato la funzione booleana data in ciascun metodo. Funzionalmente, queste due funzioni booleane sono le stesse. Quindi, in base al requisito, possiamo scegliere una di queste due funzioni booleane.
Esempio 2
Cerchiamo di trovare il file complement della funzione booleana, f = p'q + pq '.
Il complemento della funzione booleana è f '= (p'q + pq') '.
Step 1 - Usa il teorema di DeMorgan, (x + y) '= x'.y'.
⇒ f '= (p'q)'. (Pq ')'
Step 2 - Usa il teorema di DeMorgan, (xy) '= x' + y '
⇒ f '= {(p') '+ q'}. {P '+ (q') '}
Step3 - Usa il postulato booleano, (x ')' = x.
⇒ f '= {p + q'}. {P '+ q}
⇒ f '= pp' + pq + p'q '+ qq'
Step 4 - Usa il postulato booleano, xx '= 0.
⇒ f = 0 + pq + p'q '+ 0
⇒ f = pq + p'q '
quindi, il complement della funzione booleana, p'q + pq 'è pq + p’q’.