논리 연산

01 문서ㄴ/ㄴ 수학과 관련된 것ㅇ/ㄹ 다룹니다. 01 문서ㄴ/ㄴ 수학과 관련된 무언7ㅏ0ㅔ 대해서 다루ㄴ/ㄴ 문서입니다. ㄱ/ㅂ식 수학일 수도 전공 수학일 수도 있고, 혹ㅇ/ㄴ 수학과 관련된 역사속의 인물일지도 모ㄹ/ㅂ니다. 01 문서ㄹ/ㄹ 읽다7ㅏ 수학뽕0ㅔ 빠져버려도 본 위키ㄴ/ㄴ 책임지지 않ㅅ/ㅂ니다. 1 + 1 = 귀요미>_<

이 문서는 이해하기 어려운 대상을 다룹니다. 이 문서는 일반적인 뇌를 가지고도 이해하기 어려운 대상에 대해 다룹니다. 두뇌를 풀가동해도 이해하기 어려울 것입니다. 나 아는사람 강다니엘 닮은 이모가 다시보게되는게 다시 그때처럼 안닮게 엄마보면 느껴지는걸수도 있는거임?

개요

19세기 중반에 조지 불이라는 사람이 고안한 논리 명제끼리 계산하는 것으로, 불 대수라고도 부른다.

1+1=1이 될 수 있는 기적의 계산법이다. 정확히 말하자면 우리가 아는 덧셈 기호의 용법과 다른 '논리합'이라는 것인데, 후술한다.

자격증 취득할 때 자주 접하게 되는 것으로, 전기 회로부터 코딩까지 다양한 분야에서 반드시 알아야 하는 것이다.

당장 이 위키에서도 #if 문법이나 #expr 문법의 조건식을 작성하려면 불 대수 개념이 필수다.

다들 중학교 수학에서 배웠던 집합의 개념 알지? 그것과 매우 비슷하다.

참과 거짓

논리 명제(불 대수)는 이진법을 사용한다. 즉 0과 1밖에 없다. 이를 '원소'라 부른다.

중딩 때는 명제의 참과 거짓을 p와 ~p라고 배웠을 것이다.

그러나 불 대수에서는 수학식으로 쓸 때 참을 1, 거짓을 0이라 부른다.

불 대수의 원소
뜻	숫자	알파벳
거짓(False)	0	F
참(True)	1	T

기초 연산

그렇다면 이번에는 불 대수들이 무슨 연산 기호로 계산되는지 살펴보자.

가장 기초적인 것은

• 부정(¬, NOT)
• 논리곱(∧, AND)
• 논리합(∨, OR)

이 셋이다.

미리 설명하자면 부정은 너네가 아는 '~이/가 아니다'와 같으며, 논리곱 AND는 'A이면서 동시에 B', 논리합 OR는 'A이거나 B'이다.

부정(¬, NOT)

중딩 때 명제 앞에 ~(물결표)를 붙이면서 표현했던 것. 집합에서는 오른쪽 위에 작게 C를 붙여 '여집합'이라고 불렀을 것이다.

말 그대로 명제를 부정하는 식이다. 논리 연산식에서는 ¬를 앞에 붙여 표현할 것이다.

논리가 하나만 있어도 계산이 가능하다. 이를 '단항 연산'이라 부른다.

A라는 참인 명제가 '문재앙은 애미가 없다'라면 A에 부정 연산을 한 ¬A는 거짓인 명제, '문재앙은 애미가 있다'가 되는 것이다.

반대로 거짓인 명제(이재명은 유능하다)라면 부정 연산을 했을 때 참인 명제(이재명은 무능하다)가 나온다.

NOT(¬) 연산의 결과
A	¬	¬A
0		1
1		0

숫자로 된 불 대수(0, 1)에 부정 연산을 해서 뒤집힌 숫자(1, 0)를 '보수'라고 부르는데, 이런 연산을 하는 계산기를 '보수기'라고 부른다.

그리고 이진수의 모든 자릿수(비트)에 부정 연산을 해서 나온 수를 '1의 보수', 그 값에 1을 더한 것을 '2의 보수'라고 부른다. 2의 보수는 컴퓨터가 숫자를 음수로 만들 때 활용하는 방식이다.

그런데 이건 아직 이 단계에서 설명하기엔 복잡하므로 생략한다. 코딩에 관심이 많다면 정보처리 관련 자격증 책을 사서 배울 수 있다.

논리곱(∧, AND)

여기서부터는 논리가 2개 필요하다. 항이 2개이므로 '이항 연산'이라고 부른다.

중딩 때 집합을 배울 때 교집합이라는 것을 배웠을 것이다. 그것과 같은 기능을 한다. A라는 집합에 포함되면서 동시에 B라는 집합에도 포함되는 것을 A∩B라고 쓰지 않았던가?

마찬가지다. 논리곱은 A이면서 동시에 B, 즉 둘 다 참일 때에만 참이 되는 연산을 말한다. 기호는 ∧라고 쓴다. 즉 A와 B 둘 다 참인 것을 A∧B라고 쓴다.

하나라도 거짓이면 논리곱의 값은 거짓이다.

A·B 또는 AB라고 표기하기도 한다.

코딩에서는 & 또는 &&라고 쓴다. C언어나 자바 등은 &를 비트 연산자로, &&를 논리 연산자로 쓰는데, 이 문서는 코딩을 가르치는 문서는 아니므로 비트 연산에 대해서는 (논리 대신) '이진수의 자릿수(비트)를 가지고 계산하는 것이라고 간단하게만 설명하고 넘어가도록 하자.

AND(∧) 연산의 결과
A	B	∧	A∧B
0	0		0
0	1		0
1	0		0
1	1		1

논리합(∨, OR)

반대로 논리합은 집합의 합집합 개념과 같다. A라는 집합에만 포함되어도 되고, B라는 집합에만 포함되어도 된다. 이를 A와 B를 합친 집합이라 하여 A∪B라고 썼을 것이다.

논리합은 A가 참이거나 B가 참이거나 둘 중 하나만 성립해도 참이 되는 것이다. 물론 A이면서 동시에 B인 경우(논리곱)에도 참이 된다. 다만 둘 다 거짓인 경우에는 거짓이 된다.

+ 기호를 써서 A+B라고 하기도 한다. 만약 A와 B 둘 다 참이라면? 숫자로 바꿨을 때 1+1이라고 쓰며 답은 1이 된다. 즉 논리합 연산에서 1+1=1인 것이다.

코딩에서는 | 또는 ||라고 쓴다. 마찬가지로 C언어와 자바에서는 |는 비트 연산자, ||가 논리 연산자이다.

OR(∨) 연산의 결과
A	B	∨	A∨B
0	0		0
0	1		1
1	0		1
1	1		1

더 복잡한 연산

여기서부터는 앞의 세 연산을 두 번 이상 적용하거나 A와 B 중 한 쪽이 다른 한 쪽에 포함되어 있는 등 복잡한 상황을 알아볼 것이다.

부정 논리곱(⊼, NAND)

논리곱 연산(∧)을 한 다음 그 값을 부정(¬)한 것이다. 집합으로 치면 교집합의 여집합 (A∩B)^C으로, 교집합 부분을 제외한 나머지 모든 부분이 참인 것과 같다.

논리곱은 둘 다 참일 때만 참을 반환하는 연산이었다. 그렇다면 부정 논리곱은 당연히 둘 다 참일 때 거짓을 반환하고 나머지는 모두 참을 반환하게 된다.

NAND(⊼) 연산의 결과
A	B	⊼	A⊼B
0	0		1
0	1		1
1	0		1
1	1		0

부정 논리합(⊽, NOR)

이쯤 되면 이건 뭔지 예상이 갈 것이다. 그렇다. 논리합(∨)의 결과를 부정(¬)하는 연산이다.

집합으로 치면 합집합의 여집합 (A∪B)^C과 같다. A도 거짓이고 B도 거짓이어야만 참이 되는 연산이다. 둘 중 하나라도 참일 경우 거짓이 된다.

NOR(⊽) 연산의 결과
A	B	⊽	A⊽B
0	0		1
0	1		0
1	0		0
1	1		0

배타적 논리합(⊻, XOR)

아마 이번 것은 예상이 잘 안 갈 것이다. 부정은 앞에 N이 붙었는데? X는 뭐지? 부정 연산을 하지는 않은 거 같은데?

eXclusive OR의 약자이다. 앞서 말한 것처럼 부정 연산과는 관련없으며 오히려 논리합의 값에서 논리곱의 값을 뺀 것이다. 그런데 이렇게 설명하면 이해가 잘 안 갈 것이다.

간단히 말하자면 A와 B의 참/거짓 여부가 서로 다를 때, 즉 A와 B 둘 중 하나만 참이어야 참이 되는 연산이다. 둘 다 참이면 거짓이 되고, 둘 다 거짓이어도 거짓이 된다.

맨 처음 설명을 풀어서 얘기하면 논리합(둘 중 하나만 참이거나 둘 다 참이면 참)에서 논리곱(둘 다 참이어야만 참)을 빼서 '둘 중 하나만 참이어야만 참'이 된 것이다.

식에서는 ⊕라는 기호를 쓴다.

그냥 간단하게 표로 확인하자.

XOR(⊻) 연산의 결과
A	B	⊻	A⊻B
0	0		0
0	1		1
1	0		1
1	1		0

코딩에서는 ^라는 기호로 배타적 논리합을 사용한다. 가끔 코딩을 처음 배우는 사람들이 제곱을 표현하려고 수식에 2^4와 같이 적는데, 이러면 16이 나오지 않는다. 이진법으로 풀어서 (010)^(100)이 되고, 각 비트끼리 배타적 논리합을 하여 이진수 110 -> 십진수 6이 나와버린다.

C언어에서 제곱을 쓰고 싶으면 #include <math.h>로 수학 함수들을 불러온 다음 pow(밑, 지수)와 같이 사용하자.

동치(≡, EQV)

배타적 논리합(⊻)의 값에 부정 연산(¬)을 한 것이다. 즉 XOR과 반대로 둘 다 참이거나 둘 다 거짓이어야 참이 되고, 둘 중 하나만 참이면(둘의 참/거짓 여부가 다르면) 거짓이 된다.

그런데 쉽게 얘기하면 A와 B가 같냐는 것이다. 같으면 참, 다르면 거짓. 코딩에서는 ==라는 기호로 나타낸다.

EQV(≡) 연산의 결과
A	B	≡	A≡B
0	0		1
0	1		0
1	0		0
1	1		1

함의(→, IMPLY)

이건 좀 더 복잡하다. A가 참이고 B가 거짓일 때만 거짓을 반환하는 연산이다.

원리를 설명하자면, A가 B 안에 포함되어 있는 것이다. A라는 명제가 '노무현은 국정원 지하에 살아있다'이고 B라는 명제가 '노무현은 살아있다'라고 가정해보자. A는 B라는 명제에 포함된 것이다.

• 둘 다 참일 경우 - A가 참이라면 B는 당연히 참이 된다.
• A는 참, B는 거짓일 경우 - 노무현이 국정원 지하에 살아있는데 노무현이 죽었다는 것이 논리적으로 말이 되는가? 당연히 거짓.
• A는 거짓, B는 참일 경우 - 노무현이 살아있는 것은 사실이지만, 그 장소가 국정원 지하는 아니라는 것이다. 지옥에 있는 노무현 나와라처럼 어버이연합 틀딱들이 가지고 있는 관짝에 살아있는 것일 수도 있다. 따라서 참.
• 둘 다 거짓일 경우 - B가 거짓이라면 A는 당연히 거짓이 된다. 이때 이 논리 연산 값을 '거짓'이라고 지칭하는 오류를 범하지 않도록 하자. 이는 논리적으로 문제가 없으므로 참이다.

이 연산은 교환법칙이 성립하지 않는다. 종속관계가 명확해 위치를 바꾸면 뜻이 완전히 달라지기 때문이다.

IMPLY(→) 연산의 결과
A	B	→	A→B
0	0		1
0	1		1
1	0		0
1	1		1

역(←, CONV)

CONVerse.

함의의 순서를 반대로 뒤집어놓은 것이다. 즉 A←B는 B→A와 같으며 B가 A 안에 포함된 것이다. 더 설명할 필요는 없다.

CONV(←) 연산의 결과
A	B	←	A←B
0	0		1
0	1		0
1	0		1
1	1		1

비함의(↛, NIMPLY)

함의 연산(→)의 값을 부정(¬)한 것이다. 더 설명할 필요는 없다.

NIMPLY(↛) 연산의 결과
A	B	↛	A↛B
0	0		0
0	1		0
1	0		1
1	1		0

역비함의(↚)

역 연산(←)의 값을 부정(¬)한 것이다. 더 설명할 필요는 없다.

역비함의(↚) 연산의 결과
A	B	↚	A↚B
0	0		0
0	1		1
1	0		0
1	1		0

요약

이항 연산 결과를 한 표로 정리하면 다음과 같다.

논리 이항 연산의 결과
연산 종류	(A,B)
	(0,0)	(0,1)	(1,0)	(1,1)
논리곱(∧, AND)	0	0	0	1
논리합(∨, OR)	0	1	1	1
부정 논리곱(⊼, NAND)	1	1	1	0
부정 논리합(⊽, NOR)	1	0	0	0
배타적 논리합(⊻, XOR)	0	1	1	0
동치(≡, EQV)	1	0	0	1
함의(→, IMPLY)	1	1	0	1
역(←, CONV)	1	0	1	1
비함의(↛, NIMPLY)	0	0	1	0
역비함의(↚)	0	1	0	0

성질

논리 연산에는 특징이 있다.

항등원

불 대수를 특정 논리값으로 논리곱하거나 논리합하면 값이 변하지 않고 그대로 나오게 되는데 이 논리값을 항등원이라 한다.

논리곱의 항등원 1

이를테면 A와 1을 논리곱하면 A·1인데, 1은 집합으로 비유하면 전체집합과 같다. A라는 집합과 전체집합의 교집합은 A 스스로가 되므로 A·1=A이다. 교환법칙을 적용해 1·A도 A가 된다.

따라서 논리곱의 항등원은 1이다.

논리합의 항등원 0

A와 0을 논리합하면 A+0인데, 아무것도 합해지지 않았으므로 그 값은 A 스스로가 되고 식으로 쓰면 A+0=A이다. 교환법칙을 적용해 0+A=A가 된다.

따라서 논리합의 항등원은 0이다.

연산 우선 순위

NOT -> AND -> OR 순서로 한다.

단항 연산인 부정 연산을 가장 먼저 한다. 그 다음 논리곱을 계산하고 그 다음 논리합을 계산한다. 음수/양수 부호가 먼저 계산되고 그 다음 곱셈, 덧셈 순서대로 하는 수학의 연산처럼 생각하면 편하다.

쌍대성 원리

논리곱(·)과 논리합(+)을 서로 뒤바꾸거나 0과 1을 서로 뒤바꿔도 등식은 그대로 성립하는 원리이다. 다만 변수의 위치는 바꾸지 않으며 연산 순서도 그대로이다. 곱을 합으로 바꿀 경우 합에 괄호를 쳐서 그것이 곱일 때와 마찬가지로 우선적으로 연산되게 해주어야 한다.

이를테면 A·(B+C)는 분배 법칙에 따라 A·B+A·C가 되는데, 논리곱과 논리합을 뒤바꾼 A+(B·C)는 (A+B)·(A+C)가 된다.

법칙

교환법칙

논리곱, 논리합, 배타적 논리곱(⊕)에 적용된다.

• A + B = B + A
• A · B = B · A
• A ⊕ B = B ⊕ A

결합법칙

논리곱, 논리합, 배타적 논리곱에 적용되며 부정 연산과 관련된 연산들에는 적용되지 않는다.

• (A + B) + C = A + (B + C)
• (A · B) · C = A · (B · C)
• (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)

분배법칙

논리곱, 논리합, 배타적 논리곱에 적용된다.

• A · (B + C) = A · B + A · C
• A + B · C = (A + B) · (A + C)
• A · (B ⊕ C) = A · B ⊕ A · C

멱등법칙

같은 불 대수를 논리합하거나 논리곱하면 같은 값이 나오는 것이다.

• A + A = A
• A · A = A

흡수법칙

• A + A · B = A
• A · (A + B) = A

다른 불 대수와의 논리곱/논리합을 자기 자신과 각각 논리합/논리곱하면 자기 자신이 나오는 것이다.

첫 번째 식의 증명은 다음과 같다.

  A + A · B
= (A + A) · (A + B) -> 분배법칙 적용
= A · (A + B) -> 멱등법칙 적용
= (A + 0) · (A + B) -> 논리합의 항등원 0
= A + (0 · B) -> 결합법칙
= A + 0
= A

두 번째 식은 쌍대성 원리에 따라 참이다.

이중 부정

부정 연산(')을 두 번 하면 자기 자신이 되는 것이다.

• (A')' = A

드모르간 법칙

논리합의 부정은 부정의 논리곱과 같고, 논리곱의 부정은 부정의 논리합과 같다는 것이다.

• (A + B)' = A' · B'
• (A · B)' = A' + B'

긍정+부정=1 / 긍정·부정=0

• A + A' = 1
• A · A' = 0

자신과 자신의 부정을 합하면 1이 된다. 곱하면 0이 된다.

A+1=1 / A·0=0

1을 논리합하면 A가 무엇이든 간에 값이 1이 되며, 0을 논리곱하면 교집합이 없으므로 0이 된다.

합의 법칙

이건 좀 복잡하다.

• AB + BC + CA' = AB + BC + CA' = AB + CA'
• (A + B)(B + C)(C + A') = (A + B)(B + C)(C + A') = (A + B)(C + A')

위 식에 나온 것처럼 변수가 3개인 식에서 서로 다른 항에 한 변수의 긍정(A)과 부정(A')이 다 있으면 나머지 두 변수로만 이루어진 항(BC 또는 B+C)은 소거할 수 있다.

일단 첫 번째 식의 BC를 풀어보자.

  BC
= 1 · BC
= (A + A') · BC
= ABC + A'BC
= ABC + CA'B

그리고 이를 첫 번째 식의 BC 자리에 대신 넣는다.

  AB + BC + CA'
= AB + ABC + CA'B + CA'
= AB(1 + C) + CA'(B + 1)
= AB·1 + CA'·1
= AB + CA'

Q.E.D. 그리고 쌍대성 원리에 따라 두 번째 식도 비슷한 원리로 풀 수 있으니 생략한다.

기타

• (A ⊕ B)' = A ⊕ B' = A' ⊕ B
• A' ⊕ B' = A ⊕ B
• A + A' · B = A + B
• A · (A' + B) = A · B