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
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.
-
$\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$$.Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$. -
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).serge_burckel a écrit:Pas il faudrait.....mais il suffirait.
D'où le "faudrait".Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$. -
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.Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$. -
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.Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé. -
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.Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé. -
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".Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
-
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.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.8K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 30
+25 Invités