Expressive completeness and decidability
This short paper first addresses the question of under what conditions of a finite set of (2-valued) truth functional connectives, it is decidable whether that set is expressively complete. The authors first prove a theorem, due to Post, setting truth-table conditions on connectives in the set. They also prove a theorem on the degree of formulae generated by these connectives. Finally, after a short discussion on the Turing representation of truth-functional connectives, they show that ``there is no effective procedure that, given a recursive specification of a finite set of connectives, decides whether the set is expressivley complete.
- Expressive completeness through logically tractable models
- Complexity, decidability and completeness
- Completeness and Decidability in Sequence Logic
- scientific article; zbMATH DE number 4059375
- scientific article; zbMATH DE number 1497801
- Expressiveness and the completeness of Hoare's logic
- Model completeness and relative decidability
- Completeness in Proof-Theoretic Semantics
- On completeness of logic programs
- scientific article; zbMATH DE number 1169382
- Completeness proofs for propositional logic with polynomial-time connectives
- Completeness and Decidability in Sequence Logic
- scientific article; zbMATH DE number 4059375 (Why is no real title available?)
- scientific article; zbMATH DE number 107724 (Why is no real title available?)
- Syntactic Completeness of Proper Display Calculi
- Complexity, decidability and completeness
This page was built for publication: Expressive completeness and decidability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2277437)
