분해능(로직)

수학논리와 자동화된 정리증명에 있어서 분해능은 명제논리와 1차 논리학에서 문장에 대한 반박완전한 정리검증 기법으로 이어지는 추론의 규칙이다. 명제 논리학에서는 결의안 규칙을 체계적으로 적용하는 것이 공식 불만족에 대한 의사결정 절차로 작용하여 (완성된) 부울 만족도 문제를 해결한다. 1차 로직의 경우 1차 로직의 불만족 문제에 대한 반알고리즘의 근거로 해상도를 사용할 수 있어 괴델의 완전성 정리에서 이어지는 방법보다 더 실용적인 방법을 제공한다.

분해능 규칙은 Davis와 Putnam(1960)^[1]으로 거슬러 올라갈 수 있지만, 그들의 알고리즘은 주어진 공식의 모든 접지 인스턴스를 시도해야 했다. 이 결합 폭발의 원천은 1965년 존 앨런 로빈슨의 구문 통일 알고리즘에 의해 제거되었는데, 이 알고리즘은 반박 완결성을 유지하기 위해 필요한 한 증거 "온디맨드" 중에 공식을 인스턴스화할 수 있게 했다.^[2]

결의규칙에 의해 만들어진 조항을 결의안 규칙이라고 부르기도 한다.

명제논리의 해결

결의 규칙

명제논리의 결의규칙은 상호보완적 문맹을 포함하는 두 절이 내포한 새로운 조항을 생성하는 하나의 유효한 추론 규칙이다. 문자 그대로는 명제 변수 또는 명제 변수의 부정이다. 한 리터가 다른 리터의 부정인 경우 2 리터럴이 보완된다고 한다(다음에서${\displaystyle \mathrm{}}$in ${\displaystyle c}$ ${\displaystyle \lnot c}$을(를$)$ c {\$displaysty c}$의 보완으로 받아들인다$$).$$ 결과 조항은 보완이 없는 모든 리터럴을 포함한다. 공식:

${\displaystyle {\frac {a_{1}\lor a_{2}\lor \cdots \lor \lor b_{1}\lor \cdots \lor \lor \lor \cdots \lor b_{1}\{1}\lor b_{1}\lor b_{cdots}}}}}}}}}}}}}}}lor \cdodots \cdots}}}}}}}}}}}}}}}}}$

어디에

모든 ${\displaystyle i_{}}$ ${\$ ${\displaystyle b_{}}$ i ${\$및 $c{\displaystyle }$ ${\displaystyle c}$은(는) 리터럴이며,

구분선은 "내부"를 나타낸다.

위와 같은 것도 다음과 같이 쓸 수 있다.

${\displaystyle {\frac {(\neg a_{1}\land \neg a_{2}\land \cdots )\rightarrow c,\quad c\rightarrow (b_{1}\lor b_{2}\lor \cdots )}{(\neg a_{1}\land \neg a_{2}\land \cdots )\rightarrow (b_{1}\lor b_{2}\lor \cdots )}}}$

또는 다음과 같이 도식적으로:

${\displaystyle {\frac{1}\cuppled\{\ell \rift\}\\\\\\\\\\\\\\\\\\\cHBFFFFF\}{2}\Gamma _{1}\campa \{1}\campa _{2}\campa \2}}: \ell \el \}}}}}}}}}}}}}$

다음과 같은 용어가 있다.

• $\gamma {\displaystyle {\mathrm{}}_{}}$ $displaystyle \Gamma _{1}\cup$ \$left\{\ell \right\}}$ 및$$ $\gamma {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {2\mathrm{}}_{}{}_{}}$ ${\$은 추론의 전제 조건이다.
• ${\displaystyle {\mathrm{\gamma }}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ∪ ${\displaystyle {2\mathrm{}}_{}}$ 2 ${\$구제의 해결책)이 그 결론이다.
• 리터럴 $\ell {\displaystyle }$ ${\displaystyle \ell$}은$$(는) 좌측 해결 리터럴이며
• 문자 그대로의 ${\$은(는) 오른쪽 해결된 문자 그대로다$$.
• ${\displaystyle \ell }$ $displaystyle \ell}$은(는) 해결된 원자 또는 피벗이다.

결의규칙에서 생산되는 조항을 두 입력절의 해결이라고 한다. 용어보다는 조항에 적용되는 합의 원칙이다.^[3]

두 절이 둘 이상의 보완 리터럴을 포함하는 경우, 각 해당 쌍에 대해 결의 규칙을 (독립적으로) 적용할 수 있다. 그러나 결과는 항상 tautology이다.

모더스 폰은 (1리터 조항과 2리터 조항 중) 해결의 특별한 경우로 볼 수 있다.

${\displaystyle {\frac {p\오른쪽 화살표 q,\put p}{q}}}$

와 같다

${\displaystyle {\frac {\lnot p\lor q,\lor p}{q}}}$

분해능 기법

완전한 검색 알고리즘과 결합하면, 분해능 규칙은 명제 공식의 만족도를 결정하기 위한 건전하고 완전한 알고리즘을 산출하고, 나아가 공리 집합에 따라 문장의 유효성을 결정한다.

이 분해능 기법은 모순에 의한 증거를 사용하며, 명제논리의 어떤 문장이든 접속 정상 형태의 동등한 문장으로 변형될 수 있다는 사실에 기초하고 있다.^[4] 단계는 다음과 같다.

• 지식기반의 모든 문장과 증명할 문장의 부정(추측)은 결막으로 연결되어 있다.
• 결과 문장은 결막은 절의 집합인 S에서 원소로 보는 결막 정상 형태로 변형된다.^[4]
  • For example, ${\displaystyle (A_{1}\lor A_{2})\land (B_{1}\lor B_{2}\lor B_{3})\land (C_{1})}$ gives rise to the set ${\displaystyle S=\{A_{1}\lor A_{2},B_{1}\lor B_{2}\lor B_{3},C_{1}\}}$.
• 결의 규칙은 보완 리터럴을 포함하는 모든 가능한 조항 쌍에 적용된다. 분해능 규칙을 적용할 때마다 반복 리터럴을 제거하여 결과 문장을 단순화한다. 절에 보완 리터럴이 포함되어 있으면 (자동학으로서) 폐기된다. 그렇지 않은 경우, 그리고 아직 S 절에 존재하지 않는 경우 S에 추가되며, 추가적인 해결 추론을 위해 검토된다.
• 결의규칙을 적용한 후 빈 절이 도출되면 원래의 공식은 만족스럽지 못하며(또는 모순됨), 따라서 공리에서 초기 추측이 따른다고 결론 내릴 수 있다.
• 한편, 빈 절은 도출할 수 없고, 결의 규칙을 적용하여 더 이상 새로운 절들을 도출할 수 없다면, 그 추측은 본래의 지식기반의 정리가 아니다.

이 알고리즘의 한 예는 원래의 데이비스-이다.나중에 DPLL 알고리즘으로 정제된 Putnam 알고리즘은 분해제의 명시적 표현 필요성을 제거했다.

분해능 기법에 대한 이 설명은 분해능 유도를 나타내는 기초 데이터 구조로 S를 사용한다. 목록, 나무 및 지시된 반복 그래프는 다른 가능한 공통적인 대안이다. 트리 표현은 해상도 규칙이 이항이라는 사실에 더 충실하다. 절에 대한 연속 표기법과 함께, 나무 표현은 결의 규칙이 원자 절단 포뮬라로 제한되는 절단 규칙의 특별한 경우와 어떻게 관련이 있는지를 명확히 한다. 그러나 나무 표현은 빈 절의 도출에 두 번 이상 사용된 절의 중복 하위 분열을 명시적으로 보여주기 때문에 세트나 목록 표현만큼 압축적이지 않다. 그래프 표현은 목록 표시만큼 절의 수가 압축될 수 있으며 각 분해물을 도출하기 위해 해결된 절에 대한 구조적 정보도 저장한다.

간단한 예

${\displaystyle {\frac {a\vee b,\reght \neg a\ve c}{b\ve c}}$

쉬운 말로: ${\displaystyle a}$이(가) 거짓이라고 가정하십시오. ${\displaystyle \vee }$ ${\displaystyle b}$ ${\displaystyle a\vee b}$ 전제가 참이 되려면$$ $b{\displaystyle }$ ${\displaystyle b}$이 참이어야 한다$$. $또는{\displaystyle }$ ${\displaystyle a}$이(가) 참이라고$$ 가정하십시오. 전제 ${\displaystyle \neg }$ ${\displaystyle c}$ ${\displaystyle \neg a\ve c}$이(가) 참이 되려면$$ $c{\displaystyle }$ ${\displaystyle c}$이(가) 참이어야 한다$$. 따라서 두 전제가 모두 유효하다면$$${\displaystyle a}$의 거짓이나 진실성에 관계없이 결론 b${\displaystyle b}$ c ${\displaystyle b\ve$ c$}$은 $사실$이다.

첫 번째 순서 논리에서의 분해능

분해능 규칙은 다음과 같은 1차 로직으로 일반화할 수 있다.^[5]

${\displaystyle {\frac {\\Gamma _{1}\cup \left\{{}L_{1}\오른쪽\}\,\,\,\,\감마 _{2}\cup \왼쪽\{L_{2}\오른쪽\}{{{{1}\컵 \감마 _{2}}\phi }}}}}$

여기서 $\varphi {\displaystyle }$${\$$displaystyle \pi$}은$$$$(는) L 1{\$displaystyle L_{1},$ ${\displaystyle \stackrel{}{{L\mathrm{}}_{}}}$ $displaystyle {\l_{2$}},$$$\gamma {\displaystyle {\mathrm{}}_{}}$ ${\$ $\Gamma_$${1$} 및 ${\displaystyle {and}_{}}$ $}{\displaystyledata_{2$}}의 가장 일반적인 통일이다.

예

$P{\displaystyle }$( ${\displaystyle x}$)${\displaystyle }$, Q${\displaystyle }$( ${\displaystyle x}$) ${\displaystyle P(x), Q(x)}$ 및$$ $\neg {\displaystyle \mathrm{}}$ ${\displaystyle P}$(${\displaystyle b}$) ${\displaystyle \neg P(b)}$은$({\displaystyle }$는) [${\displaystyle b}$/ x ${\displaystyle ]}$ ${\displaystyle [b/x]$를 결합체로$$ 하여 이 규칙을 적용할 수 있다$$.

여기서 x는 변수, b는 상수다.

${\displaystyle {\frac {P(x),Q(x)\,\,\,\\neg P(b)}{Q(b)}}[b/x]}}}$

자, 이제 알겠다.

• $P{\displaystyle }$( ${\displaystyle x}$)${\displaystyle }$, Q${\displaystyle }$( ${\displaystyle x}$) ${\displaystyle P(x), Q(x)}$ 및$$ $\neg {\displaystyle \mathrm{}}$ ${\displaystyle P}$(${\displaystyle b)}$ ${\displaystyle \neg P(b)}$ 조항은 추론의$$ 전제다.
• ${\displaystyle Q}$( ${\displaystyle b}$) ${\displaystyle Q(b)}($구제의 분해자)가 그 결론이다.
• 리터럴 ${\displaystyle P}$( x${\displaystyle }$) ${\displaystyle P(x)}$은(는) 왼쪽 해결 리터럴이며
• ${\displaystyle \mathrm{리터럴}}{\displaystyle \mathrm{}(}$ ${\displaystyle P}$( b$$) {\$displaystyle \neg P($b)}은(는) 오른쪽 해결된 리터럴이며$$,
• ${\displaystyle P}$ ${\displaystyle P}$은(는) 해결된 원자 또는 피벗이다.
• ${\displaystyle [}$ ${\displaystyle b}$/ ${\displaystyle x}$ ${\displaystyle ]}$ ${\displaystyle [b/x]}$은(는) 해결된 리터럴의 가장 일반적인 유니퍼다.

비공식적 설명

첫째 순서의 논리학에서, 분해능은 논리 추론의 전통적인 삼단논법을 하나의 규칙으로 압축한다.

해상도가 어떻게 작용하는지 이해하려면 용어 논리의 다음 예시 삼단논리를 고려하십시오.

모든 그리스인들은 유럽인이다.

호머는 그리스인이다.

그러므로 호머는 유럽인이다.

또는 보다 일반적으로 다음과 같이 한다.

$\displaystyle \all x.P(x)\오른쪽 화살표 Q(x)}$

$P(a)}$

따라서 $Q{\displaystyle }$(${\displaystyle a}$ ) ${\displaystyle$ Q$(a)}$

분해능 기법을 사용하여 추론을 다시 시작하려면 먼저 절들을 접속 정상 형태(CNF)로 변환해야 한다. 이 형태에서 모든 정량화는 암묵적이 된다: 변수에 대한 범용 정량자(X, Y, ...)는 단순히 이해한 대로 생략되는 반면 실존적으로 정량화된 변수는 스콜렘 함수로 대체된다.

$\displaystyle \neg P(x)\vee Q(x)}$

$P(a)}$

따라서 $Q{\displaystyle }$(${\displaystyle a}$ ) ${\displaystyle$ Q$(a)}$

그렇다면 문제는 해결 기법이 처음 두 개에서 마지막 절을 어떻게 도출하느냐 하는 겁니다. 규칙은 간단하다:

• 동일한 술어가 포함된 두 절을 찾으십시오. 여기서 한 절에서는 부정되지만 다른 절에서는 부정되지 않는다.
• 두 술어에 대해 단일화를 실시한다. (통일이 실패하면 술어를 잘못 선택했다. 이전 단계로 돌아가서 다시 시도하십시오.)
• 두 절의 다른 술어에서도 통일 술어에 바인딩된 바인딩되지 않은 변수가 발생할 경우, 해당 변수들을 바인딩된 값(단어)으로 교체하십시오.
• 통일된 술어를 버리고, 두 절의 나머지 술어를 새로운 절에 결합하고, 또한 "주문" 운영자가 결합한다.

위의 예에 이 규칙을 적용하기 위해, 우리는 조건자 P가 부정된 형태로 발생한다는 것을 발견한다.

¬P(X)

제1절에서, 그리고 부정하지 않은.

P(a)

제2절에서 X는 바인딩되지 않은 변수인 반면, a는 바인딩된 값(항)이다. 둘을 통일하면 치환된다.

X ↦ a

통일 술어를 삭제하고 이 대체를 나머지 술어(이 경우 Q(X)만)에 적용하면 다음과 같은 결론이 나온다.

Q(a)

다른 예로는 삼단논법적 형태를 고려한다.

크레탄은 모두 섬사람이다.

모든 섬사람들은 거짓말쟁이다.

그러므로 크레탄은 모두 거짓말쟁이다.

아니면 더 일반적으로,

∀X P(X) → Q(X)

∀X Q(X) → R(X)

따라서 ∀X P(X) → R(X)

CNF에서 선행조건은 다음과 같이 된다.

¬P(X) ∨ Q(X)

¬Q(Y) ∨ R(Y)

(두 번째 절의 변수는 서로 다른 절의 변수가 구별된다는 점을 명확히 하기 위해 이름을 바꾸었다는 점에 유의하십시오.)

이제 첫 번째 절의 Q(X)와 두 번째 절의 (Q(Y)를 통일한다는 것은 어쨌든 X와 Y가 같은 변수가 된다는 것을 의미한다. 이를 나머지 조항으로 대체하고 결합하면 다음과 같은 결론이 나온다.

¬P(X) ∨ R(X)

팩토링

로빈슨이 정의한 결의안 규칙은 또한 위에서 정의한 결의안 적용 전이나 도중에 동일한 조항에 2리터를 통일하는 팩토링을 통합했다. 결과 추론 규칙은 refution-완전하며,^[6] 팩토링에 의해 강화된 분해능만을 사용하는 빈 절의 파생이 존재하는 경우에만 조항의 집합이 만족스럽지 못하다.

빈 절을 도출하기 위해 팩토링이 필요한 불만족조항의 예는 다음과 같다.

${\displaystyle {\begin{array}{rlcl}(1):&P(u)&\lor &P(f(u)\(2):&\lnot P(v)&\lor &P(w)\\(3):&\lnot P(x)&\lor &\lnot P(f(x))\\end{array}}}$

각 조항은 2리터로 구성되어 있기 때문에, 각 조항은 각각의 가능한 해결책으로 구성되어 있다. 그러므로 인수하지 않고 결의함으로써 빈 절은 결코 얻을 수 없다. 팩토링을 사용하면 다음과 같이 얻을 수 있다.^[7]

${\displaystyle {\begin{array}{rll}(4):&P(u)\lor P(f(w))&{\text{ (1) 및 (2)를 해결하여 }{{{v=f(u)\\(5):&P(w)&{\text}{ 인수인계(4), }u=f(w)\(6):&\lnot P(f(w'))&{\text{{5) 및 (3)을(를) 확인하여 }}w=w',x=f(w')\(7):&{\text{false}}&{\text{value (5) 및 (6)을(를) 사용하여 }{w=f(w')\\\end{array}}}}}$

비클러스터 결의

상기 결의안 규칙의 일반화는 원래 공식이 폐쇄 정상적인 형태일 필요가 없는 것으로 고안되었다.^{[8][9][10][11][12][13]}

이러한 기법은 주로 중간 결과 공식의 인간의 가독성을 보존하는 것이 중요한 곳을 입증하는 대화형 정리에서 유용하다. 게다가, 그들은 절 형태로 변환하는 동안 결합 폭발을 피하고,^{[10]: 98} 때때로 해결 단계를 저장한다.^{[13]: 425}

명제논리의 비클러스터 결의안

명제적 논리를 위해 머레이와^{[9]: 18} 마나, 월딩거는^{[10]: 98} 이 규칙을 사용한다.

${\$$;\;\;\;\;\;\;\;\;\;$$G[p]\\\hline F[{\textit {true}]\lor G[{\textit {false}]\\end{array$

여기서 $p{\displaystyle }$ ${\displaystyle p}$은 임의의 공식, F [$p{\displaystyle }$ ${\displaystyle ]}$${\displaystyle$ $F$$[p]$는 $보조공식$으로서 p ${\displaystyle$ p$}$을(를) 포함하는 공식을 의미하며$$, ${\displaystyle$ $F$$[{\textit {true}]$는 $p$가 발생할 때마다$$ F${\displaystyle [}p{\displaystyle }$$]$로${\displaystyle }$대체하여 $구축$된다. ${\displaystyle {\textit {true}}}$; likewise for ${\displaystyle G}$. The resolvent ${\displaystyle F[{\textit {true}}]\lor G[{\textit {false}}]}$ is intended to be simplified using rules like ${\displaystyle q\land {\textit {true}}\implies q}$, etc. 쓸모없는 사소한 해결책이 발생하지 않도록 하기 위해, $p{\displaystyle }$ ${\displaystyle p}$에 $각각{\displaystyle }$$$F ${\\displaystyle F}$과 $G{\displaystyle }$ ${\displaystyle G}$에서 "부정"과 "양"^[14] 발생이 하나 이상 있을$$ 때만 규칙을 적용해야 한다. 머레이는 이 규칙이 적절한 논리 변환 규칙에 의해 강화되면 완성된다는 것을 보여주었다.^{[10]: 103}

트라우고트는 규칙을 사용한다.

$F$$G[p]\\\hline F[{\textit {true}],\lnot G[{\textit {false}]$$\\end{array$

$여기$서 p ${\displaystyle p}$의 지수는 발생 극성을 나타낸다$$. While ${\displaystyle G[{\textit {true}}]}$ and ${\displaystyle G[{\textit {false}}]}$ are built as before, the formula ${\displaystyle F[G[{\textit {true}}],\lnot G[{\textit {false}}]]}$ is obtained by replacing each positive and each negative occurrence of ${\displaystyle }$$p{\displaystyle }$ ${\displaystyle F}$에서 ${\displaystyle \mathit{\text{G}}}$[true ] {\$displaystyle$ G$[{\textit {true}]}$과(와${\displaystyle )}$ 각각 [${\displaystyle \mathit{\text{false}}}$ ${\displaystyle ]}$ ${\displaystyle G[{\textit {false}]]$와$($각각각각각)가 있는 p {\$displaystystystyleasestyp$. 머레이의 접근방식과 유사하게, 변환을 적절히 단순화하는 것이 해결책에 적용되어야 한다. 트라우엇은 그의 규칙이 완전하다는 것을 증명했다. 단, $\wedge {\displaystyle }$,${\displaystyle \to }$ , →${\displaystyle \mathrm{\neg }}$ ${\displaystyle \land ,\lor ,\rightarrow ,\lnot }$은 공식에 사용되는 유일한 연결고리들이다.^{[12]: 398–400}

트라우고트의 분해능은 머레이보다 강하다.^{[12]: 395} 더욱이 새로운 2진법 정위법을 도입하지 않기 때문에 반복적인 분해능에서 폐쇄적인 형태를 지향하는 경향을 피한다. 그러나 작은 $p{\displaystyle }$ ${\displaystyle p}$을(를) 큰 $G{\displaystyle }$[${\displaystyle \mathit{\text{참}}}$ ${\displaystyle ]}$ ${\displaystyle G[{\textit {true}]$ 및$$/또는 $G{\displaystyle }$[${\displaystyle \mathit{\text{거짓}}}$ ${\displaystyle ]}$ ${\displaysty$ G$[{\textit {false}}]$로 여러 번 교체하면$$ 수식이 더 길어질 수 있다$.$^{[12]: 398}

제안 비클러스터 결의안 예

예를 들어, 사용자가 제공한 가정부터 시작

${\displaystyle {\buff}{rccc}(1):&a&\오른쪽 화살표 &b\land c\\(2):&c&\오른쪽 화살표 &d\\(3):&b\land d&\오른쪽 화살표 &e\(4):&b&\land d&\오른쪽 화살표 &e\(4):&\lnot (a&\rightarrow &e)\\\end{array}}$

머레이 규칙은 모순을 유추하기 위해 다음과 같이 사용될 수 있다.^[15]

${\displaystyle{\begin{배열}(5):&({\textit{}진정한}\rightarrow d)&, \lor&(a\rightarrow b\land{\textit{}거짓})&, \implies &, d\lor \lnot a&,{(2)과(1){,으로부터 \mbox}}p=c\\(6):&(b\land{\textit{}진정한}\rightarrow e)&, \lor&({\textit{}}거짓 \lor \lnot)&, \implies &,(b\rightarrow e)\lor\lnot a&.;{(3)과(5){,으로부터 \mbox}}p=d\\(7):&(({\t.Extit{진정한}}\rightarrow e)\lor \lnot a)&\lor&(a\rightarrow{\textit{거짓}}\land c)&, \implies &, e\lor\lnot a\lor \lnot a&,{(6)과(1){,으로부터 \mbox}}p=b\\(8):&(e\lor \lnot{\textit{}진정한}\lor\lnot{\textit{}진정한})&, \lor&\lnot({\textit{}거짓}\rightarrow e)&, \implies &, e&,(7)과(4)에서{\mbox{, w.ith}}p=a\\(9):&\lnot(a\rightarrow {\textit {true})&\lor &}{\textit {false}&#\false}&{\mbox{from (4) 및 (8) }}}{{p=e\\end\array}}}}}}$

같은 목적으로 트라우엇 규칙을 다음과 같이 사용할 수 있다.^{[12]: 397}

${\displaystyle{\begin{배열}(10):&a\rightarrow b\land({\textit{}진정한}\rightarrow d)&, \implies &, a\rightarrow b\land 기운,{(1)과(2){,으로부터 \mbox}}p=c\\(11):&a\rightarrow({\textit{}진정한}\rightarrow e)&, \implies &, a\rightarrow e&,{(10)과(3){,으로부터 \mbox}}p=(b\land d)\\(12):&\lnot{\textit{사실}}.&\implies &,{\textit{거짓}}&,{\mbox{(11) 및 (4)부터 }p=(a\오른쪽 화살표 e)\\\end{array}}}}$

두 가지 공제를 비교해 보면 다음과 같은 문제를 알 수 있다.

• 트라우고트의 규칙은 더 날카로운 해결책이 될 수 있다: 비교 (5)와 (10) 둘 다 $p{\displaystyle }$= c ${\displaystyle p=c}$에서 (1)과 (2)를 해결한다$.$
• 머레이의 규칙은 (5), (6), (7)의 세 가지 새로운 절연 기호를 도입했고 트라우고트의 규칙은 새로운 기호를 도입하지 않았다. 이런 점에서 트라우고트의 중간 공식은 머레이의 공식보다 사용자의 스타일을 더 가깝게 닮았다.
• 후자 문제로 인해 트라우엇의 규칙은 (4) 가정에서의 함축적$$$$ $함축적{\displaystyle }$ 함축적 함축적 함축적 함축적 함축적 함축적 함축적 함축적 함축적 함축적 함축적 함축적 함축적 함축적 함축적 함축적 함축적 함축적 함축적 함축적($p {\\\\\displaystytytytytytyp)$ 머레이의 규칙을 사용하여 의미론적으로 동등한 공식 $e{\displaystyle \mathrm{\vee }}$ ${\displaystyle a}$ ${\displaystyle \vee }$ a ${\displaystyle \mathrm{\vee }}$ a ${$ ${\displaystyle a}$ {\$displaystyle e\lor \lot a}$을(를) (7)로 얻었으나, 통사적 형태 때문에$$ p ${\displaystyle$ p$}$로 $사용$할 수 없었다.

1차 논리에서의 비클러스터 분해능

1차 술어 논리의 경우, Murray의 규칙은 일반화되어 각각$$${\displaystyle {F\mathrm{}}_{}}$ ${\displaystyle$ $p_{1$}와$$$$ $P{\displaystyle }$2 {\$displaystyle$$p_{$2}}의 구별되지만 식별이 불가능한 보조공식 $p{\displaystyle {}_{}}$ ${\$ p_${$1}를 허용한다$.$ If ${\displaystyle \phi }$ is the most general unifier of ${\displaystyle p_{1}}$ and ${\displaystyle p_{2}}$, then the generalized resolvent is ${\displaystyle F\phi [{\textit {true}}]\lor G\phi [{\textit {false}}]}$. While the rule remains sound if a more special substitution $\varphi {\displaystyle }$ ${\displaystyle \phi }$이(가) 사용되며$$, 완전성을 달성하기 위해 이러한 규칙 애플리케이션이 필요하지 않다.^{[citation needed]}

Traugott's rule is generalized to allow several pairwise distinct subformulas ${\displaystyle p_{1},\ldots ,p_{m}}$ of ${\displaystyle F}$ and ${\displaystyle p_{m+1},\ldots ,p_{n}}$ of ${\displaystyle G}$, as long as ${\displaystyle p_{1},\ldots$$,p_{n}}}$은(는) $일반적$인 가장 일반적인 통일체를 가지고$$ 있는데,$$say ${\displaystyle \pi }.$ 일반화된 분해능은 상위 공식에$$ $\varphi {\displaystyle }$ ${\displaystyle \pi }$를 적용한 후 얻으므로 제안 버전을 적용할 수 있다. 트라우고트의 완전성 증명은 이 완전한 일반 규칙이 사용된다는 가정에 의존한다;^{[12]: 401} 그의 규칙이 ${\displaystyle {p\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$= ${\displaystyle \cdots }$= p m = ${\displaystyle {}_{}}$ ${\displaystyle m_{}}$ = p m ${\$= ${m+1},$ p ${\displaystyle m_{}}$+ 1${\displaystyle }$=${\displaystyle p_{}}$ ${\$^[16]로 제한된다면 완전한 규칙이 유지될지는 명확하지 않다.

파라모듈레이션

파라모듈레이션은 술어 기호가 평등인 절들의 집합에 대한 추론을 위한 관련 기법이다. 그것은 반사적 정체성을 제외한 모든 "평등한" 버전의 조항들을 생성한다. 매개변수 연산에는 양수 절이 포함되어야 하며, 이 절은 동등 리터럴을 포함해야 한다. 그런 다음 평등의 한 쪽과 통합되는 하위 용어를 포함하는 조항을 검색한다. 그런 다음 하위 용어는 평등의 다른 면으로 대체된다. 파라모듈레이션의 일반적인 목적은 시스템을 원자로 줄여 대체 시 용어의 크기를 줄이는 것이다.^[17]

구현

• 캐린
• GKC
• 수달
• 프로베라9
• 스나크
• 스파스
• 뱀파이어
• Logictools 온라인 프로베롤

참고 항목

• 축약된 분리 - 분해능의 이전 버전
• 유도 논리 프로그래밍
• 역분해능
• 논리 프로그래밍
• 분석표기법
• SLD 분해능
• 결의추론

메모들

참조

• Robinson, J. Alan (1965). "A Machine-Oriented Logic Based on the Resolution Principle". Journal of the ACM. 12 (1): 23–41. doi:10.1145/321250.321253.
• Leitsch, Alexander (1997). The Resolution Calculus. Springer.
• Gallier, Jean H. (1986). Logic for Computer Science: Foundations of Automatic Theorem Proving. Harper & Row Publishers.
• Lee, Chin-Liang Chang, Richard Char-Tung (1987). Symbolic logic and mechanical theorem proving ([reprint] ed.). San Diego: Academic Press. ISBN 0-12-170350-9.

외부 링크

• Alex Sakharov. "Resolution Principle". MathWorld.
• Alex Sakharov. "Resolution". MathWorld.