아래 그림의 논리회로와 같은 진리값을 NAND소자만으로 구성하여 나타내… | [공조냉동기계기사 필기] 22년 1회차 기출문제 상세 페이지

그림의 회로는 입력 A, B가 AND 게이트로 들어가고, 입력 C는 NOT(인버터)을 지난 뒤 그 AND 출력과 함께 OR 게이트로 들어가 출력 X가 된다. 즉 $X = A\cdot B + \overline{C}$ 이다.
이 식을 NAND만으로 바꾸려면 이중부정과 드모르간 정리를 쓴다. $X = AB+\overline{C} = \overline{\overline{AB+\overline{C}}} = \overline{\overline{AB}\cdot C}$ 로 정리된다.
마지막 식은 첫 번째 NAND로 $\overline{AB}$를 만들고, 그 출력과 C를 두 번째 NAND에 넣는 형태다. 실제로 $\overline{\overline{AB}\cdot C} = AB + \overline{C}$ 이므로 원래 회로와 진리값이 완전히 같다.
따라서 필요한 NAND 소자는 최소 2개다. AND·OR·NOT을 각각 NAND 조합으로 하나씩 바꿔 쌓으면 개수가 훨씬 늘어나지만, 식을 먼저 정리하면 이렇게 줄일 수 있다.