Correspondence Analysis for Some Fragments of Classical Propositional Logic

In the paper, we apply Kooi and Tamminga’s correspondence analysis (that has been previously applied to some notable three- and four-valued logics) to some conventional and functionally incomplete fragments of classical propositional logic. In particular, the paper deals with the implication, disjunction, and negation fragments. Additionally, we consider an application of correspondence analysis to some connectiveless fragment with certain basic properties of the logical consequence relation only. As a result of the application, one obtains a sound and complete natural deduction system for any binary extension of each fragment in question. With the focus on exclusive disjunction we comparatively study the proposed systems. Finally, we discuss Segerberg’s systems for connectiveless and negation fragments and compare them with our systems.

1. We come back to this issue in Sect. 5, where we compare Segerberg’s approach and ours, since Segerberg, as we did, considered classical logic. Let us notice that Kooi and Tamminga do not mention Segerberg’s work.

2. For the purpose of this paper, we don’t treat conjunction (\( \wedge \)) as a primitive. However, correspondence analysis works with conjunction, too.

3. Note the inference schemata for \( f_\circ (0,1)=0 \), \( f_\circ (1,0)=0 \), \( f_\circ (1,1)=0 \), and \( f_\circ (1,1)=1 \) are the same as in Theorem 2.1 while the rest ones are different. This fact is essential for the proof of Theorem 4.13 (Completeness) below.

4. Note case \( f_\circ (0,0)=1 \) below clearly indicates some extensions contain tautologies that isn’t the case for the other correspondence analyses in this paper. It doesn’t imply they don’t contain tautologies (in fact, they do, e.g. the implication fragment contains Peirce’s law; see Sect. 3.1 below). However, correspondence analysis for the disjunction fragment shows the existence of tautologies in some of its extensions explicitely.

5. The reader will find some similarities with Kalmár’s folklore conditions in the equivalences below. However, the difference is that Kalmár’s conditions are usually expressed via some implicational formulae (see, for example, [17]).

6. The rule (EEM) is inspired by a formula \( A\vee (A\rightarrow B) \) (see Definition 4.4 which will clarify it) to have been known as the extended law of excluded middle [19, p. 17]. Note by adding \( A\vee (A\rightarrow B) \) or Peirce’s law \( ((A\rightarrow B)\rightarrow A)\rightarrow A \) to intuitionistic logic one obtains classical logic [19, p. 18]. To be sure, there are other formulae which give the same result (for example, it is a folklore about the law of double negation elimination \( \lnot \lnot A\rightarrow A \) and the law of excluded middle \( A\vee \lnot A \)). We stress, however, that despite some laws discussed in this footnote contain disjunction or negation the rules of the natural deduction system for the implication fragment contain implication only.

7. Though the symbol \( \veebar \) isn’t in the languages of this paper, we will use it for the human-friendliness of the presentation.

8. This example is a kind of introduction rule for exclusive disjunction and may be viewed as an analogue of one of the well-known introduction rules for inclusive disjunction: \(\frac{p}{p\vee q}\).

9. We remind the reader that “\( \Rightarrow \)” in Theorem 2.3 turns out to be the usual assertion of a subderivation in the formulation of some rules of this natural deduction system (see the beginning of Sect. 2.2 above).

10. To be sure, there are deductively equal alternatives to these rules. We pick up this pair of rules as the most convenient for our completeness proof. The rule (EM) is inspired by the law of excluded middle \( A\vee \lnot A\) (see Definition 4.3 which will clarify it) and the rule (EFQ) is Ex Falso Quodlibet.

11. Note we adapt this Definition to the rule of extended excluded middle (EEM) while Definition 4.3 is adapted to the rule of excluded middle (EM). Since non-trivial theories which are defined in Definition 4.3 are called maximal ones, so non-trivial theories which are defined in Definition 4.4 are said to be extended maximal ones.

12. We acknowledge, however, that in [8] the authors do not claim that Segerberg’s ideas could not be extended to n-valued logic without their reduction.

We would like to thank the first reviewer for the valuable suggestions. The second author thanks Xenia Shliakhtina for the everlasting inspiration.

Authors and Affiliations

1. University of Lodz, Lindleya 3/5, 90-131, Lodz, Poland

   Yaroslav Petrukhin

2. Lomonosov Moscow State University, Lomonosovsky prospekt 27-4, 119991, Moscow, Russia

   Vasilyi Shangin

Corresponding author

Correspondence to Yaroslav Petrukhin.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The first author is supported by Polish National Science Centre, Grant Number DEC-2017/25/B/HS1/01268. The second author is supported by RFBR, Grant Number 20-011-00698 A.

Reprints and permissions