On the degree of complexity of sentential logics. A couple of examples

The first part of the paper is a reminder of fundamental results connected with the adequacy problem for sentential logics with respect to matrix semantics. One of the main notions associated with the problem, namely that of the degree of complexity of a sentential logic, is elucidated by a couple of examples in the second part of the paper. E.g., it is shown that the minimal logic of Johansson and some of its extensions have degree of complexity 2. This is the first example of an exact estimation of the degree of natural complex logics, i.e. logics whose deducibility relation cannot be represented by a single matrix. The remaining examples of complex logics are more artificial, having been constructed for the purpose of checking some theoretical possibilities.The paper was presented to the Polish Philosophical Society, Wrocaw Branch, at its meeting on March 27^th, 1980.The authors wish to thank both the referees of Studia Logica for their helpful and very insightful remarks. Following their criticism, we have been able to improve the style and structure of our presentation. In particular, we are indebted to the referees for pointing out a gap in the original proof of Theorem 2, and we have incorporated into the revised text a corrected proof of step (2.1) which one of them was kind enough to supply in detail.     

On the degree of complexity of sentential logics.II. An example of the logic with semi-negation

In this paper being a sequel to our [1] the logic with semi-negation is chosen as an example to elucidate some basic notions of the semantics for sentential calculi. E.g., there are shown some links between the Post number and the degree of complexity of a sentential logic, and it is proved that the degree of complexity of the sentential logic with semi-negation is 20. This is the first known example of a logic with such a degree of complexity. The results of the final part of the paper cast a new light on the scope of the Kripke-style semantics in comparison to the matrix semantics.In memory of Roman Suszko     

The contraction rule and decision problems for logics without structural rules

This paper shows a role of the contraction rule in decision problems for the logics weaker than the intuitionistic logic that are obtained by deleting some or all of structural rules. It is well-known that for such a predicate logic L, if L does not have the contraction rule then it is decidable. In this paper, it will be shown first that the predicate logic FL_ec with the contraction and exchange rules, but without the weakening rule, is undecidable while the propositional fragment of FL_ec is decidable. On the other hand, it will be remarked that logics without the contraction rule are still decidable, if our language contains function symbols.     

On sentential anagrams: Making sentences out of words

Perception and production of language often have a problem-solving component to them, and this has not been much studied. The present article describes an exploratory approach to some aspects of production which required college students to reorder sentential anagrams. The main finding was that the number of words to be ordered was the greatest influence on performance, whereas little if any influence was exerted by the grammatical variables studied. Although the problem-solving process does not model all language use, it may model the more creative aspect, in which people try to make nonstandard statements. In contrast to a common current view that sentences are holistic, well-formed linguistic objects in mind, the present work emphasizes the developmental and interactive aspect of language production.This work was supported by Grant A7655 from the National, Research Council of Canada and by Leave Fellowship W 760 174 from Canada Council.     

On structural completeness of implicational logics

We consider the notion of structural completeness with respect to arbitrary (finitary and/or infinitary) inferential rules. Our main task is to characterize structurally complete intermediate logics. We prove that the structurally complete extension of any pure implicational in termediate logic C can be given as an extension of C with a certain family of schematically denned infinitary rules; the same rules are used for each C. The cardinality of the family is continuum and, in the case of (the pure implicational fragment of) intuitionistic logic, the family cannot be reduced to a countable one. It means that the structurally complete extension of the intuitionistic logic is not countably axiomatizable by schematic rules.This work was supported by the Polish Academy of Sciences, CPBP 08.15, Struktura logiczna rozumowa niesformalizowanych.     

On structural completeness of many-valued logics

In the paper some consequence operations generated by ukasiewicz's matrices are examined.Allatum est die 6 Maii 1976     

On maximal intermediate predicate constructive logics

We extend to the predicate frame a previous characterization of the maximal intermediate propositional constructive logics. This provides a technique to get maximal intermediate predicate constructive logics starting from suitable sets of classically valid predicate formulae we call maximal nonstandard predicate constructive logics. As an example of this technique, we exhibit two maximal intermediate predicate constructive logics, yet leaving open the problem of stating whether the two logics are distinct. Further properties of these logics will be also investigated.Presented by H. Ono     

On finite linear intermediate predicate logics

An intermediate predicate logicS ₊ ⁿ (n>0) is introduced and investigated. First, a sequent calculusGS _n is introduced, which is shown to be equivalent toS ₊ ⁿ and for which the cut elimination theorem holds. In § 2, it will be shown thatS ₊ ⁿ is characterized by the class of all linear Kripke frames of the heightn.To the memory of the late Professor Iwao Nishimura     

Counterexamples in sentential reasoning

How do logically naive individuals determine that an inference is invalid? In logic, there are two ways to proceed: (1) make an exhaustive search but fail to find a proof of the conclusion and (2) use the interpretation of the relevant sentences to construct a counterexample—that is, a possibility consistent with the premises but inconsistent with the conclusion. We report three experiments in which the strategies that individuals use to refute invalid inferences based on sentential connectives were examined. In Experiment 1, the participants’ task was to justify their evaluations, and it showed that they used counterexamples more often than any other strategy. Experiment 2 showed that they were more likely to use counterexamples to refute invalid conclusions consistent with the premises than to refute invalid conclusions inconsistent with the premises. In Experiment 3, no reliable difference was detected in the results between participants who wrote justifications and participants who did not.     

Some paraconsistent sentential calculi

In [8] Jakowski defined by means of an appropriate interpretation a paraconsistent calculusD ₂ . In [9] J. Kotas showed thatD ₂ is equivalent to the calculusM(S5) whose theses are exactly all formulasa such thatMa is a thesis ofS5. The papers [11], [7], [3], and [4] showed that interesting paraconsistent calculi could be obtained using modal systems other thanS5 and modalities other thanM. This paper generalises the above work. LetA be an arbitrary modality (i.e. string ofM's,L's and negation signs). Then theA-extension of a set of formulasX is {¦A X}}. Various properties ofA-extensions of normal modal systems are examined, including a problem of their axiomatizability     

On detachment-substitutional formalization in normal modal logics

The aim of this paper is to propose a criterion of finite detachment-substitutional formalization for normal modal systems. The criterion will comprise only those normal modal systems which are finitely axiomatizable by means of the substitution, detachment for material implication and Gödel rules.Some results of this paper were announced in the abstract [2].Allatum est die 10 Junii 1976     

Justification logics and hybrid logics

Hybrid logics internalize their own semantics. Members of the newer family of justification logics internalize their own proof methodology. It is an appealing goal to combine these two ideas into a single system, and in this paper we make a start. We present a hybrid/justification version of the modal logic T. We give a semantics, a proof theory, and prove a completeness theorem. In addition, we prove a Realization Theorem, something that plays a central role for justification logics generally. Since justification logics are newer and less well known than hybrid logics, we sketch their background, and give pointers to their range of applicability. We conclude with suggestions for future research. Indeed, the main goal of this paper is to encourage others to continue the investigation begun here.