Application (mathématiques)/Application caractéristique

Nous avons défini [[../Définitions|au premier chapitre]], pour toute partie A d'un ensemble E, la [[../Définitions#Exemples d’applications|fonction indicatrice de A]] (ou « application caractéristique de A ») :

$\begin{array}{ccccc}{\chi }_A& :& E& \to & \{0,1\}\\ & & x& \mapsto & \{\begin{array}{ccc}1& \text{si }& x\in A\\ 0& \text{si }& x\notin A.\end{array}\end{array}$.

La bijection $\chi$

Grimpons à l'étage supérieur : l'ensemble E restant fixe, faisons maintenant varier A dans l'ensemble $𝒫(E)$ des parties de $E$.

Traduction arithmétique des opérations ensemblistes

On peut combiner des fonctions à valeurs entières en utilisant les opérations arithmétiques usuelles. Le résultat est une fonction à valeurs entières. Mais si les fonctions de départ ne prennent que les valeurs 0 ou 1 alors, certaines combinaisons arithmétiques produisent une fonction qui, elle aussi, ne prend que ces deux valeurs. En particulier : Modèle:Proposition

Transformation des formules entières en formules modulo 2

Identifions l’ensemble {0, 1} à l'ensemble des deux classes de congruence modulo 2 (0 = Pair, 1 = Impair) et munissons cet ensemble de l'addition et de la multiplication correspondantes. Sur {0, 1}, la multiplication modulo 2 est la même que la multiplication usuelle, mais l'addition modulo 2 correspond au OU exlusif, ou XOR, noté ici $\oplus$ :

$\oplus$	0	1
0	0	1
1	1	0

Avec ces nouvelles opérations, par construction, n'importe quelle combinaison de fonctions à valeurs dans {0, 1} sera automatiquement à valeurs dans {0, 1}. Les formules précédentes deviennent :