{'fraction_non_alphanumeric': 0.052530592017484785, 'fraction_numerical': 0.012084323417665223, 'mean_word_length': 4.132924602139316, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 47, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Modular many-valued semantics for combined logics

We obtain, for the first time, a modular many-valued semantics for combined logics, which is built directly from many-valued semantics for the logics being combined, by means of suitable universal operations over partial non-deterministic logical matrices. Our constructions preserve finite-valuedness in the context of multiple-conclusion logics whereas, unsurprisingly, it may be lost in the context of single-conclusion logics. Besides illustrating our constructions over a wide range of examples, we also develop concrete applications of our semantic characterizations, namely regarding the semantics of strengthening a given many-valued logic with additional axioms, the study of conditions under which a given logic may be seen as a combination of simpler syntactically defined fragments whose calculi can be obtained independently and put together to form a calculus for the whole logic, and also general conditions for decidability to be preserved by the combination mechanism.


Introduction
Modularly putting together logics, or their fragments, namely by joining corresponding calculi, while keeping control of the metatheoretic properties induced and, in particular, of the resulting underlying semantics, is the core idea of the general mechanism for combining logics known as fibring [38,40,65,18,25,24]. Given its fundamental character and abstract formulation, this mechanism is a key ingredient of the general theory of universal logic [12,14]. Further, due to its compositional nature, a deep understanding of combined logics is crucial for the construction and analysis of complex logics, a subject of ever growing importance in application fields (see [37], for instance). Given logics L 1 and L 2 , fibring combines them into the smallest logic L 1 • L 2 on the combined language which extends both L 1 and L 2 . This simple idea, however, is far from well understood, to date, despite the long track of work on the subject. An interesting running example of the difficulties at hand consists of the combination of the conjunction-only and disjunction-only fragments of classical logic, which does not coincide with its conjunction-disjunction fragment (see, for instance, [15,21,46]), and which we will also address.
To date, we have many interesting general results regarding conservativity, decidability, finite model properties, or interpolation, as well as soundness and completeness preservation with respect to different forms of symbolic calculi [39,23,67,68,34,10,18,25,60,65,76,30,63,51,52] for combined logics, but there is no generally usable tool support for the obtained logics, due mainly to the absence of a satisfactory semantic counterpart of fibring that naturally relates models of the component logics with models of the combined logic. With the honorable exception of fusion of modal logics [70,74,41,35,48], a very particular case of fibring, the available general semantics for combined logics, so far, are either not constructible from the semantics of the component logics [76,67,60] (due to the use of fullness assumptions), or use highly uncommon semantic structures [66,63].
For these reasons, general fibred semantics is still an open problem: how to combine, in the general case, the semantics M 1 (adequate for logic L 1 ) and M 2 (adequate for logic L 2 ) into a semantics M 1 ⋆ M 2 built directly from M 1 and M 2 , providing an adequate semantics for L 1 • L 2 ? We have known for some time that this question is far from straightforward. Namely, when taking logical matrices as models, as is most common, we know that combining two logics, each given by a single finite matrix, can result in a logic that cannot even be given by a finite set of finite matrices, nor by a single matrix, even if infinite [52,22]. This fact led us to considering non-deterministic logical matrices (Nmatrices), as introduced by Avron and coauthors [4,5], and in [53] we understood how this expressive gain could solve the problem in a neat way, but just for disjoint combinations, that is, when the logics being combined do not share any connectives.
In this paper, finally, we define a simple and usable general semantics for combined propositional-based logics. We do so by further enriching our semantic structures with partiality, and adopting partial non-deterministic logical matrices (PNmatrices), as introduced in [8]. As we shall see, the added expressivity brought by partiality is crucial not just in keeping our semantic structures as compact as possible, but mostly in dealing with shared language. Our work has an additional fundamental ingredient. We consider a very enlightening step forward from traditional Tarski-style Set × Formula single-conclusion consequence relations (see [73]) to Scott-like Set×Set multiple-conclusion consequence relations as introduce in [64]. This abstraction really sheds new light into the overall problem, as shall be made clear.
We will thus show that semantics for combined logics can always be obtained in the form of a PNmatrix obtained directly from given PNmatrices characterizing the original logics. Further, the resulting semantics will be finite as long as the given PNmatrices are finite, at least in the setting of multiple-conclusion logics. The connections between single-conclusion and multiple-conclusion consequence relations (see [69]) are fundamental, at this point, in understanding how much more demanding it is to obtain a similar result in the single-conclusion setting, where indeed finiteness may be lost.
Our approach is anchored on the observation that semantics, be they given by means of matrices, Nmatrices, or PNmatrices, are simply clever ways of defining suitable collections of bivaluations (see [13]). Since a collection of bivaluations characterizes in a unique way a multiple-conclusion logic (see [69]), it is relatively simple to express the combination of multiple-conclusion logics in terms of bivaluations. Then, we just need to come up with a matching construction over PNmatrices, generalizing the finiteness-preserving strict-product operation proposed in [53]. The single-conclusion case is harder, simply because the characterization of a Tarskistyle consequence in terms of bivaluations is no longer unique. The situation can be restored, however, when the collection of bivaluations is meet-closed, once we consider a simple (though not finiteness-preserving) corresponding operation over PNmatrices. Furthermore, we show that the constructions above enjoy universal properties, consistent with the definition of L 1 •L 2 as the least logic that extends L 1 and L 2 , as advocated in [65,18]. Besides providing a range of meaningful concrete examples, we also explore three concrete applications of the semantic characteri-zations obtained, which can be seen as relevant contributions in their own right: a semantic characterization of logics obtained by imposing new axioms to a given many-valued logic (with some perhaps surprising consequences, such as a denumerable semantics for intuitionistic propositional logic); an analysis of when and how to split a logic into syntactical fragments whose combination is the original logic, as a method for obtaining a calculus for a given many-valued logic by putting together axiomatizations for simpler syntactic fragments; and some general, preliminary, results on the preservation of decidability when combining logics.
The rest of the paper is organized as follows. In Section 2 we recall the necessary notions, namely regarding logics, their syntax, semantics and calculi, and define the relevant notions regarding combined syntax and combined logics, along with examples illustrating the particularites both of single-conclusion versus multipleconclusion consequence, and of partiality and non-determinism. The section is a bit long, but the reader can browse through faster, and come back for details when necessary. Section 3 is devoted to the main contributions of the paper, namely the semantic characterization of combined logics in terms of bivaluations, and PNmatrices, first in the multiple-conclusion setting and then in the more complex singleconclusion scenario, by means of simple strict-product and ω-power operations on PNmatrices. Section 4, then, shows that the characterizations previously obtained enjoy natural universal properties. Section 5 showcases the three mentioned applications of our characterization, including some relevant important contributions by themselves. The paper concludes, in Section 6, with a summary of the results obtained, their implications, and an outlook of further research.

Logics and their combination
We start by introducing our main objects of interest, fixing notation, and setting up the technical framework necessary for studying the semantics of combined logics, as well as of their associated calculi and semantics.

Syntax
The syntax of a (propositional) logic is defined, as usual, by means of a signature, an indexed family Σ = {Σ (n) } n∈N0 of denumerable sets where each Σ (n) contains all allowed n-place connectives, and an infinite denumerable set P of variables (which we consider fixed once and for all). As standard, L Σ (P ) denotes the set of all formulas 1 constructed from the variables in P using the connectives in Σ. We will use p, q, r, . . . to denote variables, A, B, C, . . . to denote formulas, and Γ, ∆, Θ, . . . to denote sets of formulas, in all cases, possibly, with annotations.
We use var(A), sub(A), hd(A) to denote, respectively, the set of variables occurring in A, the set of subformulas of A, and the head constructor of A, given a formula A ∈ L Σ (P ). These notations have simple inductive definitions: var(p) = sub(p) = {p}, and hd(p) = p for p ∈ P ; and if c ∈ Σ (n) and A 1 , . . . , A n ∈ L Σ (P ), var(c(A 1 , . . . , A n )) = n i=1 var(A i ), sub(c(A 1 , . . . , A n )) = {c(A 1 , . . . , A n )} ∪ n i=1 sub(A i ), and hd(c(A 1 , . . . , A n )) = c. These notations extend to sets of formulas in the obvious way.
As we will consider combined logics, with mixed syntax, we need to consider different signatures, as well as relations and operations between signatures. Signatures being families of sets, the usual set-theoretic notions can be smoothly extended to signatures. We will sometimes abuse notation, and confuse a signature Σ with the set ( n∈N0 Σ (n) ) of all its connectives, and write c ∈ Σ when c is some n-place connective c ∈ Σ (n) . For this reason, the empty signature, with no connectives at all, will be simply denoted by ∅.
For both types of logics (we will use ∝ as a placeholder for either a multipleconclusion ⊲ or a single-conclusion ⊢), it is well-known that the logics with a common signature form a complete lattice (under the inclusion ordering on the consequence relations), as in both cases it is relatively straightforward to check that intersections of consequence relations are consequence relations (see [73,69]). These facts make it relatively easy to enrich the signature of a logic. Namely, if Σ 0 ⊆ Σ and Σ 0 , ∝ 0 is a logic then the extension of Σ 0 , ∝ 0 to Σ, denoted by Σ, ∝ Σ 0 , is the least logic (of the same type) with signature Σ such that ∝ 0 ⊆ ∝ Σ 0 . It is relatively simple to see that ∝ Σ 0 = σ:P →L Σ (P ) σ(∝ 0 ) = unskel(∝ 0 ). Just note that for each substitution σ : P → L Σ (P ) we have that (skel • σ) : P → L Σ0 (P ) is also a substitution, and also unskel •(skel • σ) = σ. The fact that skel, unskel are bijections make it straightforward to show that ∝ Σ 0 is indeed a consequence relation of the correct type.

Calculi
Logics are often defined by syntactic means, using symbolic calculi. Again, we will consider multiple as well as single-conclusion calculi.
A multiple-conclusion calculus is pair Σ, R where Σ is a signature, and R ⊆ ℘(L Σ (P )) × ℘(L Σ (P )) is a set of (schematic) (multiple-conclusion) inference rules, each rule Γ, ∆ ∈ R being usually represented as Γ ∆ where Γ is the set of premises and ∆ the set of conclusions of the rule, also represented as A1 ... An B1 ... Bm when Γ = {A 1 , . . . , A n } and ∆ = {B 1 , . . . , B m }. We can easily associate a multiple-conclusion logic Σ, ⊲ R to a given calculus Σ, R by means of a suitable tree-shaped notion of derivation (see [69,54,19]). For the purpose of this paper, however, it is sufficient to characterize Σ, ⊲ R as the least multiple-conclusion logic such that R ⊆ ⊲ R , being compact when the rules in R all have finite sets of premises and conclusions.
A single-conclusion calculus is pair Σ, R where Σ is a signature, and R ⊆ ℘(L Σ (P )) × L Σ (P ) is a set of (schematic) (single-conclusion) inference rules, each rule Γ, A ∈ R being usually represented as Γ A where Γ is the set of premises and A the conclusion of the rule. It is clear that single-conclusion calculi can be rephrased as particular cases of multiple-conclusion calculi, namely those whose rules all have singleton sets of conclusions, and that the corresponding notion of derivation will now be linear-shaped, and coincide with the usual notion of proof in Hilbert-style calculi, giving rise to an associated single conclusion logic Σ, ⊢ R . Again, in any case, Σ, ⊢ R is the least single-conclusion logic such that R ⊆ ⊢ R , and again it is finitary if all the rules in R have finitely many premises. In that case, if we use R for both a single conclusion-calculus and its singleton-conclusion multiple-conclusion rephrasal, it is straightforward to see that Σ, ⊲ R = min( Σ, ⊢ R ).
Combining calculi at this level is quite simple, as has been known for a long time in the single-conclusion case [17]. The logic associated to joining the rules of two calculi is precisely the combination of the logics defined by each calculi.
For simplicity, whenever ∝ = ∝ R (in either the single or the multiple-conclusion scenarios), we will say that R constitutes an axiomatization of the logic Σ, ∝ .

Semantics
Another common way of charactering logics is by semantic means. For their universality we shall consider logical matrices, but will consider an extension of the usual notion which also incorporates two less common ingredients: non-determinism and partiality, following [4,8]. These two ingredients play essential roles in our forthcoming results.
A partial non-deterministic matrix (PNmatrix) is a pair Σ, M where Σ is a signature, and M = V, D, · M is such that V is a set (of truth-values), D ⊆ V is the set of designated values, and for each n ∈ N 0 and c ∈ Σ (n) , · M provides the truth-table c M : V n → ℘(V ) of c in M. When appropriate we shall refer to M as a Σ-PNmatrix. When c M (x 1 , . . . , x n ) = ∅ for all x 1 , . . . , x n ∈ V we say that the truth-table of c in M is total. When c M (x 1 , . . . , x n ) has at most one element for all x 1 , . . . , x n ∈ V we say that the truth-table of c in M is deterministic. When all the truth-tables are total, we say that Σ, M is also total, or equivalently that it is a non-deterministic matrix (Nmatrix). Analogously, when all the truth-tables are deterministic, we say that Σ, M is also deterministic, or equivalently that it is a partial matrix (Pmatrix). Finally, if Σ, M is total and deterministic we say that it is simply a matrix (the usual notion of a logical matrix, up to an isomorphism).
A M-valuation is a function v : ) for every n ∈ N 0 , every n-place connective c ∈ Σ, and every A 1 , . . . , A n ∈ L Σ (P ). We denote the set of all M-valuations by Val(M).
As is well known, if Σ, M is a matrix then every function f : Q → V with Q ⊆ P can be extended to a M-valuation (in an essentially unique way for all formulas A with var(A) ⊆ Q). When M is a Nmatrix, a function f as above can possibly be extended in many different ways. Still, we know from [4] that a function f : Γ → V with Γ ⊆ L Σ (P ) can be extended to a M-valuation provided that sub(Γ) ⊆ Γ and that f (c(A 1 , . . . , A n )) ∈ c M (f (A 1 ), . . . , f (A n )) whenever c(A 1 , . . . , A n ) ∈ Γ. We dub such a function a prevaluation of the PNmatrix M. In case M is not total, in general, one does not even have such a guarantee [8], unless f (Γ) ∈ T M = v∈Val(M) ℘(v(L Σ (P ))). In other words, given X ⊆ V , we have X ∈ T M if the values in X are all together possible in some valuation of M. Of course, c M (x 1 , . . . , Given a signature Σ, a bivaluation is a function b : L Σ (P ) → {0, 1}. The set of all such bivaluations is denoted by BVal(Σ). A set of bivaluations B ⊆ BVal(Σ) is known to characterize a multiple-conclusion relation ⊲ B ⊆ ℘(L Σ (P )) × ℘(L Σ (P )) defined by Γ ⊲ B ∆ when, for every b ∈ B, either 0 ∈ b(Γ) or 1 ∈ b(∆). Of course, B also characterizes the more usual single conclusion relation A PNmatrix Σ, M with M = V, D, · M easily defines a set of induced bivaluations, closed for substitutions, namely ∈ D, simply captures the distinction between designated and undesignated values. We will write ∝ M instead of ∝ BVal(M) , and say that Σ, ∝ M is the type-conclusion logic characterized by M, for type ∈ {single, multiple}, which is always compact (finitary) when V is finite. Clearly, sing( Σ, ⊲ M ) = Σ, ⊢ M .
Note that if Γ, ∆ is a maximal consistent theory-pair of Σ, ⊲ M then there must exist b ∈ BVal(M) such that b −1 (1) = Γ, and consequently also b −1 (0) = ∆. In the single-conclusion case, it is well-known that if Γ is a relatively maximal theory of Σ, ⊢ M then there must also exist b ∈ BVal(M) such that b −1 (1) = Γ (see [69]).
When Σ 0 , M 0 is a PNmatrix it is very easy, making essential use of non-determinism, to define a PNmatrix Σ, M Σ 0 that characterizes the extension to Σ of the logic characterized by M 0 .
Our work in the next Section of the paper is to prove results that enable us to describe the semantics of the combination of logics characterized by (P)(N)matrices, analogous to Proposition 2. Before tackling these problems, it is certainly useful to ground all the relevant notions to concrete illustrative examples.

Illustrations
In this subsection we present a few examples illustrating the relevant notions, as introduced earlier, including the new semantic phenomena brought by partiality and non-determinism, the divide between the single and multiple-conclusion settings, and also the idiosyncrasies of combined logics.

Example 3. (Classical logic, fragments and combinations).
Let Σ cls be the usual connectives ⊤, ¬, ∧, ∨, →, that is, Σ For simplicity, given some connectives Θ of the signature, we will write Σ Θ cls to denote the subsignature of Σ cls containing only the connectives in Θ.
The multiple-conclusion version of classical logic ⊲ cls is known from [69] to be alternatively characterized by the following multiple-conclusion calculus.
It is crucial to observe that the axiomatization above is completely modular with respect to syntax, as each rule involves a single connective. Said another way, the axiomatization is obtained by joining axiomatizations of each of its single-connective fragments, or equivalently we have that where ⊲ c cls = ⊲ cls ∩(℘(L Σ c cls (P )) × ℘(L Σ c cls (P ))) for each c ∈ Σ cls is the corresponding single-connective fragment of the logic. This fact marks a sharp contrast with respect to the single-conclusion setting, which goes well beyond classical logic, and that will play a key role in our developments. Namely, the single-conclusion version of classical logic is known to be characterized by the following single-conclusion calculus.
The fact that the single-conclusion axiomatization is not at all modular with respect to syntax, and that most rules refer to more than one connective, is definitely not a coincidence, as shown in [21]. Indeed, each of the single-connective fragments ⊢ c cls = ⊢ cls ∩(℘(L Σ c cls (P )) × L Σ c cls (P )) of ⊢ cls for each connective c ∈ Σ cls can be axiomatized as follows (see [62] It is clear that joining all these rules will yield a logic much weaker than classical logic (see [21]), that is, A suitable semantics for the resulting combined logic is not obvious. △ The previous example, though very familiar, was useful for illustrating some of the notions and notations used in this paper, and in particular the differences between the single and multiple-conclusion settings, namely when combining logics. However, even in a two-valued scenario, non-determinism allows for characterizing some interesting non-classical connectives and logics. The first connective ⊥ ⊤ is a completely free 0-place connective, known as botop in [55]. Its logic is characterized by the empty calculus, without any rules. Then, is a 1-place modal-like box operator whose logic is characterized by the usual necessitation rule: The 2-place implication-like connective is characterized solely by the rule of modus ponens: p , p q q .
All rules above serve both the single and multiple-conclusion settings. Lastly, the 2-place connective ∧ ∨, was named platypus in [50], and features some properties of classical conjunction mingled with classical disjunction. Namely, its multiple-conclusion logic is characterized by the following two (familiar) rules.
p , q p∧ ∨q p∧ ∨q p , q As shown in [50], the single-conclusion logic of platypus cannot be finitely axiomatized. △ Of course, the added richness provided by non-determinism goes well beyond the two-valued cases seen above.

Example 5. (Information sources).
In [3], the authors introduce a logic for modelling the reasoning of a processor which collects information from different classical sources. Namely, each source may provide information that a certain formula of classical logic is true, or false, or no information at all. This situation gives rise to four possible situation as, for each formula, (t) the processor may have information that it is true and no information that it is false, or (f ) information that it is false and no information that it is true, or (⊤) have information that it is true and also information that it is false, or (⊥) have no information at all about the formula. This situation is easily understandable if one reads the situations as collecting the available classical truth-values (0,1) for each formula as As originally presented, the logic is defined over the signature Σ S = Σ ∧,∨,¬ cls and characterized by the Nmatrix S = {f, ⊥, ⊤, t}, {⊤, t}, · S defined by the tables below.
Clearly, both conjunction and disjunction have non-deterministic interpretations. For instance, note that t ∧ S t = {t, ⊤}. Thus, a valuation v ∈ Val(S) may be such that there exist formulas From [54,19] we know that both ⊲ S and ⊢ S are axiomatized by the following rules.
p The fact that this single-conclusion calculus characterizes the multiple-conclusion consequence ⊲ S is remarkable, implying that min( Σ S , ⊢ S )= Σ S , ⊲ S . Namely, given any set of formulas Γ, note that Γ ⊲ S ∅, as the function such that v(A) = ⊤ for all formulas A ∈ L ΣS (P ), is such that v ∈ Val(S).
Note that these logics could not possibly be characterized by finite matrices. Namely, let p ∈ P be a variable, and define A 0 = p and A k+1 = p ∨ A k for k ∈ N 0 . Note that Γ = {A k : k ∈ N 0 } satisfies sub(Γ) ⊆ Γ, and consider for each i ∈ N 0 the prevaluation f i : Γ → {f, ⊥, ⊤, t} of S defined by Each f i thus extends to a valuation v i ∈ Val(S) showing that A i ⊢ S A k for k < i. Hence, ⊢ S fails to be locally finite and therefore cannot be characterized by a finite set of finite matrices [22]. The same applies to ⊲ S , simply because sing( Σ S , ⊲ S )= Σ S , ⊢ S . △ Besides allowing for a great amount of compactification, non-determinism has another outstanding property regarding modularity with respect to syntax.

Example 6. (Language extensions).
Above, given a logic Σ 0 , ∝ 0 and Σ 0 ⊆ Σ, we have defined its extension to the larger signature as Σ, ∝ Σ 0 . If Σ 0 , ∝ 0 has an associated calculus Σ 0 , R , then it is clear that the extension Σ, ∝ Σ 0 is associated to the exact same rules via the calculus Σ, R .
Take, for instance, single-conclusion classical propositional logic Σ cls , ⊢ cls as defined in Example 3. Suppose that we wish to consider its extension to a larger signature Σ ⊇ Σ cls containing a new connective c ∈ Σ (2) . We know that the exact same calculus presented above is associated to the extended logic Σ, ⊢ Σ cls . What is more, we also have that the extended logic is characterized by the Σ-Nmatrix ¾ Σ which extends the Σ cls -matrix ¾ by letting where the connective is interpreted in a (neutral) fully non-deterministic manner. This extension could not be possibly characterized finitely without using nondeterminism [4]. △ At last, we should illustrate the advantages and intricacies that result from introducing partiality.

Example 7. (Kleene's strong three-valued logic).
We consider the implication-free fragment of Kleene's strong three-valued logic as defined in [36]. The logic is defined over the signature Σ = Σ ∧,∨,¬ cls and is usually characterized by means of two three-valued Σ-matrices. Equivalently, the logic is given just by the four-valued Pmatrix KS = {0, a, b, 1}, {b, 1}, · KS defined by the following truth-tables.
Note that several entries of the tables contain ∅, namely a The single-conclusion logic Σ, ⊢ KS is known to be associated with the calculus The multiple-conclusion logic Σ, ⊲ KS is known from [19] to be associated with the calculus This latter multiple-conclusion calculus is clearly more natural. As it contains genuinely multiple-conclusion rules, in this case, min( Σ, ⊢ KS ) Σ, ⊲ KS . Note, for instance, that p ∨ q ⊲ KS p, q, but that p ∨ q ⊢ KS p and p ∨ q ⊢ KS q. △ Partiality can indeed be used in almost all cases to provide a single PNmatrix for a logic characterized by a set of Nmatrices, as we will see later.

Semantics for combined logics
In this section, we are seeking semantic characterizations for combined logics, using bivaluations, and then PNmatrices. The multiple-conclusion abstraction, which we will analyze first, is important for its purity with respect to combination. As we will show, the step toward the single-conclusion case is then a matter of controlling, semantically, the relationship with the multiple-conclusion companions. In both cases, non-determinism and partiality play fundamental roles (as we know that similar results are impossible with respect to matrices).

The multiple-conclusion case
In the multiple-conclusion case, the characterization we need is really very simple, if one considers bivaluations. The result stems directly from the known fact (see [69]) that for every multiple-conclusion logic Σ, ⊲ there exists a unique set of bivaluations B such that We fix signatures Σ 1 , Σ 2 , and sets of bivaluations B 1 ⊆ BVal(Σ 1 ) and B 2 ⊆ BVal(Σ 2 ), both closed for substitutions.
Since ⊲ B is the least consequence with this property we can conclude that ⊲ B ⊆ ⊲ B mult 12 , and therefore B mult 12 ⊆ B. This result allows us to obtain a clean abstract characterization of the combination of multiple-conclusion logics. One just needs to note that, given a signature Σ, a partition Ω, Ω of L Σ (P ) is essentially the same thing as a bivaluation b ∈ BVal(Σ) with b −1 (1) = Ω and b −1 (0) = Ω. Corollary 9. Let Σ 1 , ⊲ 1 , Σ 2 , ⊲ 2 be multiple-conclusion logics, and consider their combination Proof. Using Proposition 8, and letting The question is now whether we can mimic this simplicity at the level of PNmatrices. It turns out that one can define a very simple but powerful operation (already studied in [53] with respect to Nmatrices, but only in the disjoint case) in order to combine PNmatrices.
We fix PNmatrices Σ 1 , M 1 and Σ 2 , and only if the following conditions hold: Note that V * contains all pairs of truth-values which are compatible, that is, either both designated, or both undesignated. The pairs where both values are designated constitute D * . The truth-table of a shared connective c ∈ Σ 1 ∩ Σ 2 comprises all the pairs of values in the truth-tables of M 1 , M 2 which are compatible. The truth-table of a non-shared connective, say c ∈ Σ 1 \ Σ 2 , has each possible value in the truth-table of M 1 paired with all compatible values in V 2 . Clearly, the resulting PNmatrix is fundamentally non-deterministic for non-shared connectives whenever the given PNmatrices have several designated values, and several undesignated values. For shared connectives, non-determinism may appear if inherited from some of the given PNmatrices. Partiality, on its turn, is crucial to the interpretation of shared connectives, showing up whenever the values given by the truth-tables of M 1 , M 2 cannot be paired compatibly. For non-shared connectives, partiality may still appear if inherited from the given PNmatrices, or in pathological cases where the given PNmatrices do not have designated values, or do not have undesignated values.
Before characterizing the exact scope of this construction, we should note that valuations in M 1 * M 2 are always suitable combinations of valuations in M 1 and M 2 . For k ∈ {1, 2}, we will use π k : V * → V k to denote the obvious projection functions, i.e., π 1 (x, y) = x and π 2 (x, for each A. These properties apply also to prevaluations over any set of formulas closed for subformulas.
and v are compatible for every formula in L Σ1∪Σ2 (P ), and thus induce the same bivaluation. We then have that BVal( ) inducing the same bivaluation, it turns out that they must be compatible for all and only if A ∈ Ω, and induces the exact same bivaluation. We conclude that BVal(M Σ1∪Σ2 Now, we can easily identify the multiple-conclusion logic characterized by a strict product as the corresponding combined logic.

Theorem 12. The combination of multiple-conclusion logics characterized by PNmatrices is the multiple-conclusion logic characterized by their strict product, that
Proof. The result follows directly from Proposition 8 and Lemma 11. With This result, besides being based on a simple operation on PNmatrices, has a very useful feature: it provides a finite-valued semantics for the combined logic whenever we are given finite-valued semantics for both given multiple-conclusion logics.
Let us look at some examples, starting with the two-valued case.

such as those in Examples 3 or 4.
Note that according to Definition 10, M 1 * M 2 is also two-valued, having values (0, 0) and (1, 1), with the latter designated. In the following discussion, for simplicity, we shall rename the two values to just 0 and 1, respectively, and assume that the strict product is If c ∈ Σ 1 ∩ Σ 2 is a shared connective, and assuming for the sake of exposition that c is a 2-place connective, we have that c * behaves as depicted below.
This behaviour is absolutely similar for connectives with any number of places, that is, If c ∈ Σ 1 ∪Σ 2 is not a shared connective, and assuming without loss of generality It is clear that the resulting PNmatrix may be genuinely partial in case some of the sets are disjoint, and in general will be a Pmatrix whenever starting with two matrices.
Recalling Example 3, we see that given any two sets of classical connectives We will see later that in the single-conclusion case the situation can be dramatically different. △ Let us now consider a richer example. According to Theorem 12, we know that Σ, Further, we also have that (0 1 2 → * 00) = ∅, which then implies that the total components of the Pmatrix are T K * L = {X ⊆ {00, 0 1 2 , 11} : {00, 0 1 2 } X}, which implies that BVal(K * L) is precisely the set of all classical interpretations of classical implication. We can conclude, thus, that Σ, coincides with the multiple-conclusion implication-only fragment of classical logic, as defined in Example 3.
Confirmation of this interesting fact can be obtained by putting together calculi for the logics, according to Proposition 2. These multiple-conclusion versions of the logics are not very well known, but a calculus for ⊲ K can be readily obtained using the technique of [54,19], whereas a calculus for ⊲ L can be found in [2]. Of course, all the rules in these calculi are classically valid, because ⊲ K , ⊲ L ⊆ ⊲ → cls (all classical valuations are permitted in both matrices). Further, as we know the rules of classical implication from Example 3, it suffices to note that: (1) We will return to this example in the more familiar single-conclusion setting. △ We shall now illustrate how different it is to combine logics with or without shared connectives.

Example 15. (The three-valued implications of Kleene and Łukasiewicz, disjointly).
We shall revisited Example 14 above, combining the (multiple-conclusion) logics of Kleene's and Łukasiewicz's three-valued implications, but now assuming that the connectives are syntactically different, i.e., that Kleene's implication comes from a signature Σ K with Σ According to Theorem 12, we know that

11
Of course, this is quite different from simply considering the given three-valued interpretations of each connective. Note, namely, that since all designated entries of → K K ′ are also designated in → L L ′ one could perhaps wrongly expect to have that p → K q ⊲ K ′ * L ′ p → L q. This assertion can be easily shown to fail by considering,

The single-conclusion case
The results above really illustrate the simplifying power of using multiple conclusions. Of course, things are not so simple in the single-conclusion scenario. Still, we know enough to be able to take nice conclusions from the same line of reasoning. Let us start with bivaluations.
If we analyze the proof of Proposition 8, it is simple to understand why it cannot be simply replicated in the single-conclusion case. Easily, the same line of reasoning would allows us to conclude that may very well not be the least such singleconclusion logic. Given This problem lies in a crucial difference from the multiple-conclusion case, as the same single-conclusion logic can be characterized by distinct sets of bivaluations. Given B ⊆ BVal(Σ), let its meet-closure be the set B ∩ = {b X : X ⊆ B} ⊆ BVal(Σ) with each meet defined by b X (A) = 1 precisely if b(A) = 1 for every b ∈ X, for each A ∈ L Σ (P ). It is well known that ⊢ B ⊆ ⊢ B ′ if and only if B ′ ⊆ B ∩ , and thus that two sets of bivaluations characterize the same single-conclusion logic precisely when their meet-closures coincide. Namely, every single-conclusion logic Σ, ⊢ is The trick is then to work with meet-closed sets of bivaluations, that is, B = B ∩ . In that case, it is worth noting that Σ, ⊲ B = min( Σ, ⊢ B ).
Since ⊢ B is the least consequence with this property we can conclude that ⊢ B ⊆ ⊢ B sing

12
, and therefore B sing ) ∩ , and so B ⊆ B sing 12 .
Note that B sing 12 is necessarily meet-closed, as it is the intersection of meet-closed sets. Hence, not only min( The next abstract characterization of combined single-conclusion logics follows. Just note that given b ∈ B ⊆ BVal(Σ) closed for substitutions, it is always the case Proof. Using Proposition 16, and letting This result captures neatly the intuition one already had from Proposition 2, namely that Γ ⊢ 12 A precisely when A is obtained by closing Γ with respect to both ⊢ 1 and ⊢ 2 .
Turning to PNmatrices, expectedly, Theorem 12 does not immediately apply to single-conclusion logics, as shown by the next counterexample.

Example 18. (Limitations of the strict product operation).
We present an example showing that, contrarily to the multiple-conclusion setting, the single-conclusion logic characterized by the strict product of two PNmatrices may fail to be the combination of the single-conclusion logics characterized by each of the given PNmatrices.
Consider the ¬-only and ∧-only fragments of classical logic, Σ ¬ cls , ⊢ ¬ cls and Σ ∧ cls , ⊢ ∧ cls respectively, as defined in Example 3. As we have seen in Example 13, the strict product of their two-valued matrices is simply the classical two-valued matrix for both connectives ¬, ∧ which characterizes the ¬, ∧-fragment of classical logic.
However, letting Σ ¬ cls , ⊢ ¬ cls • Σ ∧ cls , ⊢ ∧ cls = Σ ¬,∧ cls , ⊢ , and taking into account the single-conclusion calculi for each of the fragments, shown also in Example 3 and also Proposition 2, it is not at all clear that ⊢ = ⊢ ¬,∧ cls . As a matter of fact, this is not the case, as ⊢ is a strictly weaker consequence, as shown in [21,53]. Namely, ¬p ⊢ ¬(p ∧ p). We will show exactly why in a forthcoming example.
Clearly, the set of classical bivaluations for conjunction is meet-closed, and therefore the phenomenon above can only be justified by the fact that the set of classical bivaluations for negation is not meet-closed. Concretely, it is clear that there is a unique classical (bi)valuation b 0 : L Σ ¬ cls (P ) → {0, 1} such that b 0 (p) = 0 for all p ∈ P , and thus b 0 (¬p) = 1 and so on, and also a unique classical (bi)valuation As before, the problem lies with the fact that, in general, the set of bivaluations induced by a PNmatrix does not have to be meet-closed. In order to cope with this possibility, we consider the following property.
Of course, a PNmatrix that has a meet-closed set of bivaluations is necessarily saturated. It turns out, however, that saturation does not necessarily imply a meetclosed set of bivaluations, but it gets sufficiently close. Let 1 : as Γ is consistent. We conclude that b X ∈ BVal(M) and thus that M is saturated.
Under the assumption that the PNmatrices are saturated, Theorem 12 can now be adapted to the single-conclusion case too.

Theorem 21. The combination of single-conclusion logics characterized by saturated PNmatrices is the single-conclusion logic characterized by their strict prod
Proof. The result follows directly from Proposition 16, and Lemmas 11 and 20. With As a corollary of this proof it also results that Σ 1 ∪ Σ 2 , M 1 * M 2 is a saturated PNmatrix, and thus that saturation is preserved by the strict product operation.

Example 22. (Strict product and saturation).
Recall the discussion in Example 18 about the single-conclusion combination of the ¬-only and ∧-only fragments of classical logic, Σ ¬ cls , ⊢ ¬ cls and Σ ∧ cls , ⊢ ∧ cls .
Since the set of all classical bivaluations for the ∧-only language is meet-closed, On the other hand, as seen before, the set of all classical bivaluations for the ¬only language is not meet-closed, and the corresponding two-valued matrix is not saturated. Instead, let us consider the three-valued By the consistency of Γ we know that v is well defined, because A and ¬A cannot both be in Γ due to rule p ¬p q . Additionally, rules Given the saturation of the two matrices, according to Theorem 21, the resulting 2 shows that ¬p ⊢ ¬(p ∧ p). Of course, this implies that putting together calculi for each of the connectives is not enough to fully characterize the way they interact in classical logic, as can be visually confirmed from the rules in Example 3. △ As this point, we should question the scope of applicability of Theorem 21, and how often we can expect to find naturally saturated PNmatrices as in the example above. What should we do when given PNmatrices that are not saturated? Fortunately, there is a simple way of transforming a PNmatrix into a saturated PNmatrix both characterizing the same single-conclusion logic 3 .
if and only if the following condition holds: For each k ∈ N we use π k : V ω → V to denote the obvious projection function, i.e., π k ({x i } i∈N ) = x k . Clearly, we have that v ∈ Val(M ω ) if and only if (π k • v) ∈ Val(M) for every k ∈ N.
To show that Σ, M ω is saturated, let Γ be a consistent theory of Σ, ⊢ M , and fix Let v ∈ Val(M ω ) be such that (π k • v) = v k for every k ∈ N. We have that v(Γ) ⊆ D ω because v k (Γ) ⊆ D for every k ∈ N, and for every B / ∈ Γ, we have that We conclude that Σ, M ω is saturated 4 .
The following result follows easily from Theorem 21 and Lemma 24.
Theorem 25. The combination of single-conclusion logics characterized by PNmatrices is the multiple-conclusion logic characterized by the strict product of their ω-powers, that is, Though still usable, this result does not provide us with a finite-valued semantics for the combined logic, even if departing from finite-valued PNmatrices. Indeed, in the relevant cases, a ω-power PNmatrix is always infinite (and not even denumerable), the exceptions being ω-powers of PNmatrices with at most one truth-value, easily seen to be saturated to begin with. Note also that the situation is not unexpected, as we know that some combinations cannot be endowed with finite-valued semantics [52], and it is playing the role of meet-closure in the case of bivaluations. Still, there are cases when saturation is not necessary (we will see a relevant example of this phenomenon in Subsection 5.1 below), or when saturation can be achieved by a finite power of the given PNmatrix. We present some examples below, and further discuss this question in the conclusion of the paper. 4 The proof of Lemma 24 actually shows that the bivaluations of M ω are closed for non-empty denumerable meets. This is enough, in our case, since the empty meet corresponds to the irrelevant 1 bivaluation, and also because non-denumerable meets are not necessary given that we always work with denumerable languages.

Example 26. (Three-valued implications of Kleene and Łukasiewicz).
Recall Example 14, where we discussed the combination of the three-valued implications of Kleene and Łukasiewicz in the multiple-conclusion setting, with shared implication, and we concluded that the resulting logic coincided with the multipleconclusion version of the implication-fragment of classical logic. Now, we shall see that, incidentally, the corresponding single-conclusion combination also coincides with classical implication, albeit for distinct reasons. For easier readability, we recall here the signature Σ with Σ (2) = {→} and Σ n = ∅ for n = 2, and the three-valued implication matrices of Kleene and Łukasiewicz, namely , v(q) = 0 and v(q → r) = 1. We must therefore consider the ω-power of each of the matrices. Note that in both cases, the resulting truth-values are infinite denumerable tuples {x i } i∈N with each x i ∈ {0, 1 2 , 1}, which for simplicity we will represent as pairs of sets X 0 , X 1 with X 0 = {i ∈ N : x i = 0} and X 1 = {i ∈ N : x i = 1}. Of course, then, As both matrices have 1 as their unique designated value, we also get in both cases that D ω = { ∅, N }. The resulting matrices are thus K ω = V ω , D ω , · K ω and L ω = V ω , D ω , · L ω , defined according to the tables below.

Representing pairs of pairs as four-tuples we get the set of truth-values
The resulting strict product is then K ω * L ω = V * , D * , · * as defined by the table below.
This semantics has a non-trivial look, but it turns out that one can still draw valuable conclusions from it. Due to the partiality of K ω * L ω it is worth noting that the Pmatrix has a lot of spurious values This observation implies that if v ∈ Val(K ω * L ω ) then π 1 • v ∈ Val(K ω ) never uses the 1 2 value of matrix K. As K behaves classically for the 0, 1 values, we conclude that all bivaluations in BVal(K ω * L ω ) are classical. On the other hand, we know from Lemmas 11,20 and 24 that Since not just K but also L behaves classically for the 0, 1 values, we conclude that all classical bivaluations are in BVal(K ω * L ω ). Thus, we have that Σ,  Of course, we did not need to know that such a matrix existed, and instead we could have blindly obtained the ω-power of the two-valued classical matrix for negation, and then obtained its strict product with the saturated two-valued classical matrix for negation. The semantics thus obtained would be less amiable, but still characterizes the combination. Alternatively, we could have noted that the four-valued 2-power of the matrix of negation would already be saturated (the three-valued matrix used before is a simplification of it).
(3) As a last interesting example of disjoint combination let us consider the fragments Σ ∧ cls , ⊢ ∧ cls and Σ ∨ cls , ⊢ ∨ cls . We already know from [21] that the combination Σ ∧ cls , ⊢ ∧ cls • Σ ∨ cls , ⊢ ∨ cls = Σ ∧,∨ cls , ⊢ is weaker than ⊢ ∧,∨ cls . Namely, we have that p ∨ (p ∧ p) ⊢ p, as can be confirmed by any valuation with ∅ v(p) N and v(p ∧ p) = N \ v(p) = N, which then implies that v(p ∨ (p ∧ p)) = N, on the Nmatrix resulting from the strict product of the two-valued classical matrix for conjunction and the ω-power of the two-valued classical matrix for disjunction, corresponding (after renaming) to M * = ℘(N), {N}, · * as defined by the tables below.
Of course a simpler semantics would be desirable, but we know that the twovalued classical matrix for disjunction is not saturated. Namely, note that {p∨q} ⊢ ∨ To confirm this, we first note that none of the two-valued classical matrices for the fragments is saturated. This is simply because both include implication, ∅ ⊢ cls p and ∅ ⊢ cls p → q but any classical valuation will have v(p) = 1 or v(p → q) = 1. Thus, we need to consider the strict product of the ω-power of each of the matrices, which results (after renaming) in the PNmatrix M * = ℘(N) × ℘(N), {(N, N)}, · * as defined by the tables below, where we use X = N \ X.

Easily, we have v(p → p) = N, N and hence v(¬(p → p))
Let f : N → U 0 be any surjective function. We claim that the function defined , and also easy to see that v ′ (¬B) = v ′ (B) using the observations in the previous paragraph. △

Universal properties
According to the very successful mathematical approach to General Systems Theory initiated by J. Goguen in [44,45], composition operations should always be explained by universal properties, in the sense of category theory [49,1]. This approach has been used also with respect to combinations of logics, for instance in [18,65]. Herein, we briefly show how our results are explained by simple universal constructions.

PNmatrices and rexpansions
In order to explore the relationships among PNmatrices, let us consider a suitable notion of homomorphism. If Expectedly, the strict product of PNmatrices as introduced in Definition 10 enjoys a universal characterization, whose proof is straightforward. Proposition 28. Let Σ 1 , M 1 and Σ 2 , M 2 be PNmatrices. Their strict product Σ 1 ∪ Σ 2 , M 1 * M 2 is a product in PNMatr, with projection homomorphisms π i : It goes without saying that the relationships between valuations in the PNmatrices Σ 1 , M 1 , Σ 2 , M 2 and valuations in Σ 1 ∪ Σ 2 , M 1 * M 2 mediated by the projection homomorphisms that were presented in Section 3.1 are simple consequences of the universal property enjoyed by products in a category.
It is clear that (Σ, ⊕M) is a coproduct of M in PNMatr, with inclusion homomorphisms ι i : Σ, M i → Σ, ⊕M defined, for each i ∈ I and each x ∈ V i , by ι i (x) = (i, x). Therefore, we have i∈I BVal(M i ) ⊆ BVal(⊕M). Perhaps surprisingly, however, it may happen that BVal(⊕M) = i∈I BVal(M i ).

The good, the bad, and the ugly
Now, we will prove the (good, very good) fact that 'almost' every logic (in the single or multiple-conclusion sense, it does not matter) can be characterized by a single PNmatrix (actually, a Pmatrix). This property is striking, as it is well known to fail for matrices, or even Nmatrices (see [22,69,73]), and at the same time reinforces the wide range of applicability of our results. The bad and the ugly are actually both related to the 'almost' part of our statement. On the one hand, we need to understand the reason for the exception, which actually lies on the (bad) fact that valuations on PNmatrices cannot be locally assessed for a sublanguage (or subsignature). On the other hand, the nature of the exception is related to a rather annoying (and mathematically ugly) syntactic property. Both are suitably illustrated by Example 29, as the the crucial reason for the behaviour shown in this example is the absence of a 2-place connective (actually, of any connective with at least two places). Proof. Observe that if v ∈ Val(⊕M) and A, B ∈ L Σ (P ) are such that v(A) = (i, x) and v(B) = (j, y) then it must be the case that i = j. This is a consequence of the existence of a connective c ∈ Σ (n) for some n > 1, as v(c (A, B, . . . , B) , x), (j, y), . . . , (j, y)) and, by definition, we have c ⊕ ((i, x), (j, y), . . . , (j, y) As the compatibility of these values is granted by the definition of designated values in ⊕M, it easily follows that BVal(⊕M) = i∈I BVal(M i ).
In the single-conclusion case, we know that a logic Σ, ⊢ is precisely characterized by the set of its theories [73]. Hence, the Lindenbaum bundle Lind( Σ, ⊢ ) consists of the Lindenbaum matrices M Γ over Σ such that Γ is a theory of Σ, ⊢ (when the logic is compact, we could as well consider only its relatively maximal theories).
Given a set of bivaluation B ⊆ BVal(Σ) closed for substitutions, we also define Lind( Σ, B ) as consisting of the Lindenbaum matrices M b for every b ∈ B.
The following result is an immediate consequence of Lemma 30, taking into account the Pmatrix corresponding to summing the Lindenbaum bundle into consideration.
We should note that when considering signatures with no connectives with two or more places, it really may happen that the logic characterized by a set of PNmatrices does not coincide with the logic characterized by their coproduct.

Multiple-conclusion combination
The results of Section 3, namely Proposition 8, Lemma 11 and Theorem 12, allowed us to characterize the combination of the multiple-conclusion logics defined by two PNmatrices as the logic defined by the intersection of their induced bivaluations, or equivalently as the logic of their strict product. Our aim is to provide a categorial explanation for these results.

PNMatr
Rexp Biv In the terminology of [6], that we extend here to PNmatrices, the existence of a strict homomorphism h : Σ, M → Σ 0 , M 0 means that Σ, M is a rexpansion of Σ 0 , M 0 . For simplicity, we will consider the quotient of PNMatr obtained by identifying all strict homomorphisms between the same two PNmatrices, thus obtaining a thin category that we will dub Rexp. Equivalently, Rexp consists of the preordered class of all PNmatrices under the rexpansion relation, and we write Σ, M ⊑ Σ 0 , M 0 precisely when Σ, M is a rexpansion of Σ 0 , M 0 . The obvious quotient functor Q : PNMatr → Rexp that sends each PNmatrix to itself is trivially continuous and cocontinuous. Therefore, it follows that Σ, ⊕M = Σ,M ∈M Σ, M is a (non-unique) join in Rexp, and we can say that ⊕M is the least PNMatrix of which all PNmatrices in M are rexpansions. Dually, is a (non-unique) meet in Rexp, and we can say that the strict product of two PNmatrices is the largest PNmatrix that is a rexpansion of both Σ 1 , M 1 and Σ 2 , M 2 .
We need also to consider the posetal category Biv, consisting of all pairs Σ, B where Σ is a signature and B ⊆ BVal(Σ) is closed for substitutions, partially ordered by the relation defined as Σ, B ⊑ Σ 0 , B 0 if Σ 0 ⊆ Σ and B ⊆ B Σ 0 . Easily, the mapping BVal extends easily to a (order-preserving) functor BVal : Rexp → Biv such that BVal( Σ, M ) = Σ, BVal(M) . If we further define Lind ⊕ : Biv → Rexp by Lind ⊕ ( Σ, B ) = Σ, ⊕Lind(B) we also obtain a (order-preserving) functor, which is actually left-adjoint to BVal. Proposition 33. The functors Lind ⊕ , BVal constitute a Galois connection, that is, for every Σ, B in Biv and every Σ 0 , M 0 in Rexp, the following conditions are equivalent: Reciprocally, assume that Σ, B ⊑ BVal( Σ 0 , M 0 ). This means that not only Σ 0 ⊆ Σ but also B ⊆ BVal(M 0 ) Σ . The latter inclusion implies that for each Consequently, BVal preserves meets (limits) and we rediscover Lemma 11, as , which is easily seen to be equal to Finally, we consider another posetal category Mult, of multiple-conclusion logics ordered by inclusion, that is, The mapping Mult : Biv → Mult such that Mult( Σ, B ) = Σ, ⊲ B is now easily seen to establish an order isomorphism between .Biv and Mult op .
As a consequence, we can recover Proposition 8, because Theorem 12 can also be recovered, simply, by noting that

Single-conclusion combination
The results of Section 3, namely Proposition 16 and Theorems 21 and 25, allowed us to characterize the combination of the single-conclusion logics defined by two PNmatrices as the logic defined by the intersection of the meet-closure of their induced bivaluations, or equivalently as the logic of the strict product of their ωpowers (or the PNmatrices themselves, when saturated). In order to explain these results categorially, we can adopt a similar strategy.
Given the properties of ω-powers, as stated in Lemma 24, we can restrict our attention to the full subcategory SPNMatr of PNMatr whose objects are just the saturated PNmatrices. We apply the same restriction to obtain the full subcategory SRexp of Rexp. As we know that the strict product of saturated PNmatrices is still saturated, the operation will still correspond to a (non-unique) meet in SRexp. Interestingly, however, coproducts of saturated matrices need not be saturated.

Example 35. (Sums and saturation).
Let Σ be the signature whose only connectives are @ ∈ Σ (0) and f ∈ Σ (1) , and consider the PNmatrix Σ, Easily However, the PNmatrix ⊕{M ∅ , M 1 } is not saturated. In fact, it suffices to show that BVal(⊕{M ∅ , M 1 }), which clearly contains the bivaluation 1, is not meet-closed. To see this, fix a variable p ∈ P and note that v 1 , v 2 :

0) is the only value not designated and that any valuation
Following the lines developed in Section 3, we shall also consider the full subcategory Biv ∩ of Biv whose objects are meet-closed sets of bivaluations. The functor BVal +1 : SRexp → Biv ∩ is such that BVal To establish that Σ, M is saturated, using again Lemma 20, it is sufficient to show that given X = {b γi : i ∈ I} ⊆ BVal(M) if the meet b X = 1 then b X ∈ BVal(M). First note that if b X = 1 then it is the case that I = ∅, and we can fix j ∈ I. For each t ∈ Atm consider X t = {γ i (t) : i ∈ I} ⊆ B \{1}. As B is meet-closed, the meet b Xt ∈ B, but it may still happen that b Xt = 1. Define γ : Atm → (B \ {1}) by We claim that b X = b γ . To see this, consider a formula A and let t = atm(A).
If, on the contrary, we have b Xt = 1 this means that γ i (t) = 1 for every Similarly, we have that Lind −1 ⊕ is left-adjoint to BVal +1 .

Proposition 38.
Sing : Biv ∩ → Sing is a dual order isomorphism, that is: • Sing is bijective, and Proof. Sing is bijective precisely because for every single-conclusion logic Σ, ⊢ there exists one unique meet-closed set of bivaluations B ⊆ BVal(Σ) such that ⊲ = ⊲ B . We know from [73] As a consequence, just note that ⊢ B0 ⊆ ⊢ B if and only if B ⊆ B ∩ 0 = B 0 , just because B 0 is meet-closed and thus, equivalently, Σ, B ⊑ Σ 0 , B 0 .
As a consequence, we can recover Proposition 16 too, just because we have Theorem 21 can also be recovered. If Σ 1 , M 1 and Σ 2 , M 2 are saturated PNmatrices, then note that . Theorem 25 also follows, by the same argument, using Lemma 24.

Examples and applications
Besides illustrating examples, of which we have already shown a few, our aim is now to present concrete applications of the tools we defined for obtaining usable semantics for combined logics, namely with respect to the modular conception and analysis of logics.

Adding axioms
Often, one works with a single-conclusion logic which can then be streghtened by the addition of new axioms [6,26,20] (and possibly also new syntax). Concretely, let Σ 1 , ⊢ 1 be a single-conclusion logic, Σ 2 be a signature, Ax ⊆ L Σ2 (P ) be a set of axiom schemata, and define Ax inst = {A σ : A ∈ Ax and σ : P → L Σ1∪Σ2 (P )}. The strengthening of Σ 1 , ⊢ 1 with the schema axioms Ax is the single-conclusion A, for every Γ ∪ {A} ⊆ L Σ1∪Σ2 (P ). Our aim is to apply the ideas developed above in order to obtain a semantic characterization of Σ 1 ∪ Σ 2 , ⊢ Ax 1 from a given semantic characterization of Σ 1 , ⊢ 1 .
In terms of bivaluations, the following simple result from [21] is instrumental. A if and only if Γ ⊢ Ax B1 A.
is easily seen to be meet-closed, but such a requirement is clearly not necessary for B 1 .
With respect to PNmatrices, we can take advantage of non-determinism for building a simple semantics for the logic associated to the calculus whose rules are precisely ∅ A for each A ∈ Ax, also equivalently defined by the set of bivaluations • for every n ∈ N 0 , c ∈ (Σ 1 ∪ Σ 2 ) (n) and A x1 1 , . . . , A xn n ∈ V Ax , we let It is easy to characterize the properties of this construction.

Lemma 41. We have that BVal(M
Of course, it is simple to check that Γ ⊢ M Ax A if and only if A ∈ Γ ∪ Ax inst , and thus that Σ 1 ∪ Σ 2 , ⊢ Ax Theorem 42. The strengthening with Ax of the single-conclusion logic characterized by a PNmatrix is the single-conclusion logic characterized by its strict product with M Ax , that is, given a PNmatrix Proof. The result follows directly from Proposition 39, and Lemma 11 and 41. With Note that this construction, though similar to the ones presented in the previous section, has a remarkable difference: the PNmatrix M 1 does not need to be saturated. The proof technique is essentially the same, but takes advantage of the fact that any set extending a theory of Σ 1 ∪ Σ 2 , ⊢ M Ax is still a theory, as it retains all the instances of axioms. The end result, though, is still infinite-valued (denumerably infinite, now, provided M 1 is denumerable), but has really interesting consequences.
For instance, we have seen in Example 4 that the logics defined by the rules of modus ponens and/or necessitation, p , p q q p p can be given a very simple non-deterministic two-valued semantics. Hence, according to Theorem 42, every logic obtained from these by the addition of axioms can be characterized by a denumerable PNmatrix, which of course includes every modal logic, normal or not. A most interesting consequence of this idea is shown in the following example.

Example 43. (Intuitionistic logic).
Fix a signature Σ int containing the desired set of intuitionistic propositional connectives, including implication, i.e., → ∈ Σ (2) int . Also, fix a set of axioms Int which together with the rule of modus ponens constitutes a calculus for intuitionistic propositional logic Σ int , ⊢ int (Int could consist of just the first two axioms in the axiomatization of ⊢ → cls , in case implication is the only connective of Σ int ). Take a signature Σ whose only connective is implication, that is, → ∈ Σ (2) and consider the Σ-Nmatrix MP = {0, 1}, {1}, · MP where → MP = ¾ ′ as defined in Example 4. That is to say that Σ, ⊢ MP is the logic axiomatized by the rule of modus ponens.
Obviously, ⊢ Int MP = ⊢ int , and Theorem 42 tells us that it is characterized by the PNmatrix MP * M Int . Since MP is finite and M Int is denumerable, we can conclude that MP * M Int is denumerable, which means that intuitionistic propositional logic can be characterized by a single denumerable PNmatrix. This is a remarkable property of PNmatrices, witnessing their compactification abilities, as it contrasts with the known fact that a characteristic matrix for intuitionistic logic needs to be nondenumerable [43,75,73]. △ Nicer, finite-valued, semantics can be obtained in particularly well-behaved scenarios, which (unsurprisingly) do not include the examples above. We refer to reader to [20] for further details.

Axiomatizability by splitting
Obtaining symbolic calculi, or axiomatizations, for logics of interest, namely if presented by semantic means, is well-known to be a non-trivial task, even harder when one seeks particularly well-behaved calculi. Herein, we show that to some extent, our results about combined semantics can have an impact on the possibility of splitting this task into the problem of obtaining calculi for suitably defined syntactic fragments of the logic, which can then put together, in a modular way, to produce a calculus for the original logic. Indeed, in abstract, given a logic L we will be looking for ways to obtain logics L 1 , L 2 such that L 1 • L 2 = L.
Concretely, let Σ, M with M = V, D, · M be a PNmatrix, and split the associated logical language into signatures Σ 1 , Under which conditions can we obtain an axiomatization of Σ, ∝ M by just putting together axiomatizations of Σ 1 , ∝ M1 and Σ 2 , ∝ M2 , in either the single and multipleconclusion settings?
Recall from [69,54,19] that Σ, M is said to be monadic provided that for every two values x, y ∈ V with x = y there exists a one-variable formula S ∈ L Σ ({p}), to which we call a separator of x and y, such that S M (x), S M (y) = ∅ and S M (x) ⊆ D and S M (y) ∩ D = ∅, or vice-versa. When all the separators S can be found in L Σ0 ({p}) for a subsignature Σ 0 ⊆ Σ, we say that the PNmatrix is Σ 0 -monadic. To prove the converse inclusion, we need to take into account that M 1 * M 2 may have spurious values, that is, pairs (x, y) such that v(A) = (x, y) for whatever v ∈ Val(M 1 * M 2 ) and A ∈ L Σ (P ). Indeed, we can show that if v(A) = (x, y) then it must be the case that x = y, using the proviso of monadicity on the shared subsignature. We can now state our split axiomatization result for multiple-conclusion logics.

Theorem 45. If R i is an axiomatization of
Proof. Clearly, using Theorem 12 along with Proposition 2, we have Σ, an axiomatization of the multiple-conclusion logic characterized by the strict product M 1 * M 2 . Using the monadicity proviso, Lemma 44 ensures that BVal(M) = BVal(M 1 * M 2 ) and therefore ⊲ M1 * M2 = ⊲ M , which concludes the proof.
The previous result allows us to obtain a multiple-conclusion calculus for the logic characterized by a given PNmatrix by simply putting together calculi for simpler logics, under the appropriate provisos. For instance, taking advantage of techniques such as [54], one can even obtain incrementally analytic axiomatizations for the logic of a given monadic PNmatrix.
It is worth noting that the result of Theorem 45 has some simple immediate consequences. Namely, it trivially applies to any PNmatrix having no more than one designated value and one undesignated value, namely in Boolean like PNmatrices like those in Examples 3 and 4, by simply using the separator p (this actually shows that one can provide axiomatizations for each connective separately, not just for fragments of classical logic, but also covering less common two-valued nondeterministic connectives). Let us look at another interesting example. Consider the splitting corresponding to the signatures Σ = Σ 1 ∪ Σ 2 with Σ 1 containing ∧, ¬ and Σ 2 containing ∨, ¬, and let KS 1 and KS 2 be the corresponding reducts of KS. Since ¬ ∈ Σ 1 ∩ Σ 2 , Theorem 45 tells us that we can obtain a calculus for Σ, ⊲ KS by simply joining calculi for the fragments Σ 1 , ⊲ KS 1 and Σ 2 , ⊲ KS 2 .
It is worth noting that in the multiple-conclusion calculus for ⊲ KS put forth in Example 7, the rules where ∨ does not appear constitute a calculus for ⊲ KS1 , and the rules where ∧ does not appear constitute a calculus for ⊲ KS 2 . △ In the following example we will see that monadicity in the shared language is only a sufficient condition for splitting axiomatizations, but that it really plays an important role in the result. Besides the familiar connectives of negation and implication, ∇ is a possibility operator that can be traced back to Łukasiewicz and Tarski (see [72]). Note that ∇A is definable as ¬A → A, and thus ∇p ⊲ L ¬p → p.
The matrix L is monadic, namely using p, ¬p as its separators, but also alternatively using p, ∇p, as both ¬p and ∇p separate 0 from 1 2 . However, one cannot separate these values using only implication. This said, we could of course apply Theorem 45 to splittings of signatures sharing ¬, or ∇, or both, as in the previous example. Instead, let us look at some more informative cases.
(1) Let us first consider the splitting corresponding to the signatures Σ = Σ 1 ∪Σ 2 with Σ 1 containing ¬, → and Σ 2 containing ∇, and let L 1 and L 2 be the corresponding reducts of L. Since ¬, ∇ / ∈ Σ 1 ∩ Σ 2 = ∅, Theorem 45 cannot guarantee that we can obtain a calculus for Σ, ⊲ L by simply joining calculi for the fragments Σ 1 , ⊲ L1 and Σ 2 , ⊲ L2 . Indeed, this can never be the case as Σ, ⊲ L1 * L2 is strictly weaker that the Łukasiewicz logic Σ, ⊲ L . To see this, note that the strict product

11
This example shows that the requirement that the given PNmatrix is Σ 1 ∩ Σ 2monadic is sufficient, but not necessary, for the splitting axiomatization result to follow. △ Although obtaining axiomatizations for single-conclusion logics is known to be substantially harder, our line of reasoning may still apply, as long as we further demand saturation.
Proof. It is easy to see that if Σ, M is saturated, then Σ i , M i is also saturated, Using Theorem 21 and Proposition 2, we can conclude that Σ, Note that the saturation proviso makes the result of Theorem 48 harder to use. In any case, the result is in line with the results of [21], namely about the (im)possibility of independently axiomatizating each Boolean connective in fragments of classical logic.

Example 49. (Classical logic can hardly be split).
Recall Example 3, and the analysis of combined fragments of classical logic in the single-conclusion setting that we developed in Example 27. Much as these combinations differ substantially from the multiple-conclusion case, also splitting axiomatizations of classical logic, universally possible in the multiple-conclusion scenario, as we saw above, become a rarity in the single-conclusion case.
We have seen that classical matrices are always trivially monadic, but now Theorem 48 further demands saturation. It turns out that the two-valued interpretation of most interesting classical connectives is not saturated, namely for fragments containing ¬, →, or ∨, as we have seen previously, which leads mostly to the failure of split axiomatizations as already shown in Example 27. Connectives whose interpretation is saturated include, however, ∧, ⊤, and ⊥. Hence, Theorem  According to Theorem 45, the observations above imply that a multiple-conclusion calculus for Σ S , ⊲ S can be obtained by joining multiple-conclusion calculi for fragments based on splitting signatures Σ 1 , Σ 2 ⊆ Σ S such that Σ 1 ∪ Σ 2 = Σ S as long as Further, the Nmatrix S is saturated. Given a consistent theory Γ of ⊢ S , it is easy to see Actually, the saturation of S can also be seen as a consequence of the fact that ⊲ S is axiomatized by a single-conclusion calculus.

Decidability preservation
Transference theorems have always been a main drive of the research in combining logics. Decidability is certainly one of the most desirable properties a logic should have, opening the way for the development of tool support for logical reasoning. There are some known results [30,51], namely with respect to disjoint combinations, but it is worth looking carefully at the semantic characterizations developed in the previous section, and analyzing their contribution to decidability preservation in general. That is, when given two decidable logics, under which conditions can we guarantee that their combination is still decidable?

Deciding multiple-conclusion combined logics
Let us first look at the decision problem for multiple-conclusion logics. We will say that a multiple-conclusion logic Σ, ⊲ is decidable if there exists an algorithm D, which terminates when given any finite sets Γ, ∆ ⊆ L Σ (P ) as input, and outputs D(Γ, ∆) = yes if Γ ⊲ ∆, and D(Γ, ∆) = no if Γ ⊲ ∆. According to this definition it is clear that one is actually deciding the compact version Σ, ⊲ fin of the logic, and hence we will henceforth assume, without loss of generality, that the logic at hand is compact.
Of course, any logic characterized by a finite PNmatrix is decidable [8]. This case covers the combination of any two logics when they are each characterized by a finite PNmatrix, given that the strict product operation preserves finiteness. But we can go beyond the finite-valued case.
Corollary 9 is quite appealing, and mathematically clean, but a decision procedure based on it would require (potentially) running through all partitions of the set of all formulas. As the similarity with cut for sets is striking, one may try to obtain a more usable version inspired by cut for a suitable finite set, namely in relation to the input, which we will dub context.
This definition has a more abstract alternative characterization.
Proof. The result is immediate, taking into account Proposition 8 and the fact that, for each k, the unique set of bivaluations characterizing Σ k , We can now obtain a more decidability-friendly version of Corollary 9.
We now apply these ideas toward decidability preservation we assume that the context function ctx is computable.
compute Ω = ctx(Γ ∪ ∆) non − deterministically choose partition Ω, Ω of Ω if D 1 (Γ ∪ Ω, ∆ ∪ Ω) = yes or D 2 (Γ ∪ Ω, ∆ ∪ Ω) = yes then output yes else output no The correctness of D is an immediate consequence of Lemma 52, noting that the no output is always correct, independently of the non-deterministic choice of the partition, whereas the yes output is only correct when it holds for all choices.
It should be noted that sub-extensibility, or totality of the strict product in the case of PNmatrices, is a sufficient condition for preserving decidability, but further research needs to be done in order to find tighter conditions.

Example 55. (Decidability preservation for disjoint combinations).
A major result of [51] was the preservation of decidability for disjoint combinations of single-conclusion logics. We will get back to this particular result in the next subsection, but for now we will show that decidability is preserved also by disjoint combination of multiple-conclusion logics. Assume that both Σ 1 , ⊲ 1 , Σ 2 , ⊲ 2 are decidable, and Σ 1 ∩ Σ 2 = ∅.
As a first, partial, approach, let us consider the case when one knows that there exist (total) Nmatrices Σ 1 , M 1 , Σ 2 , M 2 such that ⊲ M1 = ⊲ 1 and ⊲ M2 = ⊲ 2 . If each of the Nmatrices has both designated and undesignated values, it follows easily from Definition 10 that Σ 1 ∪ Σ 2 , M 1 * M 2 is also a (total) Nmatrix, and the combined logic Σ 1 ∪ Σ 2 , ⊲ 1 • ⊲ 2 is decidable as a consequence of Corollary 54. Of course, if any of the two Nmatrices only has all its values designated (or all undesignated), the corresponding component logic will be trivially decidable, and the same applies to the resulting combined logic. However, in general, there is no reason to assume that the given logics can be characterized by (total) Nmatrices. Still, a very general but simple argument can be drawn along the lines of Theorem 53.
In order to prove that Σ 1 ∪ Σ 2 , ⊲ 1 • ⊲ 2 is decidable using Theorem 53, it suffices to show that Σ 1 , ⊲ 1 , Σ 2 , ⊲ 2 are ctx-extensible for a suitable computable context function. Let X be a finite theorem-set of either ⊲ 1 or ⊲ 2 , that is, ∅ ⊲ i X for some i ∈ {1, 2}, if such a set exists. In that case, if B i is the set of bivaluations characterizing Σ i , ⊲ i and b ∈ B i then it is clear that 1 ∈ b(X). When none of the component logics has a finite theorem-set then X = ∅, and compactness implies that 0 ∈ B i . Symmetrically, let X be a finite anti-theorem-set of either ⊲ 1 or ⊲ 2 , that is, X ⊲ i ∅ for some i ∈ {1, 2}, if such a set exists. In that case, if b ∈ B i then it is clear that 0 ∈ b(X). As before, X = ∅ if none of the component logics has a finite anti-theorem-set, in which case compactness implies that 1 ∈ B i .
We consider ctx(Ω) = sub(Ω ∪ X ∪ X), which can clearly be computed. Suppose now that B 1 , B 2 are the sets of bivaluations (closed for substitutions) characterizing the component logics 12 . Thus, we proceed knowing that we can fix formulas F 0 , First we modify b 1 , b 2 so that they also agree on P \ var(ctx(Ω)) (for simplicity, we chose to evaluate them all to 0). Consider the substitution σ : P → L Σ1∪Σ2 (P ) such that , and further agree on all formulas in Ω 0 = P ∪ ctx(Ω).
Inductively, let Ω k+1 = Ω k ∪ {c(A 1 , . . . , A n ) ∈ L Σ1∪Σ2 (P ) : A 1 , . . . , A n ∈ Ω k } and obtain bivaluations b k+1  We will further illustrate the use of such general results to concrete combined logics in the more familiar case, below, of single-conclusion logics. Of course, our general decidability preservation technique using a suitable context function resembles many of the decidability preservation techniques used in concrete examples, such as fusions of modal logics [41], or even beyond in combining equational and first-order theories [58,57,7,71,61]. A deeper account of the scope of the abstraction we propose is beyond the reach of this paper.

Deciding single-conclusion combined logics
As before, the single-conclusion case can now be addressed as an application of the same ideas. A single-conclusion logic Σ, ⊢ is decidable if there exists an algorithm D, which terminates when given any finite set Γ ⊆ L Σ (P ) and formula A ∈ L Σ (P ) as input, and outputs D(Γ, A) = yes if Γ ⊢ A, and D(Γ, A) = no if Γ ⊢ A. As before, we will henceforth assume with lost of generality that the logic at hand is compact, as this definition is equivalent to deciding the compact version Σ, ⊢ fin of the logic.
The following very simple result will help us to apply the ideas used in the multiple-conclusion scenario, to the single-conclusion case. Proposition 56. The following implications hold.
Proof. We consider each property. Now, to go directly to the results, we say that single-conclusion logics Σ 1 , ⊢ 1 , Σ 2 , ⊢ 2 are ctx-extensible when B 1 and B 2 are sets of bivaluations characterizing them, that is, ⊢ 1 = ⊢ B1 and ⊢ 2 = ⊢ B2 , and their (uniquely determined) meetclosures B ∩ 1 , B ∩ 2 are ctx-extensible. Again, this definition has a more abstract alternative characterization, based on theories.
Proof. The result is immediate, taking into account Proposition 16 and the fact that, for each k, the unique meet-closed set of bivaluations characterizing Σ k , ⊢ k is B ∩ k = {b ∈ BVal(Σ k ) : b −1 (1) is a theory of Σ k , ⊢ k }.
As before, we obtain a general decidability preservation result.
By saturation, Lemma 20 guarantees that BVal(M k ) ∩ = BVal(M k ) ∪ {1} for each k ∈ {1, 2}. Their sub-extensibility follows easily from the fact that also BVal(M 1 ), BVal(M 2 ) are sub-extensible, implied by the hypothesis that the strict product is total, as in the proof of Corollary 54.
The case of disjoint combinations is also worth revisiting.

Conclusion
The main contribution of this paper is the definition of a first modular semantics for combined logics, in both the single and multiple-conclusion scenarios. It is worth emphasizing again that the analysis of the latter scenario was crucial for the development, due to its tight connection with bivaluations. Of course, bivaluations could be simply seen as partitions of the language, or as theories, but looking at them as semantic functions helps to smoothen the path to many-valued interpretations. Naturally, the adoption of PNmatrices as models was also fundamental, as partiality enables us to deal with possibly conflicting interpretations of shared language, whereas non-determinism makes it straightforward to accomodate language extensions.
Discovering the finiteness-preserving strict-product operation on PNmatrices and its universal property were certainly central to the results obtained. Further, it should be said that it provides a solution to the problem at hand which is quite close to the abstract idea of Gabbay's fibring function [38,40,18], and a very natural modular version of Schechter's proposal [63]. Unfortunately, when combining single-conclusion logics, this is simply not enough. The solution we found uses the ω-power operation for saturation purposes, but at the expense of losing finitevaluedness. This path hinders the easy application of these techniques in practice for single-conclusion logics, in general, also because checking saturation does not seem to be a trivial task. Nevertheless, we have seen that ω-powers may ultimately be too radical a solution, namely as finite powers are sometimes sufficient. Clearly, a better understanding of saturation is necessary, namely also regarding its connection with admissibility of rules, as studied for instance in [47,27,11].
At this point we should remark that the fact that we only consider logics defined by a single PNmatrix, instead of a collection of PNmatrices, is a simplifying assumption with almost no loss of generality, as we have shown that partiality allows for summing collections of PNmatrices whenever one has at least one connective with more than one place.
The three applications developed taking into account our semantic characterizations are also worth mentioning as valuable contributions.
First, the construction of a semantics for strengthening a given many-valued logic with additional axioms is interesting in its implications, but just a reinterpretation of a result in [20], where less general but finite semantics for certain well-behaved particular cases are also obtained. Nevertheless, obtaining a denumerable PNmatrix for intuitionistic propositional logic is a worth example of the compressing power of partiality and non-determinism, and deserves to be further explored, namely in connection with ideas for aproximating logics (see, for instance, [9,33,42,56,59]).
Secondly, studying conditions under which the problem of obtaining a calculus for a logic may be split into the problem of obtaining axiomatizations for suitable syntactically defined fragments of the logic is quite crucial for a modular understanding of combining logics. A related approach was considered in [29], but aiming at a disjoint split with additional axioms. On the contrary, the results we obtain here are inline with ideas explored in [21] concerning axiomatizations of classical logic, and fit well with our running track of research on extracting calculi for PNmatrices in an automated way, namely using monadicity requirements [54,19].
Third, and last, having a clear semantics for combined logics is a crucial tool for studying their decidability. The very general criteria we obtained already cover previous results regarding disjoint combinations, as we have shown. We believe they are also powerful enough to encompass other results in the literature, like the decidability of fusions of modal logics [74,41], and even adaptations of Nelson-Oppen-like techniques for deciding certain equational and first-order theories [58,57,7,71,61]. A thourough analysis of the complexity of the obtained decision algorithms was intentionally not addressed in this paper, but certainly deserves future attention.