A superredundant clause is a clause that is redundant in the resolution closure of a formula. The converse concept of superirredundancy ensures membership of the clause in all minimal CNF formulae that are equivalent to the given one. This allows for building formulae where some clauses are fixed when minimizing size. An example are proofs of complexity hardness of the problems of minimal formula size. Others are proofs of size when forgetting variables or revising a formula. Most clauses can be made superirredundant by splitting them over a new variable.
翻译:超级冗余条款是一个多余的条款,在公式的解析结束时是多余的。 超冗余的反比概念确保了该条款在与给定公式相当的所有最低CNF公式中的成员资格。 这允许在最小尺寸时在确定某些条款的情况下建立公式。 一个例子是最小公式大小问题的复杂性硬性的证据。 另一些则在忘记变量或修改公式时证明其大小。 多数条款可以通过将其分成一个新的变量而成为超级多余条款 。