19 Jan 2018

Priest (8.4) Introduction to Non-Classical Logic, ‘FDE [First Degree Entailment] and Many-valued Logics’, summary

 

by Corry Shores

 

[Search Blog Here. Index-tags are found on the bottom of the left column.]

 

[Central Entry Directory]

[Logic and Semantics, entry directory]

[Graham Priest, entry directory]

[Priest, Introduction to Non-Classical Logic, entry directory]

 

[The following is summary of Priest’s text, which is already written with maximum efficiency. Bracketed commentary and boldface are my own, unless otherwise noted. I do not have specialized training in this field, so please trust the original text over my summarization. I apologize for my typos and other distracting mistakes, because I have not finished proofreading.]

 

 

Summary of

 

Graham Priest

 

An Introduction to Non-Classical Logic: From If to Is

 

Part I

Propositional Logic

 

8

First Degree Entailment

 

8.4

FDE and Many-valued Logics

 

 

 

Brief summary:

First Degree Entailment’s evaluating relation allows for four value situations, namely, a formula being valued as 1, as 0, as having a relation to 1 and to 0, and as having no such value relations. We can thus alternatively think of First Degree Entailment as having four singular values each as their own: 1 (for just true), 0 (for just false), b (for both), and n (for neither). The value assignments are then structured so that they match the outcomes for the First Degree Entailment rules. The truth tables for the connectives in four-valued FDE semantics are thus:

 

f¬  
1 0
b b
n n
o 1

 

f 1 b n o
1 1 b n 0
b b b 0 0
n n 0 n 0
o 0 0 0 0

 

f 1 b n o
1 1 1 1 1
b 1 b 1 b
n 1 1 n n
o 1 b n 0

 

We can make a short-hand of these valuations with the following diamond lattice (Hasse diagram):

 

1

↗               ↖

b                                 n

↖                   ↗

0

 

[Here is a version that I modified for my own purposes of visual demonstration, so it is not Priest’s, and it is probably flawed:

 

1

↙↗       

         ↖↘

b           

|

             n

        ↘↖        

         ↗↙

0

 

Negation toggles 0 and 1, and it maps n to itself and b to itself:

Negation and

1

↙↗       

        ↖↘

b           

|

             n

        ↘↖        

         ↗↙

0

 

For conjunction, we take the greatest lower bound for both of the conjunct values, that is to say, when moving upward, we find the highest place we can start from in order to arrive at both of the two conjunct values (we can also start and arrive at the same place, if we begin at our destination).

Conjunction >

(greatest lower bound, reading upwards)

1

       

        

b           

|

             n

                

        

0

 

For disjunction, we look for the least upper bound: when moving downward, we seek the lowest place we can start from to arrive at both values.

Disjunction ↓ <

(least upper bound, reading downwards)

1

       

        

b           

|

             n

                

        

0

 

] The designated values in FDE are 1 and b, so an inference in FDE is valid only if there is no interpretation that assigns all the premises 1 or b and the conclusion 0 or n. We can place constraints on FDE in order to obtain other logics, like the three-valued logics K3 and LP and also Classical Logic. One such constraint is exclusion, which prevents there from being a formula that is both 1 and 0:

Exclusion: for no p, 1 and 0

FDE under the constraint of exclusion is K3. Now, to make K3 sound and complete, we use modified FDE tableaux rules, namely, we can (additionally) also close a branch when it contains A,+ and ¬A,+. Another constraint is exhaustion, which prevents there from being any formulas with no values:

Exhaustion: for all p, either 1 or 0

FDE under the exhaustion constraint is LP. To make LP sound and complete, we modify the FDE tableaux rules such that {1}  a branch also closes if it has formulas of the form A,− and ¬A, −, and {2} we obtain counter-models from open branches by using the following rule: “if p,− is not on the branch (and so, in particular, if p,+ is), set 1; and if ¬p,− is not on the branch (and so, in particular, if ¬p,+ is), set 0” (149). And then, FDE under both the exhaustion and exclusion constraints is Classical Logic. Note that FDE is a  proper sub-logic of K3 and LP, because every interpretation of K3 or LP is an interpretation in FDE .

 

 

 

 

 

Contents

 

8.4.1

[FDE as a 4-Valued Logic]

 

8.4.2

[FDE 4-Valued Truth-Value Assignments for Connectives]

 

8.4.3

[A Diamond Lattice ( Hasse Diagram) for Connectives]

 

8.4.4

[Designated Values in FDE: 1, b]

 

8.4.5

[FDE as Different from K3, Ł3, LP, and RM3]

 

8.4.6

[The Exclusion Constraint]

 

8.4.7

[Exclusion-Constrained FDE as K3]

 

8.4.8

[K3 Tableaux as FDE with an Addition]

 

8.4.9

[The Exhaustion Constraint]

 

8.4.10

[Exclusion-Constrained FDE as LP]

 

8.4.11

[LP Tableaux as FDE with Two Additions]

 

8.4.12

[Exhaustion and Exclusion-Constrained FDE as Classical Logic]

 

8.4.13

[FDE as a Proper Sub-logic of K3 and LP]

 

 

 

 

 

Summary

 

8.4.1

[FDE as a 4-Valued Logic]

 

[We can also think of First Degree Entailment as having four values all their own: 1, 0, b (both), and n (neither); (rather than the both situation involving two separate evaluations and the neither involving a lack of value relations. Here instead there are four singular value assignments.)]

 

Recall from section 8.2.5 our semantics for First Degree Entailment (FDE). We use relation ρ to assign to formulas either 1, 0, both 1 and 0, or neither of the two:

 

Situation 1:

1

 

Situation 2:

0

 

Situation 3:

1

0

 

Situation 4:

[no such relations given. We might have formula p, but relation ρ does not relate it to any values.]

 

Given that the rules for connectives also assign any of these for values, we can think of First Degree Entailment as a 4-valued logic. For the other two values, we write b for both values and n for neither values.

Given any formula, A, and any interpretation, ρ, there are four possibilities: A is true and not also false, A is false and not also true, A is true and false, A is neither true nor false. If we write these possibilities as 1, 0, b and n, respectively, this makes it possible to think of FDE as a 4-valued logic.

(146)

[contents]

 

 

8.4.2

[FDE 4-Valued Truth-Value Assignments for Connectives]

 

[We structure the value assignments on the basis of the rules for First Degree Entailment]

 

[Recall from section 8.2.6 the rules for determining values for formulas built up using connectives, in First Degree Entailment:

A1 iff 1 and 1

A0 iff 0 or 0

 

A1 iff 1 or 1

A0 iff 0 and 0

 

¬1 iff 0

¬0 iff 1

(143)

We can use these to make truth tables for the truth functions for connectives (so while atomic formula are assigned values using a relation rather than a truth function, the complex formula do use a truth-valuating function, it seems.)] The truth tables for the four-valued FDE semantics are:

f¬  
1 0
b b
n n
o 1

 

f 1 b n o
1 1 b n 0
b b b 0 0
n n 0 n 0
o 0 0 0 0

 

f 1 b n o
1 1 1 1 1
b 1 b 1 b
n 1 1 n n
o 1 b n 0

 

Priest then goes through some evaluations that show how we use our classical intuitions about how truth and falsity operate for the connectives, only now with the additional possibilities of both and neither values (I will skip further elaboration, as we did something similar and fairly thorough in section 8.4.3. There we evaluate for negation, conjunction, and disjunction using four values, only with the value relation where there might be separate relations for each of the two values for the same formula or no such value relations.]

The truth conditions of 8.2.6 give the following truth tables:

[see above for the tables.] |

The details are laborious, but easy enough to check. Thus, suppose that A is n and B is b. Then it is not the case that A and B are both true; hence, A B is not true. But B is false; hence, A B is false. Thus, A B is false but not true, 0. Since B is true, AB is true; and since A and B are not both false, AB is not false. Hence, AB is true and not false, 1. The other cases are left as an exercise.

(146-147)

[contents]

 

 

 

 

8.4.3

[A Diamond Lattice ( Hasse Diagram) for Connectives]

 

[We can use a diamond lattice as a shorthand of the truth tables for evaluating the 4-valued semantics.]

 

Priest then shows a way to understand these values using a diamond lattice [in other contexts I have seen it called a Hasse diagram.]

Priest:

1

↗               ↖

b                                 n

↖                   ↗

0

(After p.147)

[I am not so good with these structures, but as I understand, they are designed so that with certain guidelines you can know how to make the evaluations for the connectives. I found their description in Barry Richards’ “Logical Reasoning, Development and Learning” to be useful. It is drawn in the following way, to also represent certain evaluations using the circular arrow and up/down arrow. Also notice the lack of arrow heads on the diagonal arrows.

 

Richards:

t

╱      

       ╲

⟳∅           

|

           (t, f)⟲

╲      

       ╱

f

(After Richards 1987, p.90)

 

Let me combine them for convenience. [I am not sure what the upward direction of the diagonal arrowheads mean in Priest’s version. We will need to read the diagram in some cases starting from the top and going down and in others starting at the bottom and going up. My best guess at their meaning is that maybe as a mathematical sort of structure, there is no indication of top and bottom. What I mean is, without those arrows, there are no other symbols provided that would make such an orientational indication. Regardless of the reason, I will do the following with regard to the diagonals. I will have them pointing both ways to express both directions generally, and I will let the spatial properties of the diagram be indicative of its top and bottom. The reason I am doing this, as you will see, is so that I can have a master diagram, which, by our attending to certain symbols and not to others, serves in all cases uniquely.]

 

My Priest/Richards Modified Hybrid:

1

↙↗       

         ↖↘

b           

|

             n

        ↘↖        

         ↗↙

0

 

Priest says that negation toggles 0 and 1, and it maps n to itself and b to itself. So suppose we want to evaluate a negation. Our concern will be with these arrows in red.

 

Negation and

1

↙↗       

        ↖↘

b           

|

             n

        ↘↖        

         ↗↙

0

 

For conjunction, the value will be the highest place from which one can begin at in order to arrive at both of the two conjunct values by moving upward. This is also called the greatest lower bound.

 

Conjunction >

(greatest lower bound, reading upwards)

1

       

        

b           

|

             n

                

        

0

 

So suppose we have 0 and 0. To arrive at both 0 and 0, moving upward, we cannot start any higher than 0. Suppose we have 0 and 1. To get to both of them, our highest starting place would be 0. If we have b and 0, or if we have n and 0, our highest starting place would be 0. If we have b and 1, then our highest starting place going up is b, and if we have n and 1, our highest starting place is n. If we have b and b, we cannot start higher than b, and for n and n, it is likewise n. If we have b and n, our highest point of departure to get to them is 0. And finally, if we have 1 and 1, our greatest lower bound is 1 (it would not be b or n, because we can get to one if we are already there in both cases. But for the conjunction of b and n, we cannot start from either to get to the other, as we do not move laterally, so we need to start lower than both). For disjunction, we look for the least upper bound, which is the lowest place one can start at to arrive at both values, moving downward.

 

Disjunction ↓ <

(least upper bound, reading downwards)

1

       

        

b           

|

             n

                

        

0

 

Suppose we have 0 and 0. To get to 0, we cannot start any lower than 0, moving downward. Suppose we have 0 and 1. We cannot start any lower than 1 to get to them. Suppose we have b and 0, our lowest starting place is b, and if we have n and 0, our lowest starting place is n. If we have b and 1 or n and 1, our lowest starting place is 1. If b and b, the lowest starting place to get to both of them is b, and for n and n, it is n. If we have b and n, our lowest starting place to get to both of them is 1. And to get to 1 and 1, we can start no lower than 1.]

An easy way to remember these values is with the following diagram, the ‘diamond lattice’:

1

↗               ↖

b                                 n

↖                   ↗

0

 
The conjunction of any two elements, x and y, is their greatest lower bound, that is, the greatest thing from which one can get to both x and y going up the arrows. Thus, for example, b n = 0 and b 1 = b. The disjunction of two elements, x and y, is the least upper bound, that is, the least thing from which one can get to both x and y going down the arrows. Thus, for example, b n = 1, b ∨ 1 = 1. Negation toggles 0 and 1, and maps each of n and b to itself.2

(147)

2. In fact, this structure is more than a mnemonic. The lattice is one of the most fundamental of a group of structures called ‘De Morgan lattices’, which can be used to give a different semantics for FDE.

(147)

 

 

 

8.4.4

[Designated Values in FDE: 1, b]

 

[The designated values in FDE are 1 and b.]

 

Recall from section 7.2.2 the notion of designated values: they are the values that are preserved in valid inferences. For example, in classical bivalent logic, “an inference is semantically valid just if there is no interpretation that assigns all the premises [the value 1], but assigns the conclusion [the value 0]” (121, bracketing substitutions are mine; see section 7.2.3). In three-valued K3 we likewise have just the 1 as the designated value, so the same rule holds. But in LP, an inference is valid only if there is no interpretation that assigns all premises the value 1 or i but assigns the conclusion 0.] The designated values for FDE are 1 and b. (So an inference in FDE is valid only if there is no interpretation that assigns all the premises 1 or b and the conclusion 0 or n.]

8.4.4 Since validity in FDE is defined in terms of truth preservation, the set of designated values is {1, b} (true only, and both true and false).

(147)

[contents]

 

 

 

 

8.4.5

[FDE as Different from K3, Ł3, LP, and RM3]

 

[FDE is related to the other 3-valued logics we examined before, but it is not the same.]

 

In chapter 7, we examined a few 3-valued logics [including  K3, Ł3, LP, and RM3]. FDE is not one of them, but as we will see, it is related.

8.4.5 This is not one of the many-valued logics that we met in the last chapter, but two of the ones that we did meet there are closely related to FDE.

(147)

[contents]

 

 

 

8.4.6

[The Exclusion Constraint]

 

[We can place constraints on FDE. One constraint is exclusion, which prevents there from being a formula that is both 1 and 0.]

 

[Now Priest will examine some constraints on FDE which will generate K3, as in this sub-section, and later, LP. Recall from section 7.3.2 that in K3, the third value is understood to mean neither true nor false. Priest will now mention a constraint on FDE that would alter the valuations such that we get K3. That constraint, called exclusion, prevents there from being a formula that is both 1 and 0.]

Suppose that we consider an FDE interpretation that satisfies the constraint:

Exclusion: for no p, 1 and 0

| i.e., no propositional parameter is both true and false. Then it is not difficult to check that the same holds for every sentence, A.3 That is, nothing takes the value b.

(147-148)

3 Proof: The proof is by an induction over the complexity of sentences. Suppose that it is true for A and B; we show that it is true for ¬A, AB and AB. Suppose that ¬1 and ¬0; then 0 and 1, contrary to supposition. Suppose that A1 and A0; then 1 and 1, and either 0 or 0; hence, either 1 and 0, or the same for B. Both cases are false, by assumption. The argument for AB is similar.

(148)

[contents]

 

 

 

8.4.7

[Exclusion-Constrained FDE as K3]

 

[FDE under the constraint of exclusion is K3.]

 

The logic we obtain by placing the exclusion constraint on FDE (see section 8.4.6) is K3. [Now compare for example the conjunction table for K3 and for exclusion-constrained FDE.

K3

f 1 i 0
1 1 i 0
i i i 0
0 0 0 0

 

 

FDE

f 1 b n o
1 1 b n 0
b b b 0 0
n n 0 n 0
o 0 0 0 0

But now put out of mind the rows for b.

f 1 i 0
1 1 i 0
i i i 0
0 0 0 0

f 1 b n o
1 1 b n 0
b b b 0 0
n n 0 n 0
o 0 0 0 0

As you can see, they are identical after that constraint, when you take i to be n.]

The logic defined in terms of truth preservation over all interpretations satisfying this constraint is, in fact, K3. For if we take the above matrices, and ignore the rows and columns for b, we get exactly the matrices for K3(identifying n with i). (In K3, A ⊃ B can be defined as ¬AB, as we observed in 7.3.8.)

(148)

[contents]

 

 

 

8.4.8

[K3 Tableaux as FDE with an Addition]

 

[To make K3 sound and complete, we use modified FDE tableaux rules, namely, we also close a branch when it contains A,+ and ¬A,+.]

 

[Recall from section 8.3.1 the tableaux rules. Priest says in section 8.3.5 that

a branch of a tableau closes if it contains nodes of the form A,+ and A,−.

(145)

Now recall from section 1.1.7 the notions of soundness and completeness:

If every proof-theoretically valid inference is semantically valid (so that ⊢ entails ⊨) the proof-theory is said to be sound. If every semantically valid inference is proof-theoretically valid (so that ⊨ entails ⊢) the proof-theory is said to be complete.

(3)

(In other words, it seems, if in a logical system both its semantics and its proof procedures make the same sentences valid or invalid, then the system is sound and complete.) To make K3 sound and complete, we use a modified version of the tableaux of the prior section, except now we add an additional closure rule, namely, a branch is closed when it contains A,+ and ¬A,+. And also recall from section 8.3.6 how we obtain counter-models, namely for open branches, to any p,+, we assign 1; and to any ¬p,+ we assign 0. We do the same here too.]

K3 is sound and complete with respect to the tableaux of the previous section, augmented by one extra closure rule: a branch closes if it contains nodes of the form A,+ and ¬A,+. (This is proved in 8.7.8.) Here, for example, is a tableau showing that p ∧ ¬ p K3 q. (The tableau is open in FDE.)

p∧¬p,+
q,−
p,+
¬p,+
×

 
Counter-models are read off from open branches of tableaux in exactly the same way as in FDE.

(148)

[contents]

 

 

 

8.4.9

[The Exhaustion Constraint]

 

[On the other hand, we can apply the exhaustion constraint to FDE, meaning that we prevent it from having formulas with no values.]

 

We now consider a different constraint, exhaustion, which prevents there from being formulas valued as neither 1 nor 0. This limits our possible values to 1, 0, and b.

Suppose, on the other hand, that we consider an FDE interpretation that satisfies the constraint:

Exhaustion: for all p, either 1 or 0

i.e., every propositional parameter is either true or false – and maybe both. Then it is not difficult to check that, again, the same holds for every sentence, A.4 That is, nothing takes the value n.

(148)

4 Proof: The proof is by an induction over the complexity of sentences. Suppose that it is true for A and B; we show that it is true for ¬A, AB and AB. Suppose that either 1 or 0; then either ¬0 or ¬1. Since 1 or 0, and 1 or 0, then either 1 and 1, and so A1; or 0 or 0, and so A0. The argument for AB is similar.

(148)

[contents]

 

 

 

8.4.10

[Exclusion-Constrained FDE as LP]

 

[FDE under the exhaustion constraint is LP.]

 

[FDE modified by the exhaustion constraint is LP. To see that, compare for example conjunction, except we put aside the n column and we think of i as b.

LP

f 1 i 0
1 1 i 0
i i i 0
0 0 0 0

FDE

f 1 b n o
1 1 b n 0
b b b 0 0
n n 0 n 0
o 0 0 0 0

]

The logic defined by truth preservation over all interpretations satisfying this constraint is, in fact, LP. For if we take the matrices of 8.4.2 and ignore the rows and columns for n, we get exactly the matrices for LP (identifying b with i). (Again, in LP, A B can be defined as ¬A B, as we observed in 7.4.6.)

(149)

[contents]

 

 

8.4.11

[LP Tableaux as FDE with Two Additions]

 

[To make LP sound and complete, we modify the FDE tableaux rules such that {1}  a branch also closes if it has formulas of the form A,− and ¬A, −, and {2} we obtain counter-models from open branches using this rule: “if p,− is not on the branch (and so, in particular, if p,+ is), set 1; and if ¬p,− is not on the branch (and so, in particular, if ¬p,+ is), set 0.”]

 

[To make LP sound and complete, we will similarly modify the FDE tableaux rules. There are two main differences, one regarding branch closure and another about counter-models, namely, {1}  a branch also closes if it has formulas of the form A,− and ¬A, −, and {2} we obtain counter-models from open branches using this rule: “if p,− is not on the branch (and so, in particular, if p,+ is), set 1; and if ¬p,− is not on the branch (and so, in particular, if ¬p,+ is), set 0.”]

LP is sound and complete with respect to the tableaux of the previous section, augmented by one extra closure rule: a branch closes if it contains nodes of the form A,−and ¬A,−. (This is proved in 8.7.9.) Here, for example, is a tableau showing that pLP q∨¬q. (The tableau is open in FDE.)

p,+

q∨¬q,−

q,−

¬q,−

×

Counter-models are read off from open branches of tableaux by employing the following rule: if p,− is not on the branch (and so, in particular, if p,+ is), set 1; and if ¬p,− is not on the branch (and so, in particular, if ¬p,+ is), set 0.

(149)

[contents]

 

 

8.4.12

[Exhaustion and Exclusion-Constrained FDE as Classical Logic]

 

[FDE under both the exhaustion and exclusion constraints is Classical Logic.]

 

[Now suppose we constrain FDE with both exclusion and exhaustion. That would mean that no formulas could be neither valued, and also none could be both valued. That just leaves as possibilities 1 and 0, and thus the values of classical logic. Furthermore, Priest explains, that if we add the tableaux closure rules from both K3 and LP, then we obtain a set of rules that would work for classical logic.]

Finally, and of course, if an interpretation satisfies both Exclusion and Exhaustion, then for every p, 0 or 1, but not both, and the same follows for arbitrary A. In this case, we have what is, in effect, an interpretation for classical logic. Adding the closure rules for K3 and LP to those of FDE, therefore gives us a new tableau procedure for classical logic.

(149)

[contents]

 

 

 

8.4.13

[FDE as a Proper Sub-logic of K3 and LP]

 

[FDE is a  proper sub-logic of K3 and LP, because every interpretation of K3 or LP are interpretations in FDE .]

 

[(First we need the notion of sub-logic. On p.140 in an exercise, he writes: “Show that every normal many-valued logic is a sub-logic of classical logic (i.e., that every inference valid in the logic is valid in classical logic)”). In section 8.4.8 and section 8.4.11,  Priest gave examples of formulas that are valid in  K3 or LP, but not in FDE. Now, because every interpretation of K3 or LP are interpretations in FDE (but not all interpretations of FDE are interpretations of K3 or LP), this makes FDE be a proper sub-logic of each of them. (Here I get a bit confused. Recall that an interpretation is defined in section 1.3.1 in the following way:

An interpretation of the language is a function, v, which assigns to each propositional parameter either 1 (true), or 0 (false). Thus, we write things such as v(p) = 1 and v(q) = 0.

(5)

I do not understand how we would compare the number of interpretations, under this definition. Is there not just one v in each case? Maybe this determination also works for valid inferences, as we look to the example proofs for evidence (these proofs suggest that all valid inferences of K3 and LP are valid in FDE, but maybe not the other way around.) The other confusing thing for me is that here the logic whose set of parts is a subset of the other is not the sub-logic of the other, but rather it is the other way around (all interpretations of LP are also interpretations in FDE, but FDE is the sub-logic here). Right now I misunderstand the situation, but the text itself is straight-forward. I wonder if the idea would be rather about the constraints. So the logic here with the larger set of valid formulas or interpretations is the sub-logic of another perhaps because it has fewer constraints than them. So maybe to be a sub-logic is something like being a parent logic, and those above it are more restricted versions. And in the exercise quotation above, we think of multi-valued logics as the sub-logics, maybe because classical logic is more restricted. Another possibility is simply that we are going by the number of truth values, with more values making one logic “lower”. So FDE is a sub-logic of  K3 and LP, because FDE has {1,0,b,n} while K3 and LP have {1,0,n} and {1,0,b} respectively. And K3 and LP are sub-logics of classical logic, because classical only has {1,0}. But I am guessing quite poorly here, so please see the quotation instead:)]

Since all K3 interpretations are FDE interpretations, and all LP interpretations are FDE interpretations, FDE is a sub-logic of K3 and LP. It is a proper sub-logic of each, as the tableaux of 8.4.8 and 8.4.11 show.

(149)

[contents]

 

 

 

 

From:

 

Priest, Graham. 2008 [2001]. An Introduction to Non-Classical Logic: From If to Is, 2nd edn. Cambridge: Cambridge University.

 

 

Or if otherwise cited:

Richards, Barry. 1987. “Logical Reasoning, Development and Learning.” In Piaget Today, pp.87-99. Edited by Bärbel Inhelder, Denys de Caprona, and Angela Cornu-Wells. Hove and London / Hillsdale, N.J.: Lawrence Erlbaum.

 

 

.

No comments:

Post a Comment