Complementary Logics for Classical Propositional Languages
Achille C. Varzi
Istituto per la Ricerca Scientifica e Tecnologica , Povo (Trento), Italy(Published in Kriterion. Zeitschrift für Philosophie, 4 (1992), 20–24.)

This note presents a simple axiomatic system by means of which exactly thosesentences can be derived that are rated non-tautologous in classical propositional
logic. Since the logic is decidable, there exist of course many algorithms that do
the job, e.g. using semantic tableaux or refutation trees. However, a formulationin terms of axioms and rules of inference is by no means a straightforward task,
as these must be of a most non-standard non-classical sort. 1 For instance, axioms
cannot be axiom schemata and standard substitution rules cannot hold, since a
non-tautology may well become tautologous upon substitution. Moreover, thesystem must be paraconsistent, i.e. such as to allow derivation of sentences with
opposite truth values. The system presented here provides, I think, a rather niceway of dealing with these difficulties.
Since tautologous sentences are also axiomatizable, the outcome is an exhaustive characterization of the logic of classical propositional languages inpurely syntactic terms. The picture can then be completed by developing related
systems axiomatizing classical contradictions, contingencies, non-contradictions
and non-contingencies, respectively: systems of this kind, which provide additional examples of paraconsistent calculi with a classical background, are discussed in the final section.
1

A complete, Hilbert-type axiomatization of classical non-tautologies was first provided
by Caicedo (1978). Following Lukaziewicz’s (1951) rejection method, in Varzi (1990) I have introduced a simplified system based on the sole axiom ⊥ (falsehood) and the two rules of inference: (i) if A is a substitution instance of B, then A B; and (ii) if A is obtained from B byreplacement of equivalent sentences, then B A (counting as equivalent the pairs {T, ~⊥}, {⊥,⊥∨⊥}, {T, ⊥∨T}, {T, T∨⊥}, {T, T∨T}). Similar methods have been used independently by
Scott (1957) and Dutkiewicz (1989) to axiomatize intuitionistic non-tautologies. The systempresented in this note is mathematically less elegant, but the format of the inferential rules andthe structure of the completeness proof possess some intrinsic interest and allow useful comparisons with the logic of tautologies.
11. Preliminaries
I shall focus on a propositional language L whose symbols comprise a denumerable stock of variables ‘p0’, ‘p1’, ‘p2’, …, the three connectives ‘~’ (negation),‘∧’ (conjunction), ‘∨’ (disjunction), and the two parentheses ‘(’ and ‘)’.2 The
notion of a sentence of L is defined as usual: every variable is a sentence; and if
A, B and C are sentences, so are ~A, (B∧C) and (B∨C). Variables are also calledatomic sentences. In addition, sentences involving exactly the same variables will
be referred to as conjoint sentences, whereas sentences with no variable in common will qualify as disjoint. I shall also speak of two sentences A and B as being
equivalent (to each other): by this I shall mean that one of the following conditions holds for some sentences C, C0, C1, C2, … , Cn, where n ≥ 2 :
E.1
E.2
E.3
E.4
E.5
E.6
E.7

A,B∈{C,~~C}
A,B∈{C,(C∧C)}
A,B∈{C,(C∨C)}
A,B∈{(C1∧C2),(C2∧C1)}
A,B∈{(C1∨C2),(C2∨C1)}
A,B∈{(~C1∧~C2),~(C2∨C1)}
A,B∈{(~C1∨~C2),~(C2∧C1)}
A,B∈{(C∧(~C2∨C2∨...∨Cn)),C}
A,B∈{(C∨(~C2∧C2∧...∧Cn)),C}
A,B∈{(C0∧(C1∧C2)),((C0∧C1)∧C2)}
A,B∈{(C0∨(C1∨C2)),((C0∨C1)∨C2)}
A,B∈{(C∧(C1∨C2)),((C∧C1)∨(C∧C2))}
A,B∈{(C∨(C1∧C2)),((C∨C1)∧(C∨C2))}

Here ‘(~C2∨C2∨...∨Cn)’ and ‘(~C2∧C2∧...∧Cn)’ are stand for any sentence of L
that can be obtained from such expressions by replacing each Ci by a sentence(2 ≤ i ≤ n) and a judicious addition of parentheses. In the following, I shall takefor granted this and other obvious abbreviations unless the context would notprevent confusion.
2. Semantics and Syntactics
Relative to the language L , we may define a valuation to be any function V assigning a value in {0,1} to each sentence, subject to the usual conditions:2

It goes without saying that any truth-functionally complete set of connectives would do.

2

V.1
V.2
V.3
V.4

if A=~B, then V (A)=1− V (B)if A=(B∧C), then V (A)=V (B)∩V (C)if A=(B∨C), then V (A)=V (B)∪V (C)if A is obtained from a sentence A' by replacing one or more occurrences of a sentence B' in A' by occurrences of a sentence B to which
B' is equivalent, then V (A)=V (A').3

On this basis, and taking 0 as the antidesignated value, a given sentence A of L
will then qualify as a non-tautology if and only if (iff) there exists a valuation V
such that V (A)=0 (in the following, I shall refer to such a V as a non-model ofA).
To provide a syntactic counterpart of this notion, let every variable of L
count as an axiom, and let a sentence A count as a consequence of a set of sentences Γ iff one of the following conditions is satisfied:
C.1
C.2
C.3
C.4

A=~B for some atomic sentence B∈Γ
A=(B∧C) for some conjoint sentences B,C∈Γ
A=(B∨C) for some disjoint sentences B,C∈Γ
A is obtained from a sentence A'∈Γ by replacing one or more occurrences of a sentence B' in A' by occurrences of a sentence B to which
B' is equivalent.4

Let now a sentence A count as a non-theorem (of L) iff there exists a sequence ofsentences A0…An (n ≥ 0) so that (i) An=A, and (ii) each Ai (i ≤ n) is either an axiom or a consequence of {A0… Ai-1} (such a sequence may be called a non-proofof A). Then, as we shall now see, the notion of a non-tautology and the notion ofa non-theorem identify exactly the same sentences.
3. Soundness and CompletenessThat the set of all non-tautologies includes the set of all non-theorems is easily
seen, i.e.:3

V.4 is obviously implied by V.1-V.3 . I only include it here for convenient reference.
In view of C.4, it will be clear that C.1-C.3 involve several redundancies. (For example,
one could add the requirements that all occurrences of ‘(’ in A be adjacent, and that the variables
occurring in A occur in a certain order; also, C.2 could be simplified to “A=(B∧C) for some sentences B,C such that B∈Γ” and C.3 could be reduced to “A=(B∨C) or A=(B∨~C) for some sentences B,C such that B∈Γ and C is a variable not occurring in B”, in which case E.5 could thenbe deleted). Again, the present formulation is dictated mainly by reasons of convenience.
4

3

T.1

Every non-theorem is a non-tautology.

For, suppose that A is a non-theorem, and let A0…An (n ≥ 0) be a non-proof of
A=An. Clearly, A0 is non-tautologous, since A0 can only be a variable and every
variable has infinitely many non-models. So pick any other Ak (0 < k ≤ n) andassume that each Ai (0 ≤ i < k) has a non-model. Let Γ={A0, ..., Ak-1}. If Ak =~B
for some atomic sentence B∈Γ (by C.1 ), then again B has to be a variable, and so
any of the infinitely many valuations that assign 1 to B will be a non-model of Ak(by V.1 ). Next, if Ak =(B∧C) for some conjoint sentences B,C∈Γ (by C.2 ), then
any non-model V of B will surely be a non-model of Ak , for V (B)=0 implies
V (B∧C)=V (Ak )=0 (by V.2 ). Third, if Ak =(B∨C) for some disjoint sentences
B,C∈Γ (by C.3 ), then a non-model of Ak can be constructed as follows: let V1 be
a non-model of B, let V2 be a non-model of C, and let V be that valuation which
agrees with V1 with respect to the value to be assigned to the variables occurringin B, and agrees with V2 with respect to the value to be assigned to any othervariable (including those occurring in C); then clearly V (B)= V1(B) andV (C)=V2(C), hence V (B∨C)=V (Ak )=0 (by V.3 ). Finally, if Ak is obtained fromsome sentence A'∈Γ by replacing one or more occurrences of a sentence B' in A'
by occurrences of a sentence B to which B' is equivalent (by C.4 ), then any nonmodel of A' will also be a non-model of Ak , as every valuation that assigns thevalue 0 to A' will assign the same value to Ak (by V.4 ). Thus, our arbitrary sentence Ak is sure to have a non-model. The desired result follows now by mathematical induction and generalization.
We may now proceed to prove the converse of T.1 :T.2

Every non-tautology is a non-theorem.

To this end, a couple of subsidiary definitions will be useful. First, let us extend
the relation of equivalence introduced in Section 1 to a more general, transitive
relation: I shall say that a sentence A is indirectly equivalent to a sentence A' (inshort A≅ A') iff there exists a sequence of sentences A0…An (n ≥ 0) such that(i) An=A, (ii) A0=A', and (iii) Ai+1 is equivalent to Ai for each i < n (I shall call sucha sequence an ≅ -transformation of A' into A). Clearly, ≅ is an equivalence relation,and it is easy to see that if a sentence A is obtained from a sentence A' by replacing one or more occurrences of a sentence B' in A' by occurrences of a sentence B
to which B' is indirectly equivalent, then A≅ A'. Also, an easy inductive argument(using V.4 ) shows that any two indirectly equivalent sentences are always assigned identical values by any valuation, which implies that ≅ preserves theproperty of being non-tautologous. Similarly, one verifies that ≅ preserves theproperty of being a non-theorem: for if A0… Am (m ≥ 0) is a non-proof of Am and4

Am… An (n ≥ m) is an ≅ -transformation of Am into An, then n-m applications of
C.4 show that A0… Am… An is a non-proof of An. (In the following, I shall appeal
to such basic properties of ≅ without explicit mention).
Second, let us say that a sentence A is in standard form (SF) iff (i) each occurence of ‘~’ in A is immediately followed by an atomic sentence; (ii) no occurrence of ‘∨’ in A is adjacent to a sentence that contains occurrences of ‘∧’; and(iii) for every conjunct C of A (= every sentence C that occurs adjacently tosome occurrence of ‘∧’ in A), all disjuncts of C (= all sentences that occur adjacently to some occurrence of ‘∨’ in C) are pairwise disjoint (if A involves no conjunct, we take this condition to hold for C=A). Note of course that a sentencesatisfying condition (i) is known in the literature as a sentence in elementary
form (EF), whereas a sentence satisfying both (i) and (ii) is typically referred toas a sentence in (conjunctive) normal form (NF).
Using these auxiliary notions, I shall now prove two related lemmas, L.1
and L.2 : from these, the desired result, T.2 , will follow immediately.5
L.1

Every non-tautology is indirectly equivalent to a sentence in standardform.

I will break the argument into three parts: first (a) I will show that any given sentence A is indirectly equivalent to a sentence A' in elementary form; next (b) I willshow that any sentence A' in elementary form is indirectly equivalent to a sentence A'' in normal form; and finally (c) I will show that any non-tautologous sentence A'' in normal form is indirectly equivalent to a sentence A''' in standard
form. Since ≅ is transitive and preserves the property of being non-tautologous,
L.1 will then follow from (a)-(c) by taking A to be an arbitrary non-tautology.
(a) The first part of the argument proceeds by mathematical induction on
the length of A. Clearly, if A is atomic, then A'=A is the desired sentence in EF;
and if A is of the form (B∧C) or of the form (B∨C), then we can simply put
A'=(B'∧C') or A'=(B'∨C') respectively, where B' and C' are sentences in EF suchthat B≅ B' and C≅ C' (such sentences are assumed to exist by the induction hypothesis, I.H.). If, on the other hand, A is of the form ~B, then we may distinguish four cases: (i) if B is atomic, then again A is already in EF, and we may put

If we interpret ‘≅’ as the relation of semantic equivalence (taking “A ≅ B” to mean “V(A)=V (B) for every valuation V ”) or as the classical relation of deductive equivalence (taking “A ≅B” to mean “A and B can be derived from each other in the classical sentential calculus”), then
L.1 and L.2 state some well-known results (Post (1921)). As they stand, the two lemmas inquestion are to make sure that such results only depend on V.4 and C.4.
5

5

A'=A; (ii) if B is of the form ~C, then there must exist some sentence C' in EFsuch that C≅ C' (by I.H.), and we may therefore put A'=C' (since A =~~C≅ C by
E.1 ); (iii) if B is of the form (C∧D), then we know that there are sentences X' andY' in EF such that ~C≅ X' and ~D≅ Y' (by I.H.), and so we may just put A'=(X'∨Y')(since A=~(C∧D) ≅ (~C∨~D) by E.4 ); finally (iv) if B is of the form (C∨D), thenagain there must be sentences X' and Y' in EF such that ~C≅ X' and ~D≅ Y' (byI.H.) and we may put A'=(X'∧Y') (since A=~(C∨D)≅ (~C∧~D) by E.4 ). Thus, inevery possible case, A can surely be ≅ -transformed into a sentence A' in EF.
(b) Suppose now that A' is in EF. To show that A' is indirectly equivalent tosome sentence A'' in NF we may, again, proceed by strong induction. The casewhere A' is atomic or of the form ~B' (where B' must be atomic) presents noproblem, for in that case we can simply put A''=A'; and if A' is a sentence of theform (B'∧C'), then B' and C' must be in EF, and so we may take any two sentences B'' and C'' in NF such that B'≅ B'' and C'≅ C'' (which are known to exist by
I.H.) and set A''= (B''∧C''). In case A' is of the form (B'∨C'), then again there must
be sentences B'' and C'' in NF such that B'≅ B'' and C'≅ C'' (by I.H.): we can thenproceed by induction on the number n of occurrences of ‘∧’ in (B''∨C'') to showthat there is a sentence Z in NF to which (B''∨C'') is indirectly equivalent, andthen set A''=Z: (i) if n =0, then (B''∨C'') is already in NF, and we may therefore
take Z=(B''∨C''); if n > 0 and ‘∧’ occurs in C'', then C'' must be of the form
(D1∧D2), where D1 and D2 are sentences in NF; thus (B''∨C'') = (B''∨ (D1∧ D2)) ≅((B''∨D1)∧(B''∨D2)) (by E.7 ); but both (B''∨D1) and (B''∨D2) are assumed to beindirectly equivalent to appropriate sentences in NF (by I.H.): hence, whereZ1 and Z2 are any two such sentences, the sentence Z=(Z1∧Z2) will do; finally(iii) if n >0 but ‘∧’ does not occur in C'', then we note that (B''∨C'')≅ (C''∨B'') (by
E.3 ), and the problem reduces to (ii).
(c) To conclude, assume now that A'' is in NF, and suppose A'' is a nontautology. Then A'' must be of the form B0 or of the form (B0∧ ... ∧Bn) (n > 0),
where each Bi (i ≤ n) is a sentence in NF that contains no occurrence of ‘∧’, andwhere at least one Bi (i ≤ n) involves no occurrence of opposite disjuncts (= pairsof disjuncts D1, D2 such that D1= ~D2): otherwise every valuation would assign
the value 1 to A'' (by V.3 ). In addition, every Bj (j ≤ n) which does involve occurrences of opposite disjuncts can be eliminated by repeated application of E.5(along with E.3 , E.6 ). That is, A'' can be ≅ -transformed into a sentence A° of theform C0 or of the form (C0∧ ... ∧Cm) (m ≤ n) where the Ck ’s (k ≤ m) are exactly
those sentences Bi (i ≤ n) which do not involve occurrences of opposite disjuncts. Obviously, such Ck ’s may still involve more than one occurrence of thesame variable. But such repetitions can easily be eliminated by subsequent appli6

cations of E.2 (using also E.3 and E.6 ). Thus, A° is in turn seen to be equivalent
to a sentence A''' of the form C0' or of the form (C0'∧ ... ∧Cm') where the disjunctsof each Ck ' (k ≤ m) are pairwise disjoint. And such a sentence, A''', is the desired
sentence in SF to which A'' is indirectly equivalent.
L.2

Every sentence in standard form is indirectly equivalent to a nontheorem.

To see this, we can fix upon an arbitrary sentence A in SF and distinguish twocases.
(a) Suppose first that ‘∧’ does not occur in A. Then A must be of the form
B0 or of the form (B0∨ ... ∨Bn) (n > 0), where each Bi (i ≤ n) is either a variable ora sentence consisting of ‘~’ followed by a variable. Clearly, such Bi’s are all nontheorems, for every variable is an axiom, and the result of prefacing ‘~’ to anaxiom always yields a non-theorem (by C.1 ). Also, such Bi’s are all pairwise disjoint, for A is assumed to be in SF. Thus, if A=B0, then A is a non-theorem, while
if A=(B0∨ ... ∨Bn), then A is a consequence of {B0, ..., Bn} (by n applications of
C.3 ) whence again it follows that A is a non-theorem. And obviously, A≅ A.
(b) Suppose now that A contains occurrences of ‘∧’. Then A must be of theform (B0∧ ... ∧Bn) (n > 0), where each Bi (i ≤ n) is a sentence in NF containing nooccurrence of ‘∧’. So let pj (j ≥ 0) be any variable occurring in A: by repeated application of E.5 and E.7 , A can easily be ≅ -transformed into a sentence A' of theform (B0'∧ ... ∧Bn'), where for each i ≤ n, Bi'=Bi if pj occurs in Bi, andBi'=((Bi∨pj)∧(Bi∨~pj)) otherwise. Hence, by carrying on a finite number of such
≅ -transformations (one for each variable occurring in A), A can eventually be ≅ transformed into a sentence A° of the form (C0∧ ... ∧Ck ) in which ‘∧’ occurs k ≥ ntimes and in which all the Ci’s (i ≤ k) are pairwise conjoint. But such a sentence
is a non-theorem, since it is a consequence of {C0, ... , Ck } (by k applications ofC.2 ) where each Ci (i ≤ k) is a non-theorem (as shown in (a) above). Thus, A° is
the desired non-theorem to which A is indirectly equivalent.
We have thus shown that every non-tautology is indirectly equivalent tosome sentence in SF ( L.1 ) and that every sentence in SF is indirectly equivalent
to some non-theorem (L.2 ). From this, and from the above-mentioned propertiesof ≅ , it follows that every non-tautology is a non-theorem (T.2 ).
4. Complementary Systems
We have seen that the syntactic system defined in Section 2, call it T~, is adequate to specify the set of all non-tautologies (= sentences that are assigned the7value 0 by at least one valuation) of L. Since the value assigned by a valuation V
to a sentence A is always opposite to the value assigned by V to ~A, it is clearthat the set of all non-contradictions (= sentences that are assigned the value 1 byat least one valuation) is also specifiable by means of a purely syntactic system:
just substitute ‘∨’ for ‘∧’ and ‘∧’ for ‘∨’ in C.2 -C.3 , and the resulting system,
call it C~, will do (or: just characterize C~ indirectly, by defining a sentence A to
be a non-theorem of C~ iff ~A is a non-theorem of T~). For the same reason, it isa fact that whenever a syntactic system T is given by means of which one canadequately specify the set of all tautologies (= sentences which are assigned thevalue 1 by every valuation), one can immediately define a perfectly symmetricsystem, C, which is adequate to specify the set of all contradictions (= sentences
which are assigned the value 0 by every valuation): just substitute ‘∨’ for ‘∧’ and‘∧’ for ‘∨’ in the axioms and rules of inference of T (or: just characterize C indirectly, by defining a sentence A to be a theorem of C iff ~A is a theorem of T).6
Accordingly, one would get a complete picture of the logic of L if one could
define a third pair of complementary systems, say N and N~, which are adequate
to specify the set of all contingencies (= sentences that are both non-tautologous
and non-contradictory) and the set of all non-contingencies (= sentences that areeither tautologous or contradictory) respectively. Indirectly, such systems can ofcourse be characterized in terms of T , C , T~ and C~ (just define a sentence A to
be a non-theorem of N iff A is a non-theorem of both T~ and C~, and define A to
be a theorem of N~ iff A is a theorem of either T or C). However, the argumentsof Section 3 suggest a more direct approach too. For let a sentence A count as a
Boolean sentence iff (i) A is in standard form, (ii) all conjuncts of A are pairwise
distinct, and (iii) every variable occurring in A occurs exactly once in each conjunct of A (or in A itself if A has no conjunct). Then, as axioms of N we can takeall and only those sentences A, ~A satisfying the following condition:
A.1

A is a Boolean sentence with less than 2 n conjuncts, where n is thenumber of distinct variables occurring in A

and as axioms of N~ we can take all and only those sentences A, ~A satisfying:
A.2

A is a Boolean sentence with exactly 2 n conjuncts, where n is thenumber of distinct variables occurring in A.

Taking a sentence A to count as a consequence of a set of sentences Γ in N iff C.4
holds (likewise for N~) and defining the notion of a non-theorem of N as in Sec6

See for example Morgan (1973).

8

tion 2 (likewise for N~), minor changes to the proofs of T.1 and T.2 above willshow that the resulting systems satisfy the desired requirements.7
All of these results reflect of course the fact that the relevant sets of sentences (tautologies, contradictions, contingencies, etc.) are all decidable, andshould therefore come as no surprise. The point is rather that such sets are now
seen to be on a par as far as their syntactical characterization is concerned. At
the same time, this does not mean that those sets are equally “interesting”. The
fact remains that every substitution instance of a tautology of L is a valid sentence of, say, the language of quantification theory; whereas the substitution instances of a non-tautologous sentence of L do not have to be invalid in a languagewith quantifiers. They have to be non-tautologous — but that’s all.8
References
Caicedo X., ‘A Formal System for the Non-Theorems of the Propositional Calculus’, Notre
Dame Journal of Formal Logic, 19 (1978), 147-51.
Dutkiewicz R., ‘The Method of Axiomatic Rejection for Intuitionistic Propositional Logic’,
Studia Logica, 48 (1989), 449-59.
Lukasiewicz J., Aristotle’s Syllogistic from the Standpoint of Modern Formal Logic, Oxford:
Clarendon Press, 1951.
Morgan, C. G., ‘Sentential Calculus for Logical Falsehoods’, Notre Dame Journal of Formal
Logic, 14 (1973), pp. 347-53.
Post, E. L., ‘Introduction to a General Theory of Elementary Propositions’, American Journalof Mathematics, 43 (1921), 163-85.
Scott D., ‘Completeness Proofs for the Intuitionistic Sentential Calculus’, Summaries of Talks
Presented at the Summer Institute for Symbolic Logic (Cornell University, July 1957),
Princeton: Institute for Defense Analyses, Communications Research Division, 1957, pp.
231-42.
Seager, W. E., ‘Axiomatic Nether Logic’, Typescript, University of Toronto, 1986.
Varzi A. C., ‘Complementary Sentential Logics’, Bulletin of the Section of Logic, 19 (1990),
112-16.

7

As they are, the axioms of N and N~ involve various redundancies: these can be eliminated by adding the following clauses to the definition of “Boolean sentence”: (iv) all occurrences of ‘(’ in A are adjacent, and (v) all variables occurring in A occur in alphabetical order ineach conjunct of A (or in A itself if A has no conjunct). Moreover, certain axioms could be obtained as (non-)theorems if certain rules were assumed in addition to C.4. For example, it is easy
to see that N is nothing but the weakening of T ~ obtained by inserting A.1 in the formulation of
C.2: in this sense, N would have the same axioms as T ~ and a similar (though weaker) systemof rules.
8
I would like to thank Bill Seager, whose work on “nether” logic (1986) was the sourceof my interest in the topic of this note. Bill’s generous comments on an earlier draft are also
gratefully acknowledged.

9