명제논리, 부울대수, 논리게이트

이번 절에서는 1장 2절에서 배운 0과 1을 가지고 참/거짓 판단을 배우는 시간입니다.

1장 2절에서는 이렇게 배웠습니다.

컴퓨터는 숫자를 0과 1로 표현합니다.

1장 3절에서는 한 단계 더 갑니다.

컴퓨터는 판단도 0과 1로 처리합니다.

즉,

참 = 1
거짓 = 0

이라고 이해하면 됩니다.

이번 절 내용은 이산수학의 논리와 명제·부울대수, 논리회로의 부울대수와 논리게이트, 컴퓨터구조의 디지털 논리회로와 직접 연결됩니다.

이번 절의 큰 그림

이번 절의 학습 흐름은 다음과 같습니다.

명제논리
→ 부울대수
→ 논리게이트
→ 논리회로

각각을 쉽게 말하면 다음과 같습니다.

중요한 연결은 이것입니다.

명제논리의 참/거짓
= 부울대수의 1/0
= 논리회로의 전기 켜짐/꺼짐

명제논리 기본

명제란?

명제는 참인지 거짓인지 분명하게 판단할 수 있는 문장입니다.

예를 들면 다음과 같습니다.

명제는 반드시 참 또는 거짓 중 하나여야 합니다.

참 = 1
거짓 = 0

명제 변수

명제를 매번 긴 문장으로 쓰면 불편합니다.

그래서 보통 p, q, r 같은 문자로 표현합니다.

p: 비가 옵니다
q: 우산을 가져갑니다

라고 가정하겠습니다.

그러면

비가 오고 우산을 가져갑니다

라는 문장은 이렇게 쓸 수 있습니다.

p ∧ q

여기서 ∧는 “그리고”라는 뜻입니다.

논리연산과 진리표

기본 논리연산

명제논리에서 가장 중요한 연산은 5개입니다.

시험에서는 보통 ∧, ∨, ~, →가 많이 나옵니다.

NOT: 부정

NOT은 반대로 바꾸는 것입니다.

참 → 거짓
거짓 → 참

p: 비가 옵니다
¬p: 비가 오지 않습니다

진리표는 다음과 같습니다.

컴퓨터식으로 쓰면 다음과 같습니다.

AND: 논리곱

AND는 둘 다 참일 때만 참입니다.

p ∧ q

p이고 q입니다

예를 들어 로그인 조건을 생각해 보겠습니다.

p: 아이디가 맞습니다
q: 비밀번호가 맞습니다

p ∧ q

즉,

아이디도 맞고 비밀번호도 맞아야 로그인 성공

진리표는 다음과 같습니다.

컴퓨터식으로 쓰면 다음과 같습니다.

AND는 둘 다 1이어야 1입니다.

OR: 논리합

OR는 하나라도 참이면 참입니다.

p ∨ q

p 또는 q입니다

예를 들어 할인 조건을 살펴보겠습니다.

p: 학생입니다
q: 쿠폰이 있습니다

p ∨ q

라면,

학생이거나 쿠폰이 있으면 할인

입니다.

진리표는 다음과 같습니다.

컴퓨터식으로 쓰면 다음과 같습니다.

OR는 하나라도 1이면 1입니다.

주의할 점이 있습니다. 논리학에서 OR는 보통 포함적 OR입니다.

즉,

p도 참이고 q도 참인 경우도 참

입니다.

XOR: 배타적 OR

OR와 비슷하지만 다른 점이 있습니다. 바로 XOR입니다.

XOR는 둘이 다를 때만 참입니다.

XOR는 정확히 하나만 1일 때 1입니다.

예를 들어 스위치 두 개로 전등을 조작하는 회로를 생각할 수 있습니다.

스위치 상태가 서로 다르면 켜짐
스위치 상태가 같으면 꺼짐

이런 경우 XOR와 관련됩니다.

논리회로 범위에도 AND, OR, NOT뿐 아니라 XOR, NAND, NOR 같은 논리게이트가 포함됩니다.

조건문 p → q

이산수학에서 학생들이 가장 많이 헷갈리는 부분이 다음과 같습니다.

p → q

p이면 q입니다.

p: 비가 옵니다
q: 길이 젖습니다

p → q

는

비가 오면 길이 젖습니다

라는 뜻입니다.

진리표는 다음과 같습니다.

가장 중요한 것은 이것입니다.

p가 참인데 q가 거짓일 때만 p → q는 거짓입니다.

즉,

약속을 했는데 결과가 안 지켜진 경우만 거짓

입니다.

예를 들어 선생님이 말했습니다.

숙제를 하면 사탕을 줍니다.

이 말이 거짓이 되는 경우는 하나입니다.

숙제를 했는데 사탕을 안 줬습니다.

숙제를 안 한 경우에는 이 약속이 깨졌다고 보기 어렵습니다.

쌍조건문 p ↔ q

쌍조건문은 양쪽의 참/거짓이 같을 때 참입니다.

p ↔ q

p일 때 그리고 그때에만 q입니다.

p와 q가 같습니다.

진리표는 다음과 같습니다.

둘 다 같으면 1, 다르면 0

XOR와 반대라고 보면 됩니다.

진리표 전체 정리

p와 q가 있을 때 가능한 경우는 4가지입니다.

00, 01, 10, 11

표로 정리하면 다음과 같습니다.

이 표는 반드시 익숙해져야 합니다.

논리식의 성질

항진명제, 모순명제, 사건명제

명제식은 결과에 따라 세 가지로 나눌 수 있습니다.

항진명제

p ∨ ¬p

p이거나 p가 아닙니다

비가 오거나 비가 오지 않습니다

이것은 무조건 참입니다.

모순명제

p ∧ ¬p

p이고 동시에 p가 아닙니다

비가 오고 동시에 비가 오지 않습니다

이것은 불가능합니다.

그래서 항상 거짓입니다.

이산수학 예시문제에서도 모순명제를 묻는 문제가 나오고, p ∧ ∼p가 모순명제에 해당합니다.

논리적 동치

논리적 동치란 두 명제식의 진리값이 항상 같은 것입니다.

기호로는 이렇게 씁니다.

A ≡ B

A와 B는 논리적으로 같습니다.

가장 중요한 동치는 이것입니다.

p → q ≡ ¬p ∨ q

즉,

p이면 q입니다

는

p가 아니거나 q입니다

와 같습니다.

처음에는 이상해 보이지만 진리표를 만들면 완전히 같습니다.

결과 열이 같습니다.

p → q ≡ ¬p ∨ q

입니다.

부울대수

부울대수란?

이제 명제논리에서 부울대수로 넘어갑니다.

부울대수는 0과 1만 가지고 계산하는 대수입니다.

일반 수학에서는 숫자가 많습니다.

0, 1, 2, 3, 4, ...

하지만 부울대수에서는 값이 두 개뿐입니다.

0, 1

1 = 참
0 = 거짓

으로 이해하면 됩니다.

부울대수는 컴퓨터 회로를 설계할 때 핵심입니다. 논리회로 범위에 부울대수, 부울함수의 간소화, 논리게이트, 논리회로가 포함되어 있고, 이산수학에서도 부울식과 부울함수의 간소화를 다룹니다.

명제논리와 부울대수의 연결

명제논리와 부울대수는 사실 같은 구조를 다른 말로 표현한 것입니다.

중요합니다.

논리곱 AND = 곱셈처럼 쓰지만 일반 곱셈과 완전히 같지는 않습니다.
논리합 OR = 덧셈처럼 쓰지만 일반 덧셈과 완전히 같지는 않습니다.

1 + 1 = 1

입니다.

참 OR 참 = 참

이기 때문입니다.

일반 산수의 1 + 1 = 2와 다릅니다.

부울대수 기본 법칙

시험에 자주 나오는 부울대수 법칙을 정리하자.

항등 법칙

x + 0 = x
x · 1 = x

OR에서 0은 영향을 주지 않습니다.
AND에서 1은 영향을 주지 않습니다.

x + 0 = x

0 + 0 = 0

1 + 0 = 1

결과는 항상 x다.

지배 법칙

x + 1 = 1
x · 0 = 0

OR에 1이 있으면 무조건 1
AND에 0이 있으면 무조건 0

멱등 법칙

x + x = x
x · x = x

같은 것을 여러 번 OR하거나 AND해도 결과는 그대로입니다.

보수 법칙

x + x' = 1
x · x' = 0

x 또는 x가 아님 = 항상 참
x이고 x가 아님 = 항상 거짓

이것은 아까 배운 항진명제, 모순명제와 연결됩니다.

이중 부정 법칙

(x')' = x

아닌 것의 아니다 = 원래 것

비가 오지 않는 것이 아니다 = 비가 옵니다

교환 법칙

x + y = y + x
xy = yx

순서를 바꿔도 결과가 같습니다.

결합 법칙

(x + y) + z = x + (y + z)
(xy)z = x(yz)

묶는 위치가 달라도 결과가 같습니다.

분배 법칙

x(y + z) = xy + xz

이것은 일반 수학과 비슷합니다.

부울대수에서는 이것도 성립합니다.

x + yz = (x + y)(x + z)

두 번째 식은 처음 보면 낯설지만 부울대수에서는 중요합니다.

흡수 법칙

x + xy = x
x(x + y) = x

이것은 시험에서 간소화 문제에 자주 쓰입니다.

x + xy

여기서 x가 이미 참이면 전체가 참입니다. x가 거짓이면 xy도 거짓입니다.

x + xy = x

입니다.

드모르간 법칙

이번 절의 핵심 중 하나입니다.

드모르간 법칙은 NOT이 괄호 전체에 걸릴 때 쓰는 법칙입니다.

반드시 정리해 둡니다.

(xy)' = x' + y'

(x + y)' = x'y'

전체 부정을 풀 때 AND와 OR가 서로 바뀝니다.
각 항은 부정됩니다.

즉,

AND의 부정 = OR로 바뀌고 각각 부정
OR의 부정 = AND로 바뀌고 각각 부정

예시 1

(AB)' = A' + B'

예시 2

(A + B)' = A'B'

예시 3

(A + BC)'

전체를 부정하므로 먼저 OR가 AND로 바뀝니다.

(A + BC)' = A' · (BC)'

그리고 (BC)'에도 드모르간을 적용합니다.

(BC)' = B' + C'

(A + BC)' = A'(B' + C')

논리회로 예시문제에서도 부울대수 등식이 맞는지 판단하는 유형이 나옵니다. 이런 문제에서 드모르간 법칙과 흡수 법칙이 자주 쓰입니다.

드모르간 법칙을 외운 뒤에는 식 간소화와 NAND/NOR 회로 구현까지 한 흐름으로 연결해 봅니다.

논리게이트와 회로

논리게이트란?

이제 논리회로로 넘어갑니다.

논리게이트는 0 또는 1을 입력받아서 0 또는 1을 출력하는 기본 회로입니다.

예를 들어 AND 게이트는 입력이 두 개입니다.

A, B 입력
Y 출력

A와 B가 둘 다 1일 때만 Y가 1입니다.

A AND B = Y

논리게이트는 컴퓨터 내부 회로의 기본 재료입니다.

기본 논리게이트 6개

시험에서 가장 중요한 논리게이트는 다음 6개입니다.

논리게이트 진리표

A, B 두 입력에 대한 주요 게이트 결과를 한 번에 살펴보겠습니다.

이 표는 자주 봐야 합니다.

특히 NAND와 NOR는 헷갈리기 쉽습니다.

NAND = AND 결과를 뒤집음
NOR = OR 결과를 뒤집음

NAND와 NOR가 중요한 이유

NAND와 NOR는 특별합니다.

왜냐하면 NAND만으로도 모든 회로를 만들 수 있고, NOR만으로도 모든 회로를 만들 수 있기 때문입니다.

그래서 NAND와 NOR를 범용 게이트라고 부릅니다.

예를 들어 NOT을 NAND로 만들 수 있습니다.

A NAND A = (AA)' = A'

즉, 입력을 둘 다 A로 넣으면 NOT이 됩니다.

NOR도 마찬가지입니다.

A NOR A = (A + A)' = A'

논리식에서 회로로 바꾸기

논리식이 주어지면 회로로 바꿀 수 있어야 합니다.

Y = AB + C

이 식을 읽어 보겠습니다.

AB

는 A와 B를 AND한 것입니다.

AB + C

는 AND 결과와 C를 OR한 것입니다.

A, B → AND → 결과
결과, C → OR → Y

즉,

Y = AB + C

는 AND 게이트 하나와 OR 게이트 하나로 만들 수 있습니다.

회로에서 논리식으로 바꾸기

반대로 회로를 보고 논리식으로 바꾸는 것도 중요합니다.

예를 들어 어떤 회로가 이렇게 되어 있다고 가정하겠습니다.

A와 B가 AND로 들어감 → 결과 X
X와 C가 OR로 들어감 → 출력 Y

X = AB
Y = X + C

Y = AB + C

입니다.

시험에서는 회로 그림을 주고 식을 묻거나, 식을 주고 간소화된 회로를 고르게 합니다.

논리식 간소화

논리식 간소화란?

논리식 간소화는 복잡한 식을 더 짧게 만드는 것입니다.

왜 간소화가 중요할까요?

식이 짧아짐
→ 필요한 게이트 수가 줄어듦
→ 회로가 단순해짐
→ 비용과 오류 가능성이 줄어듦

Y = A + AB

A + AB = A

Y = A

복잡한 회로가 단순한 회로로 바뀝니다.

간소화 예제 1

다음 식을 간소화해 보겠습니다.

Y = A + AB

x + xy = x

여기서 x는 A, y는 B다.

A + AB = A

Y = A

간소화 예제 2

다음 식을 간소화해 보겠습니다.

Y = A(A + B)

x(x + y) = x

A(A + B) = A

Y = A

간소화 예제 3

다음 식을 간소화해 보겠습니다.

Y = AB + AB'

먼저 공통인 A를 묶습니다.

Y = A(B + B')

B + B' = 1

Y = A · 1

A · 1 = A

Y = A

간소화 예제 4

다음 식을 간소화해 보겠습니다.

Y = (A + B)(A + B')

(x + y)(x + z) = x + yz

x = A
y = B
z = B'

(A + B)(A + B') = A + BB'

BB' = 0

A + 0 = A

Y = A

시험형 연결 포인트

연산 우선순위

논리식에서 우선순위도 중요합니다.

보통 다음 순서로 계산합니다.

1순위: 괄호
2순위: NOT
3순위: AND
4순위: OR

A + BC'

는 이렇게 해석합니다.

A + (B · C')

즉, C를 먼저 NOT하고, B와 AND하고, 마지막에 A와 OR합니다.

절대 이렇게 보면 안 됩니다.

(A + B)C'

괄호가 없으면 AND가 OR보다 먼저입니다.

명제논리와 C언어 조건문 연결

이번 절에서 배운 내용은 C프로그래밍과도 연결됩니다.

C언어에서 조건문은 참/거짓을 판단합니다.

if (score >= 60) {
    printf("pass");
}

score >= 60

은 명제처럼 참 또는 거짓이 됩니다.

또 C언어에는 논리연산자가 있습니다.

if (id_ok && pw_ok) {
    printf("login");
}

id_ok ∧ pw_ok

와 같습니다.

즉, 아이디도 맞고 비밀번호도 맞아야 로그인됩니다.

C프로그래밍 범위에도 관계 연산자, 논리 연산자, 비트 연산자, 연산자 우선순위가 포함되어 있습니다.

자주 혼동되는 출제 포인트

혼동 포인트 1. OR는 둘 다 참이어도 참입니다

논리학의 OR는 보통 이렇게 동작합니다.

1 OR 1 = 1

“둘 중 하나만”이라고 생각하면 XOR와 헷갈리기 쉽습니다.

혼동 포인트 2. p → q는 p가 참이고 q가 거짓일 때만 거짓입니다

조건문 진리표에서 가장 중요합니다.

p → q

p = 1, q = 0

뿐입니다.

혼동 포인트 3. 부울대수의 +는 일반 덧셈이 아닙니다

1 + 1 = 1

입니다.

왜냐하면 +는 OR이기 때문입니다.

혼동 포인트 4. 드모르간에서 AND와 OR가 바뀝니다

(AB)' = A' + B'

(A + B)' = A'B'

부정만 붙이고 연산자를 그대로 두면 틀립니다.

(AB)' = A'B'

(AB)' = A' + B'

혼동 포인트 5. NAND와 NOR는 결과를 뒤집은 것입니다

NAND = AND 후 NOT
NOR = OR 후 NOT

A NAND B = (AB)'
A NOR B = (A + B)'

이번 절의 핵심 정리

이번 절에서 최소한 이것들은 정리해야 합니다.

논리연산

부울대수 법칙

논리게이트

논리 문제는 진리표, 부울대수, 게이트 그림이 서로 다른 표현일 뿐이라는 점이 중요합니다. 문제에서 식을 주면 게이트로, 게이트를 주면 식과 진리표로 바꿔 보는 연습을 하면 출제 방향이 바뀌어도 흔들리지 않습니다.

이번 절의 핵심 한 문장

이번 절의 핵심을 한 문장으로 정리하면 다음과 같습니다.

명제논리는 참과 거짓을 다루고, 부울대수는 그것을 0과 1의 식으로 바꾸며, 논리게이트는 그 식을 실제 회로로 구현합니다.

참/거짓 → 1/0 → AND/OR/NOT 회로

확인 문제

문제 1

다음 중 명제인 것은?

① 밥 먹어라 ② x는 5보다 큽니다 ③ 2는 짝수입니다 ④ 이 영화는 재미있습니다

문제 2

p ∧ q가 참이 되는 경우는?

① p만 참일 때 ② q만 참일 때 ③ p와 q가 둘 다 참일 때 ④ p와 q가 둘 다 거짓일 때

문제 3

p ∨ q에서 p = 0, q = 1이면 결과는?

① 0 ② 1 ③ p ④ q'

문제 4

p → q가 거짓이 되는 경우는?

① p = 0, q = 0 ② p = 0, q = 1 ③ p = 1, q = 0 ④ p = 1, q = 1

문제 5

다음 중 모순명제는?

① p ∨ ¬p ② p ∧ ¬p ③ p → p ④ p ↔ p

문제 6

드모르간 법칙에 의해 (A + B)'는 무엇인가?

① A' + B' ② A'B' ③ AB ④ A + B

문제 7

AB + AB'를 간소화하면?

① A ② B ③ A + B ④ AB

문제 8

NAND 게이트의 식은?

① AB ② A + B ③ (AB)' ④ (A + B)'

정답과 해설은 절별 확인문제 정답해설에서 확인합니다.

다음 1장 4절은 조합논리회로와 순서논리회로입니다. 이번 절에서 배운 AND, OR, NOT 같은 게이트들이 모여서 가산기, 디코더, 멀티플렉서, 플립플롭, 레지스터 같은 실제 회로가 됩니다.