부울대수와 논리 회로

스위치 두 개로 출입 신호를 만들 때 모든 경우의 동작을 식으로 적을 수 있습니다. 명제 논리를 0·1 값으로 옮기는 부울대수를 익힙니다. 곱은 AND, 합은 OR, 보수는 NOT이라는 약속을 먼저 확인합니다.

수의 연산과 다른 0·1 법칙

부울합에서 1+1=1이고 부울곱에서 1·1=1입니다. 이것은 정수 덧셈이 아닙니다. $x+0=x$, $x\cdot1=x$, $x+1=1$, $x\cdot0=0$, $x+x=x$, $x\cdot x=x$가 기본입니다. 보수 $\bar x$와는 $x+\bar x=1$, $x\bar x=0$입니다.

흡수법칙 $x+xy=x$를 확인해 봅시다. x=0이면 둘 다 0, x=1이면 둘 다 1입니다. 대수적으로 $x+xy=x(1+y)=x\cdot1=x$입니다. 분배법칙을 이용해 $xy+x\bar y=x(y+\bar y)=x$도 얻습니다.

드모르간 법칙은 $\overline{xy}=\bar x+\bar y$, $\overline{x+y}=\bar x\bar y$입니다. 전체 보수를 빼면서 각 변수만 부정하고 같은 연산자를 유지하면 틀립니다. 쌍대는 0↔1, +↔·를 동시에 바꾸는 연산이며 어떤 특정 입력의 값이 같다는 의미는 아닙니다.

식과 게이트를 왕복한다

AND는 둘 다 1, OR는 하나 이상 1, NOT은 값을 뒤집습니다. NAND는 AND의 출력 보수, NOR는 OR의 출력 보수, XOR는 두 입력이 다를 때 1입니다. NAND 하나에 같은 x를 두 입력으로 넣으면 $\overline{xx}=\bar x$라 NOT을 구현합니다. NAND로 AND를 만들려면 NAND 출력의 보수를 한 번 더 취합니다.

출입식 $F=L(A+W)$는 관리자 A 또는 작성자 W의 OR 출력을 로그인 L과 AND로 연결합니다. 입력 L=0,A=0,W=1에서 OR는 1이지만 마지막 AND는 0입니다. 조건을 게이트 흐름으로 읽어도 논리식의 괄호와 같은 의미여야 합니다.

최소항은 모든 변수가 한 번씩 나타나는 곱항으로, 특정 입력 조합 하나에서만 1입니다. 변수 x,y,z에 대한 $\bar x y z$는 011만 선택합니다. 진리표의 출력 1인 행들의 최소항을 OR하면 정규 곱의 합(SOP, sum of products) 형태를 얻습니다. 최대항은 반대로 특정 행 하나에서 0이 되는 합항이며 출력이 0인 행의 최대항들을 AND하여 정규 합의 곱(POS, product of sums) 형태를 만듭니다. 곱항들의 합이 SOP, 합항들의 곱이 POS입니다.

스스로 풀어보기

문제 1. $xy+\bar x y$를 줄이고 네 입력에서 값이 같음을 확인하세요.

풀이: y(x+\bar x)=y입니다. (x,y)=00,01,10,11에서 원식과 y의 출력은 0,1,0,1입니다. 대수 변형과 진리표 두 방법으로 확인했습니다.

문제 2. x,y의 XOR를 AND·OR·NOT으로 표현하세요.

힌트: 01과 10 두 행을 각각 선택합니다.

풀이: $\bar x y+x\bar y$입니다. x,y가 서로 다를 때만 둘 중 한 항이 1이며 같은 경우 두 항 모두 0입니다. OR인 x+y와 달리 11에서 0입니다.

1+1이 헷갈리면 연산 이름부터 표시하세요. 식을 시각적으로 최소화하는 선택 심화는 카르노맵입니다.