arXiv:1711.05816v1 [cs.AI] 15 Nov 2017

K3, Ł3, LP, RM3, A3, FDE, M:
How to Make Many-Valued Logics Work for You
Francis Jeffry Pelletier
Dept. Philosophy
University of Alberta

Allen P. Hazen
Dept. Philosophy
University of Alberta

Version of September 18, 2017

Abstract
We investigate some well-known (and a few not-so-well-known) many-valued logics that have
a small number (3 or 4) of truth values. For some of them we complain that they do not have
any logical use (despite their perhaps having some intuitive semantic interest) and we look at
ways to add features so as to make them useful, while retaining their intuitive appeal. At the
end, we show some surprising results in the system FDE, and its relationships with features
of other logics. We close with some new examples of “synonymous logics.” An Appendix
contains a natural deduction system for our augmented FDE, and proofs of soundness and
completeness.

1 Truth-Values: Many, versus Gaps and Gluts
Everyone knows and loves the two “classical” truth-values, True and False. In “classical” logic1 ,
every sentence is either T or F but not both. Before getting to the detailed issues of this paper,
we pause to make four comments of a “philosophical nature” with the intent of setting the issues
aside. First, there is the long-standing issue of whether a logic contains sentences, statements, or
propositions. We take no position on this issue: what we think of as the logical point is neutral on
this issue. Related to this, perhaps, is the issue of whether a logic should be considered a set of its
theorems or defined instead by the valid inferences it accepts. This topic does mark a distinction
in the three-valued cases we consider, and we will remark on this as the occasion arises. Second,
there are logics – perhaps not “classical” ones – that would prefer to claim the objects of interest
are (e.g.) obligations, or commands, or ethical/epistemic items, rather than T and F. Perhaps the
items that have such values are not to be considered ‘sentences’ but rather exhortations or promises
1
There are those (e.g., Priest, 2006) who claim that this common terminology of ‘classical’ betrays a bias and is
in fact incorrect as an account of the history of thought about logic. We won’t attempt to deal with this, and will
just use the common terminology. For a more comprehensive review of topics and issues relevant to truth values see
Shramko and Wansing (2017)

1

or. . . ? If so, then we say that we are restricting our attention to (declarative) sentences. Third, while
‘sentence’ seems appropriate for propositional logic, some further accommodation is required for
formulas of predicate logic. The present paper is mostly concerned with propositional logic, and
so we will simply use ‘sentence’. And finally, there is the philosophical issue of whether T and
F should be considered to be objects– perhaps existing in a “third realm” – or as properties of
sentences. Our view is that this distinction – which is maybe of considerable philosophical interest
– does not affect any of the claims we will be making, and so we just will pass over it in silence.
So, given that T and F are so revered, where does this leave many-valued logic? One intuition
that has been held by very many theorists is that there simply are more than just the T and F truth
values. Some of these theorists hold that various phenomena show that there is another category
beyond T and F: perhaps we should call it I for Indefinite. Presupposition failures in a formula
might determine that it is I; vagueness might determine that a formula is I; the unactualized (as yet)
future might determine that some formulas are I; fictional discourse seems neither straightforwardly
true or false, so perhaps sentences about fictional objects also should be I. And there no doubt are
other types of formulas that could intuitively be thought to be “indeterminate”.
(1) a.
b.
c.
d.

The present Queen of Germany is happy.
That 45-year-old man is old.
There will be a Presidential impeachment in the next 30 years.
James T. Kirk is captain of the starship Enterprise.

Some theorists, agreeing with the just-expressed intuition that the sentences in (1) are neither T nor
F, nonetheless wish to deny that they designate a third value. Rather, they say, such sentences lack
a truth-value (i.e., are neither T nor F; nor are they I, since they deny such a value). Such sentences
have no truth-value: they express a truth-value gap. And logics that have this understanding are
usually called “gap logics.”
Formally speaking, there is little difference between the two attitudes of expressing I or being a
gap. In both cases one wishes to know how to evaluate complex sentences that contain one of these
types of sentences as a part. That is, we need a way to express the truth-table-like properties of this
third option. In the remainder of this paper we will use N for this attitude, whether it is viewed as
expressing I or as being a gap. (The N can be viewed as expressing the notion “neither T nor F”,
which is neutral between expressing I or expressing a gap.) And we will call the logics generated
with either one of these understandings of N, “gap logics.”
Gap logics – whether taken to allow for truth values other than T and F, or instead to allow for
some sentences not to have a truth value – are only one way to look at some recalcitrant natural
language cases. Other theorists point to some different phenomena in their justification of a third
truth value. The semantic paradoxes, such as the Liar Paradox (where the sentence “This sentence
is false” is false if it is true, and is true if it is false) suggest that some statements should be treated
as both true and false. It is difficult to deal with this paradox in a gap logic, because saying that
“This sentence is false” is neither true nor false leads immediately to the strengthened Liar Paradox:
“Either this sentence is false or else it is neither true nor false”. Here it seems that claiming that the

2

sentence expresses a gap leads to truth, while saying that it is true leads to falsity and saying that
it is false leads to truth. In contrast, to say that the sentence “This sentence is false” is both true
and false does not lead to this regress: The sentence “This sentence is either false or else is both
true and false” leads only to the conclusion that it is both true and false. This dialetheic theory –
that some sentences are both true and false – is called a “glut theory” because of the presence of
both truth values characterizing some sentences. The intermediate value, on this conception, can
be called B (for “both”), and we will use this.
There are also examples from naı̈ve set theory such as the Paradox of Well-Founded sets, the
Paradox of a Universal Set, Russell’s Paradox, and Richard’s Paradox (see Cantini (2014) for a
historical overview of these). There is a desire on the part of some theorists in the philosophy of
mathematics to reinstate naı̈ve set theory and use it in the development of mathematics, instead
of (for example) Zermelo-Frankel set theory. Such theorists perhaps will feel encouraged in their
belief that the glut-style of resolution of the Liar Paradox might be usable in the case of these other
set theoretic paradoxes, and that naı̈ve set theory can once again be used.
Various theorists have pointed out that vagueness needn’t be viewed as missing a truth-value; it
is equally plausible to think of vagueness as manifesting both the positive character and its absence.
A middle-height person can be seen as both short and tall, equally as plausibly as being neither
short nor tall. (See Hyde (1997); Beall and Colyvan (2001); Hyde and Colyvan (2008).) As well,
certain psychological studies seem to indicate that the “dialetheic answer” is more common than
the “gap” answer, at least in a wide variety of cases (see Alxatib and Pelletier (2011); Ripley (2011)
for studies that examine people’s answers to such cases).
There are also other categories of examples that have been discussed in philosophy over the
ages: Can God make a stone so heavy that He can’t lift it? Perhaps the answer is, “Well, yes and
no.” There are cases of vague predicates such as green and religion, e.g., an object can be both
green and not green, and a belief system can be both a religion and not a religion. There are legal
systems that are inconsistent, in which an action is both legal and illegal. In the physical world,
there is a point when a person is walking through a doorway at which the person is both in and not
in the room. And so on. As a result, the glut theory has its share of advocates.
A way to bring the gap and glut views of the truth values under the same conceptual roof is to
think of the method that assigns a truth value to formulas as a relation rather than a function. A
function, by definition, assigns exactly one value to a formula – either T or F or, in the context of
our 3-valued logics, it may also assign B or I. A relation, however, can assign more than one value:
we may now think that there are exactly two truth values, T and F, but the assignment relation can
assign subsets of {T, F}. A gap logic allows assignment of {T}, {F}, and ∅. A glut logic allows {T},
{F}, and {T, F}.
But both the gap and the glut logics seem to have difficulties of a logical nature that we will
examine in §4.

3

2 K3 and LP: The Basic 3-Valued Logics
In all of the 3-valued logics we consider, the 3-valued matrices for ∧, ∨, ¬ are the same, except for
what the “third value” is called: in K3 (Kleene, 1952, §64) we call it N but in LP (Asenjo, 1966;
Priest, 1979) we call it B.
One way to understand why the K3 truth values for these connectives are correctly given in the
following tables is to think of N as meaning “has one of the values T or F, but I don’t know which
one”. In this understanding, a negation of N would also have to have the value N; a disjunction
with one disjunct valued N and the other T would as a whole be T. . . but if one were valued N and
the other F, then as a whole it would have to be N. Similar considerations will show that the ∧
truth table is also in accord with this understanding of the N value. (This interpretation of the truth
values presumes that one pays no attention to the interaction of the connectives: (p ∧ ¬p) seems to
be false and (p ∨ ¬p) seems true, but that’s because of the interaction of two connectives.)
On the other hand, if the middle value is understood as being both true and false as in LP, we
will still get those same truth tables, with only a change of letter from N to B: negating something
that is both true and false will yield something that is both false and true. If a disjunction had
one disjunct valued B and the other T, then the entire disjunction would be valued T. But if that
second disjunct were valued F instead, then the entire disjunction would be valued B. Similar
considerations will show that the ∧ truth table is also in accord with this understanding of the B
value.
∧
T
N/B
F

T
T
N/B
F

N/B
N/B
N/B
F

F
F
F
F

∨
T
N/B
F

T
T
T
T

N/B
T
N/B
N/B

F
T
N/B
F

¬
T
N/B
F

F
N/B
T

Despite the apparent identity of K3 and LP (other than the mere change of names of N and B),
the two logics are in fact different by virtue of their differing accounts of what semantic values are
to be considered as privileged. That is, which values are to be the designated values for the logic
– those values that are semantically said to be the ones that the logic is concerned to manifest in
a positive light. In both logics this positivity results from the value(s) that exhibit (at least some
degree of) truth: but in K3 only T has that property whereas in LP both T and B manifest some
degree of truth. And therefore LP treats the semantically privileged values – the designated values
– to be both T and B, while in K3 the only designated value is T.
Although both K3 and LP have no formula whose value is always T, LP (unlike K3) does have
formulas whose semantic value is always designated. In fact, the class of propositional LP formulas
that are designated is identical to that of propositional classical 2-valued logic, a fact to which we
return in §4.
Note that these truth tables give the classical values for compound formulas with classical
components, and give the intermediate value for formulas all of whose components have that value.
Thus neither logic is functionally complete: no truth function giving a non-classical (classical)
value for uniformly classical (non-classical) arguments can be represented in them.
4

3 FDE and M: Four-Valued Logics
The logic FDE was described in (Belnap, 1992) and (Dunn, 1976). It is a four-valued system: the
values are T, F, B, and N. . . the four values we have already encountered2 (although the intuitive
semantics behind these values, as given by Belnap, are perhaps somewhat different than we encountered above). K3 and LP agree with each other (and with classical logic) as regards the values
T and F, so in combining them it is easy to identify K3’s T and F with LP’s T and F. FDE then
agrees with K3 about N: agrees that it is not a designated value, and agrees on the values of combinations of N with T and F. FDE also agrees with LP about B: agrees that it is a designated value,
and agrees on the values of combinations of B with T and F. Neither of the three-valued logics
allow combinations of B with N, so these combinations need a bit more thought. The choice made
is perhaps most easily described by representing the four values as sets of the two classical values:
T={T}, B={T,F}, N={ }, F={F} (where of course the bold-face values stand for FDE values and the
normal text values stand for classical ones!). A given classical value then goes into the set of values
of a compound formula just in case the component formulas have values containing classical values
which, by the classical rules, would yield the given value for the compound. (This way of thinking
also makes the designation statue of B and N seem natural: an FDE value is designated just in case
it, thought of as a set, contains the classical value T.)
This treatment of the four values and their ordering is perhaps best visualized by the diagram:
T
N

B
F

The four values form a lattice, with the value of a conjunction (disjunction) being the meet (join) of
the values of its conjuncts (disjuncts), and with negation interpreted as inverting the lattice order.
More formally, we take the basic truth-tables for ∧, ∨ and ¬ to be straightforwardly taken from
K3 and LP, for the values that do not involve only B and N together. For those values we interpolate
as given in the truth tables in Table 1 for the FDE connectives.

4 What’s Wrong with K3, LP, and FDE
We start with K3 and LP. Note that the ∧, ∨, ¬ truth-functions always yield a N (or a B) whenever
all the input values are N (or B, respectively). This means that there are no formulas that always
take the value T. In these logics, those three truth functions are all of the primitive functions, and
so that same fact also implies that not every truth function is definable in K3 (or LP). And if ϕ’s
being semantically valid means that ϕ always takes the value T for all input values, as it does in
K3, then there are no semantically valid formulas in K3.
2

Or, returning to the conception of a relational assignment, FDE allows any subset of the two “real” truth values:
{T}, {F}, {T, F}, and ∅.

5

ϕ
T
T
T
T
B
B
B
B
N
N
N
N
F
F
F
F

ψ
T
B
N
F
T
B
N
F
T
B
N
F
T
B
N
F

¬ϕ
F

B

N

T

(ϕ ∧ ψ)
T
B
N
F
B
B
F
F
N
F
N
F
F
F
F
F

(ϕ ∨ ψ)
T
T
T
T
T
B
T
B
T
T
N
N
T
B
N
F

Table 1: Four-valued truth-tables for the basic connectives of FDE

And given that these are all the primitive truth functions, then the only plausible candidate for
being a conditional in these logics comes by way of the classical definition: (ϕ ⊃ ψ) =d f (¬ϕ ∨ ψ).
ϕ
T
T
T
N/B
N/B
N/B
F
F
F

ψ
T
N/B
F
T
N/B
F
T
N/B
F

(ϕ ⊃K3 ψ)
T
N
F
T
N
N
T
T
T

(ϕ ⊃LP ψ)
T
B
F
T
B
B
T
T
T

Table 2: Conditionals available in K3 and LP, using the classical definition

The only difference between ⊃K3 and ⊃LP is that in K3 the “third value” is understood as
indicating a truth-value gap, i.e., as neither T nor F, whereas whereas in LP it is understood as
indicating a truth-value glut, i.e., as both T and F.

6

One notes that the rule of inference, Modus Ponens (MP), (ϕ ⊃K3 ψ), ϕ  ψ, is a valid rule in
K3: if both premises are T, then the conclusion will also be, as can be seen from the truth table for
⊃K3 . Despite this, the statement of MP, ((ϕ ⊃K3 ψ) ∧ ϕ) ⊃K3 ψ, does not always exhibit the value T
(since no formula of K3 always takes the value T). Thus the deduction theorem does not hold for
K3. Matters are the reverse for the logic LP: the rule of MP is invalid, as can be seen by making ϕ
be B and ψ be F. In that case both (ϕ ⊃LP ψ) and ϕ have designated values (both are B), but yet the
conclusion, ψ, is F. On the other side, the statement of MP, ((ϕ ⊃LP ψ) ∧ ϕ) ⊃LP ψ, is always T.
(One can see that the counterexample to the rule MP makes both conjuncts of the antecedent be B
and hence that antecedent is B. But a B antecedent with a F consequent is evaluated B. Hence the
statement is designated.)
As we remarked above, the theorems of LP are identical to those of classical logic – LP does
nothing more than divide up the classical notion of truth into two parts: the “true-only” and the
“true-and-also-false”. As both types of truth are designated values in the logic, the theorems of
the two are the same, and hence LP is not different from classical logic so far as logical truth
goes. Where it does differ is in the class of valid rules of inference, as we have noted. The reverse
describes the situation in K3: whereas the deduction theorem holds and modus ponens fails for LP,
in K3 the deduction theorem fails but modus ponens holds.
So, it seems that both K3 and LP are not very useful as guides to reasoning, despite their
apparent (to some) virtues in accounting for intuitive semantic values of sentences that exhibit
some troublesome features (such as vagueness or semantic paradox). After discussing the logical
state of K3 and LP, and the disappointing properties of the conditional operators available in them,
Soloman Feferman put it:
Multiplying such examples, I conclude that nothing like sustained ordinary reasoning
can be carried on in either logic. (Feferman, 1984, p. 264, italics in original.)
On the topic of non-classical logics more generally, van Fraassen (1969) expresses the worry in
more picturesque terminology. New logics, he worries, along with “the appearance of wonderful
new ‘logical’ connectives, and of rules of ‘deduction’ resembling the prescriptions to be read in The
Key of Solomon” will make “standard logic texts read like witches’ grimoires”, and will “incline
one to dismiss the technical study of [non-classical logic] as a mathematical parlor game.”
Turning now to FDE, it is clearly a merger of K3 and LP, so shares all their shortcomings. Since
FDE includes the feature of K3 that there are no truth functions from all-atomics-having-the-valueN to any other truth value, it follows that there are no formulas that always take one or the other
of the designated values T or B. And as with K3, the logic is functionally incomplete since there
is no formula that will yield one of T, B, or F if all its atomic letters are assigned N. Like K3 and
LP, FDE does not have a usable conditional and hence there is no sense in which it is a logic that
one can reason with. Although Feferman (1984) didn’t include FDE in his disparaging remarks we
just quoted, since FDE is simply a “gluing together ” of K3 and LP – the two logics Feferman did
complain about – it is clear that he would have held the same opinion about FDE.
We wish to show that matters are not so dire as Feferman seems to think for the FDE-related
logics we are investigating. And so we now turn to possible ways to fix these shortcomings.
7

5 An FDE Fix?
Various researchers have added conditionals to K3 and LP, with the thought of being able to do
“sustained reasoning” in these logics. We might mention here Łukaseiewicz’s conditional added
to K33 , with the intent of accommodating “future contingents.” This yields a logic that is usually
called Ł3. And conditionals can be added to LP with the intent of allowing reasoning to take place
in the context of dialetheism. We will look here at the more closely at the logics RM3 and a logic
we will call LP+cmi that are generated by adding different conditionals to LP.
Although the metamathematical study of RM3 has been fruitful in the study of relevance logics,
it seems to us that LP+cmi is likely to be a more convenient to use4 – particularly in light of Tedder’s
2015 employment of it in formulating mathematically interesting axiomatic theories. Somewhat to
our surprise, it generalizes to the 4-valued case!
Here is the conditional we propose: we call it the “classical material implication” (or “cmi”)
and we symbolize it →cmi .
→cmi
T
B
N
F

T
T
T
T
T

B
B
B
T
T

N
N
N
T
T

F
F
F
T
T

Table 3: Truth matrix for →cmi .
In §3 we remarked that the natural understanding of FDE’s semantic values is that the designated ones are T and B, while the undesignated ones are N and F. As can be seen in Table 3, any
conditional that takes a designated value has the feature that if its antecedent is also designated,
then its consequent will be also. It can also be seen that if the values are restricted to the classical
T and F, then the conditional mirrors the classical ⊃. We also obtain the truth table for the classical ⊃ if we look at this with blurred vision, so that the two designated values blur into one and
the two undesignated values similarly coalesce, showing that the valid formulas (i.e., those taking
a designated value on every assignment of truth values to their atoms) and inferences (i.e., those
preserving designation on every assignment) are precisely those of the pure ⊃ fragment of classical
logic. Combined with a similarly blurred view of the truth tables for ∧ and ∨ we can extend this
observation to formulas having these connectives as well as →cmi , and we can extend it further to
quantifiers if we think of them as generalized conjunctions and disjunctions. Thus:
Proposition 1. For positive formulas (i.e., those not containing ¬), the valid formulas and inferences of FDE+cmi are exactly those of classical logic.
3
Although of course this is not the historical reason he came up with his conditional, since he didn’t have K3 before
him at the time.
4
Tedder uses the name A3 for what we call LP+cmi. Since we are comparing a number of logics, we prefer a more
systematic nomenclature.

8

The 4-valued logic FDE+cmi has two obvious 3-valued extensions, defined semantically by
restricting the set of truth values allowed: K3+cmi defined by reference to {T,N,F} and LP+cmi
defined by reference to {T,B,F}. These logics result from the addition of a conditional connective,
→cmi , defined by the relevant rows of the matrix of Table 3, to the conditional-free logics K3 and
LP.

5.1 FDE+cmi
The classical nature of the conditional in FDE+cmi makes it a much more pleasant item to work
with than most previously proposed conditionals in many-valued logics: something like sustained
ordinary reasoning can be carried out in FDE+cmi and in its 3-valued extensions. However, although the positive logic is completely classical, there are some surprises in the interaction of →
(we will henceforth leave the subscript off this operator) with negation. One unpleasant one is that
the principle of Contraposition fails: if JϕK = T and JψK = B, then Jϕ → ψK takes the designated value B, but J¬ψ → ¬ϕK is F. And also, if JϕK = N and JψK = F, then Jϕ → ψK=T, but
J¬ψ → ¬ϕK= F. Since a counterexample can be obtained using either of the nonclassical values,
Contraposition is invalid not only in FDE+cmi but also in both of its 3-valued extensions K3+cmi
and LP+cmi.
We can, of course, define a new conditional connective for which Contraposition holds:
(ϕ ⇒ ψ) =d f ((ϕ → ψ) ∧ (¬ψ → ¬ϕ))
This is a useful connective! The corresponding biconditional
(ϕ ⇔ ψ) =d f ((ϕ ⇒ ψ) ∧ (ψ ⇒ ϕ))
takes a designated value if and only if JϕK = JψK. (Note that J(ϕ ⇔ ψ)K=B if JϕK = JψK = B,
and =T if JϕK and JψK have one of the other three values.) As a result, it supports a principle of
Substitution: formulas of the form
(ϕ ⇔ ψ) → ((· · · ϕ · · · ) ⇔ (· · · ψ · · · ))
are valid. (In contrast, the biconditional similarly defined in terms of our basic conditional yields
a designated value just in case either both of its terms have designated values or both have undesignated values. As a result, it does not license substitution: If ϕ and ψ have different designated
values, and also if they have different undesignated values, (ϕ ↔ ψ) will have a designated value,
but (¬ϕ ↔ ¬ψ) will not. On the other hand, ↔ can be added to the list of “positive” connectives,
∧, ∨, →, whose logic is exactly classical.)
On the other hand, the ⇒ connective has certain undesirable features which militate against its
adoption as the basic conditional operator of a logic designed for use. Principles analogous to some
of the structural rules of (Gentzen, 1934), easily derivable by the conventional natural deduction
rules for the conditional, fail for it. Some also fail for ⇒ in K3+cmi, and others in LP+cmi.

9

5.2 On the K3 Side
The truth tables for → and ⇒ differ on only one of the nine lines for K3, as indicated in Table 4: if
JϕK=N and JψK=F, then Jϕ → ψK=T but Jϕ ⇒ ψK=N.
ϕ
T
T
T
N
N
N
F
F
F

ψ
T
N
F
T
N
F
T
N
F

(ϕ → ψ)
T
N
F
T
T
T
T
T
T

(ϕ ⇒ ψ)
T
N
F
T
T
N
T
T
T

⇐

Table 4: Comparison of two conditionals in K3+cmi

This is enough, however, to invalidate the principle of Contraction:
(ϕ ⇒ (ϕ ⇒ ψ)) ⇒ (ϕ ⇒ ψ)
This should be old news! The derived truth table for ⇒ in K3+cmi is exactly that of the conditional
of Łukasiewicz’s 3-valued logic, for which Contraction failure is familiar. Since the interpretations
of the other connectives are the same for K3 and Ł3, we have
Proposition 2. Łukasiewicz’s 3-valued logic is faithfully interpretable in K3+cmi.
In fact, we have the converse as well5 : our → can be defined in Ł3 by
(ϕ → ψ) =d f (ϕ ⇒ (ϕ ⇒ ψ)),
so K3+cmi is faithfully interpretable in Ł3. K3+cmi and Ł3 can thus be seen as, in effect, alternative formulations of a single logic (see further discussion in Section 7). We think the classical
nature of → makes it easier to use than ⇒, and recommend translation into K3+cmi to anyone
interested in proving theorems in Ł3.

5.3 On the LP Side
Now looking at the logic with truth values {T,B,F}, we see in Table 5 that ⇒ again differs from →
on only one of the nine lines: but this time if JϕK=T and JψK=B, then Jϕ → ψK=B but Jϕ ⇒ ψK=F.
5
(Nelson, 1959) should be credited with the observations of the failure of contraposition, its brute force restoration,
and contraction failure in his system of constructible falsity. . . which is essentially the addition of intuitionistic implication to K3. What our observation adds to this is that these phenomena do not depend on the intuitionistic nature of
Nelson’s implication, but arise already in the 3-valued and 4-valued logics.

10

ϕ
T
T
T
B
B
B
F
F
F

ψ
T
B
F
T
B
F
T
B
F

(ϕ → ψ)
T
B
F
T
B
F
T
T
T

(ϕ ⇒ ψ)
T
F
F
T
B
F
T
T
T

⇐

Table 5: Comparison of two conditionals in LP

This difference in truth table is enough to invalidate the principle of Thinning:
ϕ ⇒ (ψ ⇒ ϕ)
If JϕK = B and JψK = T, then Jψ ⇒ ϕK and hence Jϕ ⇒ (ψ ⇒ ϕ)K will both be F. As Tedder (2015)
notes, ⇒ in LP+cmi has exactly the truth table of the logic RM3 (and, since RM3 is a cousin of the
relevance family of logics, failure of Thinning in it is just what one would expect). RM3 and LP
agree on {∧, ∨, ¬}, so we have
Proposition 3. RM3 can be faithfully interpreted in LP+cmi.
Again, the converse is also true: → can be defined in terms of ⇒ in RM3 by
(ϕ → ψ) =d f ((ϕ ⇒ ψ) ∨ ψ)
So in the same sense, RM3 and LP+cmi can be thought of as alternative formulations of a single
logic (see discussion in Section 7), and again, we think adoption of → as primitive is likely to be
more convenient.

5.4 About M
Given that K3 and LP are obtained semantically from FDE by adding different conditions on valuations, and syntactically by adding different rules, one might incautiously conjecture that the FDE
consequence relation is simply the intersection of the K3 and LP relations. Not so: (ϕ∧¬ϕ) implies
(ψ ∨ ¬ψ) in both 3-valued logics, but not in FDE. There is thus a fifth logic in the neighbourhood,
which is sometimes called Mingle and which we will unimaginatively call M.

11

CL
LP

K3
M
FDE

It is characterized semantically as the set of inferences preserving designation on every FDE
valuation which does not assign B to one formula and N to another, and syntactically by adding
the above-mentioned inference as a general rule to a formulation of FDE. We think M seems like
a rather silly logic (why should the presence of a single truth-value glut rule out the existence of
any truth-value gaps, or vice versa?), but record here that M+cmi can be formulated in the obvious
way, and that our completeness proof in the Appendix for FDE+cmi extends without difficulty to
cover it.

5.5 Putting them Together
We have not explored the behaviour of ⇒ in FDE+cmi, and, in contrast to the situation with the
3-valued logics, do not know of a historically proposed equivalent for it. Contraction and Thinning
will, of course, both fail for ⇒ in the 4-valued logic. With no relevant insight, we have resorted to
construction of truth tables to verify that → can be recovered from ⇒ in the 4-valued environment
by the double-barrelled definition.
(ϕ → ψ) =d f ((ϕ ⇒ (ϕ ⇒ ψ)) ∨ ψ)

6 More and Less Drastic Expansions
In Hazen and Pelletier (2017) it was shown that a Second Order logic based on LP was surprisingly
weak. This was due to the limited expressive power of the language with no conditional operator.
In contrast, FDE+cmi, with its classical conditional, can be shown to contain full classical Second
Order Logic. Using propositional quantification, we can define a falsum propositional constant:
f = ∀p(p)
(Obviously set/property quantification would do as well: ∀X∀x(X(x)).) This constant and the
conditional give us in effect a “classical” negation: the conditional (ϕ → f) takes the value F when
JϕK is designated and the T when JϕK is undesignated. Call a predicate (monadic or relational)
classical just in case no atomic formula in it, on any assignment to the individual variables, takes
either of the intermediate truth values N or B. N can be ruled out by the First Order formula
∀x(ψ(x) ∨ ¬ψ(x)), which will not take a designated value if the predicate yields the value N for any
individual in the domain. The possibility that ψ somewhere yields the value B, however, cannot be
12

excluded by a purely First Order formula: if ψ yields B for every individual, then every First Order
formula in which ψ is the only bit of non-logical vocabulary occurring will have the designated
value B. Using the ersatz classical negation, however, we can say ((∃x(ψ(x) ∧ ¬ψ(x)) → f). The
classicality of the predicate, then, can by expressed by the conjunction of these two formulas. We
may then interpret classical Second Order Logic in Second Order FDE+cmi by simply restricting
all Second Order quantifiers to classical predicates.
Coming back down to the fragment of Second Order FDE+cmi with only propositional quantification, we can define the other three propositional constants. Verum is easy:
t = ∃p(p)
Defining a constant for B is perhaps less obvious. ∃p(p ∧ ¬p) would work in the 3-valued logic
LP, but when N is also available it fails: JpK = B gives Jp ∧ ¬pK = B, JpK = N gives Jp ∧ ¬pK = N,
and the existential quantification will have as value the join of these in the truth-value lattice: T!6
However, Jp → pK=B when JpK=B, and is T otherwise, so we may define
b = ∀p(p → p)
Defining a constant for N in FDE+cmi is altogether harder (though ∃p(p ∧ ¬p) would work
in the 3-valued logic K3+cmi). Indeed, it can be shown that no definiens with, in prenex form, a
single block of propositional quantifiers (all universal or all existential) will work.
Proof. Consider a purely propositional formula of FDE+cmi. An assignment giving the value B to
all of its variables will give the formula the value B. Thus the set of values assumed by the formula
on different assignments to its propositional variables will include B. The value of the sentence
formed by binding its variables by existential quantifiers will be the lattice join of the values in this
set, and so must be either B or T. The value of the sentence formed by binding its variables by
universal quantifiers will be the lattice meet of the values in this set, and so must be either B or F.
In neither case will the quantified formula serve as a definiens for the constant n.

The propositional constant n can, however, be defined by a sentence of more complicated
quantificational structure. J(ϕ ⇔ ψ)K is designated if and only if JϕK = JψK. It can thus be thought
of as expressing identity of truth value. The conditional ((ϕ ⇔ t) → f), then, says that the value of
ϕ is not T, and similarly for ((ϕ ⇔ b) → f) and ((ϕ ⇔ f) → f). So we may define n by
n =d f ∃q(((q ⇔ t) → f) ∧ ((q ⇔ b) → f) ∧ ((q ⇔ f) → f) ∧ q)
For, if q in the matrix is assigned one of the values T, B, or F, one of the first three conjuncts, and so
the whole, will have the value F. If JqK=N, however, the first three conjuncts will all have the value
T, but the fourth, q, and so the whole conjunction, will have the value N. Since the join of F and N
is N, the value of the full, quantified, sentence is N. By extracting the quantifiers concealed in the
6
The existentially quantified formula takes the join of the values N, B, and F. . . which, surprisingly, is T. One
doesn’t expect a disjunction to take a higher value than any of its disjuncts, but in this case, because the four values are
not linearly ordered, it does.

13

propositional constants in the contained biconditionals in the right order, we can put the definiens
into prenex form with only one alternation of quantifiers (so, it will be Σ2 ).
A final observation. Propositional FDE+cmi, unaugmented, is not functionally complete: no
4-valued truth function mapping uniformly classical arguments to an intermediate value, or mapping uniformly B arguments to a value other than B, can be represented. Adding the four propositional constants (now thought of as primitives) gives us functional completeness, for an arbitrary n-ary truth function can be expressed by the conjunction of 4n conditionals, each having as
antecedent an n-place conjunction of ⇔ biconditionals specifying a set of values for the arguments, and as consequent the constant for the desired value. That is, we can say in the language
that a formula takes a particular one of the semantic values, thus mimicking the “parametric” Joperators of (Rosser and Turquette, 1952), and together with the defined truth-constants, we can
construct DNF or CNF formulas that manifest any 4-valued truth table by using the technique of
(Rosser and Turquette, 1952).

7 Synonymous Logics
In Pelletier (1984); Pelletier and Urquhart (2003), the notion of “translational equivalence” was
introduced and defined, and used to describe a concept of synonymous logics. This concept was
intended to describe cases where two logic systems were “really the same system” despite having
different formulations, different vocabulary, and possibly having such different formulation that it
would not be at all obvious that the logics were “really the same.” This notion was shown to be
different from various other conceptions in the literature, such as mutual interpretability and having
exact translations between logics, which were shown to be weaker; other notions, such as having
identical definitional extensions, were shown to be the same conception.7
Two logics, L1 and L2 , are translationally equivalent if and only if there are translation schemes
t1 from L1 into L2 and t2 from L2 into L1 such that
1. if ⊢L1 ϕ then ⊢L2 ϕt1
2. if ⊢L2 ϕ then ⊢L1 ϕt2
3. for any formula ϕ in L1 , (ϕt1 )t2 is equivalent to ϕ (in L1 )
4. for any formula ϕ in L2 , (ϕt2 )t1 is equivalent to ϕ (in L2 )8
7

Further aspects of the notion, as well as formal details, are in Pelletier and Urquhart (2003).
In Pelletier and Urquhart (2003) it was assumed that the logics in question had a “biconditional equivalence connective” and the third and fourth conditions were expressed in terms of the biconditional being a theorem in the appropriate
logics. In the context of that paper, the logics were classical except for modal operators, and so there were such equivalence operators in each logic. In the present context, we cannot assume that the biconditionals of the various logics will
operate in the same way, and so we envisage checking the “equivalent to” conditions semantically, by simply looking at
the relevant truth tables.
8

14

We are in a position to show some new results of synonymity of logics. Since the languages
of our different logics are identical except for their (bi)conditionals, we will employ the following
translations for all the portions of the logics involved except the differing (bi)conditionals in the
logics:
• For ϕ an atomic sentence, (ϕ)t is ϕ
• For negated formulas, (¬ϕ)t is ¬(ϕ)t
• If ◦ is any binary operator other than a conditional, (ϕ ◦ ψ)t is ((ϕ)t ◦ (ψ)t )
In §5.2 we showed that systems K3+cmi and Ł3 could be faithfully interpreted in each other.
We can now prove a stronger result.
Theorem 1 (K3+cmi and Ł3 are synonymous logics). Let (ϕ →K3+cmi ψ)t1 be (ϕ →Ł3 (ϕt1 →Ł3
ψt1 )), and let (ϕ →Ł3 ψ)t2 be (ϕ ⇒K3+cmi ψ)). . . . i.e., [(ϕ →K3+cmi ψ) ∧ (¬ψ →K3+cmi ¬ϕ)].
Then the four conditions for translational equivalence are met: the first two by the facts of
identity of translations for all connectives except conditionals, and for conditionals by the truth
tables for →Ł3 and →K3+cmi . The second two are met because the stated translations t1 and t2 of
this theorem “cycle” – that is, they each immediately introduce a conditional formula in the other
logic which in turn will be eliminated when translated back into the first logic.
Note that ((ϕ →K3+cmi ψ)t1 )t2 = (ϕ ⇒K3+cmi (ϕ ⇒K3+cmi ψ)), which – in primitive notation – is
[ϕ →K3+cmi ((ϕ →K3+cmi ψ) ∧ (¬ψ →K3+cmi ¬ϕ))] ∧
[¬((ϕ →K3+cmi ψ) ∧ (¬ψ →K3+cmi ¬ϕ)) →K3+cmi ¬ϕ]
This last formula and (ϕ →K3+cmi ψ) can be checked using the 9-row K3+cmi truth tables to show
their equivalency.
Note also that ((ϕ →Ł3 ψ)t2 )t1 = [ϕ →Ł3 (ϕ →Ł3 ψ)] ∧ [¬ψ →Ł3 (¬ψ →Ł3 ¬ϕ)] which can also
be checked in the 9-row truth tables for Ł3 to demonstrate its equivalence to (ϕ →Ł3 ψ).
In §5.3 we showed that systems LP+cmi and RM3 could be faithfully interpreted in each other.
We can now prove a stronger result.
Theorem 2 (LP+cmi and RM3 are synonymous logics). Let (ϕ →LP+cmi ψ)t1 be ((ϕ →RM3
ψ) ∨ ψ), and let (ϕ →RM3 ψ)t2 be (ϕ ⇒LP+cmi ψ)). . . . i.e., [(ϕ →LP+cmi ψ) ∧ (¬ψ →LP+cmi ¬ϕ)].
Then the four conditions for translational equivalence are met, in pretty much the same way as
they were met in the previous theorem, keeping in mind that →K3+cmi and →LP+cmi are different, as
are ⇒K3+cmi and ⇒LP+cmi .
These instances of synonymous logics strike us as both unexpected and also as “cleaner” versions of synonymy of logics than the one(s) displayed in (Pelletier and Urquhart, 2003), which
employed a propositional constant in one of the logics. As remarked in Pelletier and Urquhart
(2003), two logics are translationally equivalent in this way if and only if they have a common definitional extension. Note then for each of our pairs of synonymous logics, the appropriate 3-valued
logic with two conditional operators, →cmi and ⇒cmi is a definitional extension of both members
of the pair. And thus the two logics are translationally equivalent to each other.
15

8 Concluding Remarks
We have discussed a family of logics that are related to FDE, showing how they are related to
each other and also to some other logics that have populated the literature (such as Ł3 and RM3).
Surprisingly, perhaps, we are also able to show some new and “cleaner” examples of synonymous
logics (in the sense of Pelletier and Urquhart, 2003). Deductive systems for the various logics, as
well as soundness and completeness proofs are in the Appendices.

16

References
Alxatib, S. and F. J. Pelletier (2011). The psychology of vagueness: Borderline cases and contradictions. Mind and Language 26, 287–326.
Asenjo, F. (1966). A calculus of antinomies. Notre Dame Journal of Formal Logic 7, 103–105.
Beall, J. and M. Colyvan (2001). From heaps of gluts to hyde-ing the sorites. Mind 110, 401–408.
Belnap, N.D., J. (1992). A useful four-valued logic: How a computer should think. In A. Anderson, J. N.D. Belnap, and J. Dunn (Eds.), Entailment: The Logic of Relevance and Necessity, Volume II. Princeton UP. First appeared as “A Useful Four-valued Logic” Modern Use of
Multiple-valued Logic J.M. Dunn and G. Epstein (eds.), Dordrecht: D. Reidel, 1977; and “How a
Computer Should Think” Contemporary Aspects of Philosophy G. Ryle (ed.), Oriel Press, 1977.
Cantini,
A.
(2014).
Paradoxes
and
Contemporary
Logic.
In
E.
Zalta
(Ed.),
The
Stanford
Encyclopedia
of
Philosophy.
http://plato.stanford.edu/archives/fall2014/entries/paradoxes-contemporary-logic/.
Dunn, J. (1976). Intuitive semantics for first degree entailment and coupled trees. Philosophical
Studies 29, 149–168.
Feferman, S. (1984). Toward useful type-free theories, I. Journal of Symbolic Logic 40, 75–111.
Reprinted in Robert L. Martin (ed.) Recent Essays on Truth and the Liar Paradox, pp. 237–288,
Oxford: Clarendon Press. Page references to this reprinting.
Fitch, F. (1952). Symbolic Logic: An Introduction. NY: Ronald Press.
Gentzen, G. (1934). Untersuchungen über das logische Schließen, I and II. Mathematische
Zeitschrift 39, 176–210, 405–431. English translation “Investigations into Logical Deduction”
published in American Philosophical Quarterly 1: 288–306 (1964), and 2: 204–218 (1965).
Reprinted in M. E. Szabo (ed.) (1969) The Collected Papers of Gerhard Gentzen, North-Holland,
Amsterdam, pp. 68–131. Page references to the APQ version.
Hazen, A. P. and F. J. Pelletier (2017). Second-order logic of paradox. Notre Dame Journal of
Formal Logic. 2018 forthcoming.
Hyde, D. (1997). From heaps and gaps to heaps of gluts. Mind 106, 641–660.
Hyde, D. and M. Colyvan (2008). Paraconsistent vagueness: Why not? Australasian Journal of
Logic 6, 107–121.
Kleene, S. (1952). Introduction to Metamathematics. Amsterdam: North-Holland.

17

Nelson, D. (1959). Negation and separation of concepts in constructive systems. In A. Heyting
(Ed.), Constructively in Mathematics: Proceedings of the Colloquium Held at Amsterdam, 1957,
pp. 208–225. Amsterdam: North Holland.
Pelletier, F. J. (1984). Six problems in translational equivalence. Logique et Analyse 108, 423–434.
Pelletier, F. J. and A. Urquhart (2003). Synonymous logics. Journal of Philosophical Logic 32,
259–285. See also the authors’ “Synonymous Logics: A Correction”, JPL 37: 95–100, 2008.
Priest, G. (1979). The logic of paradox. Journal of Philosophical Logic 8, 219–241.
Priest, G. (2006). In Contradiction: A Study of the Transconsistent, 2nd Ed. Oxford: Oxford
University Press.
Priest, G. (2018). Natural deduction systems for logics in the FDE family. In H. Wansing and
H. Omori (Eds.), FDE Some 40 Years Later(?). Dordrecht: Springer. Forthcoming.
Ripley, D. (2011). Contradiction at the borders. In Vagueness in Communication, pp. 169–188.
Dordrecht: Springer.
Rosser, J. B. and A. Turquette (1952). Many-Valued Logics. Amsterdam: North Holland.
Shramko, Y. and H. Wansing (2017). Truth values. In E. N. Zalta (Ed.), The Stanford Encyclopedia
of Philosophy (Summer 2017 ed.). Metaphysics Research Lab, Stanford University.
Tedder, A. (2014). Paraconsistent logic for dialethic arithmetics. Master’s thesis, University of Alberta, Philosophy Department, Edmonton, Alberta, Canada. Available at
https://www.library.ualberta.ca/catalog/6796277.
Tedder, A. (2015). Axioms for finite collapse models of arithmetic. Review of Symbolic Logic 8,
529–539.
van Fraassen, B. (1969). Presuppositions, supervaluations and free logic. In K. Lambert (Ed.), The
Logical Way of Doing Things, pp. 67–92. New Haven: Yale UP.

18

Appendix I: Deductive Systems
Tedder (2014) contains a Hilbert-style axiomatic system, and (more interestingly) a (multiple
succedent) sequent calculus for LP+cmi. (Tedder (2015) presents only the Hilbert system.) The sequent calculus closely follows (Gentzen, 1934)’s system LP for classical logic, with the following
changes:
(i) Gentzen’s rules for negation (“change the side and change the sign”) are dropped,
(ii) double negation rules are added, allowing a sequent to be followed by one like it except that
one of its formulas–on either side–is doubly negated,
(iii) negative rules for conjunction and disjunction (and, analogously, for quantifiers) are added,
allowing the insertion of a negated conjunction or disjunction under the same conditions as
allow the insertion of its De Morgan equivalent disjunction or conjunction,
(iv) negative conditional rules are added, allowing ¬(ϕ → ψ) to be inserted under the same conditions as (ϕ ∧ ¬ψ), and
(v) Gentzen’s identity axioms, ϕ ⊢ ϕ, are supplemented with “Gap excluding” axioms of the form
⊢ ϕ, ¬ϕ.
Cut elimination is proven by a straightforward adaptation of Gentzen’s method.
Dropping the Gap exclusion axioms from this system yields a sequent calculus for FDE+cmi.
Replacing them with “Glut excluding axioms” of the form ϕ, ¬ϕ ⊢ gives one for K3+cmi, and
replacing them instead with Mingle axioms of the form ϕ, ¬ϕ ⊢ ψ, ¬ψ gives one for M+cmi.
A natural deduction system, either in the style of Gentzen’s NK or in the Fitch-style presentation of many American textbooks, for any of these logics will include
(i) the standard Introduction and Elimination rules for ∧, ∨, → (and for the quantifiers in a First
Order system),
(ii) Double Negation Introduction and Elimination rues, by which a formula and its double negation may each be inferred from the other,
(iii) Negative Introduction and Elimination rules for ∧ and ∨ (and, analogously for the quantifiers), as in (Fitch, 1952) enforcing the interdeducibility of negated conjunctions and disjunctions with their De Morgan equivalent disjunctions and conjunctions,
(iv) Negative Introduction and Elimination rules for →, enforcing the interdeducibility of ¬(ϕ →
ψ) with (ϕ ∧ ¬ψ).
As is well-known, the standard Introduction and Elimination rules for → give only the Intuitionistic
logic of the conditional, so these have to be supplemented with some classicizing postulate to give
the full classical logic of the positive connectives. Addition of Peirce’s Law, (((ϕ → ψ) → ϕ) →
19

ϕ) as an axiom scheme is one conventional way of doing this, but an alternative axiom scheme,
(ϕ ∨ (ϕ → ψ)) seems a good deal easier to work with, and can be converted into a moderately
elegant natural deduction rule:
(v) A formula, χ, may be asserted if it is derivable both from the hypothesis ϕ and from the
hypothesis (ϕ → ψ).
These rules suffice for the propositional logic FDE+cmi. (A First Order system would have to
supplement the standard and negative Introduction and Elimination Rules for the quantifiers with
something to guarantee the “constant domain” inference
∀x(ϕ ∨ Ψ(x)) ⊢ (ϕ ∨ ∀x(Ψ(x))
(see Fitch 1952, §21.31.) Systems for the other logics are obtained by adding rules to this basic
system:
1) Ex falso quodlibet (“explosion”), for K3+cmi;
2) Excluded middle: χ may be asserted if it is derivable both from the hypothesis ϕ and from the
hypothesis ¬ϕ, for LP+cmi;
3) Mingle: (ψ ∨ ¬ψ) may be inferred from (ϕ ∧ ¬ϕ), for M+cmi.
More visually: Natural deduction rules for FDE+cmi will be double negation and both the
positive and negative IntElim rules for ∧ and ∨. Additionally, there is a series of rules for our →
operator.
Double Negation:
1

A

2

¬¬A

¬¬ Int

1

¬¬A

2

A

¬¬ Elim

Standard rules for lattice connectives:
1

A∧B

2

A

∧ Elim

1

A∧B

2

B

20

1

A

2

B

3

A∧B

∧ Elim
∧ Int

1

A∨B

2

A

3

...

4

C

1

A

5

B

2

A∨B

6

...

7

C

8

∨ Int

1

B

2

A∨B

∨ Int

∨ Elim

C

Negative rules for the lattice connectives9 :
1

¬(A ∨ B)

2

¬A

1

¬A

2

¬B

3

¬(A ∨ B)

1

¬A

2

¬(A ∧ B)

1

¬(A ∧ B)

2

¬A

3

...

4

C

5

¬B

6

...

7

C

8
9

C

¬∨ Elim

1

¬(A ∨ B)

2

¬B

¬∨ Elim

¬∨ Int

¬∧ Int

1

¬B

2

¬(A ∧ B)

¬∧ Int

¬∧ Elim

In the context of the positive rules, these negative rules are equivalent to Fitch’s (1952) original negation IntElim

rules.

21

Rules for Conditional10
1

(A → B)

2

A

3

B

1

A

2

...

3

B

4

A→B

→ Elim

1

¬(A → B)

2

A

¬ → Elim

1

¬(A → B)

2

¬B

→ Int

¬ → Elim

1

A

2

...

3

B

1

A

4

A→C

2

¬B

5

...

3

¬(A → B)

6

B

7

B

¬ → Int

Dilemma

10
The Dilemma rule, if added to, say, Intuitionistic Logic, would yield a formulation of full classical logic. It does
not collapse FDE+cmi into classical logic because the usual ¬-Introduction rule (reductio) of Intuitionistic Logic is
absent.

22

Appendix II: Soundness and Completeness
The natural deduction system is provably sound and complete, where soundness is taken to mean
that if all the premisses of a derivation have designated values on an assignment, the conclusion
will as well.
Soundness can be verified in the usual way, arguing by induction on the size of the derivation
after establishing that each rule is sound. For rules in which a conclusion is inferred directly from
one or two premisses, this is immediate, by inspection of the truth tables. A rule in which a hypothesis is discharged (that is, in the terminology of Fitch-style natural deduction, a rule involving
one or two subordinate proofs) is considered sound just in case, if all the undischarged hypotheses
above the conclusion of the rule (in Fitch-style: the formulas reiterated into subordinate proofs)
have designated values, the conclusion also has a designated value. It is easy to see that the subproof rules of the system will be sound provided that the reasoning within the subordinate proofs
is sound. The full soundness proof, then, will take the form of a double induction, on the length,
and on the depth of nesting of subordinate proofs within, a proof. The overall strategy is perfectly
standard for soundness proofs of natural deduction systems.
Completeness can be proven by a variant of Henkin’s method, similar to that used in Priest
(2018). We desire to show that, if a formula A is not derivable from a set of premisses Γ, then there
is an assignment on which A takes an undesignated value but every member of Γ is designated.
In a Henkin-style proof this is done in two stages. In the first, it is shown that Γ can be extended
to an eligible set Γ∗ which still does not (syntactically) imply A, where a set of formulas is said
to be eligible if it has some of the formal characteristics of the set of formulas taking designated
values on some assignment. In the second it is shown that the eligible set is actually elected: an
assignment is defined on which all and only the members of the set take designated values.
In applying Henkin’s method to a classical system, eligible sets are simply complete theories,
a.k.a. maximal consistent sets of formulas. In logics tolerating contradictions, consistency is obviously not a requirement, and in logics tolerating truth value “gaps” maximality is also not to be
hoped for! An appropriate notion of eligibility for our purposes counts a set of formulas as eligible
if and only if (i) it is deductively closed (and so, in particular, contains a conjunction if and only if
it contains both conjuncts, and contains a disjunction if it contains either disjunct), and (ii) contains
at least one of the disjuncts of each disjunction it contains. Given A not derivable from Γ, it is readily seen that a set maximal with respect to the property of containing Γ but not implying A will be
eligible in this sense, and the existence of such a maximal set follows from standard set-theoretic
considerations (Teichmüller-Tukey lemma). (In general these maximal sets will not be the only
eligible supersets of Γ not implying A, and an alternative proof adding formulas to Γ only if they
are required by clause (ii) may yield a smaller eligible set.)
Given an eligible set Γ∗ , we define an assignment to propositional variables by setting
• v(p) = T iff p is a member but ¬p is not a member of Γ∗,
• v(p) = B iff p and ¬p both belong to Γ∗ ,

23

• v(p) = N iff neither p nor ¬p belongs to Γ∗ , and
• v(p) = F iff ¬p but not p is a member of Γ∗ .
(Note that a variable takes a designated value if and only if it belongs to Γ∗ .) It remains to verify
(by induction on formula complexity) that arbitrary formulas take values on this assignment under
the same conditions of their, and their negations’, membership in Γ∗ . None of the cases are hard;
those not immediately obvious usually become obvious when one remembers that formulas of the
form A ∨ (A → B) are provable in the system.
In a bit more detail:
Soundness:
The notion of validity we want is:
Definition 1. Validity: If all the assumptions11 have designated values, then every formula or
subordinate derivation of the derivation has a designated value.
One could easily check that all the rules are classically valid, and conclude that of course the
FDE+cmi system is sound. But perhaps some of the negative rules are worth checking.
∧
T
B
N
F

T
T
B
N
F

B
B
B
F
F

N
N
F
N
F

F
F
F
F
F

Table 6: ∧ truth-table

A quick check of the ¬∧-Int rules against this truth table makes it clear that these rules are sound.
The presence of B means that ¬∧-Elim takes a bit longer, but is clearly correct also.
In full formal detail, the soundness proof (as is usual for a soundness proof of Fitch-style natural
deduction systems) is a double induction on
1. Length: the number of non-assumption formula items in the derivation.
2. Depth: the depth of nesting of subproofs.
The induction step of the Depth induction goes:
Suppose A comes by a subproof-using rule. (Now, a number of cases.) By hypothesis
of induction on Length, anything reiterated into the subproof is ok (since A would
occur in a main subproof above this step). By hypothesis of induction on Depth [we
11

Where formulas reiterated into a subproof are counted among that subproof’s assumptions.

24

call this the “key step”], the subproof is sound. So, if the hypothesis of the subproof is
ok, so is its “active” last item. So – now verifying each case – A is ok.
This gives us the cases for subproof-involving rules in the indicative step of the Length
induction for derivations of depth ≤ n. So derivations at this depth are sound. In a
derivation of depth n + 1, every subproof is of depth ≤ n, so the “key step” is guaranteed.
Completeness Construction:
Define a set of formulas to be saturated if and only if
1. It is consistent in the sense of not being the set of all formulas, and
2. It is deductively closed, and so automatically contains
(a) A conjunction if and only if it contains both conjuncts, and
(b) A disjunction if it contains at least one disjunct
3. It contains at least one disjunct of each of its disjunctions
Note that for classical logic, in which by deductive closure (A ∨ ¬A) belongs to every saturated set, saturation amounts to maximal consistency: saturated sets are the generalization for
non-classical logics of the “maximal consistent sets” familiar from Henkin proofs for classic(-ally
based) logic(s).
What we have to prove is:
Lemma 1. For any set of formulas, Γ, and for any formula, A, not derivable from Γ, there is a
saturated superset of Γ, Γ∗ , not containing A. (Since this specification includes the requirement
that A < Γ∗ , the requirement of consistency, (1), doesn’t have to be made part of the definition of
saturated set.
Proof. (By a version of the standard Lindenbaum construction.)
For classical logic, where we want maximal consistent sets anyway, it is normal to consider all
the formulas of the language (in some order), tossing each one in if its addition doesn’t permit the
derivation of the bad thing. But this can tend to undesirably stuffed sets of formulas! For example,
the maximal consistent sets of intuitionistic propositional logic are classically maximal! So we
prefer a more cautious addition of formulas.
Definition 2. An ordinally indexed series of sets of formulas:
Let Γ0 = Γ
Assume some fixed well-ordering of the formulas of the language:
For odd successors, α,

25

• If Γα is saturated, stop
• if not, pick the first (in the assumed ordering) disjunction in Γα for which neither
disjunct is in Γα . By the ∨-Elim rule, if Γα does not imply A, at least one of these
disjuncts can be added to Γα without permitting the derivation of A. Let Γα+1 be
the result of adding the first such disjunct (or the only one, if only one can be
added) to Γα .
For even successors (and for 0), let Γα+1 be the deductive closure of Γα .
S
(Γα ).
For limit ordinals λ, let Γλ =
α<λ

By cardinality considerations (there are more ordinals than formulas, so eventually we will run
out of formulas to add), this sequence must reach a fixed point, ΓΩ . By the usual Henkin arguments,
ΓΩ is saturated and does not imply A.
Now, for atomic p, define
• p has the value T iff p does and ¬p does not belong to ΓΩ
• p has the value B iff both p and ¬p belong to ΓΩ
• p has the value N iff neither p nor ¬p belong to ΓΩ
• p has value F iff ¬p but not p belongs to ΓΩ
We now in a position to verify that for arbitrary formulas A, the same correlation holds between
value and status with respect to membership in ΓΩ


Completeness Verification:
Theorem 3. Given a saturated set S, if we define, for atomic p:
p T iff p ∈ S and ¬p < S
p B iff p ∈ S and ¬p ∈ S
p N iff p < S and ¬p < S
p F iff p < S and ¬p ∈ S
we will have the same coincidence of values and S-status for all formulas
Proof. By induction on formula structures. We omit proofs for the ¬, ∨, ∧ connectives, which are
obvious. So we consider →:
The way up Suppose equivalence holds for A and B, we show it holds for A → B.
There are 16 combinations of truth-like values for A, B. For each, by hypothesis of induction,
assume the right S-membership status.
• Cases: Left column. B is T, so is in S. So, A → B is in S. ¬B is not in S, so by simple
¬ →-Elim, ¬(A → B) can’t be either.
26

• Cases: Bottom two rows. A is either F or N, so by hypothesis of induction, A is not in S. By
Dilemma, A ∨ (A → B) is in S, so by saturation (A → B) ∈ S . In the other direction, simple
¬ →-Elim rule would get from ¬(A → B) to A, so ¬(A → B) can’t be in S.
• Cases: Top row: A has value T, so A ∈ S , ¬A < S
– subcase: B has value B, so both B ∈ S and ¬B ∈ S . Since B ∈ S , →-Int gives
(A → B) ∈ S . Since A ∈ S and ¬B ∈ S , the simple ¬ →-Int rule gives ¬(A → B) ∈ S .
– subcase: B has value N, so neither B ∈ S nor ¬B ∈ S . If (A → B) were in S, →-Elim
would put B in, so (A → B) < S . If ¬(A → B) were in S, simple ¬ →-Elim rule would
put both A and ¬B in S, so ¬(A → B) < S .
– subcase: B has value F, so ¬B ∈ S and B < S . If (A → B) were in S, →-Elim would
put B in, so (A → B) < S . On the other hand, since A and ¬B are both available, simple
¬ →-Int gives ¬(A → B) ∈ S .
• Cases: Second row: A has value B, so both A ∈ S and ¬A ∈ S
– subcase: B has value B, so by hypothesis of induction, B and ¬B are both in S. Since
B is available, →-Int gets (A → B) ∈ S . Since A and ¬B are both available, simple
¬ →-Int puts ¬(A → B) ∈ S .
– subcase: B has value N, so neither B nor ¬B is in S. Since A is available, if (A → B)
were in S, →-Elim would put B in S. If ¬(A → B) were in S, simple ¬ →-Elim would
put ¬B in S. So neither (A → B) nor ¬(A → B is in S.
– subcase: B has value F, so ¬B ∈ S and B < S . Since A and ¬B are available, ¬ →-Int
puts ¬(A → B) ∈ S . Since A is available, if A → B were in S, B would be also.

Normally, in a Henkin-style completeness proof, one defines truth for atoms as membership
in the saturated set, and the verification stage checks that complex formulas are true if and only if
they are members. This requires two arguments: one that if a formula is true it is a member, and
one that if a formula belongs to the set, then it is true.
Because the semantic clauses for T, B, N, F are more complex, these two parts are now intermingled. If a formula has a certain value, then both the membership and non-membership of the
formula and its negation (one for each) in the set have to be checked. Thus the way up (verifying
that formulas with certain values have the right membership statuses) already in effect includes the
way back down (verifying that formulas with certain membership statuses have the right values).

27

