Completeness proofs for propositional logic with polynomial-time connectives

John N. Crossley; Philip J. Scott

doi:10.1016/0168-0072(89)90044-4

Completeness proofs for propositional logic with polynomial-time connectives

Research output: Contribution to journal › Article › Research › peer-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 language	English
Pages (from-to)	39-52
Number of pages	14
Journal	Annals of Pure and Applied Logic
Volume	44
Issue number	1-2
DOIs	https://doi.org/10.1016/0168-0072(89)90044-4
Publication status	Published - 9 Oct 1989

Access to Document

10.1016/0168-0072(89)90044-4

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 = oct,

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

}

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

AN - SCOPUS:45349112893

SN - 0168-0072

VL - 44

SP - 39

EP - 52

JO - Annals of Pure and Applied Logic

JF - Annals of Pure and Applied Logic

IS - 1-2

ER -

Completeness proofs for propositional logic with polynomial-time connectives

Abstract

Access to Document

Other files and links

Cite this