Re: The BOOLEAN data type - What is really Boolean and what is not?

From: Costin Cozianu <c_cozianu_at_hotmail.com>
Date: Fri, 25 Apr 2003 18:49:46 -0700
Message-ID: <b8cocp$8q4qk$1@ID-152540.news.dfncis.de>

Bruce Rennie wrote:
> pkl_at_mailme.dk (Peter Koch Larsen) wrote in message news:<61c84197.0304180715.23ded92b_at_posting.google.com>...
>

>>Costin Cozianu <c_cozianu_at_hotmail.com> wrote in message news:<b7ncgr$2odsj$1_at_ID-152540.news.dfncis.de>...
>>
>>>--CELKO-- wrote:
>>
>>[large snip]
>>

>
> [Snipped]
>

>>>Using a decent type system , I can define a three valued logic boolean, 
>>>in  5 lines of code and reuse it all over the place where I need. If I 
>>>really need to I can dfine a fuzzy boolean data type in a hadnful of 
>>>code and reuse it all over the place.
>>
>>Yes - not that difficult.

>
>
> In fact - IMPOSSIBLE. Boolean algebras require either 2 or an integer
> power of 2 number of values in the domain. Check any good
> combinatorics text for how this works. So at a minimum you will have
>
> True or False ( 2 distinct values )
>
> or you could have
>
> True A B False ( 4 distinct values ) or 8, 16, etc
>
> where both A and B are part way between True and False.
>
> This leads to the correct logic tables.
>
> Since three valued logic is not Boolean ( there are a number of
> different ways the logic operations can be written ( for 3VL-AND and
> 3VL-OR and 3VL-NOT )), you have to decide on the particular operations
> that you will allow and how the results will be calculated. Therefore,
> the normal Boolean operations of AND and OR and NOT cannot and do not
> work with three value domains.
>
> Allowing another value in the Boolean (2VL) domain forces it to no
> longer be Boolean. Problems arise. For further research, look at the
> Russian TERNARY computer from the 1950's. This was not a Boolean logic
> based machine.
>
>

>>The to me fundamental problem is how to cope with missing values. I
>>agree that You have no need for them in base tables, but what happens
>>in the situation where you have an outer join? If outer joins are to
>>be provided by the DBMS - and I believe they are to useful to be let
>>out - there must be some means of denoting that a field has no value.
>>There are three ways to go:

>
>
> If the value is missing, then provide a way in the design of the
> database that allows you NOT to store information without resorting to
> the use of NULLS. An appropriate redesign/rethink of the questions
> being asked of the DBMS on the database will give rise to sensible
> answers. Too many times I've been required to provide answers to the
> wrong questions - so - teach the questioners to ask the right
> questions - not always easy, but doable. It allows correct information
> to be given instead of wrong/partially correct that is generally
> given now (statement is stated this way deliberately - think carefully
> the implications).
>
>

>>1) Use a NULLABLE type. This could be an extension like the sum-type
>>mentioned (i have not read that thread yet so i can not comment).  I
>>see no problems with that approach.
>>2) Use a DEFAULT value. This could be feasible in some situations, but
>>in many situations it would not. The most obvious example would be if
>>the field in question is boolean. Which default could you possible
>>use?
>>3) Use a marker that existed independently of the field. This approach
>>has so many flaws that I believe it to be infeasible. For one thing,
>>what value should we store in that field? If we have ADT's we must be
>>careful as the ADT might have some constraints, that if not set will
>>invalidate the type - a CIRCLE could as an example be required a
>>non-negative radius. Even non-ADT types might have some integrity
>>constraints: think about a floating point number stored in the IEEE
>>format.
>>
>>My personal conclusion is that we are stuck with NULLS - if not in the
>>SQL sense then at least in the sense that we are to have some kind of
>>sum type. And if we are stuck with such a type, then the only sensible
>>thing is to have it standardised by the DBMS - how else are we going
>>to let the DBMS perform the outer join by itself?
>>This is getting very off topic, however, so I have started a new
>>thread on this subject.
>>
>>Kind regards
>>Peter

>
>
> regards
>

Any formalism is as good as the quality of the solutions it brings to a targeted domain. It's true that for logic circuits you probably need to have a proper boolean algebra.

For the purpose of constructing type theory, which has its importance in, it has been observed that for example Tertium Non Datur ( a \/ (!a) = 1 ) is unnecessary or even harmful (it leads to contradictory proofs), therefore it is not accepted.

Therefore it is true that you cannot construct boolean algebras with 3 elements, but you can construct any damn logic you please if you don't make that a boolean algebra (i.e. drop the existence of complements and consequently you reformulate the Tertium Non Datur or drop it altogether).

Of course, then we have to discuss the merits of the new formalism. Given the fact that a large part of modern mathematics has done beautfully without tertium non datur, I don't see why database users cannot be given the benefit of a doubt that they can work in a multi-valued logic not based on boolean algebra.

All I care for is to have a lattice with :

1. bounded below: There exists an element 0, such that a ? 0 = a for all a in A.
2. bounded above: There exists an element 1, such that a ? 1 = a for all a in A.
3. distributive law: For all a, b, c in A, (a ? b) ? c = (a ? c) ? (b ? c).

but without the reverse element, and without Tertium Non Datur.

4) existence of complements: For every a in A there exists an element ¬a in A such that a ? ¬a = 1 and a ? ¬a = 0.

Indeed, all the little fuzzy logic(s) I've been taught, doesn't support number 4 at all, and number 4 would have absolutely no value for the domains for which fuzzy logic is necessary.

Then we have to analyze the merits or demerits of each formalism, if you want to claim that fuzzy logic has no merits because it doesn't support number 4, you'd be way off the charts :)

So, I'm all for formalisms and for mathematics in software, but the fact that something is a specific formalism or something else is a different formalisms, even a less powerful (weaker) formalisms, doesn't say much. To make a complete argument you have to discuss the value of the formalism with regards to a particular domain of application.

If you can't apply Field theory to a problem you have to see what you can do with Anneaux (or how the heck they are called in English ??), if you can't have a boolean algebra you may still get useful results just with lattice theory.

So why do you think a three valued logic (or indeed a logic on the continuous [0,1]) is that bad for database management so that you can dismiss it out of hand ?

Why do you think it makes any sense at all to have a boolean algebra with 2^N elements, let's take the easiest case 4, when I don't see for the life of me how you can map the algebraic rules to semantics understood by users and programmers ?

best regards,
Costin Cozianu Received on Fri Apr 25 2003 - 20:49:46 CDT