분석표기법

증명 이론에서 의미론적 tableau(/tæbloʊ, ˈtæbloʊ/; 복수형: tableau, truth tree라고도 함)는 송신 및 관련 로직의 결정 절차, 1차 논리 공식의 증명 절차다.분석 테이블라우는 논리 공식에 대해 계산된 트리 구조로, 각 노드에서 증명되거나 반박될 원래 공식의 보조 양식을 갖는다.계산은 이 나무를 구성하고 그것을 사용하여 전체 공식을 증명하거나 반박한다.또한 Tableau 방법은 다양한 로직의 유한한 공식 집합의 만족도를 결정할 수 있다.모달 로직(Girle 2000)에 가장 많이 사용되는 교정 절차다.null

소개

보충표에서 목적은 공식의 부정이 충족될 수 없다는 것을 보여주는 것이다.메인 커넥티브부터 시작하여 일반적인 커넥티브를 각각 취급하는 규칙이 있다.많은 경우에 이러한 규칙을 적용하면 하위 테이블라우가 둘로 나뉘게 된다.정량자는 인스턴스화된다.탁자의 어느 가지라도 명백한 모순으로 이어지면 나뭇가지가 닫힌다.모든 가지가 닫히면 증거가 완성되고 원래의 공식은 논리적인 진리인 것이다.null

분석 tableau 방법의 이면에 있는 근본 사상은 구조적인 증명 이론의 컷 엘리미네이션 정리에서 도출되지만, 증명 이론과의 연계가 근래에야 이루어졌기 때문에 tableau calculi의 기원은 논리 결합체의 의미(또는 의미론)에 있다.null

좀 더 구체적으로 말하면, 테이블라우 미적분학은 하나의 논리 결합체를 그것의 구성 부분으로 분해하는 방법을 명시하는 각 규칙과 함께 한정된 규칙 모음으로 구성된다.규칙은 일반적으로 한정된 공식 집합의 용어로 표현되지만, 다중 집합, 목록 또는 심지어 공식의 나무와 같이 더 복잡한 데이터 구조를 사용해야 하는 로직도 있다.따라서 "set"은 {set, multiset, list, tree} 중 하나를 의미한다.null

만약 모든 논리 결합자에 대해 그러한 규칙이 있다면, 그 절차는 결국 원자 공식과 그들의 부정으로만 구성된 세트를 생산하게 될 것이며, 이것은 더 이상 분해될 수 없다.그러한 집합은 문제의 논리의 의미론에 관해서 만족하거나 만족하지 못하는 것으로 쉽게 인식된다.이 과정을 추적하기 위해 탁자의 노드 자체를 나무 형태로 설정하고 이 나무의 가지를 만들어 체계적으로 평가한다.이 트리를 탐색하는 이러한 체계적인 방법은 추론과 자동 추론을 수행하는 알고리즘을 만들어낸다.노드에 세트, 멀티셋, 목록 또는 트리가 포함되는지 여부에 관계없이 이 큰 트리가 존재한다는 점에 유의하십시오.null

명제 논리학

이 절에서는 고전 명제 논리의 표고 미적분을 제시한다.탁자는 주어진 공식 세트가 만족스러운지 아닌지 점검한다.It can be used to check either validity or entailment: a formula is valid if its negation is unsatisfiable and formulae ${\displaystyle A_{1},\ldots ,A_{n}}$ imply ${\displaystyle B}$ if ${\displaystyle \{A_{1},\ldots ,A_{n},\neg B\}}$ is unsatisfiable.null

명제 테이블보의 주요 원리는 보완적인 리터럴 쌍이 생산되거나 더 이상의 확장이 불가능할 때까지 복잡한 공식들을 더 작은 공식으로 "분쇄"하려는 것이다.null

이 방법은 노드에 공식이 표시된 트리에서 작동한다.각 단계에서, 이 트리는 수정된다; 제안적인 경우, 오직 허용되는 변경은 나뭇잎의 후손으로 노드를 추가하는 것이다.세트에 모든 공식의 체인으로 만들어진 나무를 생성하여 만족스럽지 못함을 증명하는 것으로부터 절차가 시작된다.이 시작 단계의 변형은 루트가$\$ {\$displaystyle$\top $}$로 레이블이 지정된 단일 노드 트리로 시작하는 것이다$.$ 이 두 번째 경우 절차는 항상 잎 아래 세트의 공식을 복사할 수 있다.실행 예로서$,{\displaystyle }$ 세트 { (${\displaystyle \vee }$ ${\displaystyle \mathrm{\neg }}$ ${\displaystyle b}$) ${\displaystyle \wedge }$ b ,${\displaystyle \mathrm{\neg }}$ ${\displaystyle a}$} ${\displaystyle \{(a\vee \neg$ b$)\wedge$ b$,\neg$ a$\}$에 대한 테이블au가 표시된다$$.null

tableau의 원리는 같은 가지 노드의 공식을 함께 고려하는 반면 다른 가지들은 분리하는 것으로 간주하는 것이다.그 결과, tableau는 접속사들을 분리하는 공식을 나무처럼 표현한 것이다.이 공식은 불만족함을 증명하기 위한 세트와 동등하다.이 절차는 결과 테이블라우로 대표되는 공식이 원래 공식과 동등하도록 테이블라우를 수정한다.이러한 접속사 중 하나는 한 쌍의 보완 리터럴을 포함할 수 있으며, 이 경우 해당 접속사가 만족스럽지 못한 것으로 입증된다.모든 접속사가 만족스럽지 못한 것으로 판명되면, 원래의 공식 집합은 만족스럽지 못하다.null

그리고

탁자의 가지에 두 공식을 결합한 공식$$ $A{\displaystyle }$ ${\displaystyle \wedge }$ ${\displaystyle B}$ ${\displaystyle A\wedge$ B$}$이(가) 포함되어 있을 때마다 이 두 공식이 모두 그 공식의 결과물이다.이 사실은 테이블라우 확장에 대한 다음 규칙에 의해 공식화될 수 있다.

( ${\displaystyle }${\$displaystyle$\$wedge$ $}$) Tableau의 가지에 ${\displaystyle A}$ ${\displaystyle \wedge }$ B ${\displaystyle A$$}$과($와)$$B{\displaystyle }$ {\$displaystyle B}$라는 결막 공식이 포함된 두 개의 노드의 체인을 리프에 추가하십시오$.$

이 규칙은 일반적으로 다음과 같이 쓰여 있다.

${\displaystyle (\land ){\frac {A\wedge B}{\begin{array}{c}}A\\B\end{array}}}$

이 규칙의 변형은 노드가 단일 공식이 아닌 일련의 공식을 포함하도록 허용한다.In this case, the formulae in this set are considered in conjunction, so one can add ${\displaystyle \{A,B\}}$ at the end of a branch containing ${\displaystyle A\wedge B}$. More precisely, if a node on a branch is labeled ${\displaystyle X\cup \{A\wedge B\}}$, one can add to the branch the new leaf${\displaystyle X}$ ${\displaystyle \cup }${ ${\displaystyle A}$ ,${\displaystyle B}$ ${\displaystyle \}}$ ${\displaystyle$ X$\cup \{A,B$

아니면

테이블라우의 가지에 $A{\displaystyle }$ ${\displaystyle \vee }$ ${\displaystyle B}$ ${\displaystyle A\vee$ B$}$와 같이 두 공식을 분리하는 공식이 포함된 경우, 다음 규칙을 적용할 수 있다$.$

$({\displaystyle \ve }$) 분기의 노드에 이항 공식 ${\displaystyle A}$∨ B ${\displaystyle A\ve B}$이(가) 포함되어 있는 경우, 분기의 잎에 각각 $공식{\displaystyle }$ A$${\$displaystyle A}$와 B ${\displaystytyle$ B$}$를 포함하는 두 형제 자식을 생성하십시오$.$null

이 규칙은 분기를 둘로 분할하여 최종 노드에 대해서만 다르다.가지들은 서로 분리되어 고려되기 때문에, 비공통 노드의 분리가 $정확히{\displaystyle }$ A ${\displaystyle \vee }$ ${\displaystyle B}$ ${\displaystyle A\vee B}$이기 때문에, 두 가지 결과 가지는 원래의 분기와 동등하다$.$분리 규칙은 일반적으로 생성될 두 개의 고유 노드의 공식을 분리하기 위해$$ $displaystyle }$ 기호를 사용하여 공식적으로 작성된다.

${\displaystyle (\ve){\frac {A\ve B}{A\mid B}}}$

If nodes are assumed to contain sets of formulae, this rule is replaced by: if a node is labeled ${\displaystyle Y\cup \{A\vee B\}}$, a leaf of the branch this node is in can be appended two sibling child nodes labeled ${\displaystyle Y\cup \{A\}}$ and ${\displaystyle Y\cup \{B\}}$, respectively.null

아니다

tableaux의 목적은 반대편 리터럴 쌍이 생성되거나 다른 규칙이 적용될 수 없을 때까지 점진적으로 간단한 공식을 생성하는 것이다.부정은 처음에 부정의 정상적인 형태로 공식을 만들어 치료할 수 있으므로 부정은 문자의 앞에서만 일어난다.Alternatively, one can use De Morgan's laws during the expansion of the tableau, so that for example ${\displaystyle \neg (A\wedge B)}$ is treated as ${\displaystyle \neg A\vee \neg B}$. Rules that introduce or remove a pair of negations (such as in ${\displaystyle \neg \neg A}$) are also used in this사례(그렇지 않으면,$$${\displaystyle \mathrm{like}}$ formula (A would${\displaystyle B}$) ${\displaystyle \neg \neg$ ($A\wedge B)}:$

${\displaystyle (\neg 1){\frac {A}{\neg \neg A}}$

${\displaystyle (\neg 2){\frac {\neg \neg A}{A}}$

폐쇄

모든 tableau는 공식을 그래픽으로 표현한 것으로 간주할 수 있으며, 이는 tableau가 구축된 공식은 테이블au가 구축된 세트와 동일하다.이 공식은 다음과 같다: Tableau의 각 가지들은 그 공식의 결합을 나타내고 Tableau는 그 가지들의 분리를 나타낸다.확장 규칙은 표고를 표현된 등가 공식을 가진 것으로 변환한다.tableau는 입력 세트의 공식을 포함하는 단일 분기로 초기화되기 때문에, 그것으로부터 얻은 모든 후속 tableau는 해당 집합과 동등한 공식을 나타낸다(초기 tableau가 true로 표시된 단일 노드인 변종에서 tableau는 원래 집합의 결과).null

tableaux의 방법은 초기 공식 집합에서 시작하여 모순이 반대 문자의 단순한 형태로 나타날 때까지 tableau에 더 간단하고 단순한 공식으로 추가함으로써 작용한다.탁자로 대표되는 공식은 가지로 대표되는 공식을 분리하는 것이기 때문에, 모든 가지에 한 쌍의 반대 문자가 들어 있을 때 모순을 얻는다.null

한 가지 가지가 문자 그대로의 부정과 그 부정을 포함하면, 그 상응하는 공식은 만족스럽지 못하다.이에 따라 이 지점은 더 확대할 필요가 없어 이제 '폐업'할 수 있게 됐다.탁자의 모든 가지가 닫히면 탁자로 대표되는 공식은 만족스럽지 못하므로, 원래 세트 역시 만족스럽지 못하다.모든 지점이 닫히는 테이블라우를 얻는 것은 원세트의 불만족을 증명하는 방법이다.명제의 경우, 모든 확장 규칙을 적용할 수 있는 모든 곳에 적용했다면, 닫힌 테이블라우를 찾는 것이 불가능하다는 것에 의해서 만족도가 증명된다는 것도 증명할 수 있다.특히 테이블라우에 열린(비닫힘) 분기가 일부 포함되어 있고, 리터럴이 아닌 모든 공식은 공식이 있는 모든 분기에 새로운 노드를 생성하기 위해 규칙에 의해 사용되어 온 경우, 세트는 만족스럽다.null

이 규칙은 공식이 둘 이상의 분기에서 발생할 수 있다는 점을 고려한다(적어도 노드 아래에 분기점이 있는 경우).이 경우 공식을 확장하는 규칙을 적용하여 아직 열려 있는 이 모든 분기에 그 결론을 추가해야 테이블라우를 더 확장할 수 없고 따라서 공식이 만족스럽다고 결론을 내릴 수 있다.null

세트 라벨 테이블라우

tableau의 변형은 단일 공식이 아닌 공식 세트로 노드에 라벨을 붙이는 것이다.이 경우 초기 tableau는 만족스러운 것으로 증명될 집합이 라벨로 표시된 단일 노드다.따라서 집합의 공식은 연계된 것으로 간주된다.null

tableau의 확장 규칙은 이제 모든 내부 노드를 무시하고 tableau의 잎에서 작동할 수 있다.결합의 경우 규칙은 A $conjunction{\displaystyle }$ B ${\displaystyle \{\backslash }$$displaystyle A}$과 B {\$displaystyle B}$을(를) 포함하는 집합과 그 대신$$ $A{\displaystyle }$$$ ${\$displaystyle A}과$$(와)를 포함하는 집합의 동등성에 기초한다.특히 잎에 $X{\displaystyle }$ ${\displaystyle \cup \{A}$ ${\displaystyle \wedge }$ ${\displaystyle B\}}$ ${\displaystyle X\cup \{A\$${\displaystyle \mathrm{wedge}}$ B$\}}}$ 라벨 $X{\displaystyle }$ ${\displaystyle \cup }${${\displaystyle A,}$ B$}{\displaystyle$ X$\cup \{A,B$이(가) 붙은 라벨이 붙은 경우 노드를 추가할 수 있다$.$

${\displaystyle (\wedge ){\frac {X\cup \{A\wedge B\}}{X\cup \{A,B\}}}}}$

For disjunction, a set ${\displaystyle X\cup \{A\vee B\}}$ is equivalent to the disjunction of the two sets ${\displaystyle X\cup \{A\}}$ and ${\displaystyle X\cup \{B\}}$. As a result, if the first set labels a leaf, two children can be appended to it, labeled with the latter two formulae.null

${\displaystyle (\ve ){\frac {X\cup \{A\ve B\}}{X\cup \{A\}X\cup \{B\}}}}}$

마지막으로, 집합에 리터럴과 부정이 모두 포함된 경우, 이 분기는 닫을 수 있다.

${\displaystyle (id){\frac {X\cup \{p,\neg p\}}{close}}}$

주어진 유한 집합 X에 대한 테이블라우는 부모에게 테이블라우 규칙을 적용하여 모든 하위 노드를 얻는 루트 X를 가진 유한(상향) 트리다.그러한 테이블라우의 분기는 해당 리프 노드가 "닫힘"을 포함하는 경우 닫힌다.모든 나뭇가지가 닫히면 탁자는 닫힌다.하나 이상의 분기가 닫히지 않으면 테이블라우가 열린다.null

다음은 세트 X = {r0 & ~r0, p0 & ((~p0 q q0) & ~q0)에 대한 두 개의 닫힌 표이며, 각 규칙 애플리케이션은 오른쪽에 표시된다(& 및 ~ ~는 각각 $\wedge {\displaystyle }$ ${\displaystyle \wedge }$ 및$$ $\neg {\displaystyle \mathrm{}}$ ${\displaystystyle \ne$ \ne$\}$을 나타냄).

{r0&~r0,p0&((~p0 vq0)&~q0)}{r0&~r0,p0&((~p0 vq0)&~q0)}----------------------------------(&)------------------------------------------------------------(&){r0, ~r0,p0&((~p0 vq0)&~q0)}{r0.&~r0, p0,((~p0 vq0)&~q0)}요.-------------------------------(이드)?--------------------------------------------------(&)을 마감했다{r0&~r0, p0,(~p0 vq0), ~q0}---------------------------------------------.-----------------------------------------------------------------------------------------------------------------------------------------------(v){r0&~r0, p0, ~p0, ~q0}{r0&~r0, p0, q0, ~q0}------------------------(이드)----------------------(이드) 닫기를 클릭합니다.d폐쇄적인

오른손은 표시를 놓치고 닫는 데 시간이 오래 걸리는 반면 왼손은 한 가지 규칙만 적용하면 닫힌다.분명히, 우리는 항상 가장 짧은 닫힌 테이블을 찾기를 원하지만, 공식의 모든 입력 세트에 대해 가장 짧은 닫힌 테이블을 찾는 하나의 알고리즘은 존재할 수 없다는 것을 보여줄 수 있다.null

위에 제시된$$ 세 가지 규칙$({\displaystyle }$ ${\displaystyle \wedge }$) ${\displaystyle$$(\wedge$ $)\},$ (${\displaystyle }$${\displaystyle \vee }$) {\$displaystyle$ ($)}$은(는) 부정된 정상 형태의 $공식$ X${\displaystyle {}^{}}${$${\$displaystyle X'}$이(가) 공동으로 만족하는지 여부를 결정하기에 충분하다.

$X{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$에 대한 닫힌 테이블au를 찾을 때까지$$ 또는 모든 가능성을 $소진$하고 X${\displaystyle {}^{}}${$${\$displaystyle$ X$'}$에 대한 테이블au가 모두 열려 있다는$$ 결론을 내릴 때까지 가능한 모든 순서에 가능한 모든 규칙을 적용하십시오.null

첫 번째 경우에는 $X{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ X$'}$이(가) 공동으로 만족하지 못하고$$, 두 번째 경우에는 열린 가지의 잎사귀 노드가 원자 공식과 부정 원자 공식에 할당을 주어 $\$ {\$displaystyle$X'}이(가$$) 공동으로 만족하도록 한다.고전적 논리는 실제로 하나의 테이블au만을 완전히 조사하면 되는 다소 좋은 속성을 가지고 있다: X ${\displaystyle {\prime }^{}}$ ${\$ X$'}$이(가) 닫히면 $X{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ {\displaystyle $X$$'}$이(가) 만족스럽지 못하며$$, $열려{\displaystyle {}^{}}$ 있으면 X $\$ {\$displaysty$ X'}이(가$$)그러나 이 속성은 일반적으로 다른 로직들에 의해 향유되지 않는다.null

이러한 규칙은 최초의 공식 X 집합을 취하여 각 멤버 C를 논리적으로 동등한 부정의 정상 형식 C로 대체함으로써 모든 고전적 논리에 충분하다. 우리는 X'가 만족스러운 경우에만 만족한다는 것을 알고 있다. 따라서 X'가 만족한다면 X'에 대한 폐쇄적인 테이블au를 검색하는 것으로 위에서 설명한 절차를 사용하여 X'를 찾는 것으로 충분하다.null

$X{\displaystyle }$=${\displaystyle }${ ${\displaystyle \mathrm{\neg }}$ ${\displaystyle A\}}$ ${\displaystyle X=\{\neg A\}$을(를) 설정함으로써 공식$$ A가 고전적 논리의 tautology인지 여부를 테스트할 수 있다.

$\{{\displaystyle }$ ${\displaystyle \mathrm{\neg }}$ ${\displaystyle A\}}$ ${\displaystyle \{\neg A\}$의 테이블au가 닫히면$$ $\neg {\displaystyle \mathrm{}}$ A ${\displaystyle \neg A}$은(는) 만족스럽지 못하므로$$ 진리 값을 할당해도 A가 거짓이 되지 않기 때문에 A는 자동학이다.그렇지 않으면 {${\displaystyle \mathrm{\neg }}$ ${\displaystyle A\}}$ ${\displaystyle \{\neg A\}$에 대한 열린 테이블au 분기의 모든 잎은 A를 위조하는 임무를 부여한다$$.null

조건부

고전적인 명제적 논리는 대개 물질적 함의를 나타내는 결합성을 가지고 있다.만약 우리가 이 결합체를 ⇒으로 쓴다면, A formula B라는 공식은 "만약 A가 B"를 의미한다.A ⇒ B를 구성 공식으로 분해하는 것은 탁상 규칙을 부여하는 것이 가능하다.마찬가지로 ¬(A ∧ B), ¬(A ∨ B), ¬(A ∨ B), ¬(A ⇒ B) 각각을 분해하는 것에 대해 각각 하나의 규칙을 줄 수 있다.이 규칙들은 함께 각각의 규칙이 그것의 구성 요소로 하나의 공식을 분해하지만 어떤 규칙도 작은 구성 요소로 더 큰 공식을 만들지 않기 때문에 고전적 논리에서 주어진 공식을 동시에 만족하는지를 결정하는 종료 절차를 제공할 것이다.따라서 우리는 결국 원자와 원자의 부정만을 포함하는 노드에 도달해야 한다.이 마지막 노드가 일치하면 분기를 닫을 수 있고 그렇지 않으면 열린 상태로 유지된다.null

그러나 다음과 같은 동등성은 고전적 논리학에서 (...) = (...)는 왼손 공식과 논리적으로 오른손 공식과 동등하다는 것을 의미한다.

$\displaystyle {\begin{array}{lcl}\ng(A\land B)&=\ng A\lor \ng(A\lor B)&\ng A\land \neg B\\\\ng(\ng A)&&&#&#&#&#&#&##############&###############################A\\\neg (A\Rightarrow B)&=&A\land \neg B\\A\Rightarrow B&=&\neg A\lor B\\\A\Leftrightarrow B&=&(A\land B)\lor(\neg A\land \neg B)\\neg(A\land \neg B)&=(A\land \land B)\lor(\neg A\land B)\end{array}}}}}}}$

고전적 논리의 임의 공식 C에서 시작하여 이러한 동등성을 반복적으로 적용하여 왼쪽을 C에서 오른쪽 측면으로 대체하면, 논리적으로 C와 동등하지만 C'가 함축하지 않는 속성을 가진 공식 C'를 얻게 되고, ¬은 원자 공식 앞에만 나타난다.그러한 공식은 부정 정상 형태라고 하며 고전적 논리의 모든 공식 C가 부정 정상 형태에서 논리적으로 동등한 공식 C'를 가지고 있다는 것을 공식적으로 증명할 수 있다.즉, C'가 만족스러우면 C도 만족한다.null

1차 로직 테이블라우

표고는 보편적 및 실존적 정량자를 각각 취급하는 두 가지 규칙에 의해 첫 번째 순서 술어 논리까지 확장된다.두 가지 다른 규칙 집합을 사용할 수 있다. 두 규칙 모두 실존적 정량자를 처리하기 위해 스콜레마이징 형식을 사용하지만 보편적 정량자의 처리에 대해서는 다르다.null

유효성을 확인하기 위한 공식 집합은 여기에 자유 변수를 포함하지 않는 것으로 되어 있다; 자유 변수는 암묵적으로 보편적으로 계량되므로 제한이 아니다. 따라서 이러한 변수에 대한 범용 정량자가 추가될 수 있으므로 자유 변수가 없는 공식이 된다.null

통일 없는 1차 테이블라우

1차 공식 $\forall {\displaystyle \mathrm{}}$ ${\displaystyle x}$ .${\displaystyle \gamma }$ (${\displaystyle x}$) ${\displaystyle \forall x.\$$gamma (x$$)}$은 t {\$displaystyle t}$이(가$)$ 기본 용어인 모든 공식 $($)을 의미한다$$.따라서 다음과 같은 추론 규칙이 정확하다.

${\displaystyle }$(${\displaystyle \mathrm{\forall }}$ ) ${\displaystyle \forall \frac{\mathrm{}}{}}$ x .${\displaystyle \frac{\gamma }{}}$( ${\displaystyle \frac{x}{}}$) ${\displaystyle \frac{}{}}$( ${\displaystyle \frac{t}{}}$) ${\$frac {\$forall x.\property (x)}{\displaysty$($t$$)}}}}}}$ $여기$서 t$${\$displaystyt}$은 임의의 접지 용어다.

제안적 연결 장치에 대한 규칙에 대해 정반대로, 동일한 공식에 이 규칙을 여러 번 적용해야 할 수 있다.예를 들어, ${\displaystyle \mathrm{세트}}{\displaystyle }${ ${\displaystyle \mathrm{\neg }}$ P${\displaystyle }$( ${\displaystyle a}$) ${\displaystyle \mathrm{\vee }}$ ${\displaystyle P}$( ${\displaystyle b}$)${\displaystyle }$, ${\displaystyle \mathrm{\forall }}$ ${\displaystyle x}$. P${\displaystyle }$( ${\displaystyle x)\}}$ ${\displaystyle \{\neg P($$a)\vee \neg P(b),\forall$x.$P{\displaystyle (}$$x)\}$은(는) ${\displaystyle P(a)}$ 및$$ $P{\displaystyle (b}$)$${\$displaystyle P(b)}$이(가)${\displaystyle \mathrm{}x}$x . ${\displaystyle P}$( ${\displaystyle x}$) ${\displaystyle \forall x$에서 생성된 경우에만 만족스럽지 않음을 증명할 수 있다$$$.$$P(x)}$.

실존적 정량자는 스콜레마이징(Skolemization)을 통해 처리된다.특히 $\exists {\displaystyle \mathrm{}}$ ${\displaystyle x}$ .${\displaystyle \Delta }$( ${\displaystyle x}$) ${\displaystyle \exists x.\delta (x)}$과 같은 선도적인 실존적 정량자를 가진 공식은 자신의 스콜레마이징 $\Delta {\displaystyle }$ $){\displaystyle \delta$ ($c)$를 생성하는데$,$ $여기$서 c ${\displaysty c}$은 새로운 상수 기호다.null

${\displaystyle }$(${\displaystyle \mathrm{\exists }}$ ) ${\displaystyle \exists \frac{\mathrm{}}{}}$ ${\displaystyle \frac{x}{}}$(${\displaystyle \frac{}{x}}$ ) Δ ${\displaystyle \frac{(}{}}$c ) ${\${\$fract x.\property (x)}{\displaysty$ c$}}}$ 여기서$$ $c{\displaystyle }$ ${\displaysty c}$은 새로운$$ 상수 기호다.

skolem 용어 $c{\displaystyle }$ ${\displaystyle c}$은(는) 상수(아리티 0의 함수)로, $x{\displaystyle }$ ${\displaystyle x}$에 대한 정량이 모든 범용 정량기의 범위 내에서 발생하지 않기$$ 때문이다.$원래{\displaystyle }$ 공식에 x ${\displaystyle x}$에 대한 정량화가 해당 범위 내에 있는$$ 것과 같은 일부 범용 정량자가 포함된 경우, 이러한 정량자는 범용 정량자에 대한 규칙의 적용에 의해 분명히 제거되었다.null

실존적 정량자에 대한 규칙은 새로운 상수 기호를 도입한다.${\displaystyle \mathrm{이러한}}$ 기호는 범용 ${\displaystyle \mathrm{정량자}}$에 규칙으로 사용할 수 있으므로 c ${\$$displaystyle \forall y.\gamma(y)}$이$($가) 원래 공식에 있지$$ 않지만 실존 $정량자$에 대한 규칙에 의해 생성된 스콜렘 상수인 ${\displaystyle \mathrm{경우}}$에도$\gamma {\displaystyle }$(c$$${\displaystyle )\{\backslash }$$displaystystyle$ $\gamma(c)$를 생성할 수 있다$$.null

보편적 및 실존적 정량자에 대한 위의 두 가지 규칙은 정확하며, 명제적 규칙도 그러하다: 공식의 집합이 폐쇄적 테이블라우를 생성한다면, 이 집합은 만족스럽지 못하다.완전성은 또한 증명될 수 있다: 만약 일련의 공식들이 만족스럽지 않다면, 이 규칙들에 의해 그것으로부터 만들어진 닫힌 테이블라우가 존재한다.그러나 실제로 그러한 폐쇄적인 탁자를 찾으려면 적절한 규칙 적용 정책이 필요하다.그렇지 않으면 만족스럽지 못한 세트는 무한히 성장하는 탁자를 만들어 낼 수 있다.예를 들어$,{\displaystyle }$ 세트 { ${\displaystyle \mathrm{\neg }}$ ${\displaystyle P}$( ${\displaystyle f}$( ${\displaystyle c}$)${\displaystyle }$,${\displaystyle \mathrm{\forall }}$ x${\displaystyle }$. ${\displaystyle P}$( x${\displaystyle )\}}$ ${\displaystyle \{\neg P(f(c)),\all x.$$P(x)\}$은(는) 불만족스럽지만$$,${\displaystyle \mathrm{one}}$ x . P ( x$){\displaystyle \forall x$에 범용 정량자에 대한 규칙을 현명하지 못한 방법으로 계속 적용하면 닫힌 표고를 얻을 수 없다$.$$예$를 들어 $P{\displaystyle }$(${\displaystyle x}$$)}$${\displaystyle }$$,$ ${\displaystyle P}$(${\displaystyle f}$(${\displaystyle }$)${\displaystyle }$, ${\displaystyle P}$ ( ${\displaystyle f}$ ( ) , F${\displaystyle }$( ${\displaystyle f}$(${\displaystyle }$)${\displaystyle }$, , , , , $…[$ $displaystyle P(c$), $P(f(c)),$P$($f$(f(c)),$ P$(dots$ } 등$.$ 탁상 규칙의 적용에 대한 이것과 유사한 "불공정" 정책을 배제함으로써 닫힌 테이블au를 항상 발견할 수 있다$.$null

범용 정량자${\displaystyle (\forall )}$ ${\displaystyle(\forall )}$에 대한 규칙은 인스턴스화할 용어를 지정하지 않기 때문에 유일한 비결정적 규칙이다$$.또한 다른 규칙은 공식과 공식의 각 경로에 대해 한 번만 적용하면 되지만, 이 규칙에는 복수의 적용이 필요할 수 있다.그러나 다른 규칙이 적용되지 않을 때까지 규칙의 적용을 지연시키고 테이블라우의 경로에 이미 나타나는 접지 용어에 규칙의 적용을 제한함으로써 이 규칙의 적용을 제한할 수 있다.아래에 제시된 통일과의 표고의 변형은 비결정론 문제를 해결하는 것을 목표로 한다.null

통일로 1차 테이블아우

단일화가 없는 tableau의 주요 문제는 보편적 정량화 규칙에 $대해$ t ${\displaystyle t}$을(를) 어떻게 선택할 것인가 하는 것이다.실제로 가능한 모든 기본 용어가 사용될 수 있지만, 명백히 그들 중 대부분은 탁자를 닫는 데 무용지물이 될 수 있다.null

이 문제에 대한 해결책은 규칙의 결과로 적어도 테이블라우의 분기를 닫을 수 있는 시기로 용어의 선택을 "지연"하는 것이다.이 작업은 ${\displaystyle \mathrm{용어}}$ 대신 변수를 사용하여 수행할 수 있으며, 따라서 $\forall {\displaystyle \mathrm{}}$ x .${\displaystyle \gamma }$(${\displaystyle x}$ ) ${\displaystyle \forall$ x$.\gamma (x)}$이(가)$$$\gamma {\displaystyle }$( ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$) ${\displaysty \gamma (x')$를 생성한$$ 다음 나중에 $x{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$을 용어로 대체할$$ 수 있다.범용 정량자에 대한 규칙은 다음과 같다.

${\displaystyle }$(${\displaystyle \mathrm{\forall }}$ )${\displaystyle \frac{\mathrm{}x}{}}$ .${\displaystyle \frac{\gamma }{}}$( x${\displaystyle \frac{}{}}$) ${\displaystyle \frac{}{}}$ ( ${\displaystyle \frac{x}{{}^{}}}$) { ( ${\displaystyle \frac{{}^{}}{}}$ )$$ (x ){\$displaystyle (\forall ){\frac$ {\$frac(\forall$ x$.\flause (x)}}}}}}$여기서$$ $x{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$은 테이블의 다른 모든 곳에서 발생하지 않는 변수다$$.

공식의 초기 집합은 자유 변수를 포함하지 않아야 하지만, 표의 공식은 이 규칙에 의해 생성된 자유 변수를 포함한다.이러한 자유 변수는 암묵적으로 보편적으로 정량화된 것으로 간주된다.null

이 규칙은 기초 용어 대신 변수를 사용한다.이러한 변화의 이득은 이러한 변수들이 Tableau의 분기를 닫을 수 있을 때 값을 부여할 수 있다는 것이며, 이로 인해 무용지물이 될 수 있는 항을 생성하는 문제를 해결할 수 있다는 것이다.null

$(\displaystyle (\displayma )}$

if ${\displaystyle \sigma }$ is the most general unifier of two literals ${\displaystyle A}$ and ${\displaystyle B}$, where ${\displaystyle A}$ and the negation of ${\displaystyle B}$ occur in the same branch of the tableau, ${\displaystyle \sigma }$ can be applied at the same time to all formulae of식탁보

${\displaystyle 예}$를 들어$,{\displaystyle }$ { ${\displaystyle \mathrm{\neg }}$ ${\displaystyle P}$( a${\displaystyle }$)${\displaystyle }$, ${\displaystyle \mathrm{\forall }}$ ${\displaystyle x}$. ${\displaystyle P}$ (${\displaystyle x)\}}$ ${\displaystyle \{\neg P(a),\all x.$${\displaystyle P}$$(x)\}\}$은(는) 먼저 $P{\displaystyle ({x\mathrm{}}_{}}$ 1$){\displaystyle P(x_{1}})$를 생성하여 만족스럽지 못함을 증명할$$ 수 있다$.$ 이 리터럴의 부정은 $\neg {\displaystyle \mathrm{}}$ $){\displaystyle \$$neg$ $P(a$$)}$로$,$ 가장 일반적인 유니파인은 ${\displaystyle {x\mathrm{}}_{}}$ $1$을 ${\$$dis$ $substylease a}$로 대체하는 것이다$.$적정을 수행하면 $P{\displaystyle (}$ ${\displaystyle {x\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$) ${\displaystyle P(x_{1})$를 P${\displaystyle (}$ )$${\$displaystyle P(a$${\displaystyle 으}$)로 교체하고 테이블au를 닫는다.null

이 규칙은 최소한 테이블라우의 한 분기를 닫는다. 즉 고려된 리터럴 쌍을 포함하는 분기를 포함한다.그러나 대체는 이 두 리터에만 적용되는 것이 아니라 테이블라우 전체에 적용해야 한다.이것은 tableau의 자유변수는 경직되어 있다는 말로 표현된다. 변수의 발생이 다른 것으로 대체되는 경우, 동일한 변수의 다른 모든 발생은 동일한 방식으로 대체되어야 한다.형식적으로 자유 변수는 보편적으로 정량화되며(비정확히) 표의 모든 공식은 이 정량자의 범위에 포함된다.null

실존적 정량자는 스콜레마이징에 의해 처리된다.단일화가 없는 테이블라우와는 반대로 스콜렘 용어는 단순한 상수가 아닐 수도 있다.실제로 통일된 표의 공식은 자유 변수를 포함할 수 있으며, 이는 암묵적으로 보편적으로 계량화된 것으로 간주된다.따라서${\displaystyle \mathrm{}}$∃ ${\displaystyle x}$ .${\displaystyle \Delta }$( x${\displaystyle }$) ${\displaystyle \exists$ x$.\delta (x)}$와 같은 공식은 범용 정량자의 범위에 속할 수$$ 있다. 만일 이 경우 스콜렘 용어는 단순한 상수가 아니라 새로운 함수 기호와 공식의 자유 변수로 만들어진 용어다.null

$x$$}$$}}}{\displaystyle f}$이(가) 새로운 함수 기호이고 ${\displaystyle {x\mathrm{}}_{}}$ $1{\displaystyle {}_{}}$,${\displaystyle }$x ${\displaystyle n_{}}$ ${\$의 자유 변수 $\Delta {\displaystyle }${\$displaystyle \properties}$

$이{\displaystyle {}_{}}$ 규칙은 x ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle x_{}}$ ${\displaystyle {}_{}}$ ${\$이(가) $\Delta {\displaystyle }$ ${\displaystyle \delta }$만의 변수가 아닌 분기의 자유 변수인$$ 규칙에 대한 단순화를 통합한다.함수 기호가 $\Delta {\displaystyle }$ ${\displaystyle \delta$ }과$($와) 동일한 공식에서 이미 사용된$$ 경우 이 규칙은 변수 이름 변경까지 재사용하여 더욱 단순화할 수 있다.null

표수로 대표되는 공식은 자유 변수를 보편적으로 정량화한 것으로 간주한다는 추가적인 가정과 함께 제안 사례와 유사한 방식으로 얻는다.명제의 경우, 각 가지의 공식은 결합되고 그 결과 공식은 분리된다.또한 결과 공식의 모든 자유 변수는 보편적으로 정량화된다.이 모든 정량자는 그 범위에 전체 공식을 가지고 있다.In other words, if ${\displaystyle F}$ is the formula obtained by disjoining the conjunction of the formulae in each branch, and ${\displaystyle x_{1},\ldots ,x_{n}}$ are the free variables in it, then ${\displaystyle \forall x_{1},\ldots ,x_{n}.$$F}$는 tableau로 대표되는 공식이다.다음과 같은 고려사항이 적용된다.

• 자유 변수가 보편적으로 정량화된다는 가정은 가장 일반적인 통일체의 적용을 소리 규칙으로 만드는 것이다. 왜냐하면 $\gamma {\displaystyle }$${\displaystyle }$( ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$) ${\$$displaystyle$ $\$$gamma$ $(x')}$은 $x{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ x$\text{'}\},$ $\gamma {\displaystyle }$ (${\displaystyle }$t${\displaystyle }$) ${\displaysty \gamma (t)$ i$$$}$의 모든 가능한 값에 대해$$$$진실임을 의미하기 때문이다.s 가장 일반적인 통합자가 $x{\displaystyle }$ ${\displaystyle x}$을(를) 대체하는$$ $t{\displaystyle }$ ${\displaystyle t}$ 용어에 대해 true.
• 표의 자유 변수는 경직적이다. 동일한 변수의 모든 발생은 동일한 항으로 교체해야 한다.모든 변수는 아직 결정되지 않은 용어를 나타내는 기호로 간주될 수 있다.이는 표수로 대표되는 전체 공식에 대해 자유 변수가 보편적으로 정량화된 것으로 가정된 결과로서, 동일한 변수가 두 개의 다른 노드에서 자유롭게 발생하는 경우, 두 발생 모두 동일한 정량자의 범위에 포함된다.As an example, if the formulae in two nodes are ${\displaystyle A(x)}$ and ${\displaystyle B(x)}$, where ${\displaystyle x}$ is free in both, the formula represented by the tableau is something in the form ${\displaystyle \forall x.(...$$A(x)...B(x$ 이 공식은 ${\displaystyle (...}$ ${\displaystyle A}$( x${\displaystyle }$)${\displaystyle }$.${\displaystyle B}$(${\displaystyle x}$)${\displaystyle (...)$을 암시한다.$A(x)...B(x)...}$은(는) $x{\displaystyle }$ ${\displaystyle x$의 모든 값에 대해 참이지만$$ 일반적으로 의미$(.{\displaystyle A}$( t${\displaystyle }$)${\displaystyle }$.${\displaystyle {}^{}}$( ) . . . . .${\displaystyle }$.${\displaystyle }$.${\displaystyle }$. . . . . . . .${\displaystyle }$. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .$displaystystylean (...$$A(t)...A(t')...$$)}$은(는) $일반적$으로 다른 값을 가질 수 있으므로$$t {\$displaystyle t}$ 및 $\$ {\$displaystyle t'}$에 대한$$ 두 가지 용어$.$즉, $x{\displaystyle }$ ${\displaystyle x}$을(를) $A{\displaystyle (x}$ ${\displaystyle )}$ ${\displaystyle A(x)}$ 및$$ $B{\displaystyle (x)}$ ${\displaystyle B(x)}$의 서로 다른 두 용어로 대체할 수 없다는$$ 뜻이다$.$
• 유효성을 확인하기 위한 공식의 자유 변수 또한 보편적으로 정량화된 것으로 간주된다.그러나 테이블라우 규칙은 공식의 반대편에서 작동하지만 여전히 자유 변수를 보편적으로 정량화된 것으로 취급하기 때문에 이러한 변수들은 테이블라우를 구축할 때 자유로울 수 없다.For example, ${\displaystyle P(x)\rightarrow P(c)}$ is not valid (it is not true in the model where ${\displaystyle D=\{1,2\},P(1)=\bot ,P(2)=\top ,c=1}$, and the interpretation where ${\displaystyle x=2}$).따라서$,{\displaystyle }$ { ${\displaystyle P}$(${\displaystyle x}$ )${\displaystyle }$, ${\displaystyle \mathrm{\neg }}$ ${\displaystyle P}$(${\displaystyle c}$ ) ${\displaystyle \}}$ ${\displaystyle$\{$P(x),\neg P(c)\}}$은(동일한 모델과 해석으로 만족한다).그러나 닫힌 ${\displaystyle \mathrm{테이블au}}$는 $P{\displaystyle }$ ( x ) {\$displaystyle$ ${\displaystyle P}$$(x)}$ 및$$ $\neg {\displaystyle \mathrm{}}$ P ${\displaystyle (c)}$ ${\displaystyle \neg P(c)}$과$($와${\displaystyle )}$ 함께 생성될 수 있으며, $x{\displaystyle }$ ${\displaystyle$ $x$$}$을(를) $c{\displaystyle }$ ${\displaystystyc}$로 대체하면$$ 닫힘이 생성된다.올바른 절차는 먼저 범용 정량자를 명시적으로 만들어 $\forall {\displaystyle \mathrm{}}$ ${\displaystyle x}$.${\displaystyle }$( (${\displaystyle p}$(${\displaystyle }$) →${\displaystyle }$P ( ) → ${\displaystyle P}$(${\displaystyle }$) ${\displaystyle \forall x.$ ($p(x)\rightarrow P (c)}}$을(를) 생성하는 것이다$.$

다음 두 가지 변형도 정확하다.null

• 이 대체물이 Tableau를 나타내는 공식에 대해 자유롭다면 Tableau의 자유 변수에 대한 대체물을 Tableau 전체에 적용하는 것은 올바른 규칙이다.다른 세계에서는, 그러한 치환법을 적용하면 여전히 입력 세트의 결과인 테이블라우가 된다.대부분의 일반적 고유어를 사용하면 자동으로 테이블라우의 자유도 조건이 충족된다.
• 일반적으로 모든 변수는 전체 테이블라우에서 같은 용어로 대체되어야 하지만, 이것이 필요하지 않은 특별한 경우가 있다.

통일과의 표는 완전하다는 것을 증명할 수 있다: 일련의 공식들이 만족스럽지 않다면, 그것은 통일된 표와 함께 증명된 것이다.그러나 실제로 그런 증거를 찾는 것은 어려운 문제일 수 있다.단일화가 없는 경우와 반대로 대체 적용은 테이블라우의 기존 부분을 수정할 수 있으며, 대체 적용은 최소한 분기를 닫는 동안 다른 분기를 닫을 수 없게 만들 수 있다(세트가 불만족스럽더라도).null

이 문제에 대한 해결책은 지연된 인스턴스화: 모든 지점을 동시에 닫는 지점을 찾을 때까지 대체물을 적용하지 않는다.이 변종과 함께, 만족스럽지 못한 세트에 대한 증거는 항상 다른 규칙의 적절한 적용 정책에 의해 발견될 수 있다.그러나 이 방법은 전체 테이블라우를 메모리에 보관할 것을 요구한다. 일반적인 방법은 분기를 닫아 버릴 수 있는 반면, 이 변형은 끝까지 어떤 분기도 닫지 않는다.null

집합이 만족스럽지 않더라도 생성될 수 있는 일부 테이블aux가 닫힐 수 없는 문제는 다른 테이블au 확장 규칙 집합에 공통적이다: 이러한 규칙의 적용의 일부 특정 시퀀스가 닫힌 테이블au 구성을 허용하더라도(세트가 만족스럽지 못한 경우), 일부 다른 시퀀스는 닫을 수 없는 테이블au로 이어진다.. 이러한 경우에 대한 일반적인 해결책은 "Tableau 검색" 섹션에 요약되어 있다.null

Tableau calculi 및 특성

tableau 미적분은 tableau의 구축과 수정을 허용하는 일련의 규칙이다.명제적 tableau 규칙, 통일 없는 tableau 규칙, 통일과의 tableau 규칙은 모두 tableau calculi이다.탁상 미적분학이 소유할 수도 있고 소유하지 않을 수도 있는 중요한 특성으로는 완전성, 파괴성 및 증명 결합성이 있다.null

Tableau 미적분학은 주어진 불만족스러운 공식의 모든 집합에 대해 Tableau 증빙을 만들 수 있다면 complete라고 불린다.위에 언급된 탁상용 칼쿨리는 완전하다는 것을 증명할 수 있다.null

통일된 탁자와 다른 두 캘커리의 현저한 차이는 후자의 두 캘커리는 새 노드를 추가하여 탁자를 수정하는 반면, 전자의 캘커는 탁자의 기존 부분을 수정하는 대체물을 허용한다는 것이다.보다 일반적으로 tableau calculi는 tableau에 새 노드만 추가하느냐에 따라 파괴적이거나 비파괴적인 것으로 분류된다.따라서 통일과 함께하는 탁구는 파괴적인 반면 통일 없는 명제 탁자와 탁자는 파괴적인 것이 아니다.null

교정 결합은 임의의 탁자에서 임의의 불만족 집합에 대한 증거를 얻기 위한 탁상 미적분의 성질로서, 이 탁상 자체가 미적분의 규칙을 적용하여 얻었다고 가정한다.즉, 증명혼합성 탁상 미적분학에서는 불만족스러운 집합으로부터 어떤 규칙이라도 적용할 수 있고, 다른 규칙을 적용하여 닫힌 규칙을 얻을 수 있는 탁상학을 얻을 수 있다.null

증명 절차

tableau 미적분은 단순히 tableau가 어떻게 수정될 수 있는지를 알려주는 규칙들의 집합이다.증명 절차는 실제로 증거를 찾는 방법이다(있는 경우).즉, 탁상 미적분은 규칙의 집합인 반면, 증명 절차는 이러한 규칙의 적용 정책이다.미적분이 완성된다 하더라도, 가능한 규칙 적용의 모든 선택이 만족스럽지 못한 집합의 증거로 이어지는 것은 아니다.예를 들어$,{\displaystyle }$ { ${\displaystyle P}$( ${\displaystyle f}$(${\displaystyle }$)${\displaystyle }$, ${\displaystyle R}$(${\displaystyle }$)${\displaystyle }$, ${\displaystyle \mathrm{\neg }}$ ${\displaystyle P}$( ) , ${\displaystyle \neg }$ ${\displaystyle P}$(${\displaystyle }$)${\displaystyle }$,${\displaystyle \mathrm{\forall }}$ ${\displaystyle X}$ (${\displaystyle }$) , ${\displaystyle \mathrm{\forall }}$ X${\displaystyle }$. ${\displaystyle Q}$} ${\displaystyle \{P(f(c), R(c),\neg P(f(c)\vee \neg R(c$), $\all$ x (c),\) 등이 있다$.$$Q(x)\}$은(는) 만족스럽지 못하지만$$, 통일 없는 통일과 탁보 모두 보편적 정량자가 마지막 공식에 반복적으로 적용되는 규칙을 허용하는 한편, 세 번째 공식에 분리 규칙을 적용하는 것만으로도 폐쇄로 직결된다.null

증명 절차의 경우, 완전성의 정의가 주어졌다: 주어진 불만족스러운 공식 집합에 대해 닫힌 테이블라우를 찾을 수 있다면 증명 절차는 강하게 완성된다.기초 미적분의 입증 결합은 완전성과 관련이 있다: 증명 결합은 임의로 부분적으로 구성된 테이블라우에서 닫힌 테이블라우가 항상 생성될 수 있다는 보장이다(세트가 불만족스러운 경우).입증 결합이 없다면 '잘못된' 규칙을 적용하면 다른 규칙을 적용하여 탁자를 완성할 수 없게 될 수 있다.null

단일화가 없는 명제적 표고와 표고는 강력한 입증 절차를 가지고 있다.특히, 완전한 증명 절차는 규칙을 공정하게 적용하는 것이다.이러한 캘커리가 불만족스러운 집합에서 폐쇄적인 테이블라우를 생성할 수 없는 유일한 방법은 일부 적용 가능한 규칙을 적용하지 않는 것이기 때문이다.null

명제적 표의 경우 공정성은 모든 분기의 모든 공식을 확장하는 것과 같다.더 정확히 말하면, 공식의 모든 공식과 모든 분기에 대해, 그 공식을 전제조건으로 하는 규칙은 분기를 확장하기 위해 사용되었다.명제 표에 대한 공정한 증명 절차는 매우 완벽하다.null

단일화가 없는 1차 표의 경우, 보편적 정량화 규칙에 둘 이상의 적용이 필요할 수 있다는 점을 제외하고는 공정성의 조건이 유사하다.공정성은 모든 보편적 계량기를 무한정 확대하는 것이다.즉, 규칙의 공정한 적용 정책은 여전히 가끔 열려 있는 모든 분기의 모든 보편적 계량기를 확대하지 않고는 다른 규칙을 계속 적용할 수 없다.null

닫힌 테이블라우 검색

만약 탁상 미적분이 완성된다면, 모든 불만족스러운 공식들은 연관된 닫힌 탁상들을 가지고 있다.이 탁자는 항상 미적분학의 규칙의 일부를 적용함으로써 얻을 수 있지만, 주어진 공식에 적용할 규칙의 문제는 여전히 남아 있다.결과적으로, 완전성은 주어진 불만족스러운 공식의 모든 집합에 대해 항상 폐쇄적인 테이블라우로 이어지는 규칙의 적용의 실현 가능한 정책의 존재를 자동으로 암시하지는 않는다.통일 없이 그라운드 탁자와 탁자에 대해 공정한 입증 절차가 완료되지만, 통일과 함께 탁자에 대해서는 그렇지 않다.null

이 문제에 대한 일반적인 해결책은 닫힌 것이 발견될 때까지 탁자의 공간을 검색하는 것이다(만약 있다면, 세트는 만족스럽지 못하다).이 접근법에서는 빈 테이블라우로 시작한 다음 가능한 모든 해당 규칙을 재귀적으로 적용한다.이 절차는 노드에 tableaux 레이블이 지정되어 있고, 유효한 규칙 중 하나를 적용하여 노드의 tableau를 부모에 있는 tableau에서 얻을 수 있는 (불확실한) 트리를 방문한다.null

나뭇가지 하나하나가 무한할 수 있기 때문에 이 나무는 깊이부터가 아니라 폭부터 찾아가야 한다.이것은 나무의 폭이 기하급수적으로 커질 수 있기 때문에 많은 공간을 필요로 한다.일부 노드를 두 번 이상 방문할 수 있지만 다항식 공간에서 작동하는 방법은 반복적으로 심층화하면서 먼저 방문하는 방식으로, 먼저 일정 깊이까지 트리를 방문했다가 다시 심층화하여 방문한다.이 특정 절차는 각 단계에서 중지할 시기를 결정하기 위해 깊이(적용된 테이블라우 규칙의 수이기도 함)를 사용한다.대신 다양한 다른 매개변수(예: 노드 레이블 지정 Tableau 크기)가 사용되어 왔다.null

감소 검소 감소

검색 트리의 크기는 주어진 (상위) 테이블에서 생성될 수 있는 (하위) 테이블보의 수에 따라 달라진다.따라서 이러한 테이블의 수를 줄이면 필요한 검색이 감소한다.null

이 숫자를 줄이는 방법은 내부 구조에 따라 일부 테이블보의 생성을 허용하지 않는 것이다.예를 들어, 한 가지 분기에 리터럴이 포함되어 있다면, 같은 리터럴을 생성하는 확장 규칙을 사용하는 것은 소용없는 일이다. 왜냐하면 리터럴의 두 사본을 포함하는 분기에 원래 공식의 세트가 같기 때문이다.이 팽창은 닫힌 테이블라우가 존재한다면 그것 없이 발견될 수 있기 때문에 허용되지 않을 수 있다.이 제한은 확장하기 위해서만 탁자의 구조를 보면 확인할 수 있기 때문에 구조적이다.null

검색을 줄이는 다른 방법으로는 닫힌 테이블라우를 다른 테이블로 확장하여 여전히 찾을 수 있다는 이유로 테이블라우 생성을 허용하지 않는다.이러한 제한을 글로벌이라고 한다.글로벌 제한의 예로서, 어떤 오픈 지점이 확장될 것인지를 지정하는 규칙을 채택할 수 있다.그 결과, 테이블라우가 예를 들어 두 개의 비공개 분기를 가지고 있는 경우, 규칙은 두 번째 분기의 확장을 허용하지 않으면서 어느 분기를 확장해야 하는지 알려준다.이 제한은 한 가지 가능한 선택이 금지되었기 때문에 검색 공간을 줄인다; 그러나 완전한 것은 손상되지 않는다. 왜냐하면 첫 번째 지점이 결국 닫히면 두 번째 지점이 여전히 확장될 것이기 때문이다.As an example, a tableau with root ${\displaystyle \neg a\wedge \neg b}$, child ${\displaystyle a\vee b}$, and two leaves ${\displaystyle a}$ and ${\displaystyle b}$ can be closed in two ways: applying ${\displaystyle (\wedge )}$ first to ${\displaystyle a}$ and then to ${\disp$$레이스타일 b}$ 또는 그 반대의 경우$.$분명히 두 가지 가능성을 모두 따를 필요는 없다; 사람들은 (${\displaystyle \wedge }$) ${\displaystyle (\wedge )}$이(가) $처음{\displaystyle }$ ${\displaystyle a}$에 적용되는$$ 경우만 고려하고$$ $b{\displaystyle }$ ${\displaystyle b$}에 처음 적용되는 경우는 무시할 수 있다$.$이 두 번째 확장을 무시할 수 있는 것은 먼저$$ ${\displaystyle a}$에 확장 기능을 적용하고$$ 그 $후$에는 b$${\$displaystyle b$}에 확장 기능을 적용하는 다른 테이블라우의 존재이기 때문에 글로벌 제한 사항이다.null

tableaux

임의 공식 대신 절 세트에 적용할 경우, 표고 방법은 여러 가지 효율성 개선을 허용한다.${\displaystyle {}_{}}$ 조항은 자유 ${\displaystyle {변수}_{}}$를 포함하지 않고$$${\displaystyle }$각 $L{\displaystyle {}_{}}$${\displaystyle }$${\displaystyle I_{}}$ $displaystyle$ ${\displaystyle {L\_}_{}}$${$$1}{1}{$1}\$cdots \$cdots$\ve L_{m}}}$ 공식으로 각 L${\${{$i}}}}$이 문자 그대로인$$ 식이다.범용 정량자는 명확성을 위해 생략되는 경우가 많으므로, $예$를${\displaystyle \mathrm{들어}}$ P${\displaystyle }$( ${\displaystyle x}$, y )${\displaystyle (}$ ${\displaystyle Q}$ (${\displaystyle }$f ( ) ${\displaystyle (}$ ${\displaystyle Q}$( ${\displaystyle x}$ ) ${\displaystyle$ P $(x,$${\displaystyle y}$$)\vee Q$(${\displaystyle f}$$(x)}}}$는 실제로$$${\displaystyle \mathrm{}x}$ x${\displaystyle }$(${\displaystyle x}$)$∨$ ${\displaystyle Q}$(${\displaystyle }$) ${\displaystystystylease를 의미한다.$$P(x,y)\vee Q(f(x))}$. Note that, if taken literally, these two formulae are not the same as for satisfiability: rather, the satisfiability ${\displaystyle P(x,y)\vee Q(f(x))}$ is the same as that of ${\displaystyle \exists x,y.$$P(x,y)\vee$ Q$(f(x$자유 변수가 보편적으로 정량화되는 것은 1차 만족도의 정의의 결과가 아니라, 오히려 조항을 다룰 때 암묵적 공통 가정으로 사용된다.null

절에 적용할 수 있는 유일한 확장 규칙은 ($\$ ) {\$displaystyle$ (\forall $)}$과$({\displaystyle \vee )}${\$displaystyle (\ve )}$이다$.$ 이 두 규칙은 완전성을 잃지 않고 조합으로 대체할 수 있다.특히 다음 규칙은 통일과 함께 1차 미적분학의 규칙$$$){\displaystyle (\forall )}$과$(∨){\displaystyle (\ve )}$을 순차적으로 적용하는 것에 해당한다.null

${\displaystyle (C){\frac {L_{1}\vee \cdots \vee L_{n}}{L_{1}' \cdots L_{n}'}}}$ where ${\displaystyle L_{1}'\vee \cdots \vee L_{n}'}$ is obtained by replacing every variable with a new one in ${\displaystyle L_{1}\vee$$\cdots \ve L_{n}}$

만족도를 점검해야 할 세트가 조항으로만 구성되었을 때, 이것과 통일 규칙은 만족감을 입증하기에 충분하다.다른 세계에서는${\displaystyle }$(${\displaystyle C}$) ${\displaystyle (C)}$과$({\displaystyle 와)}$ ${\displaystyle (\sigma )}$로 구성된 테이블라우 캘커리가 완성된다$$.null

조항확장 규정은 리터럴만을 생성하고 새로운 조항은 전혀 없기 때문에 이를 적용할 수 있는 조항은 입력 집합의 조항일 뿐이다.이에 따라 조항확장 규정은 조항이 입력 집합에 있는 경우로 더욱 제한될 수 있다.null

${\displaystyle (C){\frac {L_{1}\vee \cdots \vee L_{n}}{L_{1}' \cdots L_{n}'}}}$ where ${\displaystyle L_{1}'\vee \cdots \vee L_{n}'}$ is obtained by replacing every variable with a new one in ${\displaystyle L_{1}\vee$$\cdots \ve L_{n$ 입력 세트의 한 절임

이 규칙은 입력 세트의 절들을 직접 이용하므로 입력 절의 체인에 대한 테이블라우를 초기화할 필요가 없다.따라서 초기 tableau는 ${\displaystyle \mathrm{tr}}$ ${\displaystyle u}$ e ${\displaystyle true}$라는 단일 노드로 초기화할 수 있다$.$ 이 라벨은 암시적으로 생략되는 경우가 많다.이러한 한층 더 간소화된 결과, (뿌리에서 떨어져) 탁아우의 모든 노드에는 리터럴이라는 라벨이 붙어 있다.null

절 tableau에 여러 가지 최적화를 사용할 수 있다.이러한 최적화는 위의 "폐쇄 테이블라우 검색" 섹션에서 설명한 폐쇄 테이블라우 검색 시 탐색할 수 있는 테이블aux의 수를 줄이는 것을 목적으로 한다.null

연결 테이블라우

연결은 이미 분기에 있는 문자와 무관한 절을 사용하여 분기를 확장하는 것을 금지하는 조건이다.연결은 두 가지 방법으로 정의할 수 있다.

강한 유대감

분기를 확장할 때 현재 리프에서 리터럴의 부정과 통일될 수 있는 리터럴을 포함하는 경우에만 입력 절을 사용하십시오.

약한 유대감

가지에 있는 문자의 부정과 통일된 문자를 포함하는 절의 사용을 허용하다.

두 조건 모두 뿌리로만 구성된 가지에만 적용된다.두 번째 정의는 리터럴이 분기에 있는 리터럴의 부정과 통합되는 리터럴을 포함하는 절의 사용을 허용하는 반면, 첫 번째 정의는 리터럴이 현재 분기의 잎에 있도록 하는 추가적인 제약사항만 허용한다.null

연결성(강성 또는 약성)에 의해 조항 확장이 제한되는 경우, 그 적용은 새로운 잎 중 하나에 대체재를 적용하여 가지를 닫을 수 있는 테이블라우를 생성한다.특히 이것은 가지에서 리터럴의 부정(혹은 부모에서 리터럴의 부정)과 통일되는 조항의 리터럴이 들어 있는 잎이다.null

연결성의 두 조건은 완전한 1차 미적분학으로 이어진다: 일련의 조항이 만족스럽지 않으면 닫힌 연결(강력하거나 약하게) 테이블라우를 가지고 있다.이와 같은 폐쇄형 테이블라우는 "폐쇄 테이블라우 검색" 섹션에서 설명한 바와 같이 테이블au의 공간에서 검색하면 찾을 수 있다.이 검색에서 연결성은 가능한 확장 선택사항을 제거하여 검색을 감소시킨다.다른 세계에서는, 나무의 한 노드의 테이블라우가 일반적으로 여러 가지 다른 방식으로 확장될 수 있지만, 연결은 그 중 극히 일부만 허용할 수 있기 때문에, 더 확장되어야 할 결과 테이블라우의 수가 감소한다.null

이는 다음의 (제안) 예에서 확인할 수 있다.The tableau made of a chain ${\displaystyle true-a}$ for the set of clauses ${\displaystyle \{a,\neg a\vee b,\neg c\vee d,\neg b\}}$ can be in general expanded using each of the four input clauses, but connection only allows the expansion that uses ${\displaystyle \neg a\vee b}$이것은 tableaux의 나무가 일반적으로 4개의 잎을 가지고 있다는 것을 의미하지만 연결성이 강요될 경우 오직 1개의 잎만을 가지고 있다.이는 연결성이 일반적으로 고려해야 할 네 가지 테이블라우 대신 확장하려고 시도할 테이블라우 하나만 남겨둔다는 것을 의미한다.이러한 선택의 감소에도 불구하고, 완전성 정리는 세트가 만족스럽지 못할 경우 닫힌 테이블라우를 찾을 수 있다는 것을 암시한다.null

연계성 조건은 명제(클라호스) 사례에 적용될 때, 결과 미적분학을 불분명한 것으로 만든다.${\displaystyle 예}$를 들어$,{\displaystyle }$ { ${\displaystyle a}$, b ,${\displaystyle \mathrm{\neg }}$ ${\displaystyle b}$ ${\displaystyle \}}$ ${\displaystyle \{a,b,\neg b\}$은(는) 불만족스럽지만$,{\displaystyle }$ ${\$$displaystyle (C)$를 {\$displaystyle a}$에 적용하면 체인 $t{\displaystyle }$ ${\displaystyle u}$ -${\displaystytype true-a$이 생성되며, 이 경우 강력하거나 약한 연결되지 않는다.edness. 약한 연결성의 경우, 결합은 뿌리 확장에 사용되는 조항이 불만족과 관련이 있다면, 즉, 최소한 불만족스러운 조항 집합의 부분집합에 포함되어 있다는 것을 전제로 한다.유감스럽게도 어떤 조항이 이 조건을 충족하는지 확인하는 문제 자체가 어려운 문제다.비혼합성에도 불구하고 위의 "폐쇄된 테이블라우 검색" 섹션에서 설명한 바와 같이, 닫힌 테이블라우를 검색을 사용하여 찾을 수 있다.검색이 필요한 반면, 연결성은 확장의 가능한 선택을 줄여 검색의 효율성을 높인다.null

일반 테이블보

동일한 분기에서 두 번 리터럴이 발생하지 않는 경우 테이블라우는 규칙적이다.이 조건을 시행하면 비정규 테이블라우를 발생시키는 조항은 확장할 수 없기 때문에 테이블라우 확장의 가능한 선택이 감소할 수 있다.null

이러한 허용되지 않는 확장 조치는 아무리 소용이 없다.$B{\displaystyle }$ ${\displaystyle B}$이(가) $리터럴{\displaystyle }$ L ${\displaystyle L}$을(를) 포함하는 분기이고$,$ $C{\displaystyle }$ ${\displaystyle C}$이(가) 확장이 규칙성을 위반하는 조항이라면$$, $C{\displaystyle }$ ${\displaystyle C}$을(를) 포함하고 있다$.$ Tableau를 닫으려면 $B{\displaystyle }$ ${\displaystyle -}$ ${\displaystyle L}$을 확장하고 닫아야 한다.$$$L{\displaystyle }$ ${\displaystyle L}$이(가) 두 번 발생하는$B-L$그러나 이 가지의 공식은 $B{\displaystyle }$ ${\displaystyle B}$의 공식과 정확히 같다.그 결과, $B{\displaystyle }$- ${\displaystyle L}$ ${\displaystyle B-L}$을(를) 닫는 동일한 확장 $단계$도 B$${\$displaystyle$ B$}$을(를) 닫는다$.$ $이$는 C ${\displaystyle$ C$}$을(를) 확장할$$ 필요가 없다는 것을 의미하며, $C{\displaystyle }${\$displaystyle C}$이 다른 리터럴을 포함하면$$ 닫아야 하는 다른 잎을 생성하였다.명제의 경우, 잎을 닫는 데 필요한 팽창은 완전히 쓸모없다; 첫 번째 순서의 경우, 그것들은 일부 통일성 때문에 나머지 테이블라우에만 영향을 미칠 수 있다; 그러나 이것들은 테이블라우의 나머지 부분을 닫는 데 사용되는 대체물과 결합될 수 있다.null

모달 로직의 표

모달 논리학에서 모델은 각각 진실 평가에 관련된 가능한 세계의 집합으로 구성된다. 접근성 관계는 다른 세계에서 접근 가능한 세계를 말한다.모달 공식은 가능한 세계에 걸친 조건뿐만 아니라 그것으로부터 접근 가능한 조건에도 명시할 수 있다.예를 들어$,{\displaystyle }$ $A{\displaystyle }$ ${\$$displaystyle \Box$ A$}$이(가) 액세스할 수 있는 모든 월드에서 참인$$ 경우 world ${\displaystyle A}$ ${\$$displaystyle$ \$Box$ A}은(는) 세계에서$$ 참이다.null

명제적 논리의 경우, 모달 로직의 표는 공식을 반복적으로 그것의 기본 구성요소로 분해하는 것에 기초한다.그러나 모달 공식을 확장하려면 다른 세계에 걸쳐 조건을 명시해야 할 수 있다.${\displaystyle 예}$를 들어, ${\displaystyle \neg }$ $\$ A {\$displaystyle \neg \Box$A}이$$(가) 세계에서 참인 경우, $A{\displaystyle }$ ${\displaystyle A}$이(가) 거짓인 세계에서 액세스할 수 있는 세계가 존재한다.그렇다고 명제에 다음의 법칙을 간단히 덧붙일 수는 없다.null

${\displaystyle {\frac {\neg \Box A}{\neg A}}$

명제표에서 모든 공식은 동일한 진실 평가를 참조하지만, 위의 규칙의 전제조건은 다른 세계에 있는 반면 다른 세계에 있는 것이다.이것을 고려하지 않으면 잘못된 결과가 나올 것이다.예를 들어 공식 $a{\displaystyle }$ ${\displaystyle \mathrm{\neg }}$ ◻${\displaystyle }$◻ ${\displaystyle a}$ a ${\displaystyle a\wedge \neg \Box a}$은(는) $현재{\displaystyle }$ 세계에서 참이며$$, ${\displaystyle a}$은(는) 액세스할 수 있는 세계에서 거짓이라고$$ 명시한다$$.단순히 (${\displaystyle \wedge }$ ) ${\displaystyle (\wedge )}$과 위의 확장 규칙을 적용하면 ${\displaystyle a}$과 ${\displaystyle \neg a}$이$($가) 생성되지만, 이 두 공식은 일반적으로 서로 다른 세계에 있는 것처럼 모순을 생성해서는 안 된다.모달표보칼슘은 위의 것과 같은 종류의 규칙을 포함하고 있지만, 다른 세계를 언급하는 공식의 부정확한 상호작용을 피하기 위한 메커니즘을 포함하고 있다.null

기술적으로 모달 로직의 표는 공식 집합의 만족도를 점검한다: 모델 $M{\displaystyle }$ ${\displaystyle$ M$}$과 월드$$ $w{\displaystyle }$ ${\displaystyle w}$이(가) 존재하는지 여부를 점검하여 해당 모델과 세계에 공식이 참이 되도록 한다$$.위의 예에서 ${\displaystyle a}$은(는) w ${\displaystyle w}$에 ${\$$displaystyle a$$}$의 진위를 명시하는$$ 반면$,$ 공식 $¬$ $w{\displaystyle }$${\displaystyle {}^{}}$${\displaystyle w}$ 및$$ w}에서 액세스할 수 있는 ${\displaystyle \mathrm{일부}}$$$ 세계에서는$$ ${\$의${\displaystyle \mathrm{}}$진리를 명시한다$$.hich는 일반적으로 $w{\displaystyle }$ ${\displaystyle w}$과 다를 수 있다$.$ 형식은 다른 세계를 나타낼 수 있다는 점을 고려한다.null

이 사실은 중요한 결과를 가지고 있다: 세상에 존재하는 공식은 그 세계의 다른 후계자들에 대한 조건들을 암시할 수 있다.그런 다음, 단일 후계자를 언급하는 공식의 하위집합에서 만족도가 증명될 수 있다.이것은 한 세상에 한 명 이상의 후계자가 있을 수 있는 경우를 붙잡는데, 이것은 대부분의 모달 논리에 적용된다.만일 그렇다면 $\neg {\displaystyle \mathrm{}}$ ${\displaystyle A}$$$${\displaystyle \wedge }$ ${\displaystyle \mathrm{\neg }}$ ¬ ${\displaystyle ◻}$ ${\displaystyle B}$ ${\displaystyle \neg \box$$A$\$wedge \neg$ \$neg$\$B}$이(가$)$ 있는$$ 후계자가 존재하고${\displaystyle \mathrm{}}${$$B {\$displaystyle \neg$ B}이$$(가$)$가 있는 후계자가 존재한다면 이러한$$ 공식은 참이다.반대로 임의의 후계자에서$$ $\neg {\displaystyle \mathrm{}}$ ${\displaystyle A}$ ${\displaystyle$ $\$$neg A}$의 불만족을 나타낼 수 있다면, 이${\displaystyle \mathrm{}\mathrm{공식}}$은 $\$ B {\$displaystyle$ \$neg$ B}이$($가) 쥐고$$ 있는 세계를 확인하지 않고서는 만족하지 못하는 것으로 증명된다.At the same time, if one can show unsatisfiability of ${\displaystyle \neg B}$, there is no need to check ${\displaystyle \neg A}$. As a result, while there are two possible way to expand ${\displaystyle \neg \Box A\wedge \neg \Box B}$, one of these two ways is always sufficient to prove unsatisfiability if공식은 만족스럽지 못하다.예를 들어$,{\displaystyle \mathrm{}}$ ${\displaystyle a}$ A$${\$displaystyle \neg$A}이$$(가) 보유하고 있는 임의의 세계를 고려하여 Tableau를 확장할 수 있다.이러한 확장이 불만족스러움으로 이어진다면 원래의 공식은 불만족스럽다.그러나 이런 식으로 만족감을 증명할 수 없을 수도 ${\displaystyle \mathrm{있고}}$,${\displaystyle \mathrm{}}${$$B {\$displaystyle \neg$ B$$$}$이(가) 쥐고 있는 세계를 대신 고려했어야 했다.따라서 one${\displaystyle \neg \Box A}$만 ${\displaystyle \mathrm{확장}}$하거나 b${\displaystyle }$B$${\$displaystyle \neg \Box$B}만$$ 확장하면 항상 불만족스러움을 입증할 수 있지만, 잘못된 선택이 이루어진 경우 테이블au가 닫히지 않을 수 있다.두 가지 보조양식을 확장하면 완벽하지만 입증 충돌은 아닌 탁상용 칼쿨리가 발생한다.따라서 "폐쇄 테이블라우 검색"에 설명된 대로 검색해야 할 수 있다.null

tableau 확장 규칙의 전제 조건과 결과가 동일한 세계를 참조하는지 여부에 따라 이 규칙을 정적 또는 트랜잭션이라고 한다.제안형 연결에 대한 규칙이 모두 정적인 반면, 모달 연결에 대한 모든 규칙이 트랜잭션인 것은 아니다. 예를 들어, 공리 T를 포함한 모든 모달 논리에서는 $◻{\displaystyle }$ ${\displaystyle A}$ ${\displaystyle \Box A}$이(가) 동일한 $세계$에서 A ${\displaystystyle$ A$}$을(를) 의미한다고 한다.그 결과, 상대적 (모달) 테이블라우 확장 규칙은 그 전제조건과 결과가 모두 같은 세계를 가리키기 때문에 정적이다.null

공식 삭제 테이블라우

잘못된 방식으로 상호 작용하지 않는 다른 세계를 지칭하는 공식을 만드는 방법은 나뭇가지의 모든 공식이 동일한 세계를 가리키도록 하는 것이다.일관성을 검사할 집합의 모든 공식은 동일한 세계를 참조하는 것으로 가정하기 때문에 이 조건은 처음에 참이다.분기를 확장할 때 두 가지 상황이 가능하다. 새로운 공식은 분기의 다른 공식과 같은 세계를 가리킨다.첫 번째 경우에는 규칙이 정상적으로 적용된다.두 번째의 경우, 신세계에서도 보유하지 않는 지부의 모든 공식은 지부에서 삭제되며, 아마도 구세계와 여전히 상대적인 다른 모든 지부에 추가될 수 있다.null

예를 들어, S5에서 한 세계에서 참인 ${\displaystyle \mathrm{모든}}$ 공식 $◻{\displaystyle }$ ${\displaystyle \Box A}$은(는) 접근 가능한 모든 세계에서도 참이다(${\displaystyle 즉}$, A ${\displaystyle A}$ 및$$ $◻{\displaystyle }$ ${\displaystyle \Box A}).$따라서 다른 세계에 결과가 나타나는$$${\displaystyle \frac{\neg }{}}$ $\$ A {\$displaystyle {\frac {\nex$ $\Box A$$}{\$$nex$ A$}}$을(를$)$ 적용할 때 분기에서 모든 공식을 삭제하지만$,$ 새로운 세계에서도 공식을 그대로 ${\displaystyle \mathrm{유지}}$할 수 있다.그런 다음 완전성을 유지하기 위해 삭제된 공식을 구세계를 여전히 지칭하는 다른 모든 가지에 추가한다.null

세계적인 표고

서로 다른 세계를 참조하는 공식 사이의 올바른 상호작용을 보장하기 위한 다른 메커니즘은 공식에서 라벨로 표시된 공식으로 전환하는 것이다: $A{\displaystyle }${\$displaystyle A$을 쓰는 대신 ${\displaystyle w}$ :${\displaystyle }$A ${\displaystyle w:$$}$은(는) A이$(가$) w {\$displaystyle$ $w}$ $월드$에서 보유함을$$ 명시하도록 하기 위해$$$.$

모든 제안적 확장 규칙은 모두 동일한 세계 레이블을 가진 공식을 참조한다고 명시함으로써 이 변형에 적응된다.예를 들어 $w{\displaystyle }$: ${\displaystyle A}$ ${\displaystyle \wedge }$ B ${\displaystyle w:$$A\wedge B}$은(는) ${\displaystyle w}$로 표시된 두 개의 노드를 생성함$$: A${\displaystyle w:$${\displaystyle \mathrm{A<img\; alt="w:A"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/d482e1c37b655f8b5a4e59fd03e786208b2a6ae1"\; style="vertical-align:\; -0.338ex;\; width:5.344ex;\; height:2.176ex;"\; papago-attr-id="628">}}$$}$ 및 w${\displaystyle }$: B ${\displaystyle w:$$B$ 분기는 $w{\displaystyle :}$ ${\displaystyle w:a}$ 및 $w$: {\displaystyle $:\neg$ a$}$과 $같이$ 동일한 세계의 반대편 리터럴 2개를 포함하는 경우에만 닫힌다.$$${\displaystyle w:}$ ${\displaysty w:$${\displaystyle a}$$}$ $및$ w$\:$ {\$displaystystyle w':\ne}$과 같이 두 월드 레이블이 다른 경우 닫히지 않는다$.$

모달 팽창 규칙은 다른 세계를 가리키는 결과를 가질 수 있다.예를 들어${\displaystyle \mathrm{}}$¬ ${\displaystyle ◻}$ ${\displaystyle A}$ ${\displaystyle \neg \Box A}$에 대한 규칙은 다음과 같이 기록된다$$.

${\displaystyle {\frac {w:\neg \Box A}{w':\neg A}$

이 규칙의 전제 조건과 결과는 각각 $w{\displaystyle }$ ${\displaystyle$ w$}$과 w${\displaystyle {}^{}}w{\displaystyle {}^{}}$ ${\$을(를) 가리킨다$.$다양한 캘커리는 라벨로 사용되는 세계의 접근성을 추적하기 위해 다른 방법을 사용한다.어떤 것은 w${\displaystyle {}^{}}R{\displaystyle {}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$$displaystyle$ $w'}$을(를) $w{\displaystyle }$ ${\$displaystyle $w'}$에서 액세스할 수 있다는$$ 것을$$ $나타내는{\displaystyle }$ w R w ′ {\$displaystyle$ w'}과 같은 유사 형식을 포함한다$.$ 어떤 다른 일부는 정수의 시퀀스를 월드 라벨로 사용하며, 이 표기법은 접근성 관계를 암시적으로 나타낸다(예:${\displaystyle }$($,$,${\displaystyle 2}$,$3).$$3)}$은(는)${\displaystyle }$(1${\displaystyle ,}$ ${\displaystyle 4}$,${\displaystyle }$2${\displaystyle }$) ${\displaystyle (1,4,2)}$ 에서 액세스할 수 있다$$.)$$

세트 라벨링 테이블aux

서로 다른 세계에 있는 공식들 사이의 상호작용 문제는 세트 라벨링 테이블보를 사용함으로써 극복할 수 있다.이들은 노드에 공식 집합이 붙어 있는 나무들이다. 확장 규칙은 잎의 라벨에만 기초하여 새 노드를 잎에 부착하는 방법을 알려준다(가지에 있는 다른 노드의 라벨에는 표시되지 않음).null

모달 로직의 표는 주어진 모달 로직에서 모달 공식 집합의 만족도를 확인하는 데 사용된다.공식 $S{\displaystyle }$ ${\displaystyle S}$을$($를) 지정하면 $모델{\displaystyle }$ M ${\displaystyle M}$과($와{\displaystyle }$) M${\displaystyle ,}$ ${\displaystyle w}$ ${\displaystyle \models }$ S$${\$displaystyle M,w\models$ S$}$과(와) 같은 월드 $W{\displaystyle }$ ${\displaystystyle W}$의 존재를 확인한다$.$

확장 규칙은 사용된 특정 모달 논리에 따라 달라진다.기본 모달 논리 K에 대한 테이블라우 시스템은 다음과 같은 명제 테이블라우 규칙에 추가하여 얻을 수 있다.

${\displaystyle (K){\frac {\Box A_{1};\Ldots;\Box A_{n};\neg \Box B}{A_{1};\ldots;A_{n};\neg B}}$

직관적으로 이 규칙의 전제조건은 모든 접근 가능한 ${\displaystyle {}_{}}$에서는 $모든{\displaystyle {}_{}}$ 공식 A${\displaystyle {}_{}{1\mathrm{}}_{}}$ ,${\displaystyle \dots ,}$ ${\displaystyle n_{}}$ ${\$의 진실, 그리고 어떤 접근 가능한 세계에서는$$ $\neg {\displaystyle \mathrm{}}$ {\$displaystyle \neg B}$의 진실을 표현한다.이 규칙의 결과는 $\neg {\displaystyle \mathrm{}}$ ${\displaystyle B}$ ${\displaystyle \neg B}$이(가) 참인 세계 중 하나에서 반드시 참이어야 하는 공식이다.null

좀 더 기술적으로 모달 테이블aux 방법은 $모델{\displaystyle }$ M ${\displaystyle M}$과 공식 집합을 참으로 만드는$$ $월드{\displaystyle }$ w ${\displaystyle w}$의 존재를 확인한다.If ${\displaystyle \Box A_{1};\ldots ;\Box A_{n};\neg \Box B}$ are true in ${\displaystyle w}$, there must be a world ${\displaystyle w'}$ that is accessible from ${\displaystyle w}$ and that makes ${\displaystyle A_{1};\ldots ;A_{n};\neg B}$ true따라서 이 규칙은 그러한 $w{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$에서 충족되어야 하는 공식 집합을 도출하는 것과 같다$.$

While the preconditions ${\displaystyle \Box A_{1};\ldots ;\Box A_{n};\neg \Box B}$ are assumed satisfied by ${\displaystyle M,w}$, the consequences ${\displaystyle A_{1};\ldots ;A_{n};\neg B}$ are assumed satisfied in ${\displaystyle M,w'}$: same모델이지만 다른 세계일 수도 있다.세트 라벨 표는 각 공식이 참이라고 가정되는 세계를 명시적으로 추적하지 않는다. 두 개의 노드가 동일한 세계를 참조할 수도 있고 아닐 수도 있다.그러나 주어진 노드에 라벨을 붙이는 공식은 같은 세계에서 참된 것으로 가정한다.null

공식이 참이라고 가정되는 가능한 다른 세계의 결과로서, 모달 규칙의 모든 적용은 하나의 세계에서 다른 세계로 이동하는 것에 대응하므로, 한 노드의 공식은 모든 후손에서 자동으로 유효하지 않다.이 조건은 세트 라벨링 테이블로 자동 포획되는데, 확장 규칙은 그들이 적용되는 잎에만 기초하고 조상은 그렇지 않기 때문이다.null

Remarkably, ${\displaystyle (K)}$ does not directly extend to multiple negated boxed formulae such as in ${\displaystyle \Box A_{1};\ldots ;\Box A_{n};\neg \Box B_{1};\neg \Box B_{2}}$: while there exists an accessible world where ${\displaystyle B_{1}}$ is false$그리고{\displaystyle {}_{}}$ B ${\$}}개가 거짓인$$ 하나의 세계, 이 두 세계가 반드시 동일한 것은 아니다.null

발의안 규칙과는 달리$,{\displaystyle }$ (${\displaystyle K}$) ${\디스플레이$ 스타일$(K)}$은 모든 전제조건에 대한 조건을 명시하고$$ 있다.For example, it cannot be applied to a node labeled by ${\displaystyle a;\Box b;\Box (b\rightarrow c);\neg \Box c}$; while this set is inconsistent and this could be easily proved by applying ${\displaystyle (K)}$, this rule cannot be applied because of formula ${\displaystyle a}$, which is n불일치와도 관련이 있다.이러한 공식의 제거는 다음과 같은 규칙에 의해 가능하다.

${\displaystyle (\theta ){\frac {A_{1};\ldots ;A_{n};B_{1};\ldots ;B_{m}{A_{1};\ldots ;A_{n}}}}}}$

이 규칙(박리 규칙)을 추가하면 결과 미적분학이 서로 일치하지 않게 된다. 동일한 집합에 대해 닫힌 테이블라우가 존재하더라도 일관되지 않은 집합에 대한 테이블라우는 닫기가 불가능할 수 있다.null

규칙 (${\displaystyle \theta }$ ) ${\displaystyle (\theta )}$은 비결정론적이다: 제거할 공식(또는 보관할 공식) 집합은 임의로 선택할 수 있다. 이는 너무 크지 않은 공식 집합을 선택하는 문제를 야기한다. 이는 결과적으로 세트를 만족시키고 너무 작지 않게 하기 때문에 필요한 확장 규칙을 적용할 수 없게 만든다.가능한 선택의 수가 많으면 닫힌 탁자를 찾는 문제가 더 어려워진다.null

${\displaystyle \mathrm{이러한}}$ 비결정론은 모달 확장 규칙 이전에만 적용되도록$($ $style$ ) ${\displaystyle$ (\theta )}의 사용을 제한하고, 다른 규칙을 적용할 수 없게 만드는 공식만 제거함으로써 피할 수 있다.이 조건은 또한 두 규칙을 하나의 규칙으로 병합하여 공식화할 수 있다.결과 규칙은 이전 규칙과 동일한 결과를 내지만, 이전 규칙을 적용할 수 없게 만든 공식은 모두 암묵적으로 폐기한다.${\displaystyle (}{\displaystyle }$mechanism ) ${\displaystyle (\theta )}$을(를) 제거하기 위한 이 메커니즘은 많은 모달 로직에서 완전성을 유지하는 것으로 증명되었다$$.null

Axiom T는 접근성 관계의 반사성을 표현한다: 모든 세계는 그 자체로부터 접근 가능하다.해당 tableau 확장 규칙은 다음과 같다.

${\displaystyle (T){\frac {A_{1};\ldots;A_{n};\Box B}{}{}{A_{1};\ldots;A_{n};\Box B;B}}$

이 규칙은 ${\displaystyle \mathrm{동일}}$한 세계에 대한 조건과 관련된다:${\displaystyle }$a B ${\displaystyle \Box B}$이(가) 한 세계에서 참인 경우, 반사성 $B{\displaystyle }$ ${\displaystyle B}$은(는) 같은 세계에서도 참이다$$.이 규칙은 그 전제조건과 결과 둘 다 같은 세계를 가리키기 때문에 거래가 아닌 정적인 것이다.null

$이{\displaystyle }$ 규칙은 ${$B {\$displaystyle$ B}을(를) 생성하기 위해 "사용"되었음에도 불구하고 ${\displaystyle \mathrm{precondition}}$ B ${\displaystyle$ $\$$Box B}$을(를) 전제조건에서$$ 결과물까지 복사한다$.$ 이는 고려된 세계가 ${\displaystyle \mathrm{같으므로}}{\displaystyle }${$$B {\$displaysty$ \$B}$도 그 상태를 유지한다.이런 '복사'가 필요한 경우도 있다.It is for example necessary to prove the inconsistency of ${\displaystyle \Box (a\wedge \neg \Box a)}$: the only applicable rules are in order ${\displaystyle (T),(\wedge ),(\theta ),(K)}$, from which one is blocked if ${\displaystyle \Box a}$ is not copied.null

보조 테이블보

다른 세계에서 공식 보유를 처리하는 다른 방법은 테이블라우에 소개된 각각의 새로운 세계에 대해 다른 테이블라우를 시작하는 것이다.예를 들어, $\neg {\displaystyle \mathrm{}}$ ${\displaystyle ◻}$ ${\displaystyle A}$ ${\displaystyle \neg \Box A}$은(는) 액세스 가능한 세계에서 $A{\displaystyle }$ ${\displaystyle A}$이(가) 거짓임을$$ 의미하므로$$,${\displaystyle \mathrm{}a}$ A ${\displaystyle \neg$ A$}$에 의해 루트를 새로 시작한다$.$ 이 새로운 tableau는 확장 규칙이 적용된 원래 tableau의 노드에 연결된다. 즉, 이 tableau의 종료.동일한 노드가 다른 보조 테이블aux와 연결되었는지 여부에 관계없이, 노드가 있는 모든 분기의 폐쇄를 생성한다.보조 tableaux의 확장 규칙은 원래 tableau와 동일하므로 보조 tableau는 다른 (보조) tableau를 차례로 가질 수 있다.null

전지구적 가정

위의 모달 테이블은 공식 집합의 일관성을 확립하며, 국소 논리적 결과 문제를 해결하는 데 사용할 수 있다.이것은 각 모델 $M{\displaystyle }$ ${\displaystyle M}$에 대해$$$A{\displaystyle }$ ${\displaystyle A}$이(가) ${\displaystyle w}$이$($가) w {\displaystyle w}인 경우 B ${\displaysty$ B$}$이($가{\displaystyle }$) 동일한 세계에서도 참인지$$ 여부를 확인하는 문제다.$이$는 A ${\displaystyle A}$이(가) 동일한$$ 모델의 동일한 세계에서도 참이라는 가정 하에 $B{\displaystyle }$ ${\displaystyle B}$이(가) 모델의$$ 세계에서 참인지 여부를 확인하는 것과 같다.null

관련된 문제는 글로벌 결과 문제인데, 여기서 $공식{\displaystyle }$(또는 공식 집합) G ${\displaystyle G}$이(가) 모델의 모든 가능한 세계에서 참이라고$$ 가정한다.문제는 $G{\displaystyle }$ ${\displaystyle G}$이(가) 모든$$ 세계에서 참인 $모델{\displaystyle }$ $M{\displaystyle }$ ${\displaystyle$ M$}$에서 B ${\displaystyle$ B$}$이(가) 모든 세계에서도 참인지$$ 확인하는 것이다.null

가정된 공식은 일부 세계에서는 사실이지만 다른 세계에서는 그렇지 않은 모델에서는 국지적 가정과 전지구적 가정이 다르다.예를 들어$,{\displaystyle }$ { ${\displaystyle P}$, ${\displaystyle \mathrm{\neg }}$ ◻${\displaystyle ◻}$ (${\displaystyle P}$ ${\displaystyle \wedge }$ Q${\displaystyle }$)${\displaystyle }$} ${\displaystyle \{P,\neg \Box (P\wedge$ Q$)\}}$은(는)${\displaystyle }$globally$$ ${\displaystyle Q}$ ${\displaystyle$\neg $\Box Q}$을(는)로$$ 포함하지만 로컬은 아니다.$P{\displaystyle }$ ${\displaystyle P}$과 respectively P$,{\displaystyle \mathrm{}Q}$ ${\displaystyle \neg$ P$,Q}$을(를) 각각$$ 참으로 만드는 두 개의 월드로 구성된 모델에는 로컬 엔트리가 적용되지 않으며, 첫 번째 세계에서는 가정은 참이지만${\displaystyle q}$ Q ${\displaystyle \Box$ Q$}$은 거짓이다.$P{\displaystyle }$ ${\displaystyle P}$은(는) 한 세계에서는 참이라고 가정할 수$$ 있고 다른 세계에서는 거짓이라고 가정할 수 있기 때문에 이 백례는 효과가 있다.${\displaystyle \mathrm{그러나}}$ 동일한 가정이 글로벌하다고 간주되는 경우,${\displaystyle \mathrm{}}$¬ P ${\displaystyle \neg P}$은(는) 모델의 어떤 세계에서도 허용되지 않는다$$.null

그래서 하나의 A{A\displaystyle}의 세계적인 가정 G{G\displaystyle}아래인지 B{B\displaystyle}은 지역 결과 확인할 수 있는 이런 2가지 문제가,. Tableaux calculi 세계적인 관념을 매일 노드에 대한 추가 관계 없이 세계의에 대해 언급하고 허용함으로써 대처할 수 있게 결합할 수 있습니다.null

공증

다음 규칙 가끔씩 사용됩니다.null

균일 표기법

언제 tableaux 확장 규칙을 쓰도록 예를 들어 α{\displaystyle \alpha}항상α 1∧ α 2{\displaystyle \alpha_{1}\wedge \alpha _{2}}로 여겨지공식은 종종 규칙을 사용하여, 지적되어 있습니다..다음 표에서는 공식을, first-order고 모델 명제 논리학의 표기법을 제공한다.null

표기법	제조 법
${\displaystyle \alpha}$	${\displaystyle \alpha_{1}\wedge \alpha _{2}}.$	${\displaystyle \neg({\overline{\alpha_{1}}}\vee{\overline{\alpha_{2}}})}.$	${\displaystyle \neg(\alpha_{1}\rightarrow{\overline{\alpha_{2}}})}.$
${\beta\displaystyle}$	${\displaystyle \beta_{1}\vee \beta _{2}}.$	${\displaystyle{\overline{\beta_{1}}}\rightarrow \beta _{2}}.$	${\displaystyle \neg({\overline{\beta_{1}}}\wedge{{\beta_{2}}\overline})}.$
${\displaystyle \gamma}$	${\displaystyle \forall x\gamma_{1}())}$	${\displaystyle \neg \cHB x{\overline {\reverline _{1}(x)}}$
$\displaystyle \reason }$	${\displaystyle \cHB_{1}(x)}$	${\displaystyle \neg \forall x{\overline {\reverline _{1}(x)}}$
$\displaystyle \pi }$	${\displaystyle \Diamond \pi _{1}$	${\displaystyle \neg \Box {\overline {\pi _{1}}}$
$\displaystyle \upsilon }$	${\displaystyle \Box \upsilon _{1}.$	${\displaystyle \neg \Diamond {\overline {\upsilon _{1}}}$

Each label in the first column is taken to be either formula in the other columns. An overlined formula such as ${\displaystyle {\overline {\alpha _{1}}}}$ indicates that ${\displaystyle \alpha _{1}}$ is the negation of whatever formula appears in its place, so that for example in formula ${\displaystyle \neg (a\vee b)}$ the subformula ${\displaystyle \alpha _{1}}$ is the negation of ${\displaystyle a}$.

Since every label indicates many equivalent formulae, this notation allows writing a single rule for all these equivalent formulae. For example, the conjunction expansion rule is formulated as:

${\displaystyle (\alpha ){\frac {\alpha }{\begin{array}{c}\alpha _{1}\\\alpha _{2}\end{array}}}}$

Signed formulae

A formula in a tableau is assumed true. Signed tableaux allows stating that a formula is false. This is generally achieved by adding a label to each formula, where the label T indicates formulae assumed true and F those assumed false. A different but equivalent notation is that to write formulae that are assumed true at the left of the node and formulae assumed false at its right.

History

In his Symbolic Logic Part II, Charles Lutwidge Dodgson introduced the Method of Trees, the earliest modern use of a truth tree.^[1]

The method of semantic tableaux was invented by the Dutch logician Evert Willem Beth (Beth 1955) and simplified, for classical logic, by Raymond Smullyan (Smullyan 1968, 1995). It is Smullyan's simplification, "one-sided tableaux", that is described above. Smullyan's method has been generalized to arbitrary many-valued propositional and first-order logics by Walter Carnielli (Carnielli 1987).^[2] Tableaux can be intuitively seen as sequent systems upside-down. This symmetrical relation between tableaux and sequent systems was formally established in (Carnielli 1991).^[3]

See also

• Resolution (logic)

References

• Beth, Evert W., 1955. "Semantic entailment and formal derivability", Mededelingen van de Koninklijke Nederlandse Akademie van Wetenschappen, Afdeling Letterkunde, N.R. Vol 18, no 13, 1955, pp 309–42. Reprinted in Jaakko Intikka (ed.) The Philosophy of Mathematics, Oxford University Press, 1969.
• Bostock, David, 1997. Intermediate Logic. Oxford Univ. Press.
• M D'Agostino, D Gabbay, R Haehnle, J Posegga (Eds), Handbook of Tableau Methods, Kluwer,1999.
• Girle, Rod, 2000. Modal Logics and Philosophy. Teddington UK: Acumen.
• Goré, Rajeev (1999) "Tableau Methods for Modal and Temporal Logics" in D'Agostino, M., Dov Gabbay, R. Haehnle, and J. Posegga, eds., Handbook of Tableau Methods. Kluwer: 297-396.
• Richard Jeffrey, 2006 (1967). Formal Logic: Its Scope and Limits, 4th ed. Hackett Publishing Company, Inc.
• Raymond Smullyan, 1995 (1968). First Order-Logic. Dover Publications.
• Melvin Fitting (1996). First-order logic and automated theorem proving (2nd ed.). Springer-Verlag.
• Reiner Hähnle (2001). Tableaux and Related Methods. Handbook of Automated Reasoning
• Reinhold Letz, Gernot Stenz (2001). Model Elimination and Connection Tableau Procedures. Handbook of Automated Reasoning
• Zeman, J. J. (1973) Modal Logic. Reidel.

External links

• TABLEAUX: an annual international conference on automated reasoning with analytic tableaux and related methods
• JAR: Journal of Automated Reasoning
• The tableaux package: an interactive prover for propositional and first-order logic using tableaux
• Tree proof generator: another interactive prover for propositional and first-order logic using tableaux
• LoTREC: a generic tableaux-based prover for modal logics from IRIT/Toulouse University