Abstract The idea of treating negation as a modality manifests itself in various logical systems, especially in Došen’s propositional logic $\textsf {N}$, whose negation is weaker than that of Johansson’s minimal logic. Among the interesting extensions of $\textsf {N}$ are the propositional logics $\textsf {N}^{\ast }$ and $\textsf {Hype}$; the former was proposed in Cabalar et al. (2006, Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning, 25–36), while the latter has recently been advocated in Leitgeb (2019, J. Philos. Logic, 48, 305–405), but was first introduced in Moisil (1942, Disquisitiones Math. et Phys., 2, 3–98). I shall develop predicate versions of $\textsf {N}$ and $\textsf {N}^{\ast }$ and provide a simple Routley-style semantics for the predicate version of $\textsf {Hype}$. The corresponding strong completeness results will be proved by means of a useful general technique. It should be remarked that this work can also be seen as a starting point for the investigation of intuitionistic predicate modal logics.

In this article we describe a bunch ofprobability logics with quantifiers over events, and develop primary techniques for proving computational complexity results (in terms ofm-degrees) about these logics, mainly over discrete probability spaces. Also the article contains a comparison with some other probability logics and a discussion of interesting analogies with research in the metamathematics of Boolean algebras, demonstrating a number of attractive features and intuitive advantages of the present proposal.

Many important achievements of formal logic have been concerned with the discovery of incomputability—and thus firmly rooted in the undecidability of the halting problem and its complement. Also, the latter produce influental examples of Σ10 - and Π10 -complete sets, in modern terminology. Changing the focus from modelling computations to measuring complexity of theories, the article describes how to obtain Σ10 - and Π10 -completeness results for a wide range of fragments of theories in a very uniform way, and the reasoning will employ the following concepts. Let σ be a first-order signature and Valσ the collection of all valid σ -sentences. For C∈{Π10,Σ10} , call a set Γ of σ -sentences hereditarilyC-complete iff for any C -set Δ , whenever Valσ∩Γ⊆Δ⊆Γ , then Δ is C -complete. Both notions are closely connected with that of being hereditarily undecidable, but unlike their common predecessor, serve the purpose of getting computational complexity results, via employing the two most fundamental levels of the arithmetical hierarchy. This article presents major tools and main examples in the study of hereditary Π10 - and Σ10 -completeness, with a discussion of various applications.

In the present article, the quantifiers over propositions are first introduced into the language for reasoning about probability, then the complexity issues for validity problems dealing with the corresponding hierarchy of probabilistic sentences are investigated. We prove, among other things, the Π11-completeness for the general validity and also indicate the least level in the hierarchy for which the validity problem is undecidable.