dénombrement: fonctions booléennes de n variables

[acx01b]

bonjour,

je souhaiterais savoir combien il existe de fonctions booléennes de n variables

par exemple:
(A ou B) et (C ou D) et ((non D) ou (non C))
est une fonction booléenne de 4 variables (A, B, C, D)

j'ai commencé le travail mais après ça se corse !

il existe 4 fonctions d'une variable A:
f(A) = A
f(A) = non A
f(A) = vrai
f(A) = faux

maintenant avec 2 variables il y a .... 12 fonctions:
f(A,B) = vrai
f(A,B) = faux
f(A,B) = A
f(A,B) = non A
f(A,B) = A et B
f(A,B) = A ou B
f(A,B) = non (A et B)
f(A,B) = non (A ou B)
f(A,B) = (A et (non B)) ou (B et (non A)) = A xor B
f(A,B) = (A et B) ou ((non A) et (non B)) = non (A xor B)
f(A,B) = A et (non B)
f(A,B) = A ou (non B)

en effet si on considère que l'on peut substituer les variables: la fonction A et (non B) est la même fonction que B et (non A)

et on a 12 fonctions booléennes de 2 variables au lieu de 16 (avec la formule nombre de fonctions booléennes de n variables = 2^(2^n) donnée souvent en cours)

voila merci d'avance
-----

[invite88ef51f0]

Salut,
Je dirais que si tu fais la table de vérité, tu as n entrées qui peuvent prendre 2 valeurs, donc 2ⁿ cases à remplir. Tu as deux possibilités pour chaque case, donc au final 2^2ⁿ tables différentes.

Bref, il doit t'en manquer dans le cas n=2.

[invite6de5f0ac]

Bref, il doit t'en manquer dans le cas n=2.

Bonjour,

Je confirme: le nombre cherché est bien 2^2ⁿ, comme le raisonnement élémentaire l'indique. Mais je ne vois pas (à cette heure-ci en tout cas, au milieu de mon café du matin) celles que acx01b a loupées...

-- françois

[invite88ef51f0]

Il me semble que certaines fonctions ne s'expriment pas simplement avec des et/ou/non.
Peut-être en regardant là :
http://fr.wikipedia.org/wiki/Alg%C3%..._fondamentales

Les fonctions implication et inhibition ont été dites ou pas ?

[A voir en vidéo sur Futura]

[invite6de5f0ac]

Il me semble que certaines fonctions ne s'expriment pas simplement avec des et/ou/non.
Les fonctions implication et inhibition ont été dites ou pas ?

Eh bin si! Toute fonction booléenne s'exprime uniquement avec des NOR (ou des NAND), c'est couramment utilisé en électronique...
Par exemple, (A => B) n'est autre que ((non A) ou B) si je me souviens bien, et (non A) = (A NOR A), (X ou B) = ((X NOR B) NOR (X NOR B)), et ainsi de suite...
Réviser les lois de De Morgan!!!

-- françois

[invite6de5f0ac]

en effet si on considère que l'on peut substituer les variables: la fonction A et (non B) est la même fonction que B et (non A)

Aaaah... je commence à comprendre!

Certaines fonctions sont "commutatives", et dans ce cas on ne les compterait pas comme distinctes... Alors là effectivement il faut quotienter par le nombre de permutations, et ça se corse. Je regarde de plus près.

-- françois

[Médiat]

Eh bin si! Toute fonction booléenne s'exprime uniquement avec des NOR (ou des NAND), c'est couramment utilisé en électronique...

Absolument, juste une précision, en mathématiques on utilise (assez peu, mais l'intérêt est théorique), la barre de Sheffer (A v B and not (A & B))qui doit correspondre soit au NAND soit au NOR (mes connaissances en électronique se limitant au bouton On/Off de ma chaîne Hifi)

[invite6de5f0ac]

Absolument, juste une précision, en mathématiques on utilise (assez peu, mais l'intérêt est théorique), la barre de Sheffer (A v B and not (A & B))qui doit correspondre soit au NAND soit au NOR (mes connaissances en électronique se limitant au bouton On/Off de ma chaîne Hifi)

Exact. La barre de Sheffer (que je note A | B, à ne pas confondre avec le "|" du langage C qui est un OU logique, binaire en fait) est vraie quand A et B sont différents. Ce n'est donc ni un NOR ni un NAND. C'est en fait la négation de l'équivalence.

Mais il est essentiel de noter qu'on ne peut faire les autres fonctions que si l'opérateur de base permet l'inversion (le NOT). Ça peut paraître évident comme ça, mais... c'est aussi pour ça qu'il existe des circuits logiques DTL (diode-transistor) et TTL (transistor-transistor), un transistor est toujours indispensable pour réaliser l'inversion. Avec rien que des diodes on peut faire des ET et des OU mais pas de NON...

-- françois

[acx01b]

Bonsoir,

on dénombre les fonctions booléennes à n variables
je propose comme idée:
étant donné une expression booléenne de n variables, si en permutant les variables d'une autre expression booléenne de n variables on obtient la même expression, alors on ne la compte qu'une fois...

par exemple on considère une équivalence:
((non A) ou B) et C <=> ((non B) ou A) et C

si on utilise la formule 2^(2^n) qui correspond
aux mots de 2^n lettres prises parmis 2 (i.e les mots de 2^n bits), ou à la construction de toutes les tables de vérités possibles, on compte 6 fois cette fonction :
((non A) ou B) et C
((non B) ou A) et C
((non A) ou C) et B
((non C) ou A) et B
((non B) ou C) et A
((non C) ou B) et A
et bien d'autres aussi

la question reste toujours: combien il y-a-t-il de nombres de fonctions booléennes à n variables ?

merci

[MMu]

En général si est l'ensembles des fonctions alors
Dans le cas des fonctions booléennes à variables on a
Il s'ensuit tout de suite

[acx01b]

bon c'est super les gens ne lisent pas le sujet de la discussion...

lol

[acx01b]

bonjour

resultats calculés:
pour 1 variable: 4 fonctions booléennes
pour 2 variables: 12 fonctions booléennes
pour 3 variables: 80 fonctions booléennes
pour 4 variables: 3984 fonctions booléennes

après ça prend plus d'une heure à calculer

l'agorithme est simple:
si il n'y a pas de permutation des variables pour lesquelles la fonction booléenne a son équivalente (table de vérité)
total est incrémenté
et cette fonction n'est plus utilisée dans le reste des calculs (tab[1<<N][numeros_de_la_fonction] est mis à 1)

int tab[17][65536]; // limité à 4 variables: 17 = 2^4 + 1, 65536 = 2^(2^4)
int tableau_permutations[4][24];
int un_dec_un_dec_N; // 1 << (1 << N)
int un_dec_N; // 1 << N
int fact_N; // factoriel N: N! (nombre de permutations)

void permutations(int *ens, int n, int i) {
static int nieme_permutation = 0;
if (i<n-1) {
int k;
for (k=i; k<n; k++) {
if (ens[i] != ens[k]) {
ens[i] ^= ens[k];
ens[k] ^= ens[i];
ens[i] ^= ens[k];
permutations(ens,n,i+1);
ens[i] ^= ens[k];
ens[k] ^= ens[i];
ens[i] ^= ens[k];
}
else {
permutations(ens,n,i+1);
}
}
}
else {
int k;
for (k=0;k<N;k++) tableau_permutations[k][nieme_permutation] = ens[k];
nieme_permutation++;
}
}

int verifier_si_fonction_redondant e (int current) {
int permutation;
for (permutation=1;permutation < fact_N; permutation++) {
int k,v;
for (k=current+1; k < un_dec_un_dec_N; k++) {
v = 1;
int m;
for (m=0; m < un_dec_N; m++) {
int acc;
acc = 0;
int b;
for (b=0; b < N; b++) {
acc += ((m&(1<<b)) ? 1 : 0)*tableau_permutations[b][permutation];
}
if (tab[acc][current] != tab[m][k]) { v = 0; break; }
}
if (v) { tab[un_dec_N][current] = 1; return 1;}
}
}
return 0;
}
int main() {
un_dec_N = 1<<N;
un_dec_un_dec_N = 1<<(1<<N);
fact_N = 1;
int k;
for (k=2;k<=N;k++) fact_N *= k;

// remplir le tableau avec la table de verite de chaque fonction booléenne

for (k=0; k < un_dec_un_dec_N; k++) {
int m;
for (m=0;m < un_dec_N;m++) {
if ((1<<m)&k) tab[m][k] = 1;
else tab[m][k] = 0;
}
tab[un_dec_N][k] = 0;
}

// remplir le tableau des permutations des variables
int ens[5] = {1,2,4,8,16};
permutations(ens,N,0);
int u;
// compter le nombre de fonction booléenne non redondantes
int total;
int current;
total = 0;
for (current = 0; current < un_dec_un_dec_N; current++) {
if (!verifier_si_fonction_redonda nte(current)) total++;
printf("%d\n",current);
}
printf("nombre de fonctions booléennes de %d variables: %d\n",N,total);
return 0;
}

[Médiat]

Tu as oublié
pour 0 variable : 2 fonctions booléennes
Tu veux la suite ?

pour 5 variables : 37333248 fonctions booléennes
pour 6 variables : 25626412338274304 fonctions booléennes
pour 7 variables : 675163429731859743281756900876 61568 fonctions booléennes.


De tête je n'ai pas pu calculer plus loin.

 Cliquez pour afficher

là

[acx01b]

salut !
merci pour ta réponse, par contre j'aurais besoin d'un détective qui me traduise la formule en langage humain!!!

a(n) = sum {1*s_1+2*s_2+...=n} (fix A[s_1, s_2, ...]/(1^s_1*s_1!*2^s_2*s_2!*...)) where fix A[s_1, s_2, ...] = 2^sum {i>=1} ( sum {d|i} ( mu(i/d)*( 2^sum {j>=1} ( gcd(j, d)*s_j))))/i.

trouvée sur http://www.research.att.com/~njas/se...%2c12&p=2&n=10

merci d'avance

[acx01b]

désolé de faire remonter la discussion :

mon problème est maintenant de traduire la formule en langage mathématique:

a(n) = sum {1*s_1+2*s_2+...=n} (fix A[s_1, s_2, ...]/(1^s_1*s_1!*2^s_2*s_2!*...))
where fix A[s_1, s_2, ...] = 2^sum {i>=1} ( sum {d|i} ( mu(i/d)*( 2^sum {j>=1} ( gcd(j, d)*s_j))))/i

si quelqu'un a une idée de ce que ça signifie ?? merci