The symmetry rule in propositional logic (Q1961453)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The symmetry rule in propositional logic |
scientific article |
Statements
The symmetry rule in propositional logic (English)
0 references
14 February 2000
0 references
The addition of the symmetry rule to the resolution proof system sometimes allows considerable shortening in the length of refutations. An exponential lower bound on the size of resolution refutations using two forms of a global symmetry rule is shown. The paper also discusses the relationship of symmetry rules to the extension rule that allows the use of abbreviative definitions in proofs. Also, symmetry of random clause sets is considered.
0 references
symmetry rule
0 references
exponential lower bound on the size of resolution refutations
0 references
extension rule
0 references
random clause
0 references
0 references