Saturday, May 21, 2005

3VL. Not quite.

I recall doing this sometime between 1984 and 1988, after I moved from Utah to Phoenix. When I was working out my version of 3-valued logic, the truth tables for "And" (&) and "or" (v) were satisfactory, but in order to express relationships between propositions, I needed a conditional and biconditional. My first attempt gave (using the constants) T -> T = T; T -> U = U; T -> F = F; U -> T = T; U -> U = U; U -> F = U; F -> T = T; F -> U = T; F -> F = T.
I then began exploring truth tables for the tautologies of classical logic, for instance de Morgan's law ~ (P & Q) <-> ~P v ~Q. I quickly found that there was a gaping hole in every truth table I could construct. For the most familiar logical laws, most entries turned out T, but when P and Q both had values of U, the proposition in question had values of U. This was hardly tolerable. It should be obvious that "if P then P" should be a tautology, but even for something this simple, I got U. At this point, I think I decided to see what else had been done on the subject. I went out to the ASU library to find either Rosser and Turquette's "Many valued logic" or Restall's "Three valued logic" (I'm not sure which), and found that this had been done. It's still not clear to me whether this was Kleene's "weak" system or his "strong" system, but in either case, it didn't work, for the very reason I had already discovered. I found that there was another alternative, Lukasiewicz 3-valued logic, which had the same truth tables I had already worked out, but differed in only one place: U -> U = T (instead of U. I didn't have much time to study it then, but I took this one idea to work with later.
Maybe a year or so later, I saw a friend working on truth tables for a different 3VL, and picked up my own studies again. This time, it occurred to me that I could use a function to distinguish "T or U" from "F", and called this "possible", and one to distinguish "T" from "U or F", and called this one "certain" or "necessary". In combination with negation, one of the first and easiest results were the formulas "Certainly not" = "not possible" and "Not necessarily" = "Possibly not".
When I found this, I considered it too simple and elegant to ignore. Also, using the Lukasiewicz conditional, and biconditional, I could prove a number of significant theorems of elementary propositional logic. However, one of the most important ones, Modus ponens, didn't work. I consulted the source most easily available to me, the Encyclopedia Britannica's article on "History and Kinds of logic", and learned a little bit more about the Lewis systems of modal logic. I particularly noted that there were several varieties, that these systems were not truth functional and could not be expressed with truth tables, but had to be constructed on an axiomatic basis. and that the decision problem (deciding whether a given proposition was or was not a theorem), was particularly difficult. I then tried evaluating a number of the axioms according to the three-valued tables I had developed, and found that some of them worked, and some of them didn't. At this point, I wondered "Why do some of these work, but not others?".

No comments: