Working with NOR gates

From: Laconic2 <laconic2_at_comcast.net>
Date: Sat, 30 Oct 2004 09:47:29 -0400
Message-ID: <Yqednae-Q9LlBh7cRVn-gA_at_comcast.com>



This topic is a spin off from Marshall's comment that he would like a language with <OR> built into it, but he shies away from <NOT>. It's far enough off topic so that I wanted to start a new topic.

Some of you may be familiar with the idea that it's possible to generate all the Boolean arithmetic operators starting with just NAND. As it turns out, it's equally possible to do that, starting with NOR.

A NOR gate takes two or more inputs, and generates TRUE if and only if all the inputs are FALSE. In some digital logic parts lists, this kind of gate is called an "inverter". If you have a source of FALSE, then you can combine it with any input to produce NOT the input. But it's simpler to generalize the NOR gate down to one or zero inputs. A NOR gate with only one input is a NOT gate. A NOR with zero inputs generates TRUE. TRUE fed into NOT generates FALSE.

A NOR gate fed into a NOT gate is an OR gate. Two or more inputs, each fed through a NOT gate, and the outputs fed through a NOR gate, is an AND gate. And so on.

 If you build a circuit with feedback, you can get second order logic. Beware.

Anyway, what if one were to generalize this concept from Boolean arithmetic to relations.

What if I have this predicate? "The employee with emp_id 123 has a first name that is NOT 'FRED'". In the same relation, I have a predicate like this, "The employee with emp_id 123 has a first name that is NOT 'BILL'". Now the assertion of these two predicates together is like asserting "The employee with emp_id 123 has a first name that is NOT ('FRED' OR 'BILL')". Notice how I snuck the OR in there, without having a mechanism to express OR in relations to begin with. It's easier to think about this stuff if there are only a finite number of first names.

This is just thinking out loud. It's not rigorous. But maybe some of you want to play with it. Received on Sat Oct 30 2004 - 15:47:29 CEST

Original text of this message