by Corry Shores
[Search Blog Here. Index-tags are found on the bottom of the left column.]
[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
7. Many-valued Logics
7.2. Many-valued Logic: The General Structure
Brief summary:
In providing the general structure for many-valued logics, we first simplify our system by defining material equivalence in the following way:
A ≡ B is defined as (A ⊃ B) ∧ (B ⊃ A)
We will articulate the structure of many-valued logics by naming all the components, including the parts relevant for truth and validity evaluations. In its most condensed form, the structure of many-valued logics is:
⟨V, D, {fc; c ∈ C}⟩
V is the set of assignable truth values. D is the set of designated values, which are those that are preserved in valid inferences (like 1 for classical bivalent logic). C is the set of connectives. c is some particular connective. And fc is the truth function corresponding to some connective, and it operates on the truth values of the formula in question. In a classical bivalent logic,
V = {1, 0}
D = {1}
C = {¬, ∧, ∨, ⊃, ≡} (but recall we have redefined ≡)
fc; c ∈ C = {f¬, f∧, f∨, f⊃}
We also have an interpretation function v that assigns values to the propositional parameters, and the connective truth functions operate recursively on the assigned propositional parameter values to compute the values of the complex formulas. The connective truth functions are defined in terms of the series of values for the places in the n-tuple corresponding to that connective:
if c is an n-place connective,
v(c(A1, ... , An)) = fc(v(A1), ... , v(An))
For example, we could consider a classical bivalent system where V = {1, 0}, and we could define the connective functions for negation and conjunction in the following way.
f¬ is a one-place function such that f¬(0) = 1 and f¬(1) = 0;
f∧ is a two-place function such that f∧(x, y) = 1 if x = y = 1, and f∧(x, y) = 0 otherwise [...]
| f¬ | |
| 1 | 0 |
| 0 | 1 |
| f∧ | 1 | 0 |
| 1 | 1 | 0 |
| 0 | o | o |
(120-121)
The connective evaluations are done recursively. We substitute the connective truth functions in for the connectives themselves by working from greatest to least scope. For example:
v(¬(p∧q)) = f¬(v(p ∧ q)) = f¬(f∧(v(p), v(q)))
Consider the following value assignments for the above formula:
v(p) = 1 and v(q) = 0
Using our connective truth function definitions from above, we would recursively evaluate by going from least to greatest scope, so:
v(¬(p ∧ q)) = f¬(f∧(1, 0)) = f¬(0) = 1
Semantic entailment, validity, and tautology (logical truth) are defined using D, the set of designated values. A set of formulas semantically entails some conclusion when there is no interpretation that assigns designated values to the premises while not assigning a designated value to the conclusion.
Σ ⊨ A iff there is no interpretation, v, such that for all B ∈ Σ, v(B) ∈ D, but v(A) ∉ D
Thus a valid inference is one where there is no interpretation in which all the premises have designated values but the conclusion does not. A formula is a logical truth (tautology) when every evaluation assigns it a designated value.
A is a logical truth iff φ ⊨ A, i.e., iff for every interpretation v(A) ∈ D
In order to craft a many-valued system of our choosing, we can modify the components of this structure. We of course will want to expand V to include three or more possible assignments for truth-value. We might also want to restructure validity by adding designated values. Additionally, we could change the types of connectives or alter the evaluations for their truth functions. We say that a logic is finitely many-valued when V has a finite number of values in it; and when V has n members, we say that it is an n-valued logic. We can evaluate an argument for validity by computing the values for the premises and conclusions for every possible set of assignments for the propositional parameters. When there is an interpretation where all the premises have a designated value but the conclusion does not, then it is invalid, and valid otherwise. The number of possible sets of assignments can become unmanageable for such validity evaluations, because they increase exponentially with each additional propositional parameter.
if there are m propositional parameters employed in an inference, and n truth values, there are nm possible cases to consider.
(122)
Summary
7.2.1
[A ≡ B is defined as (A ⊃ B) ∧ (B ⊃ A).]
[For simplicity, we will define material equivalence using conjunction and the material conditional (see section 1.2.1). But I do not know yet how that simplifies things, other than making one fewer connective to define.]
Let us start with the general structure of a many-valued logic. To simplify things, we take, henceforth, A ≡ B to be defined as (A ⊃ B) ∧ (B ⊃ A).
(120)
7.2.2
[The basic structure for many-valued logic is described by first filling it out with classical values. It is composed of a set of truth values {1, 0}, a set of designated values (the values preserved in valid inferences): {1}, and a set of connectives with their corresponding truth functions. The negation and conjunction truth functions assign values here in the classical bivalent way. The structure in its condensed form is: ⟨V, D, {fc; c ∈ C}⟩. V is the set of assignable truth values, D is the set of designated values, C is the set of connectives, c is some particular connective, and fc is the truth function corresponding to the connective that operates on the truth values of the formula in question.]
[Priest will now give the structure of many-valued logics. That structure is a set of symbols and functions that it uses. In its most condensed form, it is: ⟨V, D, {fc; c ∈ C}⟩. Let us unpack that. V stands for the set of truth values that can be assigned in our many-valued semantics. Here, those values are found in the set {1,0}. We might at this point be confused, because there are only two values. Either we are setting up a bivalent logic, and later we add more values, or, as in Nolt’s account, we will assign both or no values as members of a set. (From what happens later, it seems we begin here with a bivalent logic as a template that we will modify according to the many-valued logics we construct.) The D is the set of designated values, which are those that are preserved in valid inferences. Here there is just one value, 1, hence so far it seems to be a classical structure. We also have connectives, and as we will see, they are ¬ (negation), ∧ (conjunction), ∨ (disjunction), and ⊃ (material conditional). We think then of the connective’s truth functionally, which seems to mean that we think of the connectives as functions that assign a truth value based on the value they operate upon. So if a formula is assigned the value 1, the truth function operator for negation will assign it 0. Priest also defines conjunction here in the usual bivalent, classical way.]
Let C be the class of connectives of classical propositional logic {∧,∨,¬, ⊃}. The classical propositional calculus can be thought of as defined by the structure ⟨V, D, {fc; c ∈ C}⟩. V is the set of truth values {1,0}. D is the set of designated values {1}; these are the values that are preserved in valid inferences. For every connective, c, fc is the truth function it denotes. Thus, f¬ is a one-place function such that f¬(0) = 1 and f¬(1) = 0; f∧ is a two-place function such that f∧(x, y) = 1 if x = y = 1, and f∧(x, y) = 0 otherwise; and so | on. These functions can be (and often are) depicted in the following ‘truth tables’.
| f¬ | |
| 1 | 0 |
| 0 | 1 |
| f∧ | 1 | 0 |
| 1 | 1 | 0 |
| 0 | o | o |
(120-121)
7.2.3
[The interpretation function v maps propositional parameters to V, and thus assigning either 1 or 0. Truth functions apply to those V values recursively in complex formulas. Inferences are semantically valid iff “there is no interpretation that assigns all the premises a value in D, but assigns the conclusion a value not in D.”]
[Now we wonder about assigning truth values to formulas. We do so with an interpretation function, v, which maps the propositional parameter to V, meaning, to either 1 or o. He says the truth functions are applied recursively. For this notion, first recall the idea of “scope indicators” and “main operators” from Agler’s Symbolic Logic section 2.2.3. The recursive procedure seems to be that we substitute the v function for the main connective, while putting that connective’s truth function in for where the v function just was. If this presents us with a new main connective, then we keep repeating until all the connectives are replaced with connective truth functions. This is his example:
v(¬(p∧q)) = f¬(v(p ∧ q)) = f¬(f∧(v(p), v(q))).
(So if v(p) = 1 and v(q) = 0, v(¬(p ∧ q)) = f¬(f∧(1, 0)) = f¬(0) = 1.)
Let us go part by part. We want to know the value for this formula:
v(¬(p∧q))
We see that in order to know its value, we need to negate the formulation on the next lowest scale or scope, upon which the negation is operating. So we put the negation function in for v, and we now put v in for the negation connective, because we now need to know the value of the negation of the formula in parenthesis.
f¬(v(p ∧ q))
But we notice now that to determine this value, we need to see how the conjunction operates on the next lowest scale or scope, so we do the same thing.
f¬(f∧(v(p), v(q)))
So the v in v(p) and v(q) will assign a 1 or a 0 to these propositional parameters. In the example assignments, v(p) = 1 and v(q) = 0, that gives us:
f¬(f∧(1, 0)
We then calculate our evaluations moving from the lowest to the highest scope. Recall our rule for the behavior of the f∧ function.
f∧ is a two-place function such that f∧(x, y) = 1 if x = y = 1, and f∧(x, y) = 0 otherwise
Not both are 1, so the function assigns the pair the value 0.
f¬(0)
We next look at our rule for the negation truth function.
f¬ is a one-place function such that f¬(0) = 1 and f¬(1) = 0
Since the given value is 0, the function assigns it the value 1.
f¬(0) = 1
Priest next defines semantic validity, which follows the definition we have for it already (see section 1.1 and section 1.3). We must note that for validity, the value being preserved must be in D, the designated values. This will be important later when third values can be in D. “an inference is semantically valid just if there is no interpretation that assigns all the premises a value in D, but assigns the conclusion a value not in D”.]
An interpretation, v, is a map from the propositional parameters to V. An interpretation is extended to a map from all formulas into V by applying the appropriate truth functions recursively. Thus, for example, v(¬(p∧q)) = f¬(v(p ∧ q)) = f¬(f∧(v(p), v(q))). (So if v(p) = 1 and v(q) = 0, v(¬(p ∧ q)) = f¬(f∧(1, 0)) = f¬(0) = 1.) Finally, an inference is semantically valid just if there is no interpretation that assigns all the premises a value in D, but assigns the conclusion a value not in D.
(121)
7.2.4
[Many-valued logics keep this structure, but the contents of each set can vary from the classical template we made above. For example, it may have different connectives, different truth values, or different designated values.]
[We can then obtain a many-valued logic by broadening the components of this structure. We may have the same or a different set of connectives in set C. And V may contain any number of truth values, so long as there is at least one value. D can even have different values. Our connectives are normally either one or two place, but we can also have connectives with more places.]
A many-valued logic is a natural generalisation of this structure. Given some propositional language with connectives C (maybe the same as those of the classical propositional calculus, maybe different), a logic is defined by a structure ⟨V, D, {fc; c ∈ C}⟩. V is the set of truth values: it may have any number of members (≥ 1). D is a subset of V, and is the set of designated values. For every connective, c, fc is the corresponding truth function. Thus, if c is an n-place connective, fc is an n-place function with inputs and outputs in V.
(121)
7.2.5
[Connectives can take any number of places more than two, and they are evaluated accordingly using the connective functions operating on the series of values. A set of formulas semantically entails some conclusion when there is no interpretation that assigns designated values to the premises but not to the conclusion. A formula is a logical truth (tautology) when every evaluation assigns it a designated value.]
[An interpretation is (still) understood as a mapping from propositional parameters to values in V, by means of the function v. And again we use truth functions recursively, as above. The truth functions for connectives will have some number of places, and the assignment will be based on the values given at each place. Valid inferences are only those where, when all the premises have a designated value, the conclusion does too (or as it is formulated here, when there is no interpretation v making the premises have a designated value but the conclusion not have a designated value). A tautology or logical truth is a formula where every interpretation assigns it a designated value. It is also defined as a formula that is a semantic consequence of the empty set (for discussion on this formulation of tautology, see the comments in section 1.3.4 and section 2.3.11.]
An interpretation for the language is a map, v, from propositional parameters into V. This is extended to a map from all formulas of the language to V by applying the appropriate truth functions recursively. Thus, if c is an n-place connective, v(c(A1, ... , An)) = fc(v(A1), ... , v(An)). Finally, Σ ⊨ A iff there is no interpretation, v, such that for all B ∈ Σ, v(B) ∈ D, but v(A) ∉ D. A is a logical truth iff φ ⊨ A, i.e., iff for every interpretation v(A) ∈ D.
(121)
7.2.6
[“If V is finite, the logic is said to be finitely many-valued. If V has n members, it is said to be an n-valued logic.”]
[Later we will examine fuzzy logics where our assignable values are all the real numbers between zero and one, and thus we would have an infinite set of possible values to assign. But here we are dealing with a finite number of values.]
If V is finite, the logic is said to be finitely many-valued. If V has n members, it is said to be an n-valued logic.
(121)
7.2.7
[We can check an argument for validity by computing the values for all the premises and conclusions for every possible truth assignment for the propositional parameters. If there is at least one instance where all the premises obtain a designated value but the conclusion does not, then it is invalid. Otherwise, it is valid.]
[Recall from Agler’s Symbolic Logic section 3.6 the truth table method to evaluate arguments for validity. We fill out all the possible truth value assignments for the atomic formulas, and then we compute the values for the premises and conclusion to see if there is any line where all the premises are true and the conclusion false. Here we can do the same, looking for lines (or just simply for evaluation cases, if we are not using tables) where all the premises have a designated value and the conclusion does not.]
For any finitely many-valued logic, the validity of an inference with finitely many premises can be determined, as in the classical propositional calculus, simply by considering all the possible cases. We list all the possible combinations of truth values for the propositional parameters employed. | Then, for each combination, we compute the value of each premise and the conclusion. If, in any of these, the premises are all designated and the conclusion is not, the inference is invalid. Otherwise, it is valid. We will have an example of this procedure in the next section.
(122)
7.2.8
[This exhaustive checking procedure can become impractical in many-valued logic as we increase the number of propositional parameters. “For if there are m propositional parameters employed in an inference, and n truth values, there are nm possible cases to consider.”]
[Recall from Nolt’s Logics section 16.3.21 an argument we checked for validity in a four-valued semantics. It was disjunctive syllogism:
P ∨ Q, ~P ⊢ Q
(Nolt 445)
We have two propositional parameters, P and Q. But we have four possible value assignments for any parameter. In order to evaluate every possibility, as you can see, we need 16 rows, or 24. As you can imagine, the number of rows can get impractically long as we add more parameters.]
This method, though theoretically adequate, is often impractical because of exponential explosion. For if there are m propositional parameters employed in an inference, and n truth values, there are nm possible cases to consider. This grows very rapidly. Thus, if the logic is 4-valued and we have an inference involving just four propositional parameters, there are already 256 cases to consider!
(122)
Priest, Graham. 2008 [2001]. An Introduction to Non-Classical Logic: From If to Is, 2nd edn. Cambridge: Cambridge University.
Also cited:
Nolt, John. Logics. Belmont, CA: Wadsworth, 1997.
