Skip to main content
SpringerLink
Log in

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

  • Published:
Studia Logica Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. S. L. Bloom andR. Suszko,Investigations into the sentential calculus with identity,Notre Dame Journal of Formal Logic 13 (1972), pp. 289–308.

    Google Scholar 

  2. E. Capińska,On standard consequence operations in the implicational language,Bulletin of the Section of Logic 8 (1979), pp. 202–205.

    Google Scholar 

  3. Dov M. Gabbay,Semantic proof of the Craig interpolation theorem for intuitionistic logic and extensions. Part I. in:Logic Colloquium '69, edited by R. O. Gandy and C. M. E. Yates, North-Holland Publ. Co., Amsterdam 1971, pp. 391–401.

    Google Scholar 

  4. E. Graczyńska andA. Wroński,Constructing denumerable matrices strongly adequate for pre-finite logics,Studia Logica 33 (1974), pp. 417–423.

    Google Scholar 

  5. J. Hawranek,A matrix strongly adequate for S5 with MP and RN,Bulletin of the Section of Logic 9 (1980), pp. 122–124.

    Google Scholar 

  6. L. L. Maksimova,The principle of separation of variables in sentential logics (in Russian),Algebra i Logika 15 (1976), pp. 168–184.

    Google Scholar 

  7. J. Łoś andR. Suszko,Remarks on sentential logics,Indagationes Mathematicae 20 (1958), pp. 177–183.

    Google Scholar 

  8. J. Perzanowski andA. Wroński,The deduction theorems for the system of Feys-von Wright,Zeszyty Naukowe Uniwersytetu Jagiellońskiego. Prace z logiki 6 (1971), pp. 11–14.

    Google Scholar 

  9. K. Segerberg,Propositional logics related to Heyting's and Johansson's,Theoria 34 (1968), pp. 26–61.

    Google Scholar 

  10. D. J. Shoesmith andT. Smiley,Deducibility and many-valuedness,The Journal of Symbolic Logic 36 (1970), pp. 610–622.

    Google Scholar 

  11. R. Suszko,Adequate models for the non-Fregean sentential calculus (SCI), in:Logic, language, and probability. A selection of papers contributed to sections IV, VI, and XI of the Fourth International Congress for Logic, Methodology, and Philosophy of Science, Bucharest, September 1971, Edited by Radu J. Bogdan and Ilkka Niiniluoto, D. Reidel Publ. Co., Dordrecht, 1973, pp. 49–54.

    Google Scholar 

  12. M. Tokarz,The existence of matrices strongly adequate for E, R and their fragments,Studia Logica 38 (1979), pp. 75–85.

    Google Scholar 

  13. R. Wójcicki,Some remarks on the consequence operation in sentential logics,Fundamenta Mathematicae 58 (1970), pp. 269–279.

    Google Scholar 

  14. R. Wójcicki,Investigations into methodology of sentential calculi I, Institute of Philosophy and Sociology, Polish Academy of Science, Warsaw 1971, 77 pp. (Mimeographed).

    Google Scholar 

  15. A. Wroński,On cardinalities of matrices strongly adequate for the intuitionistic propositional logic,Reports on Mathematical Logic 3 (1974), pp. 67–72.

    Google Scholar 

  16. S. Zachorowski,Proof of a conjecture of Roman Suszko,Studia Logica 34 (1975), pp. 253–256.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Polish Academy of Sciences, Institute of Philosophy and Sociology, The Section of Logic, Szewska 36, 50-139, Wrocław, Poland

    Jacek Hawranek & Jan Zygmunt

Authors
  1. Jacek Hawranek
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jan Zygmunt
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

The paper was presented to the Polish Philosophical Society, Wrocław Branch, at its meeting on March 27th, 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.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hawranek, J., Zygmunt, J. On the degree of complexity of sentential logics. A couple of examples. Stud Logica 40, 141–153 (1981). https://doi.org/10.1007/BF01874705

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01874705

Keywords

Search

Navigation