Saturday, April 24, 2010

Three-Valued Logic And Irreproducible Results In Science, Part I

This is a short series of two posts that discusses Three-Valued Logic (3VL) and uses it to demonstrate how irreproducible results corrupt not only the scientific work in which they appear, but also spread that corruption to any related work.

In short, this series of posts demonstrates that irreproducible results are viral. My current work on the Aqua satellite is used as an illustrative example in the second of these posts.

In this post we look at Two-Valued Logic and Three-Valued Logic and briefly discuss how they work.

Two-Valued Logic
To start off, let's take a quick look at the more common two valued logic system. This system gets its name from the fact that there are only two possible values for any statement: True or False. Two-Valued Logic is also called Boolean logic.

In regards to this post, we're most concerned with how these logic values of True and False can move through a system of logical predicates. For example, if we have a True statement and a False statement and a logical predicate requiring at least one true statement, than that predicate transforms the one True statement and one False statement into a single statement that is True. This is because the requirement of at least one True statement has been met and the predicate is therefore True.

Such a predicate is commonly referred to as an OR statement. For an OR statement to be True, either statement 1 or statement 2 must be True. There are several types of predicates in Boolean logic. The most common are OR, AND, and NOT. One way to define predicates is using a true table. A truth table shows all possible inputs to the predicate and what the output of the predicate is. The truth tables for OR, AND, and NOT in Boolean logic are shown below.

OR Truth Table.

AND Truth Table

NOT Truth Table.

In a nutshell, the OR predicate accepts two inputs and converts them to a single output. That output will be True if either of its inputs are True, or False if both inputs are False.

The AND predicate also accepts two inputs, but returns TRUE only if both inputs are True. In all other cases it returns False.

The NOT predicate simply flips True inputs to False outputs and False inputs to True Outputs.

TECHNICAL ASIDE: Truth tables are one way to define logical predicates. They use "case analysis", a method of listing every possible case and the corresponding outcome. However, there are other, more elegant ways to define predicates. In his book Predicate Calculus And Programming Semantics, the late Edsger Dijkstra defined the AND predicate using what is known as The Golden Rule, shown below, with the equivalence operator (==) having the lowest binding and meaning "Is The Same As":

      The Golden Rule: p AND q == p == q == p OR q

This type of definition is considered superior to case analysis. Once the properties of the various predicates are captured in this manner, they can be used as building blocks to far more sophisticated theorems. Case analysis, on the other hand, can never demonstrate anything more than what is provided by the cases themselves.

Three-Valued Logic
Three-Valued Logic (3VL) builds upon Boolean Logic. There are several conventions for 3VL. We'll be looking at a particular convention, one in which the third truth value is Unknown. So 3VL, as discussed here, has three truth values: True, False, and Unknown.

TECHNICAL ASIDE: Relational database products make heavy use of 3VL, and refer to the Unknown truth value as NULL. The late E.F. Codd invented relational databases while working for IBM, He introduced the convention of using the word NULL to represent Unknown, and assigned NULL the symbol of the Greek lowercase omega, shown in the image at the beginning of this post.

Like Boolean Logic, 3VL has predicates that can be defined using truth tables. The truth tables for 3VL AND, OR, and NOT predicates are shown below.

When the only values in use are True and False, 3VL gives the exact same answers as Boolean logic. However, when an Unknown truth value is used as inputs it can also show up as the outputs for a predicate. The result of the predicate "False OR Unknown" is Unknown. The result of the predicate "NOT Unknown" is always Unknown. The result of an AND predicate with an Unknown input is always Unknown or False, never True.

The Point Of All This
It is this last result that interests us here. The result of the predicate "X AND Unknown" can never be True, no matter what the value of X is.

This is our stopping point for now. The next post in this series will discuss the relationship between Three-Valued Logic and science.

Boolean Logic - Wikipedia Entry
Ternary Logic - Wikipedia Entry
SQL NULL - Wikipedia Entry
Predicate Calculus And Programming Semantics - Edsger Dijkstra
A Relational Model of Data for Large Shared Data Banks - Edgar F. Codd

No comments:

Post a Comment