vignette|Arbre de décision binaire
Une fonction booléenne est une fonction prenant en entrée une liste de bits et donnant en sortie un unique bit.
Les fonctions booléennes sont très utilisées en informatique théorique, notamment en théorie de la complexité et en cryptologie (par exemple dans les boîtes-S et les chiffrements par flot -- fonction de filtrage ou de combinaison de registres à décalage à rétroaction linéaire).
Une fonction booléenne est une fonction de dans où désigne le corps fini à 2 éléments. Un exemple de fonction booléenne est la fonction parité, dont la sortie dépend de la parité du nombre de 1 dans l'entrée. Une fonction booléenne peut être représentée par un circuit booléen.
Les corps finis et les polynômes interpolateurs de Lagrange conduisent rapidement à une propriété fondamentale des fonctions booléennes : la représentation dite « forme algébrique normale » (algebraic normal form ou ANF).
Toute fonction booléenne peut s'écrire comme un polynôme en variables à coefficients dans . Cependant, différents polynômes de donnent la même fonction. Par exemple, et donnent bien la même valeur lorsqu'ils sont évalués sur un élément de . Pour obtenir une représentation unique, il faut considérer les éléments de l'anneau quotient, soit :
Autrement dit, une fonction booléenne peut être représentée de manière unique par un polynôme de la forme :
( est une suite d'éléments de et ).
On pose fréquemment , et , permettant l'écriture compacte :
La notion de degré d'une fonction booléenne est alors évidente, il s'agit du degré maximal des monômes de son ANF.
Exemple de forme algébrique normale sur :
Les fonctions de degré 1 sont appelées les fonctions affines. En fait, ce sont des formes affines de l'espace vectoriel — vu comme espace sur le corps .
Ce sont les fonctions les plus simples, hormis les constantes. Il a fini par apparaître que « ressembler » à une fonction linéaire était une propriété pouvant être exploitée en cryptanalyse.
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.
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.
vignette|Arbre de décision binaire Une fonction booléenne est une fonction prenant en entrée une liste de bits et donnant en sortie un unique bit. Les fonctions booléennes sont très utilisées en informatique théorique, notamment en théorie de la complexité et en cryptologie (par exemple dans les boîtes-S et les chiffrements par flot -- fonction de filtrage ou de combinaison de registres à décalage à rétroaction linéaire). Une fonction booléenne est une fonction de dans où désigne le corps fini à 2 éléments.
En 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.
In computational complexity we study the computational resources needed to solve problems and understand the relation between different types of computation.This course advances the students knowle
We introduce formal verification as an approach for developing highly reliable systems. Formal verification finds proofs that computer systems work under all relevant scenarios. We will learn how to u
Hardware compilation is the process of transforming specialized hardware description languages into circuit descriptions, which are iteratively refined, detailed and optimized. The course presents a
Explore une synthèse réactive symbolique efficace à l'aide de diagrammes de décision binaires pour représenter compactement les fonctions et ensembles booléens.
Stream ciphers are fast cryptographic primitives to provide confidentiality of electronically transmitted data. They can be very suitable in environments with restricted resources, such as mobile devi