Wikipédia:Tradução/Circuito Booleano
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[editar código-fonte]
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[editar código-fonte]
Avaliação de um circuito[editar código-fonte]
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[editar código-fonte]
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[editar código-fonte]
Ver artigo principal: Complexidade de circuito#Classes de complexidadeVá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[editar código-fonte]
Notas de rodapé[editar código-fonte]
Referências[editar código-fonte]
- Vollmer, Heribert (1999). Introduction to Circuit Complexity. Berlin: Springer. ISBN 3-540-64310-9
