使用 prolog 解决逻辑问题

目录

prolog 作为函数式编程中的逻辑编程语言还是非常有特色的,虽然作为通用语言去解决一般问题感觉非常别扭,但是解决一阶逻辑问题却让人感觉非常自然,prolog 非常适合作为解决逻辑问题的 DSL,甚至可以用来构建一个简单专家系统用来分析问题。下面就简单的介绍一下如何用 prolog 解决简单的逻辑问题。

prolog 特色

  使用 prolog 解决问题的最大特色就是,你只需要描述问题,然后问题就可以自动的被求解出来。这其实是一种错觉,实现这种魔法的原理就是你在描述问题的时候, 已经提供了一个有限的问题求解空间,并且你加上了解的约束条件,然后 prolog 做的事就是遍历你给出的解空间,选出满足约束条件的解来。

问题


A、B、C、D、E、F 排成一队。
1. C 在 E 的前面; 
2. A 在 F 的后面;  
3. E 不在第 5 位;  
4. D 和 A 之间隔着两个人;  
5. B 在 E 的后面,并紧挨着 E。  

请问,第 4 位是谁?

prolog 程序

before(A,B) :- A<B.
after(A,B) :- A>B.
notInFifth(A) :- A \= 5.
adjacent(A,B) :- abs(A - B) =:= 1.
separatedByTwo(A,B) :- abs(A - B) =:= 2.


solution(A,B,C,D,E,F) :-
    permutation([1,2,3,4,5,6], [A,B,C,D,E,F]),
    notInFifth(E),
    separatedByTwo(D,A),
    adjacent(B,E),
    before(C,E),
    before(F,A),
    before(E,B).

运行结果

?- solution(A,B,C,D,E,F).
A = 6,
B = 3,
C = 1,
D = 4,
E = 2,
F = 5 ;

所以排列顺序是 C E B D F A,所以答案是 D

总结

  我觉得程序几乎不需要解释,基本上就是对问题的描述,我没有写任何求解的过程,然后就自动得到了我要的答案了,唯一需要动脑筋的地方就是我们需要把自然语言描述的问题,转化为一个数学问题或者说逻辑问题,比如在这个问题中我们就把 A 在 B 前面转化为 A<B,把 A,B 相邻转为 A-B 的绝对值等于 1 等等。

思考题

 有了解决上面问题的经验,现在我们来做一道思考题,题目如下:
A,B,C,D 中有一个人是罪犯
1. A 说 "我不是罪犯".
2. B 说 "D 是罪犯". 
3. C 说 "B 是罪犯".
4. D 说 "我不是罪犯".
已知上面只有一个人说了真话,问谁是罪犯?

思考题答案

solve(K) :-
   member(K,[a,b,c,d]),
   (K\=a->A=1;A=0),
   (K=d->B=1;B=0),
   (K=b->C=1;C=0),
   (K\=d->D=1;D=0),
   A+B+C+D=:=1.

目录