導出

英

lead

関

通じる、導く、リード、主導

WordNet

1. tend to or result in; "This remark lead to further arguments among the guests"
2. a soft heavy toxic malleable metallic element; bluish white when freshly cut but tarnishes readily to dull grey; "the children were playing with lead soldiers" (同)Pb, atomic number 82
3. (sports) the score by which a team or individual is winning
4. the angle between the direction a gun is aimed and the position of a moving target (correcting for the flight time of the missile)
5. thin strip of metal used to separate lines of type in printing (同)leading
6. mixture of graphite with clay in different degrees of hardness; the marking substance in a pencil (同)pencil lead
7. a position of leadership (especially in the phrase `take the lead'
8. an advantage held by a competitor in a race; "he took the lead at the last turn"
9. the playing of a card to start a trick in bridge; "the lead was in the dummy"
10. a news story of major importance (同)lead story
11. the introductory section of a story; "it was an amusing lead-in to a very serious matter" (同)lead-in, lede
12. evidence pointing to a possible solution; "the police are following a promising lead"; "the trail led straight to the perpetrator" (同)track, trail
13. (baseball) the position taken by a base runner preparing to advance to the next base; "he took a long lead off first"
14. travel in front of; go in advance of others; "The procession was headed by John" (同)head
15. take somebody somewhere; "We lead him to our chief"; "can you take me to the main entrance?"; "He conducted us to the palace" (同)take, direct, conduct, guide
16. be ahead of others; be the first; "she topped her class every year" (同)top
17. cause to undertake a certain action; "Her greed led her to forge the checks"

PrepTutorEJDIC

1. 《方向を表す副詞[句]を伴って》…‘を'『導く』,案内する / 〈道・灯火などが〉…‘に'道筋を示す;(…へ)…‘を'導く《+『名』+『to』(『into』)+『名』》 / …‘の'先頭になる,1番である / …‘の'『率いる』,指揮する / 〈ある人生・生活〉‘を'経験する,生きる,送る / 『先頭に立つ』,(競技・成績などで)リードスル / 〈人が〉『案内する』,先導する / (…に)〈道などが〉『通じている』《+『to』+『名』》 / (…の)結果となる《+『to』+『名』(do『ing』)》 / 〈U〉《the~》『先頭』,首位 / 〈C〉《a~》相手を引き離した点(時間,距離) / 〈C〉模範,手本(example) / 〈C〉(問題解決の)手がかり,ヒント(clue) / 〈C〉(劇・映画などの)主役,主演俳優 / 〈C〉(新聞報道記事などの本文の前におく要約した)前文,前書き,リード / 先頭の,主要な
2. 〈U〉『鉛』(化学記号はは『pb』) / 〈C〉鉛のおもり,測鉛 / 〈C〉《複数形で》(ガラスをはめる)鉛の枠(わく);《英》(屋根をふくのに用いる)鉛板 / 〈U〉〈C〉黒鉛,鉛筆のしん / 〈U〉《集合的に》(鉛の)弾丸 / …‘に'鉛をかぶせる,鉛を詰める,鉛のおもりを付ける

Wikipedia preview

出典(authority):フリー百科事典『ウィキペディア（Wikipedia）』「2016/08/08 06:37:34」(JST)

wiki ja

[Wiki ja表示]

導出原理（どうしゅつげんり、英: resolution principle）とは、ジョン・アラン・ロビンソンにより1965年に提案された原理または手法を言う。

導出原理を元とする導出の手法は、その後の定理自動証明に大きな影響を与え、またPrologなどの論理プログラミング言語の基礎となった。

背景

述語論理式 P が恒真であるかを証明する一般的な手続きは存在しないが、1930年に発表されたエルブランの定理はエルブラン領域の要素を論理式に代入して命題論理のレベルに落としその充足不能性を調べることで、¬P が充足不能（恒偽）であれば有限のステップで証明できることを保証している。また、エルブランの論文には単一化アルゴリズムなど他の様々なものが含まれていた。

1950年代以降、計算機上での定理証明の研究が活発になり、ギルモアのアルゴリズム(1960)やデービス・パトナムのアルゴリズム(1958,1960) が考案された。デービス・パトナムのアルゴリズムには連言標準形の使用や導出規則の考え方が含まれていた。しかし、これらはエルブランの定理の証明を直接計算機上で実現したような方法で、エルブラン領域の要素を順次生成して変数を含まない論理式(基礎例)を作成し命題論理のレベルで充足不能性を調べるものだったため、不要な論理式が多数生成され、非常に効率が悪かった。

プラウィツ（Dag Prawitz）は、論理式を生成してからチェックするのではなく、選言標準形に変換した論理式への適当な代入（単一化）によって充足不能性を調べる方法を1960年に提案した。 この方法は必要な基礎例のみを生成するため、不要な論理式の生成が抑えられ効率的だったが、選言標準形は全ての連言項を調べなければならないため全体の効率はいいとは言えなかった。

ロビンソンはデービス・パトナムの枠組みにプラウィツのアイデアを組み合わせ、ただ1つの導出規則と単一化による代入操作とで充足不能性を調べる導出原理を1965年に発表した。単純な規則で関係する論理式のみを段階的に具体化していく方法は、従来の方法よりはるかに効率がよく、また理論的なエレガントさを持っていたため、その後の定理自動証明に大きな影響を与えた。

定義

導出とは二つの節より新しい節を導き出す操作で、一方の節に含まれるリテラル $l$ と、他方の節に含まれる否定リテラル $\neg l$ をのぞき、その他のリテラルの論理和をとることで、新しい節を得ることをいう。

命題論理での導出規則を式で表せば、 ${\frac {l\vee P,\quad \neg l\vee Q}{P\vee Q}}$ と書ける。ここで上式は前提となる親節、下式はそれらから導かれる導出節（resolvent）を表す。

あるいは、別の表記法を用いて次のようにも表現できる。前提となる節を $C_{1}$ と $C_{2}$ とし, もしリテラル $L\in C_{1}$ と否定リテラル ${\overline {L}}\in C_{2}$ が存在するならば、導出節 $C_{R}$ は以下のようになる。

$C_{R}=(C_{1}\setminus \{L\})\cup (C_{2}\setminus \{{\overline {L}}\})$

導出規則は三段論法や前件肯定を一般化した規則となっている。 導出は完全な証明系であることが知られている。

例

$p\to q$ を節形式にすると $\lnot p\lor q$ となる。$C_{R}$ を$C_{1},C_{2}$ の導出節とすると、前件肯定は以下の導出と同じである。

${\begin{array}{ll}C_{1}=\lnot p\lor q&\left(p\to q\right)\\C_{2}=p\\C_{R}=q&\left(\mathrm {resolvent} \right)\end{array}}$

同様に、$p\to q$、$q\to r$ の節形式 $\lnot p\lor q$、 $\lnot q\lor r$ による三段論法は以下のようになる。

${\begin{array}{ll}C_{1}=\lnot p\lor q&\left(p\to q\right)\\C_{2}=\lnot q\lor r&\left(q\to r\right)\\C_{R}=\lnot p\lor r&\left(\mathrm {resolvent,\ } p\to r\right)\end{array}}$

一階述語論理での導出

述語論理のリテラルには個体変数が含まれるため、リテラルと否定リテラルとを単純に比較するだけでは削除できるかどうか分からない。一階述語論理ではリテラルと否定リテラルそれぞれの原子論理式が単一化できる場合に導出を行う。

また、導出の対象となる節は、冠頭標準形にして存在記号を削除したスコーレム連言標準形の論理式である。

例えば、一方の節がリテラル $p(x,y)$、もう一方の節がリテラル $\lnot p(z,f(b))$ を含む場合、適切な代入 $\sigma =\left\{z/x,y/f(b)\right\}$ により各リテラルは $p(x,f(b))$、 $\lnot p(x,f(b))$ と書き換えられ、同じにすることができる。ここで代入 $\left\{z/x,y/f(b)\right\}$ は $z\to x$、$y\to f(b)$ に書き換えることを表す。

一般に論理式 $F_{1},F_{2}$ を等しくする代入を $F_{1},F_{2}$ の単一化子（unifier）といい、そのうち最も一般的な単一化子（最汎単一化子）を $F_{1},F_{2}$ のmgu（most general unifier）という。上記の例の場合、両方の論理式を等しくする代入は $\left\{z/a,y/f(b),x/a\right\}$、$\left\{z/x,y/c,f(b)/c\right\}$ など無数に存在する。これらは本来の代入 $\left\{z/x,y/f(b)\right\}$ に $\left\{x/a\right\}$ などの代入を合成したものなので、最汎単一化子 mgu は $\left\{z/x,y/f(b)\right\}$ である。

一階述語論理での導出は mgu を用いて次のように表現できる。

もしリテラル $L_{1}\in C_{1}$ と否定リテラル ${\overline {L_{2}}}\in C_{2}$ が存在し、 $L_{1}$ と $L_{2}$ が mgu $\sigma$ を持つ場合、以下の $C_{R}$ が2項導出節（binary resolvent）である。ここで、$C_{1}\sigma ,C_{2}\sigma$ などは、それぞれの節やリテラルに代入 $\sigma$ を行ったものを表す。

$C_{R}=(C_{1}\sigma \setminus \{L_{1}\sigma \})\cup (C_{2}\sigma \setminus \{{\overline {L_{2}\sigma }}\})$

同様のやり方での2以上の複数の節から同時に導出することも可能であり、超導出（hyper-resolution）と呼ばれる。

例

以下の節からの導出を考える。

$C_{1}=\lnot P(x)\lor \lnot Q(y)\lor R(x,y)$

$C_{2}=Q\left(a\right)$

$C_{3}=P\left(b\right)$

Q を単一化する代入 $\left\{y/a\right\}$ により $C_{1}$ と $C_{2}$の導出を行うと、

$C_{R}=\lnot P(x)\lor R(x,a)$

続いて、P を単一化する代入 $\left\{x/b\right\}$ により $C_{R}$ と $C_{3}$の導出を行うと、

$C_{S}=R\left(b,a\right)$

を得ることができる。

反駁による証明

反駁（はんばく、英: refutation）とは、節の集合からの導出により空節 □ を導くことである。 反駁については以下の定理が成り立つ。

節の集合 S が充足不能である必要十分条件は、節の集合 S からの導出により空節 □ が導けることである。

これはエルブランの定理を導出に応用したものになっている。

論理式 P が恒真であれば $\lnot P$ は充足不能（恒偽）であるため、節の集合に $\lnot P$ を追加し導出を繰り返すことで空節 □ になれば、論理式 P が恒真であることが証明できる。

反駁により $P$ が $P_{1},\dots ,P_{n}$ の論理的帰結か調べるアルゴリズムは以下のように表現できる。

1. $P_{1},\dots ,P_{n}$ をスコーレム連言標準形 $C_{1},\dots ,C_{n}$ に変換する。
2. $\lnot P$ をスコーレム連言標準形 $C$ に変換する。
3. もし $C,C_{1},\dots ,C_{n}$ の反駁が存在すれば、 $P$ は $P_{1},\dots ,P_{n}$ の論理的帰結である。

あるいは、別の表現をすれば、

• $C,C_{1},\dots ,C_{n}$ が充足不能
• $\lnot P,P_{1},\dots ,P_{n}$ が充足不能
• $P_{1},\dots ,P_{n}$ の解釈が ${\mathit {T}}$ ならば $\lnot P$ の解釈は ${\mathit {F}}$
• $P_{1},\dots ,P_{n}$ の解釈が ${\mathit {T}}$ ならば $P$ の解釈は ${\mathit {T}}$

例

以下の公式が成り立つ時、$P\left(a\right)$ が成り立つかどうかを証明する場合を考える。反駁の対象となる論理式は以下の論理式に $\lnot P(a)$ を追加したものである。

1. $\forall x\ ((S(x)\lor T(x))\to P(x))$,
2. $\forall x\ (S(x)\lor R(x))$,
3. $\lnot R(a)$

最初の論理式は $(\forall x\ (S(x)\to P(x))\land (\forall x\ (T(x)\to P(x))$ と等価なため、次の2つの節で表現できる。

$C_{1}=\lnot S(x)\lor P(x)$

$C_{2}=\lnot T(x)\lor P(x)$

2番目の論理式は以下の節になる。

$C_{3}=S(x)\lor R(x)$

さらに3番目は以下の節になる。

$C_{4}=\lnot R(a)$

証明したい論理式の否定は以下の節である。

$C_{5}=\lnot P(a)$

これらの節 ${C_{1},C_{2},C_{3},C_{4},C_{5}}$ が反駁の対象となる節集合である。

$C_{3}$ と $C_{4}$ の $R$ についての導出を考えると、$\left\{x/a\right\}$ の代入により以下が導かれる。

$C_{6}=S\left(a\right)$

$C_{1}$ と $C_{6}$ の $S$ についての導出を考えると、

$C_{7}=P\left(a\right)$

最後に $C_{5}$ と $C_{7}$ の導出により空節 □ が導かれ、$P\left(a\right)$ が成り立つことを証明できる。

証明戦略

導出は２つの節を前提として導出節を導くものであるので、どの節に導出規則を適用するかについては様々な選択肢があり、そのやり方により効率が大幅に異なる。代表的な証明戦略として以下のものがある。

• 線形導出（linear resolution）

前提となる節の一方を、頂上節（top clause）として指定した節と、頂上節から導出された節に限定する方法。導出木を書くと導出の流れが線状に一列に並ぶため、線形導出と呼ばれる。論理プログラミング言語の代表であるPrologで用いられるSLD導出（Selective Linear resolution for Definite clause）は線形導出の一種である。

• 入力導出（input resolution）

前提となる節の一方を最初に与えられた節集合の要素（導出された節以外の節）に限定する方法。

• 支持集合戦略（set-of-support strategy）

あらかじめ支持集合という節の集合を指定しておき、前提となる節の一方を支持集合の節とそこから導出された節に限定する方法。節集合S、T がありS-T が充足可能であるときT はS の支持集合と言う。目標に関係ないところを探索しないよう導出の対象を制限することで、より効率的な導出を行うための手法で、1965年に Lawrence Wos らが提案した。

• 意味導出（semantic resolution）

論理式のモデルあるいは解釈を利用して導出の対象を制限し、探索の空間を狭めることで効率的な導出を行う手法。特定のモデルにおいて真となる可能性がある節と偽となる可能性のある節とを親節に選ぶ Slagle の Semantic Clash resolution など様々な方法がある。

脚注

関連項目

• 数理論理学
  • 命題論理
  • 述語論理

• 自動定理証明
• 論理プログラミング
• エルブランの定理
  • ギルモアのアルゴリズム
  • デービス・パトナムのアルゴリズム
  • DPLLアルゴリズム

参考文献

• 長尾 真、淵 一博 『論理と意味』7、岩波書店〈岩波講座 情報科学〉、1983年。
• 山崎 進 『計算論理に基づく推論ソフトウェア論』 コロナ社、2000年。
• D.ヒルベルト、W.アッケルマン 『記号論理学の基礎』 伊藤誠（訳）、大阪教育図書社、1954年。
• Robert Kowalski (1974), Predicate Logic as Programming Language, http://www.doc.ic.ac.uk/~rak/papers/IFIP%2074.pdf 
• Wolfgang Bibel (2007), “Early History and Perspectives of Automated Deduction”, Advances in Artificial Intelligence, Lecture Notes in Computer Science, Springer-Verlag Berlin, ISBN 9783540745648, http://www.intellektik.de/resources/OsnabrueckBuchfassung.pdf 
• J. Alan Robinson. "A Machine-Oriented Logic Based on the Resolution Principle." J. Assoc. Comput. Mach. 12, pp.23-41, 1965.
• Davis Martin. The Early History of Automated Deduction. in Handbook of Automated Reasoning, Volume I, Alan Robinson and Andrei Voronkov(ed), 2001. ISBN 9780444829498.
• Robert Kowalski. Logic for Problem Solving. North Holland, Elsevier, 1979.　ISBN 978-0444003683
• Gallier, Jean H. (1986). Logic for Computer Science: Foundations of Automatic Theorem Proving. Harper & Row Publishers. http://www.cis.upenn.edu/~jean/gbooks/logic.html. 
• 佐藤 泰介. 導出原理による定理証明. 情報処理 22(11), pp.1024-1036, 1981.

外部リンク

• Alex Sakharov, "Resolution Principle" - MathWorld.（英語）
• Alex Sakharov, "Resolution" - MathWorld.（英語）
• Notes on computability and resolution (pdf)
• 述語論理とその意味論 (pdf) 筑波大学講義資料

UpToDate Contents

全文を閲覧するには購読必要です。 To read the full text you will need to subscribe.

• 1. 高ナトリウム血症の治療 treatment of hypernatremia
• 2. Polysomnography in the evaluation of parasomnias and epilepsy
• 3. 脾辺縁帯リンパ腫の臨床症状、病理学的特徴、および診断 clinical manifestations pathologic features and diagnosis of splenic marginal zone lymphoma
• 4. 成人における市中肺炎：リスクの層別化と入院の決定 community acquired pneumonia in adults risk stratification and the decision to admit
• 5. 組織球性肉腫 histiocytic sarcoma

Japanese Journal

• 日本語疑問文の応答の冒頭に現れる「は」について : 係助詞から感動詞へ

• 有田 節子
• 国立国語研究所論集 9, 1-22, 2015-07
• … 裸のハの分布上の特徴を係助詞ハと疑問文の意味から導出し,さらに,裸のハが係助詞から感動詞への変化の途上にあることを示す。 …
• NAID 110009920469

• 並列構造解析に向けた依存構造解析アルゴリズムの拡張

• 吉本 暁文,新保 仁,原 一夫,松本 裕治
• 情報処理学会研究報告. SLP, 音声言語情報処理 2015-SLP-106(5), 1-6, 2015-05-18
• … 一般的に依存構造解析のアルゴリズムでは,句構造を扱わないために並列構造を考慮することが難しい.そこで,依存構造解析のための Eisner アルゴリズムを,並列構造解析ができるように拡張した.その規則の導出木は,既存の依存構造のアノテーションから導出することができる. …
• NAID 110009899875

• 水生生物の保全に係る環境基準値の基本的な考え方と導出法 : ノニルフェノールを事例として (特集 水質汚濁に係る環境基準などの設定経緯)

• 林 岳彦
• 水環境学会誌 38(5), 173-177, 2015-05
• NAID 40020477453

Related Links

• 「導出」 製薬業界の専門用語 ：日本経済新聞

「製薬ベンチャーのA社は、抗アレルギー薬の開発権をB社に導出する決定をした」――。こんなニュースを聞くことがありますが、「導出」はなじみが薄い言葉でしょう。ここでは、どんな意味で使われているのかご存

• どうしゅつ【導出】の意味 - 国語辞書 - goo辞書

どうしゅつ【導出】とは。意味や解説、類語。[名](スル)みちびきだすこと。特に、論理的に結論をひきだすこと。「新しい理論から―された方法」 - goo国語辞書は27万語以上を収録。政治・経済・医学・ITなど、最新用語の追加も ...

Related Pictures

---

★リンクテーブル★

リンク元	「導く」「主導」「通じる」「リード」
拡張検索	「導出静脈」「後頭導出静脈」

「導く」

　　[★]

英

guide、lead、bring、steer

関

案内、ガイド、指導、先導、通じる、連れていく、運ぶ、もたらす、リード、導出、主導

「主導」

　　[★]

英

initiative、lead、initiative

関

通じる、導く、リード、導出、発議、イニシアチブ、イニシアティブ

「通じる」

　　[★]

英

(道が)lead、(話が)communicate

関

情報交換、伝える、導く、リード、連絡、導出、通信、主導

「リード」

　　[★]

英

lead、lead

関

通じる、導く、導出、主導

「導出静脈」

　　[★]

英

emissary veins

ラ

venae emissariae

「後頭導出静脈」

　　[★]

英

occipital emissary vein