创建随机的CNF公式

Question

对于我的论文，我正在研究知识库的特定特性，以及这如何影响论证树的大小。我需要一个我已经拥有的prolog中的SAT求解器，但是我还需要一种创建随机从句的算法。 k-sat表示精确长度k的子句。为简单起见，我将k设置为3，最大4。我想将k（每个条款的文字数量）作为程序的参数。因此，如果我想要一个3个序列，具有1000个条款和300个文字，那么我的程序应创建一个具有100个长度3的知识库，其中所有这些文字都必须随机分散，以一定的负面比例（50） /50为简单起见）。我希望输出看起来像这样，输出：一组随机创建的子句：

v1：-v2，v3。

v2：-v3，-v4。

有人可以帮我吗？

Answer 1

logTalk提供了用户 - 可扩展 nofollow noreferrer“> nutyary nutyary 图书馆和QuickCheck Support在其 lgtunit 开发器工具。您可以同时使用大多数Prolog Systems 。

Answer 2

尝试做类似的事情：

random_knowledge_base(NumberOfClauses,
                      LiteralsPerClause,
                      AmountOfLiterals,
                      Ratio,
                      KnowledgeBase) :-
    length(KnowledgeBase, NumberOfClauses),
    maplist(random_clause(LiteralsPerClause, AmountOfLiterals, Ratio), KnowledgeBase).

random_clause(LiteralsPerClause, AmountOfLiterals, Ratio, Head :- Body) :-
    randseq(LiteralsPerClause, AmountOfLiterals, [Number|Numbers]),
    atom_concat(p, Number, Head),
    maplist(literal(Ratio), Numbers, Literals),
    comma_list(Body, Literals).

literal(Ratio, Number, Literal) :-
    atom_concat(p, Number, Proposition),
    (   maybe(Ratio)
    ->  Literal = Proposition
    ;   Literal = -Proposition ).

示例：

?- random_knowledge_base(5, 3, 9, 0.7, B).
B = [(p2 :- p5, -p6),  (p8 :- p3, p6),  (p9 :- p7, p2),  (p4 :- -p1, p6),  (p8 :- p1, p9)].

代码的详细说明

• ISO谓词 atom_concat/3 condentes两个原子形成第三个原子：

?- atom_concat(p, 2, A).
A = p2. 

• predicate 也许/1 概率 p 成功，概率为1- p ：

?- maybe(0.5).
true.

?- maybe(0.5).
false.

• a形式的目标（条件 - ＆gt; ）作为条件语句的工作：

?- (maybe(0.5) -> writeln(positive) ; writeln(negative)).
negative
true.

?- (maybe(0.5) -> writeln(positive) ; writeln(negative)).
positive
true.

• 例如，目标字面（0.5，1，l）随机生成字面p1或- p1：

?- literal(0.5, 1, L).
L = -p1.

?- literal(0.5, 1, L).
L = p1.

• 要在范围1 .. m 中选择 k ，我们可以使用 randseq/3 。对于 k = 3和 m = 5，我们必须：

?- randseq(3, 5, Ns).
Ns = [4, 5, 2].

?- randseq(3, 5, Ns).
Ns = [1, 3, 2].

• 将 k 任意整数的列表转换为 k <> k <> k < /em>对应的文字，我们可以使用 mapList/3 ：

?- randseq(3, 5, Ns), maplist(literal(0.5), Ns, Ls).
Ns = [1, 3, 5],
Ls = [p1, p3, p5].

• 谓词 comma_list/2 可以使用将文字列表转换为一个连词：

?- randseq(3, 5, Ns), maplist(literal(0.5), Ns, Ls), comma_list(B, Ls).
Ns = [1, 5, 3],
Ls = [p1, p5, p3],
B =  (p1, p5, p3).

?- randseq(3, 5, Ns), maplist(literal(0.5), Ns, Ls), comma_list(B, Ls), C = (p3 :- B).
Ns = [1, 4, 2],
Ls = [-p1, p4, -p2],
B =  (-p1, p4, -p2),
C =  (p3 :- -p1, p4, -p2).

• 将其整体放在一起，我们有peadicate rando_clause/4：

?- random_clause(3, 4, 0.5, C).
C =  (p3 :- p4, -p2).

?- random_clause(3, 4, 0.5, C).
C =  (p1 :- -p5, p4).

以例如4个条款来创建一个随机知识基础：

?- length(KB, 4).
KB = [_, _, _, _].

?- length(KB, 4), maplist(random_clause(3,5,0.5), KB).
KB = [(p2 :-p1, -p3),  (p5 :-p2, p3),  (p3 :- -p4, p5),  (p3 :- -p1, p4)].

或者，使用predenate randoge> randoge_knwoLEDGE_BASE /5：

?- random_knowledge_base(4, 3, 5, 0.5, KB).
KB = [(p1 :- -p4, -p5),  (p2 :- p3, p4),  (p2 :-p3, -p5),  (p3 :- -p1, -p4)].