진실함수

논리학에서 진리 함수는^[1] 진리 값을 입력으로 받아들이고 고유한 진리 값을 출력물로 생성하는 함수다. 즉, 다음과 같다. 진리 함수의 입력과 출력은 모두 진리 값이다. 진리 함수는 항상 정확히 하나의 진리 값을 출력하며, 동일한 진리 값을 입력하면 항상 동일한 진리 값을 출력한다. 대표적인 예가 명제 논리학인데, 여기에서 명제 서술문은 논리적 연결자에 의해 연결된 개별적인 진술을 사용하여 구성된다. 복합 서술문의 진리 값이 구성성명의 진리 값에 의해 전적으로 결정되는 경우, 복합 서술문은 진실 함수라고 불리며, 모든 논리적 연결이다.사용되는 tiv는 실제 기능한다고 한다.^[2]

고전적 명제논리는 모든 진술이 참이거나 거짓인 하나의 진실 가치를 정확히 가지고 있고, 모든 논리 결합자는 진실 기능적(본 통신원의 진실 표와 함께)이므로 모든 복합 진술은 진실 기능적 논리인 것이다.^[3][4] 반면에 모달논리는 진실성이 없다.

개요

복합 문장의 진리 값이 하위 문장의 진리 값의 함수인 경우 논리 결합은 진리 기능적이다. 한 부류의 커넥터는 각각의 구성원이 사실이라면 기능적이다. 예를 들어, "애플은 과일이고 당근은 야채"와 같은 문장이 사실이고, "애플은 과일"과 "당근은 야채"가 각각 사실일 경우에만 사실이고, 그렇지 않을 경우 그것은 거짓이기 때문에 결합 "및"은 진실 기능적이다. 영어와 같은 자연 언어의 일부 연결어는 사실적으로 기능하지 않는다.

"x believe that..." 형식의 커넥티브는 진실로 기능하지 않는 커넥티브의 대표적인 예다. 예시라면 메리는 앨 고어가 2000년 4월 20일 미국의 대통령이라고 잘못 믿고 있지만, 그녀는 달이 초록 치즈로 만들어졌다고 믿지 않는다.

"매리는 앨 고어가 2000년 4월 20일 미국의 대통령이었다고 믿고 있다."

는 동안 사실이다.

"메리는 달이 초록 치즈로 만들어졌다고 믿는다."

거짓이다. 두 경우 모두 구성요소 문장(즉, "Al Gore는 2000년 4월 20일 미국의 대통령이었다", "달은 녹색 치즈로 만들어졌다")은 거짓이지만, "Mary는 그렇게 믿는다"라는 문구를 접두사로 하여 형성된 복합문장은 각각 진실-가치에서 차이가 있다. 즉, "메리는 그렇게 믿고 있다."는 구성요소 문장의 진실 가치에만 의해 결정되는 것이 아니며, 따라서 (단일) 결합체(또는 단일성이므로 단순히 연산자)는 비기능적이다.

공식의 작성에 사용되는 고전적 논리 커넥티브(예: &, →)의 등급은 진리 기능적이다. 논쟁으로서의 다양한 진실 가치에 대한 그들의 가치는 대개 진실 표에 의해 주어진다. 진리 기능 명제 미적분학은 공식으로 진리 또는 거짓으로 해석될 수 있는 공식적인 시스템이다.

이항 진실 함수 표

두 개의 값 논리에서는 두 개의 입력 P와 Q 중에서 부울 함수라고도 하는 16개의 가능한 진리 함수가 있다. 이러한 함수 중 어느 것이든 고전적 논리에서 어떤 논리 결합의 진리표에 해당하며, 그 논리의 하나 또는 둘 다에 의존하지 않는 함수 등 몇 가지 퇴보적인 경우를 포함한다. 간결함을 위하여 다음의 진리표에서는 진리와 거짓을 각각 1과 0으로 표기한다.

모순/거짓말 표기법 등가 공식 진리표 벤 다이어그램 $\displaystyle \bot }$ "하단" P ∧ ¬ ¬ ¬ opq Q 0 1 P 0 0 0 1 0 0	Tautology/True 표기법 등가 공식 진리표 벤 다이어그램 $\displaystyle \top }$ "상단" P ∨ ¬ ¬ ¬ Vpq Q 0 1 P 0 1 1 1 1 1
프로포지션 P 표기법 등가 공식 진리표 벤 다이어그램 P p 입크 Q 0 1 P 0 0 0 1 1 1	P의 부정 표기법 등가 공식 진리표 벤 다이어그램 ¬P ~P Np Fpq Q 0 1 P 0 1 1 1 0 0
제안 Q 표기법 등가 공식 진리표 벤 다이어그램 Q q hpq Q 0 1 P 0 0 1 1 0 1	Q의 부정 표기법 등가 공식 진리표 벤 다이어그램 ¬Q ~Q Nq Gpq Q 0 1 P 0 1 0 1 1 0
접속사 표기법 등가 공식 진리표 벤 다이어그램 P ∧ Q P&Q P·Q P와 Q P ↛Q ¬P ↚ Q ¬P ↓ ↓Q Kpq Q 0 1 P 0 0 0 1 0 1	대체 거부 표기법 등가 공식 진리표 벤 다이어그램 P ↑ Q PQ P 낸드 Q P → ¬Q ¬P ← Q ¬P ∨ ∨Q Dpq Q 0 1 P 0 1 1 1 1 0
분리 표기법 등가 공식 진리표 벤 다이어그램 P ∨ Q P 또는 Q P ← ¬Q ¬P → Q ¬P ↑ ↑Q ¬(¬P ∧ ∧ qQ) 압크 Q 0 1 P 0 0 1 1 1 1	접합부거부 표기법 등가 공식 진리표 벤 다이어그램 P ↓ Q P NOR Q P ↚ ¬Q ¬P ↛ Q ¬P ∧ ∧Q 엑스펙 Q 0 1 P 0 1 0 1 0 0
재료비복제 표기법 등가 공식 진리표 벤 다이어그램 P ↛ Q P$\displaystyle \not \supset }$Q P$(\displaystyle )}$Q P ∧ ¬Q ¬P ↓ Q ¬P ↚ ↚Q Lpq Q 0 1 P 0 0 0 1 1 0	물질적 함축성 표기법 등가 공식 진리표 벤 다이어그램 P → Q P ⊃ Q P$\displaystyle \leq }$Q P ↑ ¬Q ¬P ∨ Q ¬P ← ←Q Cpq Q 0 1 P 0 1 1 1 0 1
컨버스 비임플렉스 표기법 등가 공식 진리표 벤 다이어그램 P ↚ Q P$\displaystyle \not \display$Q P$(\displaystyle <)$Q P ↓ ¬Q ¬P ∧ Q ¬P ↛ ↛Q 엠피크 Q 0 1 P 0 0 1 1 0 0	컨버스 시사 표기법 등가 공식 진리표 벤 다이어그램 P ← Q P ⊂ Q P$\displaystyle \geq }$Q P ∨ ¬Q ¬P ↑ Q ¬P → ¬Q Bpq Q 0 1 P 0 1 0 1 1 1
배타적 분리 표기법 등가 공식 진리표 벤 다이어그램 P ↮ Q P ≢ Q P ⨁ Q P XOR Q P${\displaystyle }$£ ${\displaystyle \왼쪽$ 화살표 $}$ $$\Q ¬P 파운드${\displaystyle \왼쪽$ 화살표 $}$ ¬P ↮ ↮Q jpq Q 0 1 P 0 0 1 1 1 0	바이콘디렉트 표기법 등가 공식 진리표 벤 다이어그램 P${\displaystyle \왼쪽 화살표 }$Q P ≡ Q P XNOR Q P IFF Q P ↮ ¬Q ¬P ↮ Q ¬P 파운드${\displaystyle \좌우타로우 \}$ ¬$$Q 에픽 Q 0 1 P 0 1 0 1 0 1

기능 완성도

함수는 구성으로 표현될 수 있기 때문에, 진리 기능 논리 미적분학에는 위에서 언급한 모든 기능이 기능적으로 완성되기 위해 전용 기호가 있을 필요는 없다. 이것은 명제 미적분학에서 특정 복합성문의 논리적 등가성으로 표현된다. 예를 들어 고전논리는 P → Q에 해당하는 equivalentP ∨ Q를 가지고 있다. 따라서 "실행"(not)과 "실행"(또는)이 이미 사용 중인 경우 고전적 기반 논리 시스템에는 조건부 연산자 "→"가 필요하지 않다.

명제 미적분학에서 표현할 수 있는 모든 문장을 표현할 수 있는 최소한의 연산자 집합을 기능적으로 최소 완성 집합이라고 한다. 최소 완성 연산자 집합은 NAND 단독 {number} 및 NOR 단독 {number}이(가) 달성한다.

다음은 아리티가 2를 초과하지 않는 최소한의 기능적으로 완전한 연산자 집합이다.^[5]

원소

{↑}, {↓}.

두 원소

${\displaystyle \{\vee ,\neg \}}$, ${\displaystyle \{\wedge ,\neg \}}$, ${\displaystyle \{\to ,\neg \}}$, ${\displaystyle \{\gets ,\neg \}}$, ${\displaystyle \{\to ,\bot \}}$, ${\displaystyle \{\gets ,\bot \}}$, ${\displaystyle \{\to ,\nle$$ftrightarrow \}}$, ${\displaystyle \{\gets ,\nleftrightarrow \}}$, ${\displaystyle \{\to ,\nrightarrow \}}$, ${\displaystyle \{\to ,\nleftarrow \}}$, ${\displaystyle \{\gets ,\nrightarrow \}}$, ${\displaystyle \{\gets ,\nleftarrow \}}$, ${\displaystyle \$${\nrightarrow ,\neg \}}$, ${\displaystyle \{\nleftarrow ,\neg \}}$, ${\displaystyle \{\nrightarrow ,\top \}}$, ${\displaystyle \{\nleftarrow ,\top \}}$, ${\displaystyle \{\nrightarrow ,\leftrightarrow \}}$, ${\displaystyle \{\nleftarrow ,\leftrightarrow \}}$.

삼원소

${\displaystyle \{\lor ,\leftrightarrow ,\bot \}}$, ${\displaystyle \{\lor ,\leftrightarrow ,\nleftrightarrow \}}$, ${\displaystyle \{\lor ,\nleftrightarrow ,\top \}}$, ${\displaystyle \{\land ,\leftrightarrow ,\bot \}}$, ${\displaystyle \{\land ,\lef$$triightarrow ,\nfrightarrow$ $\backslash \}\},$${\displaystyle }${ ${\displaystyle \wedge ,}$ ${\displaystyle \nleftrightarrow ,\mathrm{\top \}}}$ ${\displaystyle \{\land,\nfrightarrow$ $,\backslash \}\}\}.$

대수적 특성

일부 진실 함수는 해당 결합체를 포함하는 이론에서 표현될 수 있는 속성을 가지고 있다. 이항 진리 함수(또는 그에 상응하는 논리 결합체)가 가질 수 있는 속성 중 일부는 다음과 같다.

• 연관성: 두 개 이상의 동일한 연관성을 연속해서 포함하는 식 내에서, 피연산자의 순서가 변경되지 않는 한 연산의 순서는 중요하지 않다.
• 동시성: 연결부의 피연산자는 표현식의 진실 값에 영향을 주지 않고 교환될 수 있다.
• 분배성: ·에 의해 표시된 결합체는 모든 피연산자 a, b, c에 대해 a · (b + c) = (a · b) + (a · c)이면 +로 표시된 다른 결합체에 분배된다.
• 특이점: 연산의 피연산자가 같을 때마다, 연결자는 피연산자에게 그 결과로 준다. 즉, 작전은 진실보존과 거짓보존이다(아래 참조).
• 흡수: 모든 연산자 a, b에 대해 ${\displaystyle \mathrm{for}}$ (${\displaystyle (b}$)${\displaystyle }$=$$${\displaystyle \vee }$ ( ${\displaystyle (}$ ${\displaystyle b}$ ) = ∨ ( ${\displaystyle \wedge }$ b${\displaystyle }$)${\displaystyle }$= ${\displaystyle a\land (a\lor b)=a}$인 경우, connectives ives, ${\$land$$ b$}$의 쌍이 흡수 $법칙$을 만족한다.

다음의 다섯 가지 속성 각각에 대해 적어도 한 명 이상의 구성원이 없는 경우에만 일련의 진실 함수가 기능적으로 완전하다.

• 단조로운: 만약_11n f(a₁, ..., a_n) 모든 a₁, ..., a_n, a, b₁, ..., b_nnn, b₂₂ { {0₁,1}(예: ${\displaystyle \vee ,}$ ∨,${\displaystyle }$⊤,${\displaystyle \mathrm{}}$⊤, ⊥,${\displaystyle \mathrm{}}$⊥, ⊥, ⊥, {\displaystyle $\vee,\wedge,\top,\bot$ $\}).$
• appine: 각 변수에 대해 값을 변경하면 다른 모든 변수의 모든 고정 값에 대해 항상 또는 절대 연산의 진실-값이 변경되지 않는다. $예$: $\neg ,{\displaystyle \mathrm{}}$↔,$$↔,${\displaystyle <img\; alt="\{\backslash displaystyle\; \backslash neg\; ,\backslash leftrightarrow\; \}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/1382b6d3098dcd67af1e32e0d3650df790dd143b"\; style="vertical-align:\; -0.671ex;\; width:4.908ex;\; height:2.176ex;"\; papago-attr-id="210">}$↔, ${\displaystyle \mathrm{\top ,}}$ ⊥,${\displaystyle }${, ${$ {\$displaystyle \not$\left \$riftrightarrow,\top,\bot$ $\}.$
• 자체 이중: 작업에 대한 진리값 할당을 진리표에서 위에서 아래로 읽는 것은 아래로부터 위로 읽는 보완책을 취하는 것과 같다. 즉, f(¬a₁, ..., ¬a_n) = ¬f(a₁, ..., a_n). 예: $\neg {\displaystyle \mathrm{}}$ ${\displaystyle \neg$
• 사실 확인: 모든 변수에 '참'의 진리 값이 할당되는 해석은 이러한 연산의 결과로 '참'의 진리 값을 산출한다. 예: ${\displaystyle \vee ,}$∧,${\displaystyle \mathrm{\top ,}}$→,${\displaystyle \leftrightarrow ,}${, ${\displaystyle \{,}${, {\$displaystyle \ve,\wedge,\top,\rightarrow,\leftrightarrow,\subset$ $\}.$ (유효성 참조)
• 거짓 확인: 모든 변수에 '거짓'의 진리 값이 할당되는 해석은 이러한 연산의 결과로 '거짓'의 진리 값을 산출한다. 예: ${\displaystyle \vee ,}$\,${\displaystyle }$↮,${\displaystyle \mathrm{\perp ,}}$ ${\displaystyle \not\subset ,}$⊅, ${$ {\$displaystyle \ve,\wedge,\nleft$ rightarrow$,\bot,\not \subset,\not \subsubset }.$ (유효성 참조$)$

아리티

콘크리트 함수는 연산자라고도 할 수 있다. 2개의 값 논리에는 2개의 무효 연산자(정수)와 4개의 단항 연산자, 16개의 이항 연산자, 256개의 삼항 연산자, $2{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {{2n}^{}}^{}}$ ${\$개의 n-ary$$ 연산자가 있다. 3개의 값 논리에는 3개의 무효 연산자(정수)가 있고, 27개의 단항 연산자, 19683개의 이진 연산자, 7625597484987개의 3개의 연산자, ${\displaystyle {3개}^{}}$의 ${\displaystyle {{3n}^{}}^{}}$ ${\$ 3$^{3^{n}}$n-ary$$ 연산자가 있다. k 값 논리에는 k ${\displaystyle {null}^{}}$ 연산자, k $k{\displaystyle {}^{}}$ ${\$ k$^{k}{$k$$$}$ 단항 연산자, k ${\displaystyle {k{}^{}}^{}}$ ${\displaystyle {{k\mathrm{}}^{}}^{}}$ 2$${\$displaystyle$$$k$^{k^{3}}$ 이진$$ 연산자, $k$ ${\displaystyle {k{}^{}}^{}}$ ${\displaystyle {k^{}}^{}}$3 {\$displaysty k^{k^{n}}},$ n-ary$$ 연산자가 있다. k 값 논리에서의 n-ary 연산자는 Z $k{\displaystyle {\mathbb{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$→ ${\displaystyle {}_{}}$ k ${\$\mathb {Z} $_{k}}}}$의 함수다$.$ 따라서 그러한 연산자의 수는 ${\displaystyle {}_{}}$ ${\displaystyle {}^{}{}_{}{}^{{\mathbb{}}_{}^{}}}$ ${\displaystyle {{}_{}^{}}^{}}$ n${\displaystyle {{}_{}^{}}^{}}$= ${\displaystyle {}^{}}$ ${\displaystyle {k^{}}^{}}$ n ${\$}^{{$k^{n}}}}{{k^{$n}}}}}인데$,$ 이것이 위의 숫자들이 도출된 방법이다.

그러나 특정 경지의 운용자 중 일부는 실제로 일부 입력에 대해 낮은 경도 연산을 수행하고 나머지 입력은 무시하는 퇴행형식이다. Out of the 256 ternary boolean operators cited above, ${\displaystyle {\binom {3}{2}}\cdot 16-{\binom {3}{1}}\cdot 4+{\binom {3}{0}}\cdot 2}$ of them are such degenerate forms of binary or lower-arity operators, using the inclusion–exclusion principle. ternary ${\displaystyle \mathrm{연산자}}$ f${\displaystyle (x}$, ${\displaystyle y}$,${\displaystyle z}$ ) =${\displaystyle \mathrm{}}${$$x {\$displaystyle$ f$(x,y,z)=\lnot x}$는 실제로$$ 한 입력에 적용되는 단항 연산자 중 하나이며, 다른 두 입력은 무시한다.

"Not"는 단항 연산자로, 단항 (¬P)이 필요하다. 나머지는 이항 연산자로, 복합성명(P ∧ Q, P ∨ Q, P → Q, P ↔ Q)을 하기 위해 두 개의 용어를 사용한다.

논리 연산자 Ω 집합은 다음과 같이 분리 하위 집합으로 분할할 수 있다.

$\displaystyle \Oomega =\{0}\cup \Oomega_{1}\cup \ldots \cup \Oomega_{j}\cup \ldots \cup \cup \Oomega_{m}\,}$

이 파티션에서 $\Omega {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle j_{}}$ ${\$는 arity j의 연산자 기호 집합이다$$.

보다 친숙한 명제 캘커리에서 $\Omega {\displaystyle \mathrm{}}$ ${\displaystyle \Oomega$ }은$($는) 일반적으로 다음과 같이 분할된다.

무효 연산자: $\Omega {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$=${\displaystyle }${ ${\displaystyle \mathrm{\perp }}$, ${\displaystyle \mathrm{\top }}$ } ${\displaystyle \}}$ ${\displaystyle \Oomega _{0}=\\bot ,\top \}}}$

단일 연산자: $\Omega {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$=${\displaystyle }${ ${\displaystyle \mathrm{\neg }}$ ${\displaystyle \}}$ ${\displaystyle \Oomega _{1}=\{\lnot \}}}$

이진 연산자: $\Omega {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {2\mathrm{}}_{}{}_{}\vee ,}$→${\displaystyle }$↔, ↔, ${\displaystyle \leftrightarrow ,}$↔}$${\$displaystyle \Oomega _{$2}\$supset$\{\$land,\lor,\rightarrow \rightarrow \}}}}}}}}$

구성성의 원리

논리 결합 기호는 진리표를 사용하는 대신 해석 함수와 기능적으로 완전한 진리 기능 집합(Gamut 1991년)을 통해 해석될 수 있으며, 의미 구성 원리에 의해 자세히 설명된다. 내가 해석함수가 되게 하고, Ⅱ, Ⅱ를 임의의 두 문장으로 하고, 진실함수 f를_nand 다음과 같이 정의하게 한다.

• f_nand(T,T) = F; f_nand(T,F) = f_nand(F,T) = f_nand(F,F) = T

그런 다음 편의를 위해 f_not, f_or, f 등을_and f로_nand 정의한다.

• f_not(x) = f_nand(x,x)
• f_or(x,y) = f_nand(f_not(x), f_not(y)
• f_and(x,y) = f_not(x_nand,y)

또는, 대안으로 f_not, f 등을_orand 직접 정의한다.

• f_not(T) = F; f_not(F) = T;
• f_or(T,T) = f_or(T,F) = f_or(F,T) = T; f_or(F,F) = F
• f_and(T,T) = T; f_and(T,F) = f_and(F,T) = f_and(F,F) = F

그러면

등

따라서 S가 논리 결합을 나타내는 논리 기호 v₁...v와_n 비논리적 기호 c₁...c로_n 구성된 일련의 기호로 구성된 문장이라면 I(v₁)의 경우에 한해...I(v_n)는 f_nand${\displaystyle (\mathrm{또는}}$ 다른 기능 전체 $진실$ 기능의 집합)를 통해 v를₁ v로_n 해석할 수 있도록 제공되었고$,$ $그러면{\displaystyle }$I($v)$의 진실-값은 완전히₁ c...c_n, 즉 I(c₁)의 진실-값으로 결정된다$$.I(c_n). 즉, 기대되고 요구된 대로 S는 모든 비논리적 기호에 대한 해석에서만 참이거나 거짓이다.

컴퓨터 공학

논리 연산자는 디지털 회로에서 논리 게이트로 구현된다. 사실상 모든 디지털 회로(주요 예외는 DRAM)는 NAND, NOR, NOT, 전송 게이트에서 구축된다. NAND와 NOR 게이트는 논리적으로 2입력 게이트의 계단식 격자와 동일하지만 일반적인 2입력보다 3입력이 더 많은 게이트는 상당히 일반적이다. 다른 모든 연산자는 위의 논리 게이트 중 2개 이상의 논리적으로 동등한 조합으로 분해하여 실행한다.

"NAND 단독", "NOR 단독", "NOR 및 AND"의 "논리적 동등성"은 튜링 동등성과 유사하다.

모든 진실 기능이 NOR만으로 표현될 수 있다는 사실은 아폴로 유도 컴퓨터로 증명된다.

참고 항목

메모들

참조

• 이 글에는 크리에이티브 커먼스 귀속/공유 앨리케 라이센스에 따라 라이센스가 부여된 PlanetMath의 TrueFunction의 자료가 통합되어 있다.

추가 읽기

• 요제프 마리아 보체스키(1959년)는 프랑스어, 독일어 판본에서 번역한 수학적 논리학의 프리시스(A Précis of Mathematical Logic)로, 네덜란드 남부의 오토 버드(Otto Bird), 도드레흐트(Dordrecht)가 번역했다: D. 레이델
• Alonzo Church(1944), Princeton, NJ: Princeton University Press. 진실 함수 개념에 대한 내역은 소개를 참조하십시오.