Semplificazione delle funzioni booleane
Semplificazione mediante funzioni algebriche
In questo approccio, un'espressione booleana viene ridotta a icona in un'espressione equivalente applicando identità booleane.
Problema 1
Ridurre a icona la seguente espressione booleana utilizzando identità booleane:
$$ F (A, B, C) = A'B + BC '+ BC + AB'C' $$
Soluzione
Dato, $ F (A, B, C) = A'B + BC '+ BC + AB'C' $
Oppure, $ F (A, B, C) = A'B + (BC '+ BC') + BC + AB'C '$
[Per legge idempotente, BC '= BC' + BC ']
Oppure, $ F (A, B, C) = A'B + (BC '+ BC) + (BC' + AB'C ') $
Oppure, $ F (A, B, C) = A'B + B (C '+ C) + C' (B + AB ') $
[Per leggi distributive]
Oppure $ F (A, B, C) = A'B + B.1 + C '(B + A) $
[(C '+ C) = 1 e legge di assorbimento (B + AB') = (B + A)]
Oppure $ F (A, B, C) = A'B + B + C '(B + A) $
[B.1 = B]
Oppure, $ F (A, B, C) = B (A '+ 1) + C' (B + A) $
Oppure $ F (A, B, C) = B.1 + C '(B + A) $
[(A '+ 1) = 1]
Oppure $ F (A, B, C) = B + C '(B + A) $
[As, B.1 = B]
Oppure $ F (A, B, C) = B + BC '+ AC' $
Oppure $ F (A, B, C) = B (1 + C ') + AC' $
Oppure $ F (A, B, C) = B.1 + AC '$
[As, (1 + C ') = 1]
Oppure $ F (A, B, C) = B + AC '$
[As, B.1 = B]
Quindi, $ F (A, B, C) = B + AC '$ è la forma minimizzata.
Problema 2
Ridurre a icona la seguente espressione booleana utilizzando identità booleane:
$$ F (A, B, C) = (A + B) (A + C) $$
Soluzione
Dato, $ F (A, B, C) = (A + B) (A + C) $
Oppure, $ F (A, B, C) = AA + AC + BA + BC $ [Applicazione della regola distributiva]
Oppure, $ F (A, B, C) = A + AC + BA + BC $ [Applicazione della legge idempotente]
Oppure, $ F (A, B, C) = A (1 + C) + BA + BC $ [Applicazione del diritto distributivo]
Oppure $ F (A, B, C) = A + BA + BC $ [Applicazione della legge sulla dominanza]
Oppure $ F (A, B, C) = (A + 1) .A + BC $ [Applicazione del diritto distributivo]
Oppure, $ F (A, B, C) = 1.A + BC $ [Applicazione della legge sulla dominanza]
Oppure $ F (A, B, C) = A + BC $ [Applicazione della legge di dominanza]
Quindi, $ F (A, B, C) = A + BC $ è la forma minimizzata.
Mappe di Karnaugh
La mappa di Karnaugh (K – map), introdotta da Maurice Karnaughin nel 1953, è una rappresentazione a griglia di una tabella di verità che viene utilizzata per semplificare le espressioni algebriche booleane. Una mappa di Karnaugh ha zero e una voce in posizioni diverse. Fornisce il raggruppamento di espressioni booleane con fattori comuni ed elimina le variabili indesiderate dall'espressione. In una K-map, attraversare un confine di cella verticale o orizzontale è sempre un cambiamento di una sola variabile.
Esempio 1
Di seguito è riportata una tabella di verità arbitraria:
| UN | B | Un'operazione B |
|---|---|---|
| 0 | 0 | w |
| 0 | 1 | X |
| 1 | 0 | y |
| 1 | 1 | z |
Ora creeremo una k-map per la tabella di verità sopra -
Esempio 2
Ora creeremo una mappa K per l'espressione - AB + A'B '
Semplificazione utilizzando K-map
K-map utilizza alcune regole per la semplificazione delle espressioni booleane combinando insieme celle adiacenti in un unico termine. Le regole sono descritte di seguito:
Rule 1 - Qualsiasi cella contenente uno zero non può essere raggruppata.
Raggruppamento sbagliato
Rule 2 - I gruppi devono contenere 2n celle (n a partire da 1).
Raggruppamento sbagliato
Rule 3 - Il raggruppamento deve essere orizzontale o verticale, ma non diagonale.
Raggruppamento diagonale errato
Raggruppamento verticale corretto
Raggruppamento orizzontale corretto
Rule 4 - I gruppi devono essere coperti il più ampiamente possibile.
Raggruppamento insufficiente
Raggruppamento corretto
Rule 5 - Se 1 di qualsiasi cella non può essere raggruppata con nessun'altra cella, agirà come un gruppo stesso.
Raggruppamento corretto
Rule 6 - I gruppi possono sovrapporsi, ma dovrebbero esserci meno gruppi possibile.
Raggruppamento corretto
Rule 7 - La cella / le celle più a sinistra possono essere raggruppate con la / le celle più a destra e la / le celle più in alto possono essere raggruppate con la / le celle più in basso.
Raggruppamento corretto
Problema
Riduci a icona la seguente espressione booleana utilizzando K-map -
$$ F (A, B, C) = A'BC + A'BC '+ AB'C' + AB'C $$
Soluzione
Ogni termine viene inserito in k-map e otteniamo quanto segue:
Mappa K per F (A, B, C)
Ora raggrupperemo le celle di 1 secondo le regole sopra indicate -
Mappa K per F (A, B, C)
Abbiamo due gruppi denominati $ A'B $ e $ AB '$. Quindi, $ F (A, B, C) = A'B + AB '= A \ oplus B $. È la forma minimizzata.