Re: Boolean algebra "2 nots" problem

From: Don Reble (djr_at_nk.ca)
Date: 06/24/04 

Date: Thu, 24 Jun 2004 17:51:41 -0600

> Given three inputs A, B, C, generate three outputs A', B', C' using
> any number of AND and OR operations, but a maximum of 2 NOTs.

Ok.

There are eight possible input states:
    ABC, ABC', AB'C, AB'C', A'BC, A'BC', A'B'C, A'B'C'.
There are 256 possible functions; a function maps each of the eight
possible input states to either of two output states. I name each
function with an eight bit string; the function produces the n'th bit of
the string, in response to the n'th input state.

The given functions are A=11110000, B=11001100, and C=10101010.
Do these combinations:

10001000 = 11001100 AND 10101010
10100000 = 11110000 AND 10101010
11000000 = 11110000 AND 11001100
11101110 = 11001100 OR 10101010

10000000 = 11110000 AND 10001000
11111000 = 11110000 OR 10001000

11101000 = 11111000 AND 11101110

00010111 = NOT 11101000

00000010 = 10101010 AND 00010111
00000100 = 11001100 AND 00010111
10010111 = 10000000 OR 00010111

11001110 = 11001100 OR 00000010
11110010 = 11110000 OR 00000010
11110100 = 11110000 OR 00000100
11110110 = 11110000 OR 00000110

00000110 = 11001110 AND 00010111
00010010 = 11110010 AND 00010111
00010100 = 11110100 AND 00010111
10010110 = 11110110 AND 10010111

01101001 = NOT 10010110

01101111 = 01101001 OR 00000110
01111011 = 01101001 OR 00010010
01111101 = 01101001 OR 00010100

00000111 = 01101111 AND 00010111
00010011 = 01111011 AND 00010111
00010101 = 01111101 AND 00010111
 
10001111 = 10001000 OR 00000111
10110011 = 10100000 OR 00010011
11010101 = 11000000 OR 00010101

00001111 = 10001111 AND 01101111
00110011 = 10110011 AND 01111011
01010101 = 11010101 AND 01111101

As you see, there are two NOT's, and the last group has A', B', and C'. 

--
Don Reble       djr@nk.ca