scientific article; zbMATH DE number 4114609
[For the entire collection see Zbl 0666.00011.] Let F be the set of propositional calculus formulae constructed by means of \(\wedge\), \(\vee\), \(\neg\) and the variables \(x_ i\). Every consistent and tautologically closed subset \(T\varsubsetneq F\) is called a theory. A set \(M\subseteq N\) is said to be a model for a formula \(f\in F\) if \(f(C^ M(1),C^ M(2),...,C^ M(n))=1\), where \(C^ M\) is the characteristic function of M. Let \(\nu\) be a Gödel numbering of F and \(\nu^{-1}(f)\) be the number of f in this numbering. By \(T^*_ R\) denote the set \(\{\nu^{- 1}(f)|\) \(f\in F\) \& \(R\vDash f\}\) and let \(S'\) (S) be the set of all (finite) binary sequences (so \(C^ M\in S')\). Supposing that S is ordered lexicographically, for \(n\in {\mathbb{N}}\) let \(\mu (n)=\sigma\) if \(\sigma\) is the n-th element of this ordering. The author investigates some relationships between \(T^*_ M\), M and several related sets with respect to different reducibilities. Among other results he shows that m-degrees of hereditary sets (and only these sets) are m-degrees of theories. There exists a recursive theory which has only one nonrecursive complete extension. The author suggests to describe a family of sets which can be models for recursive theories having unique nonrecursive complete extensions.
- scientific article; zbMATH DE number 3995647
- scientific article; zbMATH DE number 65760
- The Complexity of Propositional Proofs
- The Complexity of Propositional Proofs
- scientific article; zbMATH DE number 1860672
- scientific article; zbMATH DE number 1156870
- scientific article; zbMATH DE number 1390276
- Complexity of Propositional Independence and Inclusion Logic
- Propositional logics complexity and the sub-formula property
- The complexity of propositional implication
- The complexity of Gentzen systems for propositional logic
- Possibilistic logic: Complexity and algorithms
- Complexity Classifications for Logic-Based Argumentation
- scientific article; zbMATH DE number 5599076 (Why is no real title available?)
- The metatheory of the classical propositional calculus is not axiomatizable
- scientific article; zbMATH DE number 2063839 (Why is no real title available?)
- A note on the complexity of propositional Hoare logic
- Complexity of hyperconcepts
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4729773)