셰퍼 스트로크

셰퍼 스트로크
낸드
정의
진리표
논리 게이트
정상형식
이분법
결막
절갈킨다항식
포스트의 선반
0-52	아니요.
1시 30분	아니요.
모노톤	아니요.
아핀	아니요.
	v; t;

부울 함수와 명제 미적분학에서 셰퍼 스트로크는 접속사 연산의 부정과 동등한 논리 연산을 나타내며, 통상적인 언어로 "둘 다 아니다"라고 표현한다. 사실상 피연산자 중 적어도 한 명은 허위라고 말하기 때문에 낸드("not and") 또는 대체부정이라고도 한다. 디지털 전자제품에서는 낸드 게이트에 해당한다. 그것은 헨리 M의 이름을 따서 지어졌다. 셰퍼(Sheffer)로 쓰여 ↑ 또는 (그러나, 흔히 분리를 나타내기 위해 사용된 것은 아님)로 쓰여졌다. 보체스키 표기법에서는 Dpq로 표기할 수 있다.

이중은 NOR 연산자(Peirce 화살표 또는 Quine 단검이라고도 한다)이다. 듀얼과 마찬가지로, 다른 논리 연산자 없이, NAND는 논리적인 공식 시스템을 구성하기 위해 자체적으로 사용할 수 있다(NAND 기능적으로 완전하게 만들기). 이 특성은 NAND 게이트를 컴퓨터 프로세서 설계에 사용하는 것을 포함하여 현대 디지털 전자제품에 결정적으로 만든다.

정의

NAND 연산은 두 개의 논리적 값에 대한 논리 연산이다. 그것은 적어도 하나의 명제 중 하나가 거짓인 경우에 한하여 진실의 가치를 산출한다.

진리표

$P\uparrow Q$ $P\uparrow Q$ $P\uparrow Q$ ${\displaystyle P\uparrow$ Q $}($ $P\mathop {|} Q$ $P\mathop {|} Q$ $P\mathop {|} Q$ ${\displaystyle P\mathop$ { } Q $P\mathop {|} Q$ $또는$ Dpq로도 작성됨)의 진리표는 다음과 같다.

$P}$	$(\displaystyle Q}$	$P\uparrow Q}$
T	T	F
T	F	T
F	T	T
F	F	T

논리적 동등성

$P$ $P$ 및 $P$ Q $Q$ 의 셰퍼 스트로크는 이들의 접속사를 부정하는 것이다 $Q$ .

$P\uparrow Q}$	$\왼쪽 화살표$	$\displaystyle \neg(P\land Q)}$
	$\왼쪽 화살표$	$\displaystyle \neg }$

De Morgan의 법칙에 따르면, 이것은 $P$ ${\displaystyle$ P $}$ 과 $Q$ ${\displaystyle$ Q $}$ 의 부정을 분리하는 것과도 같다.

$P\uparrow Q}$	$\왼쪽 화살표$	$\displaystyle \neg P}$	$\displaystyle \lor }$	$\displaystyle \neg Q}$
	$\왼쪽 화살표$		$\displaystyle \lor }$

역사

그 획의 이름은 헨리 M의 이름을 따서 지어졌다. 1913년 미국수학협회의 거래에 뇌졸중을 이용한 부울 알헤브라의 공리화를 제공하는 논문을 발표한 셰퍼는 헌팅턴이 제안논리의 익숙한 운영자(그리고, 또는 그렇지 않음)를 고용함으로써 그 표준제형에 동등함을 증명했다. 부울 알헤브라의 자기이중성 때문에 셰퍼의 공리는 스트로크 대신 낸드나 NOR 운용에 대해서도 동일하게 유효하다. 셰퍼는 자신의 논문에서 비연관(NOR)을 각주로만 언급하고 특별한 징후가 없는 것으로 해석했다. 1917년 논문에서 이 뇌졸중을 비접속(NAND)의 징조로 처음 사용했고, 그 이후 현재 관행이 되고 있는 사람은 장 니코드였다.^[2]^[3] 러셀과 화이트헤드는 1927년 제2판 프린키마티카에서 셰퍼 스트로크를 사용했으며, 초판의 "또는" 또는 "아닙" 운용을 대체하는 것으로 제안했다.

찰스 샌더스 피어스(1880년)는 암페크('양방향 절단'을 위해)라는 용어를 사용하며 30여 년 전에 낸드나 NOR의 기능적 완성도를 발견했지만, 그의 연구 결과를 발표하지는 않았다.

특성.

NAND는 다음의 다섯 가지 특성 중 어느 것도 보유하지 않으며, 각각은 부재해야 하며, 기능적으로 완전한 운영자 집합의 적어도 한 명에게 충분한, 즉 진실-보존, 거짓-보존, 선형성, 단조성, 자기이중성을 보유하지 않는다. (운영자는 진실이다- (건전성) 모든 주장이 진실(건전성)일 때마다 그 가치가 진실인지(건전성) 보존한다.) 따라서 {NAND}은(는) 기능적으로 완전한 집합이다.

이것 또한 다음과 같이 실현할 수 있다. 기능적으로 완성된 세트 {AND, OR, NOT}의 세 가지 요소는 모두 NAND만을 사용하여 구성할 수 있다. 따라서 {NAND} 집합도 기능적으로 완전해야 한다.

셰퍼 스트로크 측면에서 기타 부울 연산

NAND $\uparrow$ $\uparrow$ 의 관점에서 표현되는 일반적인 명제 논리 연산자는 다음과 같다 $\uparrow$

$\displaystyle \neg P}$	$\왼쪽 화살표$	$P}$	$\displaystyle \uparrow }$	$P}$
	$\왼쪽 화살표$		$\displaystyle \uparrow }$

$P\오른쪽 화살표 Q}$	$\왼쪽 화살표$	$(\displaystyle ~P})$	$\displaystyle \uparrow }$	${\displaystyle(Q\uparrow Q)}$	$\왼쪽 화살표$	$(\displaystyle ~P})$	$\displaystyle \uparrow }$	${\displaystyle(P\uparrow Q)}$
	$\왼쪽 화살표$		$\displaystyle \uparrow }$		$\왼쪽 화살표$		$\displaystyle \uparrow }$

$P\왼쪽 화살표 Q}$	$\왼쪽 화살표$	${\displaystyle(P\uparrow Q)}$	$\displaystyle \uparrow }$	${\displaystyle(P\uparrow P)\uparrow(Q\uparrow Q)}$
	$\왼쪽 화살표$		$\displaystyle \uparrow }$

$P\land Q}$	$\왼쪽 화살표$	${\displaystyle(P\uparrow Q)}$	$\displaystyle \uparrow }$	${\displaystyle(P\uparrow Q)}$
	$\왼쪽 화살표$		$\displaystyle \uparrow }$

$P\lor Q}$	$\왼쪽 화살표$	${\displaystyle(P\uparrow P)}$	$\displaystyle \uparrow }$	${\displaystyle(Q\uparrow Q)}$
	$\왼쪽 화살표$		$\displaystyle \uparrow }$

셰퍼 스트로크를 기반으로 한 공식 시스템

다음은 전적으로 셰퍼 스트로크를 기반으로 함에도 불구하고 명제적 논리의 기능적 표현력을 갖는 형식적 시스템의 예다.

기호

p_n 자연수의 경우 n:

( )

셰퍼 스트로크는 통근하지만 연관되지 않는다(예 $:$ $($ T $T)$ F = $T$ , 그러나 T $(T$ F $)$ = $F$ ). 따라서 셰퍼 스트로크를 infix 기호로 포함한 모든 공식 시스템은 그룹화 방법을 포함해야 한다(스트로크를 접두사로 사용할 경우 그룹화는 자동이므로: $TTF$ = T, $T$ $TF$ = $F$ ). 우리는 이 취지에 '()'와 '''를 채용할 것이다.

우리는 또한₀ p, p₁, p 대신₂ p, q, r, …을 쓴다.

구문

시공 규칙 1: 각 자연수 n에 대해 기호 p는_n 원자로 불리는 잘 형성된 공식(wff)이다.

건설 규칙 II: X와 Y가 wffs라면 (X Y)는 wffs이다.

폐쇄 규칙: 처음 두 건설규칙으로 건설할 수 없는 공식은 wff가 아니다.

U, V, W, X, Y는 wffs를 나타내는 메타바리블이다.

공식이 제대로 형성되었는지 여부를 결정하는 절차는 다음과 같다: 건설 규칙을 거꾸로 적용하여 공식을 "해체"하여 공식을 더 작은 보조 공식으로 분해한다. 그런 다음 이 반복적인 해체 프로세스를 각 보조양식에 반복하십시오. 결국 공식을 원자로 줄여야 하지만, 일부 보조 공식을 그렇게 줄일 수 없다면, 그 공식은 wff가 아니다.

미적분학.

폼의 모든 wffs

((U (V W))(Y (Y))(X V)((U X)(U X)))))

공리야 의 인스턴스

{\displaystyle(U(V W), U\vdash W}

추론 규칙이다.

단순화

이 논리의 유일한 결합체는 ,이기 때문에 기호는 모두 폐기될 수 있고, 단지 괄호만 글자를 그룹화할 수 있다. 괄호 한 쌍은 항상 wff 한 쌍을 둘러싸야 한다. 이 단순화된 표기법에서 이론의 예는 다음과 같다.

(p(q(q)(pq)(pq)(pq))),

(p(p(q)(pp)))).

기호는 다음과 같이 함으로써 더 단순화할 수 있다.

(U) :=(UU)

((U)\equiv U

이러한 단순화는 일부 규칙을 변경할 필요성을 야기한다.

괄호 안에는 두 글자 이상이 허용된다.
괄호 안의 문자나 wff는 통근할 수 있다.
동일한 괄호 안에 반복되는 글자 또는 wffs를 제거할 수 있다.

그 결과는 Peirce 실존적 그래프를 모체로 한 것이다.

표기법을 단순화하는 또 다른 방법은 폴란드 표기법을 사용하여 괄호를 제거하는 것이다. 예를 들어, 괄호만 있는 이전의 예들은 다음과 같이 스트로크만 사용하여 다시 쓸 수 있었다.

(p(q(q)(pq)(pq)(pq))))가 된다.

p

p

q

q

q

pq,

(p(p(q)(pp)))가 된다.

p

p

Qq

pp

.

이는 괄호 버전과 동일한 규칙을 따르며, 개구부 괄호는 셰퍼 스트로크로 대체되고 (중복) 닫기 괄호는 제거된다.

또는 (일부 공식의 경우) 괄호와 스트로크를 모두 생략하고, 예를 들어 기능 적용 순서를 오른쪽에서 왼쪽으로 적용(역폴란드 표기법 - 순서에 기초한 다른 모호하지 않은 규약이 적용됨)하도록 인수의 순서를 결정할 수 있다.

{\signified}&pqr\equiv(p\mid(q\mid r)),{\text{white}\&rqp\equiv(r\mid(q\mid p))).\end{정렬}}

참고 항목

참조

보체스키, 조제프 마리아(1960), 수리논리의 프레시스, 레브, 알버트 메네(Albert Menne), 오토 버드(Otto Bird), 도드레흐트(Dordrecht ), 사우스 홀랜드: D: D. 레이델
Church, Alonzo (1956). Introduction to mathematical logic. Volume 1. Princeton University Press.
Nicod, Jean G. P. (1917). "A Reduction in the Number of Primitive Propositions of Logic". Proceedings of the Cambridge Philosophical Society. 19: 32–41.
찰스 샌더스 피어스, 1880년, C. 하르트손과 Weiss, P, 에드, (1931년–35년) 찰스 샌더스 페어스의 논문 수집, 제4권: 12–20, 캠브리지: 하버드 대학 출판부.
Sheffer, H. M. (1913), "A set of five independent postulates for Boolean algebras, with application to logical constants", Transactions of the American Mathematical Society, 14: 481–488, doi:10.2307/1988701, JSTOR 1988701

외부 링크

[FOOTNOTESheffer1913-1] 셰퍼 1913년

[FOOTNOTENicod1917-2] 니코드 1917.

[FOOTNOTEChurch1956134-3] 1956년 교회 134쪽

[2]

[3]

v t 논리 연결 장치
Tautology/True $\top$ $\top$
대체 거부(NAND 게이트) $\uparrow$ $\uparrow$ 컨버스 시사 $\displaystyle \왼쪽 화살표 }$ 시사(IMMLY 게이트) $\rightarrow$ → ${\디스플레이$ 스타일 \오른쪽 $화살표 }$ 분리(OR 게이트) $\lor$ $\lor$
부정(NOT 게이트) $\neg$ $\neg$ 단독 또는 (XOR 게이트) $\not \leftrightarrow$ ${\displaystyle \not \좌우$ 이동 $}$ Bicondient (XNOR 게이트) $\leftrightarrow$ ${\디스플레이$ 스타일 $\좌우$ 이동 $}$ 문(디지털 버퍼)
공동 거부(NOR 게이트) $\downarrow$ ↓ $\downarrow$ NIMPLY 게이트(Nonimplication $)({\displaystyle \nrightarrow })$ $\nrightarrow$ 컨버스 비임플렉스 $\displaystyle \nleftarrow }$ 접속사(AND 게이트) $\land$ $\land$
모순/거짓 $\bot$ $\bot$
철학포털

Search