opérations relationnelles à l'aide incrément seulement, boucle, assigner, zéro

Question

Ceci est une question de suivi pour: Subtraction operation using only increment, loop, assign, zero

Nous sommes seulement autorisés à utiliser les opérations suivantes:

1. INCR (x) - Une fois assigner x + 1 à x
2. assign (x, y) - Cette fonction affectera la valeur de y à x (x = y)
3. zéro (x) - Cette fonction affectera 0 à x (x = 0)
4. boucle X {} - opérations écrites entre crochets seront exécutés X fois

Par exemple, peut être mis en œuvre plus comme suit:

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

Comment puis-je mettre en œuvre le relational operators en utilisant ces quatre opérations? Les opérations relationnelles sont:

1. eq (x, y) - Est-ce que x est égal à y? Lt (x, y) - x est-il inférieur à y?
2. gt (x, y) - Est-ce que x est supérieur à y?

Nous avons aussi leurs contraires:

1. ne (x, y) - est x pas égal à y?
2. gte (x, y) - Est-ce que x est supérieur ou égal à y? Lte (x, y)
3. - Est-ce que x est inférieur ou égal à y?

Toute aide sera appréciée.

Answer 1

L'ensemble des nombres naturels N est fermé par addition et soustraction:

N + N = N 
N - N = N 

Cela signifie que l'addition ou la soustraction de deux nombres naturels est aussi un nombre naturel (compte tenu 0 - 1 est 0 et non -1, nous ne peut pas avoir de nombres naturels négatifs).

Cependant, l'ensemble des nombres naturels N est pas fermé sous les opérations relationnelles:

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

Cela signifie que le résultat de la comparaison de deux nombres naturels est soit véracité (à savoir 1) ou faux (à savoir 0). Donc, nous traitons l'ensemble des booléens (c'est-à-dire {0, 1}) comme un ensemble restreint des nombres naturels (c'est-à-dire N).

false = 0 
true = incr(false) 

La première question que nous devons répondre est “ comment pouvons-nous chiffrons if déclarations afin que nous puissions branche basée soit sur la véracité ou la fausseté?” La réponse est simple, nous utilisons l'opération loop:

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

Si la condition de boucle est true (à savoir 1), puis la boucle exécute exactement une fois. Si la condition de boucle est false (c'est-à-dire 0), la boucle ne s'exécute pas. Nous pouvons l'utiliser pour écrire un code de branchement.

Alors, comment définissons-nous les opérations relationnelles? Il s'avère que, tout peut être défini en termes de lte:

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

Nous savons que x ≥ y est le même que y ≤ x. Par conséquent:

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

Nous savons que si x > y est vrai, alors x ≤ y est faux. Par conséquent:

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

Nous savons que x < y est le même que y > x. Par conséquent:

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

Nous savons que si x ≤ y et y ≤ x puis x = y. Par conséquent:

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

Enfin, nous savons que si x = y est vrai, alors x ≠ y est faux. Par conséquent:

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

Maintenant, tout ce que nous devons faire est de définir les fonctions suivantes:

1. La fonction sub est définie comme suit:

   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 fonction not est le même que la fonction isZero:

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

3. La fonction and est la même que la fonction 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 
   } 
   

C'est tout ce que vous avez besoin. J'espère que cela pourra aider.