Completeness proofs for propositional logic with polynomial-time connectives

John N. Crossley, Philip J. Scott

    Research output: Contribution to journalArticleResearchpeer-review


    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
    Issue number1-2
    Publication statusPublished - 9 Oct 1989

    Cite this