Operasi relasional hanya menggunakan kenaikan, perulangan, penetapan, nol

Himpunan bilangan asli N ditutup pada penjumlahan dan pengurangan:

N + N = N
N - N = N

Artinya penjumlahan atau pengurangan dua bilangan asli juga merupakan bilangan asli (mengingat 0 - 1 adalah 0 dan bukan -1, kita tidak dapat mempunyai bilangan asli negatif).

Namun, himpunan bilangan asli N tidak tertutup pada operasi relasional:

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

Artinya, hasil perbandingan dua bilangan asli adalah benar (yaitu 1) atau salah (yaitu 0).

Jadi, kami memperlakukan himpunan boolean (yaitu {0, 1}) sebagai himpunan terbatas dari bilangan asli (yaitu N).

false = 0
true  = incr(false)

Pertanyaan pertama yang harus kita jawab adalah bagaimana kita mengkodekan pernyataan if sehingga kita dapat melakukan percabangan berdasarkan kebenaran atau kepalsuan? Jawabannya sederhana, kami menggunakan operasi loop:

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

Jika kondisi perulangan adalah true (yaitu 1) maka perulangan dijalankan tepat satu kali. Jika kondisi perulangan adalah false (yaitu 0) maka perulangan tidak dijalankan. Kita dapat menggunakan ini untuk menulis kode percabangan.

Jadi, bagaimana kita mendefinisikan operasi relasional? Ternyata, semuanya dapat didefinisikan dalam lte:

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

Kita tahu bahwa x ≥ y sama dengan y ≤ x. Karena itu:

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

Kita tahu bahwa jika x > y benar maka x ≤ y salah. Karena itu:

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

Kita tahu bahwa x < y sama dengan y > x. Karena itu:

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

Kita tahu jika x ≤ y dan y ≤ x maka x = y. Karena itu:

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

Terakhir, kita mengetahui bahwa jika x = y benar maka x ≠ y salah. Karena itu:

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

Sekarang, yang perlu kita lakukan hanyalah mendefinisikan fungsi-fungsi berikut:

1. Fungsi sub didefinisikan sebagai berikut:

   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. Fungsi not sama dengan fungsi isZero:

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

3. Fungsi and sama dengan fungsi 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
   }
   

Hanya itu yang Anda butuhkan. Semoga itu bisa membantu.