다변량 논리학

Many-valued logic

논리학에서 많은 가치의 논리(다중 또는 다중의 가치 논리)는 진리 값이 개 이상 있는 명제적 미적분학이다. 전통적으로 아리스토텔레스논리 미적분학에는 어떤 명제에도 가능한 두 가지 가치(즉, "진실"과 "거짓말")밖에 없었다. 고전적 2-값 논리는 n 2보다 큰 n-값 논리로 확장될 수 있다. 문헌에서 가장 인기 있는 것은 3가지 가치(예: '참', '거짓', '알 수 없는' 값을 받아들이는 우카시오비츠클레네의 것), 4가지 가치, 9가지 가치, 3가지 이상의 가치를 지닌 유한 가치(완전히 다수가 가치), 그리고 무한 가치(무한 다수가 가치)로 퍼지 논리학, 확률 논리학 등이다.

역사

배제된 중간의 법칙을 완전히 수용하지 않은 최초의 알려진 고전 논리학자는 아리스토텔레스였다(아이러니컬하게도 그는 또한 일반적으로 최초의 고전 논리학자이자 "논리의 아버지"[1]로 여겨진다. 아리스토텔레스는 자신의 법칙이 모두 미래의 사건(De Deratione, ch. IX)에 적용되는 것은 아니라고 인정하면서도 이 고립된 말을 설명하기 위한 다변도의 논리 체계를 만들지는 않았다. 20세기가 올 때까지 이후 논리학자들은 배제된 중간의 법칙을 포함하거나 가정한 아리스토텔레스식 논리를 따랐다.

20세기는 다변량 논리학의 사상을 되살렸다. 폴란드 논리학자 겸 철학자 얀 우카시예비치(Jan Wukasiewicz)는 1920년부터 바다 전투의 아리스토텔레스의 역설(역설)을 다루기 위해 제3의 가치인 '가능성'을 이용하여 많은 가치가 있는 논리학의 체계를 만들기 시작했다. 한편 미국의 수학자 에밀 L. 포스트(1921년)도 n이 진리 값인 n ≥ 2로 추가 진리 학위 제정을 도입했다. 후에, 얀 우카시에비츠와 알프레드 타르스키가 함께 n ≥ 2의 진리 값에 대한 논리를 공식화했다. 1932년, 한스 라이헨바흐n→them에서 많은 진리 가치의 논리를 공식화했다. 1932년 쿠르트 괴델직관적 논리가 정밀하게 많은 가치를 지닌 논리가 아니라는 것을 보여주었고, 괴델 로직의 체계를 고전적 논리와 직관적 논리 사이의 중간으로 정의했다. 그러한 로직은 중간 로직이라고 알려져 있다.

클레인(강력) K3 프리스트 논리3 P

클린의 (강력한) 불변성의 논리" K3( 3 와 프리스트의 "역설의 논리"는 세 번째 "정의되지 않은" 또는 "결정되지 않은" 진실 값 I을 더한다. 부정(¬), 접속사(∧), 절연(∨∨), 함축(→∨), 함축(→K), 쌍변(↔itional)에 대한 진실 함수는 다음과 같이 주어진다.[2]

¬
T F
I I
F T
T I F
T T I F
I I I F
F F F F
T I F
T T T T
I T I I
F T I F
K T I F
T T I F
I T I I
F T T T
K T I F
T T I F
I I I I
F F I T

두 로직 사이의 차이는 tautology가 어떻게 정의되는가에 있다. K에서는3 T만이 지정된 진리 값인 반면, P에서는3 T 둘 다(논리 공식이 지정된 진리 값으로 평가되면 tautology로 간주된다). 클레네의 논리에서는 는 진실도 거짓도 아닌 '과잉'으로 해석될 수 있고, 프리스트의 논리에서는 '과잉'으로 해석될 수 있으며, 진실도 거짓도 있다. K3 어떤 tautology도 가지고 있지 않은 반면, P3 고전적인 2값 논리와 동일한 tautology를 가지고 있다.[3]

보흐바르 내부 3값 논리

또 다른 논리는 드미트리 보흐바르의 "내부" 3값 B I 스타일 클린의 약한 3값 논리라고도 한다. 부정과 쌍동설을 제외하면 그 진리표는 모두 위와 다르다.[4]

+ T I F
T T I F
I I I I
F F I F
+ T I F
T T I T
I I I I
F T I F
+ T I F
T T I F
I I I I
F T I T

보흐바르의 "내부" 논리에서 중간 진리 값은 다른 변수의 값과 관계없이 공식으로 전파되기 때문에 "논쟁적"이라고 설명할 수 있다.[4]

벨납 논리(B4)

벨납의 논리 B4 K3 P3 합친 것이다. 여기서 과결정된 진리 은 B로 표시되고 과결정된 진리 은 N으로 표시된다.

f¬
T F
B B
N N
F T
f T B N F
T T B N F
B B B F F
N N F N F
F F F F F
f T B N F
T T T T T
B T B T B
N T T N N
F T B N F

괴델 로직스 Gk G

1932년 괴델에 defined[5] 가족 Gkm그리고 4.9초 만{\displaystyle G_{km그리고 4.9초 만}}many-valued 논리의, 유한하게 많은 진리 값으로 0,1k− 1,2k− 1,…, k − 2k− 1,1{\displaystyle 0,{\tfrac{1}{k-1}},{{2\tfrac}{k-1}}},{\tfrac{k-2}{k-1}},1 ,\ldots, 예를 들어 G3{\displaystyle G_{3}}은 tr다.uth values and has . In a similar manner he defined a logic with infinitely many truth values, , in which the truth values는 [0 간격의 모든 실제 수입니다 이러한 로직에서 지정된 진리 값은 1이다.

(와) 분리 은(는) 각각 피연산자의 최소값최대값으로 정의된다.

부정 시사 은(는) 다음과 같이 정의된다.

괴델 로직은 완전히 공리성이 있으며, 즉 모든 토폴로지가 증명 가능한 논리 미적분학을 정의할 수 있다.

우카시오비치 로직스 Lv L

L and L 은(는) 다음 기능을 통해 Jan Uwkasiewicz에 의해 정의되었다.

At first Łukasiewicz used these definitions in 1920 for his three-valued logic , with truth values . In 1922 he developed a logic with infinitely many values , in which the truth values spanned the real numbers 간격 [ 1 두 경우 모두 지정된 진리 값은 1이었다.[6]

By adopting truth values defined in the same way as for Gödel logics , it is possible to create a finitely-valued family of logics , the abovementioned and the logic , in which the truth values are given by the rational numbers in the interval . The set of tautologies in and (는) 동일하다.

제품 로직 π

제품 논리학에서 우리는[ 접속사 및 시사 의 간격에 진실 값을 가지고[7] 있다

또한 거짓의 개념을 나타내는 음의 지정 0이(가) 있다. 이 값을 통해 다음과 같이 부정 Pi (와) 추가 접속사 을(를) 정의할 수 있다.

그리고 v= { v

포스트m 로직 P

In 1921 Post defined a family of logics with (as in and ) the truth values . {P 및 접속사 P {P와) P {\은 다음과 같이 정의된다.

로즈 로직스

1951년에 앨런 로즈는 진실 값이 격자를 형성하는 시스템에 대한 또 다른 논리학 계열을 정의했다.[8]

고전적 논리와의 관계

로직은 일반적으로 변환에 걸쳐 제안의 일부 의미속성을 보존하기 위한 규칙을 코드화하기 위한 시스템이다. 고전적 논리학에서 이 속성은 "진실"이다. 유효한 주장에서, 유효한 단계의 적용이 재산을 보존하기 때문에, 전제가 공동으로 진실이라면 파생 명제의 진실은 보장된다. 그러나, 그 속성은 "진실"의 그것일 필요는 없다. 대신, 그것은 다른 개념이 될 수 있다.

다중값 로직은 지정(또는 지정)의 특성을 보존하기 위한 것이다. 두 가지 이상의 진리 값이 있기 때문에 추론 규칙은 진리에 해당하는 것(관련된 의미) 이상의 것을 보존하기 위한 것일 수 있다. 예를 들어, 3개의 가치 논리에서는 때때로 두 개의 가장 큰 진리 값(예: 양의 정수로 표현될 때)이 지정되고 추론 규칙은 이러한 값을 보존한다. 정확히 말하면, 공동취득한 전제의 가치는 항상 결론보다 작거나 같을 것이다.

예를 들어, 보존된 속성은 직관 논리의 근본 개념인 명분이 될 수 있다. 그러므로 명제는 참이거나 거짓이 아니며, 그 대신 정당하거나 흠이 있다. 정당성과 진실성의 중요한 차이점은 배제된 중간부의 법칙이 지켜지지 않는다는 것이다: 결점이 없는 명제는 반드시 정당화될 수는 없다. 대신, 그것이 결점이라는 것이 증명되지 않을 뿐이다. 주요 차이점은 보존 재산의 결정성이다. 사람들은 P가 정당하다는 것을 증명할 도 있고, P가 결함이 있다는 것을 증명할 수도 있고, 둘 중 어느 것도 증명할 수 없을 수도 있다. 유효한 주장은 변혁에 걸친 정당성을 보존하기 때문에 정당화된 명제에서 도출된 명제는 여전히 정당화된다. 그러나 고전적 논리에는 배제된 중간의 법칙에 의존하는 증거가 있다. 이 제도에서는 그 법칙을 사용할 수 없기 때문에, 그렇게 증명할 수 없는 명제들이 있다.

수스코의 논문

다변량 로직의 기능 완전성

기능적 완전성은 유한한 로직과 알헤브라의 특수한 속성을 기술하는 데 사용되는 용어다. 논리의 연결고리 집합은 그 연결고리 집합을 모든 가능한 진리 기능에 해당하는 공식을 구성하는 데 사용할 수 있는 경우에만 기능적으로 완전하거나 적절하다고 한다.[9] 적절한 대수학은 변수의 모든 유한한 매핑을 연산의 어떤 구성으로 표현할 수 있는 것이다.[10]

고전적 논리: CL = ({0,1}, ¬, →, ∨, ↔, ↔, ↔, ↔)는 기능적으로 완전하지만, 우카시오비츠 논리나 무한히 많은 가치의 로직은 이 속성을 가지고 있지 않다.[10][11]

우리는 미세하게 많은 가치의 논리를 Ln({1, 2, ..., n} ƒ1, ..., ƒm)로 정의할 수 있는데 여기서 n ≥ 2는 주어진 자연수다. 포스트(1921)는 어떤 논리가 m 순서th 모델의 함수를 생성할 수 있다고 가정하면, 적절한 논리 L에n 있는 커넥티브의 어떤 상응하는 조합이 순서 m+1의 모델을 만들 수 있다는 것을 증명한다.[12]

적용들

많은 가치가 있는 논리학의 알려진 응용은 대략 두 그룹으로 분류될 수 있다.[13] 첫 번째 그룹은 이진법 문제를 보다 효율적으로 해결하기 위해 많은 가치의 논리를 사용한다. 예를 들어, 다중 출력 부울 함수를 나타내는 잘 알려진 접근방식은 출력 부분을 단일 다값 변수로 처리하고 단일 출력 특성 함수(특히 표시 함수)로 변환하는 것이다. 그 밖에 다액의 로직 어플리케이션으로는 입력 디코더를 이용한 프로그램 가능한 로직 어레이(PLA)의 설계, 유한 상태 머신의 최적화, 시험, 검증 등이 있다.

두 번째 그룹은 다값 메모리, 산술 회로, 현장 프로그래머블 게이트 어레이(FPGA) 등 세 가지 이상의 이산 신호 레벨을 채택하는 전자 회로 설계를 목표로 한다. 많은 값이 매겨진 회로는 표준 2진 회로에 비해 이론적 이점이 많다. 예를 들어 회로 내 신호가 2개 수준이 아닌 4개 이상의 수준을 가정할 경우 칩의 상호 연결 및 오프 연결은 감소할 수 있다. 메모리 설계에서 메모리 셀당 1비트 정보 대신 2개의 정보를 저장하면 동일한 다이 크기에서 메모리의 밀도가 두 배가 된다. 산술 회로를 사용하는 애플리케이션은 종종 이진수 시스템에 대한 대안의 사용으로부터 이익을 얻는다. 예를 들어, 잔류물과 중복 번호 시스템[14] 정상적인 이항 추가나 뺄셈에 관여하는 리플스루 운반물을 감소시키거나 제거하여 고속 산술 연산을 초래할 수 있다. 이러한 숫자 시스템은 다액의 회로를 사용하여 자연적으로 구현된다. 그러나 이러한 잠재적 장점들의 실용성은 회로 실현의 가용성에 크게 좌우되며, 이는 오늘날의 표준 기술과 호환되거나 경쟁력이 있어야 한다. 전자 회로 설계에 도움이 되는 것 외에도, 회로의 결함과 결함을 시험하기 위해 다액의 가치 논리가 광범위하게 사용된다. 기본적으로 디지털 회로 시험에 사용되는 알려진 모든 ATG 알고리즘은 5 값 논리(0, 1, x, D, D')[15]를 해결할 수 있는 시뮬레이터가 필요하다. 추가 값(x, D, D')은 (1) 알 수 없음/비초기화, (2) 1 대신 0, (3) 0 대신 1을 나타낸다.

연구 장소

IEEE 국제 다가치 논리 심포지엄(ISMVL)은 1970년부터 매년 개최되고 있다. 그것은 대부분 디지털 디자인과 검증에서 응용 프로그램에 적응한다.[16] 또한 복수 가치 논리학소프트 컴퓨팅 저널도 있다.[17]

참고 항목

수학적 논리학
철학 논리학
디지털 논리

참조

  1. ^ 헐리, 패트릭. 논리에 대한 간략한 소개, 제9판. (2006).
  2. ^ (Gottwald 2005, 페이지 19)
  3. ^ Humberstone, Lloyd (2011). The Connectives. Cambridge, Massachusetts: The MIT Press. pp. 201. ISBN 978-0-262-01654-4.
  4. ^ a b (베르그만 2008, 페이지 80)
  5. ^ Gödel, Kurt (1932). "Zum intuitionistischen Aussagenkalkül". Anzeiger der Akademie der Wissenschaften in Wien (69): 65f.
  6. ^ Kreiser, Lothar; Gottwald, Siegfried; Stelzner, Werner (1990). Nichtklassische Logik. Eine Einführung. Berlin: Akademie-Verlag. pp. 41ff–45ff. ISBN 978-3-05-000274-3.
  7. ^ 하젝, 페트르: 퍼지 논리학. 인: Edward N. Zalta: 스탠포드 철학 백과사전, 2009년 봄. ([1]
  8. ^ Rose, Alan (December 1951). "Systems of logic whose truth-values form lattices". Mathematische Annalen. 123: 152–165. doi:10.1007/BF02054946. S2CID 119735870.
  9. ^ Smith, Nicholas (2012). Logic: The Laws of Truth. Princeton University Press. p. 124.
  10. ^ a b Malinowski, Grzegorz (1993). Many-Valued Logics. Clarendon Press. pp. 26–27.
  11. ^ Church, Alonzo (1996). Introduction to Mathematical Logic. Princeton University Press. ISBN 978-0-691-02906-1.
  12. ^ Post, Emil L. (1921). "Introduction to a General Theory of Elementary Propositions". American Journal of Mathematics. 43 (3): 163–185. doi:10.2307/2370324. hdl:2027/uiuo.ark:/13960/t9j450f7q. ISSN 0002-9327. JSTOR 2370324.
  13. ^ 두브로바, 엘레나(2002년). Hassoun S.와 Sasao T의 다변량 논리합성과 최적화, 편집자, 논리합성검증, Kluwer Academic Publishers, 페이지 89-114
  14. ^ Meher, Pramod Kumar; Valls, Javier; Juang, Tso-Bing; Sridharan, K.; Maharatna, Koushik (2008-08-22). "50 Years of CORDIC: Algorithms, Architectures and Applications" (PDF). IEEE Transactions on Circuits & Systems I: Regular Papers (published 2009-09-09). 56 (9): 1893–1907. doi:10.1109/TCSI.2009.2025803. S2CID 5465045. Retrieved 2016-01-03.
  15. ^ Abramovici, Miron; Breuer, Melvin A.; Friedman, Arthur D. (1994). Digital Systems Testing and Testable Design. New York: Computer Science Press. p. 183. ISBN 978-0-7803-1062-9.
  16. ^ "IEEE International Symposium on Multiple-Valued Logic (ISMVL)". www.informatik.uni-trier.de/~ley.
  17. ^ "Archived copy". Archived from the original on 2014-03-15. Retrieved 2011-08-12.{{cite web}}: CS1 maint: 타이틀로 보관된 사본(링크)

추가 읽기

일반

  • 아우구스토, 루이스 M. (2017). 여러 값 로직: 수학적, 계산적 도입. 런던: 대학 출판사. 340쪽. ISBN 978-1-84890-250-3 웹 페이지
  • 베지아우 J.-Y(1997), 많은 가치 논리란 무엇인가? 제27회 다가치 논리학 국제 심포지엄의 진행, IEEE 컴퓨터 학회, 로스 알라미토스, 페이지 117–121.
  • Malinowski, Gregorz, (2001) Multi-Value Logics, Goble, Lou, Ed, The Blackwell Guide to Tychological Logic. 블랙웰.
  • Bergmann, Merrie (2008), An introduction to many-valued and fuzzy logic: semantics, algebras, and derivation systems, Cambridge University Press, ISBN 978-0-521-88128-9
  • 시뇰리, R. L. O., 도타비아노, I. M. L. 문디치, D. (2000년) 많은 가치를 지닌 추론대수학적 기초. 클루워.
  • Malinowski, Grzegorz (1993). Many-valued logics. Clarendon Press. ISBN 978-0-19-853787-8.
  • S. Gottwald, 많은 가치가 있는 로직들에 대한 논문. 로직과 계산에 관한 연구, 제9권, 연구 보도: 영국 허트포드샤이어, 2001.
  • Gottwald, Siegfried (2005). "Many-Valued Logics" (PDF). Archived from the original on 2016-03-03. {{cite journal}}: Cite 저널은 필요로 한다. journal= (도움말)CS1 maint: bot: 원래 URL 상태를 알 수 없음(링크)
  • Miller, D. Michael; Thornton, Mitchell A. (2008). Multiple valued logic: concepts and representations. Synthesis lectures on digital circuits and systems. Vol. 12. Morgan & Claypool Publishers. ISBN 978-1-59829-190-2.
  • Hahjek P, (1998년), 퍼지 논리의 변성학. 클루워. (푸지 논리는 많은 가치를 지닌 논리생성으로 이해되었다.)

특정

  • 알렉산드르 지노비예프, 다액의 논리학의 철학적 문제 D. 레이델 출판사, 169p, 1963.
  • 1957년 이전, 시간과 촬영장비. 1956년 존 로크의 강의를 토대로 한 옥스퍼드 대학 출판부
  • Goguen J.A. 1968/69, 부정확한 개념의 논리, Synthetse, 19, 325–373.
  • Chang C.C.Keisler H. J. 1966. 프린스턴, 프린스턴 대학교 출판부의 연속 모델 이론.
  • Gerla G. 2001, 퍼지 논리: Dordrecht, Kluwer 학술 출판사 근사 추론을 위한 수학 도구.
  • 파벨카 J. 1979, 퍼지 논리 I: 많은 가치 있는 추론 규칙, Zeitschr. f. 수학. 로직 und 그룬들라겐 d. 수학, 25, 45-52
  • Metcalfe, George; Olivetti, Nicola; Dov M. Gabbay (2008). Proof Theory for Fuzzy Logics. Springer. ISBN 978-1-4020-9408-8. Hahjek의 전통에서 많은 가치가 있는 논리학의 증명 이론도 다룬다.
  • Hähnle, Reiner (1993). Automated deduction in multiple-valued logics. Clarendon Press. ISBN 978-0-19-853989-6.
  • Azevedo, Francisco (2003). Constraint solving over multi-valued logics: application to digital circuits. IOS Press. ISBN 978-1-58603-304-0.
  • Bolc, Leonard; Borowik, Piotr (2003). Many-valued Logics 2: Automated reasoning and practical applications. Springer. ISBN 978-3-540-64507-8.
  • Stanković, Radomir S.; Astola, Jaakko T.; Moraga, Claudio (2012). Representation of Multiple-Valued Logic Functions. Morgan & Claypool Publishers. doi:10.2200/S00420ED1V01Y201205DCS037. ISBN 978-1-60845-942-1.
  • Abramovici, Miron; Breuer, Melvin A.; Friedman, Arthur D. (1994). Digital Systems Testing and Testable Design. New York: Computer Science Press. ISBN 978-0-7803-1062-9.

외부 링크