폴란드어 표기법
Polish notation폴란드어 표기법(PN) 또는 폴란드어 표기법()은 연산자가 피연산자 앞에 오는 수학적 표기법이다,역폴란드 노타 뿐만 아니라연산자가 피연산자를 따르는 이온(RPN).각 연산자가 고정된 피연산자 수를 갖는 한 괄호는 필요하지 않습니다.폴란드어 표기법은 1924년 [5]: 367, Footnote 3) [6]: 180, Footnote 3) 폴란드어 표기법을 발명한 논리학자 얀 우카시에비치의 [2]: 24 [3]: 78 [4]국적을 의미합니다.
폴란드어 표기법이라는 용어는 때때로 역폴란드어 [7]표기법을 포함하는 것으로 간주됩니다(infix 표기법의 반대).
폴란드어 표기법이 프로그래밍 언어 해석기에 의해 수학적 표현을 위한 구문으로 사용될 때, 그것은 쉽게 추상 구문 트리로 구문 분석되고 사실, 동일한 것에 대해 일대일 표현을 정의할 수 있습니다.따라서 Lisp(아래 참조) 및 관련 프로그래밍 언어는 전체 구문을 접두사 표기법으로 정의합니다(다른 언어는 접두사 표기법을 사용함).
역사
1931년 얀[5]: 367, Footnote 3) [6]: 180, Footnote 3) 우카시에비치의 논문에서 인용한 바에 따르면 어떻게 표기법이 발명되었는지를 알 수 있습니다.
저는 1924년에 괄호가 없는 표기법을 생각하게 되었습니다.저는 제 기사 우카시에비치 (1), 페이지 610, 각주에서 처음으로 그 표기법을 사용했습니다.
우카시에비치, 즉 우카시에비치(1)[8]가 인용한 참조는 분명히 폴란드어로 석판화된 보고서입니다.우카시에비치의 참조[5] 논문은 헨리 A에 의해 검토되었습니다. 1965년 [9]기호논리학 저널에 실린 Pogorzelski.1924년에 모세 쇤핀켈의 [10]기사의 편집자였던 하인리히 베만은 논리 공식에서 괄호를 제거하는 아이디어를 이미 가지고 있었습니다.그의 논문 중 하나에서 우카시에비치는 그의 표기법이 가장 간결하고 최초의 선형적으로 괄호가 없는 표기법이라고 말했지만, 고틀로프 프레게가 1879년에 괄호가 없는 베그리프스크리트 표기법을 이미 [11]제안한 첫 번째 것은 아닙니다.
Alonzo Church는 수학 논리에 대한 그의 고전적인 책에서 이 표기법을 알프레드 화이트헤드와 버트런드 러셀의 수학적 원리 [12]설명과 대조되는 표기법 체계에서 주목할 가치가 있다고 언급합니다.
우카시에비치의 1951년 저서인 아리스토텔레스의 삼단논법에서, 그는 그의 표기법의 원리가 괄호를 피하기 위해 논쟁 앞에 함수를 쓰는 것이었고 [3]: 78 1929년부터 논리적 논문에 그의 표기법을 사용했다고 언급합니다.그는 이어서 1930년 알프레드 타르스키와 함께 [13]쓴 문장 미적분학 논문을 예로 들었습니다.
논리학에서 [14]더 이상 많이 사용되지 않는 동안, 폴란드 표기법은 그 이후 컴퓨터 과학에서 자리를 잡았습니다.
설명.
숫자 1과 2를 추가하는 표현식은 폴란드어 표기법으로 1 + 2(infix)가 아닌 + 12(접두사)로 작성됩니다.더 복잡한 식에서 연산자는 여전히 피연산자 앞에 있지만 피연산자 자체는 다시 연산자와 피연산자를 포함한 식일 수 있습니다.예를 들어, 전통적인 인픽스 표기법으로 쓰여질 표현은 다음과 같습니다.
폴란드 표기법으로 다음과 같이 쓸 수 있습니다.
관련된 모든 연산자의 주어진 배열을 가정하면(여기서 "-"는 부호 변화의 단항 함수가 아닌 뺄셈의 이진 연산을 나타냅니다), 잘 형성된 접두사 표현은 모호하지 않으며 접두사 표현 내의 괄호는 필요하지 않습니다.이와 같이, 위의 표현식은 다음과 같이 더욱 단순화될 수 있습니다.
두 피연산자(예: 5 빼기 6 및 7)를 사용할 수 있을 때까지 제품의 처리가 지연됩니다.다른 표기법과 마찬가지로 가장 안쪽 표현식이 먼저 평가되지만, 폴란드 표기법에서는 괄호보다는 연산자와 피연산자의 순서로 이 "내부"를 전달할 수 있습니다.
기존의 infix 표기법에서는 위의 예를 참조하여 이동하므로 표준 우선 순위 규칙을 재정의하려면 괄호가 필요합니다.
또는 제거합니다.
식의 의미와 결과를 변경합니다.이 버전은 다음과 같이 폴란드어 표기법으로 작성되었습니다.
나눗셈이나 뺄셈과 같은 비가환 연산을 다룰 때 연산자가 인수를 왼쪽에서 오른쪽으로 취하는 방법의 정의와 함께 연산자의 순차적 배열을 조정해야 합니다.예를 들어, 10이 5인 ÷105는 10 ÷5("5로 10 나누기"로 읽음)의 의미를 갖거나, 7이 6인 -76은 7 -6("7 피연산자 6에서 빼기"로 읽음)의 의미를 갖습니다.
평가 알고리즘
접두사/접두사 표기법은 일반적으로 infix 표기법에 사용되는 것처럼 괄호와 다른 우선 순위 규칙 없이 의도된 작업 순서를 표현할 수 있는 선천적인 기능으로 특히 인기가 있습니다.대신, 이 표기법은 먼저 평가할 연산자를 고유하게 나타냅니다.측정 시스템은 각각 고정된 배열을 가지고 있다고 가정하고 필요한 모든 피연산자가 명시적으로 주어졌다고 가정합니다.유효한 접두사 식은 항상 연산자로 시작하고 피연산자로 끝납니다.평가는 왼쪽에서 오른쪽으로 진행하거나 반대 방향으로 진행할 수 있습니다.왼쪽에서 시작하여, 연산자 또는 피연산자를 나타내는 토큰으로 구성된 입력 문자열은 스택의 상위 항목에 최상위 연산자(바로 아래)에 맞는 피연산자의 수가 포함될 때까지 스택의 토큰에 대해 푸시됩니다.스택 맨 위의 토큰 그룹(마지막으로 쌓인 연산자와 해당 피연산자 수)은 이러한 피연산자에서 연산자를 실행한 결과로 대체됩니다.그런 다음 이러한 방식으로 입력 처리가 계속됩니다.따라서 유효한 접두사 식에서 가장 오른쪽 피연산자는 전체 식을 평가한 결과를 제외하고 스택을 비웁니다.오른쪽에서 시작할 때 토큰 푸시는 비슷하게 수행되며, 연산자에 의해 평가가 트리거되어 스택 상단에 이미 배열에 맞는 적절한 피연산자 수를 찾습니다.이제 유효한 접두사 식의 맨 왼쪽 토큰은 스택의 피연산자 수에 맞는 연산자여야 하며, 이 연산자는 다시 결과를 산출합니다.설명에서 알 수 있듯이 임의 스택 검사 기능이 없는 푸시다운 저장소는 이 구문 분석을 구현하기에 충분합니다.
위의 스케치된 스택 조작은 역폴란드 표기법의 식에 대해서도 미러링된 입력으로 작동합니다.
논리에 대한 폴란드어 표기법
아래 표는 현대 논리학에서 얀 우카시에비치의 표기법의 핵심을 보여줍니다.폴란드어 표기법 표의 일부 문자는 다음과 같이 폴란드어의 특정 단어를 나타냅니다.
개념. | 재래식 표기법 | 폴란드의 표기법 | 폴란드의 용어 |
---|---|---|---|
부정 | [2]: 27–28 | 네가짜 | |
재료 조건부 | [2]: 28–31 | 함축성 있는 | |
분리 | [2]: 34–35 | 얼터너티브와 | |
접속사 | [2]: 35–36 | 코니웅크자 | |
비접속어 | [2]: 36 | dysjunkcja | |
바이컨디셔널 | {\ E \ Q {\ Q \ | 에퀴왈렌차 | |
범용 계량기 | [2]: 154–156 | 콴티피카토르골니 | |
실존적 정량자 | [2]: 157 | 관티피카토르 스체고우위 | |
베룸 | [15]: 275 | 까칠까칠 | |
가능 | {\ M 또는[16]: 52 [3]: 134 {\ | 모글리오비치 | |
필요성 | {\ L 또는[3]: 134 {\ | 코니에츠노이치 |
정량자는 다치 논리에 대한 우카시에비치의 연구에서 명제 값에 걸쳐 있었습니다.
보첸스키는 고전적인 명제 [18]: 16 논리의 16개 이진 연결을 모두 명명하는 폴란드 표기법 시스템을 도입했습니다.고전적인 명제 논리학의 경우, 우카시에비치 표기법의 호환 가능한 확장입니다.그러나 Bocheinski가 명제 논리에서 L L과 MM}(비사용 및 역비사용)을 하고, 우카시에비치가 모달 논리에서L{ L과 M M을 사용한다는 점에서 이 표기법은 양립할 수 없습니다.
구현
접두사 표기법은 언어의 연산자 자체가 데이터(일급 함수)이기 때문에 괄호가 필요한 리스프 S 표현식에서 광범위하게 적용되었습니다.리스프 함수는 가변적일 수도 있습니다.Lisp와 마찬가지로 Tcl 프로그래밍 언어는 Mathop 라이브러리를 통해 폴란드 표기법을 사용합니다.Ambi[19] 프로그래밍 언어는 산술 연산 및 프로그램 구성에 폴란드어 표기법을 사용합니다.LDAP 필터 구문은 폴란드어 접두사 [20]표기법을 사용합니다.
포스트픽스 표기법은 PostScript 및 Forth와 같은 많은 스택 지향 프로그래밍 언어에서 사용됩니다.또한 CoffeeScript 구문을 사용하면 다른 언어에서 공통적으로 사용되는 단항 포스트픽스 구문을 지원하면서 접두사 표기법을 사용하여 함수를 호출할 수 있습니다.
식의 반환 값 수는 식의 피연산자 수와 연산자의 총 도면 연속성 사이의 차이에서 연산자의 총 반환 값을 뺀 값과 같습니다.
폴란드 표기법은 일반적으로 포스트픽스 형식으로 특정 계산기, 특히 Hewlett-Packard에서 [21]선택한 표기법입니다.하위 수준에서 포스트픽스 연산자는 Burroughs 대형 시스템과 같은 일부 스택 시스템에서 사용됩니다.
참고 항목
- 역폴란드 표기법(RPN)
- 함수 적용
- 람다 미적분학
- 카레링
- 리스프(프로그래밍 언어)
- 폴란드 수학원
- 헝가리 표기법
- 동사-주어-목적어(VSO)
- 동사-목적어-주어(VOS)
- 헤드 방향성 매개변수
- WFF 'N 프루프
레퍼런스
- ^ Jorke, Günter; Lampe, Bernhard; Wengel, Norbert (1989). Arithmetische Algorithmen der Mikrorechentechnik [Arithmetic algorithms in microcomputers] (in German) (1 ed.). Berlin, Germany: VEB Verlag Technik. ISBN 3-34100515-3. EAN 978-3-34100515-6. MPN 5539165. License 201.370/4/89. Retrieved 2015-12-01.
- ^ a b c d e f g h i Łukasiewicz, Jan (1929). Elementy logiki matematycznej (in Polish) (1 ed.). Warsaw, Poland: Państwowe Wydawnictwo Naukowe; Łukasiewicz, Jan (1963). Elements of Mathematical Logic. Translated by Wojtasiewicz, Olgierd Adrian [in Polish]. New York, USA: The MacMillan Company.
- ^ a b c d e Łukasiewicz, Jan (1957) [1951]. Aristotle's Syllogistic from the Standpoint of Modern Formal Logic (2 ed.). Oxford University Press. (1987년 갈랜드 출판사에서 재인쇄, ISBN 0-8240-6924-2.)
- ^ Kennedy, John (August 1982). "RPN Perspective". PPC Calculator Journal. Mathematics Department, Santa Monica College, Santa Monica, California, USA. 9 (5): 26–29. CiteSeerX 10.1.1.90.6448. Archived from the original on 2022-07-01. Retrieved 2022-07-02. (12페이지)
- ^ a b c Łukasiewicz, Jan (1931). "Uwagi o aksjomacie Nicoda i 'dedukcji uogólniającej'" [Comments on Nicod's Axiom and on 'Generalizing Deduction']. Księga pamiątkowa Polskiego Towarzystwa Filozoficznego We Lwowie, 12. II. 1904-12. II. 1929 (in Polish). Lwów: Wydawnictwo Polskie Towarzystwo Filozoficzne. pp. 366–383.
- ^ a b Łukasiewicz, Jan (1970). "Comments on Nicod's Axiom and on 'Generalizing Deduction'". In Borkowski, L. (ed.). Selected Works. Amsterdam and London/Warszawa: North-Holland Publishing Company/Polish Scientific Publishers. pp. 179–196.
- ^ Main, Michael (2006). Data structures and other objects using Java (3rd ed.). Pearson PLC Addison-Wesley. p. 334. ISBN 978-0-321-37525-4.
- ^ Łukasiewicz, Jan (1929). "O znaczeniu i potrzebach logiki matematycznej". Nauka Polska (in Polish). 10: 604–620.
- ^ 포고르첼스키, 헨리 앤드류 (1965년 9월)."검토된 작업:니코드의 공리와 얀 우카시에비치, 예지 스워페키, 파우스투위 비다닉투 나우코웨의 "공제의 일반화"에 대한 발언.기호 논리학 저널(검토).기호 논리 협회. 30 (3): 376–377. JSTOR 2269644. (NB).얀 우카시에비치의 1931년 논문 《우와기악스조마시에 니코다이 데두크지우골니아이체이》는 1961년 폴란드 바르샤바의 파슈투우에 비데우니츠투 나우코웨에서 제리 슈페키가 편집한 책으로 재발간되었다
- ^ 쇤핀켈, 모세 (1924)."위베르 디 바우스타인 der mathemistichen Logic" [수학적 논리의 구성 요소에 대하여].수학자 아날렌(독일어).92 (3–4): 305–316. doi: 10.1007/BF01448013.S2CID 118507515; 판 하이에노르트, Jean, Ed. (1967)."수학적 논리의 구성 요소에 대해"1879-1931 수학 논리학의 원천 책.바우어-멩겔베르크 옮김, 스테판 [네덜란드어].하버드 대학 출판부 355-366페이지.
- ^ Gottschall, Christian (2005). Logische Notationen und deren Verarbeitung auf elektronischen Rechenanlagen aus theoretischer, praktischer und historischer Sicht (Diploma thesis) (in German). Vienna, Austria. p. 88:
Die ältesten Texte in den 'Selected Works', in denen Łukasiewicz polnische Notation verwendet, datieren relativ spät, sind aber Präsentationen vorangehender Arbeiten, die 'in the course of the years 1920–1930' (S. 131) stattgefunden haben, also auch keine genauere Zeitangabe geben.
{{cite book}}
CS1 유지 관리: 위치에 게시자가 없습니다(링크). - ^ Church, Alonzo (1944). Introduction to Mathematical Logic. Princeton, New Jersey, USA: Princeton University Press. p. 38.
[…] Worthy of remark is the parenthesis-free notation of Jan Łukasiewicz. In this the letters N, A, C, E, K are used in the roles of negation, disjunction, implication, equivalence, conjunction respectively. […]
- ^ Łukasiewicz, Jan; Tarski, Afred (1930). "Untersuchungen über den Aussagenkalküls" [Investigations into the Sentential Calculus]. Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie (in German). 23 (Cl. III): 30–50.
- ^ Martínez Nava, Xóchitl (2011-06-01), "Mhy bib I fail logic? Dyslexia in the teaching of logic", in Blackburn, Patrick; van Ditmarsch, Hans; Manzano, Maria; Soler-Toscano, Fernando (eds.), Tools for Teaching Logic: Third International Congress, TICTTL 2011, Salamanca, Spain, June 1–4, 2011, Proceedings, Lecture Notes in Artificial Intelligence, vol. 6680, Springer Nature, pp. 162–169, doi:10.1007/978-3-642-21350-2_19, ISBN 978-3-64221349-6,
[…] Polish or prefix notation has come to disuse given the difficulty that using it implies. […]
- ^ Łukasiewicz, Jan (1939). "Der Äquivalenzenkalkül". Collectanea Logica (in German). 1: 145–169.
- ^ Łukasiewicz, Jan (1930). "Untersuchungen über den Aussagenkalküls" [Investigations into the Sentential Calculus]. Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie (in German). 23 (Cl. III): 51–77.
- ^ a b Łukasiewicz, Jan (1953). "A System of Modal Logic". The Journal of Computing Systems. 3 (1): 111–149.
- ^ Bocheński, J. M. (1949). Précis de logique mathématique (PDF) (in French). The Netherlands: F. G. Kroonder, Bussum, Pays-Bas. 다음으로 번역:
- ^ "Google Code Archive - Long-term storage for Google Code Project Hosting". Archived from the original on 2017-09-28. Retrieved 2022-11-14.
- ^ "LDAP Filter Syntax". Archived from the original on 2022-10-14. Retrieved 2022-11-14.
- ^ "HP calculators - HP 35s RPN Mode" (PDF). Hewlett-Packard. Archived (PDF) from the original on 2022-01-21. Retrieved 2022-11-14.
서지학
- Foth, Michael; Wilke, Thomas, Eds. (2015) [2014-11-14].독일 예나에서 작성되었습니다.켈러, 스택 앤트 자동화 게데흐트니스 – 아이네 스트룩투미트 포텐지알 [셀라, 스택 및 자동 메모리 - 잠재력이 있는 구조] (PDF) (Tagungsband zum Koloquium 14).2014년 11월 예나에서).GI 시리즈:정보학 강의 노트(LNI) – 주제(독일어).T-7권. 본, 독일:게셀샤프트 인포마틱 (GI) / 쾰른 드러크 + 베를라그 GmbH.ISBN 978-3-88579-426-4.ISSN 1614-3213입니다.2020-04-12 원본에서 보관(PDF).2020-04-12 검색됨. [1] (77페이지)
- Langmaack, Hans [독일어로] (2015) [2014-11-14].독일 킬에서 작성되었습니다.프리드리히 바우어와 클라우스 사멜슨 아르비텐은 1950년대에 지하실 원리와 자동화라는 용어의 도입에 관한 프리드리히 바우어와 클라우스 사멜슨의 저작들을 독일어로 번역하였다.예나, 독일:Informatik 연구소, Christian-Albrechts-Universität zu Kiel, 19-29페이지.2022-11-14년 원본에서 보관(PDF).2022-11-14 검색됨. (11페이지) (NB. Fother & Wilke에서 출판됨)
- 구스, 게르하르트[독일어] (2017-08-07).Geschichte der deutschsprachigen Informatik - Programiersprachen und Ubersetzerbau [독일어권 국가의 정보학의 역사 - 프로그래밍 언어와 컴파일러 디자인] (PDF) (독일어).독일 카를스루에 공과대학교(KIT)의 파쿨테튀르 인포마티크.2022-05-19년 원본에서 보관(PDF).2022-11-14 검색 완료. (11페이지)