논리 연산

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 연산 법칙
3. 연산의 종류
4. 논리 연산의 표현
- 4.1. 표기법의 역사
5. 논리 연산자의 성질
6. 우선 순위
7. 완전성
8. 응용
- 8.1. 컴퓨터 과학
- 8.2. 집합론
9. 자연어와의 관계
참조

1. 개요

논리 연산은 논리적 명제를 조작하고 결합하는 데 사용되는 연산이다. 멱등, 교환, 결합, 분배, 흡수, 드 모르간의 법칙 등의 연산 법칙을 따르며, 부정, 논리곱, 논리합, 조건문, 쌍조건문 등의 종류가 있다. 논리 연산은 0입력, 1입력, 2입력 연산으로 나뉘며, 완전성을 통해 특정 연산자 집합만으로 모든 논리 연산을 표현할 수 있다. 컴퓨터 과학에서는 논리 게이트를 통해 디지털 회로를 구성하고 비트 연산을 수행하며, 집합론에서는 집합 연산을 정의하는 데 사용된다. 자연어 연결사와 관련된 연구도 진행되며, 형식 의미론에서 자연어 연결사의 의미를 논리 연산과 연결하여 연구한다.

더 읽어볼만한 페이지

논리 기호 - 화살표
화살표는 방향이나 관계를 나타내는 기호로, 과거에는 물의 흐름이나 군대 이동을 나타냈지만 현재는 표지판, 수학, 논리학, 컴퓨터 과학 등 다양한 분야에서 활용되며 유니코드에는 다양한 형태의 화살표 기호들이 정의되어 있다.
논리 기호 - 이중 턴스틸
이중 턴스틸은 논리학에서 모델 구조와 문장 집합의 관계를 나타내는 기호로, 문장 집합의 충족 가능성을 표현하며 의미론적 귀결 및 항진명제와 관련되어 있고, 유니코드와 LaTeX, TeX 환경에서 특정 방식으로 표현된다.
논리 연결자 - 거짓
거짓은 논리학에서 명제의 진리값 중 하나로 참의 반대되는 개념이며, 고전 논리와 부울 논리에서 명제가 가질 수 있는 값이고, 부정, 조건문과 연관되어 있으며, 형식 이론에서는 정리로 도출되지 않을 때 일관성이 있다고 정의된다.
논리 연결자 - 논리적 참
컴퓨터 과학 - 수학적 최적화
수학적 최적화는 주어진 집합에서 실수 또는 정수 변수를 갖는 함수의 최댓값이나 최솟값을 찾는 문제로, 변수 종류, 제약 조건, 목적 함수 개수에 따라 다양한 분야로 나뉘며 여러 학문 분야에서 활용된다.
컴퓨터 과학 - 증명 보조기
증명 보조기는 수학적 증명의 정확성을 검증하고 형식적인 증명 탐색을 지원하는 소프트웨어 도구로, 고차 논리, 의존 타입, 작은 커널, 자동 정리 증명, 반사 증명, 코드 생성 등의 다양한 기능을 제공하며, "정리 증명기 박물관" 프로젝트를 통해 소스 보존을 목표로 하는 다양한 시스템들이 존재한다.

논리 연산
개요
정의	논리 연산(logical operations)은 하나 이상의 논리 입력에 대해 논리적 출력을 생성하는 연산이다.
다른 이름	불 연산(boolean operations) 논리 접속사 (logical connectives) 명제 접속사 (propositional connectives)
종류
부정 (NOT)	입력된 논리값의 반대 값을 출력한다. (참 → 거짓, 거짓 → 참)
논리곱 (AND)	모든 입력이 참일 경우에만 참을 출력한다.
논리합 (OR)	하나 이상의 입력이 참일 경우 참을 출력한다.
배타적 논리합 (XOR)	입력 중 하나만 참일 경우 참을 출력한다.
조건 (IMPLICATION)	'만약 A라면 B이다'의 형태로, A가 참이고 B가 거짓일 경우에만 거짓을 출력한다.
동치 (EQUIVALENCE)	두 입력이 동일한 논리값을 가질 경우 참을 출력한다.
NAND	논리곱의 결과를 부정한다.
NOR	논리합의 결과를 부정한다.
응용 분야
컴퓨터 과학	디지털 회로 설계 프로그래밍 언어 (조건문, 논리 연산자) 데이터베이스 (SQL의 WHERE 절)
수학	명제 논리 집합론
철학	논리적 추론

2. 연산 법칙

논리합( $\lor$ ), 논리곱( $\land$ ), 부정( $\lnot$ ) 연산은 다음과 같은 법칙들을 따른다.

'''멱등 법칙'''

\begin{align}p \lor p &\equiv p \\p \land p &\equiv p \\\end{align}

'''교환 법칙'''

\begin{align}p \lor q &\equiv q \lor p \\p \land q &\equiv q \land p \\\end{align}

'''결합 법칙'''

\begin{align}p \lor(q \lor r) &\equiv (p \lor q)\lor r \\p \land(q \land r) &\equiv (p \land q)\land r \\\end{align}

'''분배 법칙'''

\begin{align}p \lor(q \land r) &\equiv (p \lor q)\land(p \lor r) \\p \land(q \lor r) &\equiv (p \land q)\lor(p \land r) \\\end{align}

'''흡수 법칙'''

\begin{align}p \lor(p \land q) &\equiv p \\p \land(p \lor q) &\equiv p \\\end{align}

'''드 모르간의 법칙'''

\begin{align}\lnot(p \lor q) &\equiv (\lnot p)\land(\lnot q) \\\lnot(p \land q) &\equiv (\lnot p)\lor(\lnot q) \\\end{align}

'''기타'''

\begin{align}&p \lor 0 \equiv p \\&p \land 0 \equiv 0 \\&p \lor 1 \equiv 1 \\&p \land 1 \equiv p \\&p \lor (\lnot p) \equiv 1 \\&p \land (\lnot p) \equiv 0 \\&\lnot(\lnot p) \equiv p \\\end{align}

3. 연산의 종류

여기에서는 출력이 하나인 논리 함수만을 다룬다. 논리 연산에서 사용하는 진리값은 참(1)과 거짓(0) 두 가지로 표현한다.

논리 연산은 입력되는 값의 개수에 따라 분류할 수 있다. 입력이 없는 0입력 연산, 입력이 하나인 1입력 연산, 입력이 두 개인 2입력 연산 등이 있다.

3. 1. 0입력 연산

(작성할 내용 없음 - 원본 소스에 해당 섹션 관련 정보가 부재함)

3. 2. 1입력 연산

하나의 입력을 받아 하나의 출력을 내는 부울 함수는 다음 4가지 종류가 있다.

입력값에 관계없이 항상 0을 출력한다.
입력값에 관계없이 항상 1을 출력한다.
입력값을 그대로 출력한다.
입력이 0이면 1을, 입력이 1이면 0을 출력한다. 즉, 입력의 부정( $\neg$ , '''NOT''') 연산을 수행한다.

3. 3. 2입력 연산

2개의 입력 ''P'', ''Q''에 대해 가능한 논리 연산은 다음 16가지가 전부이다.

이하 표에서는 논리합에는

\vee

, 논리곱에는

\wedge

기호를 사용한다.

2입력 논리 연산 (P, Q)
연산	기호	등가식	진리표 (P, Q)				벤 다이어그램
0, 0	0, 1	1, 0	1, 1				벤 다이어그램
모순	$\bot$ , P $\wedge$ ¬P		0	0	0	0	모순
논리곱 (AND)	P $\wedge$ Q, P & Q, P AND Q	¬(P $\rightarrow$ ¬Q), ¬(¬P $\leftarrow$ Q), ¬P $\downarrow$ ¬Q	0	0	0	1	논리곱
비함의	P $\not\rightarrow$ Q, P $\not\supset$ Q	P $\wedge$ ¬Q, ¬P $\downarrow$ Q, ¬(P $\not\leftarrow$ ¬Q)	0	0	1	0	비함의
명제 P	P		0	0	1	1	명제 P
역비함의	P $\not\leftarrow$ Q, P $\not\subset$ Q	P $\downarrow$ ¬Q, ¬P $\wedge$ Q, ¬(P $\not\rightarrow$ ¬Q)	0	1	0	0	역비함의
명제 Q	Q		0	1	0	1	명제 Q
배타적 논리합 (XOR)	P $\oplus$ Q, P $\not\leftrightarrow$ Q, P $\not\equiv$ Q, P XOR Q	(P $\leftrightarrow$ ¬Q), (¬P $\leftrightarrow$ Q), ¬(P $\leftrightarrow$ Q)	0	1	1	0	배타적 논리합
논리합 (OR)	P $\vee$ Q, P OR Q	P $\leftarrow$ ¬Q, ¬P $\rightarrow$ Q, ¬(¬P $\uparrow$ ¬Q)	0	1	1	1	논리합
NOR (Not OR)	P $\downarrow$ Q, P NOR Q	P $\not\leftarrow$ ¬Q, ¬(¬P $\not\rightarrow$ Q), ¬P $\wedge$ ¬Q	1	0	0	0	NOR
동치 (XNOR)	P $\leftrightarrow$ Q, P $\equiv$ Q, P XNOR Q, P IFF Q	P $\not\leftrightarrow$ ¬Q, ¬P $\not\leftrightarrow$ Q, ¬P $\leftrightarrow$ ¬Q	1	0	0	1	동치
부정 Q	¬Q		1	0	1	0	부정 Q
역함의	P $\leftarrow$ Q, P $\subset$ Q	P $\vee$ ¬Q, ¬P $\uparrow$ Q, ¬P $\rightarrow$ ¬Q	1	0	1	1	역함의
부정 P	¬P		1	1	0	0	부정 P
함의 (조건식)	P $\rightarrow$ Q, P $\supset$ Q	P $\uparrow$ ¬Q, ¬P $\vee$ Q, ¬P $\leftarrow$ ¬Q	1	1	0	1	함의
NAND (Not AND)	P $\uparrow$ Q, P \| Q, P NAND Q	P $\rightarrow$ ¬Q, ¬P $\leftarrow$ Q, ¬P $\vee$ ¬Q	1	1	1	0	NAND
항진	$\top$ , P $\vee$ ¬P		1	1	1	1	항진

4. 논리 연산의 표현

표벤
다이어그램0항 접속사(상수)⊤진리/항진1--⊥거짓/모순0--단항 접속사 $p$ =01

p

¬

¬p

이항 접속사

p

=0011

q

=0101∧논리곱0001↑대안 부정 (NAND)1110∨논리합0111↓배타적 논리합 (XOR)0110↔조건문1101↛역함축1011↚자세한 정보

집합 연산	연결자	정의
교집합	논리곱	$A \cap B = \{x : x \in A \land x \in B \}$ ^[23]^[24]^[25]
합집합	논리합	$A \cup B = \{x : x \in A \lor x \in B \}$ ^[26]^[23]^[24]
여집합	부정	$\overline{A} = \{x : x \notin A \}$ ^[27]^[24]^[28]
부분 집합	함축	$A \subseteq B \leftrightarrow (x \in A \rightarrow x \in B)$ ^[29]^[24]^[30]
동일	쌍조건자	$A = B \leftrightarrow (\forall X)[A \in X \leftrightarrow B \in X]$ ^[29]^[24]^[31]

연결사	영어로	부분에 대한 명사	동사구
결합	A와 B 둘 다	결합자	A와 B는 결합된다
분리	A 또는 B, 또는 둘 다	분리자	A와 B는 분리된다
부정	A가 아닌 경우	부정항/피연산자	A는 부정된다
조건문	만약 A, 그러면 B	전건, 후건	B는 A에 의해 함축된다
쌍조건문	A는, 그리고 오직 A일 때만, B	동치	A와 B는 동치이다

논리 연산

1. 개요

더 읽어볼만한 페이지

2. 연산 법칙

3. 연산의 종류

3. 1. 0입력 연산

3. 2. 1입력 연산

3. 3. 2입력 연산

4. 논리 연산의 표현

4. 1. 표기법의 역사

5. 논리 연산자의 성질

6. 우선 순위

7. 완전성

8. 응용

8. 1. 컴퓨터 과학

8. 2. 집합론

9. 자연어와의 관계

참조

영어 단어	연결사	기호	논리 게이트
not	부정	$\neg$	NOT
and	논리곱	$\wedge$	AND
or	논리합	$\vee$	OR
if...then	조건문	$\to$	IMPLY
...if	역함축	$\leftarrow$
either...or	배타적 논리합	$\oplus$	XOR
if and only if	쌍조건	$\leftrightarrow$	XNOR
not both	대안 부정 (NAND)	$\uparrow$	NAND
neither...nor	결합 부정 (NOR)	$\downarrow$	NOR
but not	비함축	$\not\to$	NIMPLY