순서 다음은 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씩 끊어서..

AND-OR Forms AND-OR circuit는 3가지의 form으로 변환이 가능하다. Function은 sum-of-products 형태여야 한다. 먼저 기본적으로 F = A + BC' + B'CD 가 주어졌다고 하자. 이 식은 기본적으로 DeMorgan's law를 이용해서 나머지 3가지로 변환이 가능하다. 이러한 식은 곧바로, 위 그림과 같이 구현이 가능하다. AND-OR으로 부터 NAND-NAND, OR-NAND, NOR-OR 꼴로 변형되었다. 잘 살펴보면 알 수 있듯이, 기본적으로 gate나 gate input의 위치는 그대로지만, gate input은 complement가 들어가기도 하고, gate의 종류도 바뀐다. 어찌됐든, 4가지 모두로 결국 같은 function이 구현된다. OR-AN..