Definizione di algebra di Boole

Definizione di algebra di Boole

Si dice che un insieme K è munito della struttura di algebra, o che esso è organizzato in algebra o che esso costituisce un 'algebra (astratta), se in esso sono ovunque definite due leggi binarie di composizione interna o, in altri termini, due funzioni che facciano corrispondere ad una qualsiasi coppia di elementi di K ancora un elemento di K.

Le due leggi vengono anche dette funzioni fondamentali dell'algebra.

Indicheremo le due leggi binarie con i simboli '+'e ' ' e con i nomi, rispettivamente, di OR (+) e AND (

Indicheremo l'algebra con la tripla <K,+, >

L'insieme K si dice anche insieme di 'sostegno' dell'algebra.

L'algebra di Boole è una particolare algebra

Poiché vale la proprietà associativa, le funzioni AND e OR possono anche essere definite su più variabili

(a+b)+c = a+(b+c) = a+b+c                 (a∙b)∙c = a∙(b∙c) =a∙b∙c

Proprietà fondamentale di un reticolo è che l'insieme K che lo sostiene è ordinato, ossia in esso esiste una relazione d'ordine.

Per relazione d'ordine x≤y si intende una relazione che goda delle proprietà:

riflessiva: x ≤ x ;

antisimmetrica: x ≤ y e y ≤ x x = y ;

transitiva: x ≤ y e y ≤ z x ≤ z.

La relazione x+y=y è una relazione d'ordine in quanto gode delle tre proprietà sopra richiamate. Essa è infatti:

riflessiva per la P₃ : x+x=x;

antisimmetrica in quanto da x+y=y (x≤y) e y+x=x (y ≤ x) scaturisce x=y;

transitiva in quanto da x+y=y (x≤y) e y+z=z (y≤z) scaturisce x+z=z, cioè x≤z, come si può verificare sommando membro a membro, applicando la P₃ e sostituendo z ad y + z.

L'operazione unaria che, applicata all'elemento a, genera l'elemento dicesi 'complementazione'.

Un'algebra di Boole è dunque la sestupla <K,+,∙,, 0, 1 > dove:

K è l'insieme di sostegno,

0 e 1 sono i due elementi minimo e massimo,

+ è l'operazione in genere detta di 'somma' o OR,

∙ è il 'prodotto' o AND;

è la 'complementazione' o NOT.

Una volta che si sia individuato un insieme K e siano definite in esso le tre operazioni di cui sopra in modo che rispettino i 14 postulati elencati (da P₁ a P'₇), si ottiene un modello di algebra di Boole

Legge di dualità

Variabili e funzioni booleane

Si dice valore booleano uno qualsiasi degli elementi dell'insieme K, sostegno dell'algebra,

Si dice variabile booleana una variabile che può assumere un valore booleano;

Si dice letterale di una variabile a la variabile stessa o il suo complemento .

Si dice che y è funzione booleana delle n variabili x_l, x₂,.,.,x_n

y = f (x₁, x₂,,x_n)   

se esiste una corrispondenza per cui ad ogni n-pla di valori delle variabili indipendenti x₁, x₂,,x_n è associato un valore booleano di quella dipendente y.

Le funzioni AND, OR, NOT, impiegate per definire l'algebra, sono dette anche funzioni fondamentali dell'algebra o funzioni logiche elementari

AND: y = x₁∙x₂∙∙x_n

OR :   y = x₁+x₂++x_n

NOT : y =

Una funzione può essere rappresentata graficamente dallo schema:

Dato un insieme di funzioni

F =

una funzione può talora essere espressa come 'funzione delle funzioni F':

y = f_y(y₁, y₂, , y_n) con f_y I F       

dove ciascuna delle y_i è una delle variabili indipendenti oppure a sua volta è espressa in una forma analoga:

y_i = f_i(y_1i, y_2i, , y_n) con f_i I F

e così via, secondo lo schema grafico:        

Ciò non è possibile per qualsiasi funzione y e per qualsiasi insieme F.

Se, dato un insieme F, tutte le funzioni dell'algebra sono esprimibili in funzione delle funzioni di F, F si dice funzionalmente completo.

Lo schema di figura suggerisce la definizione di livello di una variabile.

Al fine della definizione di cui sopra, talora si considerano indipendenti tutti i letterali delle variabili indipendenti vere e proprie; in altri termini, si considera che la complementazione di una variabile indipendente non costituisca un livello.

Esempio

Esempio di funzione a 4 livelli

Torna inoltre utile la definizione di 'livello complementare'.

Con riferimento alla figura, si ha ad esempio che P₁ e P₂ sono di livello complementare 1, in quanto variabili della y; b, c (come variabili di P₁) e S₁ sono di livello complementare 2; b e c (come variabili di S₃) sono di livello complementare 3 e così via.

Ai fini della trasformazione da una forma algebrica ad un'altra, risulta inoltre particolarmente utile la seguente definizione:

In altri termini, la forma duale è quella che sostituisca ad ogni operatore + il suo duale ∙ (e viceversa) ed, eventualmente, ad ogni elemento 1 il suo duale 0 (e viceversa).

Ovviamente, il duale della funzione AND è la funzione OR e viceversa.

Eguaglianze notevoli e teorema di De Morgan

Dai postulati dell' algebra si ricavano alcune eguaglianze notevoli

Complemento di 0 e di 1

Convoluzione

Elementi neutri di somma e prodotto

a+0=a        a∙1=a

Assorbimento del complemento

Teorema di De Morgan

Teorema di Shannon

ove è la funzione duale di f:

il complemento di una funzione è ottenuto sostituendo ad ogni variabile il suo complemento e scambiando ogni funzione componente con la sua duale

Principio dell'eliminazione

L'algebra degli insiemi

Dati due insiemi a e b appartenenti ad un insieme T, si definiscono gli operatori di:

unione di a con b () che produce l'insieme degli elementi appartenenti almeno ad uno dei due insiemi a e b;

intersezione di a e b (₎che produce l'insieme degli elementi comuni ad a e b.

complemento di a e si indica ~a, l'insieme costituito dagli elementi di T non appartenenti ad a.

Se gli elementi di a sono caratterizzati dal godere la proprietà A e quelli di b la proprietà B, gli elementi di godono di una delle due proprietà A oppure B o di entrambe mentre gli elementi di godono delle proprietà A e B. Gli elementi di ~a sono caratterizzati dal non godere la proprietà A.

Detto K l'insieme delle parti di T, ossia l'insieme i cui elementi sono tutti i possibili sottoinsiemi di T, l'insieme vuoto F e T stesso si dimostra che:

In quanto sono soddisfatte tutte le 14 relazioni che definiscono un'algebra di Boole.

Si ha dunque la corrispondenza di cui alla tabella che segue:

Spesso le operazioni sugli insiemi vengono indicate in grafici detti diagrammi di Venn; in essi l'insieme T (detto anche insieme 'universo') viene rappresentato da un rettangolo ed i sottoinsiemi da figure piane con contorno chiuso in esso contenute.

a) Insieme universo b) a, -a c) a b

d) a b               e) a b=F f) b a

La relazione d'ordine ≤, sempre presente in un'algebra di Boole, equivale alla relazione di inclusione fra insiemi; si ha infatti

b a b a = a

b a b a = b

F A T

per tutti gli elementi a,b,c,,,, di K.

L'importanza dell'algebra degli insiemi risiede nel teorema di Stone:

In altri termini, il modello degli insiemi (e per esso i diagrammi di Venn) può essere assunto come strumento per verificare o dimostrare proprietà di una qualsiasi algebra di Boole..

L'algebra della logica delle proposizioni

Sia K un insieme costituito dai soli elementi 0 ed 1 e si definiscano le seguenti operazioni:

Disgiunzione        Congiunzione

Negazione

Assunto il valore 1 rappresentativo del vero e il valore 0 del falso, nella logica delle proposizioni tali operazioni possono essere così espresse:

la disgiunzione (oppure, ) di due proposizioni è falsa (0) se e solo se entrambe le proposizioni sono false;

la congiunzione (e, ) di due proposizioni è vera (1) se e solo se entrambe le proposizioni sono vere;

la negazione (non, ) di una proposizione vera è falsa, quella di una falsa è vera.

È facile constatare che:

in quanto soddisfa i 14 postulati che caratterizzano un'algebra di Boole: in particolare, essa è detta algebra primordiale di Boole

Esempi

Dette p e q le due proposizioni

p = 'fra i punti A e B vi è un corto circuito',

q = 'il punto C è a massa',

la proposizione

y₁ = = 'fra i punti A e B vi è un corto circuito

oppure il punto C è a massa'

è vera sia che vi sia il corto circuito (p=1) ma il punto C non sia a massa (q=0), sia che il punto C sia a massa (q=1) ma non vi sia il corto (p=0), sia infine che le due proposizioni componenti siano vere entrambe.

Analogamente, la proposizione:

y₂ = = 'fra i punti A e B vi è un corto circuito

e il punto C è a massa'

è vera solo se vi è il corto ed il punto C è a massa.

Infine, la proposizione:

y₃ = q = 'il punto C non è a massa'

è vera se il punto non è a massa, è falsa se lo è.

Equivalenza logica

Due variabili o funzioni dell'algebra sono uguali se e solo se assumono i medesimi valori di verità, cioè se sono entrambe vere oppure entrambe false. Nel qual caso si scrive:

a = b a b a b

e corrispondono tutti alla dizione 'a è vera se e solo se b è vera'. Se a e b sono uguali deve essere soddisfatta la relazione

f(a, b) =

relazione che è infatti vera per a = b = vero e per a = b = falso.

La funzione

f(a, b) = ab +

è detta pertanto funzione equivalenza

Implicazione logica

Una nozione importante in logica è quella di implicazione: si dice che 'x implica y' se dalla verità di x (detto antecedente) scaturisce necessariamente quella di y (detto conseguente); in termini algebrici, essendo l'implicazione falsa se e solo se x è vera ed y è falsa, applicando il teorema di De Morgan, si ha:

= x

x y = + y

Si dimostra che

e quindi se x implica y

x + y = y

Implicazione ed equivalenza

Dalle implicazioni x y e y x scaturisce l'equivalenza x y, come si deriva dal concetto di relazione d'ordine o anche algebricamente: essendo vere (cioè = 1) entrambe le implicazioni, si ha:

( + y) (x + ) = + xy = 1

e quindi x = y.

L'algebra dei circuiti

L' algebra dei circuiti è un'algebra di Boole in cui gli elementi dell'insieme sono i due valori del bit, per i quali si adoperano le dizioni equivalenti:

valore logico l, o segnale alto, o vero, o presente;

valore logico 0, o segnale basso o falso, o assente.

In detta algebra una variabile booleana è associata ad un punto di un circuito logico. Detto punto può essere un ingresso e quindi costituire una variabile indipendente oppure, l'uscita o un punto interno del circuito e quindi costituire una variabile dipendente

Un circuito logico è dunque in genere caratterizzato da n bit di 'ingresso' ed uno di 'uscita'[1], funzione dei primi:

y = f(x₁, x₂, , x_n)

Per realizzare un qualsiasi circuito logico è dunque necessario in primo luogo disporre di alcuni circuiti logici elementari - detti anche porte logiche (gates)- atti a realizzare le funzioni di un insieme F funzionalmente completo (ad esempio le porte AND, OR, NOT); la forma della funzione f suggerirà poi uno schema di connessione fra le porte atto a realizzare la funzione e quindi il circuito desiderato.

Un insieme di circuiti logici viene anche detto rete logica: in base agli schemi di connessione adoperati per la realizzazione delle funzioni, le reti logiche vengono dette 'unilaterali' e 'bilaterali

Reti unilaterali

  

La rete è detta unilaterale in quanto il flusso di elaborazione procede fisicamente in un 'unica direzione, dai segnali di ingresso verso quelli di uscita.

Nota la funzione booleana che esprime l'uscita e espressa la funzione come funzione di funzioni di un insieme funzionalmente completo, la forma della funzione determina la struttura della rete con impiego di blocchi funzionali che realizzano le funzioni dell'insieme funzionalmente completo.

Reti bilaterali

          

a) b) c)

d) e) f)

Nelle reti bilaterali, una variabile indipendente è costituita idealmente da un 'contatto' x fra i punti A e B (fig. 7.2a), che può essere 'aperto' (x = 0) oppure 'chiuso' (x = 1). Il contatto può essere invertito, ossia aperto se è x=1 () e chiuso per x=0 () per realizzare la funzione NOT.

Collegando più contatti in serie o in parallelo fra di loro si ottiene una rete logica costituita da un circuito che fra una qualsiasi coppia di suoi punti è aperto o chiuso, in dipendenza dello stato dei singoli contatti.

Ad una coppia (es. ai punti A e B) può essere associata una variabile booleana e costituire l'uscita' della rete.

f_AB = f(x₁, x₂,,x_n)

dove f_AB è detta funzione di trasmissione fra i punti A e B.

La rete è detta 'bilaterale' perché la sua funzione di uscita è valutata fra due punti.

I circuiti elementari AND o OR si ottengono semplicemente connettendo rispettivamente in serie o in parallelo due contatti

Esempi

       

a) b)

Forme elementari

Dicesi:

letterale di una variabile x è la variabile stessa o il suo complemento

termine elementare o clausola di ordine n un prodotto di n (≥ 1) letterali di variabili distinte

fattore elementare di ordine n una somma di n (≥ 1) letterali di variabili distinte

Esempi:

,.etc.

,.etc.

Le clausole e i fattori elementari con n > 1 sono funzioni di livello 1.

Dicesi:

forme elementari: funzioni di livello 2 costituite da somme di clausole (forme elementari di primo tipo o di tipo P) o, dualmente, da prodotti di fattori elementari (forme elementari di secondo tipo o di tipo S);

Esempi

a + b + cx

Date n variabili dicesi

mintermine o termine prodotto (termine P) una clausola di ordine n e quindi un prodotto dei letterali di tutte le variabili. I mintermini di n variabili sono 2ⁿ

Esempi

e così via.

maxtermine o fattore somma (fattore S) una somma di n letterali, uno per ciascuna variabile. Anche i maxtermini di n variabili sono 2ⁿ

Esempi

Nella convenzione adottata, si ha, per il teorema di De Morgan:

_i.

Si hanno inoltre le seguenti eguaglianze, facilmente dimostrabili:

                              

   

Si noti che i mintermini (maxtermini) sono particolari funzioni che assumono valore 1 (0) per una sola n-pla di valori delle variabili indipendenti.

Tabelle di verità e forme canoniche

Funzioni di n variabili

Se l'algebra è finita, una funzione può essere definita in forma tabellare, definendo il valore della variabile dipendente per tutte le finite combinazioni di valori delle n variabili indipendenti.

Se l'algebra ha k valori (per l'algebra primordiale k = 2) i punti in cui la funzione deve essere definita sono

Ciascuna funzione è poi caratterizzata da un suo valore in corrispondenza di ciascun punto; poiché i punti sono N e i valori sono k, il numero complessivo M di funzioni di n variabili è:

Se è k = 2; si ha:

Tabella di verità e forma normale P

La tabella che definisce una funzione si dice tabella di verità, in quanto, sul modello di algebra della logica, stabilisce una corrispondenza fra i valori di verità della proposizione risultante e quelli delle proposizioni componenti.

Tabella di verità di una funzione di tre variabili

Il passaggio dalla tabella di verità ad una forma algebrica può essere ottenuto facilmente considerando che:

Applicando la relazione iterativamente alle n variabili alla variabile x₁, si ha:

avendo posto se il valore della funzione in corrispondenza del punto P_i è 1, altrimenti.

Si ha dunque:

Essa dice che una funzione è espressa da una sommatoria dei mintermini in corrispondenza dei quali la tabella di verità espone

La forma normale P si trae direttamente dalla tabella di verità, trasformando i valori della funzione nei suoi punti in altrettante Ad esempio, dalla tabella di cui all'esempio precedente si ha:

α₀ = α_l = α₂ = α₃ = α₇= 1                     α₄ = α₅ = α₆ = 0

e la forma normale P è:

Oltre che con la dimostrazione algebrica di cui sopra, alla forma canonica si può anche pervenire tramutando in forma algebrica i connettivi logici impliciti nella tabella di verità.

Da quanto esposto si può trarre la regola generale:

Forma normale ed altre forme P

Da quanto detto in precedenza si ha che:

Tutte le funzioni dell'algebra primordiale sono algebriche in quanto per qualsiasi funzione esiste almeno la forma normale P e quindi la possibilità di esprimere la funzione come somma di prodotti.

La forma normale è una particolare forma elementare; da essa, con appositi passaggi algebrici, si possono trovare altre forme della funzione.

Viceversa, data una funzione in una forma algebrica qualsiasi, se ne può trovare la forma normale di primo tipo con il seguente procedimento:

a)      esecuzione delle operazioni indicate fra parentesi o espansione della funzione, fino a trasformarla in una forma elementare di somma di clausole;

b) moltiplicazione di ciascuna clausola non contenente i letterali di x₁,x_j,.. .,x_k per il prodotto (x_i+_i) (x_j+_j)(x_k+_k) = 1.

Forma normale di tipo S

Poiché nell'algebra di Bole vale la legge di dualità, si può affermare che:

Essa dice che una funzione è espressa da una produttoria dei maxtermini in corrispondenza dei quali la tabella di verità espone

La dualità si estende anche al modo di trarre una forma algebrica dalla tabella di verità considerando gli 0 invece che gli 1 della tabella:

L'asserto può essere dimostrato a partire dalla relazione:

e sviluppando il procedimento duale di quello precedente oppure scrivendola forma normale della funzione negata

da cui, complementando, applicando il teorema di De Morgan e tenendo conto che è , si ha:

che è appunto la forma canonica di tipo S.

Si noti che per a_i = 1 risulta e quindi nella prima forma normale è presente, mentre e quindi nella seconda forma normale è assente e viceversa per a_i

Numeri caratteristici

La stringa ordinata di valori a , tipica di ciascuna funzione, di lunghezza 2ⁿ per funzioni di n variabili e coincidente con la colonna di '0' e '1' nella tabella di verità, costituisce un numero binario che può essere adoperato per identificare la funzione e viene detto numero caratteristico o designativo della funzione.

Ad esempio:

Il numero caratteristico viene talora adoperato come pedice per identificare la funzione; la f di cui sopra sarebbe allora indicata come f₂₄₁.

Avendo ordinato le variabili indipendenti, si ha che il numero caratteristico della prima, seconda, terza..  variabile sono rispettivamente:

# x₀ = 0 101010101

# x₁ = 0 100110011

# x₂ = 0 100001111

e così via.

Dati i numeri caratteristici di a e b, quello delle funzioni a + b, a ∙ b, si può ottenere eseguendo rispettivamente le operazioni logiche di somma, prodotto e negazione sui bit omologhi dei numeri caratteristici di a e b

Ad esempio, il numero caratteristico della funzione

f = a + bc + b

si può ottenere come segue:

# a                           = 00001111

# b                          = 00110011

# c                           = 01010101

# bc = 00010001

# a + bc                   = 00011111

b = 00110000

= 00111111

L'impiego dei numeri caratteristici spesso semplifica le manipolazioni algebriche ed è molto utile per rappresentare numericamente le funzioni in programmi di elaborazioni booleane su calcolatori.

Equazioni booleane

Un'equazione booleana banale è espressa dall'eguaglianza

dove è un mintermine di n variabili; la ovvia soluzione di tale equazione e quella per la quale sono uguagli ad 1 tutti i letterali di P_i. Dualmente, l'equazione

ha per radice i valori nulli di tutti i letterali di S_i. Ad esempio, per

a b = l

si ha la radice mentre per

a + b + = 0

si ha la radice .

Più in generale, un'equazione in n variabili si può porre nella forma:

f(x₁, x₂,. x_n) = 1;             

e le sue soluzioni si possono agevolmente trovare ponendo f nella forma

normale P;

                        

È evidente che ciascun mintermine per il quale sia , se eguagliato ad 1, la soddisfa e determina dunque una delle radici dell' equazione. Ad esempio, l'equazione

a b c + a b + a c = l

ha le tre radici:

Dualmente si può procedere con la forma S: l'equazione

                    

ha per radici i singoli maxtermini per i quali sia a_i = 0 eguagliati a 0.

Se la è in forma elementare (invece che canonica), si può pervenire rapidamente alla soluzione dell'equazione f = 1 . Infatti una clausola di ordine i con i < n eguagliata ad 1 impone infatti unitari i suoi letterali e non impone alcuna condizione sulle variabili in essa non presenti.

Per funzioni di 3 variabili a b c, ad esempio, l'equazione

a c = 1

pone come soluzioni

che indicheremo sinteticamente con la sequenza di valori

dove il 'tratto' sta ad indicare i due possibili valori 0 ed 1. Con riferimento all'esempio precedente si ha allora:

a b c + a b + a c = a b + a c = l

da cui risultano le soluzioni

che indicano sinteticamente le medesime soluzioni già trovate.

Nel caso più generale, un'equazione booleana può porsi nella forma

f(X) = g(X)  

i valori di verità di f(X} e g(X} devono coincidere, cioè che f(X} e g(X} o sono entrambe false o entrambe vere; si ha pertanto:

ovvero:

che, posta nella forma (11.4), determina le radici dell'equazione.

Funzioni incompletamente specificate

Nella definizione di una funzione y = f(x₁, x₂,,x_n) può accadere che in corrispondenza di alcune n-ple di valori delle x_i non sia assegnato il valore di y

Ciò può avvenire per due motivi:

a)     le variabili x_i non sono in realtà indipendenti fra loro.

b)     pur assumendo le x_i i valori corrispondenti ai punti di non specificazione, è realmente indifferente ai fini pratici il valore di y in tali punti.

Si dice allora che la funzione ha punti di indifferenza (don't care) o valori di non specificazione: essi saranno indicati con il simbolo 'ф' (che ricorda appunto sia il simbolo '0' che il simbolo 'l') o con il simbolo '-'.

Esempio

Per la funzione:

Le funzioni compatibili sono:

Le condizioni di indifferenza si possono esprimere algebricamente come condizioni di 'vincolo' sulle variabili, mediante un'equazione booleana .

(x₁, x₂,,x_n) = 1              

le cui radici indicano i punti in cui la funzione è definita oppure mediante l'equazione opposta:

(x₁, x₂,,x_n) = 1

le cui radici indicano i punti di non specificazione. Per la funzione di fig. 12.1, ad esempio, si hanno le condizioni di vincolo

+ c + a + a c + a b + a b c = a + = 1

oppure le condizioni di non specificazione

b b c = b = 1

Una condizione di vincolo abbastanza diffusa è che, posto

y = f(x₁, x₂,,x_k, ℓ₁, ℓ₂,,ℓ_q) = f(X, L)              

sussista la relazione

                 

In altri termini, su k delle n variabili (che abbiamo dette x) sussiste la condizione che mai due di esse siano eguali ad 1.

Si consideri ora che ciascun mintermine è dato dal prodotto di un mintermine nelle sole X e di uno nelle sole L:

Posto allora y nella forma normale (9.3), fattorizzando rispetto alle , si ha:

Considerando ora che i mintermini nella X aventi due variabili uguali ad 1 sono nulli per la (12.3), si può effettuare un cambio di indici, numerando solo i seguenti :

con j=0 i termini con i₁=0

con j=q i mintermini nelle X con x_q=1 e tutte le altre x_i=0

(gli altri mintermini sono certamente nulli):

Si ha allora:

A ciascun termine j della sommatoria si aggiungano ora, perché non specificati, tutti i termini del tipo, dove è un mintermine con x_j=1 e le altre x in una qualsiasi configurazione e si ponga in evidenza ; si ha:

in quanto la sommatoria di tutti i mintermini nelle k-1 variabili x che escludono x_j è 1. Si ha in definitiva:   

Quindi la funzione y può essere scomposta nella forma di k + 1 funzioni delle sole variabili ℓ_l, ℓ₂,,ℓ_q; di queste funzioni una è moltiplicata per il mintermine, mentre ciascuna delle altre k è moltiplicata per una diversa X_j.

Se in particolare y è funzione delle sole x (q= 0, n=k), allora ciascuna delle coincide con una costante e si ha:

Dalla (12.4) si ricava per dualità che, con la condizione di vincolo

si ha:

Implicanti di una funzione

Si ricorda che le relazioni

sono equivalenti e sono verificate se e solo se (cfr. § 6):

Qualora ciò si verifichi, diremo che f₁ è un implicante di f.

Per ogni assegnata funzione f, esistono in genere molte funzioni che la implicano; pertanto per ogni funzione fisseremo un insieme I di funzioni implicanti di f

Dato un insieme I di implicanti di una funzione f, si dice primo implicante, o implicante principale, l'implicante che a sua volta non implica nessun altro implicante dell'insieme. Con interpretazione grafica è primo implicante di f un insieme contenuto in f e non in altri insiemi anch'essi contenuti in f f f f f , sono implicanti di f, ma di questi, solo f , e f sono primi, avendosi:

;       ; ;

;      ; ;

Data una funzione in forma elementare di tipo P, le n clausole A_i sono implicanti di f, cioè

                                

Si ha infatti:

Fra tutti gli implicanti di f assumono particolare importanza le clausole che la implicano o, in altri termini, le clausole che possono comparire in una qualsiasi forma elementare; nel seguito si assume l'insieme I degli implicanti di f come l'insieme delle clausole implicanti f, che indicheremo semplicemente come implicanti.

Assumono inoltre particolare importanza alcune proprietà delle clausole:

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

b)     La somma di due clausole di ordine n che contengono n - l letterali uguali ed in cui un letterale dell'una sia il complemento di quello dell'altra è la clausola di ordine n - l formata dai letterali comuni

c)     Ad una funzione può essere aggiunto un suo implicante senza alterarne il valore, cioè se A f si ha:

f = f + A

d)     A è un implicante di f se e solo se nella prima forma canonica di f sono presenti tutti i mintermini aventi A come fattore

I diagrammi di Veitch e le mappe di Karnaugh

I diagrammi di Veitch e le mappe di Kamaugh costituiscono mezzi grafici per la rappresentazione di funzioni booleane di poche variabili; su di essi è inoltre possibile eseguire manipolazioni e semplificazioni delle forme algebriche di una funzione.

Le mappe di Kamaugh costituiscono una forma topograficamente organizzata delle tabelle di verità, secondo la quale la combinazione di valori delle variabili indipendenti corrispondenti ad un termine P si ottiene leggendo i valori segnati in corrispondenza della riga e della colonna cui il termine p appartiene.

Nella forma proposta da Veitch, esse costituiscono una organizzazione topografica dell'algebra degli insiemi: le funzioni di n variabili (2 n 4) sono rappresentate mediante n sottoinsiemi dell'insieme totale e i 2ⁿ mintermini si ottengono per intersezione dei sottoinsiemi dell'algebra.

Considerando 'adiacenti' i quadratini che abbiano un lato in comune e i quadratini posti alle estremità opposte della mappa, si hanno le seguenti caratteristiche notevoli delle mappe:

i mintermini che si oppongono in una sola variabile sono adiacenti e quindi le coppie di quadratini adiacenti rappresentano una clausola di ordine (n -1);

per n 2, le clausole di ordine (n - 1) che si oppongono in una sola variabile sono ancora adiacenti e quindi le 'quadruple' rappresentano clausole di ordine (n - 2);

per n 3 le 'ottuple' poste come in fig. 14.3d) rappresentano clausole di ordine (n - 3).

a) 2 variabili

    

b) 3 variabili

c) 4 variabili

Diagrammi di Veitch e mappe di Karnaugh

Diremo sottocubi di ordine n i singoli quadratini delle mappe, di ordine (n - 1) le 'coppie' di ordine (n - 2) le 'quadruple' e di ordine (n -3) le 'ottuple'. Si ha ovviamente che tutti i sottocubi di una funzione rappresentano gli implicanti della funzione stessa e rappresentano pertanto tutti i termini elementari nei quali la funzione può essere scomposta.

Altra notevole proprietà delle mappe è che gli implicanti primi di una funzione sono i sottocubi di 'area massima' o, in altri termini, i sottocubi non contenuti in altri sottocubi della funzione.

Sfortunatamente, non è possibile con un disegno piano ottenere tutte le caratteristiche di cui sopra per funzioni a più di 4 variabili; a volte si adoperano disegni pluridimensionali; l'immediatezza della visione di cui godono i diagrammi per funzioni di 2,3 e4 variabili viene comunque persa.

Le mappe di Karnaugh, oltre a rappresentare una funzione in forma canonica o elementare, consentono di trasformare facilmente una funzione da forma canonica ad elementare nonché da una forma elementare a quella canonica o ad altra elementare; sono infine utili per verificare l'identità fra due forme diverse della stessa funzione.

Per le funzioni in forma canonica o elementare di tipo S è possibile costruire mappe in maniera del tutto simile, adoperando un procedimento duale; in particolare, si segna uno O in corrispondenza di ciascun fattore S_i per cui è _i = 0 ed i fattori S si dispongono sulla mappa in modo che S_i occupi il posto omologo di P_i. Ne consegue che la mappa di tipo S ha gli '0' segnati in tutte le posizioni in cui la mappa di tipo P non ha alcun segno e pertanto sulla medesima mappa possono, per dualità, legger si entrambe le forme P ed S.