backup del Post

Spending review sulle operazioni

Vi siete mai chiesti perché le quattro operazioni siano proprio quattro, e non due, sette o quarantadue? Beh, quarantadue operazioni da ricordare sarebbero in effetti un po’ troppe, e forse elevazione a potenza, estrazione di radice e logaritmo non sono proprio così elementari; inoltre dire che “la sottrazione è l’opposto dell’addizione e la divisione l’inverso della moltiplicazione” può dare qualche problema con frazioni e numeri negativi. (Ah: c’è chi dice che definire la moltiplicazione come somma ripetuta dia più danni che altro. Ne riparliamo magari un’altra volta). Secondo me, insomma, la risposta è che quattro era un bel numero, né troppo grande né troppo piccolo.

Può però sembrare incredibile, ma non è necessario usare tutte e quattro le operazioni per ottenere i loro risultati: è possibile definire una sola operazione ◊ tale che a+b, a−b, a⋅b e a/b siano tutti esprimibili per mezzo di ◊, pur con un po’ di fatica e un paio di assunzioni – no, si chiamano “assiomi”. L’operazione è naturalmente binaria: a ◊ b, proprio come a+b. Quindi le tecniche che si applicano sono un po’ diverse da quelle che dicono a−b = a+(−b); in quest’ultimo caso infatti abbiamo introdotto un nuovo operatore unario (il − davanti a un numero, che è diverso dal − che si piazza in mezzo a due numeri anche se purtroppo viene scritto nello stesso modo). Volete sapere come si fa?

Innanzitutto possiamo scaldarci i muscoli con un esempio più facile, quello delle porte logiche nei computer. In questo caso abbiamo solo due possibili valori di ingresso e uscita, V (vero) e F (falso); le porte logiche che si usano di solito sono AND, OR e NOT con le tabelle di verità (l’equivalente logico della tavola pitagorica) mostrate qui sotto.

   +-----+-----+---------+--------+          +-----+-------+
   |  A  |  B  | A AND B | A OR B |          |  A  | NOT A |
   +-----+-----+---------+--------+          +-----+-------+
   |  V  |  V  |    V    |   V    |          |  V  |   F   |
   |  V  |  F  |    F    |   V    |          |  F  |   V   |
   |  F  |  V  |    F    |   V    |          +-----+-------+
   |  F  |  F  |    F    |   F    |
   +-----+-----+---------+--------+

(era una vita che volevo fare un po’ di ASCII art!) Oggi nella crittografia si usa spesso l’operazione XOR, che è simile all’OR tranne per il fatto che V XOR V = F; però non è un’operazione “nuova”, visto che A XOR B = ((A OR B) AND NOT (A AND B)). Bene: servono proprio tutte e tre le operazioni logiche di cui sopra? La risposta è no; ce ne basta una sola. L’operazione da usare è NAND, che ha la tabella di verità indicata qui sotto.

   +-----+-----+----------+
   |  A  |  B  | A NAND B |
   +-----+-----+----------+
   |  V  |  V  |    F     |
   |  V  |  F  |    V     |
   |  F  |  V  |    V     |
   |  F  |  F  |    V     |
   +-----+-----+----------+

Infatti, per ottenere NOT A basta fare (A NAND A); a questo punto (A AND B) è dato da NOT (A NAND B) e (A OR B) da ((NOT A) NAND (NOT B)). Che si può ricavare da questo esempio? Che se vogliamo risparmiare sulle operazioni a disposizione, occorre aggiungere qualcosa che contenga al suo interno una negazione, visto che dal meno si può ottenere il più ma non viceversa; inoltre un’operazione unaria può far comodo. Vediamo ora come sfruttare questa informazione nel caso delle operazioni aritmetiche. Per la cronaca, il procedimento l’ho trovato nel libro A Problem Seminary di Donald J. Newman, che spacchetta la ricerca in due problemi (i primi del libro).

Per prima cosa, vediamo come è possibile usare due sole operazioni per ottenere tutte e quattro quelle solite. I candidati che useremo sono la sottrazione e l’inverso x → 1/x. Avendo a disposizione la sottrazione possiamo immediatamente ottenere lo zero: x−x=0. Il numero 1 invece lo dobbiamo assumere come esistente, o perlomeno presupporre che l’equazione x = 1/x abbia almeno una soluzione. (Ah: man mano che riesco a ottenere un’operazione inizio a usarla come se l’avessi sempre avuta a disposizione, perché altrimenti rischierei di fare come Russell e Whitehead che nei loro Principia Mathematica hanno usato una pagina di formule per dimostrare che 1+1=2…)

L’addizione non è molto difficile da ottenere, quando si ha la sottrazione: x+y = x − (0 − y). Se riusciamo a ottenere la moltiplicazione, avremmo anche la divisione: in fin dei conti, x/y = x·(1/y). Come ottenere la moltiplicazione? Newman come aiutino afferma “cercate di esprimere x²“: come se fosse semplice. Lo si può fare però per gradi: si inizia a ricavare 1/(x²−x) = 1/(x(x−1)) = −((1/x)−(1/(x−1))); da qui prendiamo l’inverso e sommiamo x e siamo a posto. Il passo successivo consiste nel notare che (x+y)²−x²−y²=2xy. Ci resta pertanto solo da ottenere xy da 2xy; ma quello è immediato perché 1/((1/(2xy))+(1/(2xy)))=xy.

Prendiamo un attimo fiato prima del rush finale. Come scrivevo sopra, siamo riusciti a esprimere le quattro operazioni a partire da sottrazione e inverso. Il secondo passo di Newman consiste nel trovare l’operazione (binaria) ◊ con la quale poter esprimere sottrazione e inverso, e la sua risposta è “mettiamo tutto assieme!” L’operazione scelta per x◊y è infatti 1/(x−y). Ammettendo di avere a disposizione lo zero (e questo dev’essere proprio un assioma, stavolta: non ci sono santi) abbiamo che x ◊ 0 = 1/(x−0) = 1/x, e (x ◊ y )◊ 0 – 1/((1/x−y)-0) = x−y. QED.

Si poteva fare di meglio? Non lo so. A me questa storia di dover assumere l’esistenza di zero e uno non è che piaccia molto, ve lo dico subito. Insomma, se qualcuno trova un altro sistema è il benvenuto!