การดำเนินการเชิงสัมพันธ์โดยใช้เฉพาะส่วนเพิ่ม วนรอบ กำหนด หรือศูนย์

เซตของจำนวนธรรมชาติ N ถูกปิดภายใต้การบวกและการลบ:

N + N = N
N - N = N

ซึ่งหมายความว่าการบวกหรือการลบจำนวนธรรมชาติสองตัวก็เป็นจำนวนธรรมชาติเช่นกัน (เมื่อพิจารณาว่า 0 - 1 เป็น 0 และไม่ใช่ -1 เราจะไม่สามารถมีจำนวนธรรมชาติติดลบได้)

อย่างไรก็ตาม เซตของจำนวนธรรมชาติ N จะไม่ถูกปิดภายใต้การดำเนินการเชิงสัมพันธ์:

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

ซึ่งหมายความว่าผลลัพธ์ของการเปรียบเทียบจำนวนธรรมชาติสองตัวคือความจริง (เช่น 1) หรือความเท็จ (เช่น 0)

ดังนั้นเราจึงถือว่าชุดของบูลีน (เช่น {0, 1}) เป็นชุดจำกัดของจำนวนธรรมชาติ (เช่น N)

false = 0
true  = incr(false)

คำถามแรกที่เราต้องตอบคือเราจะเข้ารหัสคำสั่ง if เพื่อแยกย่อยตามความจริงหรือความเท็จได้อย่างไร คำตอบนั้นง่ายมาก เราใช้การดำเนินการ loop:

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

หากเงื่อนไขการวนซ้ำคือ true (เช่น 1) การวนซ้ำจะดำเนินการเพียงครั้งเดียว หากเงื่อนไขการวนซ้ำคือ false (เช่น 0) แสดงว่าการวนซ้ำไม่ทำงาน เราสามารถใช้สิ่งนี้เพื่อเขียนรหัสสาขา

แล้วเราจะนิยามการดำเนินการเชิงสัมพันธ์ได้อย่างไร? ปรากฎว่าทุกอย่างสามารถกำหนดได้ในรูปของ lte:

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

เรารู้ว่า x ≥ y เหมือนกับ y ≤ x ดังนั้น:

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

เรารู้ว่าถ้า x > y เป็นจริง ดังนั้น x ≤ y จะเป็นเท็จ ดังนั้น:

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

เรารู้ว่า x < y เหมือนกับ y > x ดังนั้น:

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

เรารู้ว่าถ้า x ≤ y และ y ≤ x แล้วก็ x = y ดังนั้น:

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

สุดท้ายนี้ เรารู้ว่าถ้า x = y เป็นจริง x ≠ y จะเป็นเท็จ ดังนั้น:

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

ตอนนี้สิ่งที่เราต้องทำคือกำหนดฟังก์ชันต่อไปนี้:

1. ฟังก์ชัน sub ถูกกำหนดไว้ดังนี้:

   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. ฟังก์ชัน not เหมือนกับฟังก์ชัน isZero:

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

3. ฟังก์ชัน and เหมือนกับฟังก์ชัน 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
   }
   

นั่นคือทั้งหมดที่คุณต้องการ หวังว่าจะช่วยได้