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

이번 절에서는 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')

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

논리게이트와 회로

논리게이트란?

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

논리게이트는 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 같은 게이트들이 모여서 가산기, 디코더, 멀티플렉서, 플립플롭, 레지스터 같은 실제 회로가 됩니다.