X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/d69000ebda300fc836232f34cebb88ddfce4ac98..01003216d61845263ad195f3ecf7334817d60407:/annexesccg.tex?ds=inline diff --git a/annexesccg.tex b/annexesccg.tex index 257f86c..bbfc12d 100644 --- a/annexesccg.tex +++ b/annexesccg.tex @@ -23,7 +23,7 @@ arcs dont ${\mathsf{N}}$ est soit l'extrémité, soit l'origine (et dans ce dern cas, les arcs sont des boucles sur ${\mathsf{N}}$). \end{lemma} -\begin{Proof} +\begin{proof} Supposons que $G(f^{\alpha})$ possède un arc de $j$ vers $i$ de signe $s$. Par définition, il existe un sommet $x\in\Bool^{{\mathsf{N}}-1}$ tel que $f^{\alpha}_{ij}(x)=s$, et puisque @@ -42,13 +42,13 @@ Ainsi $f_{ij}(x,\alpha)$ est égal à $s$. On a donc aussi $f^{\alpha}_{ij}(x)=s$. Ainsi $G(f^\alpha)$ possède un arc arc de $j$ vers $i$ de signe $s$. -\end{Proof} +\end{proof} \begin{lemma}\label{lemma:iso} Les graphes $\textsc{giu}(f^\alpha)$ et $\textsc{giu}(f)^\alpha$ sont isomorphes. \end{lemma} -\begin{Proof} +\begin{proof} Soit $h$ la bijection de $\Bool^{{\mathsf{N}}-1}$ vers $\Bool^{{\mathsf{N}}-1}\times \{\alpha\}$ définie par $h(x)=(x,\alpha)$ pour chaque $x\in\Bool^{{\mathsf{N}}-1}$. @@ -56,13 +56,13 @@ On voit facilement que $h$ permet de définir un isomorphisme entre $\textsc{giu}(f^\alpha)$ et $\textsc{giu}(f)^\alpha$: $\textsc{giu}(f^\alpha)$ possède un arc de $x$ vers $y$ si et seulement si $\textsc{giu}(f)^\alpha$ a un arc de $h(x)$ vers $h(y)$. -\end{Proof} +\end{proof} On peut alors prouver le théorème: \thAdrien* -\begin{Proof} +\begin{proof} La preuve se fait par induction sur ${\mathsf{N}}$. Soit $f$ une fonction de $\Bool^{\mathsf{N}}$ dans lui-même et qui vérifie les hypothèses du théorème. @@ -122,7 +122,7 @@ Puisque la valeur de $f_{\mathsf{N}}(x)$ on a $f_{\mathsf{N}}(x')=f_{\mathsf{N}}(x)=1\neq x'_{\mathsf{N}}$ (resp. $f_{\mathsf{N}}(y')=f_{\mathsf{N}}(y)=0\neq y'_{\mathsf{N}}$). Ainsi la condition ($*$) est établie, et le théorème est prouvé. -\end{Proof} +\end{proof}