使用归纳判断给定符号是否在序言中构成有效公式

Question

我们刚刚开始在我的课堂上学习序言，我们的第一个练习如下：

问题：

注：假设只有a、b等两个原子，而不是无穷多个。

a) 编写一个序言程序来翻译命题逻辑公式的归纳定义（即翻译定义 1）。为此，您需要使用：

1.) 一元谓词“at”表示原子公式（因此“at(f)”表示“F 是原子公式”，其中 f 是常数）。

2.) 一元谓词“fmla”表示公式（因此“fmla(F)”表示“F 是一个公式”）。

3.) 一元运算“neg”表示否定（因此“neg(F)”代表 ¬F）。

4.) 二元运算“或”表示两个公式的析取（所以“或（F，G）”代表（F∨G））。

尝试：

    at(a). % Our first atom.
    at(b). % Our second atom.

    fmla(F):-
        at(F).

    neg(F):-
        fmla(F).

    or(F,G):-
        fmla(F), fmla(G).

    fmla(F):-
        or(F,G),
        neg(F),
        fmla(G).

有效公式示例：(~A v B) ---> or(neg(a), b).

我相信我构建程序的方式是正确的，但递归部分不起作用（我在那里也遇到了单例错误）。我试图解决这个问题几个小时但无济于事。任何帮助将不胜感激。

Answer 1

你已经把原子弄对了。现在简单介绍一下命题逻辑公式的归纳定义：

at(a). % Our first atom.
at(b). % Our second atom.

fmla(F):-           % an atom is a formula
    at(F).

fmla(neg(F)) :-     % neg(F) is a formula if F is a formula
    fmla(F).

fmla(or(F,G)) :-    % or(F,G) is a formula if F and G are formulas
    fmla(F),
    fmla(G).

fmla(and(F,G)) :-   % and(F,G) is a formula if F and G are formulas
    fmla(F),
    fmla(G).

如果您尝试用上面的例子查询：

   ?- fmla(or(neg(a), b)).
yes

是否需要合取的最后一条规则取决于您坚持使用哪种归纳定义。有些教科书只使用否定和析取，因为连词可以表示为 and(A,B) = neg(or(neg(A),neg(B))).

使用归纳判断给定符号是否在序言中构成有效公式

Using induction to tell if the given symbols make a valid formula in prolog

prolog

induction