Modelling non-classical logic Challenging the paradigm

Recall the small two-state model of intuitionistic logic:

This is the simplest structure providing a model of the logic, apart from the classical truth tables (which can be seen as the one-state model). A propopsition may be in one of three cases: it may hold in the small state and therefore in the large state as well; it may fail in the large state and therefore fail in the small state as well, or it may hold in one state (the large one) and fail in the other. These three cases exhaust the possibilities, though of course if there were more states in the structure there would be more cases to consider. We may think of the case into which a proposition falls as its "value" on the interpretation. Clearly, the value of a compound formula on this scheme is determined by the values of its parts, so we can represent the structure by means of 3-valued tables in the same way as we use 2-valued tables to represent classical models.

Let us use letters to represent the three values: T means "true", in the sense of holding in state 1 (and therefore in state 2 as well); F means "false" in the sense of failing even in state 2, like r in the picture; i can be read as "indeterminate" or perhaps "intermediate", and is for formulae which fail in state 1 but hold in state 2. Then the "truth tables" are easily calculated from the definition of what it is to hold in a state:

A 3-valued interpretation of propositional logic is simply an assignment of values to the atoms, as in the classical case except that the value i is allowed. A sequent is valid according to these tables iff every interpretation on which all of the premises are true (have value T) also makes the conclusion true. Testing for this property is mechanical, if a little tedious. We may observe, for instance, that the sequent

(p IMP q) IMP p   ⊢   p

is invalid, as assigning p the value i and q the value F gives p IMP q the value F. That gives the premise the value T but the conclusion p has value i, not T. Since intuitionistic logic is sound for these tables, that shows the sequent to be intuitionistically unprovable. Validity in the 3-valued tables does not show sequents to be provable in intuitionistic logic, however, for that logic is not complete for such a simple model. For example,

⊢   NOTp OR NOTNOTp

is valid according to the 3-valued tables, but it is not an intuitionistic theorem, as noted earlier. To refute it, we need a structure with three states, which would give rise to some 5-valued truth tables if we were to write it out.

At any rate, it is useful to have available some simple models of intuitionistic logic such as the three-valued one based on the idea of a two-stage definition of truth. At the very least, such a model can show certain sequents to be intuitionistically unprovable. The question then arises of whether we can do the same for other non-classical paradigms of reasoning such as the relevant one or the logic for vagueness treated in Chapter 10 of these notes. The answer is yes and it will be worthwhile examining one or two such models to see what light they cast on the "deviant" paradigms.

The general principle is this: to show that a given sequent is not provable in a system of logic, we must define some property which holds of all the trivial sequents given by the rule 'A' of assumptions and which is preserved by all the other rules of that logic, but which does not hold of the sequent in question. One such property in the case of classical propositional logic is validity according to truth tables. For the non-classical variants considered here, there is no such finite structure that completely defines the logic, but there are still useful approximations.

The smallest non-classical structure suitable for modelling the suggested fuzzy logic (for vagueness) is the three-valued one sometimes called L3 (after Jan Łukasiewicz who introduced it) with these tables for the connectives:

These matrices should be compared with the ones given before for the three-valued interpretation of intuitionistic logic. The tables for conjunction and disjunction are the same, but that for implication gives A IMP B the value i where A has value i and B has F, whereas the previous structure had F in that position. Since NOTA is still definable as A IMPBAD, that means there is an i in the middle of the negation table as well. The change is small, but it has a large effect. NOTNOTA is fully equivalent to A now, and NOT(A AND B) is equivalent to NOTA OR NOTB. On the other hand, while in intuitionistic logic A IMP (A IMP B) is the same as A IMP B, in fuzzy logic of course it is not. To see this, note that i IMP (i IMP F) evaluates to i IMP i which is T, but i IMP F is i.

To define validity of sequents in the new three-valued structure, we need to assign values not only to formulae but also to bunches built up with commas and semicolons. A compound bunch X,Y formed with the comma just has the lower value of the two (the value of X and the value of Y). That is, it gets T iff X and Y both get T; it gets F iff at least one of X and Y gets F; it gets i otherwise. For the semicolon, on the other hand, two "i"s make an "F", so the compound X;Y also gets F if X and Y both get i. That is, bunches are evaluated according to the tables:

A sequent X ⊢ A is valid iff every assignment of values which gives T to X also gives T to A, and every assignment which gives F to A also gives F to X. With this definition, it is merely laborious to show that all the rules of the calculus presented in the previous sheet of notes come out valid. It is also easy to see that the following intuitionistically valid sequents do not:

(p IMP q) AND p   ⊢   q
p IMP NOTp   ⊢   NOTp
⊢   NOT(p AND NOTp)
(p IMP q) AND (q IMP r)   ⊢   p IMP r
p IMP (q IMP r)   ⊢   (p AND q) IMP r

The reading of the three values is quite different in the fuzzy case from that used to model intuitionistic logic. We may think of the intermediate value i as "half-true", which is of course the same thing as "half-false". The conditional is true if the consequent is as good as the antecedent (or better), false if the antecedent is completely true and the consequent completely false, and half-true if the consequent is a half-step down from the antecedent. By "as good as" here, I mean on the scale: half-true is better than false and true is better than half-true.

Yet another reading gives a three-valued model of relevant logic. This time, between truth and falsehood we have a "confused" value. This is also a kind of truth, but the negation of a formula with the "confused" value is also confused. Perhaps we should think of the confused value as "both true and false". Conjunction, disjunction and negation have the same tables as in the fuzzy case, but the conditional is quite different. A IMP B is (at least) true if and only if the value of B is at least as "good" as that of A. That is, iff (i) if A is (at least) true then so is B, and (ii) if B is (at least) false then so is A. A IMP B is false iff A is true and B is false. This gives the following three-valued tables:

For defining the value of a bunch, the semicolon is also interpreted a little differently:

As before, a sequent X ⊢ A is valid iff on every interpretation the value of A is at least as good as that of X. Thus a valid sequent preserves truth from left to right and preserves falsehood from right to left. One more detail: the "null" bunch TEE, symbolised by the number zero in the deduction system, has the value i now, whereas in the above logic for vagueness it was evaluated as T.

We call this structure S3: S for Takeo Sugihara and 3 of course for its three values.

All of the sequents noted above as invalid in fuzzy logic are relevantly provable, but the following are not:

p   ⊢   q IMP p
(p OR q) AND NOTp   ⊢   q
NOT(p IMP q)   ⊢   p AND NOTq
p AND q   ⊢   p ↔ q
(p AND q) IMP r   ⊢   pIMP (q IMP r)

Consider the last of these sequents, for example. In intuitionistic logic, as in classical logic, the two formulae (p AND q) IMP r and p IMP (q IMP r) are equivalent: they are both ways of saying that r is implied by p and q taken together. Relevantly, however, we distinguish between the different senses of "taken together". In S3, we may assign the value T to p and i to both q and r. Then we get:

The premise of the sequent evaluates to i (under its main connective) while the conclusion evaluates to F, so the sequent is not valid in S3 and hence is not relevantly provable.

The converse sequent, on the other hand is relevantly fine. Here is a proof:

In fuzzy logic, of course, the contraction move is not allowed, and in fact the sequent is unprovable as may be observed by evaluating it in L3:

It is worth stressing once again that the 3-valued structures do not constitute an adequate account of the semantics of any of the logics considered here. None of these logical systems can be captured completely by any finite structure, so it is important to avoid the impression that these are 3-valued logics. The small structures incorporating non-classical features are useful, however, for gaining a "feel" for differently-inspired paradigms of reasoning as well as for refuting some of the unprovable sequents.