Implicanti e Implicanti Primi di una Funzione Booleana

Nella lezione precedente abbiamo studiato il metodo di minimizzazione delle funzioni booleane attraverso l'uso delle mappe di Karnaugh. Questa tecnica grafica funziona se abbiamo a che fare con un numero relativamente ridotto di variabili, tipicamente fino a 4 o 5. Quando il numero di variabili aumenta, diventa più complesso applicare questa tecnica e si rende necessario ricorrere ad altri metodi come, ad esempio, il metodo di Quine-McCluskey.

Per capire come funzionano tali metodi, però, bisogna prima introdurre alcuni concetti fondamentali relativi alle funzioni booleane: gli implicanti e gli implicanti primi.

Concetti Chiave

Un implicante di una funzione booleana è un termine che implica la funzione stessa.
Un implicante primo è un implicante che non è implicato da nessun altro implicante.
Gli implicanti primi sono importanti perché una funzione booleana può essere espressa come somma dei suoi implicanti primi.
Tra gli implicanti primi, alcuni sono implicanti essenziali, ossia implicanti che coprono mintermini non coperti da nessun altro implicante.
Il nucleo di una funzione booleana è la somma degli implicanti essenziali.

Implicanti di una Funzione booleana

Una importante proprietà riguardante le funzioni booleane è l'implicazione.

Per comprendere come funziona, consideriamo due funzioni booleane, $f$ e $g$ , funzioni delle stesse variabili. Si dice che $f$ implica $g$ (e si scrive $f \Rightarrow g$ ) se ogni volta che $f$ è vera, anche $g$ è vera quando applicate agli stessi valori di input.

Ad esempio, se $f$ e $g$ sono due funzioni booleane definite come segue:

$f(x, y) = x \cdot y$
$g(x, y) = x + y$

Allora possiamo osservare che $f \Rightarrow g$ è vero, poiché ogni volta che $f(x, y)$ è vera (cioè quando sia $x$ che $y$ sono veri), anche $g(x, y)$ è vera (cioè quando $x$ è vero). Ovviamente, non vale il contrario: se $g(x, y)$ è vera, non possiamo concludere che $f(x, y)$ è vera. Così come non possiamo concludere che se $f(x, y)$ è falsa, anche $g(x, y)$ è falsa.

L'implicazione, da un punto di vista algebrico, risulta falsa solo se $f$ è vera e $g$ è falsa. Quindi possiamo scrivere:

\overline{f \Rightarrow g} = f \cdot \overline{g}

Applicando il teorema di De Morgan, possiamo riscrivere l'espressione come segue:

f \Rightarrow g = \overline{f} + g = 1

Ossia, l'implicazione è uguale alla funzione negata $\overline{f}$ sommata a $g$ .

Quando ciò si verifica allora si dice che la funzione $f$ è un implicante della funzione $g$ .

Definizione

Implicante di una funzione

Date due funzioni booleane $f$ e $g$ definite sulle stesse variabili, la funzione $f$ è un Implicante della funzione $g$ se $f \Rightarrow g$ è vero, ossia se vale:

\overline{f} + g = 1

In generale, data una funzione $g$ booleana qualunque, esistono molte funzioni $f$ che sono implicanti di $g$ . L'insieme delle funzioni implicanti di $g$ è detto insieme degli implicanti di $g$ e viene indicato con $I(g)$ .

In generale, nell'ambito della progettazione delle reti logiche e della minimizzazione delle funzioni booleane, non ci interessano tutti i possibili implicanti di una funzione generica. Ciò che ci interessa sono gli implicanti di una funzione in forma canonica o in forma standard

Se, infatti, consideriamo una funzione $g$ in prima forma canonica, ossia come somma di termini:

g = \sum_{i=1}^{n} A_i

dove $A_i$ sono le clausole della funzione, esse sono tutte implicanti di $g$ :

\forall i \in [1, n]: A_i \Rightarrow g

Ciò è facile da dimostrare, infatti scegliamo una clausola $A_k$ qualunque

\overline{A_k} + g

= \overline{A_k} + (A_1 + A_2 + \ldots + A_k + \ldots + A_n)

= (\overline{A_k} + A_k) + (A_1 + A_2 + \ldots + A_{k-1} + A_{k+1} + \ldots + A_n)

Ma la somma $\overline{A_k} + A_k$ è sempre vera, ossia sempre pari a 1, quindi:

= 1 + (A_1 + A_2 + \ldots + A_{k-1} + A_{k+1} + \ldots + A_n)

= 1

Quindi, ricapitolando:

Definizione

Clausole di una funzione booleana in forma Somma di Prodotti

Data una funzione booleana $g$ in forma Somma di Prodotti, i suoi termini o clausole sono tutte implicanti di $g$ :

g = \sum_{i=1}^{n} A_i

\forall i \in [1, n]: A_i \Rightarrow g

Proprio per la loro importanza, da adesso in poi considereremo con $I(g)$ l'insieme delle clausole implicanti di $g$ .

Proprietà delle Clausole Implicanti

Le clausole, in quanto implicanti di una funzione in forma canonica o standard, hanno delle importanti proprietà:

Una clausola $B$ ne implica un'altra $A$ se e solo se $B$ contiene tutti i letterali di $A$ .

Da un punto di vista insiemistico possiamo scrivere:

$B \subseteq A$

In tal caso, possiamo vedere $B$ come l'intersezione di $A$ con un altro insieme $C$ dell'algebra:

$B = A \cap C$

Che, in termini algebrici, possiamo scrivere:

$B = A \cdot C$

ossia $B$ è uguale ad $A$ per qualche altro letterale.

Ad esempio, se $A = x \cdot y$ e $B = x \cdot y \cdot z'$ , allora possiamo scrivere:

$B = A \cdot z'$

e $B \Rightarrow A$ .
Date due clausole $A$ e $B$ di ordine $n$ (ossia che contengono $n$ letterali), se $A$ e $B$ hanno gli stessi $n-1$ letterali e l'ultimo letterale è presente in $A$ ma è complementato in $B$ allora la somma di $A$ e $B$ è uguale alla clausola contenente solo i primi $n-1$ letterali.

In altre parole, supponiamo di avere due clausole:

$A = C \cdot x$

$B = C \cdot x'$

Ossia, le due clausole sono composte dal prodotto di $C$ con un letterale e il suo complementare.

Se consideriamo la somma delle due clausole:

$A + B = C \cdot x + C \cdot x' = C \cdot (x + x') = C \cdot 1 = C$

Allora la clausola $C$ prende il nome di consenso delle due clausole $A$ e $B$ che si oppongono nella variabile $x$ .

Ad esempio, se consideriamo la somma di termini:

$xy'z + xyz$

I due termini o clausole si oppongono nella variabile $y$ .

Per cui, considerando la somma delle due clausole, otteniamo:

$xy'z + xyz = xz(y' + y) = xz \cdot 1 = xz$

Quindi, la clausola $C = xz$ è il consenso delle due clausole $A$ e $B$ .
Ad una funzione può essere sommato un suo implicante senza modificarne il valore.

Infatti, se consideriamo una funzione $g$ e un suo implicante $A$ , possiamo scrivere:

$g = g + A$

Questo è possibile perché $A$ è già contenuto in $g$ , quindi la somma non modifica il valore di $g$ .

Ad esempio, consideriamo la funzione:

$f(x, y, z) = xy + x'z$

Un implicante di questa funzione è:

$A = xyz$

Se sommiamo $A$ a $f$ , otteniamo:

$f = f + A$

$f = xy + x'z + xyz$

Il valore di $f$ non è cambiato, poiché abbiamo sommato un implicante di $f$ . Per convincersene basta tracciare le tabelle di verità della funzione $f$ nelle due forme e verificare che sono identiche.
$A$ è una clausola implicante di una funzione booleana $f$ in prima forma canonica se e solo se in $f$ compaiono tutti i mintermini che hanno come fattore $A$ .

Prendiamo un esempio. Consideriamo la funzione in prima forma canonica che segue:

$f(x, y, z) = x'y'z + x'yz + xyz' + xyz$

Questa funzione è in prima forma canonica come somma di mintermini.

Se consideriamo la clausola $A = x'z$ abbiamo che:

$A \Rightarrow f$

In quanto $A$ è fattor comune dei mintermini $x'y'z$ e $x'yz$ .

Implicanti Primi

Tra i vari implicanti di una funzione booleana, rivestono un'importanza fondamentale i implicanti primi o implicanti principali:

Definizione

Implicanti Primi

Data una funzione booleana $g$ , un implicante $A$ dell'insieme $I(g)$ è detto implicante primo se non esiste un altro implicante $B$ di $g$ tale che $A \Rightarrow B$ :

\nexists B \in I(g) : A \Rightarrow B

L'importanza degli implicanti primi sta nel fatto che una qualunque funzione booleana $f$ può essere scritta come somma dei soli suoi implicanti primi.

La dimostrazione di questa affermazione è molto semplice. Infatti supponiamo di avere una funzione $f$ in forma standard come somma di prodotti, ossia somme di clausole:

f = \sum_i A_i

Supponiamo che uno dei termini, ad esempio $A_k$ non sia un implicante primo. Pertanto deve esistere un implicante primo $A_j$ tale che:

A_k \Rightarrow A_j \Rightarrow f

Dalle proprietà delle clausole sappiamo che possiamo aggiungere una clausola ad una funzione senza alterarne il valore, per cui possiamo aggiungere $A_j$ ad $f$ senza modificarne il risultato:

f = \sum_i A_i + A_j

Ma poiché sappiamo che:

A_j + A_k = A_j

L'implicante non primo $A_j$ può essere eliminato dalla sommatoria. Se procediamo così per tutte le clausole non implicanti prime di $f$ , quello che si ottiene è una somma di implicanti primi.

Si può dimostrare facilmente che:

Definizione

Una funzione booleana espressa come somma di implicanti primi è in forma minima

Una funzione espressa come somma di implicanti primi minimizza:

Il numero di letterali presenti;
Il numero di ingressi.

Inoltre, tra le forme minime a 2 livelli che minimizzano il numero di porte logiche ne esiste almeno una in forma di somma di implicanti primi.

Ragioniamo su quest'ultima definizione. Infatti, se consideriamo una funzione booleana $f$ e supponiamo di prendere, tra tutte le possibili forme standard, quella minima. Se quest'ultima forma viene trasformata in una forma somma di implicanti primi, nella quale una clausola $A_j$ sostituisce $A_k$ , poiché $A_j$ è una clausola di ordine inferiore rispetto a $A_k$ , la nuova forma richiederà meno ingressi e richiederà meno letterali mentre il numero di porte non aumenterà.

Quindi, tra le forme minime di una funzione si può trovare sempre una forma che sia una somma di implicanti primi.

Non vale, però, il contrario: non è detto che una forma di somma di implicanti primi sia necessariamente minima.

Implicanti Essenziali e Nucleo di una funzione booleana

Per capire quest'ultimo punto, dobbiamo introdurre due concetti fondamentali:

Definizione

Implicante Primo Essenziale

Data una funzione booleana $f$ , un suo implicante primo $A$ è detto implicante essenziale se è l'unico ad essere implicato da un mintermine di $f$ .

Un implicante essenziale si indica con il simbolo $\epsilon_i$

Per chiarire cos'è un implicante essenziale ci conviene ricorrere ad un esempio. Consideriamo la funzione booleana a quattro variabili rappresentata nella seguente mappa di Karnaugh:

**Figura 1:** Esempio di funzione booleana: mappa di Karnaugh

In questa funzione, abbiamo due implicanti essenziali. Il primo è mostrato di seguito ed è essenziale perché è l'unico che copre il mintermine (quindi è implicato dal mintermine) $w'x'y'z$ :

w'x'y'z \Rightarrow y'z

**Figura 2:** Primo implicante essenziale della funzione di esempio

Il secondo è mostrato di seguito ed è un implicante essenziale in quanto è l'unico a coprire il mintermine $wx'yz$ :

wx'yz \Rightarrow wz

**Figura 3:** Secondo implicante essenziale della funzione di esempio

Gli altri implicanti individuabili sulla mappa non sono essenziali perché gli uni che coprono sono coperti anche da altri implicanti:

**Figura 4:** Implicanti della funzione di Esempio

Come si può notare, solo l'implicante primo rosso, il primo, e quello verde, il secondo, sono essenziali perché coprono degli 1 non coperti da nessun altro. (Si ricordi che la copertura di un mintermine può avvenire tramite più implicanti primi e che la copertura significa che quel mintermine implica l'implicante primo).

A partire dagli implicanti primi possiamo definire un secondo concetto:

Definizione

Nucleo di una funzione booleana

Data una funzione booleana $f$ , dicesi Nucleo di una funzione booleana la somma degli implicanti essenziali di $f$ :

N(f) = \sum \epsilon_i

Ritornando all'esempio della funzione di sopra, il suo nucleo sarà composto dai due implicanti essenziali che abbiamo individuato sulla mappa di Karnaugh:

N(f) = y'z + wz

Si può facilmente dimostrare che una qualunque funzione booleana può essere riscritta come:

f = N(f) + R(f)

Dove $N(f)$ è il nucleo della funzione e $R(f)$ è il resto della funzione, ovvero la somma degli implicanti non essenziali. $R(f)$ può essere eventualmente nullo ma non è detto che lo sia.

In generale vale che:

Definizione

Ogni funzione espressa come somma di implicanti primi contiene tutti gli implicanti essenziali

Se $f$ è una funzione booleana ed è espressa nella forma di somma di implicanti primi essa deve contenere necessariamente il suo nucleo $N(f)$ .

La dimostrazione di questa affermazione è molto semplice.

Infatti, supponiamo di avere una funzione booleana $f$ e che $\epsilon_i$ sia un suo implicante essenziale.

Dato che $\epsilon_i$ è essenziale, deve coprire almeno un mintermine che non è coperto da nessun altro implicante. Supponiamo che tale mintermine sia $m_i$ , deve valere quindi:

m_i \Rightarrow \epsilon_i \Rightarrow f

Ciò implica che se $m_i = 1$ non deve derivare nessun $\epsilon_j = 1$ per $j \neq i$ .

Ma se $f$ espressa come somma di implicanti primi non contenesse $\epsilon_i$ , allora non varrebbe che $f = 1$ .

Da queste considerazioni nasce il metodo di Quine-McCluskey che vedremo nelle prossime lezioni.

In generale, però, tutte le tecniche di minimizzazione di una funzione booleana lavorano in questo modo:

Si ricercano tutti gli implicanti primi della funzione;
Si individuano gli implicanti essenziali tra gli implicanti primi, in altre parole si individua il nucleo $N(f)$ della funzione;
Si determina la forma minima componendo $R(f)$ , ossia si aggiungono gli implicanti primi non essenziali.

Implicanti Primi e Mappe di Karnaugh

Nella lezione precedente abbiamo visto come minimizzare funzioni di 2, 3 e 4 variabili adoperando il metodo grafico delle mappe di Karnaugh.

Nel farlo ci siamo limitati a coprire tutti gli 1 della mappa con i sotto-cubi, ossia quei raggruppamenti di 2, 4, 8 o 16 celle contigue. Non abbiamo fatto cenno agli implicanti primi, agli implicanti essenziali e alla copertura in quanto abbiamo usato un approccio più intuitivo per risolvere il problema della minimizzazione.

Adesso che abbiamo chiari i concetti di nucleo, implicanti essenziali e copertura, ci chiediamo come essi siano collegati al metodo delle mappe.

Quindi, rivediamo un attimo tali concetti in ottica delle mappe di Karnaugh.

Nella scelta di quadrati adiacenti in una mappa, dobbiamo assicurarci che:

tutti i mintermini della funzione siano coperti quando combiniamo i quadrati;
il numero di termini nell'espressione sia minimizzato;
non ci siano termini ridondanti (cioè, mintermini già coperti da altri termini).

A volte ci possono essere due o più espressioni che soddisfano i criteri di semplificazione. La procedura per combinare i quadrati nella mappa può essere resa più sistematica se comprendiamo il significato di due tipi speciali di termini. Abbiamo visto che un termine prodotto è un implicante della funzione a cui appartiene. Un implicante primo è un termine prodotto ottenuto combinando il massimo numero possibile di quadrati adiacenti nella mappa.

Quindi, un implicante è primo se nessun altro implicante con meno letterali lo copre. Se un mintermine in un quadrato è coperto da un solo implicante primo, quell'implicante primo si dice essere essenziale, cioè, non può essere rimosso da una descrizione della funzione.

Gli implicanti primi di una funzione possono essere ottenuti dalla mappa combinando tutti i possibili numeri massimi di quadrati. Questo significa che un singolo 1 su una mappa di Karnaugh rappresenta un implicante primo se non è adiacente a nessun altro 1. Due 1 adiacenti formano un implicante primo, purché non siano all'interno di un gruppo di quattro quadrati adiacenti. Quattro 1 adiacenti formano un implicante primo se non sono all'interno di un gruppo di otto quadrati adiacenti, e così via. Gli implicanti primi essenziali sono trovati guardando ogni quadrato marcato con un 1 e controllando il numero di implicanti primi che lo coprono. Un implicante primo è essenziale se è l'unico implicante primo che copre il mintermine.

Consideriamo la seguente funzione booleana a quattro variabili:

F(A, B, C, D) = \Sigma(0, 2, 3, 5, 7, 8, 9, 10, 11, 13, 15)

Alcuni dei mintermini della funzione sono marcati con 1 nelle mappe della figura che segue, in cui, inoltre, abbiamo omesso $m_3$ , $m_9$ e $m_{11}$ .

**Figura 5:** Nucleo della funzione di Esempio

Tale mappa parziale mostra i due implicanti primi essenziali ossia il nucleo della funzione, ognuno formato collassando quattro celle in un termine avente solo due letterali. Un termine è essenziale perché c'è solo un modo per includere il mintermine $m_0$ all'interno di quattro quadrati adiacenti. Questi quattro quadrati definiscono il termine $B'D'$ . Similmente, c'è solo un modo in cui il mintermine $m_5$ può essere combinato con quattro quadrati adiacenti, e questo dà il secondo termine $BD$ . I due implicanti primi essenziali coprono otto mintermini. I tre mintermini che sono stati omessi dalla mappa parziale ( $m_3$ , $m_9$ e $m_{11}$ ) devono essere considerati successivamente.

Quindi, il nucleo della funzione è:

N(F) = BD + B'D'

La figura che segue mostra tutti i modi possibili in cui i tre mintermini possono essere coperti con implicanti primi:

**Figura 6:** Implicanti Primi Non Essenziali della Funzione di Esempio

Il mintermine $m_3$ può essere coperto con l'implicante primo $CD$ o l'implicante primo $B'C$ . Il mintermine $m_9$ può essere coperto con $AD$ o $AB'$ . Il mintermine $m_{11}$ è coperto con uno qualsiasi dei quattro implicanti primi. L'espressione semplificata è ottenuta dalla somma logica dei due implicanti primi essenziali e qualsiasi due implicanti primi che coprono i mintermini $m_3$ , $m_9$ , e $m_{11}$ . Ci sono quattro modi possibili in cui la funzione può essere espressa con quattro termini prodotto di due letterali ciascuno:

F = BD + B'D' + CD + AD

= BD + B'D' + CD + AB'

= BD + B'D' + B'C + AD

= BD + B'D' + B'C + AB'

Di conseguenza, la componente $R(F)$ della funzione può avere, in questo caso, quattro forme possibili mentre il nucleo è sempre unico:

R_1(F) = CD + AD

R_2(F) = CD + AB'

R_3(F) = B'C + AD

R_4(F) = B'C + AB'

L'esempio precedente ha dimostrato che l'identificazione degli implicanti primi nella mappa aiuta nel determinare le alternative che sono disponibili per ottenere un'espressione semplificata.

La procedura per trovare l'espressione semplificata dalla mappa richiede che determiniamo prima tutti gli implicanti primi essenziali, ossia il nucleo. L'espressione semplificata è ottenuta dalla somma logica di tutti gli implicanti primi essenziali, più altri implicanti primi che possono essere necessari per coprire qualsiasi mintermine rimanente non coperto dagli implicanti primi essenziali. Occasionalmente, ci può essere più di un modo di combinare i quadrati, e ogni combinazione può produrre un'espressione ugualmente semplificata.