진리표

진리표(truth table)는 논리학에서 사용되는 수학적 표로, 특히 부울 대수, 부울 함수, 명제 연산과 관련하여 논리식의 함수 값을 각각의 함수 인수, 즉 논리 ^[1]변수가 취한 값의 각 조합에 대해 정의합니다.특히 진리표는 명제 표현이 모든 정당한 입력 값에 대해 참인지, 즉 논리적으로 유효한지를 보여주는 데 사용될 수 있습니다.

진리 테이블에는 각 입력 변수(예: A 및 B)에 대한 열이 하나씩 있고, 테이블이 나타내는 논리 연산의 가능한 모든 결과(예: A XOR B)를 보여주는 최종 열이 하나 있습니다.진리표의 각 행에는 입력 변수의 가능한 구성(예: A=true, B=true)과 해당 값에 대한 연산 결과가 포함됩니다.

진리표는 부울 함수의 입력 변수와 해당 출력 값에 대한 모든 가능한 진리값 조합을 제시하는 구조화된 표현입니다.A에서 F로의 함수 f는 A×F의 부분 집합인 특수 관계이며, 이는 단순히 f가 입출력 쌍의 목록으로 나열될 수 있음을 의미합니다.부울 함수의 경우 출력은 이진 집합에 속합니다.F = {0, 1}.n진 부울 함수의 경우 입력은 입력 부울 변수에 해당하는 이진 집합의 데카르트 곱인 도메인에서 옵니다.예를 들어, 이진 함수인 f(A, B)의 경우 f 의 정의역은 A×B 이고, A×B = {(A = 0, B = 0), (A = 0, B = 1), (A = 1, B = 0), (A = 1, B = 1)}로 나열할 수 있습니다.도메인의 각 요소는 변수 A와 B에 대한 입력 값의 조합을 나타냅니다.이제 이러한 조합은 해당 조합에 해당하는 함수의 출력과 결합할 수 있으므로 입력-출력 쌍의 집합을 A×F의 부분 집합인 특수 관계로 구성할 수 있습니다.관계가 함수가 되기 위해서는 함수의 도메인의 각 요소가 코드 도메인의 하나의 멤버에만 매핑되어야 한다는 특별한 요구 사항이 있습니다.따라서 함수 f 자체를 f = {(0, 0), f(0, 1), ((0, 1), f), (1, 0), f), (1, 1), f(1, 1)}와 같이 나열할 수 있습니다. 여기서 f, f, f, f는 각각 부울, 0 또는 1로서 코드 도메인 {0, 1}의 멤버로서의 값을 각각 도메인의 멤버에 해당하는 출력으로 나타냅니다.그러면 진리표는 위에 주어진 목록(집합)이 아닌 표 형식으로 이러한 입력-출력 쌍을 제시하며, 각 행은 해당 출력 값인 0 또는 1과 쌍을 이루는 도메인의 멤버에 해당합니다.물론 부울 함수의 경우, 도메인의 모든 구성원을 코드 도메인에 있는 이미지와 함께 나열할 필요는 없습니다. 구성원을 "1"로 매핑하는 매핑을 단순히 나열할 수 있습니다. 왜냐하면 다른 모든 구성원은 자동으로 "0"으로 매핑되어야 하기 때문입니다(이것은 우리를 마이너 용어로 유도합니다).

루트비히 비트겐슈타인은 1918년에 완성되어 ^[2]1921년에 출판된 그의 Tractatus Logico-Philosophicus에서 진리표를 발명하고 대중화시킨 것으로 일반적으로 인정받고 있습니다.이러한 제도는 1921년 에밀 레온 ^[3]포스트에 의해서도 독자적으로 제안되었습니다.

무효 연산

null 연산은 2개입니다.

항상 참입니다.
절대 사실이 아니야, 단 하나의 가성

논리 참

이 연산자는 피연산자가 0이므로 입력 값이 없으므로 출력 값은 항상 참입니다.

p	$T$
T	T
F	T

논리 false

출력 값이 참이 아닙니다. 즉, 항상 거짓입니다. 이 연산자는 피연산자가 0이므로 입력 값이 없습니다.

p	$F$
T	F
F	F

단항 연산

단항 연산은 2개입니다.

단항등식
단사부정

논리 아이덴티티

논리적 아이덴티티는 하나의 논리값 p에 대한 연산으로 출력값은 p로 유지됩니다.

논리 ID 연산자에 대한 진리표는 다음과 같습니다.

p	$p$
T	T
F	F

논리부정

논리 부정은 피연산자가 거짓이면 true 값을, 피연산자가 참이면 false 값을 생성하는 하나의 논리적 값(일반적으로 명제의 값)에 대한 연산입니다.

NOT p의 진리표(¬p, Np, Fpq 또는 ~p로도 표기)는 다음과 같습니다.

p	$◦p$
T	F
F	T

이진 연산

두 개의 이진 변수에 대해 16개의 가능한 진리 함수가 있습니다.

모든 이항 논리 연산자에 대한 진리표

다음은 두 부울 변수 P 및 Q의 ^{[note 1]}가능한 16개의 모든 진리 함수의 정의를 제공하는 확장 진리표입니다.

p	q	F⁰	도 아니다¹	↚²	◦p³	민첩하게⁴	¬q⁵	XOR⁶	낸드⁷	그리고.⁸	XNOR⁹	q¹⁰	암시하는¹¹	p¹²	←¹³	오어¹⁴	T¹⁵
T	T	F	F	F	F	F	F	F	F	T	T	T	T	T	T	T	T
T	F	F	F	F	F	T	T	T	T	F	F	F	F	T	T	T	T
F	T	F	F	T	T	F	F	T	T	F	F	T	T	F	F	T	T
F	F	F	T	F	T	F	T	F	T	F	T	F	T	F	T	F	T
Com		✓	✓					✓	✓	✓	✓					✓	✓
Assoc		✓						✓		✓	✓	✓		✓		✓	✓
Adj		바⁰	NOR¹	↛⁴	¬q⁵	민첩하게²	◦p³	XOR⁶	낸드⁷	AND⁸	XNOR⁹	p¹²	암시하는¹³	q¹⁰	→¹¹	오어¹⁴	T¹⁵
Neg		T¹⁵	오어¹⁴	←¹³	p¹²	암시하는¹¹	q¹⁰	XNOR⁹	AND⁸	낸드⁷	XOR⁶	¬q⁵	민첩하게⁴	◦p³	↚²	NOR¹	바⁰
Dual		T¹⁵	낸드⁷	→¹¹	◦p³	←¹³	¬q⁵	XNOR⁹	NOR¹	오어¹⁴	XOR⁶	q¹⁰	↚²	p¹²	↛⁴	AND⁸	바⁰
L id				F				F		T	T	T,F	T			F
R id						F		F		T	T			T,F	T	F

어디에

T = 참입니다.

F = false.

위첨자는 4개의 진리값을 F = 0, T = 1의 이진수로 읽은 결과의 숫자입니다.

Com 행은 연산자 op가 교호작용 여부를 나타냅니다(팝 Q = Qop P).

연관 행은 연산자 op가 연관성이 있는지 여부를 나타냅니다. (팝 Q) op R = 팝 (Qop R).

조정 행은 연산자 op2를 Pop Q = Qop2 P로 표시합니다.

Negrow는 연산자 op2를 Pop Q = θ(Pop2 Q)로 표시합니다.

Dual(이중) 행은 T와 F, AND를 OR로 바꾸어 얻은 이중 연산을 보여줍니다.

Lid 행은 연산자가 I 값을 가지는 경우 연산자의 왼쪽 ID를 표시하여 I op Q = Q가 되도록 합니다.

Rid 행은 연산자가 Pop I = P와 같은 값 I을 가질 경우 연산자의 오른쪽 ID를 보여줍니다.

p, q에 대한 입력 값의 네 가지 조합은 위의 표에서 행 단위로 읽습니다.각 p, q 조합에 대한 출력 함수는 표에서 행 단위로 읽을 수 있습니다.

키:

다음 표는 행이 아닌 열을 기준으로 정렬됩니다.p, q의 네 가지 조합을 입력으로 표시하기 위해 행이 아닌 열이 네 개 있습니다.

p: TFFF
q: TFTF

이 키에는 두 개의 이진 변수 p, q의 각 이진 함수에 대해 하나의 행으로 16개의 행이 있습니다. 예를 들어, 이 키의 2행에서 고유한 조합 p=F, q=T로 표시된 열에 대해 Converse nonimpplication(' ↚ {\displaystyle \nleftarrow }')의 값은 단독 T입니다. 반면 2행에서는 '↚ {\displaystyle \nleftarrow }' o의 값입니다p, q의 나머지 세 열에 대한 퍼페레이션은 F입니다.따라서 ↚ {\ $displaystyle \nleftarrow}$ 의 출력 행은 다음과 같습니다.

2: FT FFT

그리고 16열^[4] 키는

	^[4]		교환입니다.	작업명
0	(FFFF)(p, q)	⊥	false, Opq	모순
1	(FFFT)(p, q)	도 아니다	p ↓ q, Xpq	논리 NOR
2	(FFTF)(p, q)	↚	↚ q, Mpq	암시가 없는 변환
3	(FT)(p, q)	¬p, ~p	ωp, Np, Fpq	부정
4	(FFF)(p, q)	↛	↛ q, Lpq	소재불관용
5	(FTFT)(p, q)	¬q, ~q	¬q, Nq, Gpq	부정
6	(FT F)(p, q)	XOR	p⊕ q,Jpq	배타적 분배
7	(FT T)(p, q)	낸드	p ↑ q, Dpq	논리 낸드
8	(TFFF)(p, q)	그리고.	∧ q, Kpq	논리합
9	(TFFT)(p, q)	XNOR	p q, Epq인 경우에만 해당되는 경우	논리쌍조건
10	(TFTF)(p, q)	q	q, Hpq	프로젝션 함수
11	(FTT)(p, q)	p → q	만약 p라면 q, Cpq	물질적 함의
12	(TFF)(p, q)	p	p, Ipq	프로젝션 함수
13	(TTFT)(p, q)	p ← q	pif q, Bpq	역의시
14	(TT TF)(p, q)	오어	∨ q, Apq	논리적 접속
15	(TT T)(p, q)	⊤	참, Vpq	토우톨로지

논리 연산자는 벤 다이어그램을 사용하여 시각화할 수도 있습니다.

논리합(AND)

논리적 연결은 두 개의 논리적 값(일반적으로 두 명제의 값)에 대한 연산으로, 피연산자가 모두 참일 경우 참 값을 생성합니다.

p AND q(p q, Kpq, p & q 또는 p $\cdot$ ⋅ {\ $displaystyle \cdot }$ $\cdot$ 라고도 함)에 대한 진리표는 다음과 같습니다.

p	q	∧ q
T	T	T
T	F	F
F	T	F
F	F	F

일반적인 언어 용어에서 p와 q가 모두 참이면 접속사 p ∧ q는 참입니다.논리적 값을 p와 q에 할당한 다른 모든 경우에 대해 연결 p ∧ q는 false입니다.

p이면 p ∧ q가 q이고, 아니면 p ∧ q가 p라고 할 수도 있습니다.

논리접속(OR)

논리적 단절은 피연산자 중 적어도 하나가 참일 경우 참 값을 생성하는 두 개의 논리적 값(일반적으로 두 명제의 값)에 대한 연산입니다.

p OR q의 진리표(p ∨ q, Apq, p q 또는 p + q로도 표기)는 다음과 같습니다.

p	q	∨ q
T	T	T
T	F	T
F	T	T
F	F	F

영어로 표기하면 p이면 p ∨ q는 p이고, 그렇지 않으면 p ∨ q는 q입니다.

논리적 함의

논리적 의미와 물질적 조건은 둘 다 두 개의 논리적 값에 대한 연산과 연관되어 있습니다. 일반적으로 두 개의 명제의 값은 첫 번째 피연산자가 참이고 두 번째 피연산자가 거짓이면 거짓 값을 생성하고, 그렇지 않으면 참 값을 생성합니다.

논리적 의미 p와 연관된 진리표는 q를 암시합니다(p ⇒ q 또는 더 드물게 Cpq로 상징됨).

p	q	⇒ q
T	T	T
T	F	F
F	T	T
F	F	T

p 다음 q일 때 물질 조건과 관련된 진리표(p → q로 요약됨)는 다음과 같습니다.

p	q	p → q
T	T	T
T	F	F
F	T	T
F	F	T

또한 p ⇒ q 및 p → q가 ¬p ∨ q와 동일하다는 점에 유의해야 합니다.

논리적 동치

논리적 동등성(Logical Equality, biconditional 또는 exclusive nor라고도 함)은 두 피연산자가 모두 거짓이거나 두 피연산자가 모두 참일 경우 참 값을 생성하는 두 개의 논리적 값(일반적으로 두 명제의 값)에 대한 연산입니다.

p XNOR q의 진리표(p ↔ q, Epq, p = q 또는 p ≡ q로도 표기)는 다음과 같습니다.

p	q	p ↔ q
T	T	T
T	F	F
F	T	F
F	F	T

따라서 p와 q가 동일한 진리값을 가지면 pEQ q는 참이고(참이거나 거짓 둘 다), 서로 다른 진리값을 가지면 거짓입니다.

배타적 분배

배타적 분리는 두 개의 논리적 값(일반적으로 두 개의 명제의 값)에 대한 연산으로, 피연산자가 모두 참이 아닐 경우 참 값을 생성합니다.

pXOR q의 진리표(Jpq 또는 p q로 표기)는 다음과 같습니다.

p	q	⊕ q
T	T	F
T	F	T
F	T	T
F	F	F

두 개의 명제에 대해 XOR은 (p ¬ q) ∨ (¬p ∧ q)로 쓸 수도 있습니다.

논리 낸드

논리적 NAND는 두 개의 논리적 값(일반적으로 두 명제의 값)에 대한 연산으로, 피연산자가 모두 참이면 false 값을 생성합니다.즉, 피연산자 중 적어도 하나가 거짓이면 true 값을 생성합니다.

p NAND q(p ↑ q, Dpq 또는 pq로도 표기됨)에 대한 진리표는 다음과 같습니다.

p	q	p ↑ q
T	T	F
T	F	T
F	T	T
F	F	T

논리 연산을 복합 연산(compound operation), 즉 다른 연산들로부터 구축되거나 구성되는 연산으로 표현하는 것이 일반적으로 유용합니다.기본 또는 "기본"으로 간주되는 연산과 복합 또는 "파생"으로 간주되는 연산에 따라 많은 그러한 구성이 가능합니다.

논리 낸드의 경우 NOT와 AND의 합성어로 명확하게 표현 가능합니다.

접속사의 부정: ¬(p ∧ q), 그리고 부정의 접속사: (¬p) ∨(¬q)는 다음과 같이 표로 나타낼 수 있습니다.

p	q	∧ q	◦(p q)	◦p	¬q	(¬p) ∨ (¬q)
T	T	T	F	F	F	F
T	F	F	T	F	T	T
F	T	F	T	T	F	T
F	F	F	T	T	T	T

논리 NOR

논리 NOR는 두 개의 논리값(일반적으로 두 명제의 값)에 대한 연산으로, 피연산자가 모두 거짓일 경우 true 값을 생성합니다.즉, 피연산자 중 적어도 하나가 참이면 false 값을 생성합니다.↓ 발명가 찰스 샌더스 피어스의 이름을 따서 피어스 화살이라고도 하며, 단독 연산자입니다.

p NOR q의 진리표(p ↓ q 또는 Xpq로도 표기)는 다음과 같습니다.

p	q	p ↓ q
T	T	F
T	F	F
F	T	F
F	F	T

접속 ¬(p q)의 부정과 부정(¬p) ∧(¬q)의 접속은 다음과 같이 표로 나타낼 수 있습니다.

p	q	∨ q	◦(p q)	◦p	¬q	(¬p) ∧ (¬q)
T	T	T	F	F	F	F
T	F	T	F	F	T	F
F	T	T	F	T	F	F
F	F	F	T	T	T	T

NAND와 NOR에 대한 표 형식의 도함수의 검사는, 함수 인수 p와 q에 대한 논리 값의 각각의 할당 하에, (¬p) ∨(¬q)에 대한 (¬p) ∧(¬q)에 대한 (¬p) ∨(∧q)에 대한 ¬(p qq)에 대한 함수 값의 동일한 패턴을 생성합니다.따라서 각 쌍의 첫 번째 식과 두 번째 식은 논리적으로 동등하며, 논리적 값에만 관련된 모든 컨텍스트에서 서로 대체될 수 있습니다.

이 등가성은 드 모건의 법칙 중 하나입니다.

진리표의 크기

입력 변수가 n개인 경우 진리값의 조합은 2개가ⁿ 될 수 있습니다.주어진 함수는 각 조합에 대해 참 또는 거짓을 생성할 수 있으므로 n개 변수의 다른 함수의 수는 두 배의 지수^2ⁿ 2가 됩니다.

n	2ⁿ	2^2ⁿ
0	1	2
1	2	4
2	4	16
3	8	256
4	16	65,536
5	32	4,294,967,296	≈ 4.3x10⁹
6	64	18,446,744,073,709,551,616	≈ 1.8x10¹⁹
7	128	340,282,366,920,938,463,463,374,607,431,768,211,456	≈ 3.4x10³⁸
8	256	115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936	≈ 1.2x10⁷⁷

세 개 이상의 변수의 함수에 대한 진리표는 거의 주어지지 않습니다.

적용들

진리표는 다른 많은 논리적 동치를 증명하는 데 사용될 수 있습니다.예를 들어 다음 진리표를 생각해 봅니다.

$(p\오른쪽 화살표 q)\equiv (\lnot p\or q)$
$p$	$q$	$\lnot p$	$\lnot p\lor q$	$p\오른쪽 화살표 q$
T	T	F	T	T
T	F	F	F	F
F	T	T	T	T
F	F	T	T	T

이는 $p\Rightarrow q$ ⇒ $q$ {\ $displaystyle$ p $\Rightarrow$ q}이( $\lnot p\lor q$ ) 논리적으로 ¬ $\lnot p\lor q$ ∨ q ${\displaystyle$ \ $lnot$ p\or $q}$ 와 동일하다는 사실을 $p\Rightarrow q$ .

가장 일반적으로 사용되는 논리 연산자에 대한 진리표

다음은 두 개의 부울 변수 P와 Q의 가능한 16개의 진리 함수 중에서 가장 일반적으로 사용되는 7개의 정의를 제공하는 진리표입니다.

$P$	$Q$	$P\land Q$	$P\lor Q$	$P\{\underline {\lor}}\Q$	$P\{\underline {\land}}\Q$	$P\오른쪽 화살표 Q$	$P\Leftarrow Q$	$P\왼쪽 오른쪽 화살표 Q$
T	T	T	T	F	T	T	T	T
T	F	F	T	T	F	F	T	F
F	T	F	T	T	F	T	F	F
F	F	F	F	F	T	T	T	T
$P$	$Q$	$P\land Q$	$P\lor Q$	$P\{\underline {\lor}}\Q$	$P\{\underline {\land}}\Q$	$P\오른쪽 화살표 Q$	$P\Leftarrow Q$	$P\왼쪽 오른쪽 화살표 Q$
		그리고. (절약)	오어 (분리)	XOR (단독 또는 )	XNOR (단독 또는 제외)	조건부의 "if-then	조건부의 "그때는"	이중 조건의 "if-and-only-if"
어디에 T 수단 진실의 그리고. F 수단 거짓의

이진 연산자에 대한 축약된 진리표

이진 연산자의 경우 행 제목과 열 제목이 피연산자를 지정하고 테이블 셀이 결과를 지정하는 축약된 형식의 진리표도 사용됩니다.예를 들어, 부울 논리는 다음과 같은 축약된 진리표 표기법을 사용합니다.

∧	F	T
F	F	F
T	F	T

∨	F	T
F	F	T
T	T	T

이 표기법은 행이 첫 번째 피연산자이고 열이 두 번째 피연산자임을 추가로 지정할 수 있지만, 연산이 교환인 경우 특히 유용합니다.이 축약된 표기법은 논리의 다중값 확장을 논의할 때 특히 유용합니다. 그렇지 않으면 필요한 행 수의 조합 폭발을 크게 줄이기 때문입니다.또한 표에서 값의 분포를 빠르게 인식할 수 있는 특징적인 "모양"을 제공하여 독자가 규칙을 더 빠르게 파악하는 데 도움을 줄 수 있습니다.

디지털 논리의 진리표

진리표는 또한 디지털 논리 회로에서 하드웨어 룩업 테이블(LUT)의 기능을 지정하는 데 사용됩니다.n-입력 LUT의 경우 진리표는 2^n 값(또는 위 표 형식의 행)을 가지며, LUT에 대한 부울 함수를 완전히 지정합니다.EDA(Electronic Design Automation) 소프트웨어에서는 각 부울 값을 이진수의 비트로 표현함으로써 진리표 값을 정수 값으로 효율적으로 인코딩할 수 있습니다.예를 들어 32비트 정수는 입력이 최대 5개인 LUT에 대한 진리 테이블을 인코딩할 수 있습니다.

진리 테이블의 정수 표현을 사용하는 경우, LUT의 출력값은 LUT의 입력값을 기반으로 비트 인덱스 k를 계산하여 얻을 수 있으며, 이때 LUT의 출력값은 정수의 k번째 비트입니다.예를 들어 n개의 부울 입력 값 배열이 주어진 LUT의 출력 값을 계산하기 위해 진리 테이블의 출력 값의 비트 인덱스를 다음과 같이 계산할 수 있습니다. i번째 입력이 참이면 $V_{i}=1$ i = $V_{i}=1$ {\ $displaystyle$ V_ ${i$ }= $1$ 그렇지 않으면 $V_{i}=0$ i = $V_{i}=0$ {\ $displaystyle$ V_ ${i$ }= $0$ 이라고 $V_{i}=0$ .그러면 진리표의 이진 표현의 k번째 비트는 LUT의 출력 값이며, $k=V_{0}\times 2^{0}+V_{1}\times 2^{1}+V_{2}\times 2^{2}+\dots +V_{n}\times 2^{n}$ 서 k = $k=V_{0}\times 2^{0}+V_{1}\times 2^{1}+V_{2}\times 2^{2}+\dots +V_{n}\times 2^{n}$ 0 $k=V_{0}\times 2^{0}+V_{1}\times 2^{1}+V_{2}\times 2^{2}+\dots +V_{n}\times 2^{n}$ × $k=V_{0}\times 2^{0}+V_{1}\times 2^{1}+V_{2}\times 2^{2}+\dots +V_{n}\times 2^{n}$ + $k=V_{0}\times 2^{0}+V_{1}\times 2^{1}+V_{2}\times 2^{2}+\dots +V_{n}\times 2^{n}$ $k=V_{0}\times 2^{0}+V_{1}\times 2^{1}+V_{2}\times 2^{2}+\dots +V_{n}\times 2^{n}$ × $k=V_{0}\times 2^{0}+V_{1}\times 2^{1}+V_{2}\times 2^{2}+\dots +V_{n}\times 2^{n}$ + $k=V_{0}\times 2^{0}+V_{1}\times 2^{1}+V_{2}\times 2^{2}+\dots +V_{n}\times 2^{n}$ × $k=V_{0}\times 2^{0}+V_{1}\times 2^{1}+V_{2}\times 2^{2}+\dots +V_{n}\times 2^{n}$ + ⋯ + $k=V_{0}\times 2^{0}+V_{1}\times 2^{1}+V_{2}\times 2^{2}+\dots +V_{n}\times 2^{n}$ n × $k=V_{0}\times 2^{0}+V_{1}\times 2^{1}+V_{2}\times 2^{2}+\dots +V_{n}\times 2^{n}$ $k=V_{0}\times 2^{0}+V_{1}\times 2^{1}+V_{2}\times 2^{2}+\dots +V_{n}\times 2^{n}$ {\ $displaystyle$ k= $V_{0}\time$ 2 $^{0}$ + $V_{1}\time$ 2 $^{1}$ + $V_{2}\time$ 2 $^{2}+\time$ + $V_{n}\time$ 2 $^{n$

진리표는 부울 함수를 인코딩하는 단순하고 간단한 방법이지만 입력 수가 증가함에 따라 크기가 기하급수적으로 증가하는 것을 고려할 때 입력 수가 많은 함수에는 적합하지 않습니다.메모리 효율이 더 높은 다른 표현으로는 텍스트 방정식과 이진 의사결정 다이어그램이 있습니다.

디지털 전자기기에서 진리표의 응용

디지털 전자 및 컴퓨터 과학(응용 논리 공학 및 수학 분야)에서 진리표는 논리 게이트 또는 코드를 사용하지 않고 기본 부울 연산을 입력과 출력의 단순 상관 관계로 줄이는 데 사용될 수 있습니다.예를 들어 이진 덧셈은 진리표와 함께 나타낼 수 있습니다.

이진 덧셈
$A$	$B$	$C$	$R$
T	T	T	F
T	F	F	T
F	T	F	T
F	F	F	F

여기서 A는 첫 번째 피연산자, B는 두 번째 피연산자, C는 캐리 자리, R은 결과입니다.

이 진리표는 왼쪽에서 오른쪽으로 읽힙니다.

값 쌍(A,B)은 값 쌍(C,R)과 같습니다.
또는 이 예제의 경우 A + B와 같은 결과 R을 휴대용 C로 표시합니다.

이 표는 이 연산을 구현하는 데 필요한 논리 연산을 설명하는 것이 아니라 단순히 값을 출력하는 입력의 기능을 지정합니다.

결과와 관련하여, 이 예는 산술적으로 모듈로 2 이진 덧셈으로 간주될 수 있으며, 배타적 또는 (배타적 분배) 이진 논리 연산과 논리적으로 동등합니다.

이 경우 1s 및 0s와 같이 매우 간단한 입력 및 출력에만 사용할 수 있습니다.그러나 입력에 대해 가질 수 있는 값 유형의 수가 증가하면 진리표의 크기가 증가합니다.

예를 들어, 덧셈 연산에서 하나는 두 개의 피연산자, 즉 A와 B가 필요합니다.각각은 0 또는 1의 두 값 중 하나를 가질 수 있습니다.이 두 값의 조합 수는 2x2 또는 4개입니다.결과는 C와 R의 4가지 출력입니다.만약 한 개가 베이스 3을 사용한다면, 크기는 3×3, 즉 9개의 가능한 출력으로 증가할 것입니다.

위의 첫 번째 " 덧셈" 예는 반 덧셈이라고 불립니다.풀애더는 이전 작업에서 다음 애더에 대한 입력으로 운반이 제공되는 경우를 말합니다.따라서 완전 가산기의 논리를 설명하기 위해서는 8개 행으로 구성된 진리표가 필요합니다.

ABC* C R 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0C* = 이전 가산기에서 이월

역사

어빙 아넬리스의 연구에 따르면 C.S. 피어스는 진리표 ^[5]행렬을 고안한 최초의 논리학자(1883년)로 보입니다.

Peirce의 논문 요약본:

1997년 존 쇼스키는 버트런드 러셀의 1912년 "논리적 원자론의 철학" 진리표 행렬에 관한 강의의 타자본의 한 페이지를 발견했습니다.부정의 행렬은 러셀의 행렬이며, 그와 함께 루트비히 비트겐슈타인의 손에 있는 물질적 함의의 행렬입니다.1893년 피어스가 작곡한 것으로 확인된 미발표 원고에는 존 쇼스키가 발견한 물질적 함의에 대한 행렬과 동등한 진리표 행렬이 포함되어 있는 것으로 나타납니다.1885년 미국 수학 저널에 등장한 피어스의 "논리의 대수에 관하여: 표기 철학에 대한 공헌"의 구성과 관련하여 1883-84년에 작곡된 것으로 확인된 피어스의 미발표 원고에는 조건에 대한 간접적인 진리표의 예가 포함되어 있습니다.

참고 항목

메모들

^ 표기법에 대한 정보는 (Bocheinski 1959), (Enderton 2001), 그리고 (Quine 1982)에서 찾을 수 있습니다.
^ 좌/우 항등식(XOR, AND, XNOR, OR)을 갖는 연산자도 연관성이 있기 때문에 교환 모노이드입니다.이러한 구별은 논리학의 단순한 논의에서는 무관할 수 있지만, 더 발전된 수학에서는 상당히 중요할 수 있습니다.예를 들어, 범주 이론에서 농축 범주는 모노이드 이상으로 농축된 기본 범주로 설명되며, 이러한 연산자는 농축에 사용될 수 있습니다.

참고문헌

^ 엔더튼 2001
^ von Wright, Georg Henrik (1955). "Ludwig Wittgenstein, A Biographical Sketch". The Philosophical Review. 64 (4): 527–545 (p. 532, note 9). doi:10.2307/2182631. JSTOR 2182631.
^ Post, Emil (July 1921). "Introduction to a general theory of elementary propositions". American Journal of Mathematics. 43 (3): 163–185. doi:10.2307/2370324. hdl:2027/uiuo.ark:/13960/t9j450f7q. JSTOR 2370324.
^ ^a ^b Wittgenstein, Ludwig (1922). "Proposition 5.101" (PDF). Tractatus Logico-Philosophicus.
^ Anellis, Irving H. (2012). "Peirce's Truth-functional Analysis and the Origin of the Truth Table". History and Philosophy of Logic. 33: 87–97. doi:10.1080/01445340.2011.621702. S2CID 170654885.

인용작품

Bocheński, Józef Maria (1959). A Précis of Mathematical Logic. Translated by Bird, Otto. D. Reidel. doi:10.1007/978-94-017-0592-9. ISBN 978-94-017-0592-9.
Enderton, H. (2001). A Mathematical Introduction to Logic (2nd ed.). Harcourt Academic Press. ISBN 0-12-238452-0.
Quine, W.V. (1982). Methods of Logic (4th ed.). Harvard University Press. ISBN 978-0-674-57175-4.

외부 링크

"Truth table", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
Truth Tables, Tautology 및 논리적 동등성
Anellis, Irving H. (2011). "Peirce's Truth-functional Analysis and the Origin of Truth Tables". arXiv:1108.2429 [math.HO].
진리표를 부울 식으로 변환

[4] 표기법에 대한 정보는 (Bocheinski 1959), (Enderton 2001), 그리고 (Quine 1982)에서 찾을 수 있습니다.

[5] 좌/우 항등식(XOR, AND, XNOR, OR)을 갖는 연산자도 연관성이 있기 때문에 교환 모노이드입니다.이러한 구별은 논리학의 단순한 논의에서는 무관할 수 있지만, 더 발전된 수학에서는 상당히 중요할 수 있습니다.예를 들어, 범주 이론에서 농축 범주는 모노이드 이상으로 농축된 기본 범주로 설명되며, 이러한 연산자는 농축에 사용될 수 있습니다.

[1] 엔더튼 2001

[2] von Wright, Georg Henrik (1955). "Ludwig Wittgenstein, A Biographical Sketch". The Philosophical Review. 64 (4): 527–545 (p. 532, note 9). doi:10.2307/2182631. JSTOR 2182631.

[3] Post, Emil (July 1921). "Introduction to a general theory of elementary propositions". American Journal of Mathematics. 43 (3): 163–185. doi:10.2307/2370324. hdl:2027/uiuo.ark:/13960/t9j450f7q. JSTOR 2370324.

[tlp5.101-6] Wittgenstein, Ludwig (1922). "Proposition 5.101" (PDF). Tractatus Logico-Philosophicus.

[Peirce-7] Anellis, Irving H. (2012). "Peirce's Truth-functional Analysis and the Origin of the Truth Table". History and Philosophy of Logic. 33: 87–97. doi:10.1080/01445340.2011.621702. S2CID 170654885.

[1]

[2]

[3]

[note 1]

[4]

[5]

Search

진리표

네임스페이스

더

목차