최근 수정 시각 : 2024-04-06 23:00:18

논리 연산

논리 연산 관련 틀
[ 펼치기 · 접기 ]
논리학
Logics
{{{#!wiki style="margin: -0px -10px -5px; min-height: 28px"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -6px -1px -11px;"
<colbgcolor=#2ab5b5> 형식 논리 명제 논리( 논리 연산 · 삼단논법( 정언삼단논법) · 순환 논법) · 공리 · 진리치 · 술어 논리 · 논증( 논증의 재구성) · 모순 · 역설 · 논리적 오류( 논리적 오류/형식적 오류)
<colcolor=#000,#fff> 비표준 논리 직관 논리 · 양상논리 · 초일관 논리 · 다치논리( 퍼지논리) · 선형논리 · 비단조 논리
메타 논리 집합론 · 완전성 정리 · 불완전성 정리
비형식 논리 딜레마( 흑백논리)
비형식적 오류 귀납적 오류 · 심리적 오류 · 언어적 오류 · 자료적 오류 · 양비론 · 진영논리 · 편견 및 고정관념 · 궤변 · 거짓 등가성
분야 수리철학 · 수리논리학
철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 · 수리논리학 둘러보기
}}}}}}}}} ||

수학기초론
Foundations of Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px"
다루는 대상과 주요 토픽
수리논리학 논리 · 논증{ 귀납논증 · 연역논증 · 귀추 · 유추} · 공리 및 공준 · 증명{ 자동정리증명 · 귀류법 · 수학적 귀납법 · 반증 · 더블 카운팅 · PWW} · 논리함수 · 논리 연산 · 잘 정의됨 · 조건문( 조각적 정의) · 명제 논리( 명제 · 아이버슨 괄호 · · · 대우) · 양상논리 · 술어 논리( 존재성과 유일성) · 형식문법 · 유형 이론 · 모형 이론
집합론 집합( 원소 · 공집합 · 집합족 · 곱집합 · 멱집합) · 관계( 동치관계 · 순서 관계) · 순서쌍( 튜플) · 서수( 하세 다이어그램 · 큰 가산서수) · 수 체계 · ZFC( 선택공리) · 기수( 초한기수) · 절대적 무한 · 모임
범주론 범주 · 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성
계산가능성 이론 계산 · 오토마타 · 튜링 기계 · 바쁜 비버 · 정지 문제 · 재귀함수
정리
드모르간 법칙 · 대각선 논법 · 러셀의 역설 · 거짓말쟁이의 역설 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 집합-부분합 정리 · 퍼스의 항진명제 · 굿스타인 정리 · 완전성 정리 · 불완전성 정리( 괴델 부호화) · 힐베르트의 호텔 · 연속체 가설 · 퍼지 논리
기타
예비사항( 약어 및 기호) · 추상화 · 벤 다이어그램 · 수학철학
틀:논리학 · 틀:이산수학 · 틀:이론 컴퓨터 과학 · 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 }}}}}}}}}



''' 이론 컴퓨터 과학
{{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"'''
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px"
<colbgcolor=#aa3366> 이론
기본 대상 수학기초론{ 수리논리학( 논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학( 그래프 이론) · 수치해석학 · 확률론 통계학 · 선형대수학
다루는 대상과 주요 토픽
계산 가능성 이론 재귀함수 · 튜링 기계 · 람다 대수 · 처치-튜링 명제 · 바쁜 비버
오토마타 이론 FSM · 푸시다운 · 튜링 머신( 폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어
계산 복잡도 이론 점근 표기법 · 튜링 기계^ 고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임( 그리디 알고리즘, 동적 계획법)
정보이론 데이터 압축( 무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학
프로그래밍 언어이론 프로그래밍 언어( 함수형 언어 · 객체 지향 프로그래밍) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론
주요 알고리즘 및 자료구조
기초 정렬 알고리즘 · 순서도 · 탐색 알고리즘
추상적 자료형 및 구현 배열^ 벡터^ · 리스트^ 연결 리스트^ · 셋(set)^ 레드-블랙 트리, B-트리^ · 우선순위 큐^, 피보나치 힙^
수학적 최적화 조합 최적화 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습
볼록 최적화 내부점 방법 · 경사하강법
선형계획법 심플렉스법
계산 수론 및 암호학 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시( MD5 · 암호화폐 · 사전 공격( 레인보우 테이블) · SHA) · 양자 암호
대칭키 암호화 방식 블록 암호 알고리즘( AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4)
공개키 암호화 방식 공개키 암호 알고리즘( 타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9)
계산기하학 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN
그래프 이론 탐색^ BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론
정리
정지 문제 대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결
틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 }}}}}}}}}


'''[[전기전자공학과|전기·전자공학
{{{#!wiki style="font-family: Times New Roman, serif; font-style: Italic; display: inline;"
]]'''
{{{#!wiki style="margin:0 -10px -5px; min-height:calc(1.5em + 5px); word-break:keep-all"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin:-5px -1px -11px; letter-spacing:-0.05em"
<colbgcolor=#009><colcolor=white>학문 기반 학문
물리학 ( 전자기학 ( 회로이론 · 전자 회로 · 논리 회로) · 양자역학 · 물리화학 · 열역학 · 응집물질물리학) · 화학
연관 학문
수학 ( 공업수학 · 수치해석학 · 위상수학 · 미분방정식 · 대수학 ( 환론 · 표현론) · 선형대수학 · 이론 컴퓨터 과학 · 컴퓨터 공학 ( 프로그래밍 언어 ( HDL · VHDL · C · C++ · Java · 파이썬 · 베릴로그)) · 재료공학 · 제어 이론
공식 · 법칙 전자기 유도 · 가우스 법칙 · 비오-사바르 법칙 · 무어의 법칙 · 키르히호프의 법칙 · 맥스웰 방정식 · 로런츠 힘 · 앙페르 법칙 · 드모르간 법칙 · 페르미 준위 · 중첩의 원리
이론 · 연구 반도체 ( P형 반도체 · N형 반도체) · 디스플레이 · 논리 회로 ( 보수기 · 가산기 · 플립플롭 · 논리 연산) · 전자 회로 · RLC 회로 · 역률 · DSP · 히스테리시스 곡선 · 휘트스톤 브릿지 · 임베디드 시스템
용어 클럭 · ASIC · CPU 관련 ( BGA · 마이크로아키텍처 · GPS · C-DRX · 소켓) · 전계강도계 · 축전기 · CMCI · 전송선 · 양공 · 도핑(반도체) · 이미터 · 컬렉터 · 베이스
전기 · 전자
관련 정보
제품
스마트폰 · CPU · GPU ( 그래픽 카드) · ROM · RAM · SSD · HDD · MPU · CCD · eMMC · USB · UFS · LCD · LED · OLED · AMOLED · IoT · 와이파이 · 스마트 홈 · 마그네트론 · 마이크 · 스피커 · 배터리
소자
집적 회로 · 다이오드 · 진공관 · 트랜지스터 ( BJT · FET · JFET · MOSFET · T-FT) · CMOS · IGBT · 저항기 · 태양전지 · 연산 증폭기 · 사이리스터 · GTO · 레지스터 · 펠티어 소자 · 벅컨버터
자격증
전기 계열 기능사
전기기능사 · 철도전기신호기능사
기사
전기기사 · 전기산업기사 · 전기공사기사 · 전기공사산업기사 · 전기철도기사 · 전기철도산업기사 · 철도신호기사 · 철도신호산업기사
기능장 및 기술사
전기기능장 · 건축전기설비기술사 · 발송배전기술사 · 전기응용기술사 · 전기안전기술사 · 철도신호기술사 · 전기철도기술사
전자 계열 기능사
전자기기기능사 · 전자계산기기능사 · 전자캐드기능사
기사
전자기사 · 전자산업기사 · 전자계산기기사 · 전자계산기제어산업기사
기능장 및 기술사
전자기기기능장 · 전자응용기술사
기타 기능사
신재생에너지발전설비기능사(태양광)
기사
소방설비기사 · 신재생에너지발전설비기사(태양광) · 로봇소프트웨어개발기사 · 로봇하드웨어개발기사 · 로봇기구개발기사
}}}}}}}}}


||<tablealign=center><tablewidth=100%><tablebordercolor=#0066DC><tablebgcolor=#fff,#191919> ||
{{{#!wiki style="margin:0 -10px -5px"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin:-6px -1px -11px"
<colbgcolor=#0066DC><colcolor=white>기반 학문 수학( 해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 미분방정식 · 대수학( 환론 · 범주론) · 정수론) · 이론 컴퓨터 과학 · 암호학 · 전자공학 · 언어학( 형태론 · 통사론 · 의미론 · 화용론 · 음운론) · 인지과학
SoC · CPU · GPU( 그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품
기술 기계어 · 어셈블리어 · C/ C++ · C# · Java · Python · BIOS · 절차적 프로그래밍 · 객체 지향 프로그래밍 · 해킹 · ROT13 · 일회용 비밀번호 · 사물인터넷 · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · NERF · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시( SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화
연구

기타
논리 회로( 보수기 · 가산기 · 논리 연산 · 불 대수 · 플립플롭) · 정보이론 · 임베디드 시스템 · 운영 체제 · 데이터베이스 · 프로그래밍 언어{ 컴파일러( 어셈블러 · JIT) · 인터프리터 · 유형 이론 · 파싱 · 링커} · 메타데이터 · 기계학습 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩( 유니코드 · MBCS) · 네트워크 · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 구조론 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도( 최적화) · 소프트웨어 개발 방법론 · 디자인 패턴 · 정보처리이론 · 재귀 이론 · 자연어 처리( 기계 번역 · 음성인식) }}}}}}}}}
1. 개요2. 논리 연산의 종류
2.1. 부정 (NOT; ¬)2.2. 논리곱 (AND; ∧)2.3. 논리합 (OR; ∨)2.4. 부정 논리곱 (NAND; ⊼)2.5. 부정 논리합 (NOR; ⊽)2.6. 배타적 논리합 (XOR; ⊻)2.7. 동치 (EQV; ≡)
3. 성질
3.1. 항등원(identity)3.2. 연산 우선 순위
4. 연산 법칙(law)
4.1. 교환법칙(commutatitve)4.2. 결합법칙(associative)4.3. 분배법칙(distributive)4.4. 동일법칙(idempotent)4.5. 흡수법칙(absorption)4.6. 이중부정 법칙(involution)4.7. 드모르간 법칙(de Morgan's)4.8. 합의 법칙(consensus)4.9. 그 밖의 연산 법칙
5. 관련 문서

1. 개요

/ logical operation

논리 연산(logical operation, logical connective)은 19세기 중반 영국의 수학자 조지 불(George Boole, 1815년 11월 2일 ~ 1864년 12월 8일)이 고안하고 형식화한 대수 체계를 의미한다. 고안자의 이름을 따 불 대수(Boolean algebra)라고도 한다.

수리논리학이나 컴퓨터과학에서는 두 개의 상태인 참(1, T, true)과 거짓(0, F, false)을 사용하는 연산을 불 연산(Boolean expression)이라 한다. 불 대수의 출현 이후로 논리학 기호논리학의 성향이 강해지기 시작한다.

프로그래밍에서는 조건에 의한 분기나 반복을 만드는 데 이용되고, 디지털 논리 회로를 배울 때 유용하게 사용된다. 디지털 회로의 신호는 0과 1로만 구성되어 있기 때문이다. 전자계통에선 논리 연산을 하는 소자를 게이트(gate)라고 하며 트랜지스터 여러 개를 조합해서 만들 수 있다.

이산수학에서는 속(lattice) 중 complementary lattice이며 distributive lattice인 lattice를 불 속(Boolean lattice)이라 하며 이를 대수(algebra)식으로 나타낸 것을 불 대수(Boolean algebra)라고 한다. 불 속의 원소 개수는 해당 원자(atom) 개수 [math(n)]에 대해 [math(2^n)]개이다. 즉, 불 속의 원소 개수는 2의 제곱수대로 올라간다고 보면 된다.

불 대수는 집합으로 해석할 수 있다. [math(A)], [math(B)], [math(C)] 등 문자를 전체집합 [math(U=\{0, 1\})]의 공집합이 아닌 진부분집합으로 생각할 때, 논리합(or)은 합집합으로, 논리곱(and)는 교집합으로, 부정(not)은 여집합으로 생각할 수 있다.[1][2]

집합 기호는 고안자의 이름을 따서 [math(\mathbb B)]로 표현한다.[3] 아래의 연산과 함께 을 이룬다.

상태값은 편의상 {0, 1} 을 사용하지만, 경우에 따라서는 {False, True} 또는 {F, T} 를 쓰기도 한다.
0 = False(F)
1 = True(T)

2. 논리 연산의 종류

시작하기 앞서, 처음 보는 연산의 경우 진리표(truth table)를 사용하면 비교적 단순한 연산의 결과는 직접 확인할 수 있다. 다만 변수의 개수가 늘어나면 확인해야 하는 값이 대폭 증가하기 때문에, 기초적인 이해를 돕는 이상의 활용은 어렵다. 아래의 진리표를 보자.

아래는 [math(A \text{ and } B)]를 나타낸 것으로서, [math(A)]와 [math(B)] 값이 모두 참이면 1(true)을 출력하고 둘 중 하나의 값이라도 거짓이면 0(false)를 출력한다.
[math(A)] [math(B)] [math(A\wedge B)] (AND)
0 0 0
0 1 0
1 0 0
1 1 1

2.1. 부정 (NOT; ¬)

말 그대로 부정(否定)이다. 즉, 참과 거짓을 뒤집는다. C언어의 영향을 받은 프로그래밍 언어에서는 일반적으로 !를 부정 연산자로 사용하며, 그 외에 [math(\sim A)]도 많은 프로그래밍 언어에서 사용되고[4], 필기나 서적 등에서는 [math(A')] [5]또는 [math(A)] 위에 ㅡ를 그려넣은 [math(\bar{A} )] 기호가 주로 쓰인다. 불 보수(Boolean complement)로도 불린다. 이 연산을 하는 회로는 따로 보수기(inverter)라는 이름으로 불린다.
[math(A)] [math(\neg \ A)]
0 1
1 0

2.2. 논리곱 (AND; ∧)

두 명제가 모두 참이어야 참값을 돌려준다. C언어의 영향을 받은 프로그래밍 언어에서는 일반적으로 &를 논리곱 연산자로 사용하며, 불 대수에서는 AND는 곱셈과 동치이다. 불 곱(Boolean multiplication) 혹은 논리곱이라 부른다. 아래의 연산결과를 보면 왜 곱셈과 동치인지 쉽게 알 수 있을 것이다. [math(AB)] 또는 [math(A\cdot B)][6]로도 표시한다.
[math(A)] [math(B)] [math(A \wedge B)]
0 0 0
0 1 0
1 0 0
1 1 1

2.3. 논리합 (OR; ∨)

두 명제 중 어느 한 명제만 참이어도 참값을 돌려준다. C언어의 영향을 받은 프로그래밍 언어에서는 일반적으로 |를 논리합 연산자로 사용한다. 불 대수에서는 OR는 덧셈과 동치여서, 논리합(Boolean addition)으로 부른다. 아래에서 보듯 [math(\boldsymbol{1 + 1 = 1})] 임을 주의해야 한다. [math(A+B)][7]로도 표시한다.
[math(A)] [math(B)] [math(A \vee B)]
0 0 0
0 1 1
1 0 1
1 1 1

2.4. 부정 논리곱 (NAND; ⊼)

Not AND. 논리곱의 결과값을 부정한 것이다. 즉, 두 명제가 모두 참이면 거짓값을 돌려주고 그 외에는 참값을 돌려준다. 참고로 NAND만을 통해 다른 논리 연산식을 모조리 구현할 수 있기 때문에[8] 현재 사용되는 플래시 메모리들은 대부분이 NAND 회로로 구성되어 있다.
[math(A)] [math(B)] [math(A \barwedge B)]
0 0 1
0 1 1
1 0 1
1 1 0

2.5. 부정 논리합 (NOR; ⊽)

Not OR. 논리합의 결과값을 부정한 것이다. 즉, 두 명제가 모두 거짓이면 참값을 돌려주고 그 외에는 거짓값을 돌려준다. NAND와 마찬가지로 NOR만으로 다른 논리 연산식을 모조리 구현할수 있기에 초기 플래시 메모리들은 대부분이 NOR 회로로 구성하였다. 근데 NAND 회로가 값이 싸다보니 이쪽은 자연스럽게 도태되었다.
[math(A)] [math(B)] [math(A~\overline{\vee}~B)]
0 0 1
0 1 0
1 0 0
1 1 0

2.6. 배타적 논리합 (XOR; ⊻)

두 명제 중 정확히 하나만 참이어야, 혹은 두 명제의 참거짓 여부가 다를 때 참값을 돌려준다. [math(A'B+AB')][9]와 동치이다. 논리학에서는 기호 [math(\veebar)]를 사용하지만, 공학에서는 [math(\oplus)]를 사용한다.

C언어의 영향을 받은 프로그래밍 언어에서는 ^를 배타적 논리합 기호로 사용한다. 다만 일반적인 경우에는 ^가 제곱으로 사용되기 때문에 처음 프로그래밍 언어를 배우는 사람들은 제곱을 하려고 ^ 기호를 사용했다가 낭패를 겪는 경우가 있다.(…)[10][11] 이 방식으로 특정 '키'를 이용해 암호화를 하면 그 '키'로 복호화가 가능해서, 암호화 기법으로도 널리 사용된다. 비교 대상의 비트가 0이든 1이든 상관 없이 같기만 하면 0을 돌려준다는 특성을 이용하여 어셈블리어 등의 언어에서 어떤 레지스터나 변수를 0으로 초기화할 때 사용되기도 한다.[12] 이런 특성때문에 XOR을 이용해 임시 변수 없이 변수를 스왑하는 기법[13]은 메모리 사용량에서야 좀 이득을 보겠지만 실제론 거의 사용되지 않는다. 스왑하는 값이 같은 주소를 참조한다면 엉망이 되기 때문.

결합법칙이 성립하므로 n항연산으로 일반화 가능하다. 이 경우 n개의 입력 중 참의 개수가 홀수이면 출력이 참이 되는 연산으로 정의된다.
[math(A)] [math(B)] [math(A\veebar B)]
0 0 0
0 1 1
1 0 1
1 1 0

2.7. 동치 (EQV; ≡)

두 명제가 다 참이거나 다 거짓이면, 즉 두 명제의 진리값이 같으면 참값을 돌려준다. 배타적 논리합(XOR)의 부정이라고 할 수 있으므로 배타적 부정 논리합(XNOR) 또는 배타적 논리곱(XAND)이라고도 한다. 논리학에서는 기호 [math(\equiv)]를 사용하나, [math(\underline{\wedge})] 혹은 [math(\overline\veebar)]를 사용하기도 하고, 공학에서는 [math(⊙)]를 쓰기도 한다.

수학적으로는 크로네커 델타([math(\delta_{ij} = \left\{\begin{matrix} 0 \; \; \; \text{if} \; \; \; i \neq j \\ 1 \; \; \; \text{if} \; \; \; i = j \end{matrix}\right.)])로 정의돼 있다. C언어 및 그 파생 언어에서 '='는 대입(:=)을 의미하므로 동치 연산자를 '=='로 표기한다. [math((A\underline{\wedge}B)= AB+A'B')]와 동치이다.
[math(A)] [math(B)] [math(A\equiv B)]
0 0 1
0 1 0
1 0 0
1 1 1

3. 성질

공리(axiom)전제(postulation)라고도 부른다.

3.1. 항등원(identity)

[math(A\cdot 1 = A = 1\cdot A)]
[math(A+0 = A = 0+A)]

3.2. 연산 우선 순위

NOT > AND > OR 이다.
  • 부정(NOT) 연산은 AND와 OR보다 연산 우선 순위가 높다.
  • 대수학에서 곱셈 연산이 덧셈 연산보다 우선이듯이, 논리 연산에서도 논리곱(AND)이 논리합(OR) 보다 연산 순위가 높다.

분배법칙의 아래 두 식 중에 첫 번째 식의 우변에는 괄호가 없다. 이는 AND가 OR보다 연산 우선 순위가 높기 때문이다. 괄호가 생략된 것이라 보아도 되는데 [math(A\cdot B)]와 [math(A\cdot C)]에 대한 괄호의 존재 여부는 우변의 결과에 영향을 미치지 않는다.
[math(A\cdot (B+C)=A\cdot B+A\cdot C)]
[math(A+(B\cdot C)=(A+B)\cdot (A+C))]
[math(A\cdot (B+C)=(A\cdot B)+(A\cdot C)=A\cdot B+A\cdot C)]

4. 연산 법칙(law)

혼동 방지를 위해, 다음 기호만을 사용하여 표기한다.
연산 표기
NOT [math(')]
AND [math(\cdot)]
OR [math(+)]
XOR [math(\oplus)]

4.1. 교환법칙(commutatitve)

[math(A+B=B+A)]
[math(A\cdot B=B\cdot A)]
[math(A\oplus B = B\oplus A)]

4.2. 결합법칙(associative)

[math((A+B)+C=A+(B+C))]
[math((A\cdot B)C=A\cdot (B\cdot C))]
[math((A\oplus B)\oplus C = A\oplus (B\oplus C))]

NXOR을 포함하여 NAND, NOR 등 모든 부정 연산은 결합법칙이 성립하지 않는다.

4.3. 분배법칙(distributive)

[math(A\cdot (B+C)=A\cdot B+A\cdot C)]
[math(A+(B\cdot C)=(A+B)\cdot (A+C))]
[math(A\cdot (B\oplus C) = A\cdot B\oplus A\cdot C)]

논리연산의 분배법칙 결과는 [math(A+(B\cdot C)=(A+B)\cdot (A+C))]가 된다. 드모르간 법칙 하단의 설명을 보면 쉽게 이해할 수 있다.

4.4. 동일법칙(idempotent)[14]

[math(A\cdot A = A)]
[math(A + A = A)]
계산하려는 두 숫자가 똑같으면 결과도 그 똑같은 값이 나온다는 뜻이다. [math(A)]에 0을 대입했을 때도 성립하고 1을 대입했을 때도 성립하는 것으로 해당 성질을 증명할 수 있다.

4.5. 흡수법칙(absorption)

[math(A+A\cdot B=A)]
[math(A\cdot (A+B)=A)]
전기 회로에서 곱연산을 직렬로, 합연산을 병렬로 생각해보면 이해가 쉽다. 아래 식에서 [math(B)]는 [math(A)]와 병렬이라서 [math(B)]가 끊어졌어도 [math(A)]가 이어져 있으면 그대로 전기가 흐르기 때문에 사실상 [math(B)]는 없는 것이나 다름없고, [math(A)]를 직렬로 두 개 단 것과 똑같기 때문에 식이 저렇게 [math(A)]로 흡수되는 것이다.

두 흡수법칙 식의 증명은 아래와 같다. 증명의 3행에 흡수법칙의 위쪽 식이 등장한다.
[math(\def\arraystretch{1.5} \begin{array}{clr}
&A \cdot (A+B) &\\
=&A \cdot A + A \cdot B &\because 분배법칙\\
=&A + A\cdot B &\because 동일법칙\ A\cdot A = A\\
=&A\cdot 1 + A\cdot B &\because 항등원\ A\cdot 1 = A\\
=&A\cdot (1 + B) &\because 분배법칙\\
=&A\cdot 1 &\because B + 1 = 1\\
=&A &\because 항등원\ A\cdot 1 = A\\
\end{array})]

4.6. 이중부정 법칙(involution)

[math((A')' = A)]

4.7. 드모르간 법칙(de Morgan's)

[math((A \cdot B)'=A'+B')]
[math((A+B)'=A' \cdot B')]
식을 깔끔하게 정리할 때 가장 많이 사용되는데다가 NAND 연산, NOR 연산과 밀접한 연관이 있는 만큼 불 대수에서 상당히 중요하게 다뤄지는 성질이다. 오죽하면 대부분 교재에서 이 법칙 하나만 불 대수 파트에서 분리해서 따로 가르칠 정도.

사실 머리를 좀 굴려보면 AND와 OR은 같은 구조의 함수지만(항등원끼리 연산하면 항등원, 나머지 경우는 항등원이 아닌 것) AND는 항등원이 1(=0')이고 OR은 항등원이 0(=1')일 뿐이라는 걸 알 수 있는데, 다시 말해 NOT은 ({0 || 1}, AND)에서 ({0, 1}, OR)로 가는 isomorphism이다. 이중 부정규칙을 이용하면 동시에 NOT은 ({0 || 1}, OR)에서 ({0, 1}, AND)로 가는 isomorphism이므로 결론적으로 NOT은 ({0 || 1}, AND, OR)에서 ({0, 1}, OR, AND)로 가는(연산이 서로 바뀌었다) isomorphism이다.

이걸 이용해 드모르간 법칙을 쉽게 증명할 수 있을 뿐만 아니라 성질 항목에 나와있는 한쌍의 공식이 서로를 유도할 수 있다는 걸 쉽게 보일 수 있다.

4.8. 합의 법칙(consensus)

[math(AB + {\color{red}BC} + CA' = AB + CA')]
[math((A + B){\color{red}(B + C)}(C + A') = (A + B)(C + A'))]
자세히 보면 가운데 마디가 사라진 것을 볼 수 있다.

증명은 아래와 같다.
우선

[math(\def\arraystretch{1.5} \begin{array}{clr}
&BC&\\
=&1\cdot BC &\because 항등원\ A\cdot 1 = A\\
=&(A+A')\cdot BC &\because A+A' = 1\\
=&ABC+ A'BC &\because 분배법칙\\
=&ABC + CA'B &\because 교환법칙\end{array})]

임을 이용한다.

[math(\def\arraystretch{1.5} \begin{array}{clr}
&AB + BC + CA'&\\
=&AB + ABC + CA'B + CA'&\\
=&(AB+AB\cdot C) + (CA'\cdot B + CA') &\because 결합법칙\\
=&(AB + AB\cdot C) + (CA' + CA'\cdot B) &\because 교환법칙\\
=&AB + CA' &\because 흡수법칙\ A+A\cdot B = A\end{array})]
비슷한 방법으로 아래 식도 증명할 수 있다.

4.9. 그 밖의 연산 법칙

[math(A + A' = 1)]
[math(A\cdot A' = 0)]
[math(A+1=1)]
[math(A\cdot 0 = 0)]
[math((A\oplus B)' = A\oplus B' = A'\oplus B)]
[math(A'\oplus B' = A\oplus B)]
[math(A+A'\cdot B=A+B)]
[math(A\cdot (A'+B)=A\cdot B)]

마지막 두 식의 증명은 다음과 같다.
[math(\def\arraystretch{1.5} \begin{array}{clr}
&A+A'\cdot B\\
=&A\cdot(B+1) + A'\cdot B &\because B+1=1\\
=&A\cdot B + A + A'\cdot B = 0\\
=&A+B\cdot(A+A')=A+B &\because A+A'=1\end{array})]

[math(\def\arraystretch{1.5} \begin{array}{clr}
&A\cdot (A'+B)&\\
=&A\cdot A' + A\cdot B &\because 분배법칙\\
=&0 + A\cdot B &\because A\cdot A' = 0\\
=&A\cdot B &\because 항등원\ 0 + A = A\end{array})]

5. 관련 문서



[1] 단, 0을 원소로 가지는 집합끼리의 교집합은 공집합이므로, 교집합을 논리곱(and)이라고 하려면 공집합 또한 0으로 보아야 한다. [2] 이 방법을 통해 드모르간 법칙이 불 대수에서 성립함을 직접적 증명 없이 이해할 수 있다. [3] 원소가 두 개(binary)뿐인 집합이라는 의미도 함의하고 있다. [4] ~는 C언어에서도 마찬가지로 부정으로 사용되긴 하나, 논리 연산이 아닌 비트 연산이다. [5] 프라임이라 읽는다. 미분 기호로도 쓰인다. [6] 주의하자면 곱셈이 절대로 아니다! [math(A \boldsymbol{\text{ and }} B)], [math(A)] 논리곱 [math(B)]. 이래도 헷갈린다(...) [7] [math(A \boldsymbol{\text{ or }} B)] [8] [math(p\uparrow p=\neg p, (p\uparrow q)\uparrow (p\uparrow q)=p\wedge q,(p\uparrow p)\uparrow (q\uparrow q)=p\vee q)] [9] ((not A) and B) or (A and (not B)) [10] C언어에서 제곱은 math.h라는 헤더 파일을 include(포함)하고(<math.h>), pow(밑, 지수) 함수를 사용하면 가능하다. [11] PHP 5.6 이상이나 Python 등의 언어에서는 또 **로 지수를 표현하는 것이 가능하다. [12] 예를 들어, AX라는 레지스터를 0으로 초기화 할 땐 MOV AX,0을 써도 되지만 XOR AX,AX를 해도 된다는 의미이다. AX에 뭔 값이 들어있는지는 알 수 없지만, 같은 것끼지 연산시키면 무조건 0을 반환하는 XOR의 특성 상 해당 연산의 결과는 AX의 원래 값과는 상관 없이 항상 0이 된다. [13] [math(A=A\veebar B)]; [math(B=A\veebar B)]; [math(A=A\veebar B)] [14] 멱등(冪等)법칙이라고도 한다.