Circuito booliano: diferenças entre revisões

← Ver a alteração anterior Ver a alteração posterior →

Conteúdo apagado Conteúdo adicionado

Em linha

Revisão das 15h39min de 28 de abril de 2013

Na teoria da complexidade computacional e complexidade de circuito, um Circuito booleano é um modelo matemático para circuitos lógicos digitais. Uma linguagem formal pode ser decidida por uma família de circuitos Booleanos, um circuito para cada comprimento de entrada possível. Circuitos booleanos também são usados em modelos formais para lógica combinacional em eletrônica digital.

Circuitos booleanos são definidos em termos das portas lógicas que contêm. Por exemplo, um circuito pode conter as funções binárias das portas AND e OR, e função unária da porta NOT, ou ser inteiramente descrita por portas binárias NAND. Cada porta corresponde a alguma função Booleana que recebe um número fixo de bits como input e devolve um único bit como output.

Circuitos Booleanos provêm um modelo para muitos componentes digitais usados em engenharia da computação, incluindo multiplexadores, adicionadores, e unidades lógicas e aritméticas.

Definição formal

Em uma definição formal de circuitos Booleanos, Vollmer começou definindo um conjunto base B de funções Booleanas, correspondendo as portas permissíveis no modelo de circuito. Um circuito Booleano sobre uma base B, com n entradas e m saídas, é então definida como um grafo acíclico dirigido finito. Cada vértice corresponde ou à função base ou a uma das entradas, e existe um conjuto de exatamente m nós que são rotulados como saídas.^[1] As arestas também devem ter alguma ordenação, para distinguir entre diferentes argumentos da mesma função Booleana.^[2]

Uma base comum para circuitos Booleanos é o conjunto de {AND, OR, NOT}, de qual todas as outras funções Booleanas podem ser construídas.

Complexidade computacional

Avaliação de um circuito

O Problema do Valor do Circuito, que é o problema de se computar a saída de um circuito Booleano com dadas strings de entrada, é um problema de decisão P-completo.^[3] Portanto, esse problema é considerado ser "inerentemente sequencial" no sentido de que provavelmente não há um algoritmo eficiente, altamente paralelo que resolve o problema.

Medidas de complexidade

Várias importantes medidas de complexidade podem ser definidas em circuitos Booleanos, incluindo profundidade do circuito, tamanho do circuito e número de alternações entre portas AND e OR. Por exemplo, a complexidade de tamanho de um circuito Booleano é o número de portas.

Classes de complexidade

Várias importantes classes de complexidade foram definidas em termos de circuitos Booleanos, incluindo NC. NC é definida como o conjunto de funções Booleanas que podem ser decididas por circuitos Booleanos uniformes de tamanho polinomial e profundidade polilogarítmica. Aqui a palavra uniforme significa que tem que haver alguma condição na família do circuito tal que a descrição do circuito possa ser computada a partir do número de entradas do circuito apenas.

Veja também

Notas de rodapé

↑ Vollmer 1999, p. 8.
↑ Vollmer 1999, p. 9.
↑ S. Arora and B. Barak. Computational complexity, a modern approach. [S.l.: s.n.] p. 119

Referências

Vollmer, Heribert (1999). Introduction to Circuit Complexity. Berlin: Springer. ISBN 3-540-64310-9

[1] Vollmer 1999, p. 8.

[2] Vollmer 1999, p. 9.

[arorabarak-3] S. Arora and B. Barak. Computational complexity, a modern approach. [S.l.: s.n.] p. 119

[1]

[2]

[3]

@@ Linha 1: / Linha 1: @@
-Na [[teoria da complexidade computacional]] e [[complexidade de circuito]], um '''Circuito booleano''' é um [[modelo de computação|modelo]] matemático para [[eletrônica digital||circuitos lógicos digitais]]. Uma [[linguagem formal]] pode ser decidida por uma família de circuitos Booleanos, um circuito para cada comprimento de entrada possível. Circuitos booleanos também são usados em modelos formais para [[lógica combinacional]] em eletrônica digital.
+Na [[teoria da complexidade computacional]] e [[complexidade de circuito]], um '''Circuito booleano''' é um [[modelo de computação|modelo]] matemático para [[eletrônica digital|circuitos lógicos digitais]]. Uma [[linguagem formal]] pode ser decidida por uma família de circuitos Booleanos, um circuito para cada comprimento de entrada possível. Circuitos booleanos também são usados em modelos formais para [[lógica combinacional]] em eletrônica digital.
-Circuitos booleanos são definidos em termos das [[porta lógica|portas lógicas]] que contém. Por exemplo, um circuito pode conter as [[função binária|funções binárias]] das portas [[porta AND|AND]] e [[porta OR|OR]], e [[função unária]] da porta [[porta NOT|NOT]], ou ser inteiramente descrita por portas binárias [[porta NAND|NAND]]. Cada porta corresponde a alguma [[função Booleana]] que recebe um número fixo de [[bit]]s como input e devolve um único bit como output.
+Circuitos booleanos são definidos em termos das [[porta lógica|portas lógicas]] que contêm. Por exemplo, um circuito pode conter as [[função binária|funções binárias]] das portas [[porta AND|AND]] e [[porta OR|OR]], e [[função unária]] da porta [[porta NOT|NOT]], ou ser inteiramente descrita por portas binárias [[porta NAND|NAND]]. Cada porta corresponde a alguma [[função Booleana]] que recebe um número fixo de [[bit]]s como input e devolve um único bit como output.
-Circuitos Booleanos provém um modelo para muitos componentes digitais usados em [[engenharia da computação]], incluindo [[multiplexador]]es, [[adicionador(eletrônica)|adicionador]]es, e [[unidade lógica e aritmética|unidades lógicas e aritméticas]].
+Circuitos Booleanos provêm um modelo para muitos componentes digitais usados em [[engenharia da computação]], incluindo [[multiplexador]]es, [[adicionador(eletrônica)|adicionador]]es, e [[unidade lógica e aritmética|unidades lógicas e aritméticas]].
 == Definição formal ==