Forme normale algébriqueEn logique mathématique, la forme normale algébrique d'une fonction booléenne est une formule qui est un ou exclusif de conjonctions de variables propositionnelles ; par exemple 1 ⊕ a ⊕ b ⊕ ab ⊕ abc (1 correspond à la conjonction vide). Toute fonction booléenne admet une unique forme normale algébrique de taille minimale. Pour construire une formule normale algébrique, on part d'une forme normale disjonctive. On remplace ensuite la négation de a par (1 ⊕ a). On applique ensuite les règles de distributivité et d'absorption (a ⊕ a) = 0.
Algèbre de Boole (logique)Lalgèbre de Boole, ou calcul booléen, est la partie des mathématiques qui s'intéresse à une approche algébrique de la logique, vue en termes de variables, d'opérateurs et de fonctions sur les variables logiques, ce qui permet d'utiliser des techniques algébriques pour traiter les expressions à deux valeurs du calcul des propositions. Elle fut lancée en 1854 par le mathématicien britannique George Boole. L'algèbre de Boole trouve de nombreuses applications en informatique et dans la conception des circuits électroniques.
Canonical normal formIn Boolean algebra, any Boolean function can be expressed in the canonical disjunctive normal form (CDNF) or minterm canonical form, and its dual, the canonical conjunctive normal form (CCNF) or maxterm canonical form. Other canonical forms include the complete sum of prime implicants or Blake canonical form (and its dual), and the algebraic normal form (also called Zhegalkin or Reed–Muller). Minterms are called products because they are the logical AND of a set of variables, and maxterms are called sums because they are the logical OR of a set of variables.
Logic optimizationLogic optimization is a process of finding an equivalent representation of the specified logic circuit under one or more specified constraints. This process is a part of a logic synthesis applied in digital electronics and integrated circuit design. Generally, the circuit is constrained to a minimum chip area meeting a predefined response delay. The goal of logic optimization of a given circuit is to obtain the smallest logic circuit that evaluates to the same values as the original one.
Diagramme de Vennvignette|Diagramme de Venn montrant quels glyphes en majuscules sont partagés par l'alphabet grec, latin et russe. Un diagramme de Venn (également appelé diagramme logique) est un diagramme qui montre toutes les relations logiques possibles dans une collection finie de différents ensembles. Les diagrammes de Venn ont été conçus autour de 1880 par John Venn. Ils sont utilisés pour enseigner la théorie des ensembles élémentaires, ainsi que pour illustrer des relations simples en probabilité, logique, statistiques, linguistique et en informatique.
Table de véritéUne table de vérité (parfois appelée fonction de vérité) est une table mathématique utilisée en logique classique — en particulier le calcul propositionnel classique et l'algèbre de Boole — pour représenter de manière sémantique des expressions logiques et calculer la valeur de leur fonction relativement à chacun de leurs arguments fonctionnels (chaque combinaison de valeur assumée par leurs variables logiques).
Diagramme de décision binaireEn informatique, un graphe de décision binaire ou diagramme de décision binaire (ou BDD pour Binary Decision Diagram en anglais) est une structure de données utilisée pour représenter des fonctions booléennes, ou des questionnaires binaires. On utilise les BDD pour représenter des ensembles ou des relations de manière compacte / compressée. Les diagrammes de décision binaires sont utilisés par les programmes de conception assistée par ordinateur (CAO / CAD) pour générer des circuits (synthèse logique), et dans la vérification formelle.
Forme normale conjonctiveEn logique booléenne et en calcul des propositions, une formule en forme normale conjonctive ou FNC (en anglais, Conjunctive Normal Form, Clausal Normal Form ou CNF) est une conjonction de clauses, où une clause est une disjonction de littéraux. Les formules en FNC sont utilisées dans le cadre de la démonstration automatique de théorèmes ou encore dans la résolution du problème SAT (en particulier dans l'algorithme DPLL). Une expression logique est en FNC si et seulement si elle est une conjonction d'une ou plusieurs disjonction(s) d'un ou plusieurs littéraux.
Forme normale disjonctiveEn logique booléenne ou en calcul des propositions, une forme normale disjonctive ou FND (en anglais, disjunctive normal form ou DNF) est une normalisation d'une expression logique qui est une disjonction de clauses conjonctives. Elle est utilisée dans la démonstration automatique de théorèmes. Une expression logique est en FND si et seulement si elle est une disjonction d'une ou plusieurs conjonctions d'un ou plusieurs littéraux. Tout comme dans une forme normale conjonctive (FNC), les seuls opérateurs dans une FND sont le et logique, le ou logique et la négation.
AdditionneurUn additionneur est un circuit logique permettant de réaliser une addition. Ce circuit est très présent dans les ordinateurs pour le calcul arithmétique mais également pour le calcul d'adresses, d'indice de tableau dans le processeur. On dénombre deux types d'additionneurs : parallèle (circuit combinatoire) et série (circuit séquentiel). Dans la classe des additionneurs parallèles, nous décrirons ici ceux à propagation de retenue et ceux à retenue anticipée.
