Re: Relational Completeness

"Marshall Spight" <mspight_at_dnai.com> wrote in message news:V1K2d.451720$%_6.441906_at_attbi_s01...
> Consider this table:
> 1 1 xa
> 1 0 xb
> 0 1 xc
> 0 0 xd
>
> Now one can imagine {xa, xb, xc, xd} as completely specifying a
> boolean operation. Given that this is boolean *algebra* then each of
> the xn is either 1 or 0, so there are exactly sixteen possible values
> for the set of xn. (Again, we can construct a truth table for them.)
>
> In order for a set of boolean operators to be complete, one must be
> able to construct every one of the 16 possible values of {xn}. Which
> can be done with {AND, NOT}, or with {OR, NOT}, or with {NAND},
> etc.
>
> Now while this is certainly not any earth shaking result, it's certainly
> COMPLETE for the domain; every function on two bits that can
> exist has been accounted for.

What's really amazing is this: The PDP-6 computer, built by DEC from about 1964 to about 1968 exploited this fact
in order to implement all 16 boolean operations, with less logic than it would have taken to imlpement a subset of them. All they did was run four wires from four bits of the instruction register into what would have been the gates for the truth table. The "truth table" for each of these operations was right in the op-code!

(Actually, for each of the 16 operations, the were four different "modes", for a total of 64 op-codes, but that's a detail).

Some of us programmers questioned why there were boolean oerators like "set to zeroes" (SETZ) or "set to ones" (SETO). The answer was that it was cheaper to implement them than not to implement them!

Sorry for the digression. Received on Sat Sep 18 2004 - 03:18:16 CEST