Circuito booleano: differenze tra le versioni

Versione delle 08:05, 19 feb 2013

Versione attuale delle 12:17, 8 feb 2024

(22 versioni intermedie di 8 utenti non mostrate)

Riga 1:

Un '''Circuitocircuito Booleanobooleano''' è un [[modello matematico]] di [[computazione]] usato nello studio della [[teoria della complessità computazionale]]. Questi circuiti sono principalmente oggetto di studi nella [[complessità dei circuiti]] e sono dei tipi speciali di [[circuiti]]; un [[linguaggio formale]] può essere deciso da una famiglia di circuiti Booleanibooleani, un circuito per ogni possibile lunghezza di input. In aggiunta, essi sono usati come modello formale per [[logica combinatoria]] in [[elettronica digitale]].

I circuiti Booleanibooleani sono definiti in termini di [[porte logiche|porte]] che essi contengono. Ad esempio, un circuito potrebbe contenere porte AND e OR [[funzioni binarie|binarie]] e porte NOT [[unarie]], o essere interamente descritti da [[porte NAND]] binarie. Ogni porta corrisponde a qualche [[funzione Booleanabooleana]] che prende ''k'' bitsbit di input e invia in output un singolo bit.

==Definizione formale==

Diverse importanti misure di complessità possono essere definite su circuiti Booleani, incluso profondità di circuito, dimensione di circuito o numero di alternanze. In una famiglia di circuiti, consideriamo la complessità (misurata in dimensione del circuito), per esempio, come la funzione di n che da la dimensione del circuito che decide l'input di lunghezza n.

Nel dare una definizione formale di circuiti Booleanibooleani, [[Heribert Vollmer|Vollmer]] comincia definendo un setinsieme base di funzioni Booleanebooleane ''B'', corrispondenti alle porte accettabili nel modello del circuito. Un circuito Booleanobooleano su una base ''B'', con ''n'' input e ''m'' output, è definita come un [[grafo aciclico diretto]] finito. Ogni vertice corrisponde o ad una funzione base o ad un input, e c'è un set di esattamente ''m'' nodi che sono etichettati come output.<ref>Vollmer 1999, p. 8.</ref> Gli archi devono anche essere in qualche modo ordinati, per distinguere tra differenti argomenti per la stessa funzione Booleanabooleana.<ref>Vollmer 1999, p. 9.</ref>

== Complessità computazionale ==

Diverse importanti classi di complessità sono definite in termini di circuiti Booleani, incluso [[NC (complessità)|NC]]. NC è definita essere il set di [[funzioni Booleane]] che possono essere decise da circuiti Booleani uniformi di dimensione polinomiale e profondità polilogaritmica. Qui, la parola ''uniforme'' significa che deve esserci qualche condizione sulla famiglia di circuiti di modo che una descrizione di un circuito può essere fatta dal suo indice, n.

=== Valutazione di un circuito ===

Il problema ''CIRCUIT-EVAL'' prende come input la descrizione di un circuito Booleanobooleano e un'assegnazione di [[valore di verità]] alle variabili del circuito, e accetta il test solo se il circuito restituisce vero. ''CIRCUIT-EVAL'' è [[P-completo]].<ref>S. Arora, B.& Barak, ''Computational complexity2009, a modern approach'', pagep. 119.</ref>

=== Misure di complessità ===

==Definizione formale==

{{vedi anche|Complessità dei circuiti}}

Nel dare una definizione formale di circuiti Booleani, [[Heribert Vollmer|Vollmer]] comincia definendo un set base di funzioni Booleane ''B'', corrispondenti alle porte accettabili nel modello del circuito. Un circuito Booleano su una base ''B'', con ''n'' input e ''m'' output, è definita come un [[grafo aciclico diretto]] finito. Ogni vertice corrisponde o ad una funzione base o ad un input, e c'è un set di esattamente ''m'' nodi che sono etichettati come output.<ref>Vollmer 1999, p. 8.</ref> Gli archi devono anche essere in qualche modo ordinati, per distinguere tra differenti argomenti per la stessa funzione Booleana.<ref>Vollmer 1999, p. 9.</ref>

DiverseVarie importanti [[Misura di complessità|misure di complessità]] possono essere definite susui circuiti Booleanibooleani, inclusocomprese la profondità didel circuito, la dimensione didel circuito oe il numero di alternanze. Intra unaporte famigliaAND die circuiti,porte consideriamo la complessità (misurata in dimensione del circuito),OR. perPer esempio, come la funzionecomplessità di ndimensione chedi da la dimensione delun circuito chebooleano decideè l'inputil dinumero lunghezzadelle nporte.

== ValutazioneClassi di un circuitocomplessità ==

{{Torna a|Complessità dei circuiti#Classi di complessità{{!}}Classi di complessità dei circuiti}}

Il problema ''CIRCUIT-EVAL'' prende come input la descrizione di un circuito Booleano e un'assegnazione di valore di verità alle variabili del circuito, e accetta il test solo se il circuito restituisce vero. ''CIRCUIT-EVAL'' è [[P-completo]].<ref>S. Arora, B. Barak, ''Computational complexity, a modern approach'', page 119</ref>

DiverseVarie importanti classi di complessità sono definite in termini di circuiti Booleanibooleani, inclusocompreso [[NC (complessità)|NC]]. NC è definitadefinito esserecome ill'insieme set didelle [[Funzione booleana|funzioni Booleanebooleane]] che possono essere decise da circuiti Booleanibooleani uniformi di dimensione polinomiale e profondità polilogaritmica. Qui, la parola ''uniforme'' significa che ci deve esserciessere una qualche condizione sulla famiglia di circuiti diin modo che unala descrizione di un circuito puòpossa essere fattacomputata soltanto dal suonumero indice,degli ninput al circuito.

== Note ==

<references/>

== Bibliografia ==

* {{cita libro | cognome = Vollmer | nome = Heribert | titolo = Introduction to Circuit Complexity | url = https://archive.org/details/introductiontoci0000voll | anno = 1999 | editore = Springer | città = Berlino | isbn = 3-540-64310-9}}

* {{cita libro | cognome1 = Arora | nome1 = Sanjeev | cognome2 = Barak | nome2 = Boaz | titolo = Computational Complexity: A Modern Approach | anno = 2009 | editore = Cambridge University Press | città = New York | isbn = 0-521-42426-7}}

== Voci correlate ==

* [[Algebra di Boole]]

* [[Porta logica]]

{{Portale|informatica}}

[[Categoria:Teoria della computazione]]

[[Categoria:Logica nell'informatica]]