Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Circuit booléen
Résumé
vignette|Exemple circuit booléen à deux entrées et une sortie. Le circuit contient 3 portes logique.
En théorie de la complexité, un circuit booléen est un modèle de calcul constitué de portes logiques (fonctions logiques) reliées entre elles. C'est une façon de représenter une fonction booléenne.
Un circuit booléen peut être utilisé pour reconnaître un langage formel, c'est-à-dire décider si un mot appartient ou non à un langage particulier. Les caractéristiques des circuits qui reconnaissent un langage permettent de définir (ou redéfinir) des classes de complexité.
Les circuits booléens sont un modèle utilisé en génie informatique notamment pour la conception des unités arithmétiques et logiques et en informatique théorique notamment pour établir des bornes inférieures.
Un circuit booléen est un graphe orienté acyclique (DAG) fini connexe dont les feuilles sont les entrées et l'unique racine est la sortie. Les sommets sont les portes, généralement des portes ET, OU et NON. On peut évaluer la valeur de sortie récursivement à partir des feuilles : pour une porte "ET" par exemple, si les entrées sont positives la sortie sera positive sinon la sortie est négative.
Une formule de la logique propositionnelle est un cas particulier de circuit booléen qui est un arbre.
On peut aussi modéliser des circuits par des programmes straight-line : ce sont des programmes sans conditionnelles et sans boucles. Par exemple, le circuit booléen de l'illustration est équivalent au programme straight-line suivant, en appelant x1 et x2 les entrées, et en introduisant les variables y1, y2, y3 pour les trois portes logique :
y1 := x1 ou x2
y2 := non x2
y3 := y1 et y2
Les circuits classiques décident des langages codés en binaire : le premier bit du mot est la première entrée Le mot est accepté si et seulement si la sortie du circuit est vrai.
Comme un circuit ne permet de reconnaître que des mots de même tailles, on parle généralement de famille de circuits , où reconnaît les mots du langage de taille .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.