1차 논리

술어 논리, 수량 논리, 1차 술어 미적분으로도 알려진 1차 논리학은 수학, 철학, 언어학, 컴퓨터 과학에서 사용되는 공식 시스템의 집합입니다.1차 논리는 비논리적인 오브젝트 위에 계량화된 변수를 사용하고 변수를 포함하는 문장을 사용할 수 있도록 하여 "소크라테스는 사람이다"와 같은 명제 대신 "x는 소크라테스이고 x는 사람이다"라는 형태로 표현될 수 있습니다. 여기서 "존재한다"는 양화자이고, x는 ^[1]변수입니다.이것은 양적 논리나 ^[2]관계를 사용하지 않는 명제 논리와 구별된다; 이런 의미에서 명제 논리는 1차 논리의 기초이다.

주제에 대한 이론은 보통 특정한 담론의 영역과 함께 1차 논리이며, 그 영역에서 그 영역까지 확실히 많은 함수, 그 영역에 정의된 최종적인 많은 술어, 그리고 그것들에 대해 유지한다고 믿어지는 일련의 공리이다.때때로, "이론"은 단지 1차 논리의 문장 집합으로 더 형식적인 의미로 이해된다.

형용사 "1차"는 1차 논리와 고차 논리를 구별하는데, 이 논리에서는 술어 또는 함수를 인수로서 가지거나 술어 또는 함수에 대한 수량화가 ^{[3]: 56} 허용된다.1차 이론에서 술어는 종종 집합과 연관된다.해석된 고차 이론에서 술어는 집합 집합으로 해석될 수 있습니다.

1차 논리에는 건전한(즉, 모든 입증 가능한 진술이 참)과 완전함(즉, 모든 모델에서 참인 모든 진술이 입증 가능) 모두인 많은 연역 시스템이 있다.논리적 귀결 관계는 반값일 뿐이지만, 1차 논리에서 증명되는 자동화된 정리에서는 많은 발전이 이루어졌다.1차 논리는 또한 뢰벤하임-스콜렘 정리나 콤팩트성 정리 같은 증명 이론에서 해석할 수 있게 하는 몇 가지 금속학적 이론들을 충족시킨다.

1차 논리는 수학을 공리로 공식화하기 위한 표준으로 수학의 기초에서 연구된다.Peano 산술과 Zermelo-Fraenkel 집합론은 각각 수 이론과 집합론의 1차 논리학의 공리화이다.그러나 어떤 1차 이론도 자연수나 실선과 같이 무한 영역을 가진 구조를 독특하게 묘사할 수 있는 강점을 가지고 있지 않다.이 두 구조를 완전히 기술하는 공리 시스템(즉, 범주 공리 시스템)은 2차 논리와 같은 더 강력한 논리학에서 얻을 수 있습니다.

1차 논리의 기초는 Gottlob Frege와 Charles Sanders Peirce에 ^[4]의해 독립적으로 개발되었습니다.1차 논리의 역사와 그것이 어떻게 형식 논리를 지배하게 되었는지에 대해서는 호세 페레이로스(2001)를 참조한다.

서론

명제논리는 단순한 선언적 명제를 다루는 반면, 1차논리는 술어와 수량화를 추가로 다룬다.

술어는 담화 영역의 실체를 취하여 참 또는 거짓으로 평가합니다."Socrates is a philophist"와 "Plato is a philophist"라는 두 문장을 생각해보자.명제논리에서는 이들 문장은 관련이 없는 것으로 간주되며, 예를 들어 p와 q와 같은 변수에 의해 표시될 수 있다."는 철학자"라는 용어가 두 문장에서 발생하며, "a는 철학자"라는 공통 구조를 가지고 있다.변수 a는 첫 번째 문장에서 "Socrates"로 인스턴스화되고 두 번째 문장에서 "Plato"로 인스턴스화됩니다.1차 논리는 이 예에서 "철학자"와 같은 술어를 사용할 수 있지만, 명제 논리는 그렇지 않다.^[5]

술어 간의 관계는 논리적인 연결을 사용하여 나타낼 수 있습니다.예를 들어, "a가 철학자라면, a는 학자"라는 1차 공식을 생각해 보자.이 공식은 "a는 철학자"를 가설로 하고 "a는 학자"를 결론으로 하는 조건문이다.이 공식의 진리는 어떤 사물이 a로 나타내느냐와 "철학자"와 "학자"라는 술어의 해석에 따라 달라진다.

수식의 변수에 수량자를 적용할 수 있습니다.예를 들어, 앞의 공식에서 변수 a는 1차 문장으로 보편적으로 수량화할 수 있습니다. "For a, if a is are then scholar."이 문장의 "every"라는 보편적 수량어는 "만약 a가 철학자라면, a는 학자다"라는 주장이 a의 모든 선택에 대해 유지된다는 생각을 표현한다.

"모든 a에 대하여, 만약 a가 철학자라면, a는 학자입니다"라는 문장의 부정은 "a는 철학자가 되고 a는 학자가 아닌 그런 것이 존재합니다"라는 문장과 논리적으로 일치한다.실존적 수량화 "존재"는 "a는 철학자이고 a는 학자가 아니다"라는 주장이 a의 선택에 대해 유지된다는 생각을 나타낸다.

"철학자"와 "학자"는 각각 하나의 변수를 취한다.일반적으로 술어는 여러 변수를 사용할 수 있습니다.첫 번째 문장 "Socrates is the teacher of Plato"에서 술어 " is the teacher of"는 두 가지 변수를 취한다.

1차 공식의 해석(또는 모형)은 각 술어의 의미와 변수를 인스턴스화할 수 있는 엔티티를 지정합니다.이러한 실체는 담화 또는 우주의 영역을 형성하며, 일반적으로 빈 집합이 아닌 집합이어야 합니다.예를 들어, 모든 인간으로 구성된 담론의 영역과 "공화국의 저자였다"로 이해되는 "철학자이다"라는 술어를 가진 해석에서, 플라톤이 목격한 "철학자라는 것이 존재하는 것"이라는 문장은 사실로 보인다.

구문

1차 논리에는 두 가지 중요한 부분이 있습니다.구문은 어떤 유한한 기호 시퀀스가 1차 논리에서의 적절한 표현인지를 결정하는 반면, 의미론은 이러한 표현 뒤에 있는 의미를 결정합니다.

알파벳

영어와 같은 자연어와 달리 1차 논리의 언어는 완전히 형식적이어서 주어진 표현이 잘 형성되어 있는지 여부를 기계적으로 판단할 수 있다.올바른 형식의 표현에는 두 가지 주요 유형이 있습니다. 즉, 객체를 직관적으로 나타내는 용어와 참 또는 거짓일 수 있는 문장을 직관적으로 표현하는 공식입니다.1차 논리의 용어와 공식은 모든 기호가 함께 언어의 알파벳을 형성하는 기호 문자열입니다.모든 공식 언어와 마찬가지로, 기호 자체의 성격은 형식 논리의 범위를 벗어난다; 그것들은 종종 단순히 문자나 구두점 기호로 간주된다.

알파벳의 기호는 항상 같은 의미를 갖는 논리 기호와 해석에 따라 의미가 달라지는 비논리 기호로 나누는 것이 일반적입니다.예를 들어 논리 기호 ${\$ {$style$ \$land$}는$$ 항상 "and"를 나타냅니다. 논리 기호${\$ { $displaystyle \lor$로 표시되는 "or"로 해석되지 않습니다.다만, Phil(x)와 같은 논리가 아닌 술어 기호는 "x는 철학자", "x는 Philipar" 또는 기타 이름 있는 사람을 의미합니다.ry는 가까운 해석에 따라 기술됩니다.

논리 기호

논리 기호는 작성자에 따라 다르지만 일반적으로 ^[6]다음을 포함합니다.

• 정량자 기호 : for은 보편정량화, for은 실존정량화
• 논리적 연결: 연결의 경우 for, 연결의 경우 for, 연결의 경우 for, 함축의 경우 →, 이중의 경우 for, 부정의 경우 for.일부^[7] 저자는 ↔ 대신 Cpq를 사용하고 ↔ 대신 Epq를 사용합니다. 특히 →가 다른 목적으로 사용되는 상황에서는 더욱 그렇습니다.또한 편자 may는 →를 대체할 수 있으며, 트리플 바 may는 ↔를 대체할 수 있으며, Tilde(~), Np 또는 Fp는 ↔를 대체할 수 있으며, 더블 바${\({displaystyle$ $\backslash \},$ +({$displaystyle$ $+\})$ 또는 Apq는 and를 대체할 수 있으며, 앰퍼샌드 &, Kpq 또는 중간 도트 ⋅는 이러한 기호를 대체할 수 없습니다.(앞서 설명한 기호 Cpq, Epq, Np, Apq 및 Kpq는 폴란드어 표기법에서 사용됩니다.)
• 괄호, 대괄호 및 기타 구두점 기호.이러한 기호의 선택은 상황에 따라 달라집니다.
• 변수 무한 세트. 보통 알파벳 x, y, z, ...의 끝에 소문자로 표시됩니다.첨자는 변수를 구별하기 위해 자주 사용됩니다.x₀, x₁, x₂, ...
• 등호 기호(때로는 동일 기호) = (아래 § 등호 및 그 공리를 참조).

1차 로직에서는 이들 기호가 모두 필요한 것은 아닙니다.부정, 결합(또는 분리), 변수, 대괄호 및 동등성과 함께 계량자 중 하나로 충분합니다.

기타 논리 기호에는 다음이 포함됩니다.

• 참 상수: "참"의 경우 T, V 또는 for, "거짓"의 경우 F, O 또는 for(V와 O는 폴란드 표기법에서 유래).이러한 원자가 0의 논리 연산자가 없으면 이 두 상수는 수량자를 통해서만 표현될 수 있습니다.
• 셰퍼 스트로크, Dpq(낸드), 배타적 또는 Jpq 등의 추가 논리 연결.

논리가 아닌 기호

논리가 아닌 기호는 술어(관계), 함수 및 상수를 나타냅니다.과거에는 모든 목적에 대해 고정된 무한대의 비논리 기호 집합을 사용하는 것이 표준 관행이었습니다.

• 모든 정수 n ≤ 0에 대해 n-ary 또는 n-자리 술어 기호의 집합이 있습니다.n개의 요소 사이의 관계를 나타내기 때문에 관계 기호라고도 합니다.각 속성 n에 대해 무한히 공급됩니다.

  Pⁿ₀, Pⁿ₁, Pⁿ₂, Pⁿ₃, ...

• 모든 정수 n ≤ 0에 대해 n-ary 함수 기호는 무한히 많습니다.

  f ⁿ₀, f ⁿ₁, f ⁿ₂, f ⁿ₃, f, ...

술어 기호 또는 함수 기호의 정확성이 문맥에서 명확할 경우 종종 위첨자 n이 생략됩니다.

이 전통적인 접근법에는 1차 ^[8]논리의 언어가 하나밖에 없습니다.이 접근법은 특히 철학적인 책들에서 여전히 흔하다.

보다 최근의 관행은 사용자가 염두에 두고 있는 애플리케이션에 따라 서로 다른 비논리 기호를 사용하는 것입니다.따라서 특정 애플리케이션에서 사용되는 모든 비논리 기호 집합의 이름을 지정해야 합니다.이 선택은 ^[9]서명을 통해 이루어집니다.

수학에서 일반적인 서명은 그룹의 경우 {1, ×} 또는 단순히 {×}, 순서 필드의 경우 {0, 1, +, ×, <}입니다.논리가 아닌 기호의 수에는 제한이 없습니다.시그니처는 공백, 유한 또는 무한이며 셀 수 없는 경우도 있습니다.셀 수 없는 서명은 예를 들어 뢰벤하임-스콜렘 정리의 현대 증명에서 발생한다.

시그니처가 비논리적인 기호를 해석하는 방법을 나타내는 경우도 있습니다만, 시그니처의 비논리적인 심볼에 대한 해석은 별개입니다(반드시 고정된 것은 아닙니다).시그니처는 시멘틱스가 아닌 구문에 관련되어 있습니다.

이 접근법에서 모든 비논리 기호는 다음 유형 중 하나입니다.

• 0보다 크거나 같은 값의 술어 기호(또는 관계 기호)입니다.이들은 종종 P, Q, R 등의 대문자로 표시됩니다.예:
  • P(x)에서 P는 원자가 1의 술어 기호이다.가능한 해석 중 하나는 "x는 남자다"입니다.
  • Q(x,y)에서 Q는 원자가 2의 술어 기호이다.가능한 해석으로는 "x is greater than y" 및 "x is father of y"가 있습니다.
  • 원자가 0의 관계는 명제변수로 식별할 수 있으며, 명제변수는 임의의 스테이트먼트를 나타낼 수 있습니다.R에 대한 가능한 해석 중 하나는 "Socrates is a man"이다.
• 0보다 크거나 같은 원자가가 있는 함수 기호입니다.이들은 보통 f, g, h와 같은 소문자로 표시됩니다.예:
  • f(x)는 "x의 아버지"로 해석될 수 있다.산술적으로는 "-x"를 나타낼 수 있다.집합론에서는 "x의 거듭제곱 집합"을 나타낼 수 있습니다.
  • 산술에서 g(x,y)는 "x+y"를 나타낼 수 있다.집합론에서, 그것은 "x와 y의 결합"을 나타낼 수 있다.
  • 값 0의 함수 기호는 상수 기호라고 불리며, 종종 알파벳의 선두에 a, b, c와 같은 소문자로 표시됩니다.기호 a는 소크라테스의 약자일 수 있다.산술적으로는 0을 나타낼 수 있습니다.집합론에서는 빈 집합을 나타낼 수 있습니다.

기존의 접근 방식은 비논리적인 기호의 전통적인 시퀀스로 구성되도록 "맞춤" 서명을 지정하는 것만으로 현대적인 접근 방식으로 복구할 수 있습니다.

구성 규칙

<>index>.::)""개체, index>,"'"<>variable>.::)")"개체, index>,<>constant>.::)"c"개체, index>,>단항 function>.::)"f1"개체, index>,>2진 function>.::)"f2"개체, index>,<>3진 function>.::)"f"개체, index>,>단항 predicate>.::)"p1"개체, index>,>2진 속성이다.>::)"p2"개체, index>,<>3진 predicate>.::)"p3"개체, index>,<>term>.::=<>variable>,<>상수입니다.> <unary function> "(" <term> ")"                          <binary function> "(" <term> "," <term> ")"                          <ternary function> "(" <term> "," <term> "," <term> ")" <atomic formula> ::= "TRUE"                          "FALSE"                         <term> "=" &그것은, term>,>단항 predicate>,"("<>term>,")"<>bina.챙겨predicate>,"("<>term>,","<>term>,")"<>3진 predicate>,"("<>term>,","<>term>,","<>term>,")"<>formula>.::=<>원자 formula>,"¬"<>formula>, <, formula>,"∧"<>formula>, <, formula>,"∨"<>formula>, <, formula>,"⇒"<>formu.la>, <, formula>,"⇔"<>formula>,"("<>formula>,")""filename" <filename> <filename> <filename> <filename> <filename>

형성 규칙은 1차 논리의 ^[12]용어와 공식을 정의합니다.용어와 수식이 기호 문자열로 표현될 때, 이러한 규칙은 용어와 수식에 대한 정식 문법을 작성하는 데 사용될 수 있습니다.이러한 규칙은 일반적으로 문맥에 구애받지 않는다(각 제품의 왼쪽에는 단일 기호가 있다). 단, 기호 집합은 무한할 수 있고 시작 기호(예: 용어의 경우 변수)가 많을 수 있다.

조건.

용어 집합은 다음 규칙에 의해 유도적으로 정의됩니다.

• 변수.모든 변수는 용어입니다.
• 기능.n개의 인수(여기서 각 인수_i t는 항, f는 원자가 n의 함수 기호)의 임의의 식 f(t₁, …, t_n)는 항이다.특히, 개별 상수를 나타내는 기호는 무효 함수 기호이며, 따라서 항이다.

규칙 1과 규칙 2를 완전히 많이 적용함으로써 얻을 수 있는 표현만이 용어이다.예를 들어, 술어 기호를 포함하는 표현식은 항이 아닙니다.

수식

일련의 공식(Well-formed^[13] 수식(WFF)이라고도 함)은 다음 규칙에 의해 유도적으로 정의됩니다.

• 술어 기호.P가 n-ary 술어 기호이고₁ t, ..., t가_n 항이면 P(t₁, ...t_n)는 식이다.
• 평등.등식 기호가 논리의 일부로 간주되고₁ t와₂ t가 항이면₁ t₂ = t는 공식입니다.
• 부정.${\$ { $displaystyle$ \ $varphi }$가 공식일 경우$$ { $displaystyle$\$lnot$\$varphi }$는 공식입니다.
• 바이너리 접속${\$ { $displaystyle$\ $varphi }$ 및$$$display{\displaystyle }$ { $displaystyle$\ $psi$}의$$ 경우 ( ${\displaystyle }$ $ψ$ \ displaystyle \ $varphi$\ $rightarrow$\$psi$ $\}$ )는 식입니다.다른 바이너리 논리 접속에도 같은 규칙이 적용됩니다.
• 수량화.$"$ { $displaystyle$ \ $varphi$}" 가 식이고 x 가 변수인 경우 "${\displaystyle \mathrm{}x}$ $"$ (${\displaystyle \mathrm{모든}}$ x 에 $대해{\displaystyle }$ "$$\ $displaystyle \ varphi }"$ 와$$${\displaystyle \mathrm{}}$" ${\displaystyle x}$ " $(\$ $displaystyle$\ $exists$x\ $varphi$) " ($x{\displaystyle }$ 는$"$ style \ $varphi$ 를 $표시$합니다.)

규칙 1~5를 완전히 많이 적용함으로써 얻을 수 있는 표현식만이 공식이다.처음 두 규칙에서 얻은 공식은 원자 공식이라고 합니다.

예를들면,

$(\displaystyle \forall y(P(f(x)\rightarrow \neg(P(x)\rightarrow Q(f(y),x,z))))}$

f가 단항 함수 기호, P가 단항 술어 기호, Q가 삼항 술어 기호인 경우 공식입니다.단,${\displaystyle \mathrm{}x}$ ${\displaystyle x}$ x $→$ {$style \forall$ x$,x\right$ 화살표$}$는 알파벳 기호 문자열이지만 공식은 아닙니다.

정의에서 괄호의 역할은 귀납적 정의를 따름으로써(즉, 각 공식에 고유한 해석 트리가 있음) 어떤 공식도 한 가지 방법으로만 얻을 수 있도록 하는 것입니다.이 속성은 수식의 고유한 가독성이라고 합니다.공식에서 괄호가 사용되는 곳에는 많은 규칙이 있습니다.예를 들어, 일부 작성자는 괄호 대신 콜론 또는 마침표를 사용하거나 괄호가 삽입되는 위치를 변경합니다.각 저자의 특정 정의에는 고유한 가독성 증명이 수반되어야 합니다.

수식의 이 정의는 if-then-else 함수의 정의를 지원하지 않습니다.ite(c, a, b)여기서 "c"는 공식으로 표현되는 조건이며 c가 참이면 "a"를 반환하고 거짓이면 "b"를 반환합니다.이는 술어와 함수 모두 항을 모수로만 받아들일 수 있지만 첫 번째 모수는 공식이기 때문입니다.SMT-LIB 2.0과 같은 1차 로직을 기반으로 하는 일부 언어에는 ^[14]이 기능이 추가됩니다.

표기법

편의상 논리연산자의 우선순위에 관한 표기법이 개발되어 있어 경우에 따라 괄호를 쓸 필요가 없어집니다.이러한 규칙은 산술 연산 순서와 유사합니다.일반적인 규칙은 다음과 같습니다.

• $§$ $(\displaystyle$\lnot$)$이 먼저 평가됩니다${\displaystyle \mathrm{.}}$
• $다음으로 §(\displaystyle\$land$$$){\displaystyle }$ $및 §(\displaystyle\$lor$$)를 평가합니다${\displaystyle .}$
• 수량화자는 다음으로 평가됩니다.
• $→$ {\$displaystyle$\to$}$이($가)$ 마지막으로 평가됩니다${\displaystyle .}$

또한 수식을 읽기 쉽게 하기 위해 정의에 필요하지 않은 추가 구두점을 삽입할 수 있습니다.따라서 공식은

$\displaystyle \lnot \forall xP(x)\exists x(x)\lnot P(x)}$

라고 써져 있을지도 모른다

$\displaystyle (\lnot [\forall xP(x)])에서 \exists x[\lnot P(x)]로 이동합니다.}$

일부 필드에서는 위에서 정의한 접두사 표기 대신 이진 관계 및 함수에 infix 표기법을 사용하는 것이 일반적입니다.예를 들어, 산술에서는 일반적으로 "=((2,2,4)" 대신 "2 + 2 = 4"로 쓴다.infix 표기법의 공식은 접두사 표기법의 대응하는 공식의 약어로 간주하는 것이 일반적이다. cf. 또한 용어 구조 대 표현도 마찬가지이다.

위의 정의에서는 바이너리 접속에 infix 표기법을 사용하고 있습니다$($예:\$displaystyle$\to$）$ 。폴란드 표기법에서는 $→\displaystyle\rightarrow$$$∧\$displaystyle\$displaystyle$\$$to}$ 등$$)을 인수 앞에 씁니다.이 표기법은 모든 구두점 기호를 폐기할 수 있다는 점에서 유리합니다.이와 같이 폴란드어 표기법은 간결하고 우아하지만, 인간이 읽기 어렵기 때문에 실제에서는 거의 사용되지 않는다.폴란드 표기법에서 공식은

$(\displaystyle \forall y(P(f(x)\rightarrow \neg(P(x)\rightarrow Q(f(y),x,z))))}$

"subxxy→Pfxx"→PxQfyxz"가 됩니다.

자유 변수 및 제한 변수

공식에서 변수는 자유 또는 결합(또는 둘 다)될 수 있습니다.직관적으로 변수 발생은 ^[15]정량화되지 않은 경우 공식에서 자유롭다. δy P(x, y)에서는 변수 x의 유일한 발생은 자유이고 y의 발생은 결합되어 있다.수식의 자유변수 및 결합변수는 다음과 같이 유도적으로 정의됩니다.

기초 공식

is가 원자식인 경우 x는 φ에서 x가 발생하는 경우에만 if에서 free가 됩니다.게다가, 어떤 원자 공식에도 제한 변수가 없습니다.

부정

x가 에서 free인 경우 및 그 경우에 한해 free인 경우, x가 에서 bound인 경우 및 그 경우에 한해 free인 경우.

바이너리 접속

x는 x가 φ 또는 ψ 중 하나에서 free인 경우(free)에서 free인 경우(free → free)에서 발생하며, x는 ψ 또는 ψ 중 하나에서 free인 경우(free → free)에서 발생합니다.→ 대신 동일한 규칙이 다른 바이너리 연결에도 적용됩니다.

수량자

x가 y에서 자유롭고 x가 y와 다른 기호일 경우에만 y에서 자유롭다.또, x가 y 또는 x가 θ에 바인드 되어 있는 경우만, x는 y에 바인드 되어 있다.같은 규칙이 ∀ 대신에 in에도 적용됩니다.

예를 들어, δx δy(P(x) → Q(x,f(x),z))에서는 x와 y는 ^[16]결합만 발생하며 z는 자유만 발생하며 w는 공식에서 발생하지 않으므로 둘 다 발생하지 않습니다.

공식의 자유변수와 결합변수는 불연속 집합일 필요는 없다. 공식 P(x) → δx Q(x)에서 x의 첫 번째 발생은 P의 인수로서 자유이고, 두 번째 변수는 Q의 인수로서 결합되어 있다.

자유변수 발생이 없는 1차 논리식을 1차 문이라고 합니다.이러한 공식은 해석에 따라 명확한 진실 값을 갖는 공식입니다.예를 들어, Phil(x)과 같은 공식이 참인지 여부는 x가 무엇을 나타내는지에 따라 달라져야 합니다.그러나 문장 xx Phil(x)은 주어진 해석에서 참이거나 거짓일 것이다.

예: 순서화된 아벨 군

수학에서 순서화된 아벨 그룹의 언어는 하나의 상수 기호 0, 하나의 단항 함수 기호 -, 하나의 이진 함수 기호 + 및 하나의 이진 관계 기호를 가집니다.그 후, 다음과 같이 입력합니다.

• +(x, y)와 +(x, +(y, -(z)))는 용어입니다.이것들은 보통 x + y와 x + y - z로 표기됩니다.
• 식 +(x, y) = 0 및 δ(+(x, +(y, -(z), +(x, y)), +(x, y))는 원자식입니다.이 값은 일반적으로 x + y = 0 및 x + y - z x x + y로 표시됩니다.
• $식$(${\displaystyle \mathrm{}x}$ x${\displaystyle \mathrm{}[}$ ${\displaystyle y}$ [ + ${\displaystyle }$ ${\displaystyle y}$( x${\displaystyle }$,${\displaystyle y}$) ,${\displaystyle z}$ ) ${\displaystyle \to }$ ${\displaystyle \mathrm{\forall }}$ ${\displaystyle x、\mathrm{}}$ ${\displaystyle y}$ +${\displaystyle (}$( ${\displaystyle x}$, ${\displaystyle \mathrm{y}}$ ) ${\displaystyle =}$ 0${\displaystyle }$)$$\ $display$ style ( \ $forall$x \ $forall$ y $,$ [ \ $mathop$ { $+ } ( x$ ,$y$ ,$z$ ) \ $to$\$mathop all$)$ll y(x+y\leq z)\forall x\forall y(x+y=0).$} 이$$ 공식에는 하나의 자유 변수 z가 있습니다$.$

순서 있는 아벨 그룹의 공리는 언어의 문장 집합으로 표현될 수 있다.예를 들어, 그룹이 가환적이라는 공리는 보통 (${\displaystyle }$) ${\displaystyle x}$)${\displaystyle \mathrm{}}$(${\displaystyle }$) ${\displaystyle y}$)${\displaystyle }$[ ${\displaystyle x}$ + ${\displaystyle y}$ ${\displaystyle =}$ ${\displaystyle y}$+ x$]$ .\ displaystyle (\$forall$ x$)[$x + y$$= y$$+ x ] .\ $displaystyle (\forall$ x )[ x + y + x ]로${\displaystyle }$표기됩니다.$}$

의미론

1차 언어의 해석은 해당 언어의 각 비논리 기호(예약 기호, 함수 기호 또는 상수 기호)에 표현을 할당합니다.또한 수량화 범위를 지정하는 담론의 영역도 결정합니다.그 결과, 각 용어에 그것이 나타내는 객체가 할당되고, 각 술어에 객체의 속성이 할당되며, 각 문장에 참 값이 할당됩니다.이렇게 해석은 언어의 용어, 술어 및 수식에 의미적 의미를 부여합니다.형식 언어의 해석에 대한 연구는 형식 의미론이라고 불린다.다음은 1차 로직의 표준 또는 타르스키어 의미론에 대한 설명입니다.(1차 로직을 위한 게임 의미론을 정의하는 것도 가능하지만, 선택 공리를 요구하는 것 외에, 게임 의미론은 1차 로직을 위한 타르스키의 의미론과 일치하기 때문에, 여기서 게임 의미론은 상세하게 설명되지 않습니다.)

1차 구조

해석(특히 수학에서)을 지정하는 가장 일반적인 방법은 구조(모델이라고도 함)를 지정하는 것입니다.이 구조는 담화 D의 영역과 비논리 기호를 술어, 함수 및 상수에 매핑하는 해석 함수 I로 구성됩니다.

담화 D의 영역은 어떤 종류의 "객체"가 비어있지 않은 집합이다.직관적으로 해석하면 1차 공식은 이러한 오브젝트에 대한 스테이트먼트가 됩니다.예를 들어$,{\displaystyle \mathrm{}}$ ${\displaystyle \theta }$ x${\displaystyle P}$ ($x$) \ displaystyle \$exists x$P ($x$ ) states$$ the 、 D d d d 、 , p 、 , p p 、 p p p p p p p p 、 p p p p p p p p p p p p p p p p p p p p p p p p p p p in p p p in in p p p p p p p p in예를 들어, D는 정수 집합이라고 할 수 있습니다.

논리가 아닌 기호는 다음과 같이 해석됩니다.

• n-ary 함수 기호의 해석은 D에서ⁿ D까지의 함수입니다.예를 들어 담화 영역이 정수 집합인 경우, arity 2의 함수 기호 f는 그 인수의 합을 주는 함수로 해석될 수 있다.즉, 기호 f는 $함수{\displaystyle }$I (${\displaystyle f}$ $){displaystyle$ I$(f)}$와 관련지어지며, 이 해석에서는 덧셈입니다.

• 상수 기호(아리티 0의 함수 기호)의 해석은 D(빈 태플만 구성원으로 하는 집합)에서⁰ D까지의 함수이며, D의 물체로 간단히 식별할 수 있습니다.예를 들어 해석에 따라 상수 $기호{\displaystyle }$ c ${\displaystyle$ c$\}$에 값${\displaystyle }I{\displaystyle }$ (${\displaystyle c}$ ) $=$ ${\displaystyle 10}$ ${displaystyle$ I$(c$)= $10}$이 할당될 수 있습니다.

• n-ary 술어 기호의 해석은 D 요소의 n-튜플 집합으로, 술어가 참인 인수를 제공합니다.예를 들어, 이진 술어 기호 P의 $해석{\displaystyle I(}$P$)\displaystyle I($P)는$$ 첫 번째가 두 번째보다 작은 정수 쌍의 집합일 수 있습니다.이 해석에 따르면 첫 번째 인수가 두 번째 인수보다 작을 경우 술어 P가 참이 된다.마찬가지로 술어 심볼에는 ${\displaystyle D}$에서 { ${\displaystyle \mathrm{t}}$ r ${\displaystyle \mathrm{u}}$e, ${\displaystyle \mathrm{f}}$ ${\displaystyle \mathrm{a}}$ ${\displaystyle \mathrm{s}}$ e$$}(\$displaystyle \{\mathrm {true,false}$ $\backslash \})$까지의ⁿ${\displaystyle }$부울값 함수를 할당할 수 있습니다.

진실값 평가

해석과 각 변수와 담화 영역의 요소를 관련짓는 변수 할당 μ가 주어진 공식은 참 또는 거짓으로 평가된다.변수 할당이 필요한 이유는 y ${\displaystyle =}$ {\$displaystyle$ y$=x$와 $같이{\displaystyle }$ 자유 변수가 있는 공식에 의미를 부여하기 위해서입니다.이 공식의 참 값은 x와 y가 동일한 개인을 나타내는지에 따라 달라집니다.

우선 변수 할당μ는 언어의 모든 용어로 확장될 수 있으며, 그 결과 각 용어가 담화 영역의 단일 요소에 매핑된다.이 할당에는 다음 규칙이 사용됩니다.

• 변수.각 변수 x는 μ(x)로 평가됩니다.
• 기능.displaystyle ${$$1},$$…,$${\displaystyle }$$dn$ {$displaystyle d_{1},\ldots$$, d_$${$}, n-ary 함수 기호 ${\displaystyle {}_{}}$에 대해 ${\displaystyle {평가}_{}}$된 ${\displaystyle {}_{},}$ ${\displaystyle {}_{}}$ ${$$n$}, ${\displaystyle {tn}_{}}$$,$ $displaystyle$ f$({n$})를 $지정$하면 f$(t1$, …, t)는 표시됩니다$.$${\displaystyle )}$ ( ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$, ${\displaystyle ...}$ , ${\displaystyle {dn}_{}}$ ${\displaystyle {}_{}}$( $displaystyle ( I$ ( $f$) ; $d_{1}$ , \$ldots$,$d_{n}$ )$$。

다음으로 각 공식에 true 값이 할당됩니다.이 과제를 할 때 사용되는 귀납적 정의를 T-schema라고 합니다.

• 원자식 (1)${\displaystyle {}_{}}$P ( ${\displaystyle {t\mathrm{}}_{}}$1${\displaystyle }$, ${\displaystyle ...}$ ,${\displaystyle {}_{}{t}_{}}$ ${\displaystyle {}_{}}$) { $displaystyle$P ( $t$_ {1} , \$ldots$, t$_$ { $n$} } is$$ 、${\displaystyle {v\mathrm{}}_{}}$ 1${\displaystyle {}_{}、}$ ${\displaystyle ...}$ , ${\displaystyle v_{}}$ n${\displaystyle i}$I${\displaystyle }$( P$$) \ $displaystyle$\$langle$ v _ {1$}$ , \$ldots$, $v _ n$ \ $rangin$（ \ $lang$ P$）$$$） 、 。$rms{\displaystyle {}_{}}$ t ${\displaystyle {1\mathrm{}}_{}}$, ${\displaystyle ...}$ , ${\displaystyle t_{}}$n { $display$ style $t$_ {$1}$ , \$ldots$, t$_$ { $n$} 및$$ ${\displaystyle I}$(${\displaystyle }$P$$) { $display style$ I $( P$ ) $the$ 、 P { $display style$ P$$} 。이것은 D$$ { $display d^$ { $n$}의 서브셋이라고 가정하고 있습니다.
• 원자식 (2)${\displaystyle {t\mathrm{}}_{}}$ $($ $스타일$ t_{1$$}$=$$t_{$2$})$과$t$2$($ t_${1$})의 $공식{\displaystyle {}_{}}$ t1 ${\displaystyle {}_{}}$ ${\displaystyle {t2}_{}}$는 true로 지정된다(아래의 평등 섹션 참조).
• 논리적인 접속$displaystyle \neg \varphi }$】, 【 ${\displaystyle \to }$】({ $displaystyle \varphi \rightarrow \psi$ $\}$ 등) 형식의 공식은 명제논리와 같이 해당 접속자에 대한 진실표에 따라 평가된다.
• 존재 한정자.${\displaystyle x}$의 평가와 $관련$하여$μ$와 다른 변수 $중{\displaystyle {}^{}}$ ${\displaystyle \mu }$ μ${\$ {\$displaystyle$ $\mu$}만이$$$$ 존재하는 경우, M $및{\displaystyle }$μ {\$displaystyle$$\mu$$}$의 공식${\displaystyle \mathrm{}}$to x ${\displaystyle (}$ (${\displaystyle }$x$)$는 M 및 μ {\displaystyle \$mu$ }에$$$$ 따라 참이다.및 변수 $할당{\displaystyle {}^{}}$ μ$${\ ${\displaystyle {（}^{}}$ \ $display$style \ $mu$ '$）$ 。이 정식 정의에서는 x${\displaystyle (}$x)가 충족되도록 x 값을 선택할 수 있는 방법이 있는 ${\displaystyle \mathrm{경우}}$에만 x$(x)가$$$참임을 나타냅니다.
• 범용 수량자.해석 M에 의해 구성되는 모든 쌍에 대해 μ($x$)가 참이고 x의 값에 $대해서$만 μ$\$displaystyle \$mu'$와 다른$$ 변수 $할당{\displaystyle {}^{}}$ μ$$μ$x$)가 참이면 식${\displaystyle \mathrm{}\mathrm{\delta x}}$ （${\displaystyle x}$） { $displaystyle$$$\$varphi (x$ )는 M $및$μ {$displaystyle \$mu$$ }에 따라 참입니다.이것은 x에 대해 가능한 모든 값의 선택이 true가${\displaystyle \mathrm{}\mathrm{되는}}$ 경우 "${\displaystyle x}$ ${\displaystyle "}$ (${\displaystyle x}$ $)\displaystyle \forall x\varphi (x$)"가 true라는 개념을 캡처합니다.

수식에 자유 변수가 포함되어 있지 않고 문장도 포함되어 있는 경우 초기 변수 할당은 해당 참값에는 영향을 주지 않습니다.즉, M 및 기타 모든 변수 $할당{\displaystyle {}^{}}$ μ μ ${\$ \ $display$style \ $mu$에 따라 참인 경우에만 M $및{\displaystyle }$μ {\ displaystyle \ mu$$$$}에 따라 참인 문장이 됩니다.

변수 할당 함수에 의존하지 않는 진실 값을 정의하는 두 번째 일반적인 방법이 있습니다.대신 해석 M이 주어지면 먼저 M에서 담화 영역의 각 요소에 대해 하나씩 상수 기호 컬렉션을 서명에 추가한다. 예를 들어 도메인의 각 d에 대해 상수_d 기호 c가 고정된다고 하자.각 새로운 상수 기호가 도메인의 해당 요소에 할당되도록 해석이 확장됩니다.이제 다음과 같이 정량화된 공식에 대한 참을 구문적으로 정의한다.

• 존재 수량자(대체).${\displaystyle (}$ ${\displaystyle {}_{}{d}_{}}$) \ $displaystyle$ \ $varphi$$($$c$_ { d$$} )와 같이 담화 영역에 d가 있는 경우, 식${\displaystyle \mathrm{}\theta }$ x$$ (${\displaystyle }$x$$) ( x ) {$$$displaystyle$ \ varphi ( c _ { d )는$$$$ M에 따라 참이다.$여기$서 ${\displaystyle (}$ ( ${\displaystyle {}_{}{d}_{}}$ )$${ $displaystyle$\ $varphi$( $c$_ { $d$} }는$$ φ 내의 x가 자유롭게 발생할 때마다 c로 치환한_d 결과입니다.
• 범용 수량자(대체).담화 영역의 d마다 m에 따라${\displaystyle }\theta {\displaystyle }$ ( ${\displaystyle {}_{}{d}_{}}$ )$$\ $displaystyle$\$varphi$ ( c$_$ { $d$)가$$ 참이면 식${\displaystyle \mathrm{}}$θ ${\displaystyle x\theta }$ ( ${\displaystyle x}$ )${\displaystyle }${$displaystyle$\ $forall$ x \$$$varphi ( x$ )는$$ M에 따라 참이다.

이 대체 접근법은 변수 할당을 통해 접근법과 정확히 동일한 참 값을 모든 문장에 제공한다.

타당성, 만족도 및 논리적 결과

문장 evaluates이 특정 해석 M에서 true로 평가되면 M이 ;을 만족한다고 말할 수 있다.이것은 M $⊨$(\$display$ M$\vDash\varphi$ $\}$로 $표기$된다^[17].이 문장은 어느 정도 해석이 있으면 만족할 수 있다.

자유 변수가 있는 공식의 만족도는 해석 자체로는 이러한 공식의 참 값을 결정하지 않기 때문에 더 복잡합니다.가장 일반적인 관례는 자유변수를 갖는 공식은 담론의 영역에서 어떤 개인이 자유변수에 할당되어 있는지에 관계없이 공식이 참으로 유지된다면 해석에 의해 충족된다고 말한다.이것은 공식이 보편적 폐쇄를 만족하는 경우에만 만족한다고 말하는 것과 같은 효과를 가진다.

공식은 ^[18]모든 해석에서 참일 경우 논리적으로 유효합니다(또는 단순히 유효합니다).이 공식들은 명제 논리학의 반복론과 비슷한 역할을 한다.

true를 참으로 하는 모든 해석이 true을 참으로 만드는 경우, 식 is은 식 if의 논리적 결과이다.이 경우 is은 논리적으로 ψ에 내포되어 있다고 할 수 있습니다.

대수화

1차 논리의 의미론에 대한 대체 접근법은 추상대수를 통해 진행된다.이 접근법은 린덴바움-을 일반화한다.명제논리학의 타르스키 대수학.수량화 변수를 1차 로직에서 제거하는 방법에는 다음과 같은 세 가지가 있으며, 수량화자를 다른 변수 바인딩 항 연산자로 대체하는 것이 포함되지 않습니다.

• Alfred Tarski와 동료들의 원통 대수
• 폴 할모스의 폴리아드 대수
• 함수자 논리 술어인데 주로 윌러드 콰인 때문이지

이러한 대수는 모두 2-원소 부울 대수를 적절히 확장하는 격자이다.

타르스키와 기반트(1987)는 3개 이상의 양자화 범위에 있는 원자문이 없는 1차 논리의 단편은 관계 ^{[19]: 32–33} 대수와 동일한 표현력을 갖는다는 것을 보여주었다.이 조각은 표준 ZFC를 포함한 페아노 산술과 가장 자명한 집합론에 적합하기 때문에 매우 흥미롭다.그들은 또한 원시 순서쌍을 갖는 1차 논리가 2개의 순서쌍 ^{[20]: 803} 투영함수를 갖는 관계대수와 동등하다는 것을 증명한다.

1차 이론, 모델 및 초급

특정 서명의 1차 이론은 그 서명의 기호로 구성된 일련의 공리입니다.공리의 집합은 종종 유한하거나 재귀적으로 열거할 수 있으며, 이 경우 이론이 효과적이라고 불립니다.일부 저자들은 이론이 공리의 모든 논리적 결과도 포함하도록 요구한다.공리는 이론 내에서 유지되는 것으로 간주되고 그것들로부터 이론 내에서 유지되는 다른 문장들을 도출할 수 있다.

주어진 이론에서 모든 문장을 만족시키는 1차 구조를 이론의 모델이라고 한다.초등 클래스는 특정 이론을 만족시키는 모든 구조의 집합이다.이 수업들은 모델 이론의 주요 연구 주제이다.

많은 이론들이 이론을 연구할 때 염두에 두는 특정한 모델인 의도된 해석을 가지고 있다.예를 들어, Peano 산술의 의도된 해석은 통상적인 자연수와 통상적인 연산으로 구성됩니다.그러나 뢰벤하임-스콜렘 정리는 대부분의 1차 이론이 다른 비표준 모델을 가질 것이라는 것을 보여준다.

이론의 공리로부터 모순을 증명할 수 없다면 이론은 일관성이 있다.이론은 그 서명에 있는 모든 공식에 대해, 그 공식 또는 그 부정 중 하나가 이론의 공리들의 논리적 결과물일 때 완전하다.괴델의 불완전성 정리는 자연수 이론의 충분한 부분을 포함하는 효과적인 1차 이론이 결코 일관되고 완전할 수 없다는 것을 보여준다.

빈 도메인

위의 정의는 모든 해석의 담론 영역을 비워두지 않아야 한다.빈 도메인이 허용되는 포괄적인 로직 등의 설정이 있습니다.게다가 대수 구조의 클래스가 빈 구조를 포함하고 있는 경우(예를 들어 빈 포셋이 있는 경우), 그 클래스는 빈 도메인이 허용되거나 빈 구조가 클래스에서 삭제되는 경우에만 1차 로직의 초급 클래스가 될 수 있습니다.

그러나 빈 도메인에는 몇 가지 문제가 있습니다.

• 많은 일반적인 추론 규칙은 담론의 영역이 비어있지 않아야 할 때만 유효하다.예를 들어 $x$가 $\displaystyle \varphi$$\lor \exists x\psi$의 자유변수가 아닌 경우 $x{\displaystyle }$$displaystyle$\exists x$(\varphi$$$\$lor$ \$psi$$))$를 의미함을 나타내는 규칙이 있습니다.이 규칙은 정규식으로 사용됩니다.nd 빈 도메인이 허용되는지 여부.
• 범위가 비어 있는 변수 할당 함수가 없기 때문에 변수 할당 함수를 사용하는 해석에서 참의 정의는 빈 도메인에서는 사용할 수 없습니다(마찬가지로 상수 기호에는 해석을 할당할 수 없습니다).이 진실 정의에서는 원자식에 대한 진실 값을 정의하기 전에 변수 할당 함수(위 μ)를 선택해야 합니다.그리고 문장의 진실값은 변수 할당 하에서의 진실값으로 정의되며, 이 진실값은 어떤 할당이 선택되느냐에 따라 달라지지 않는다는 것이 증명된다.이 기술은 할당 기능이 전혀 없는 경우에는 작동하지 않습니다.빈 도메인을 수용하기 위해 변경해야 합니다.

따라서 빈 도메인이 허용되면 종종 특수한 경우로 취급해야 합니다.그러나 대부분의 저자는 정의상 빈 도메인을 제외합니다.

연역법

연역체계는 하나의 공식은 다른 공식의 논리적 결과라는 것을 순수하게 통사적으로 증명하기 위해 사용된다.1차 논리에는 힐베르트식 연역 체계, 자연 연역 체계, 순차 미적분, 표법, 분해능 등 많은 시스템이 있다.이것들은 추론이 유한 구문 객체라는 공통 속성을 공유합니다. 이 객체의 형식과 구성 방법은 매우 다양합니다.이러한 유한 추리 자체는 종종 증명 이론에서 파생이라고 불린다.그것들은 종종 증명이라고도 불리지만, 자연어 수학적 증명과는 달리 완전히 정형화 되어 있다.

연역 시스템은 시스템에서 도출될 수 있는 공식 중 어떤 것이 논리적으로 타당하다면 타당하다.반대로 논리적으로 유효한 모든 공식이 파생될 수 있다면 연역체계는 완전하다.이 문서에서 설명하는 시스템은 모두 건전하고 완전합니다.그들은 또한 유효한 것으로 알려진 공제가 실제로 공제인지 효과적으로 확인할 수 있는 재산을 공유한다. 이러한 공제 제도를 유효하다고 한다.

연역 시스템의 핵심 특성은 그것들이 순전히 통사적이어서, 어떠한 해석도 고려하지 않고 도출을 검증할 수 있다는 것이다.그러므로 타당한 주장은 그 해석이 수학, 경제학 또는 다른 분야에 관한 것이든 상관없이 가능한 모든 언어 해석에서 옳다.

일반적으로, 1차 논리에서의 논리적 결과는 반감각일 뿐이다: 만약 문장 A가 논리적으로 문장 B를 의미한다면, 이것은 발견될 수 있다(예를 들어, 효과적이고, 건전하고, 완전한 증명 시스템을 사용하여 발견될 때까지 증거를 찾는 것).그러나 A가 논리적으로 B를 의미하지 않는 경우, 이것은 A가 논리적으로 B의 부정을 의미한다는 것을 의미하지 않는다.A와 B가 주어진 공식에 따라 A가 논리적으로 B를 의미하는지 여부를 항상 정확하게 결정하는 효과적인 절차는 없습니다.

추론 규칙

추론 규칙은 가설로서 특정 특성을 갖는 특정 공식(또는 공식 집합)이 주어지면 결론으로서 다른 특정 공식(또는 공식 집합)을 도출할 수 있다는 것이다.해석은 가설을 만족시킬 때마다 그 해석도 결론을 만족시킨다는 점에서 타당성을 유지한다면 이 규칙은 타당하다(또는 진실 보존).

예를 들어, 하나의 일반적인 추론 규칙은 치환 규칙이다.t가 항이고 θ가 변수 x를 포함할 수 있는 공식인 경우, θ[t/x]는 모든 x의 자유 인스턴스를 θ의 t로 치환한 결과입니다.치환규칙은 치환과정 중에 자유변수 t가 결합되지 않는 한 임의의 θ 및 임의의 항 t에 대해 θ에서 [t/x]를 결론지을 수 있음을 명시하고 있다.(t의 어떤 자유변수가 결합이 되면 t를 x로 대체하려면 먼저 θ의 결합변수를 t의 자유변수와 다르게 변경해야 한다.)

바운드 변수에 대한 제한이 필요한 이유를 알기 위해서는 산술의 (0,1,+,×,=) 서명에${\displaystyle \mathrm{}\theta }$x (${\displaystyle x}$ ${\displaystyle =y}$) {$displaystyle \displaystyle$ x$(x=y$가 부여한 논리적으로 유효한 공식 θ를 검토한다.t가 "x + 1"인 경우 공식 θ[t/y]는${\displaystyle \mathrm{}\theta }$x ( ${\displaystyle x}$ ${\displaystyle =x}$ +${\displaystyle 1}$)$${$displaystyle \displaystyle$ x $(x = x$ + $1)}$이며$,$ 이는 많은 해석에서 잘못된 것입니다.문제는 치환 중에 자유 변수 x(t)가 결합되었다는 것입니다.원하는 대체는 θ의 결합 변수 x의 이름을 z로 바꾸면 얻을 수 있으며, 치환 후의 공식은${\displaystyle \mathrm{}}$θ z (${\displaystyle z}$ ${\displaystyle =x}$ +$$) {$displaystyle$ \$displaystyle z(z =$ x + 1$)\}$$$이며, 이는 다시 논리적으로 유효합니다.

대체 규칙은 추론 규칙의 몇 가지 공통적인 측면을 보여준다.그것은 완전히 구문적이다; 사람들은 어떤 해석에도 호소하지 않고 그것이 올바르게 적용되었는지 알 수 있다.적용할 수 있는 시기에 대한 (구문적으로 정의된) 제한이 있으며, 이는 파생상품의 정확성을 유지하기 위해 존중되어야 한다.더욱이, 종종 그렇듯이, 이러한 제한은 추론 규칙에 포함된 공식의 구문 조작 중에 발생하는 자유 변수와 경계 변수 사이의 상호작용 때문에 필요하다.

힐베르트식 시스템과 자연감산

힐베르트식 연역 체계에서 추리는 각각 논리 공리인 공식의 목록이며, 가까운 유도에 대해 가정된 가설이거나 추론 규칙을 통해 이전의 공식에서 나온 것이다.논리 공리는 논리적으로 유효한 공식의 몇 가지 공리 스키마로 구성되어 있습니다; 이것들은 상당한 양의 명제 논리를 포함합니다.추론 규칙은 수량화 조작을 가능하게 한다.전형적인 힐베르트식 시스템은 논리 공리의 몇 가지 무한 스키마와 함께 소수의 추론 규칙을 가지고 있다.추론 규칙으로는 모더스 포넨과 보편화만 있는 것이 일반적이다.

자연감산시스템은 공식이 유한한 리스트라는 점에서 힐베르트식 시스템과 유사하다.그러나, 자연 감점 시스템은 논리적 공리를 가지고 있지 않다; 그들은 증명된 공식에서 논리적 연결을 조작하는데 사용될 수 있는 추가 추론 규칙을 추가함으로써 보상한다.

시퀀트 미적분

순차적 미적분은 자연감산 ^[21]시스템의 특성을 연구하기 위해 개발되었다.한 번에 하나의 공식으로 작업하는 대신 형식의 표현인 시퀀스를 사용합니다.

${\displaystyle A_{1},\ldots,A_{n}\vdash B_{1},\ldots,B_{k}}$

여기서₁ A, ..., A_n, B₁, ..., B는_k 공식이며 턴스타일 기호$${\(\$displaystyle\vdash)$은 두 반을 구분하기 위한 구두점으로 사용됩니다.직감적으로 시퀀스는 (${\displaystyle {A\mathrm{}}_{}}$ 1 ${\displaystyle \wedge A_{}}$n )$${ $displaystyle (A_{1}$ \$land \cdots \land$ A_${n})$}이$$ (${\displaystyle {B\mathrm{}}_{}}$ 1 ${\displaystyle \vee }$ ${\displaystyle B_{}}$k$$) { $displaystyle (B_{1}\lor \cdots \lor$ B_${k$${\displaystyle }$를 의미한다는 생각을 나타냅니다.

타블로법

명제식((a ∨ b b) b b) → a에 대한 표류 증명.

방금 설명한 방법과는 달리 tableaux 방법의 파생은 공식 목록이 아닙니다.대신, 파생은 공식의 나무입니다.공식 A가 증명 가능하다는 것을 보여주기 위해 표법에서는 A의 부정이 만족스럽지 않다는 것을 증명하려고 합니다.파생 트리의 루트에는 $\S {\displaystyle \mathrm{}}$ $(\displaystyle\lnot$ A$)$가 있으며, 트리는 공식의 구조를 반영하는 방식으로 분기합니다.예를 들어 C${\displaystyle d}$D \ $display style$$$C \ $lor$ D$is$ that that for${\displaystyle }$for C \ lor D is showing showing 、 $C{\displaystyle }$ D$$d c c c c forC\$lor$ D의$$ 트리의 분기점에 대응하여 C와 D가 불만족임을 나타낼 필요가 있습니다.

결의안

해상도 규칙은 통일과 함께 1차 논리에 대해 건전하고 완전하다는 단일 추론 규칙이다.타블로법과 마찬가지로 해당 공식의 부정이 만족스럽지 않음을 보여줌으로써 공식을 증명한다.분해능은 자동 정리 증명에 일반적으로 사용됩니다.

분해 방법은 원자 공식의 분절인 공식에서만 작동합니다. 임의 공식은 먼저 스콜렘화를 통해 이 형식으로 변환되어야 합니다.${\displaystyle {해결}_{}}$ 규칙은 가설 $A{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle \vee }$ A${\displaystyle k_{}c}$ C$$\ $display A_{1}\lor \cdots$$$\$lor$ A_${$$k}\lor$ C$$$b$ b ${\displaystyle {B\mathrm{}}_{}}$ ${\displaystyle {}_{}\vee }$ \ $display style B_{1}\$lor \$cdots \lor B$가 아님을 나타냅니다$.${$1}\lor \cdots \lor$ B_${l}$을(를) 얻을 수 있습니다$.$

증명 가능한 아이덴티티

많은 동일성이 입증될 수 있으며, 이는 특정 공식 간의 동등성을 확립한다.이러한 ID를 사용하면 다른 연결 간에 수량자를 이동함으로써 수식을 재배치할 수 있으며, 수식을 사전 정규 형식으로 배치할 때 유용합니다.증명 가능한 ID에는 다음이 포함됩니다.

$\displaystyle \lnot x,P(x)\왼쪽 화살표 \exists x,\lnot P(x)}$

$\displaystyle \lnot \exists x,P(x)\왼쪽 화살표 \forall x,\lnot P(x)}$

$\displaystyle \forall x,\forall y,P(x,y)\왼쪽 화살표 \forall y,\forall x,P(x,y)}$

$\displaystyle \exists x,\exists y,P(x,y)\왼쪽 화살표 \exists y,\exists x,P(x,y)}$

$(\displaystyle \forall x,P(x)\land \forall x,Q(x)\왼쪽 화살표 \forall x,(P(x)\land Q(x)})}$

$(\displaystyle \exists x,P(x)\lor \exists x,Q(x)\왼쪽 화살표 \exists x,(P(x)\lor Q(x))})$

${\displaystyle P}$x${\displaystyle \mathrm{}x\mathrm{、}}$ Q ( ${\displaystyle x}$ ${\displaystyle )x}$ ( ${\displaystyle Pq}$Q ( $)\$ $display style$P \$land$ \ $exists x$, $Q$( x )\ $rightarrow$\ $exists$ x , ($P$ \ $land$Q ($$x ) $$。$여기$서 x$\$ $display style$x 는$$ P$\$ $display style$ P$\backslash$ land \ existsists }에서 해방되어서는 안 됩니다.

${\displaystyle P}$ "${\displaystyle }$" ${\displaystyle x\mathrm{}Q}$(${\displaystyle x}$ ${\displaystyle )"x}$ ( ${\displaystyle P}$"${\displaystyle Q}$ (${\displaystyle x}$)$$\ $display style$P \$lor$ \ $forall$x ,$Q$ ($x$ ) \ light $arrow$\$forall$ x , ($P$ \ $lor$Q ($x$ ) $$。$여기$서 x$\$ $display style$x 는$$ P$\$ $display style$ P$\backslash$ larrow \ forall x , x ( x ) ） 。

평등과 그 공리

1차 로직에서 등식(또는 등식)을 사용하는 데는 몇 가지 다른 규칙이 있습니다.평등 1차 논리로 알려진 가장 일반적인 규약은 항상 담화 영역의 구성원들 사이의 진정한 평등 관계로 해석되는 원시적 논리 기호로서 평등 기호를 포함하며, 따라서 주어진 두 구성원은 같은 구성원이다.이 접근법은 또한 채용된 연역 체계에 평등에 대한 특정한 공리를 추가한다.이러한 등식 공리는 다음과 같습니다.^{[22]: 198–200}

• 반사성.각 변수 x에 대해 x = x입니다.
• 함수의 대체.모든 변수 x와 y 및 함수 기호 f에 대해

  x = y → f(...x, ...) = f(...y, ...)입니다.

• 수식의 대체입니다.임의의 변수 x와 y 및 임의의 공식 θ(x)에 대하여, θ의 임의의 수의 자유 발생을 y로 치환하여 얻을 수 있는 경우, 이러한 y의 자유 발생이 유지되도록 한다.

  x = y → (변수 → '').

이것들은 공리 스키마로, 각각 무한한 공리 집합을 지정합니다.세 번째 스키마는 라이프니츠의 법칙, "대체성의 원리", "일치체의 구별 불가능", 또는 "대체 속성"으로 알려져 있다.함수 기호 f를 포함하는 두 번째 스키마는 공식을 사용하여 세 번째 스키마의 특수한 경우(동등)입니다.

x = y → (f(...., x, ...) = z → f(...., y, ...) = z).

평등의 다른 많은 속성은 위의 공리의 결과입니다. 예를 들어 다음과 같습니다.

• 대칭.x = y이면 y = ^[23]x입니다.
• 이동성x = y 및 y = z이면 x = ^[24]z입니다.

등식이 없는 1차 논리

대안적 접근법은 평등 관계를 비논리적인 기호로 간주한다.이 규칙은 동등하지 않은 1차 로직으로 알려져 있습니다.서명에 평등 관계가 포함되어 있는 경우, 평등 공리는 논리의 규칙으로 간주되는 것이 아니라 검토 중인 이론에 추가되어야 한다.이 방법과 동등성을 갖는 1차 논리의 주된 차이점은 해석은 이제 두 개의 구별되는 개인을 "동일"로 해석할 수 있다는 것이다(라이브니즈의 법칙에 따르면, 이들은 어떤 해석에서도 정확히 동일한 공식을 만족할 것이다).즉, 이제 평등 관계는 해석의 기능과 관계와 관련하여 일치하는 담화 영역의 임의 등가 관계에 의해 해석될 수 있다.

이 두 번째 규칙을 따를 때 정규 모델이라는 용어는 a = b를 만족하는 개별 a와 b가 없는 해석을 지칭하는 데 사용됩니다.등식을 갖는 1차 논리에서는 정규 모형만 고려되므로 정규 모형 이외의 모형에 대한 항은 없습니다.등식이 없는 1차 논리를 연구할 때, 뢰벤하임-스콜렘 정리 같은 결과의 진술을 수정하여 정규 모델만 고려하도록 할 필요가 있다.

보통 자연수 집합 간의 등가 관계가 생략되는 2차 산술 및 다른 고차 산술 이론의 맥락에서 등가 없는 1차 논리가 종종 사용된다.

이론 내에서의 평등 정의하다

만약 어떤 이론이 반사율과 라이프니츠의 법칙을 만족시키는 이항 공식 A(x,y)를 가지고 있다면, 그 이론은 동등함을 가지고 있거나 동등함을 가진 이론이라고 한다.그 이론은 위의 스키마의 모든 예를 공리로서 가지는 것이 아니라 파생 가능한 이론으로서 가지는 것일지도 모른다.예를 들어, 함수 기호가 없고 관계 수가 유한한 이론에서, 모든 인수의 s를 t로 바꿈으로써 관계가 변하지 않는 경우 s와 t의 두 항을 동일하게 정의함으로써 관계의 관점에서 동등함을 정의할 수 있다.

일부 이론은 평등에 대한 다른 임시 정의를 허용합니다.

• 하나의 관계 기호 θ를 갖는 부분 차수 이론에서는 s = t를 s t t ≤ t ≤ s의 약자로 정의할 수 있다.
• 하나의 관계 θ를 갖는 집합론에서는 s = t를 δx(s δx ↔ t δx) δx(x δs ↔ x δt)의 약자로 정의할 수 있다.그러면 평등에 대한 이 정의는 자동으로 평등 공리를 만족시킵니다.이 경우 일반적인 확장 공리인${\displaystyle \mathrm{}\mathrm{xx}}$[ y [ ${\displaystyle \mathrm{\forall }z}$ ( z ${\displaystyle \in xz}$ z${\displaystyle y}$y )${\displaystyle \mathrm{xx}}$ ${\displaystyle =y}$]{ $display$style \$forall$ x$\forall$ y [ \$forall$z ($z$ \ $in$x \ $Leftarrow$z \ $in$ y$$]\ display style \forall z \ $forall$ y \ forall y \ ]로 표기할 수 있습니다.오른쪽 $화살표$ x$=y$ 대체 공식${\displaystyle \mathrm{}\mathrm{xx}}$ ${\displaystyle \mathrm{\forall }}$y [ ${\displaystyle \mathrm{\forall }}$z ( ${\displaystyle z}$ ${\displaystyle \in }$ ${\displaystyle x}$ ${\displaystyle \iff }$ ${\displaystyle z}$∈ y )${\displaystyle \mathrm{\Rightarrow }}$ ( (${\displaystyle z}$ ( x${\displaystyle z}$ ${\displaystyle y\in }$ ${\displaystyle z}$ ) $]{$ $displaystyle \forall$ x$\forall$ y [\$forall$z ($z$ \$in$x \ $rightarrow z$ \ $in$ \ y \ )$$}오른쪽 $화살표 \forall$ z$(x\in$z\왼쪽 $화살표$ y$\in$ z$)]\}:$ 세트x 와 y 가 같은 요소를 가지는 경우, 같은 세트에도 속합니다.

금속학적 특성

고차 논리보다 1차 논리를 사용하는 한 가지 동기는 1차 논리가 더 강한 논리에는 없는 많은 금속학적 특성을 가지고 있다는 것입니다.이러한 결과는 개별 이론의 속성보다는 1차 논리 자체의 일반적인 특성과 관련이 있습니다.그들은 1차 이론의 모델을 구성하기 위한 기본적인 도구를 제공한다.

완전성 및 판별 불가능성

1929년 Kurt Gödel에 의해 증명된 Gödel의 완전성 정리는 1차 논리에는 건전하고 완전하며 효과적인 연역 체계가 있다는 것을 확립하고, 따라서 1차 논리 결과 관계는 유한한 증명 가능성에 의해 포착된다.순진하게, 공식 logically이 논리적으로 의미한다는 문장은 ;의 모든 모델에 의존하며, 일반적으로 이들 모델은 임의적으로 큰 카디널리티이므로 논리적인 결과를 모든 모델을 체크하는 것으로는 효과적으로 검증할 수 없다.단, 모든 유한파생물을 열거하여 φ에서 from의 파생물을 검색할 수 있다.만약 is가 논리적으로 ,에 내포되어 있다면, 결국 그러한 파생이 발견될 것이다.따라서 1차 논리 결과는 반값이다. 즉, 모든 문장 쌍(,, consequ)을 효과적으로 열거하여 is가 φ의 논리 결과임을 알 수 있다.

명제논리와는 달리, 1차논리는 언어가 적어도 2(등식 제외)의 정의의 술어를 하나 가지고 있는 한 결정할 수 없다.즉, 임의의 수식이 논리적으로 유효한지 여부를 결정하는 결정 절차가 없습니다.이 결과는 1936년과 1937년 각각 알론조 교회와 앨런 튜링에 의해 독립적으로 확립되었고, 1928년 데이비드 힐베르트와 빌헬름 아커만이 제기했던 "엔체이둥슈프로" 문제에 부정적인 답을 주었다.이들의 증명은 1차 논리에 대한 결정 문제의 해결 불가능성과 정지 문제의 해결 불가능성 사이의 연관성을 보여준다.

논리적 결과 관계가 결정 가능한 완전한 1차 논리보다 약한 시스템이 있습니다.여기에는 명제 논리 및 단항 술어 기호로 제한되고 함수 기호가 없는 1차 논리인 단항 술어 논리가 포함됩니다.결정 가능한 함수 기호가 없는 다른 로직은 2변수 로직뿐만 아니라 1차 로직의 보호 대상 단편입니다.1차 공식의 Bernays-Sönfinkel 클래스도 결정할 수 있다.1차 로직의 결정 가능한 하위 집합도 기술 로직의 프레임워크에서 연구된다.

뢰벤하임-스콜렘 정리

뢰벤하임-스콜렘 정리는 만약 1차 카디널리티 이론이 무한 모델을 가지고 있다면, 그것은 θ보다 크거나 같은 모든 무한 카디널리티의 모델을 가지고 있다는 것을 보여준다.모델 이론의 초기 결과 중 하나로, 이는 계수 가능 서명이 있는 1차 언어로 계수 가능 또는 계수 불가능을 특징짓는 것이 불가능하다는 것을 암시합니다.즉, 임의의 구조 M이 θ를 만족하는 1차 공식 θ(x)는 M의 담화 영역이 셀 수 있는 경우(또는 두 번째 경우에는 셀 수 없는 경우)에만 존재한다.

뢰벤하임-스콜렘 정리는 무한 구조가 1차 논리에서는 범주적으로 공리화될 수 없다는 것을 암시한다.예를 들어, 유일한 모델이 실선인 1차 이론은 없습니다. 무한 모델을 가진 모든 1차 이론은 연속체보다 큰 카디널리티 모델을 가지고 있습니다.실선이 무한하기 때문에 실선이 만족하는 이론은 일부 비표준 모델에서도 만족합니다.뢰벤하임-스콜렘 정리가 1차 집합론에 적용될 때, 비직관적인 결과는 스콜렘의 역설로 알려져 있다.

콤팩트성 정리

압축성 정리는 1차 문장의 집합이 모든 유한 부분 집합이 모형을 ^[25]가지고 있는 경우에만 모형을 가지고 있다고 말한다.이것은 만약 공식이 1차 공리의 무한한 집합의 논리적 결과라면, 그것은 그러한 공리의 몇 가지 유한한 수의 논리적 결과라는 것을 암시한다.이 정리는 완전성 정리의 결과로 Kurt Gödel에 의해 처음 증명되었지만, 많은 추가적인 증명들이 시간이 지남에 따라 얻어졌습니다.모델 이론의 중심 도구이며, 모델을 구성하기 위한 기본 방법을 제공합니다.

콤팩트성 정리는 1차 구조의 집합이 초급인 것에 대한 제한 효과를 가지고 있다.예를 들어, 압축성 정리는 임의로 큰 유한 모델을 갖는 모든 이론이 무한 모델을 갖는다는 것을 암시한다.따라서 모든 유한 그래프의 클래스는 기본 클래스가 아니다(다른 많은 대수 구조에서도 동일).

또한 콤팩트성 정리에 의해 암시되는 1차 논리에는 더 미묘한 한계가 있다.예를 들어 컴퓨터 과학에서는 많은 상황을 상태(노드)와 연결(방향 에지)의 방향 그래프로 모델링할 수 있습니다.이러한 시스템을 검증하려면 "정상" 상태에서 "불량" 상태에 도달할 수 없음을 보여줘야 할 수 있습니다.따라서 좋은 상태와 나쁜 상태가 그래프의 서로 다른 연결된 구성요소에 있는지 여부를 확인하려고 합니다.단, 콤팩트성 정리는 연결된 그래프가 1차 로직의 기본 클래스가 아님을 보여주기 위해 사용할 수 있으며, 그래프의 로직에는 x에서 y까지의 경로가 있다는 생각을 나타내는 1차 로직의 공식 θ(x,y)가 존재하지 않는다.단, 연결성은 2차 로직으로 표현할 수 있지만 ${\displaystyle {\mathrm{}}_{}^{}}$ 1$$\ $displaystyle$\$Sigma$ _ ${1}^{$1}$1$ enjoys enjoys compact compact compact compact compact compact compact compact compact compact compact compact connected connected connected connected connected connected connected connected connected connected connected connected connected connected connected connected connected connected quant1 \ sigma _ { 1 }^1} 1 enjoys enjoys enjoys enjoys enjoys enjoys enjoys enjoys enjoys

린드스트롬의 정리

린드스트롬에 따르면, 방금 논의된 금속학적 성질은 어떤 강력한 논리도 그러한 성질을 가질 수 없다는 의미에서 실제로 1차 논리를 특징짓는다는 것을 보여주었다(Ebbinghouse와 Flum 1994, 13장).린드스트롬은 추상 논리 시스템의 클래스와 이 클래스 구성원의 상대적 강도의 엄격한 정의를 정의했다.그는 이런 유형의 시스템에 대해 두 가지 정리를 확립했다.

• 1차 논리를 포함하고 뢰벤하임-스콜렘 정리와 콤팩트성 정리를 모두 만족시키는 린드스트롬의 정의를 만족시키는 논리 시스템은 1차 논리와 동등해야 한다.
• 뢰벤하임-스콜렘 정리를 만족시키는 린드스트롬의 정의를 만족시키는 논리체계는 1차 논리와 동등해야 한다.

제한 사항

비록 1차 논리가 수학의 많은 부분을 공식화하는데 충분하고 컴퓨터 공학이나 다른 분야에서 일반적으로 사용되고 있지만, 그것은 특정한 한계를 가지고 있다.여기에는 표현력에 대한 제한과 그것이 묘사할 수 있는 자연 언어의 조각에 대한 제한이 포함됩니다.

예를 들어 1차 로직은 결정할 수 없습니다.즉, 타당성을 위한 건전하고 완전하며 종료적인 결정 알고리즘은 불가능합니다.이를 통해 C: 변수 2개와 카운트 수량자${\displaystyle {\mathrm{}}^n}$n \ $displaystyle$\ $exists$^ { \ $geq$n$$} 및${\$ ${\displaystyle n^{}}$ \ $displaystyle$\ $exists$^ { \ $leq$ n$\}$^[26] 등의 흥미로운₂ 결정 가능한 fragment가 연구되었습니다.

표현력

뢰벤하임-스콜렘 정리는 만약 1차 이론이 무한 모델을 가지고 있다면, 모든 카디널리티의 무한 모델을 가지고 있다는 것을 보여준다.특히, 무한 모델을 가진 어떤 1차 이론도 범주화할 수 없습니다.따라서, 유일한 모델이 자연수의 집합을 도메인으로 가지고 있거나, 유일한 모델이 실수의 집합을 도메인으로 가지고 있는 1차 이론은 없습니다.무한 논리학과 고차 논리학을 포함한 많은 1차 논리학의 확장은 자연수나 실수의 범주적 공리화를 허용한다는 점에서 더 표현적이다.그러나 이러한 표현성은 금속학적 비용이 든다: 린드스트롬의 정리에 따르면, 콤팩트성 정리와 하향 뢰벤하임-스콜렘 정리는 1차보다 더 강한 논리를 가질 수 없다.

자연어 공식화

1차 논리는 "퍼스에 사는 모든 사람은 호주에 산다"와 같은 많은 간단한 수량화 구조를 자연어로 공식화할 수 있다.따라서 1차 논리는 FO(.)와 같은 지식 표현 언어의 기초로서 사용됩니다.

그러나 자연어에는 1차 논리로 표현할 수 없는 복잡한 특징이 있다.자연어 해석의 수단으로 적합한 논리체계는 1차 술어 논리보다 훨씬 풍부한 구조를 필요로 한다.^[27]

제약사항, 확장사항 및 변경사항

1차 논리에는 많은 변형이 있다.이들 중 일부는 의미론에 영향을 주지 않고 단순히 표기법을 바꾼다는 점에서 중요하지 않다.다른 사람들은 추가 수량자나 다른 새로운 논리 기호를 통해 의미론을 확장함으로써 표현력을 더 크게 변화시킨다.예를 들어, 무한 로직은 무한 크기의 공식을 허용하고, 모달 로직은 가능성과 필요성을 나타내는 기호를 추가합니다.

제한된 언어

1차 논리는 위에서 설명한 것보다 적은 수의 논리 기호를 가진 언어로 연구할 수 있습니다.

• $"{\displaystyle \mathrm{}}$${\displaystyle x}$${\displaystyle }$" (${\displaystyle x}$ )$${ $displaystyle$\$exists$x${\displaystyle }$\ $varphi ($${\displaystyle x}$) { $displaystyle \ neg$ \ $forall x$ \ $neg$ \$varphi$ ($$x )$$$\}{\displaystyle \mathrm{}}$ 및$$${\displaystyle \mathrm{}}$" ${\displaystyle x}$ "${\displaystyle }$(${\displaystyle }$x$$) { $displaystyle$\ $forall$ x \ $varphi$( x )$$}${\displaystyle \mathrm{x<img\; alt="\{\backslash displaystyle\; \backslash forall\; x\backslash varphi\; (x)\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/d380eff12756f9c8d31e4b40e2a276cec16a0783"\; style="vertical-align:\; -0.838ex;\; width:7.281ex;\; height:2.843ex;">}}$ ${\displaystyle \mathrm{because}}$ x x because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because because$displaystyle \displaystyle$ \forall $}$ 및$$ $"\displaystyle \forall"$을 드롭할 수 있습니다.
• $displaystyle \varphi \lor \psi }$는${\displaystyle \mathrm{since}(}$ $lnot$ \$varphi \land$\lpsi$),$${\displaystyle \phi }$( \$displaystyle \varphi \land$ \lpsi )로$$ 표현할 수 있기 때문에${\displaystyle }$since${\displaystyle }$（ \ displaystyle \ varphi \land \$land$$$\psi \${\displaystyle \mathrm{land}}$ \psi ${\displaystyle \mathrm{）}}$로 표현할 수 있습니다${\displaystyle \mathrm{.}}$$§$ {\$displaystyle$\display$}$은(는$$) 드롭할 수 $있습니다$즉, 논리접속으로서 $「\displaystyle\neg」$와$「\displaystyle\vee$또는 $「\displaystyle\neg」$와$「\displaystyle\wedge$를 사용하는 것으로 충분합니다.
• 마찬가지로 논리 연결로 ${\(\displaystyle\neg)$ 및$$ $→(\displaystyle\right$ 화살표$)$만 사용하거나 셰퍼 스트로크(NAND) 또는 피어스 화살표(NOR) 연산자만 있으면 됩니다.
• 함수 기호와 상수 기호를 완전히 피하고 술어 기호를 통해 적절한 방법으로 다시 작성할 수 있습니다.예를 들어, ${\displaystyle 상수\mathrm{}}$ 기호$$0(\$displaystyle$\;0$$$)$ 대신 ${\displaystyle 술어\mathrm{}}$0$x )($$x$ ${\displaystyle =}$$$(\$displaystyle$$\;$$x=$${\displaystyle 0}$$)$을 사용하고${\displaystyle ,}$ ${\displaystyle \mathrm{P}}$(${\displaystyle 0,}$ y$)$와 같은 모든 술어${\displaystyle \mathrm{}}$0(\$displaystyle \;P(0,$${\displaystyle y}$$)$을 "${\displaystyle x"}$로 바꿀 수 있습니다.$x\;(0(x)\rightarrow$ P$(x,y$f${\displaystyle }$( ${\displaystyle {}_{}{}_{}{1\mathrm{}}_{}}$, ${\displaystyle {x\mathrm{}}_{}}$2,${\displaystyle .,}$ ${\displaystyle x_{}}$n $){style$ f$(x_{1}, x_{2},$ ${$$n})$ $등$의 함수는 마찬가지로 술어${\displaystyle }$F($x$1, ${\displaystyle {x\mathrm{}}_{}}$2,$.,$ ${\displaystyle {}_{}}${$n$로 대체됩니다$.$$\displaystyle$ y$=f(x_{1},x_{2},...x_{n$이 변경은 사용된 술어 기호의 해석이 ^[28]올바른 의미를 가지도록 가까운 이론에 추가적인 공리를 추가하는 것을 필요로 한다.

이러한 제한은 연역적 시스템에서 추론 규칙이나 공리 스키마의 수를 줄이는 기술로 유용하며, 이는 금속학적 결과의 더 짧은 증명으로 이어진다.제약의 대가는 자연어 문장에 사용되는 논리적 연결은 제한된 논리 연결 집합의 관점에서 그 (긴) 정의로 대체되어야 하기 때문에 수중의 공식 시스템에서 자연어 문구를 표현하는 것이 더 어려워진다는 것이다.마찬가지로, 제한된 시스템의 파생상품은 추가 연결을 포함하는 시스템의 파생상품보다 더 길 수 있다.따라서 공식 시스템 내에서 작업하는 용이성과 공식 시스템에 대한 결과를 입증하는 용이성 사이에는 트레이드오프가 있습니다.

또한 충분히 표현적인 이론에서 함수 기호와 술어 기호의 특성을 제한할 수 있다.쌍함수를 포함하는 이론에서 원칙적으로 2보다 큰 아리티의 함수와 1보다 큰 아리티의 술어를 완전히 배제할 수 있다.이는 도메인의 요소 쌍을 가져다가 이를 포함하는 순서 쌍을 반환하는 arity 2의 함수입니다.또한 순서 쌍에서 구성요소로 투영 함수를 정의하는 arity 2의 두 개의 술어 기호를 가지면 충분하다.어느 경우든 쌍체 함수와 그 투영에 대한 자연 공리가 충족되어야 한다.

다분류논리

일반적인 1차 해석은 모든 수량화 범위가 있는 단일 담화 영역을 가지고 있다.다량 정렬된 1차 로직에서는 변수가 서로 다른 소트(도메인)를 가질 수 있습니다.이를 유형 1차 논리, 유형(데이터 유형에서와 같이)이라고 부르기도 하지만 1차 유형 이론과 동일하지는 않습니다.다량 정렬된 1차 논리는 2차 ^[29]산술 연구에 종종 사용됩니다.

이론이 완전히 많은 종류만 있을 때, 다량 정렬된 1차 논리는 단일 정렬된 1차 ^{[30]: 296–299} 논리로 축소될 수 있다.단일 정렬 이론에 다분열 이론의 각 종류별 단일 술어 기호를 도입하고, 이러한 단일 술어가 담론의 영역을 분할한다는 공리를 추가한다.예를 들어, 2개의 정렬이 있는 경우 술어 $기호{\displaystyle {}_{}}$ ${\displaystyle \mathrm{P1}}$ (${\displaystyle {}_{}}$x$$ $displaystyle$ P_${1$} ($x)}$$및$ ${\displaystyle {P2\mathrm{}}_{}}$($){displaystyle P_{2$} ($x)}$와 공리를 추가합니다.

${\displaystyle \S }$ ${\displaystyle {}_{}}$ ( ${\displaystyle {}_{}{}_{}1}$ (${\displaystyle }$x${\displaystyle }$) ) P${\displaystyle {}_{}{2\mathrm{}}_{}}$ (${\displaystyle x}$ ${\displaystyle \mathrm{)\wedge }}$ (${\displaystyle \mathrm{}}$x (${\displaystyle {}_{}}$1${\displaystyle }$( ${\displaystyle x}$)∧${\displaystyle {}_{}{P\mathrm{}}_{}}$ ${\displaystyle 2}$(${\displaystyle }$x$)\ style$ \$forall x$ ($P$_ {$1$（$$x )\lor$P _ {$2$}$ ( x$)\land$ \$lnot$ \$exists x$ ( P _ {$1$ ($x$ )\$land$ { 2 } ( x )

다음으로 $({$1$$})을 만족하는 요소를 제1종 ${\displaystyle {요소}_{}}$로$,$ $P2$({$style P_{$2$$})를 만족하는 요소를 제2종 요소로 간주한다.대응하는 술어 기호를 사용하여 정량 범위를 제한함으로써 각 종류에 걸쳐 정량화할 수 있다.예를 들어, 공식 θ(x)를 만족시키는 첫 번째 종류의 원소가 있다고 하면 다음과 같이 쓸 수 있다.

${\displaystyle {}_{}}$ (${\displaystyle {}_{}{P\mathrm{}}_{}}$ ${\displaystyle 1}$( x )${\displaystyle \wedge }$ ${\displaystyle x}$ ($x$) {$displaystyle$ \ $exists x$ ( $P _$ {$1$ ( x ) \ $land$ \$varphi$ ($$x$$) }${\displaystyle \mathrm{}。}$

추가 수량자

1차 로직에 수량자를 추가할 수 있습니다.

• 때로는 "P(x)가 정확히 1개의 x를 유지한다"고 말하는 것이 유용할 수 있습니다. 이는 "!x P(x)"로 표현될 수 있습니다.고유성 정량이라고 불리는 이 표기법은 δx (P(x) ∧y (P(y) → (x = y))와 같은 공식의 약자로 사용될 수 있다.
• 추가 수량자를 갖는 1차 로직은 "x가 많다" 등의 의미를 갖는 새로운 수량자 Qx,…를 가진다.또한 분기 수량자 및 조지 부로스 등의 복수 수량자 등도 참조한다.
• 유계량자는 집합론이나 산술 연구에 종종 사용된다.

무한 논리학

무한정 긴 문장은 무한히 논리적으로 가능하다.예를 들어 무한히 많은 공식의 결합 또는 분리를 허용하거나 무한히 많은 변수에 대한 정량화를 허용할 수 있습니다.무한히 긴 문장은 위상 이론과 모델 이론을 포함한 수학 영역에서 발생합니다.

무한정 논리학은 1차 논리를 일반화하여 무한 길이의 공식을 허용한다.공식이 무한이 될 수 있는 가장 일반적인 방법은 무한 결합과 분리를 통해서입니다.단, 함수와 관계 기호가 무한한 특성을 가질 수 있는 일반화된 시그니처 또는 수량자가 무한히 많은 변수를 바인딩할 수 있는 시그니처를 허용할 수도 있습니다.무한 공식은 유한 문자열로 나타낼 수 없기 때문에 다른 공식 표현을 선택해야 합니다. 이 컨텍스트에서 일반적인 표현은 트리입니다.따라서 기본적으로 수식은 구문 분석되는 문자열이 아니라 구문 분석 트리로 식별됩니다.

가장 일반적으로 연구되는 무한 로직은 L로 표시되며_αβ, 여기서 α와 β는 각각 기수 또는 기호 θ이다.이 표기법에서는 통상적인 1차 로직은 L입니다_ωω.논리_∞ω L에서는 수식을 작성할 때 임의의 접속 또는 분사가 허용되며 변수의 공급은 무제한이다.보다 일반적으로 θ 미만의 성분과의 결합 또는 분리를 허용하는 논리를 L이라고_κω 합니다.예를 들어 L은 카운트_ω1ω 가능한 접속과 접속을 허용합니다.

L 공식의_κω 자유 변수 집합은 θ보다 엄밀하게 작은 임의의 카디널리티를 가질 수 있지만, 공식이 ^[31]다른 공식의 보조 공식으로 나타날 때 그 중 많은 변수만 양자의 범위에 포함될 수 있다.다른 무한 논리학에서 보조 공식은 무한히 많은 수량화자의 범위에 있을 수 있다.예를 들어 L에서는_κ∞ 하나의 보편적 또는 실존적 정량자가 임의의 다수의 변수를 동시에 결합할 수 있다.마찬가지로_κλ 논리 L은 θ 미만의 변수에 대한 동시 정량화와 θ 미만의 크기의 결합 및 분리를 허용합니다.

비클래식 및 모달 로직

• 직관론적 1차 논리는 고전적 명제 미적분보다는 직관적 명제를 사용한다. 예를 들어, ¬는 φ과 동등할 필요가 없다.
• 1차 모달 논리는 우리가 살고 있는 이 우연한 진실된 세계뿐만 아니라 다른 가능한 세계를 묘사할 수 있게 해준다.어떤 버전에서는, 가능한 세계의 집합은 어떤 가능한 세계에 사느냐에 따라 달라집니다.모달 로직에는 비공식적으로 특징지을 수 있는 의미를 가진 추가 모달 연산자가 있습니다. 예를 들어, "needs that true"(모든 가능한 세계에서는 참) 및 "nays that that world"(일부 가능한 세계에서는 참)입니다.표준 1차 로직에서는 단일 도메인이 있으며 각 술어에는 하나의 확장자가 할당됩니다.1차 모달 로직에서는 각 가능한 세계에 자신의 도메인을 할당하는 도메인 함수를 가지고 있습니다.그러면 각 술어는 이러한 가능한 세계에 대해서만 상대적인 확장을 얻을 수 있습니다.이를 통해 알렉스는 철학자이지만 수학자일 수도 있고 전혀 존재하지 않았을 수도 있는 사례를 모형화할 수 있습니다.제1의 가능한 세계 P(a)는 참이고, 제2의 세계 P(a)는 거짓이며, 제3의 가능한 세계에는 도메인 내에 a가 전혀 없다.
• 1차 퍼지 로직은 고전 명제 미적분이 아닌 명제 퍼지 로직의 1차 확장이다.

고정점 논리

고정점 논리는 양의 최소 ^[32]고정점 아래에 닫힘을 추가하여 1차 논리를 확장합니다.

고차 로직

1차 논리의 특징은 개인을 수량화할 수 있지만 술어는 수량화할 수 없다는 것입니다.따라서

$\displaystyle\text\displaystyle\text{Phil}}(a)}$

법적 1차 공식이지만

$\디스플레이 스타일\text\displaystyle\text{Phil}}({\text{\text})Phil}}(a)}$

대부분의 1차 로직 공식화에서는 그렇지 않습니다.2차 로직은 1차 로직을 확장하기 위해 후자의 양자화 유형을 추가합니다.그 외의 고차 로직에서는, 2차 로직이 허가하는 것보다 더 높은 타입으로 정량화할 수 있습니다.이러한 상위 유형에는 관계 간의 관계, 관계에서 관계 간의 함수 및 기타 상위 유형 객체가 포함됩니다.따라서 1차 논리의 "first"는 수량화할 수 있는 객체의 유형을 나타냅니다.

하나의 의미론만 연구되는 1차 논리와는 달리, 2차 논리에는 몇 가지 가능한 의미론이 있습니다.2차 및 고차 로직에서 가장 일반적으로 사용되는 시멘틱스는 완전 시멘틱스라고 알려져 있습니다.추가 수량화자와 이러한 수량화자의 전체 의미론의 조합은 1차 논리보다 고차 로직을 더 강하게 만듭니다.특히, 2차 이상의 고차 논리에 대한 (의미적) 논리적 결과 관계는 반신반의할 수 없다; 완전한 의미론 하에서 건전하고 완전한 2차 논리에 대한 효과적인 추론 시스템은 없다.

완전한 의미론을 가진 2차 논리가 1차 논리보다 더 표현적이다.예를 들어 자연수와 실선을 고유하게 특징짓는 2차 논리로 공리계를 작성할 수 있다.이 표현식의 대가는 2차 논리 및 고차 논리학이 1차 논리보다 덜 매력적인 금속학적 특성을 가지고 있다는 것입니다.예를 들어, 1차 로직의 뢰벤하임-스콜렘 정리 및 콤팩트성 정리는 완전한 의미론을 가진 고차 로직으로 일반화되면 거짓이 된다.

자동화된 정리 증명 및 형식적 방법

자동정리증명이란 수학정리의 ^[33]파생(형식증명)을 검색하고 찾아내는 컴퓨터 프로그램을 개발하는 것을 말한다.탐색 공간이 매우 넓을 수 있기 때문에 미분을 찾는 것은 어려운 작업입니다; 가능한 모든 미분에 대한 철저한 탐색은 이론적으로 가능하지만 수학에 관심이 있는 많은 시스템에서는 계산적으로 불가능합니다.따라서 복잡한 경험적 함수는 블라인드 ^{[citation needed]}검색보다 더 짧은 시간에 파생된 함수를 찾기 위해 개발됩니다.

자동증명 검증의 관련 분야에서는 컴퓨터 프로그램을 사용하여 인간이 만든 증명이 맞는지 확인합니다.복잡한 자동 정리 프로버와 달리 검증 시스템은 손으로 또는 자동화된 소프트웨어 검증을 통해 정확성을 확인할 수 있을 정도로 작을 수 있습니다.이 증명 검증자의 검증은 "올바른" 라벨로 표시된 파생이 실제로 옳다는 확신을 주기 위해 필요합니다.

메타매스와 같은 일부 증명 검증자는 입력으로 완전한 파생을 주장합니다.Mizar 및 Isabelle과 같은 다른 기업들은 제대로 포맷된 증명 스케치(아직 매우 길고 상세할 수 있음)를 사용하여 간단한 증명 검색을 수행하거나 알려진 결정 절차를 적용하여 누락된 부분을 채웁니다. 그 결과 도출된 내용은 작은 핵심 "커널"에 의해 검증됩니다.그러한 많은 시스템은 주로 인간 수학자들에 의해 쌍방향으로 사용되도록 고안되었습니다: 이들은 증명 보조자로 알려져 있다.또한 유형 이론과 같이 1차 논리보다 강력한 형식 논리학을 사용할 수도 있습니다.1차 연역 체계에서 중요하지 않은 결과의 완전한 파생은 인간이 ^[34]쓰기에 매우 길기 때문에, 결과는 종종 파생이 별도로 구성될 수 있는 일련의 보조 개념으로 공식화된다.

자동화된 정리 프로버는 컴퓨터 과학에서 공식적인 검증을 구현하기 위해서도 사용됩니다.이 설정에서는 프로그램 및 프로세서 등의 하드웨어가 정식 사양에 대해 정확한지 확인하기 위해 정리 프로버가 사용됩니다.이러한 분석은 시간이 많이 걸리고 비용이 많이 들기 때문에 일반적으로 오작동이 심각한 인적 또는 재정적 결과를 초래할 수 있는 프로젝트에 사용됩니다.

모델 체크의 문제에 대해서는 입력 유한 구조가 계산 복잡도 한계와 더불어 1차 공식을 충족하는지 여부를 결정하는 효율적인 알고리즘이 알려져 있습니다. 모델 체크 first 1차 로직을 참조하십시오.

「 」를 참조해 주세요.

메모들