A Non-deterministic View on Non-classical Negations

We investigate two large families of logics, differing from each other by the treatment of negation. The logics in one of them are obtained from the positive fragment of classical logic (with or without a propositional constant ff for “the false”) by adding various standard Gentzen-type rules for negation. The logics in the other family are similarly obtained from LJ⁺, the positive fragment of intuitionistic logic (again, with or without ff). For all the systems, we provide simple semantics which is based on non-deterministic four-valued or three-valued structures, and prove soundness and completeness for all of them. We show that the role of each rule is to reduce the degree of non-determinism in the corresponding systems. We also show that all the systems considered are decidable, and our semantics can be used for the corresponding decision procedures. Most of the extensions of LJ⁺ (with or without ff) are shown to be conservative over the underlying logic, and it is determined which of them are not.