맨위로가기

진리표

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

1. 개요

진리표는 논리 연산의 결과를 시각적으로 나타내는 표로, 찰스 샌더스 퍼스가 1883년에 처음 고안한 것으로 알려져 있다. 루트비히 비트겐슈타인이 1921년 출판한 '논리 철학 논고'에서 진리 함수를 설명하는 데 사용하면서 널리 알려졌으며, 단항 및 이항 연산을 포함한 다양한 논리 연산의 결과를 표현하는 데 사용된다. 진리표는 논리적 동치 증명, 디지털 회로 설계, 디지털 전자공학 등 다양한 분야에 응용되며, 입력 변수가 증가함에 따라 표의 크기가 지수적으로 증가하는 특징을 갖는다. 진리표는 명제 변수의 진리값 조합을 체계적으로 나타내며, 번갈아 작성하거나 조합하는 방법으로 작성할 수 있다.

2. 역사

루트비히 비트겐슈타인이 1921년 논리 철학 논고를 출판하여 진리 함수를 논할 때 사용하면서 널리 알려지게 되었다.[11] 그러나 찰스 샌더스 퍼스를 비롯한 다른 논리학자들도 이미 초기 형태를 고안한 바 있으며, 에밀 포스트 역시 비트겐슈타인과는 독립적으로 진리표 체계를 완성하였다.

2. 1. 초기 형태

어빙 아넬리스의 연구에 따르면, 1883년에 찰스 샌더스 퍼스가 진리표 행렬을 고안한 최초의 논리학자로 보인다.[4] 1997년, 존 쇼스키는 버트런드 러셀의 1912년 강의 "논리적 원자론의 철학"의 타이핑된 기록에서 진리표 행렬을 발견했다. 부정에 대한 행렬은 러셀의 것이고, 그 옆에는 루트비히 비트겐슈타인의 손으로 쓴 물질적 함의에 대한 행렬이 있었다. 1893년에 퍼스가 작성한 것으로 확인된 미출판 원고에는 존 쇼스키가 발견한 물질적 함의에 대한 행렬과 동일한 진리표 행렬이 포함되어 있음이 밝혀졌다. 1883–84년에 작성된 것으로 확인된 퍼스의 미출판 원고에는 조건문의 간접 진리표 예시가 포함되어 있는데, 이는 1885년 ''미국 수학 저널''에 실린 퍼스의 "논리 대수학에 관하여: 표기법 철학에 대한 기여"의 작성을 위한 것이었다.[4]

2. 2. 독립적 발전과 확산

루트비히 비트겐슈타인이 1921년 논리 철학 논고를 출판하여 진리 함수를 논할 때 사용하면서 널리 알려지게 되었다.[11] 그러나 찰스 샌더스 퍼스를 비롯한 다른 논리학자들도 이미 초기 형태를 고안한 바 있으며, 에밀 포스트 역시 비트겐슈타인과는 독립적으로 진리표 체계를 완성하였다.

어빙 아넬리스의 연구에 따르면, 1883년에 C.S. 퍼스가 진리표 행렬을 고안한 최초의 논리학자로 보인다.[4] 1997년, 존 쇼스키는 버트런드 러셀의 1912년 강의 "논리적 원자론의 철학"의 타이핑된 기록에서 진리표 행렬을 발견했는데, 부정에 대한 행렬은 러셀의 것이고 그 옆에는 루트비히 비트겐슈타인이 직접 쓴 물질적 함의에 대한 행렬이 있었다.[4]

논리-철학 논고 5.101절에서[11] 비트겐슈타인은 진리표를 다음과 같이 나열했다.

진리값연산자연산 이름논고[12]
0(F F F F)(p, q)⊥거짓Opq모순p 그리고 not p; 그리고 q 그리고 not q
1(F F F T)(p, q)NORp ↓ qXpq논리합 부정p도 q도 아님
2(F F T F)(p, q)↚p ↚ qMpq역 비함축q 그리고 not p
3(F F T T)(p, q)¬p, ~p¬pNp, Fpq부정not p
4(F T F F)(p, q)↛p ↛ qLpq물질적 비함축p 그리고 not q
5(F T F T)(p, q)¬q, ~q¬qNq, Gpq부정not q
6(F T T F)(p, q)XORp ⊕ qJpq배타적 논리합p 또는 q, 하지만 둘 다는 아님
7(F T T T)(p, q)NANDp ↑ qDpq논리곱 부정p와 q 둘 다 아님
8(T F F F)(p, q)ANDp ∧ qKpq논리곱p 그리고 q
9(T F F T)(p, q)XNORp iff qEpq논리적 쌍조건자만약 p면 q; 그리고 만약 q면 p
10(T F T F)(p, q)qqHpq투영 함수q
11(T F T T)(p, q)p → q만약 p면 qCpq물질적 함축만약 p면 q
12(T T F F)(p, q)ppIpq투영 함수p
13(T T F T)(p, q)p ← q만약 q면 pBpq역 함축만약 q면 p
14(T T T F)(p, q)ORp ∨ qApq논리합p 또는 q
15(T T T T)(p, q)⊤참Vpq항진명제만약 p면 p; 그리고 만약 q면 q


3. 기본 논리 연산

진리표는 여러 논리 연산의 결과를 표현하는 데 사용된다.

두 개의 불리언 변수 P와 Q의 가능한 16가지 진리 함수 중 가장 일반적으로 사용되는 7가지에 대한 정의는 다음과 같다.[9]

PQP \land QP \lor QP\ \underline{\lor}\ QP\ \underline{\land}\ QP \Rightarrow QP \Leftarrow QP \Leftrightarrow Q
TTTTFTTTT
TFFTTFFTF
FTFTTFTFF
FFFFFTTTT
PQAND(결합)OR(분리)XOR(배타적 OR)XNOR(배타적 NOR)조건부
"if-then"		조건부
"if"		쌍조건부
"if-and-only-if"



축약된 형태의 진리표도 사용될 수 있는데, 행 머리글과 열 머리글이 피연산자를 지정하고 표 셀이 결과를 지정하는 방식이다. 예를 들어 불 대수에서는 다음과 같은 표기법을 사용한다.[9]

{|

|-

|

|

∧TF
TTF
FFF



|

|

∨TF
TTT
FTF



|}

이러한 표기법은 연산이 교환적일 때 유용하다. 여기서 T는 참, F는 거짓을 의미한다.

다음은 두 개의 부울 변수 ''p''와 ''q''에 대한 16개의 가능한 모든 진리 함수를 정의하는 확장된 진리표이다.[9]

:

pqstyle="background:black" |거짓0NOR1↚2¬p3NIMPLY4¬q5XOR6NAND7AND8XNOR9q10IMPLY11p12←13OR14참15
TTstyle="background:black" |FFFFFFFFTTTTTTTT
TFstyle="background:black" |FFFFTTTTFFFFTTTT
FTstyle="background:black" |FFTTFFTTFFTTFFTT
FFstyle="background:black" |FTFTFTFTFTFTFTFT
colspan="19" style="background:black" |
교환 법칙style="background:black" |✓✓✓✓✓✓✓✓
결합 법칙style="background:black" |✓✓✓✓✓✓✓✓
수반 연산자style="background:black" |F0NOR1↛4¬q5↚2¬p3XOR6NAND7AND8XNOR9p12←13q10→11OR14T15
부정style="background:black" |T15OR14←13p12IMPLY11q10XNOR9AND8NAND7XOR6¬q5NIMPLY4¬p3↚2NOR1F0
쌍대 연산style="background:black" |T15NAND7→11¬p3←13¬q5XNOR9NOR1OR14XOR6q10↚2p12↛4AND8F0
왼쪽 항등원style="background:black" |FFTTT,FTF
오른쪽 항등원style="background:black" |FFTTT,FTF



여기서[10]

:T = 참

:F = 거짓

:위첨자 0부터 15는 4개의 진릿값을 F = 0과 T = 1로 하는 이진수로 읽은 결과이다.

:'''Com''' 행은 연산자 '''op'''가 교환 법칙 - '''P op Q = Q op P'''를 따르는지 여부를 나타낸다.

:'''Assoc''' 행은 연산자 '''op'''가 결합 법칙 - '''(P op Q) op R = P op (Q op R)'''를 따르는지 여부를 나타낸다.

:'''Adj''' 행은 '''P op Q = Q op2 P'''를 만족하는 연산자 '''op2'''를 보여준다.

:'''Neg''' 행은 '''P op Q = ¬(P op2 Q)'''를 만족하는 연산자 '''op2'''를 보여준다.

:'''Dual''' 행은 T를 F로, AND를 OR로 바꾸어 얻은 쌍대 연산을 보여준다.

:'''L id''' 행은 연산자에 왼쪽 항등원이 있는 경우 - '''I op Q = Q'''를 만족하는 값 '''I'''를 보여준다.

:'''R id''' 행은 연산자에 오른쪽 항등원이 있는 경우 - '''P op I = P'''를 만족하는 값 '''I'''를 보여준다.

3. 1. 단항 연산

단항 연산은 하나의 입력값에 대해 연산을 수행한다. 대표적인 단항 연산에는 항등(identity)과 부정(negation)이 있다.

  • 항등(identity)은 입력값을 그대로 출력한다. 즉, 입력값 p에 대한 출력값은 p이다.


pp
TT
FF


  • 부정(negation, NOT)은 입력값의 반대 진리값을 출력한다. 입력값이 참이면 거짓을, 거짓이면 참을 출력한다. NOT p는 ¬p, Np, Fpq, ~p 등으로 표기한다.


p¬p
TF
FT


3. 2. 이항 연산

(p ∧ q)OR
(p ∨ q)XOR
(p ⊕ q)XNOR
(p ↔ q)IMPLY
(p → q)NAND
(p ↑ q)NOR
(p ↓ q)TTTTFTTFFTFFTTFFTFFTFTTFTTFFFFFFTTTT



이진 연산은 행 머리글과 열 머리글이 피연산자를 지정하고 표 셀이 결과를 지정하는 축약된 형태의 진리표로도 표현할 수 있다. 예를 들어 불 대수는 다음과 같이 축약된 진리표를 사용한다.

{|

|-

|

|

∧TF
TTF
FFF



|

|

∨TF
TTT
FTF



|}

이 표기법은 연산이 교환적일 때 유용하다. 행이 첫 번째 피연산자이고 열이 두 번째 피연산자임을 추가로 지정할 수 있다. 축약된 표기법은 논리의 다중 값 확장을 논의할 때 특히 유용하며, 필요한 행의 수를 줄여준다. 또한 표에서 값의 분포를 빠르게 인식할 수 있게 해준다.

진리표는 디지털 회로 내에서 하드웨어 룩업 테이블(LUT)의 기능을 지정하는 데 사용된다. n-입력 LUT의 경우 진리표는 2n개의 값을 가지며, LUT에 대한 불 대수 함수를 완전히 지정한다. 각 부울 값을 비트로, 이진법의 이진수로 표현함으로써 진리표 값은 전자 설계 자동화(EDA) 소프트웨어에서 정수 값으로 효율적으로 인코딩될 수 있다. 예를 들어, 32비트 정수는 최대 5개의 입력을 가진 LUT에 대한 진리표를 인코딩할 수 있다.

진리표는 부울 함수를 인코딩하는 간단하고 직관적인 방법이지만, 입력 수가 증가함에 따라 크기가 지수적 성장하므로 입력 수가 많은 함수에는 적합하지 않다. 텍스트 방정식과 이진 결정 다이어그램은 더 메모리 효율적인 표현이다.

두 개의 이진 변수에 대한 가능한 진리 함수는 16개이다.

4. 응용

진리표는 디지털 회로에서 룩업 테이블(LUT)의 기능을 지정하는 데 사용된다. n-입력 LUT의 진리표는 2n개의 값을 가지며, LUT에 대한 불 대수 함수를 완전히 정의한다. 진리표 값은 전자 설계 자동화(EDA) 소프트웨어에서 정수 값으로 효율적으로 인코딩될 수 있다. 32비트 정수는 최대 5개의 입력을 가진 LUT에 대한 진리표를 인코딩할 수 있다.

LUT의 출력 값은 입력 값을 기반으로 비트 인덱스 ''k''를 계산하여 얻을 수 있다. 이때 LUT의 출력 값은 정수의 ''k''번째 비트이다. ''n''개 부울 입력 값(배열 자료 구조)이 주어졌을 때, LUT 출력 값을 평가하려면 진리표 출력 값의 비트 인덱스를 계산한다. ''i''번째 입력이 참이면 V_i = 1, 거짓이면 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이다.

진리표는 부울 함수를 인코딩하는 간단하고 직관적인 방법이지만, 입력 수가 증가하면 크기가 지수적으로 증가하여 입력 수가 많은 함수에는 적합하지 않다. 텍스트 방정식과 이진 결정 다이어그램은 더 메모리 효율적인 표현이다.

4. 1. 논리적 동치 증명

진리표는 다른 많은 논리적 동치를 증명하는 데 사용될 수 있다. 예를 들어, 다음 진리표를 보자.

(p → q) ≡ (¬p ∨ q)
pq¬p¬p ∨ qp → q
TTFTT
TFFFF
FTTTT
FFTTT



이것은 p → q가 ¬p ∨ q와 논리적 동치임을 보여준다.

4. 2. 디지털 논리

진리표는 디지털 회로에서 룩업 테이블(LUT)의 기능을 지정하는 데 사용된다. n-입력 LUT의 진리표는 2n개의 값을 가지며, LUT에 대한 불 대수 함수를 완전히 정의한다. 진리표 값은 전자 설계 자동화(EDA) 소프트웨어에서 정수 값으로 효율적으로 인코딩될 수 있다.

32비트 정수는 최대 5개의 입력을 가진 LUT에 대한 진리표를 인코딩할 수 있다.

LUT의 출력 값은 입력 값을 기반으로 비트 인덱스 ''k''를 계산하여 얻을 수 있다. 이때 LUT의 출력 값은 정수의 ''k''번째 비트이다. ''n''개 부울 입력 값(배열 자료 구조)이 주어졌을 때, LUT 출력 값을 평가하려면 진리표 출력 값의 비트 인덱스를 계산한다. ''i''번째 입력이 참이면 V_i = 1, 거짓이면 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이다.

진리표는 부울 함수를 인코딩하는 간단하고 직관적인 방법이지만, 입력 수가 증가하면 크기가 지수적으로 증가하여 입력 수가 많은 함수에는 적합하지 않다. 텍스트 방정식과 이진 결정 다이어그램은 더 메모리 효율적인 표현이다.

4. 3. 디지털 전자공학

진리표는 논리 게이트나 코드를 사용하지 않고 기본 부울 연산을 입력과 출력의 간단한 관계로 나타내는 데 사용될 수 있다. 예를 들어, 이진 덧셈은 진리표로 표현될 수 있다.

이진 연산자의 경우, 행 머리글과 열 머리글이 피연산자를 지정하고 표 셀이 결과를 지정하는 축약된 형태의 진리표도 사용된다. 예를 들어, 불 대수는 다음과 같은 축약된 진리표 표기법을 사용한다.

∧TF
TTF
FFF



∨TF
TTT
FTF



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

진리표는 디지털 회로 내에서 하드웨어 룩업 테이블(LUT)의 기능을 지정하는 데 사용된다. n-입력 LUT의 경우 진리표는 2''n''개의 값을 가진다. 각 부울 값을 비트로, 이진법의 이진수로 표현함으로써 진리표 값은 전자 설계 자동화(EDA) 소프트웨어에서 정수 값으로 효율적으로 인코딩될 수 있다. 예를 들어, 32비트 정수는 최대 5개의 입력을 가진 LUT에 대한 진리표를 인코딩할 수 있다.

진리표의 정수 표현을 사용할 때, LUT의 출력 값은 LUT의 입력 값을 기반으로 비트 인덱스 ''k''를 계산하여 얻을 수 있으며, 이 경우 LUT의 출력 값은 정수의 ''k''번째 비트이다. 예를 들어, ''n''개의 부울 입력 값의 배열 자료 구조가 주어졌을 때 LUT의 출력 값을 평가하기 위해, 진리표의 출력 값의 비트 인덱스는 다음과 같이 계산할 수 있다. ''i''번째 입력이 참이면 Vi = 1로 하고, 그렇지 않으면 Vi = 0으로 한다. 그러면 진리표의 이진 표현의 ''k''번째 비트가 LUT의 출력 값이며, 여기서 k = V0 × 20 + V1 × 21 + V2 × 22 + ... + Vn × 2n이다.

진리표는 부울 함수를 인코딩하는 간단하고 직관적인 방법이지만, 입력 수가 증가함에 따라 크기가 지수적 성장하므로 입력 수가 많은 함수에는 적합하지 않다. 더 메모리 효율적인 다른 표현으로는 텍스트 방정식과 이진 결정 다이어그램이 있다.

5. 진리표 작성 방법

진리표를 작성하는 방법에 대해 저자마다 다른 권장 사항이 있지만, 명제 변수를 나타내는 ''가이드 열''[6]''과 관련하여 논리적으로 중요한 차이는 없다.[5]

5. 1. 번갈아 작성하는 방법 (Alternating method)

랜더 대학교(Lander University)의 리 아치(Lee Archie)는 출판된 진리표에서 일반적으로 사용되는 다음과 같은 절차를 권장한다.[6]

1. 변수(명제)를 알파벳 순서로 작성한다.

2. 필요한 행의 수는 2n이다. (n은 변수의 개수) (예: 세 개의 변수, 23 = 8).

3. 가장 오른쪽 열에서 시작하여 행이 소진될 때까지 '''T'''와 '''F'''를 번갈아 가며 적는다.

4. 그 다음 왼쪽 열로 이동하여 행이 소진될 때까지 두 개의 '''T'''와 '''F'''를 번갈아 가며 적는다.

5. 그런 다음 다음 왼쪽 열로 이동하여 '''T'''와 '''F'''의 개수를 두 배로 늘리면서 완료될 때까지 반복한다.[6]

이 방법은 스티븐 콜 클리니(Stephen Cole Kleene)가 생성한 "''P ⊃ (Q ∨ R ⊃ (R ⊃ ¬P))''"에 대한 다음과 같은 진리표를 생성한다:[7]

PQRP ⊃ (Q ∨ R ⊃ (R ⊃ ¬P))
TTTF
TTFT
TFTF
TFFT
FTTT
FTFT
FFTT
FFFT


5. 2. 조합 방법 (Combinatorial method)

콜린 하우슨은 모든 참(T)으로 시작하여, T와 F의 모든 조합을 나열하는 것이 "좋은 실용적인 규칙"이라고 보았다.[5] 예를 들어, 세 개의 명제 A, B, C가 있을 때, প্রথমে তিনটি 명제 모두 참(TTT)인 경우로 시작한다. 그 다음, 두 개의 참과 하나의 거짓(T)을 결합하는 모든 경우(TTF, TFT, FTT)를 나열한다. 이어서 하나의 참과 두 개의 거짓을 결합하는 모든 경우(TFF, FTF, FFT)를 나열하고, 마지막으로 모두 거짓(FFF)인 경우를 나열한다. 복합 명제가 n개의 서로 다른 명제 기호로 구성된 경우, 진리표는 2n개의 행을 갖는다.[5]

이는 콜린 하우슨이 제시한 "(A→C)∧(B→C)와 (A∨B)→C가 진리 함수적으로 동치임을 보여주는" 진리표에서 확인할 수 있다.[5]

ABC(A → C) ∧ (B → C)(A ∨ B) → C
TTTTT
TTFFF
TFTTT
FTTTT
FFTTT
FTFFF
TFFFF
FFFTT


6. 진리표의 크기

만약 입력 변수가 ''n''개 있다면, 해당 변수들의 진리값 조합은 2''n''개가 된다. 주어진 함수는 각 조합에 대해 참 또는 거짓을 반환할 수 있으므로, ''n''개의 변수를 갖는 서로 다른 함수의 수는 이중 지수 22''n''이다.

n2n22n
012
124
2416
38256
41665,536
5324,294,967,296
66418,446,744,073,709,551,616
7128340,282,366,920,938,463,463,374,607,431,768,211,456
8256115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,394,575,840,079,131,296,399,36



세 개 이상의 변수를 갖는 함수의 진리표는 거의 제시되지 않는다.

참조

[1] 간행물 Enderton 2001
[2] 학술지 Ludwig Wittgenstein, A Biographical Sketch
[3] 학술지 Introduction to a general theory of elementary propositions 1921-07
[4] 학술지 Peirce's Truth-functional Analysis and the Origin of the Truth Table 2012
[5] 서적 Logic with trees: an introduction to symbolic logic Routledge 1997
[6] 웹사이트 How to Construct a Truth Table https://philosophy.l[...] 2024-04-05
[7] 서적 Mathematical Logic https://books.google[...] Courier Corporation
[8] 서적 Digital Design, Global Edition Pearson Education, Limited 2018-07-13
[9] 간행물 Bocheński 1959
[10] 문서
[11] 서적 Tractatus Logico-Philosophicus https://www.gutenber[...] 1922
[12] 문서


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com