神奇的 amb 操作符

有一个部落叫 Kalotan，这里的人有一个很奇怪的特点，那就是男性从来只说真话；女性从来不会连续说两句真话，也不会连续说两句假话。

有一天，一个人类学家来到这个部落。遇到一对(异性)夫妇和他们的小孩 Kibi。人类学家问 Kibi：“你是男孩还是女孩？”

Kibi 说了一句 Kalotan 语。人类学家听不懂，于是转向 Kibi 的父母询问答案(他们会说英语)。于是其中一个(parent1)对他说： “Kibi 说他是男孩。” 另一个(parent2)对他说：“Kibi 是个女孩。 Kibi 撒谎了。”

如果写一个 Scheme 程序，不但立即就可以解决这个问题。还可以帮助我们分析这个问题。程序如下：

(define (distinct? . ls)
  (let loop ((lst (car ls)))
    (let ((first (car lst)) (rest (cdr lst)))
      (cond 
       ((null? rest) #t)
       ((member first rest) #f)
       (else (loop rest))))))

(define (xor a b)
  (or (and a (not b))
      (and b (not a))))

(define solve-kalotan-puzzle
  (lambda ()
    (let ((parent1 (amb 'm 'f))
          (parent2 (amb 'm 'f))
          (kibi (amb 'm 'f))
          (kibi-self-desc (amb 'm 'f))
          (kibi-lied? (amb #t #f)))

      ;; Parent1 and parant2 must have distinct sex.
      (assert
       (distinct? (list parent1 parent2)))

      ;; If kibi is a boy, then he will never tell a lie.
      (assert
       (if (eqv? kibi 'm)
           (not kibi-lied?)))

      (assert
       (if kibi-lied?
           (xor
            (and (eqv? kibi-self-desc 'm)
                 (eqv? kibi 'f))
            (and (eqv? kibi-self-desc 'f)
                 (eqv? kibi 'm)))))

      (assert
       (if (not kibi-lied?)
           (xor
            (and (eqv? kibi-self-desc 'm)
                 (eqv? kibi 'm))
            (and (eqv? kibi-self-desc 'f)
                 (eqv? kibi 'f)))))

      ;; If parent1 is male,
      ;; parent1 told the truth,
      ;; parent2 told a truth and a lie,
      ;; but we don't know which is the truth.
      (assert
       (if (eqv? parent1 'm)
           (and
            (eqv? kibi-self-desc 'm)    
            (xor                        
             (and (eqv? kibi 'f)
                  (eqv? kibi-lied? #f))
             (and (eqv? kibi 'm)
                  (eqv? kibi-lied? #t))))))

      ;; If parent1 is female,
      ;; we can't know whether parent1 told the truth,
      ;; because he(she) said only one sentence,
      ;; but parent2 must told us all truth.
      (assert
       (if (eqv? parent1 'f)
           (and                         
            (eqv? kibi 'f)
            (eqv? kibi-lied? #t))))

      ;; Output the results.
      (newline)
      (display "Kibi said its sex is ")
      (display kibi-self-desc)
      (display ".\n")
      (if kibi-lied?
          (display "Kibi lied.\n")
          (display "Kibi told the truth.\n"))
      (display "The sex of parent1, parent2 and Kibi is: ")
      (display (list parent1 parent2 kibi))
      (newline))))

(solve-kalotan-puzzle)

我们用变量 parent1, parent2, kibi 分别表示三个人的性别。用 kibi-self-desc 表示 Kibi 自称的性别。用 kibi-lied? 表示 Kibi 是否撒谎。

这里有两个帮助函数 distinct? 和 xor。distinct? 可以判断一个 list 里的元素是否没有重复。xor 是异或，当且仅当它只有一个参数为真时为真。

就能看到三个人的性别，和对另外一些事实的判断。如果你对这个结果的唯一性表示怀疑，可以用

第九章 逻辑问题

第九章

逻辑问题