진리표

3.1. 단항 연산

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

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

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

3.2. 이항 연산

다음은 두 개의 불리언 변수 P와 Q에 대한 16가지 가능한 진리 함수 중 가장 일반적으로 사용되는 7가지의 정의를 보여주는 진리표이다.

* T 는 '참'을 의미한다.
* F 는 '거짓'을 의미한다.

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

4. 응용

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

LUT의 출력 값은 입력 값을 기반으로 비트 인덱스 k를 계산하여 얻을 수 있다. 이때 LUT의 출력 값은 정수의 k번째 비트이다. n개 부울 입력 값(배열 자료 구조)이 주어졌을 때, LUT 출력 값을 평가하려면 진리표 출력 값의 비트 인덱스를 계산한다. i번째 입력이 참이면 $V\_i\; =\; 1$, 거짓이면 $V\_i\; =\; 0$으로 한다. 그러면 진리표의 이진 표현 k번째 비트가 LUT 출력 값이다. 여기서 $k\; =\; V\_0\; \backslash times\; 2^0\; +\; V\_1\; \backslash times\; 2^1\; +\; V\_2\; \backslash times\; 2^2\; +\; \backslash dots\; +\; V\_n\; \backslash times\; 2^n$이다.

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

4.1. 논리적 동치 증명

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

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

4.2. 디지털 논리

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

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

LUT의 출력 값은 입력 값을 기반으로 비트 인덱스 k를 계산하여 얻을 수 있다. 이때 LUT의 출력 값은 정수의 k번째 비트이다. n개 부울 입력 값(배열 자료 구조)이 주어졌을 때, LUT 출력 값을 평가하려면 진리표 출력 값의 비트 인덱스를 계산한다. i번째 입력이 참이면 $V\_i\; =\; 1$, 거짓이면 $V\_i\; =\; 0$으로 한다. 그러면 진리표의 이진 표현 k번째 비트가 LUT 출력 값이다. 여기서 $k\; =\; V\_0\; \backslash times\; 2^0\; +\; V\_1\; \backslash times\; 2^1\; +\; V\_2\; \backslash times\; 2^2\; +\; \backslash dots\; +\; V\_n\; \backslash times\; 2^n$이다.

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

4.3. 디지털 전자공학

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

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

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

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

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

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

5. 진리표 작성 방법

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

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

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

1. 변수(명제)를 알파벳 순서로 작성한다.
2. 필요한 행의 수는 2ⁿ이다. (n은 변수의 개수) (예: 세 개의 변수, 2³ = 8).
3. 가장 오른쪽 열에서 시작하여 행이 소진될 때까지 T와 F를 번갈아 가며 적는다.
4. 그 다음 왼쪽 열로 이동하여 행이 소진될 때까지 두 개의 T와 F를 번갈아 가며 적는다.
5. 그런 다음 다음 왼쪽 열로 이동하여 T와 F의 개수를 두 배로 늘리면서 완료될 때까지 반복한다.

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

5.2. 조합 방법 (Combinatorial method)

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

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

6. 진리표의 크기

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

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