Logique linéaire — Les-mathematiques.net The most powerful custom community solution in the world

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

Réponses

  • Attention : il ne suffit pas de réaliser le NAND ou le NOR pour tout avoir comme classiquement.

    La difficulté c'est de rester affine et de n'utiliser qu'un seul opérateur $ent$.
  • j'avais écrit un truc sur ce sujet il y a qq années.
    nor.pdf 110.1K
  • $\newcommand{\op}[2]{ent \left (\frac{#1} 2 + \frac{#2} 2 \right)}$
    $\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$$.
  • Pas il faudrait.....mais il suffirait.
  • serge_burckel a écrit:
    Pas il faudrait.....mais il suffirait.
    Si une loi de composition interne$\wedge$ sur un ensemble $E$ est telle qu'il existe mettons une fonction $\neg: E \to E$ telle que $(E,\neg,\wedge)$ est une algèbre de Boole alors $\wedge$ est associative (par définition de ce qu'est une algèbre de Boole).

    D'où le "faudrait".
  • Foys: est-ce que l'on n'a pas $c=0$ ou $c=1$ (faux ou vrai) dans $ent(a/2+ent(b/2+c/2)/2)$ or tu as choisi $c=2$ ?
  • Cette fonction est censée être définie sur tous les entiers, non?
    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.
  • pour NOT...on peut prendre $1-x$
  • En fait, c'est plus intéressant d'oublier la partie entière et de considérer ce qui peut être lu en position $i$ dans un registre.

    La motivation est calculatoire. Un ordinateur calcule vite des transformations affines et sait vite lire le $i$ ème bit d'un registre.
  • Dans ce nouveau contexte, le $a\wedge b$ devient $(a+b)_2$ puisque $(a+b)$ vaut respectivement $00,01,01,10$ pour $ab=00,01,10,11$

    et le $a\vee b$ devient $(1+a+b)_2$

    et $\lnot a$ devient $(1+a)_1$

    vous voyez ?
  • Bonjour

    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.
  • Le but est de faire des calculs par applications affines et autres opérations simples pour des processeurs.

    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".
  • L'ennemi mute. Tu peux toujours arriver à ton objectif, avant que le $2^n$ te revienne dans la figure que ce soit des secondes, des opérations, des opérandes, des chiffres binaires dans la mémoire.

    Le problème est combinatoire. Or les deux idées que tu soulèves dans cette discussion ne règle pas la combinaison.
  • Serge: comment réalises-tu le "ou exclusif" sous forme de $x,y \mapsto ent(a+bx+cy)$ avec $x,y=0$ ou $1$, et $a,b,c \in \R$ ?
  • En effet, 0 XOR 0=0, donc $a<1$.
    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.
  • Oui....la partie entière ne suffit pas. D'où l'usage des bits qui la généralise.

    Le $a\oplus b$ est simplement $(a+b)_1$
  • Comment réalise-t-on la relation ternaire suivante sous la forme de $x,y,z \mapsto (a+bx+cy+dz)_k$ ?
    000  -> false 
    100  -> true 
    010  -> true
    110  -> false 
    001  -> false
    101  -> false
    011  -> false
    111  -> false
    
    Je ne sais pas, peut-être c'est possible.
  • Par exemple avec $(5x+5y-2z)_3$
  • Pour x=0, y=0, z=1, on obtient (-2)3. Si tu représentes en complément à 2, on obtient 1. Alors qu'on voudrait 0. Ou alors tu prends la valeur absolue ? Ou alors tu considères 1 comme false ? Ou finalement, je n'ai pas compris cette notation "parenthèse".
  • Voici comment je définis la représentation binaire d'un nombre $n$ sur $N$ bits.....classique avec de la division entière en base 2.
    bin:=proc(n,N) local a,l;
    l:=[];a:=n;while nops(l)<N do l:=[op(l),a mod 2];a:=trunc(a/2);od:
    l;end:
    
    

    donc en effet, elle est invariante par rapport au signe de $n$.
  • Serge: en effet, le programme que j'avais écrit ne considérait que des nombres entiers positifs dans le cas des fonctions de forme $(a+bx+cy+dz)_k$
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!