Tables de vérité (combinatoire)

Il faut être plus précis. En effet ton exemple utilise à la fois une loi, et plusieurs variables, genre :

$a \times b = (a \circ b ) + (b \ circ b)$

Accepterais-tu $a \times b = (a \circ b \circ c) + (a \circ c)$ par exemple ?

Je pense que sans plus d'hypothèses, on ne peut pas trop avancer.

Amicalement
Volny

salut,
une idée un peu primitive, sorte de généralisation des formes normales disjonctives :
je considère les représentations binaires des k éléments,
et les (log_2 k)^2 fonctions "projections" pij(x) = y
avec ième bit de y = jème bit de x (de gauche à droite), les autres 0.
Ex:
f(a,b) avec k=3 donnée par
a b f
00 00 10
00 01 00
00 10 01
01 00 10
01 01 11
01 10 00
10 00 01
10 01 01
10 10 11

f = p11 (¬p11(a).¬p12(a).¬p11(b).¬p12(b) ) v
v p11 (¬p11(a).p12(a).¬p11(b).¬p12(b) ) v
v .... v
v p22 (¬p21(a).¬p22(a).p21(b).¬p22(b) ) v
v p22 (¬p21(a).p22(a).¬p21(b).p22(b) ) v
v ....

On remplace les ¬, v, . par le nand (ou le nor) et il suffit donc de (log_2 k)^2 lois unaires et une binaire. (si tu tiens à des lois binaires seulement, tu définis qij(x,x) = pij(x))

on peut bien sûr encore diminuer le nombre de ces fonctions auxiliaires :

qi(x) =ième bit de x (ex : q1(0) = 0, q1(1) = 0, q1(2) = 1)
r(x) = rotation circulaire d'un bit à gauche par ex.

pij(x) = r(r(...(qj(x))) (j-i ème itérée si i<= j, sinon ...)

On arrive donc à (log_2 k)^2 + 2
Problème marrant : quel est le min ?

je crois que toutes les fonctions peuvent être écrites avec deux lois unaires et une binaire :
p(x) : parité de x = dernier bit
r(x) : rotation circulaire à gauche de 1 bit de x
| : symbole de Sheffer, nand (ou nor)

ach ... suis-je bête je viens seulement de me dire que c'était en fait la généralisation de ce que certains logiciens appellent complétude fonctionnelle ... pour une logique à n valeurs. Je me disais donc que Post devait certainement en avoir parlé. Or, je possède bcp de livres que j'ai à peine ouverts. Or j'ai précisément un texte de Post prop élém, système à m valeurs, première chose que je lis : deux symboles suffisent : négation cyclique et somme ! Je regarde ce soir

Guimauve,
à mon sens, il y a bien un seul et même problème qui peut s'exprimer de deux manières différentes, soit en termes de composées de fonctions, soit en termes de logique à n valeurs (interprétation d'une formule).

Post fait fort, il se contente de la rotation et de la disjonction !


Soient n "valeurs de vérité" distinctes t1, t2, ... tn (les éléments de ton magma),
un connecteur unaire R vérifiant R(ti) = ti+1, R(tn) = t1,
un connecteur binaire v vérifiant ti v tj = tmax(i,j).

En notant Rk(p) l'itéré R(R( ... R(p)..)) (k fois, et R0(p) = p), on observe que

T(p) = p v R(p) v R2(p) v ... v Rn-1(p)
vaut tn pour toute valeur de p,

Zk(p) = R(R(Rn-1(T(p)) v p) v Rk-1(p) )
vaut t1 pour tout p sauf pour tn auquel cas Zk(tn) = tk.

Toute fonction f(p) à une variable peut maintenant s'exprimer par

f(p) = Z_f(tn)(p) v Z_f(tn-1)(R(p)) v ... v Z_f(t1)(Rn-1(p))

On définit ainsi

¬ p avec ¬ (tk) = tn-k+1

puis p.q = ¬(¬p v ¬q)

On vérifie que ti.tj = tmin(i,j).

On peut ensuite pour m variables p1, p2, ... pm construire une table dont toutes les valeurs sont t1 sauf pour une configuration th1, th2, ... thm où sa valeur est tx avec l'expression

Z_x(Rn-h1(p1)).Z_x(Rn-h2(p2)). ... .Z_x(Rn-hm(pm))

Finalement, on peut construire une table quelconque en construisant une fonction de ce genre pour pour chaque configuration puis en sommant au moyen de v.

Reste un dernier point à éclaircir, sur lequel Post reste muet : démontrer qu'un seul connecteur binaire est insuffisant pour exprimer toute fonction.
Affaire à suivre

P.S. ma déf est valable pour n =3, ça donne l'idée pour n quelconque.

Et sans vouloir insister, plus personne n'utilise les mots &quotloi interne" et &quotmagma", qui étaient à l'origine du message.

Par exemple, quelle est la loi interne du magma à huit éléments :
( \{a, b, c, d, e, f, g, h\}, $\star $ ) qui permet de générer la loi additive de $\Z/8\Z$, celle des quaternions, et celle de $({\Z/2\Z})^3$ ? Et de quelle manière ?

Un problème n'est résolu que lorsqu'on a répondu à la question posée.

Amicalement
Volny

GG

Merci de votre attention. Je crains de devoir encore un peu maltraiter les lépidoptères.
Quel est le max de deux éléments sur lesquel n'est définie aucune relation d'ordre ?
Quel est l'isomorphisme qui permet de définir les classes d'équivalences ?
Comment ajouter un nombre à un élément ?
Je vous rapelle que nous avons un magma à 8 éléments, et pas un quotient d'anneau intègre par un idéal.

Amicalement
Volny

Tiens, mon latex est mort, et mes tables sont illisibles.

Je vais voir ce que je peux faire.

A+
Volny

Te casse pas la tête pour ces tables volny, et j'espère que c'est pas moins de 50-50 pour le sérieux
Si tu as lu mon post sur Post tu as vu que les "valeurs de vérité" sont données par la famille (ordonnée) (ti).
Alors soyons fous, ordonnons tes éléments par l'ordre alphabétique :
t1 = a, t2 = b, etc.
la loi x*y est donc définie par ti * tj = tk avec k = max(i,j)+1 si max(i,j) < 8,
k = 1 si max(i,j) = 8.
Exemple : a*b = c, a*g = h, a*h = a, h*h = a, etc.
* n'est pas associative : (a*b)*c = d, a*(b*c) = e
Je définis
R(x) = x*x,
R2(x) = R(R(x)) = (x*x)*(x*x)
R3(x) = R(R(R(x))) = ((x*x)*(x*x))*((x*x)*(x*x)),
etc, jusqu'à R7(x). Je note encore R0(x) = x.
(On voit que R est le cycle (abcdefgh) et Rk sa puissance kième).

Je définis également

x *2 y = (x*y) * (x*y) = R(x*y), x *3 y = (x *2 y) * (x *2 y) = R2(x*y), etc

ainsi que

x v y = x *8 y

et l'on voit que ti v tj = tk avec k = max(i,j).

On voit également que si l'on veut exprimer x v y uniquement à l'aide de *, il faut prévoir des rames de papier, et pour les fonctions à venir, s'engager à replanter un arbre, c'est la moindre des choses.
Si on le veut, on peut exprimer les éléments uniquement avec une variable et la loi * :
h = x v R(x) v R2(x) v ... v R7(x)
g = R7(h), etc.

On a besoin maintenant des fonctions

Zk(x) = R(R(g v x) v Rk-1(x))

On voit que Zk vaut a sauf Zk(h) qui vaut tk.

Z1(x) = a
Z2(x) = R(R(g v x) v R(x))
Z3(x) = R(R(g v x) v R2(x))
...
Z8(x) = R(R(g v x) v R7(x))

Toute fonction f(x) à une variable peut maintenant s'exprimer par

f(x) = Z_f(tn)(x) v Z_f(tn-1)(R(x)) v ... v Z_f(t1)(Rn-1(x))

On définit ainsi

¬(x) avec ¬(tk) = tn-k+1

Soit ¬(x) = Z2(R(x)) v Z3(R2(x)) v ... v Z8(R7(x))
On vérifie ¬(a) = h, ¬(b) = g, ... ¬(h) = a.


puis x.y = ¬(¬(x) v ¬(y))

On vérifie que ti.tj = tmin(i,j).

On peut maintenant construire une fonction fij(x,y) qui vaut a sauf pour x = ti et y = tj
auquel cas fij(tj,tj) = tk :

fij(x,y) = Zk(R8-i(x)).Zk(R8-j(y))

Finalement, on peut construire une loi de composition quelconque en construisant une fonction de ce genre pour pour chaque configuration puis en sommant au moyen de v.



Ta première loi, où je reconnais l'addition dans Z/8Z est donc

x+y =

Z2(R7(x)).Z2(R6(y)) v Z3(R7(x)).Z3(R5(y)) v ... v Z8(R7(x)).Z8(y) v
v Z2(R6(x)).Z2(R7(y)) v Z3(R6(x)).Z3(R6(y)) v ... v Z7(R6(x)).Z7(R(y)) v
v ...
...
v Z7(x).Z7(R7(y)) v Z7(x).Z7(R5(y)) v ... v Z7(x)Z7(y)

Il y a donc 56 termes (j'ai éliminé les 8 facteurs qui donnent a, le neutre de v).

Je te laisse écrire les deux autres lois, ... remplacer les R, les Z, les ., les v par leur définition à l'aide du seul symbole *, et faire de beaux rêves

Cela dit, tu en conviendras, cette possibilité d'exprimer toute application de E^n dans E fini (en particulier toute loi de composition) à l'aide d'une seule loi de composition est purement théorique et n'a à priori aucune espèce d'intérêt ! Je trouve juste rigolo la complétude fonctionnelle du calcul prop à n valeurs de vérité avec un seul connecteur (que ne mentionne pas Post), et encore, je n'ai jamais vu d'application de ce calcul ... mais là, c'est probablement mon inculture qui parle