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.
Disjonction logiqueLa disjonction logique, ou disjonction non exclusive, de deux assertions est une façon d'affirmer qu'au moins une de ces deux assertions est vraie (la première, la deuxième, ou les deux). Dans le langage logique ou mathématique, et dans les domaines techniques qui l'emploient, elle se traduit par le OU logique, un opérateur logique dans le calcul des propositions. La proposition obtenue en reliant deux propositions par cet opérateur s'appelle également leur disjonction ou leur somme logique.
Démonstration automatique de théorèmesLa démonstration automatique de théorèmes (DAT) est l'activité d'un logiciel qui démontre une proposition qu'on lui soumet, sans l'aide de l'utilisateur. Les démonstrateurs automatiques de théorème ont résolu des conjectures intéressantes difficiles à établir, certaines ayant échappé aux mathématiciens pendant longtemps ; c'est le cas, par exemple, de la , démontrée en 1996 par le logiciel EQP.
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.
Problème SATvignette|Une instance du Sudoku peut être transformée en une formule de logique propositionnelle à satisfaire. Une assignation des variables propositionnelles donne une grille complétée. En informatique théorique, le problème SAT ou problème de satisfaisabilité booléenne est le problème de décision, qui, étant donné une formule de logique propositionnelle, détermine s'il existe une assignation des variables propositionnelles qui rend la formule vraie. Ce problème est important en théorie de la complexité.
Connecteur logiqueEn logique, un connecteur logique est un opérateur booléen utilisé dans le calcul des propositions. Comme dans toute approche logique, il faut distinguer un aspect syntaxique et un aspect sémantique. D'un point de vue syntaxique, les connecteurs sont des opérateurs dans un langage formel pour lesquels un certain nombre de règles définissent leur usage, au besoin complétées par une sémantique. Si l'on se place dans la logique classique, l'interprétation des variables se fait dans les booléens ou dans une extension multivalente de ceux-ci.
ThéorèmeEn mathématiques et en logique, un théorème (du grec théorêma, objet digne d'étude) est une assertion qui est démontrée, c'est-à-dire établie comme vraie à partir d'autres assertions déjà démontrées (théorèmes ou autres formes d'assertions) ou des assertions acceptées comme vraies, appelées axiomes. Un théorème se démontre dans un système déductif et est une conséquence logique d'un système d'axiomes. En ce sens, il se distingue d'une loi scientifique, obtenue par l'expérimentation.
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.
Unificationvignette|Unifier deux termes, c'est les rendre identiques en remplaçant les variables. En informatique et en logique, l'unification est un processus algorithmique qui, étant donnés deux termes, trouve une substitution qui appliquée aux deux termes les rend identiques. Par exemple, et peuvent être rendus identiques par la substitution et , qui donne quand on l'applique à chacun de ces termes le terme .
Syntaxe (logique)alt=Ce diagramme montre les entités syntaxiques qui peuvent être construits à partir des langages formels. Les symboles et les chaînes de symboles peuvent être divisés en formules bien formées. Un langage formel peut être considéré comme identique à l'ensemble de ses formules bien formées. L'ensemble des formules bien formées peut être divisé en théorèmes et non-théorèmes.|vignette|Ce diagramme montre les entités syntaxiques qui peuvent être construits à partir des langages formels.
