Appunti Calcolatori elettronici I

Tabella di verità

Se un supporto con cardinalità finita K, con algebra di Boole ha due valori, qualsiasi funzione si rappresenta con una tabella, detta tabella di verità, questa rappresenta su ogni riga il valore della funzione e quindi avrò 2 righe nell’algebra di Boole.

Letterali, clausole e fattori elementari

Se ho una funzione e voglio trovarne la rappresentazione algebrica, meglio pensare a quando tratto con molte variabili, allora definisco:

• Letterale: simbolo usato per rappresentare un valore generico in ingresso che definisce una variabile e specifica la variabile indipendente che può avere valore negato o meno.
• Clausola: è il prodotto dei letterali.
• Fattore elementare: somma di letterali.
• Grado di una clausola: numero di letterali che compaiono in essa.

ES. clausola a(b!) di ordine 2, fattore elementare a+b!+c è di grado 3.

Forma elementare

Definisco una funzione nella sua forma elementare se è una somma di prodotti (di letterali) Σ, o quando somma di clausole, oppure prodotto di somme.

Mintermini e maxtermini

Una funzione si dice maxtermine se è somma dei letterali di tutte le variabili indipendenti.

Si dice mintermine se è prodotto dei letterali delle variabili indipendenti.

Quindi, un mintermine è una clausola di grado n, mentre un maxtermine è un fattore elementare di grado n, dove n è numero di variabili. ̅⋅⋅̅⋅ ̅ ++̅

Es. Per una funzione a quattro variabili, è un esempio di mintermine, mentre + di maxtermine.

Essendo un prodotto, un mintermine vale 1 se e solo se tutti i letterali valgono 1 e il discorso analogo vale per il maxtermine con lo 0.

Si può notare che un letterale si può presentare in forma negata o meno, quindi a seconda di quali letterali nego, distinguo vari mintermini e maxtermini per lo stesso num di var indipendenti. In generale, per n variabili, ci sono 2 mintermini e lo stesso numero di maxtermini.

Implicanti

Un implicante di una funzione è una funzione che implica la prima. In altri termini, un implicante di una funzione, contiene una parte della verità della funzione stessa.

Implicante primo: si dice implicante primo se non implica nessun’altra funzione oltre a f. In ottica di insieme, dove la f è insieme, gli implicanti primi sono i primi insiemi contenuti in f, e non quelli contenuti a loro volta in questi.

Proprietà

• Se ho una funzione in forma elementare P, ciascuna clausola è un suo implicante.
• Una clausola implica l’altra se e solo se la prima contiene i letterali della seconda.
• La somma di due clausole di ordine n che differiscono in un solo letterale è clausola di ordine n-1 che è formata da letterali in comune ed è detta consenso.
• Ad una funzione può essere aggiunto un suo implicante senza alterarne il valore.

Una clausola A è un implicante di una funzione se e solo se nella forma formale di tipo P di f sono presenti tutti i mintermini aventi A come fattore comune.

Quindi scegliamo gli implicanti primi perché contengono il minor numero di implicanti rispetto agli altri implicanti.

Mappe di Karnaugh

Questa mappa è una rappresentazione tabellare delle funzioni booleane che sostituisce la tabella di verità.

Ogni casella rappresenta un punto del dominio, dove su una coordinata considero le configurazioni di un insieme di variabili, ed un’altra coordinata rappresenta la configurazione