DNF规范化的测试用例:用你的测试用例破坏我的代码

Question

一旦我可以悬赏，我将放弃100分给第一个发明测试用例的海报，打破我将命题逻辑语句规范化为析取范式的常规。我将省略代码，因为它很长，而且您可以将例程视为黑盒。

当一个形式是字面(p, NOT p)合取的析取范式时，它实际上是对CNF的对偶。例子:

(NOT p AND q AND r) OR s OR (NOT t)
p OR q
p OR q OR r OR s OR t
p AND q
p AND q AND r
p
NOT p

,

p AND (q OR r)
p OR (q AND (r OR s))
NOT (p AND q)

不在DNF中。

对于我自己想到的测试用例，我可以把它们分成

• 用DNF中已有的简单公式如:p, NOT p, (p AND q) or r进行烟雾试验;
• .. AND (..OR..)的情况，与或"交换";例如，p AND (q OR r)的dnf可以是(p AND q) OR (p AND r);
• 在树的路径上有两次相同的操作符，即:.. OR ( .. AND ( .. OR .. ));
特别是
• ， .. OR ( .. OR .. )之间没有其他操作符;
• 在公式中不同位置有多个否定，... NOT NOT p, NOT NOT (.. AND ..);
• 公式看起来更像一个树，(.. OR ..) AND (.. AND ..)而不仅仅是一个列表p AND (q AND (r AND ...));
• 操作符有两个以上的操作数(...) AND (p OR q OR r OR s) .

有了这些测试，我对代码做了一些简单的更改。显然是我破坏了代码，因为套件失败了。虽然这意味着我的测试帮助了我，但让我担心的是，只有一个测试发现了问题。这只是一个测试用例，如果我没有，我就会错过一个bug。对于多少个bug，我甚至都没有进行一次测试?

那么，哪些是好的测试用例呢?

Answer 1

考虑使用模糊测试。

1)生成随机语句"((A AND B) OR B)"并通过DNF规范化器传递它们。2)遍历所有可能的输入值(AB=00, 01, 11, 10)，在评估原始表达式和简化后的答案时测试答案。3)如果发现任何不良结果，大声投诉。

唯一棘手的地方是生成随机语句。我会用递归来做。一个简单的第一次传递看起来像这样:

gen_one: return one of "A", "B", "NOT A", "NOT B"
gen_op: return one of "AND", "OR", "NOR", "NAND"
genstatement:
  if rand < 10%
    return gen_one()
  else
    return "(" + genstatement() + gen_op + genstatement() + ")"