Répondre à la discussion
Affichage des résultats 1 à 15 sur 15

dénombrement: fonctions booléennes de n variables



  1. #1
    acx01b

    dénombrement: fonctions booléennes de n variables


    ------

    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

    -----

  2. Publicité
  3. #2
    Coincoin

    Re : dénombrement: fonctions booléennes de n variables

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

    Bref, il doit t'en manquer dans le cas n=2.
    Encore une victoire de Canard !

  4. #3
    fderwelt

    Re : dénombrement: fonctions booléennes de n variables

    Citation Envoyé par Coincoin Voir le message
    Bref, il doit t'en manquer dans le cas n=2.
    Bonjour,

    Je confirme: le nombre cherché est bien 2^2n, 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
    Les optimistes croient que ce monde est le meilleur possible. Les pessimistes savent que c'est vrai.

  5. #4
    Coincoin

    Re : dénombrement: fonctions booléennes de n variables

    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 ?
    Encore une victoire de Canard !

  6. #5
    fderwelt

    Re : dénombrement: fonctions booléennes de n variables

    Citation Envoyé par Coincoin Voir le message
    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
    Les optimistes croient que ce monde est le meilleur possible. Les pessimistes savent que c'est vrai.

  7. A voir en vidéo sur Futura
  8. #6
    fderwelt

    Re : dénombrement: fonctions booléennes de n variables

    Citation Envoyé par acx01b Voir le message
    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
    Les optimistes croient que ce monde est le meilleur possible. Les pessimistes savent que c'est vrai.

  9. Publicité
  10. #7
    Médiat

    Re : dénombrement: fonctions booléennes de n variables

    Citation Envoyé par fderwelt Voir le message
    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)
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  11. #8
    fderwelt

    Re : dénombrement: fonctions booléennes de n variables

    Citation Envoyé par Médiat Voir le message
    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
    Les optimistes croient que ce monde est le meilleur possible. Les pessimistes savent que c'est vrai.

  12. #9
    acx01b

    Re : dénombrement: fonctions booléennes de n variables

    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

  13. #10
    MMu

    Re : dénombrement: fonctions booléennes de n variables

    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

  14. #11
    acx01b

    Re : dénombrement: fonctions booléennes de n variables

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

    lol

  15. #12
    acx01b

    Re : dénombrement: fonctions booléennes de n variables

    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;
    }

  16. Publicité
  17. #13
    Médiat

    Re : dénombrement: fonctions booléennes de n variables

    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
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  18. #14
    acx01b

    Re : dénombrement: fonctions booléennes de n variables

    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

  19. #15
    acx01b

    Re : dénombrement: fonctions booléennes de n variables

    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

Sur le même thème :

Discussions similaires

  1. variables aléatoires et fonctions de correlations
    Par gatsu dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 22/11/2007, 20h33
  2. fonctions à plusieurs variables
    Par minidiane dans le forum Mathématiques du supérieur
    Réponses: 11
    Dernier message: 18/06/2007, 11h56
  3. fonctions à plusieurs variables
    Par minidiane dans le forum Mathématiques du supérieur
    Réponses: 6
    Dernier message: 15/06/2007, 11h06
  4. Fonctions de plusieurs variables
    Par Neji dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 04/02/2007, 20h13
  5. Variables booleennes/Tableau Karnaugh
    Par marfield77 dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 27/04/2004, 18h43