RETI LOGICHE e aLGEBRA DI  boole

Le reti logiche, reti elettriche che "ragionano", sono alla base del funzionamento dei sistemi digitali moderni, come i computer e altri dispositivi elettronici, ma anche di circuiti tradizionali che elaborano contatti on-off.

Eseguono operazioni logiche di base (come AND, OR, NOT) tra gli ingressi binari per determinare il valore dell'uscita; combinando queste operazioni si realizzano  funzioni anche molto complesse, cioè espressioni matematiche che stabiliscono come gli ingressi devono influenzare le uscite.

Questo processo può essere realizzato in logica cablata o programmata.

In logica cablata (cablare=collegare con fili):

• • collegando in serie-parallelo contatti di ingresso 

  • collegando tra loro singoli circuiti elettrici (porte logiche) ognuno dei quali realizza una operazione logica

  • per cambiare la funzione svolta bisogna ricablare la rete elettrica

In logica programmata, molto più flessibile, le porte logiche sono in grado di realizzare legami logici tra gli ingressi secondo istruzioni che possono cambiare di volta in volta.

La matematica che descrive questi processi è l'algebra di Boole (1815-1864). Utilizza variabili binarie, che possono assumere solo due stati (simboli), e un numero molto limitato di operazioni diverse.  

Nel modo più semplice possibile si può definire l'algebra come un insieme di operazioni tra numeri, simboli e variabili. Con l'algebra si possono scrivere e risolvere espressioni matematiche, equazioni e problemi che coinvolgono variabili.

Funzioni e forme rappresentative

Associando variabili ed operatori si generano le espressioni booleane.

Bisogna prestare particolare attenzione alle validità delle  proprietà associativa, commutativa e distributiva per i vari operatori perchè possono non essere verificate. Ad es.  la realizzazione di operazioni logiche a 3 o più  ingressi con porte logiche a 2 ingressi dello stesso tipo, deve essere valutata attentamente.

Una funzione booleana esprime la dipendenza di una variabile (unica uscita) da una  espressione formata da operatori e variabili (ingressi).  In algebra di Boole il numero di funzioni diverse dipende dal numero di variabili; ad es. con 2 variabili ci sono 4 casi diversi e quindi  2^4=8 funzioni, con 3 variabili 2^8=256 funzioni. Invece nell'algebra tradizionale già con una sola variabile ci sono infinite funzioni. 

Per le funzioni  utilizzeremo 4 forme rappresentative:

• la  forma letterale

• la tabella di verità, più o meno estesa in funzione del numero delle variabili di ingresso ma certamente limitata dato che le variabili possono assumere solo 2 valori. Questo non è possibile nell'algebra classica.

• la mappa di Karnaugh (ingegnere statunitense nato nel 1924), forma simile alla tabella di verità ma con caratteristiche particolari.

• lo schema logico, rappresentazione grafica tramite i simboli grafici delle porte; lo schema logico è la base per lo schema elettrico e la successiva realizzazione circuitale.

Si pongono due problemi:

• il passaggio tra le forme rappresentative 

• la semplificazione della funzione per la più semplice realizzazione possibile.

PROPRIETA' E TEOREMI

LAB

Un interruttore gestisce un display a 7 segmenti: nelle due condizioni si vuole visualizzare la lettera https://www.subito.it/biciclette/bicicletta-vintage-freni-a-bacchetta-uomo-pisa-530625545.htmL oppure H. Progettare:

•  la rete di supporto all'interruttore (pull-up o pull-down), 

• il display a catodo o anodo comune e le resistenze di limitazione della corrente

• la rete combinatoria 

Secondo la tabella si associa:

• al tasto aperto il valore logico L e al tasto chiuso il valore logico H

• alla tensione  Vo = E  il valore logico H, alla tensione Vo= 0V il valore logico 0. 

Si può fare anche al contrario.  

ES. Commentare il compito svolto dalle resistenze in termini di pull-up o pull-down

ES. Rifare l'esercizio con i deviatori senza incrociare i contatti.

Compito N. 1:

• descrivere una funzione logica elementare: forma letterale, regola, tabella, simbolo grafico

• passaggio dallo schema logico alla forma letterale e viceversa

• passaggio dalla forma letterale alla tabella

• verifica dell'uguaglianza di due espressioni tramite tabella

• verifica delle proprietà ( distributiva, associativa, ecc, )

• semplificazione di una funzione tramite le proprietà, i teoremi (1° e 2° dell'assorbimento, De Morgan) e la tecnica dell'unica variabile che cambia tra due espressioni

Passaggio dalla tabella alla funzione e semplificazione con le mappe di Karnaugh

mintermine: AND tra tutte le variabili prese in forma diretta o negata. In funzione del numero n degli ingressi sono possibili 2n mintermini, uno per ogni riga della tabella; per ottenere il mintermine associato ad una riga della tabella si prende la variabile in forma negata se è presente con lo zero, in forma diretta con l'uno.

Ad es.

ES. Se 3 pulsanti su 4 sono on allora l'uscita si attiva.

forma canonica: metodo standard per rappresentare una funzione in forma letterale a partire dalla rappresentazione tabellare.

1° forma canonica: una funzione, espressa in forma tabellare, è l'OR di tutti i mintermini che  portano la funzione a 1. Per l'es. precedente risulta Y=A B C + A B C+ ...   e il mintermine  A B C non si considera perchè la funzione nella riga corrispondente (2°) vale 0.

maxtermine  e 2° forma canonica: Applicando la regola di dualità si definisce il maxtermine (OR tra tutte le variabili prese in forma diretta se presenti con 0 e negata con 1) e la 2° forma canonica ( AND di tutti i maxtermini che  portano la funzione a 0). La seconda forma canonica può essere utile se la funzione presenta pochi 0.

semplificazione:  In genere le espressioni canoniche ottenute sono ridondanti e semplificabili. Poichè i mintermini hanno lo stesso numero di variabili si può procedere applicando la regola dell'eliminazione dell'unica variabile presa in uno in forma diretta e nell'altro in forma negata. Quindi da due mintermini si può ottiene un termine con un numero inferiore di variabili. Se da altri due mintermini si ottiene un altro termine semplificato è possibile iterare il procedimento. E' possibile cosi' accorpare 2, 4, 8, ecc. mintermini. 

Mappe di Karnaugh: Si pone il problema del riconoscimento dei mintermini accorpabili. Le mappe sono una ulteriore forma di rappresentazione di una funzione (oltre alla tabella, schema logico e forma letterale) che consente di risolvere il problema graficamente perchè i mintermini accorpabili sono posti vicini tra loro. Questo avviene perchè le celle sono posizionate in base al codice Gray e non al codice binario naturale.

Si ricorda che il codice Gray gode della proprietà che configurazioni vicine differiscono per un solo bit (o una sola variabile).

In genere la soluzione ottimale non è unica. L'obiettivo della semplificazione è la realizzazione della funzione con il minor numero di accorpamenti, che devono essere il più grande possibile, senza tralasciare nessun mintermine. Questo perchè più è grande l'accorpamento più ridotto è il numero di variabili coinvolte  e più semplice la realizzazione.

Si consiglia il seguente procedimento:

• si fa una scansione ordinata dei mintermini

• si individuano e si includono nella funzione i mintermini non accorpabili e quelli 'obbligati' nel senso che si possono accorpare solo in una modalità. Ad es. un accorpamento a 4 è da preferire agli accorpamenti a 2 interni. Ma uno a 4 non è da preferire immediatamente ad uno a 2 che si sviluppa su altri mintermini: in questo caso conviene tralasciali entrambi e proseguire la ricerca. Ad es. nel caso seguente l'accorpamento a 4 non è da considerare!

• al termine della scansione si sceglie uno  degli accorpamenti  tralasciati (ad es. quello più grande) e si reitera.

In rete si trovano semplici sw che risolvono le mappe.

Osservazioni:

• Il metodo grafico delle mappe oltre 4 variabili diventa complicato da gestire e si usano altri metodi come l'algoritmo di Quine-McCluskey.

• Si osserva che la semplificazione con le mappe può risultare  non ottimale, ad es.  in funzione del numero di integrati da utilizzare, perchè impone una realizzazione rigida con struttura AND-OR. 

• Una realizzazione SW della funzione, ad es. con microcontrollori, se non estrema in termini di velocità di esecuzione o di memoria occupata, può risultare più leggibile e rimodificabile (caratteristiche da non sottovalutare) in forma non semplificata. 

• Oggi la realizzazione circuitale delle funzioni logiche, tramite FPGA e CI analoghi, passa attraverso rappresentazioni testuali che una successiva compilazione può semplificare. La problematica risolvibile con le mappe può risultare obsoleta.

Porte universali

Sono porte che con una loro combinazione possono realizzare tutte le altre porte, grazie al teorema di De Morgan.

Sono le porte nand e nor.

Compito N.2: (in rosso i saperi minimi per il 6)

Mappe . Porte universali.

• Data una tabella a 2, 3 o 4 variabili, utilizzando la 1° forma canonica e le mappe, ricavare la funzione semplificata. 

• Semplificare una funzione data in forma analitica tramite le mappe. Calcolare il numero di integrati della serie 74xx necessario per realizzare la funzione semplificata

• Data una funzione rappresentare lo schema logico con le porte universali Nand o Nor applicando, se necessario De Morgan. Calcolare il numero di integrati della serie 74xx necessario per realizzare la funzione iniziale e quella trasformata.