Abstract NNIL-formulas, introduced by Visser in 1983–1984 in a study of $\varSigma _1$-subsitutions in Heyting arithmetic, are intuitionistic propositional formulas that do not allow nesting of implication to the left. The first results about these formulas were obtained in a paper of 1995 by Visser et al. In particular, it was shown that NNIL-formulas are exactly the formulas preserved under taking submodels of Kripke models. Recently, Bezhanishvili and de Jongh observed that NNIL-formulas are also reflected by the colour-preserving monotonic maps of Kripke models. In the present paper, we first show how this observation leads to the conclusion that NNIL-formulas are preserved by arbitrary substructures not necessarily satisfying the topo-subframe condition. Then, we apply it to construct universal models for NNIL. It follows from the properties of these universal models that NNIL-formulas are also exactly the formulas that are reflected by colour-preserving monotonic maps. By using the method developed in constructing the universal models, we give a new direct proof that the logics axiomatized by NNIL-axioms have the finite model property.

Minimal logic, i.e., intuitionistic logic without the ex falso principle, is investigated in its original form with a negation symbol instead of a symbol denoting the contradiction. A Kripke semantics is developed for minimal logic and its sublogics with a still weaker negation by introducing a function on the upward closed sets of the models. The basic logic is a logic in which the negation has no properties but the one of being a unary operator. A number of extensions is studied of which the most important ones are contraposition logic and negative ex falso, a weak form of the ex falso principle. Completeness is proved, and the created semantics is further studied. The negative translation of classical logic into intuitionistic logic is made part of a chain of translations by introducing translations from minimal logic into contraposition logic and intuitionistic logic into minimal logic, the latter having been discovered in the correspondence between Johansson and Heyting. Finally, as a bridge to the work of Franco Montagna a start is made of a study of linear models of these logics.

This work is concerned with finite identifiability of languages from positive data. We focus on the characterization of finite identifiability [Mukouchi (1992), Lange and Zeugmann (1992)], which uses definite finite tell-tale sets (DFTTs for short), finite subsets of languages which are uniquely characteristic for them. We introduce preset learners, learning functions that explicitly use (collections of) DFTTs, and, in cases where there exist only finitely many DFTTs for each language, strict preset learners which in each case use this whole finite collection. We also introduce the concept of fastest learner, a learner which comes up with the right conjecture on any input string that objectively leaves only the right choice of language. We study the use of minimal DFTTs and their influence on the speed of finite identification. We show that: (a) in the case of finite collections of finite sets—finding a minimal DFTT is polynomial time computable, while finding a minimal-size DFTT is NP-complete; (b) in the general case—finite identifiability, minimal strict preset finite identifiability and fastest finite identifiability are shown to be mutually nonequivalent. In the end we mention the relevance of this work for dynamic epistemic logic.

We investigate fragments of intuitionistic propositional logic containing implication but not disjunction. These fragments are finite, but their size grows superexponentially with the number of generators. Exact models are used to characterize the fragments.

The non-classical, nonmonotonic inference relation associated with the answer set semantics for logic programs gives rise to a relationship of strong equivalence between logical programs that can be verified in 3-valued Gödel logic, G3, the strongest non-classical intermediate propositional logic (Lifschitz et al., 2001). In this paper we will show that KC (the logic obtained by adding axiom $\neg A\vee\neg\neg A$ to intuitionistic logic), is the weakest intermediate logic for which strongly equivalent logic programs, in a language allowing negations, are logically equivalent.

Article Angluin's theorem for indexed families of r.e. sets and applications Share on Authors: Dick de Jongh Institute for Logic, Language and Computation, University of Amsterdam Institute for Logic, Language and Computation, University of AmsterdamView Profile , Makoto Kanazawa Department of Cognitive and Information Sciences, Chiba University Department of Cognitive and Information Sciences, Chiba UniversityView Profile Authors Info & Claims COLT '96: Proceedings of the ninth annual conference on Computational learning theoryJanuary 1996 Pages 193–204https://doi.org/10.1145/238061.238095Published:01 January 1996 26citation267DownloadsMetricsTotal Citations26Total Downloads267Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Abstract A definition is given for formulae A1, …, An in some theory T which is formalized in a propositional calculus S to be (in)dependent with respect to S. It is shown that, for intuitionistic propositional logic IPC, dependency (with respect to IPC itself) is decidable. This is an almost immediate consequence of Pitts’ uniform interpolation theorem for IPC. A reasonably simple infinite sequence of IPC-formulae Fn (p, q) is given such that IPC-formulae A and B are dependent if and only if at least on of the Fn (A, B) is provable.

The intuitionistic propositional logic I has the following (disjunction) property . We are interested in extensions of the intuitionistic logic which are both decidable and have the disjunction property. Systems with the disjunction property are known, for example the Kreisel-Putnam system [1] which is I + (∼ϕ → (ψ ∨ α))→ ((∼ϕ→ψ) ∨ (∼ϕ→α)) and Scott's system I + ((∼ ∼ϕ→ϕ)→(ϕ ∨ ∼ϕ))→ (∼∼ϕ ∨ ∼ϕ). It was shown in [3c] that the first system has the finite-model property. In this note we shall construct a sequence of intermediate logics Dn with the following properties: These systems are presented both semantically and syntactically, using the remarkable correspondence between properties of partially ordered sets and axiom schemata of intuitionistic logic. This correspondence, apart from being interesting in itself (for giving geometric meaning to intuitionistic axioms), is also useful in giving independence proofs and obtaining proof theoretic results for intuitionistic systems (see for example, C. Smorynski, Thesis, University of Illinois, 1972, for independence and proof theoretic results in Heyting arithmetic).