operazioni relazionali utilizzando solo incremento, loop, assegnare, pari a zero

Question

Si tratta di un follow-up domanda per: Subtraction operation using only increment, loop, assign, zero

Stiamo solo permesso di utilizzare le seguenti operazioni:

1. incr (x) - Una volta questa funzione è chiamata assegnerà x + 1 a x
2. assign (x, y) - Questa funzione assegnerà il valore di y a x (x = y)
3. zero (x) - Questa funzione assegnerà 0 a x (x = 0)
4. ciclo X {} - operazioni scritte tra parentesi saranno eseguite X volte

Per esempio, l'aggiunta può essere implementato come segue:

add(x, y) { 
    loop x 
     { y = incr(y) } 
    return y 
} 

Come faccio a implementare il relational operators utilizzando queste quattro operazioni? Le operazioni relazionali sono:

1. eq (x, y) - x è uguale a y?
2. lt (x, y) - È x minore di y?
3. gt (x, y) - x è maggiore di y?

Abbiamo anche i loro opposti:

1. ne (x, y) - è x non è uguale a Y?
2. gte (x, y) - x è maggiore o uguale a y?
3. lte (x, y) - È x minore o uguale a y?

Qualsiasi aiuto sarà apprezzato.

Answer 1

L'insieme dei numeri naturali N è chiusa sotto addizione e sottrazione:

N + N = N 
N - N = N 

Ciò significa che l'aggiunta o la sottrazione di due numeri naturali è anche un numero naturale (considerando 0 - 1 è 0 e non -1, abbiamo non può avere numeri naturali negativi).

Tuttavia, l'insieme dei numeri naturali N non è chiusa rispetto operazioni relazionali:

N < N = {0, 1} 
N > N = {0, 1} 

Ciò significa che il risultato del confronto tra due numeri naturali è o veridicità (cioè 1) o falso (cioè 0).

Pertanto, consideriamo l'insieme di valori booleani (ad esempio {0, 1}) come un insieme limitato di numeri naturali (ad esempio N).

false = 0 
true = incr(false) 

La prima domanda che dobbiamo rispondere è “ come possiamo codificare if dichiarazioni in modo che possiamo ramo basata o veridicità o la falsità?” La risposta è semplice, usiamo l'operazione loop:

isZero(x) { 
    y = true 
    loop x { y = false } 
    return y 
} 

Se la condizione del ciclo è true (cioè 1) allora il ciclo viene eseguito esattamente una volta. Se la condizione del loop è false (ad esempio 0), il ciclo non viene eseguito. Possiamo usarlo per scrivere il codice di diramazione.

Quindi, come definiamo le operazioni relazionali? Risulta, tutto può essere definito in termini di lte:

lte(x, y) { 
    z = sub(x, y) 
    z = isZero(z) 
    return z 
} 

Sappiamo che x ≥ y è lo stesso di y ≤ x. Pertanto:

gte(x, y) { 
    z = lte(y, x) 
    return z 
} 

Sappiamo che se x > y è vero allora x ≤ y è falso. Pertanto:

gt(x, y) { 
    z = lte(x, y) 
    z = not(z) 
    return z 
} 

Sappiamo che x < y è lo stesso di y > x. Pertanto:

lt(x, y) { 
    z = gt(y, x) 
    return z 
} 

Sappiamo che se x ≤ y e y ≤ x poi x = y. Pertanto:

eq(x, y) { 
    l = lte(x, y) 
    r = lte(y, x) 
    z = and(l, r) 
    return z 
} 

Infine, sappiamo che se è vero allora x = yx ≠ y è falso. Pertanto:

ne(x, y) { 
    z = eq(x, y) 
    z = not(z) 
    return z 
} 

Ora, tutto quello che dobbiamo fare è definire le seguenti funzioni:

1. La funzione sub è definito come segue:

   sub(x, y) { 
       loop y 
        { x = decr(x) } 
       return x 
   } 
   
   decr(x) { 
       y = 0 
       z = 0 
   
       loop x { 
        y = z 
        z = incr(z) 
       } 
   
       return y 
   } 
   

2. La funzione not è la uguale alla funzione isZero:

   not(x) { 
       y = isZero(x) 
       return y 
   } 
   

3. La funzione and è la stessa della funzione di mul:

   and(x, y) { 
       z = mul(x, y) 
       return z 
   } 
   
   mul(x, y) { 
       z = 0 
       loop x { z = add(y, z) } 
       return z 
   } 
   
   add(x, y) { 
       loop x 
        { y = incr(y) } 
       return y 
   } 
   

Questo è tutto ciò che serve. Spero possa aiutare.