Friday, March 2, 2012

Gödel and powerbooleans

What is a boolean?

A boolean is either true or false.

What is a powerboolean?

A powerboolean is a subset of the booleans (B):

  • True = {true}
  • Both = {true, false}
  • False = {false}
  • Null = {}

This set is equivalent to 2B (the powerset of the booleans), hence the name. The powerboolean operations are simply defined as the image of the normal boolean operations over B. The truth tables are as follows:

ANDTBFN
TTBFN
BBBFN
FFFFN
NNNNN
ORTBFN
TTTTN
BTBBN
FTBFN
NNNNN
NOT
TF
BB
FT
NN

These truth tables should not be confused with Belnap logic (which is another 4-valued logic) because there are different definitions for (N AND B), (B AND N), (N OR B), (B OR N). Also, In Belnap logic, B and N can be swapped, and the same rules apply, so they are not unique. In the powerbooleans, B and N cannot be swapped in a similar way, because if you do swap them, the truth tables would have to change. So the powerbooleans have unique values, they aren't just repetitions of some third truth value found in most 3-value logics. The 4-values of the powerbooleans are truely unique.

Who is Gödel?

Gödel is best known for his incompleteness theorems, but he is also known for the fuzzy logic named after him: "Gödel–Dummett" logic (also known as superintuitionistic, intermediate, or minimum t-norm logic). I've talked about product fuzzy logic before, but this time I'd like to talk about Gödel fuzzy logic. The operations are as follows:

  • (x AND y) = min(x, y)
  • (x OR y) = max(x, y)
  • NOT(x) = 1 - x

These operations are defined over a continuous interval from 0 to 1, so I can't really give truth tables for these, but to cut to the chase, they would look very similar to the tables above.

What do they have to do with each other?

If we let NOT(x) = (if x < 0, then x, else 1 - x), extend the interval of Gödel fuzzy logic below zero (which forces OR to be redefined in terms of our new NOT), and assign the following fuzzy values to each powerboolean:

  • True = 1
  • Both = 1/2
  • False = 0
  • Null = -1/2

then Gödel fuzzy logic and powerboolean operations are the same.

2 comments:

  1. Unless I'm missing something, it doesn't seem like it works with OR. (Null OR False) = max(-1/2, 0) = 0 = False, but it's supposed to be Null?

    ReplyDelete
    Replies
    1. Because we changed the definition of NOT, it works. (x OR y) becomes NOT(NOT(x) AND NOT(y)), which is not quite the same as max, you're right. The piecewise definition of OR becomes: (max(x, y) if x >=0 and y >=0, min(x, y) otherwise). I hope that makes more sense now.

      Delete