Cos'è ElectroYou | Login Iscriviti

ElectroYou - la comunità dei professionisti del mondo elettrico

8
voti

LogicBignami (II)

In questa seconda parte daremo uno sguardo alle principali funzioni booleane e alle loro proprietà, che sono il fondamento per la comprensione e sviluppo di qualsiasi circuito digitale.

Indice

Algebra di Boole (o booleana)

E' quel particolare ramo dell'algebra che studia, tra l'altro, la logica di tipo binario, ossia dove le variabili possono assumere due soli significati che si escludono reciprocamente.

Esempi di variabili binarie potrebbero essere: la posizione di un interruttore o di una serratura (aperto o chiuso), lo stato di una lampadina (accesa o spenta), lo stato di moto di una ruota (gira o è ferma) in tutti un significato esclude, automaticamente, l'altro.

Intendendo questi articoli come riassunto di un corso di elettronica digitale, verrà trattata esclusivamente l'algebra booleana a due valori.

Nota: Nel proseguio, salvo diversamente specificato, si considererà l'associazione delle affermazioni "VERO" e "FALSO" rispettivamente ai simboli 1 e 0.

Funzione booleana

Dati:
L'insieme universo U\; (definizione di un insieme il cui complemento è un inseme vuoto: \overline U = \empty)
un suo sottoinsieme A\; (A \subset U)
ed una variabile x \in U,

si definisce funzione booleana sull'insieme A la funzione fA tale per cui:

se x \in A allora f_A(x) = 1\;, quindi è VERA

se x \notin A allora f_A(x) = 0\;, quindi è FALSA

Esempio pratico:
Consideriamo un contenitore (il nostro insieme universo U) con all'interno oggetti di due soli colori (le variabili binarie), verdi e blu. Mettiamo poi un'altra scatola all'interno del contenitore e in questa raggruppiamo tutti gli oggetti verdi (il nostro sottoinsieme A) e consideriamo l'affermazione "è verde" (la nostra fA).
A questo punto si possono verificare due situazioni:

se peschiamo un oggetto (la nostra variabile binaria x) dentro la scatola, quindi un oggetto verde, allora saremo nella situazione x \in A e fA(x) = 1

se, invece, peschiamo un oggetto fuori dalla scatola, quindi un oggetto blu, allora saremo nella situazione x \notin A e fA(x) = 0

Operatori logici fondamentali

Negazione (o complemento): funzione logica NOT - simbolo :

Dati:

L'insieme universo U
un suo sottoinsieme A\; (A \subset U)
e due variabili x\; e \; y \in U,
con x \in A\; e y \notin A

possiamo scrivere le due funzioni booleane f_A(x) = 1\; e fA(y) = 0.

Dalla definizione di complemento che abbiamo visto precedentemente, possiamo anche scrivere che y \in \overline A\; e che x \notin \overline A\;, dove \overline A\; è l'insieme complemento di A.

Da ciò otteniamo f_{\overline A}(x) = 0\; e f_{\overline A}(y) = 1\;, che ci porta alla definizione della funzione logica NOT o Negazione:

f_{\overline A}(x) = \overline {f_A(x)}

Assegnando a f_A(x)\; i due possibili valori booleni 1 e 0, otteniamo, allora, la seguente tabella (detta Tabella della verità):

fA(x)
f_{\overline A}(x)
0
1
1
0

In pratica la funzione logica NOT altro non fa che invertire il valore assunto dalla funzione (o variabile) booleana alla quale viene applicata.: se è VERO la funzione logica NOT restituirà FALSO e viceversa.

Il simbolo grafico associato a questa funzione è il seguente:


dove x può rappresentare una funzione o, direttamente, una variabile booleana.


Proprietà della funzione NOT:

Una funzione (o variabile) booleana a cui venga applicata due volte la funzione logica NOT equivale alla funzione (o variabile) iniziale:

\overline {\overline {f_A(x)}} = f_A(x)

Congiunzione: funzione logica AND - simbolo \cdot

Dati:

L'insieme universo U
due sottoinsiemi A\; (A \subset U) e B\; (B \subset U)\; tali che A \cap B \not= \empty
quattro variabili w, x, y\;e\; z \in U tali che
w \notin A\; e w \notin B
x \in A\; e x \notin B
y \in (A \cap B)
z \notin A\; e z \in B

Consideriamo le funzioni booleane per l'insieme A\;, B\; e (A \cap B)\; relative a queste quattro variabili otteniamo la seguente tabella della verità:

fA(x) = 1
fB(x) = 0
f_{A \cap B}(x) = 0
fA(z) = 0
fB(z) = 1
f_{A \cap B}(z) = 0
fA(y) = 1
fB(y) = 1
f_{A \cap B}(y) = 1
fA(w) = 0
fB(w) = 0
f_{A \cap B}(w) = 0

Da questa si deduce che la funzione booleana relativa all'operazione intersezione è VERA se, sul medesimo elemento, sono VERE, contemporaneamente, anche le funzioni booleane dei singoli insiemi, interessati dall'operazione, altrimenti è sempre FALSA.

L'operazione di intersezione viene definita congiunzione o funzione logica AND, convenzionalmente indicata anche come prodotto logico:

f_A(n) \cdot f_B(n) = f_{A \cap B}(n)

In pratica la funzione logica AND tra due o più funzioni (o variabili) booleane è VERA solo se tutte le funzioni (o variabili) booleane coinvolte sono VERE.

Il simbolo grafico associato alla funzione è il seguente:


dove x e y possono rappresentare funzioni o, direttamente, variabili booleane.

Proprietà della funzione AND

Elemento assorbente per il prodotto logico: Il prodotto logico tra una funzione (o variabile) booleana e una condizione di FALSO, restituisce sempre una condizione di FALSO:
f_A(x) \cdot 0 = 0
Di fatto, il prodotto logico con una condizione di FALSO, blocca l'operazione sulla medesima condizione.

Elemento neutro per il prodotto logico: Il prodotto logico tra una funzione (o variabile) booleana e una condizione di VERO, restituisce la funzione (o variabile) booleana stessa:
f_A(x) \cdot 1 = f_A(x)

Proprietà di idempotenza: Il prodotto logico tra una funzione (o variabile) booleana per se stessa, restituisce la funzione (o variabile) booleana stessa:
f_A(x) \cdot f_A(x) = f_A(x)

Complementarietà: Il prodotto logico di una funzione (o variabile) booleana per la sua negazione, restituisce sempre una condizione di FALSO:
f_A(x) \cdot \overline {f_A(x)} = 0

Proprietà cummutativa: Il prodotto logico tra due funzioni (o variabili) booleane non cambia invertendo l'ordine dei fattori:
f_A(x) \cdot f_B(x) = f_B(x) \cdot f_A(x)

Disgiunzione: Funzione logica OR - Simbolo: +

Prendiamo in esame le stesse condizioni utilizzate per la funzione logica AND, quindi siano dati:

L'insieme universo U
due sottoinsiemi A\; (A \subset U) e B\; (B \subset U)\; tali che A \cap B \not= \empty
quattro variabili w, x, y\;e\; z \in U tali che
w \notin A\; e w \notin B
x \in A\; e x \notin B
y \in (A \cap B)
z \notin A\; e z \in B

Consideriamo, quindi, le funzioni booleane per l'insieme A\;, B\; e (A \cup B)\; relative a queste quattro variabili, ottenendo la seguente tabella della verità:

fA(x) = 1
fB(x) = 0
f_{A \cup B}(x) = 1
fA(z) = 0
fB(z) = 1
f_{A \cup B}(z) = 1
fA(y) = 1
fB(y) = 1
f_{A \cup B}(y) = 1
fA(w) = 0
fB(w) = 0
f_{A \cup B}(w) = 0

In questo caso la funzione booleana relativa all'operazione di unione è VERA quando, sul medesimo elemento, almeno una delle funzioni booleane dei singoli insiemi, interessati dall'operazione, è VERA, altrimenti è FALSA.
L'operazione di unione viene definita disgiunzione o funzione logica OR, convenzionalmente indicata anche come somma logica:


f_A(n) + f_B(n) = f_{A \cup B}(n)

In pratica la funzione logica OR tra due o più funzioni (o variabili) booleane è VERA quando almeno una delle funzioni (o variabili) booleane coinvolte è VERA.

Il simbolo grafico associato alla funzione è il seguente:

dove x e y possono rappresentare funzioni o, direttamente, variabili booleane.

Proprietà della funzione OR

Elemento neutro per la somma logica: La somma logica tra una funzione (o variabile) booleana e una condizione di FALSO, restituisce la funzione (o variabile) booleana stessa:
fA(x) + 0 = fA(x)

Elemento assorbente assorbente per la somma logica: La somma logica tra una funzione (o variabile) booleana e una condizione di VERO, restituisce sempre una condizione di VERO:
fA(x) + 1 = 1
Di fatto, la somma logica con una condizione di VERO, blocca l'operazione sulla medesima condizione.

Proprietà di idempotenza: La somma logica tra una funzione (o variabile) booleana per se stessa, restituisce la funzione (o variabile) booleana stessa:
fA(x) + fA(x) = fA(x)

Complementarietà: La somma logica tra una funzione (o variabile) booleana per la sua negazione, restituisce sempre una condizione di VERO:
f_A(x) + \overline {f_A(x)} = 1

Proprietà cummutativa: La somma logica tra due funzioni (o variabili) booleane non cambia invertendo l'ordine dei fattori:
fA(x) + fB(x) = fB(x) + fA(x)

Avendo visto sia la funzione logica AND che la funzione logica OR, adesso possiamo analizzare la Legge di assorbimento, la Proprietà distributiva e i Teoremi di De Morgan accennati nella Teoria degli insiemi.

Legge di assorbimento - Proprietà distributiva - Teoremi di De Morgan

Legge di assorbimento: Il prodotto logico tra una funzione (o variabile) booleana e la somma logica tra la medesima funzione (o variabile) booleana e una seconda funzione (o variabile) booleana equivale alla prima funzione (o variabile) booleana:
f_A(x) \cdot (f_A(x) + f_B(x)) = f_A(x)

Si nota, infatti, che la condizione logica di f_B(x)\; è ininfluente sull'operazione: se f_A(x)\; è VERA la somma logica è il prodotto logico sono entrambi VERI, viceversa, se f_A(x)\; è FALSA, automaticamente il prodotto logico è FALSO qualunque sia la condizione logica della somma logica.

La stessa Legge si applica alla somma di prodotto: La somma logica tra una funzione (o variabile) booleana e il prodotto logico tra la medesima funzione (o variabile) booleana e una seconda funzione (o variabile) booleana equivale alla prima funzione (o variabile) booleana:
f_A(x) + (f_A(x) \cdot f_B(x)) = f_A(x)

Anche in questo caso la condizione logica di f_B(x)\; è ininfluente sull'operazione: se f_A(x)\; è VERA, la somma logica è VERA a prescindere dalla condizione logica assunta dal prodotto logico, viceversa, se f_A(x)\; è FALSA lo sono sia la somma che il relativo prodotto logico.

Propietà distributiva:
1) La somma logica tra una funzione (o variabile) booleana e il prodotto logico di due funzioni (o variabili) booleane equivale al prodotto logico tra la somma logica tra la prima funzione (o variabile) booleana e la seconda funzione (o variabile) booleana e la somma logica tra la prima funzione (o variabile) booleana e la terza funzione (o variabile9 booleana):
f_A(x) + (f_B(x) \cdot f_C(x)) = (f_A(x) + f_B(x)) \cdot (f_A(x) + f_C(x))

Analizziamo i diversi casi:
f_A(x) = 1\; In questo caso, qualunque siano le condizioni logiche di f_B(x)\; e di f_C(x)\;, sia l'operazione a destra che quella a sinistra dell'equivalenza sono VERE.
f_A(x) = 0\; In questo caso possiamo vedere che, per le proprietà della somma logica, le due operazioni di riducono, entrambe, al prodotto logico f_B(x) \cdot f_C(x).

2) Il prodotto logico tra una funzione (o variabile) booleana e la somma logica di due funzioni (o variabili) booleane equivale alla somma logica tra il prodotto logica tra la prima funzione (o variabile) booleana e la seconda funzione (o variabile) booleana e il prodotto logico tra la prima funzione (o variabile) booleana e la terza funzione (o variabile9 booleana):
f_A(x) \cdot (f_B(x) + f_C(x)) = (f_A(x) \cdot f_B(x)) + (f_A(x) \cdot f_C(x))

L'analisi è simile alla precedente, solo che si invertono le condizioni logiche di f_A(x)\;:

f_A(x) = 0\; In questo caso, qualunque siano le condizioni logiche di f_B(x)\; e di f_C(x)\;, sia l'operazione a destra che quella a sinistra dell'equivalenza sono FALSE.
f_A(x) = 1\; In questo caso possiamo vedere che, per le proprietà del prodotto logico, le due operazioni di riducono, entrambe, alla somma logica fB(x) + fC(x).

Teoremi di De Morgan:
1) La negazione del prodotto logico tra due, o più, funzioni (o variabili) booleane equivale alla somma logica delle singole funzioni (o variabili) negate:
\overline {f_A(x) \cdot f_B(x)} = \overline{f_A(x)} + \overline {f_B(x)}

Analizziamo l'equivalenza scrivendo la tabella della verità per le due operazioni in base alle proprietà del prodotto logico, della somma logica e della negazione:

fA(x)
fB(x)
\overline {f_A(x) \cdot f_B(x)}
\overline {f_A(x)}
\overline {f_B(x)}
\overline{f_A(x)} + \overline {f_B(x)}
0
0
1
1
1
1
0
1
1
1
0
1
1
0
1
0
1
1
1
1
0
0
0
0

l'equivalenza è soddisfatta.

2) La negazione della somma logica tra due, o più, funzioni (o variabili) booleane equivale al prodotto logico delle singole funzioni (o variabili) negate:
\overline {f_A(x) + f_B(x)} = \overline{f_A(x)} \cdot \overline {f_B(x)}

Anche in questo caso eseguiamo l'analisi dell'equivalenza tramite la tabella della verità:

fA(x)
fB(x)
\overline {f_A(x) + f_B(x)}
\overline {f_A(x)}
\overline {f_B(x)}
\overline{f_A(x)} \cdot \overline {f_B(x)}
0
0
1
1
1
1
0
1
0
1
0
0
1
0
0
0
1
0
1
1
0
0
0
0

anche in questo caso l'equivalenza è soddisfatta.

Somma disgiuntiva: Funzione logica EX-OR - Simbolo: \oplus

Questa funzione logica rappresenta un'estensione della funzione logica OR.

In pratica la funzione logica EX-OR, a differenza della funzione logica OR, è VERA solo se le fuznioni (o variabili) booleane che partecipano all'operazione assumono condizioni logiche differenti, altrimenti è FALSA.
Quindi, considerando le due funzioni booleane f_A(x)\; e f_B(x)\;, la funzione logica EX-OR f_A(x) \oplus f_B(x)\; risponde alla segente tabella della verità:

fA(x)
fB(x)
f_A(x) \oplus f_B(x)
0
0
0
0
1
1
1
0
1
1
1
0

Quando tratteremo le porte logiche elementari e i circuiti combinatori, vedremo che la funzione logica EX_OR equivale a:

f_A(x) \oplus f_B(x) = (f_A(x) \cdot \overline {f_B(x)}) + (\overline {f_A(x)} \cdot f_B(x))

Il simbolo grafico associato alla funzione è il seguente:


dove x e y possono rappresentare funzioni o, direttamente, variabili booleane.

Proprietà della funzione EX_OR

Elemento neutro per la somma disgiuntiva: La somma logica disgiuntiva tra una funzione (o variabile) booleana e una condizione di FALSO, restituisce la funzione (o variabile) booleana stessa:
f_A(x) \oplus 0 = f_A(x)

La somma logica disgiuntiva tra una funzione (o variabile) booleana e una condizione di VERO, equivale a complementare la funzione (o variabile) booleana stessa:
f_A(x) \oplus 1 = \overline {f_A(x)}

La somma logica disgiuntiva tra una funzione (o variabile) booleana per se stessa, restituisce sempre una condizione di FALSO:
f_A(x) \oplus f_A(x) = 0

Complementarietà: La somma logica tra una funzione (o variabile) booleana per la sua negazione, restituisce sempre una condizione di VERO:
f_A(x) \oplus \overline {f_A(x)} = 1

Proprietà cummutativa: La somma logica disgiuntiva tra due funzioni (o variabili) booleane non cambia invertendo l'ordine dei fattori:
f_A(x) \oplus f_B(x) = f_B(x) \oplus f_A(x)

Con questo abbiamo concluso anche questa lunga chiacchierata sull'algebra booleana e le sue funzioni fondamentali per l'elaborazione dei circuiti digitali.
Prossimamente inizieremo ad analizzare le porte logiche fondamentali e i circuiti combinatori.

Articoli collegati

LogicBignami (I) - Elementi di teoria degli insiemi
Appendice LogicBignami (II) - Elenco proprietà funzioni logiche

11

Commenti e note

Inserisci un commento

di ,

Grazie mir!!!

Rispondi

di ,

Bel lavoro Max ! A mio (umile avviso) direi che va bene, del resto se non erro si cerca di elaborare un Bignami, pertanto la sintesi è d'obbligo, fermo restando che simil testo si indirizza a chi come me ad esempio non è andato oltre la maturità tecnica.. ;).

Rispondi

di ,

Ok, faccio così...
Grazie ancora della annotazione.

Rispondi

di ,

In realtà, Max, credo che quasi nessun istituto tecnico o facoltà di ingegneria abbia mai dato la vera definizione di algebra booleana ai propri studenti... comunque, a mio avviso (e se ho ben capito EdmondDantes concorda con me) basterebbe riscrivere il primo periodo della sezione sull'algebra di commutazione in questo modo: "E' quel particolare ramo dell'algebra che studia, tra l'altro, la logica di tipo binario, ossia dove le variabili possono assumere due soli significati che si escludono reciprocamente." e contestualmente specificare (nel punto del testo che ti pare più adatto) che intendi trattare solo e soltanto l'algebra booleana a due valori.

Rispondi

di ,

Wruggeri non sei rompiscatole, anzi... Ma come ho detto all'inizio dell'articolo precedente (LogicBignami I) quanto scrivo deriva dai miei studi da Istituto Tecnico e in quel contesto (almeno nella prima metà degli anni '80), nel corso di elettronica digitale, veniva data quella definizione semplicistica (e, allora, sufficiente). Se preferite andare più nello specifico dovete scrivermi per filo e per segno quello che intendete in modo che io possa aggiungerlo, ovviamente citandovi come autori perchè, in tutta onestà, io più in là della definizione che ho dato non so andare. Grazie

Rispondi

di ,

Ok, questo il link della precisazione

Rispondi

di ,

EdmondDantes, ti rispondo in un messaggio a parte per evitare papiri illeggibili (se solo si potesse andare a capo nei commenti...): mi rendo conto che era quasi scontato dal punto di vista di chi già sa le cose, perché in quella condizione ci si può permettere di essere "approssimativi", ma a chi sta imparando di fatto viene fornita una definizione sbagliata contro cui si scontreranno se vorrano procedere con l'approfondimento personale. A proposito, grazie per la precisazione sulle algebre banali e non banali: avrei dovuto scriverla io stesso, ma - mea culpa - mi è sfuggita :)

Rispondi

di ,

Ho già trattato in breve l'argomento nel paragrafo "Una precisazione terminologica" di questo mio articolo: https://www.electroyou.it/wruggeri/wiki/forma-cum-laude-logica-proposizionale. Volendo, potremmo essere ancora più formali e parlare di anelli booleani definendo le algebre booleane come algebre costruite su di essi "rinforzandone" un po' le proprietà (tranne che nel caso dell'algebra di commutazione, che se ben ricordo è l'unica algebra booleana non banale ad avere esattamente le proprietà del suo anello), discuterne le assiomatizzazioni e i risultati fondamentali (mi vengono in mente, sul momento, il criterio di Kuratowski-Posament e il teorema di Stone)... ma secondo me rischia di essere un discorso poco interessante: di fatto, credo che a molti elettronici serva operativamente conoscere al più la definizione di algebra booleana e come essa si traduce nel caso specifico dell'algebra di commutazione.

Rispondi

di ,

Leggendo le due note, penso che sarebbe utile o aprire una discussione nel forum o, eventualmente, scrivere un articolo che precisi come si classificano le "algebre di Boole". Perché anche su Wikipedia la distinzione non è fatta, e credo che la maggioranza degli utenti, me compreso, non specializzati in logica matematica, quando nominano l'algebra di Boole intendono quella che tratta le due variabili: VERO, FALSO. ;-)

Rispondi

di ,

Nel suo primo articolo ha specificato che l'interno corso e' focalizzato sull'elettronica digitale. Possiamo dire che era quasi scontato :). Al limite potrebbe specificare, nell'introduzione di questa seconda parte, che tratterà esclusivamente l'algebra di Boole a due elementi (dato lo scopo finale di questa serie di articoli), chiamandola semplicemente algebra Boole. A questo punto, specificando meglio il tuo intervento, dovremmo dire che la più semplice algebra di Boole non banale e' l'algebra di Boole a due elementi.

Rispondi

di ,

Faccio il rompiscatole: non è vero che nell'algebra booleana (notando che dire "l'algebra booleana" non ha senso, visto che ne esistono moltissime) le variabili possono assumere due soli valori!!! L'ALGEBRA DI COMMUTAZIONE, che è l'algebra booleana più semplice (o almeno, quella basata sull'anello booleano più piccolo), ha variabili che ammettono solo due valori, ma esistono algebre booleane (esempi banali delle quali sono le algebre di insiemi) che di valori per le variabili ne ammettono ben più di due.

Rispondi

Inserisci un commento

Per inserire commenti è necessario iscriversi ad ElectroYou. Se sei già iscritto, effettua il login.