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
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references