3-Valued Semantics

Before we can move from three-valued logic to fuzzy logic, we need to take a look at semantics – both how conventional two-valued logic handle semantics, and how three-valued logics extend the basic semantic structure. This isn’t exactly one of the more exciting topics I’ve ever written about – but it is important, and going through it now will set the groundwork for the interesting stuff – the semantics of a true fuzzy logic.

What we’ve looked at so far has been propositional 3-valued logics. Propositional logics aren’t particularly interesting. You can’t do or say much with them. What we really care about is predicate logics. But all we need to do is take the three-valued logics we’ve seen, and allow statements to be predicate(object).

In a conventional first-order predicate logic, we define the semantics in terms of a model or interpretation of the logic. (Technically, a logic and an interpretation aren’t quite the same thing, but for our purposes here, we don’t need to get into the difference.)

An interpretation basically takes a domain consisting of a set of objects or values, and does two things:

  1. For each atomic symbol in the logic, it assigns an object from the domain. That value is called the interpretation of the symbol.
  2. For each predicate in the logic, it assigns a set, called the extension of the predicate. The extension contains the tuples for which the predicate is true.

For example, we could use logic to talk about Scientopia. The domain would be the set of bloggers, and the set of blogs. Then we could have predicates like “Writes”, which takes two parameters – A, and B – and which is true is A is the author of the blog B.

Then the extension of “Writes” would be a set of pairs: { (MarkCC, Good Math/Bad Math), (Scicurious, Neurotic Physiology), … }.

We can also define the counterextension, which is the set of pairs for whiche the predicate is not true. So the counterextension of “writes” would contain values like { (MarkCC, Neurotic Physiology), …}.

Given a domain of objects, and the extension of each predicate, we know the meaning of statements in the logic. We know what objects we’re reasoning about, and we know the truth or falsehood of every statement. Importantly, we don’t need to know the counterextension of a predicate: if we know the extension, then the counterextension is simple the complement of the extension.

In three-valued Lukasiewicz logic, that’s not true, for reasons that should be obvious: if I(A) is the interpretation of the predicate A, then the complement of I(A) is not the same thing as I(lnot A). L_3 requires three sets for a predicate: the extension, the counterextension, and the fringe. The fringe of a predicate P is the set of values x for which P(x) is N.

To be more precise, an interpretation I for first order L_3 consists of:

  1. A set of values, D, called the domain of the logic. This is the set of objects that the logic can be used to reason about.
  2. For each predicate P of arity n (that is, taking n arguments), three sets ext(P), cext(P), and fringe(P), such that:
    • the values of the members of all three sets are members of D^n.
    • the sets are mutually exclusive – that is, there is no value that is in more than one of the sets.
    • the sets are exhaustive: ext(P) cup cext(P) cup fringe(P) = D^n.
  3. For each constant symbol a in the logic, an assignment of a to some member of D: I(a) in D

With the interpretation, we can look at statements in the logic, and determine their truth or falsehood. But when we go through a proof, we’ll often have statements that don’t operate on specific values – they use variables inside of them. In order to make a statement have a truth value, all of the variables in that statement have to be bound by a quantifier, or assigned to a specific value by a variable assignment. So given a statement, we can frequently only talk about its meaning in terms of variable assignments for it.

So, for example, consider a simple statement: P(x,y,z). In the interpretation I, P(x, y, z) is satisfied if (I(x), I(y), I(z)) in ext(P); it’s dissatisfied if (I(x), I(y), I(z)) in cext(P). Otherwise, (I(x), I(y), I(z)) must be in fringe(P), and then the statement is undetermined.

The basic connectives – and, or, not, implies, etc., all have defining rules like the above – they’re obvious and easy to derive given the truth tables for the connectives, so I’m not going to go into detail. But it does get at least a little bit interesting when we get to quantified statements. But to talk about we need to first define a construction called a variant. Given a statement with variable assignment v, which maps all of the variables in the statement to values, an x-variant of v is a variable assignment where for every variable y except x, . In other words, it’s an assignment where all of the variables except x have the same value as in v.

Now we can finally get to the interpretation of quantified statements. Given a statement forall x P, P is satisfied by a variable assignment v if P is satisfied by every x-variant of v; it’s dissatisfied if P is dissatisfied by at least one x-variant of v. Otherwise, it’s undetermined.

Similarly, an existentially quantified statement exists x P is satisfied by v if P is satisfied by at least one x-variant of v; it’s dissatisfied if P is dissatisfied by every x-variant of v. Otherwise, it’s undetermined.

Finally, now, we can get to the most important bit: what it means for a statement to be true or false in L_3. A statement S is T (true) if it is satisfied by every variable assignment on I; it’s F (false) if it’s dissatisfied by every variable assignment on I, and it’s N otherwise.

9 thoughts on “3-Valued Semantics

  1. Spencer

    “Given a statement forall x P, P is satisfied by a variable assignment v if P is satisfied by every x-variant of v.”

    I’m confused by your overloading of ‘satisfied,’ which makes this definition seem circular. Perhaps you meant:

    “Given a universally quantified statement S =forall x P, S is satisfied by a variable assignment v if P is satisfied by every x-variant of v.”

    However, I don’t understand why universal quantification is defined in terms of x-variants. Perhaps someone could give a motivating example for this?

    Reply
    1. Jonathan Amsterdam

      (Apologies, I don’t know how to get the math symbols to show up. Also, I’m using “true” and “if” a bit informally below.)

      What you want to say is “AxPx is true if Px is true for everything you can substitute for x.” But you can’t substitute objects into sentences (and the alternative, “AxPx is true if Px is true for every expression x”, gives you a dramatically different semantics, and probably not what you want). So you have to say “AxPx is true if Px is true under every assignment of x to something in the domain.” The variant part comes in when you have other variables that you want to hold constant while you change what x is assigned to. E.g. “Assign y to something. Now AxQxy is true if Qxy is true for every assignment of x to something, keeping y’s assignment unchanged.”

      Reply
  2. John Fringe

    I appreciate very much your posts on Maths, Mark.

    When you write about something unknown, one can always learn from your clever writing.

    And when you write about something familiar, it’s always a pleasure to go back to basics. I’m with Feynman on this: it’s good to rethink about known subjects. There are always new ideas.

    Reply
  3. Jonathan Amsterdam

    A couple of nit-picks:

    “we define the semantics in terms of a model or interpretation of the logic”

    I think it would be clearer and more accurate to talk about models or interpretations of sets of sentences of the logic.

    ” (Technically, a logic and an interpretation aren’t quite the same thing, but for our purposes here, we don’t need to get into the difference.)”

    I think you mean “model” instead of “logic” in the above. And the difference is very easy to state: a model of a set of sentences is an interpretation that makes them all true.

    “…what it means for a statement to be true or false in L3…”

    I don’t think that’s entirely sensical. I think you can only talk about a statement of L3 being true or false given an interpretation.

    Finally, what I think has gotten lost a bit in all the definitions is that (using ordinary letters for the quantifiers and “-” for “not”):

    AxPx iff -Ex-Px

    still holds in this logic, which is nice.

    Reply
  4. Doug Spoonwood

    “What we’ve looked at so far has been propositional 3-valued logics. Propositional logics aren’t particularly interesting. You can’t do or say much with them. What we really care about is predicate logics.”

    Interesting. I have Lukasiewicz’s _Elements of Mathematical Logic_ here. In the section on “The Sentential Calculus with Quantifiers” he uses two rules… a rule for joining the universal quantifier, and one for omitting it. He says that these rules can get justified by the formulae CCpqCCprCpKqr, CCpKqrCpq, and CCpKqrCpr. I’d suspect rules involving the existential quantifier can justified by some conditionals involving alternations instead of conjunctions.

    “The basic connectives – and, or, not, implies, etc., all have defining rules like the above – they’re obvious and easy to derive given the truth tables for the connectives, so I’m not going to go into detail. ”

    This makes me realize that the number of basic connectives for a fuzzy logic must have at least the cardinality of the continuum (an infinity “larger” than the infinity natural numbers), since even for unary functions the number of inputs and outputs here both equal the cardinality of the continuum.

    Reply
  5. Merrie Bergmann

    Mark,

    I’m flattered that you like my book An Introduction to Three-Valued and Fuzzy Logics. Your lessons have come right out of that book, including the unique terminology that I introduced. That being the case, you should cite my book as the source for your blog entries.

    Merrie Bergmann

    Reply

Leave a Reply to John Fringe Cancel reply