순서 다음은 multi-level NAND gate circuit을 만드는 과정이다. 1. circuit을 만들기 위해 function을 simpify한다. 2. 1번의 결과로부터 AND와 OR gate로 된 circuit을 만든다. 단 output은 OR gate여야 한다. 3. 2번에서는 AND와 OR가 항상 번갈아 나와야 하고, 같은 종류의 gate가 연달아 나와서는 안된다. 4. 일단 모든 gate를 NAND로 바꾸고, 연결선은 그대로 둔다. 5. output gate를 level 1이라고 했을 때 홀수 level의 gate에 들어가는 literal을 invert해준다. 이러한 과정을 통해 정말로 multi-level NAND gate circuit이 성립되는지 살펴보려면, 2-level씩 끊어서..

개요 Input과 output 사이에 직렬로 연결되는 gate의 최대 개수는 gate의 level의 개수에 따른다. 따라서, sum-of-products 또는 product-of-sums의 형태로 되어있는 function은 곧, 2-level gate circuit로 귀결된다. 일반적으로, gate가 flip-flop output으로 부터 나오는 case에서는 모든 variable과 그의 complement는 circuit input으로 사용할 수 있다. (flip-flop은 이후에 다루게 됨) 이러한 이유 때문에, inverter는 보통 level로 카운트 하지 않는다. 앞으로는 다음의 용어를 사용할 것이다. 1. AND-OR circuit AND gate가 OR gate 다음에 이어지는 2-level..