PDF generato attraverso il toolkit opensource ''mwlib''. Per maggiori informazioni, vedi [[http://code.pediapress.com/ http://code.pediapress.com/]].PDF generated at: Thu, 08 Mar 2012 01:16:01 UTC

BOOLEand or not

IndiceVoci

Porta logica 1Algebra di Boole 6Tabella della verit 16

NoteFonti e autori delle voci 20Fonti, licenze e autori delle immagini 21

Licenze della voceLicenza 22

Porta logica 1

Porta logica

Schema circuitale e fotografia di un integratocontenente porte logiche NAND

In elettronica digitale e informatica, una porta logica un circuitodigitale in grado di implementare una particolare operazione logica diuna o pi variabili booleane.

Descrizione

Le porte logiche sono : le porte a due variabili AND, OR, XOR, NOR,NAND, XNOR e a singola variabile NOT. In particolare le porte OR,AND e NOT costituiscono un insieme funzionalmente completo:attraverso gli operatori logici che implementano possibile generarequalsiasi funzione logica.

In genere le porte pi utilizzate sono le NAND e NOR, ovvero AND eOR negate. Si noti che le operazioni NAND e NOR costituiscono uninsieme funzionalmente completo di operatori logici, ovveroconsentono di rappresentare qualunque funzione logica possibile.Comunque all'atto pratico, la scelta dei tipi di porta da utilizzare determinata dalla necessit di minimizzare il numero di packagenecessari al circuito; ad esempio, se nella stesura finale dello schema elettrico di un progetto mancasse solo una portaNOT e fosse ancora disponibile una delle quattro porte NAND contenute in un package, si realizza la porta NOTmancante, unendo gli ingressi della NAND disponibile, sfruttandola come NOT, risparmiando cos un package.

Esistono porte logiche anche per quanto riguarda la pneumatica e l'idraulica.

Porte Open collectorAlcune porte logiche hanno la loro uscita configurate elettricamente in modo particolare, sono definite opencollector, ovvero a collettore aperto. In questi dispositivi, il collettore del transistor costituente l'uscita della portanon collegato al positivo dell'alimentazione, ma volante rispetto al circuito interno. Questa configurazionepermette di utilizzare la porta per pilotare direttamente dispositivi vari, quali rel, LED, ecc, semprech il valore dicorrente assorbita dal dispositivo pilotato, sia compatibile con quello fornito dal transistor di uscita. Un vantaggioulteriore costituito dal valore di tensione accettato dal transistor, normalmente superiore a quella di alimentazionedel circuito integrato, pertanto, in un circuito composto da dispositivi TTL alimentato a 5 volt, utilizzando una portaopen collector, possibile per esempio, ottenere un'onda quadra di ampiezza 12 o pi volt, prelevandola dalcollettore opportunamente collegato tramite una resistenza pull-up ad una tensione positiva del valore desiderato,oppure pilotare un rel, collegando uno dei capi della sua bobina sull'uscita della porta, e l'altro capoall'alimentazione positiva, di valore adeguato al suo funzionamento. Una delle porte pi comuni, ampiamenteutilizzata, definita HEX INVERTER BUFFER DRIVER (6 NOT in un package) il 7406. Una regola generale,piuttosto importante ai fini di preservare il circuito realizzato da eventuali momentanei disturbi casuali, nel casorimanesse qualche porta inutilizzata in qualche package (in particolare le porte CMOS), bene collegare a massa isuoi ingressi.

Porta logica 2

Tabelle di veritLe tabelle di verit sono un metodo semplice per minimizzare le funzioni logiche. Innanzitutto servono per capire glistati logici delle varie porte logiche in modo sbrigativo e di facile comprensione

AND e NAND

Porta AND

AND una porta logica che riceve in ingresso almeno due valori erestituisce 1 solo se tutti i valori di ingresso hanno valore 1.Segue la tavola di verit:

INPUT OUTPUT

0 0 0

0 1 0

1 0 0

1 1 1

Porta NAND

Al contrario la porta NAND restituisce la negazione di una portaAND e quindi restituisce 0 solo quando tutti i valori in ingressosono 1.Segue la tavola di verit:

INPUT OUTPUT

0 0 1

0 1 1

1 0 1

1 1 0

Porta logica 3

OR e NOR

Porta OR

OR una porta logica che riceve in ingresso almeno 2 valori erestituisce 1 se almeno un valore di ingresso ha valore 1.Segue la tavola di verit:

INPUT OUTPUT

0 0 0

0 1 1

1 0 1

1 1 1

Porta NOR

Al contrario la porta NOR restituisce la negazione di una porta ORe quindi restituisce 1 solo quando tutti i valori in ingresso sono 0.Segue la tavola di verit:

INPUT OUTPUT

0 0 1

0 1 0

1 0 0

1 1 0

XOR

Porta XOR

XOR (eXclusive OR) una porta logica che riceve in ingresso "n"valori e restituisce "1" in uscita se e solo se, il numero di ingressiche presentano il valore logico "1" dispari.Segue la tavola di verit di una porta XOR a "n=2" ingressi:

Porta logica 4

INPUT OUTPUT

A B o A o B

0 0 0

0 1 1

1 0 1

1 1 0

XNOR

Porta XNOR

XNOR (eXclusive NOR) una porta logica che riceve in ingresso"n" valori e restituisce "1" in uscita se e solo se, entrambi gliingressi sono uguali. Segue la tavola di verit di una porta XNOR:

INPUT OUTPUT

A B o A o B neg.

0 0 1

0 1 0

1 0 0

1 1 1

NOT

Porta NOT

Porta logica che inverte il segnale in ingresso.Questa porta logica ha un solo ingresso ed una uscita che sar 1 sel'ingresso 0 o 0 altrimenti.Segue la tavola di verit:

Porta logica 5

INPUT OUTPUT

A NOT A

0 1

1 0

Tuttavia questa tavola di verit a volte rappresentata con due elementi superflui rappresentanti gli ingressi identici:

INPUT OUTPUT

A NOT A

0 1

1 0

0 1

1 0

Voci correlate Algebra Booleana Mappa di Karnaugh Elettronica digitale Top view Porta logica AND Porta logica OR Porta logica NAND Porta logica NOT Porta logica NOR Porta logica XOR Porta logica XNOR Porta quantistica Edge triggered

Altri progetti

Wikimedia Commons contiene file multimediali: http:/ / commons. wikimedia. org/ wiki/ Category:LogicGates

Algebra di Boole 6

Algebra di BooleIn matematica, informatica ed elettronica, l'algebra di Boole, anche detta algebra booleana o reticolo booleano, un ramo dell'algebra astratta che comprende tutte le algebre che operano con i soli valori di verit 0 o 1, dettivariabili booleane o logiche. La struttura algebrica studiata dall'algebra booleana finalizzata all'elaborazione diespressioni nell'ambito del calcolo proposizionale.Essendo un reticolo dotato di particolari propriet, l'algebra booleana risulta criptomorfa, cio associatabiunivocamente e in modo da risultare logicamente equivalente, ad un insieme parzialmente ordinato reticolato. Ognialgebra booleana risulta criptomorfa ad un particolare tipo di anello, chiamato anello booleano.Tale algebra permette di definire gli operatori logici AND, OR e NOT, la cui combinazione permette di svilupparequalsiasi funzione logica e consente di trattare in termini esclusivamente algebrici le operazioni insiemistichedell'intersezione, dell'unione e della complementazione, oltre a questioni riguardanti singoli bit 0 e 1, sequenzebinarie, matrici binarie e diverse altre funzioni binarie.L'algebra di Boole, sviluppata nel 1854 da George Boole, un matematico inglese dell'University College di Cork,assume un ruolo importante in vari ambiti, in particolare nella logica matematica e nell'elettronica digitale, dovenella progettazione dei circuiti elettronici riveste grande importanza il teorema di Shannon, introdotto da ClaudeShannon intorno al 1940 e utilizzato per scomporre una funzione booleana complessa in funzioni pi semplici, o perottenere un'espressione canonica da una tabella della verit o da un'espressione non canonica.

DefinizioneL'algebra di Boole tratta l'algebra universale dell'algebra a due stati e dei modelli di tale teoria, detti algebrebooleane. L'algebra universale la famiglia di operazioni su un insieme, detto insieme fondamentale della famigliaalgebrica, che nel caso della struttura algebrica booleana contiene i soli valori 0 e 1.Il numero degli argomenti che richiede una funzione sull'insieme fondamentale detto ariet: un'operazione su {0,1}di ariet n pu essere applicata ad ognuno dei 2n possibili valori dei suoi n argomenti. Per ogni scelta di argomentil'operazione pu produrre i soli risultati 0 e 1, donde ci sono 22n operazioni di n argomenti.L'algebra a due stati possiede due operazioni con nessun argomento, i valori 0 e 1, e quattro operazioni con un soloargomento: due operazioni costanti, l'identit e la negazione, ques'tultima da come risultato 0 se l'argomento 1 eviceversa. Vi sono poi sedici operazioni binarie: due costanti, due che danno come risultato rispettivamente solo ilprimo argomento e solo il secondo, la congiunzione, che produce 1 se entrambi gli argomenti sono 1 e d 0altrimenti; la disgiunzione, che produce 0 se entrambi gli argomenti sono 0 e d 1 altrimenti; e cos via. Il numero dioperazioni con n+1 argomenti il quadrato del numero delle operazioni con n argomenti, sicch vi sono 162 = 256operazioni ternarie, 2562 = 65.536 operazioni quaterniarie e cos via.Una famiglia, detta anche indice, indicizzata da un insieme di indici, che nel caso di una famiglia di operazionicostituenti un'algebra sono detti simboli dell'operazione e costituiscono il linguaggio dell'algebra in oggetto.L'operazione indicizzata da un dato simbolo detta interpretazione di tale simbolo, ed ogni simbolo definisce ilnumero univoco di argomenti delle rispettive interpretazioni possibili. Nel caso considerato vi una corrispondenzabiunivoca tra simbolo e interpretazione. L'algebra di Boole ha 22n simboli, e dunque lo stesso numero dioperazioni, detti simboli di operazione booleana; anche se poche operazioni hanno simboli convenzionali, quali per la negazione, per la congiunzione e per la disugiunzione. In generale si indica con nfi l'i-esimo simbolo di nargomenti.

Algebra di Boole 7

BasiUna base un insieme di operazioni la cui composizione permette di ottenere tutte le operazioni appartenentiall'algebra. Le tre principali basi usate nell'algebra booleana sono: Il reticolo, una base logica introdotta nel diciannovesimo secolo da George Boole, Charles Sanders Peirce e altri

matematici che cercavano una formalizzazione algebrica dei processi logici. L'anello booleano, una base aritmetica introdotta nel ventesimo secolo da Ivan Ivanovich Zhegalkin e Marshall

Stone che proviene dall'algebra astratta. La base NAND, originata dal fatto che tramite l'operazione di NAND possibile ottenere tutte le operazioni

sull'insieme {0,1}. Tale base utilizzata in particolare nella configurazione dei circuiti logici in elettronicadigitale.

Gli elementi comuni a reticolo e anello sono le costanti 0 e 1 ed un'operazione binaria associativa e commutativa,che nella base del reticolo detta incontro, dal termine inglese meet, e denotata tra due elementi x e y dal simboloxy, mentre nella base dell'anello detta moltiplicazione e denotata xy. La base del reticolo ha inoltre le operazionialgebriche di unione xy e complemento x, mentre la base dell'anello ha l'ulteriore operazione aritmetica diaddizione xy o x+y.

ReticoloNella base del reticolo ad un'algebra booleana (A, , ) si associa un insieme parzialmente ordinato (A, ),definendo:

che anche equivalente a

possibile anche associare un'algebra booleana ad un reticolo distributivo (A, ), considerato come insiemeparzialmente ordinato, dotato di elemento minimo 0 e di elemento massimo 1, in cui ogni elemento x ha uncomplementare tale che

e

Qui e sono usati per denotare l'inf ed il sup di due elementi. Se i complementi esistono, allora sono unici.

AnelloLa base dell'anello della generica algebra booleana (A, , ) definita come (A, +, *), definendo a + b := (a b) ( b a ). In tale anello l'elemento neutro per la somma coincide con lo 0 dell'algebra booleana, mentrel'elemento neutro della moltiplicazione l'elemento 1 dell'algebra booleana. Questo anello ha la propriet che a * a =a per ogni a in A; gli anelli con questa propriet sono chiamati anelli booleani.Viceversa, assegnato un anello booleano A, possiamo trasformarlo in un'algebra booleana definendo x y = x + y x y e x y = x y. Poich queste due operazioni sono l'una l'inversa dell'altra, possiamo affermare che ognianello booleano criptomorfo di un'algebra booleana e viceversa. Inoltre, una funzione f : A B unomomorfismo tra algebre booleane se e soltanto se un omomorfismo tra anelli booleani. La categoria degli anellibooleani e delle algebre booleane sono equivalenti.Un anello ideale dell'algebra booleana A un sottoinsieme I tale che per ogni x, y in I si ha x y in I e per ogni a in A a x in I. Questa nozione di ideale coincide con la nozione di anello ideale negli anelli booleani. Un ideale I di A detto primo se I A e se a b in I implica sempre a in I o b in I. Un ideale I di A detto massimale se I A e se l'unico ideale proprio contenente I A stesso. Questa notazione coincide con la notazione teorica del ideale primo

Algebra di Boole 8

e ideale massimale nell'anello booleano A.Il duale di un ideale un filtro. Un filtro dell'algebra booleana A un sottoinsieme F tale che per ogni x, y in F si hax y in F e per ogni a in A se a x = a allora a in F.L'operazione di complementazione * applicata ai sottoinsiemi manda dunque gli ideali in filtri e viceversa: se B un'algebra booleana e un suo ideale (proprio), allora il filtro (proprio) duale di I. Seinvece un filtro (proprio), l'ideale (proprio) duale di F.

Sheffer strokeLa base Sheffer stroke o NAND si basa sulle operazioni NOT e AND, tramite le quali possibile ottenere tutte leoperazioni booleane. Un'algebra booleana pu essere definita sia da NOT e AND che da NOT e OR, essendopossibile definire OR attraverso NOT e AND cos come AND attraverso NOT e OR:

La collezione di tutti i sottoinsiemi di un dato insieme, ovvero l'insieme delle parti o insieme ambiente, munita delleoperazioni di unione, intersezione e complementazione di insiemi, che giocano rispettivamente il ruolo di OR, ANDe NOT, costituisce un'algebra booleana.Pi formalmente, se B un insieme formato da almeno 2 elementi, l'algebra booleana avente B come supporto lastruttura algebrica costituita da B, da due operazioni binarie su B, OR e AND, da un'operazione unaria NOT su B edall'elemento 0 di B, i quali godono delle seguenti propriet:

Simmetria di AND: Simmetria di OR: Involuzione di NOT: Leggi di De Morgan: L'insieme B inoltre limitato inferiormente, essendo:

L'elemento 1 definito come la negazione, o il complementare, dello 0: 1 := NOT(0). L'insieme B dunque limitatosuperiormente, essendo:

ed in particolare0 AND 1 = 0 ; 0 OR 1 = 1

Si definisce inoltre, come operazione derivata dalle precedenti, l'operatore binario OR esclusivo, denotato XOR:

In questa algebra all'operatore XOR corrisponde la differenza simmetrica:

In elettronica la porta logica NAND costituita da n ingressi e un'uscita che si porta a livello 0 solo se gli n ingressisi portano a livello 1. corrispondente alla connessione in serie di una porta AND e di una NOT.

Algebra di Boole 9

Operatori booleaniGli operatori dell'algebra booleana possono essere rappresentati in vari modi. Spesso sono scritti semplicementecome AND, OR e NOT. Nella descrizione dei circuiti, possono anche essere usati NAND (NOT AND), NOR (NOTOR) e XOR (OR esclusivo).Esistono diverse simbologie per rappresentare gli operatori, scelte in base al campo in cui si lavora: i matematiciusano spesso il simbolo + per l'OR, e per l'AND, in quanto per alcuni versi questi operatori lavorano in modoanalogo alla somma e alla moltiplicazione. La negazione NOT viene rappresentata spesso da una linea disegnatasopra l'argomento della negazione, cio dell'espressione che deve essere negata. Oppure in informatica si utilizza ilsimbolo | o || per l'OR, & o && per l'AND, e ~ per NOT (es. A OR B AND NOT C equivale a A|B & ~C).Nella progettazione di circuiti elettronici, vengono utilizzati anche gli operatori brevi NAND (AND negato), NOR(OR negato) e XNOR (XOR negato): questi operatori, come XOR, sono delle combinazioni dei tre operatori base evengono usati solo per rendere la notazione pi semplice.Operatori: NOT - simboli alternativi: x, ~, , ! AND - simboli alternativi: *, , &, BUT (usato nella logica booleana insieme al NOT) OR - simboli alternativi: +, |, XOR - simboli alternativi: , +, , , ^, EOR, orr NAND - simbolo alternativo: NOR - simbolo alternativo: XNORValori: vero - simboli alternativi: true, 1, ON, SI (YES) falso - simboli alternativi: false, 0, OFF, NOIn elettronica digitale viene definito vero un bit 1, sia in Input che in Output, che di solito assume il valore di 5 V,mentre viene definito falso un bit 0, sia in Input che in Output, che assume il valore di 0 V.Di seguito sono indicati gli operatori pi comuni e le rispettive porte logiche:

NOTL'operatore NOT restituisce il valore inverso a quello in entrata. Una concatenazione di NOT semplificabile con unsolo NOT in caso di dispari ripetizioni o con nessuno nel caso di pari.Inoltre la porta logia NOT possiede una solavariabile binaria.

A NOT A

0 1

1 0

Spesso, al fine di semplificare espressioni complesse, si usano operatori brevi che uniscono l'operazione di NOT adaltre: questi operatori sono NOR (OR + NOT), NAND (AND + NOT), XNOR (XOR + NOT). La negazione, inquesti casi, viene applicata dopo il risultato dell'operatore principale (OR, AND, XOR).Il simbolo di una porta NOT

Algebra di Boole 10

ORL'operazione logica OR restituisce 1 se almeno uno degli elementi 1, mentre restituisce 0 in tutti gli altri casi. Taleoperazione anche detta somma logica.

A B A OR B

0 0 0

0 1 1

1 0 1

1 1 1

Nella teoria degli insiemi corrisponde all'unione.Il simbolo di una porta OR :

ANDL'operazione AND d come valore 1 se tutti gli operandi hanno valore 1, mentre restituisce 0 in tutti gli altri casi.Tale operazione anche detta prodotto logico.

A B A AND B

0 0 0

0 1 0

1 0 0

1 1 1

possibile realizzare un'operazione logica AND con un numero di proposizioni arbitrarie concatenando varie ANDa due ingressi, per esempio:

Nei circuiti digitali, la porta logica AND un meccanismo comune per avere un segnale di vero se un certo numerodi altri segnali sono tutti veri.Nella teoria degli insiemi corrisponde all'intersezione.Il simbolo di una porta AND :

XORL'operatore XOR, detto anche EX-OR, OR esclusivo o somma modulo 2, restituisce 1 se e solo se la somma deglioperandi uguali ad 1 dispari, mentre restituisce 0 in tutti gli altri casi.

Algebra di Boole 11

A B A XOR B

0 0 0

0 1 1

1 0 1

1 1 0

Nella teoria degli insiemi corrisponde alla differenza simmetrica. Per passare nella forma canonica SP (somma diprodotti) basta applicare la regola:AB dove il simbolo di XOR.Il simbolo di una porta XOR :

BufferBuffer la negazione del risultato dell'operazione NOT; restituisce il valore uguale a quello in entrata. Il Buffer non un vero e proprio operatore, poich in realt non manipola l'informazione che riceve, bens la lascia passareinvariata; il Buffer dunque semplificabile con un collegamento privo di operatori.

A Buffer A

0 0

1 1

Il simbolo di una porta Buffer :

composta da un NOT in serie ad un altro NOT.

NORL'operatore NOR, la negazione del risultato dell'operazione OR, restituisce 1 se e solo se tutti gli elementi sono 0,mentre restituisce 0 in tutti gli altri casi.

A B A NOR B

0 0 1

0 1 0

1 0 0

1 1 0

Il simbolo di una porta NOR :

composta da un NOT in serie ad un OR.Utilizzando le leggi di De Morgan, possibile convertire una porta AND in NOR. Vale, dunque, la seguenterelazione:

Algebra di Boole 12

NANDL'operatore NAND, la negazione del risultato dell'operazione AND, restituisce 0 se e solo se tutti gli elementi sono1, mentre restituisce 1 in tutti gli altri casi.

A B A NAND B

0 0 1

0 1 1

1 0 1

1 1 0

Il simbolo di una porta NAND :

composta da un NOT in serie ad un AND.Utilizzando le leggi di De Morgan, possibile convertire una porta OR in NAND. Vale, dunque, la seguenterelazione:

XNORL'operatore XNOR, detto anche EX-NOR, la negazione del risultato dell'operazione XOR; nella sua versione a dueelementi restituisce 1 se tutti gli elementi sono uguali a 1 oppure se tutti gli elementi sono uguali a 0.

A B A XNOR B

0 0 1

0 1 0

1 0 0

1 1 1

Il simbolo di una porta XNOR :

composta da un NOT in serie ad un XOR.

EsempiQuesta algebra ha applicazioni nella logica, dove 0 interpretato come "falso", 1 come vero, OR, AND e

"NOT". Le espressioni che coinvolgono le variabili e le operazioni booleane rappresentano forme dichiarative;due espressioni possono essere equivalenti utilizzando i suddetti assiomi se e soltanto se le forme dichiarativecorrispondenti sono logicamente equivalenti. L'algebra booleana binaria, inoltre, usata per il disegno di circuitinell'ingegneria elettronica; qui 0 e 1 rappresentano le due condizioni differenti di un bit in un circuito digitale, ingenere bassa e alta tensione. I circuiti sono descritti da espressioni che contengono delle variabili e due espressionisono uguali per tutti i valori delle variabili se e soltanto se i circuiti corrispondenti hanno la stessa funzione ditrasferimento. Ogni combinazione dei segnali in ingresso in uscita dal componente pu essere rappresentata daun'adeguata espressione booleanaL'algebra booleana a due stati inoltre importante nella teoria generale delle algebre booleane, perch un'equazione che coinvolge parecchie variabili generalmente vera in ogni algebra booleana se e soltanto se vera nell'algebra

Algebra di Boole 13

booleana a due stati. Ci pu, per esempio, essere usato per indicare che le seguenti leggi ( teoremi di consenso )sono generalmente valide in ogni algebra booleana:

Il raggruppamento di un generico insieme S, forma un'algebra booleana con le due operazioni = unione e =intersezione. Il pi piccolo elemento 0 l'insieme vuoto ed il pi grande elemento 1 l'insieme S stesso.

L'insieme di tutti i sottoinsiemi di un insieme S che sono limitati un'algebra booleana. Per ogni numero naturale n, l'insieme di tutti i divisori positivi di n forma un reticolo distributivo se scriviamo

per a divide b. Questo reticolo un'algebra booleana se e soltanto se per ogni n non vi sono divisoriquadrati. Il pi piccolo elemento,che in generale indichiamo con lo 0, in questa algebra booleana il numeronaturale 1; mentre l'elemento che usualmente indichiamo con l'1 in questi insiemi l'elemento "n".

Altri esempi di algebre booleane sono dati dagli spazi topologici: se X uno spazio topologico, allora l'insieme ditutti i sottoinsiemi di X che siano aperti o chiusi formano un'algebra booleana con le operazioni = unione e = intersezione.

Se R un anello arbitrario dove definito un insieme idempotente tipo:A = { a in R : a2 = a e a x = x a per ogni x in R }L'insieme A diventa un'algebra booleana con le operazioni a b = a + b a b ed a b = a b.

Omomorfismi ed isomorfismiUn omomorfismo tra due algebre booleane A e B una funzione f: A B tale che per ogni a, b in A:1. f( a b ) = f( a ) f( b )2. f( a b ) = f( a ) f( b )3. f(0) = 04. f(1) = 1Da queste propriet segue anche f( a) = f(a) per ogni a in A. Ogni algebra booleana, con la definizione diomomorfismo, forma una categoria. Un isomorfismo da A su B un omomorfismo da A su B che biiettivo.L'inverso di un isomorfismo ancora un isomorfismo, e le due algebre booleane A e B si dicono isomorfe. Dal puntodi vista della teoria dell'algebra booleana, due algebre booleane isomorfe non sono distinguibili, ma differisconosoltanto nella notazione dei loro elementi.

Espressioni booleaneAll'interno di ciascuna algebra di Boole, dato un insieme di variabili e le operazioni correlate, possibile definiredelle espressioni che vengono ad assumere un determinato valore ottenibile anche sotto forme diverse. Possonoesistere cio delle espressioni che, pur essendo differenti, si rivelino equivalenti. Oltre al fatto che le espressionibooleane assumono una particolare importanza per quanto riguarda il calcolo proposizionale, in cui le variabili sonoproposizioni legate tramite congiunzioni, disgiunzioni, negazioni ed altre operazioni pi complesse, possono esisteremoltissime altre espressioni, accomunate sempre dalle propriet e dagli assiomi booleani, nelle quali si sostituiscespesso l'operazione + (comunemente detta somma) con e * (comunemente detta prodotto) con e in cui lacomplementazione indicata col simbolo ' .Per poter presentare nel modo pi efficiente una espressione booleana, la si riduce in somma di prodottifondamentali o forma normale disgiuntiva. Un prodotto fondamentale un prodotto in cui ciascuna variabile, o il suocomplemento, appaia una sola volta e rigorosamente fuori da parentesi o complementazioni complesse.Ad esempio, date le variabili x, y, z all'interno di un'algebra di Boole, sono prodotti fondamentali P(x,y,z) = xy

Algebra di Boole 14

P(x,y,z) = x'yz'Mentre non sono prodotti fondamentali yyz yy'z (xy)' cos possibile avere una somma di prodotti fondamentali, forma in cui ogni espressione pu essere ridotta, ma chenon unica. Un esempio : xy + xz + z'. Nel momento in cui ogni singola variabile, o il suo complemento, sianocontenuti in tutti i prodotti fondamentali della forma normale disgiuntiva, si ha allora una somma di prodottifondamentali completa o forma normale disgiuntiva completa. Tale scrittura unica, pertanto se due espressionisono equivalenti avranno la stessa forma normale disgiuntiva completa.Se si desidera invece che un'espressione sia scritta nel modo pi corto possibile, allora la si esprime in somma diimplicanti prime o minimali (Minimizzazione di Quine-McQluskey). Un'implicante prima (o minimale) rispetto aun'espressione un prodotto fondamentale che non altera l'espressione se sommato per intero ad essa, cio restituisceun risultato equivalente a quella iniziale; sommando un prodotto strettamente contenuto nell'implicante, tuttavia, nonsi ottiene un'equivalenza.Per individuare tutte le implicanti prime, esistono varie tecniche, tra cui il metodo del consenso, che si basasull'applicazione ciclica delle propriet di assorbimento, idempotenza, involuttivit e di De Morgan accompagnate adogni passo dall'opportuna addizione di un consenso. Dati due prodotti fondamentali, se solo e solo se una variabileappare in uno di essi non negata e nell'altro negata chiamiamo consenso il risultato della moltiplicazione dellerestanti variabili. Ad esempio: dati P = xyz, Q = x'z il consenso sar C = yzz = yz dati P = xy' Q= xy il consenso sar C = xx = x dati P = xyz e Q = x'yz' non esiste consenso, in quanto due diverse variabili appaiono una volta negate e una volta

no.La somma di implicanti prime unica, pertanto due espressioni equivalenti avranno la stessa. Nel momento in cui,completando ogni singola implicante prima, l'apporto all'espressione di una o pi di esse inutile in quantocontenuta nelle altre, la si pu eliminare ottenendo la pi essenziale delle scritture, la forma minimale. Essa, puressendo comoda, ha l'inconveniente di non essere unica, e dunque di non consentire l'individuazione di equivalenzetra pi espressioni.

Rappresentazione delle algebre booleaneSi pu dimostrare che ogni reticolo booleano finito isomorfo al reticolo booleano di tutti i sottoinsiemi di uninsieme finito. Di conseguenza, il numero di elementi di ogni reticolo booleano finito ha un sostegno che contiene unnumero di elementi uguale ad una potenza di 2.Marshall Stone ha enunciato il celebre teorema di rappresentazione per le algebre booleane dimostrando che ognialgebra booleana "A" isomorfa a tutte le algebre booleane aperte-chiuse in un certo spazio topologico, dettocompatto non connesso di Hausdorff

Algebra di Boole 15

Voci correlate 06-XX, sezione primaria dello schema di classificazione MSC 2000 Algebra di insiemi Diagramma di Venn Forma canonica Funzione booleana Mappa di Karnaugh Porta logica Sistema formale Sistema numerico binario Tabella della verit Teorema dell'assorbimento Teorema di Shannon (elettronica) Teoremi di De Morgan

Altri progetti

Wikimedia Commons contiene file multimediali: http:/ / commons. wikimedia. org/ wiki/ Category:XNORgates

Collegamenti esterni Panoramica ed esempi sulle Operazioni Booleane [1]

Note[1] http:/ / portalesapere. altervista. org/ viewtopic. php?topic=Algebra-di-Boole

Tabella della verit 16

Tabella della veritLe tabelle della verit sono tabelle matematiche usate nella logica per determinare se, attribuiti i valori di verit alleproposizioni che la compongono, una determinata proposizione vera o falsa. Utilizzate come principalerappresentazione di una funzione booleana, le espressioni possono essere costrutti formati da pi espressioni, in cuiall'inizio compare una premessa, ed alla fine una conclusione. La tabella di verit elenca sulle caselle delle righecorrispondenti alle colonne delle variabili della funzione tutte le possibili combinazioni di valori che possonoassumere le variabili booleane ed il risultato della funzione nelle caselle delle righe corrispondenti all'ultima colonnaa destra, per tale combinazione di valori.Le tabelle di verit furono introdotte da Gottlob Frege, Charles Peirce, Bertrand Russell e altri verso il 1880, edassunsero la forma attuale nel 1922, con i lavori indipendenti di Emil Post e Ludwig Wittgenstein. Nel suo TractatusLogico-Philosophicus Wittgenstein le usa per inquadrare le funzioni della verit all'interno di una serie. La vastainfluenza esercitata da questa opera ha portato ad una larga diffusione delle tabelle di verit.Le tabelle di verit sono usate per calcolare il valore di espressioni logico-funzionali. Le espressionilogico-funzionali possono essere sia atomiche (ad esempio, variabili proposizionali o semplici segnaposto) oppurefunzioni proposizionali costituite da formule atomiche e operatori logici (come AND, OR e NOT). Le intestazioni dicolonna delle tabelle della verit mostrano (i) le funzioni e/o le variabili proposizionali, e (ii) le espressioni di veritrisultanti dalle combinazioni di quelle funzioni e variabili proposizionali. Nelle righe sono riportati tutti i possibilivalori calcolati di T = vero o F = falso assegnati a (i) e (ii). In altre parole: ogni riga una diversa interpretazione di(i) e (ii).Le tabelle di verit applicate alla logica classica (cio a quella binaria) sono limitate alla logica booleana, dove sonoammessi soltanto due valori, vero (indicato anche con "1") e falso (indicato con "0").Ad esempio la seguente tabella rappresenta la funzione booleana V = XY + XZ + YZ = X AND Y OR X AND ZOR Y AND Z esprimibile anche come

F F F F

F F V F

F V F F

F V V V

V F F F

V F V V

V V F V

V V V V

Tabella della verit 17

Operatore logico negazioneLa relazione di negazione NOT () un connettivo logico, attraverso il quale, a partire da una proposizione A siforma una nuova proposizione chiamata negazione di A la quale vera quando A falsa, ed falsa quando A vera. La relazione cos definita:

F V

V F

Operatore logico congiunzionePrendiamo due variabili proposizionali, e , e l'operatore logico AND (), ottenendo la congiunzione logica "Ae B" o, pi correttamente, . In parole povere, se sia A che B sono vere, allora la congiunzione vera; ogni diversa assegnazione di valori di verit rende falsa. La relazione cos definita:

F F F

F V F

V F F

V V V

Operatore logico disgiunzionePrendiamo due variabili proposizionali, A e B, e l'operatore logico OR (V), ottenendo la congiunzione logica "A ORB", se sia A che B sono vere, allora la congiunzione A V B vera;se sono false A V B falsa;se A falsa e B veraallora A V B vera e viceversa se B vera ed A falsa allora A V B vera. La relazione cos definita: Larelazione OR () cos definita:

F F F

F V V

V F V

V V V

Operatore NAND (congiunzione negata)Espressioni composte possono essere costruite usando le parentesi per indicare la precedenza negli operatori.La negazione della congiunzione , e la disgiunzione della negazione risultano nellaseguente:

Tabella della verit 18

F F F V V V V

F V F V V F V

V F F V F V V

V V V F F F F

Operatore NORLe tabelle di verit possono essere usate per verificare equivalenze logiche.La negazione della disgiunzione ( ) , e l'unione delle congiunzioni risultanocos di seguito equivalenti:

F F F V V V V

F V V F V F F

V F V F F V F

V V V F F F F

Analizzando e confrontando le due tabelle di verit, dal momento che tutti i valori di stato possibili per e portano allo stesso stato per pari condizioni di e ; e per e , risultandouguali tra loro e alternativamente utilizzabili. Questa equivalenza conosciuta come legge di De Morgan.

Tabelle di verit per gli operatori logici pi comuniEcco le tabelle di verit per gli operatori logici pi comuni:

F F F F F V V V

F V F V V F V F

V F F V V F F V

V V V V F V V V

Legenda:V = vero, F = falso = AND (congiunzione logica) = OR (disgiunzione logica) = XOR (OR esclusivo) = XNOR (NOR esclusivo) = "se-allora" (implicazione logica) = "(allora)-se" (controimplicazione logica): se e soltanto se logicamente equivalente a : XNOR (NOR esclusivo).

I diagrammi di Johnston, simili ai diagrammi di Eulero-Venn, forniscono un metodo di visualizzazione della tabelladella verit. Un diagramma di Johnston interattivo, mostrante le tabelle della verit, reperibile qui [1].

Tabella della verit 19

Tabelle di verit condensate per operatori binariUna forma condensata della tabella di verit usata per gli operatori binari; in questa, i titoli delle righe e colonneindicano gli operandi, e gli elementi della matrice il risultato. L'algebra di Boole, ad esempio, usa questa notazionecondensata della tabella della verit:

F V

F F F

V F V

F V

F F V

V V V

Questa notazione utile specialmente se gli operatori sono commutativi, bench si possano specificare le righe comeprimo operando e le colonne come secondo. La notazione abbreviata particolarmente utile quando si trattano valorilogici multipli, dato che rallenta il vertiginoso aumento di righe che sarebbe altrimenti necessario usare. Fornisceanche una forma caratteristica e prontamente riconoscibile della distribuzione dei valori nella tabella, permettendo allettore una pi rapida comprensione.

Voci correlate Calcolo proposizionale Mappa di Karnaugh Algebra di Boole

Altri progetti

Wikimedia Commons contiene file multimediali: http:/ / commons. wikimedia. org/ wiki/ Category:Truthtables

Collegamenti esterni Generatore di tabelle di verit [2]

Note[1] http:/ / logictutorial. com[2] http:/ / turner. faculty. swau. edu/ mathematics/ materialslibrary/ truth/

Fonti e autori delle voci 20

Fonti e autori delle vociPorta logica Fonte:: http://it.wikipedia.org/w/index.php?oldid=47675415 Autori:: A7N8X, ARTE, Alfio, Alnews, An3, Avesan, Basilicofresco, Beard, Blakwolf, BlueSky, Ciro07, Cyb3rn0id,Delfort, Denadai2, Fire90, Fstefani, Galessandroni, Hellis, Igi 0, L736E, Lusum, Mambrucco, MapiVanPelt, Marcuscalabresus, Massimiliano Lincetto, Mattty, Phantomas, Simone, Tridim,WiLlY'93, Woodstock1, ^musaz, 50 Modifiche anonime

Algebra di Boole Fonte:: http://it.wikipedia.org/w/index.php?oldid=47623904 Autori:: .snoopy., AKappa, Alberto da Calvairate, Alecobbe, AnyFile, Avemundi, Beta16, Blakwolf, Buggia,Contezero, DaniDF1995, Davide, Depagen, Digitalone, DnaX, Durras, Enry17, Eumolpo, Fabexplosive, Fede Reghe, Fioravante Patrone, Fiox, Francesco Betti Sorbelli, Gabstef, Gionnico,Goemon, Ketersephirot, Kibira, Klemen Kocjancic, Lucat, Luigicaiffa, Marcel Bergeret, Marco Plassio, Marius, MartinoK, Mess, Paolovenezia, Pegua, Phantomas, Piddu, Pietrodn, Pracchia-78,Qualc1, RamsesII, Red Power, Rossa1, Salvatore Ingala, SkY`, Snowdog, Taueres, The Black, TierrayLibertad, Tridim, Trovatore, Ulisse0, Woodstock1, Ylebru, ^musaz, 118 Modifiche anonime

Tabella della verit Fonte:: http://it.wikipedia.org/w/index.php?oldid=47582320 Autori:: Beta16, Gaetanogambilonghi, Giangi74, IlCapo, Lilja, Lucio Di Madaura, Luisa, MaEr, Marcol-it,Marius, Mast, Michele Bergadano, Phantomas, Piddu, Pracchia-78, ReliableBeaver, Rossa1, Shivanarayana, Simo82, Tridim, Truman Burbank, Twice25, Ub, Ulisse0, W.visconti, Ylebru, 23Modifiche anonime

Fonti, licenze e autori delle immagini 21

Fonti, licenze e autori delle immaginiFile:7400.jpg Fonte:: http://it.wikipedia.org/w/index.php?title=File:7400.jpg Licenza: GNU Free Documentation License Autori:: 1-1111, Audriusa, Dl2000, Foroa, Inductiveload, PengoFile:AND ANSI.svg Fonte:: http://it.wikipedia.org/w/index.php?title=File:AND_ANSI.svg Licenza: Public Domain Autori:: jjbeardFile:NAND ANSI.svg Fonte:: http://it.wikipedia.org/w/index.php?title=File:NAND_ANSI.svg Licenza: Public Domain Autori:: jjbeardFile:OR ANSI.svg Fonte:: http://it.wikipedia.org/w/index.php?title=File:OR_ANSI.svg Licenza: Public Domain Autori:: jjbeardFile:NOR ANSI.svg Fonte:: http://it.wikipedia.org/w/index.php?title=File:NOR_ANSI.svg Licenza: Public Domain Autori:: jjbeardFile:XOR ANSI.svg Fonte:: http://it.wikipedia.org/w/index.php?title=File:XOR_ANSI.svg Licenza: Public Domain Autori:: jjbeardFile:XNOR ANSI.svg Fonte:: http://it.wikipedia.org/w/index.php?title=File:XNOR_ANSI.svg Licenza: Public Domain Autori:: jjbeardFile:NOT ANSI.svg Fonte:: http://it.wikipedia.org/w/index.php?title=File:NOT_ANSI.svg Licenza: Public Domain Autori:: jjbeardImmagine:Commons-logo.svg Fonte:: http://it.wikipedia.org/w/index.php?title=File:Commons-logo.svg Licenza: logo Autori:: SVG version was created by User:Grunt and cleaned up by3247, based on the earlier PNG version, created by Reidab.File:Buffer ANSI.svg Fonte:: http://it.wikipedia.org/w/index.php?title=File:Buffer_ANSI.svg Licenza: Public Domain Autori:: Inductiveload

Licenza 22

LicenzaCreative Commons Attribution-Share Alike 3.0 Unported//creativecommons.org/licenses/by-sa/3.0/