Logique linéaire
Rien à voir ici avec celle de J.Y. Girard.
Je me demande depuis un moment s'il est possible de faire du calcul propositionnel avec seulement des applications affines et de la partie entière.
Par exemple : $a\wedge b$ peut être vu comme $ent(a/2+b/2)$
Du multiplicatif devient par "magie" du linéaire.
Quelqu'un a déjà vu ça ?
Merci
Je me demande depuis un moment s'il est possible de faire du calcul propositionnel avec seulement des applications affines et de la partie entière.
Par exemple : $a\wedge b$ peut être vu comme $ent(a/2+b/2)$
Du multiplicatif devient par "magie" du linéaire.
Quelqu'un a déjà vu ça ?
Merci
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
La difficulté c'est de rester affine et de n'utiliser qu'un seul opérateur $ent$.
$\newcommand{\Ent}[1]{ent \left (#1 \right )}$
Il faudrait que cette opération soit associative, comme l'est $\wedge$ dans une algèbre de Boole.
Mais $$\op 0 {\op 1 2} = \op 0 {\Ent {\frac 3 2}} = \Ent {\frac 1 2} = 0$$ et
$$\op {\op 0 1} 2 = \op {\Ent {\frac 1 2}} 2 = \op 0 2 = \Ent 1 = 1$$.
D'où le "faudrait".
Si on reste sur $\{0,1\}$ on retrouve bien AND mais ce n'était pas clair dans la demande de Serge. Pour NOT on peut prendre $x\mapsto ent(1-x/2)$ au passage.
La motivation est calculatoire. Un ordinateur calcule vite des transformations affines et sait vite lire le $i$ ème bit d'un registre.
et le $a\vee b$ devient $(1+a+b)_2$
et $\lnot a$ devient $(1+a)_1$
vous voyez ?
On voit surtout que tu es redescendu au niveau du bit. Tu es mûr pour passer d'une seule opération de $2^n$ cas à $2^n$ opérations de 1 cas.
J'avais montré dans un papier que toute opération linéaire sur un corps quelconque de $K^n$ dans $K^n$ se calcule par $2n-1$ opérations linéaires sans utiliser d'autres mémoires que les $n$ éléments d'entrée.
Exemple classique : l'échange de deux nombres $A,B$.
Cela se fait par $A:=A+B, B:=A-B, A:=A-B$. Pas besoin d'une mémoire "tampon".
Le problème est combinatoire. Or les deux idées que tu soulèves dans cette discussion ne règle pas la combinaison.
1 XOR 0=1 donc $a+b \geq 1$.
De même 0 XOR 1=1, donc $a+c \geq 1$.
Donc $2a+b+c \geq 2$.
Or $-a>-1$, donc en additionnant, on obtient $a+b+c>1$, donc on aurait 1 XOR 1=1, or 1 XOR 1=0.
Le $a\oplus b$ est simplement $(a+b)_1$
donc en effet, elle est invariante par rapport au signe de $n$.