Don't take life too seriously: it's just a temporary situation

Si chiama “n-esimo numero di Dedekind” Dn il numero di funzioni booleane (con argomenti e valori che possono essere solo 0 o 1) a n variabili, ottenibili con operazioni AND e OR, senza usare la negazione, dette anche funzioni monotone.

Per esempio:

  • senza alcuna variabile esistono 2 funzioni (costanti): 0 e 1;

  • con una variabile a esistono tre funzioni: 0, 1 e a;

  • con due variabili a e b esistono 6 funzioni: 0, 1, a + b, ab, ab + a e ab + b, dove la somma è la somma logica (equivalente a una somma modulo 2).

 

Il nome si deve a Dedekind, che pose il problema nel 1897. Da allora sono stati fatti progressi nella determinazione di intervalli entro i quali i valori dei numeri di Dedekind debbono trovarsi, ma non è ancora stata scoperta una formula semplice, né un modo efficiente per calcolarli, tanto che a oggi sono noti solo i primi 9, mostrati nella tabella seguente.

I primi 6 furono calcolati da Randolph Church (1940), il settimo da Morgan Ward (1946), l’ottavo da Randolph Church (1965) e il nono da Doug Wiedemann (1991).

Numero di variabili

Numero di Dedekind

0

2

1

3

2

6

3

20

4

168

5

7581

6

7828354

7

2414682040998

8

56130437228687557907788

 

Nel 1981 A.D. Korshunov dimostrò che Dn cresce come Formula asintotica per i numeri di Dedekind per numeri pari di variabili per n pari e Formula asintotica per i numeri di Dedekind per numeri dispari di variabili per n dispari, dove Formula per a(n) e Formula per b(n).

 

Nel 1991 Andrzej Kisielewicz pubblicò una formula, che in teoria permette di calcolarli: Formula per il calcolo dei numeri di Dedekind, dove Notazione per il j-esimo bit di k è il j-esimo bit di k rappresentato in base 2. La formula non ha però applicazioni pratiche, a causa del numero spaventoso di addendi da calcolare.

 

Il numero di possibili funzioni booleane a n variabili, usando anche la negazione, è Numero di funzioni booleane con n variabili.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.