Completeness proofs for propositional logic with polynomial-time connectives

John N. Crossley, Philip J. Scott

    Research output: Contribution to journalArticleResearchpeer-review

    Abstract

    We introduce a conservative extension of propositional calculus which allows conjunctions and disjunctions of variable length. Consistency, completeness and decidability for both classical and intuitionistic systems are given provided some simple conditions on the formation of propositional letters are satisfied. We describe an application to PROLOG programming in the context of databases.

    Original languageEnglish
    Pages (from-to)39-52
    Number of pages14
    JournalAnnals of Pure and Applied Logic
    Volume44
    Issue number1-2
    DOIs
    Publication statusPublished - 9 Oct 1989

    Cite this

    @article{c702b5c063524009b2e1ffd475ac0da7,
    title = "Completeness proofs for propositional logic with polynomial-time connectives",
    abstract = "We introduce a conservative extension of propositional calculus which allows conjunctions and disjunctions of variable length. Consistency, completeness and decidability for both classical and intuitionistic systems are given provided some simple conditions on the formation of propositional letters are satisfied. We describe an application to PROLOG programming in the context of databases.",
    author = "Crossley, {John N.} and Scott, {Philip J.}",
    year = "1989",
    month = "10",
    day = "9",
    doi = "10.1016/0168-0072(89)90044-4",
    language = "English",
    volume = "44",
    pages = "39--52",
    journal = "Annals of Pure and Applied Logic",
    issn = "0168-0072",
    publisher = "Elsevier",
    number = "1-2",

    }

    Completeness proofs for propositional logic with polynomial-time connectives. / Crossley, John N.; Scott, Philip J.

    In: Annals of Pure and Applied Logic, Vol. 44, No. 1-2, 09.10.1989, p. 39-52.

    Research output: Contribution to journalArticleResearchpeer-review

    TY - JOUR

    T1 - Completeness proofs for propositional logic with polynomial-time connectives

    AU - Crossley, John N.

    AU - Scott, Philip J.

    PY - 1989/10/9

    Y1 - 1989/10/9

    N2 - We introduce a conservative extension of propositional calculus which allows conjunctions and disjunctions of variable length. Consistency, completeness and decidability for both classical and intuitionistic systems are given provided some simple conditions on the formation of propositional letters are satisfied. We describe an application to PROLOG programming in the context of databases.

    AB - We introduce a conservative extension of propositional calculus which allows conjunctions and disjunctions of variable length. Consistency, completeness and decidability for both classical and intuitionistic systems are given provided some simple conditions on the formation of propositional letters are satisfied. We describe an application to PROLOG programming in the context of databases.

    UR - http://www.scopus.com/inward/record.url?scp=45349112893&partnerID=8YFLogxK

    U2 - 10.1016/0168-0072(89)90044-4

    DO - 10.1016/0168-0072(89)90044-4

    M3 - Article

    VL - 44

    SP - 39

    EP - 52

    JO - Annals of Pure and Applied Logic

    JF - Annals of Pure and Applied Logic

    SN - 0168-0072

    IS - 1-2

    ER -