命題論理 (Propositional Logic)

Presentation on theme: "命題論理 (Propositional Logic)"— Presentation transcript:

1 命題論理 (Propositional Logic)
認知システム論　知識と推論（１） 知識と論理で問題を解決する 命題論理 (Propositional Logic) 　なぜ人工知能で論理を学ぶのか 　いろいろな論理と推論方式 　例題　魔宮の世界 　命題論理（構文論と意味論） 　今回からは「知識と推論」と題し，エージェントがタスクをこなすために必要な実世界に関する知識をコンピュータ内で知識ベースとして表現し，それらの知識を論理的な方法によって組み合わせる推論技術によって新しい知識を演繹（えんえき）的に導き出し，エージェントの問題解決や意志決定に役立てる技術を学ぶ． 　特に今回の授業では「命題論理」と呼ばれる古典的な論理を学ぶ．その前に，なぜ，人工知能で論理を学ぶのかを説明しておく．

2 論理 なぜ人工知能で論理を学ぶのか(1/2) 探索による問題解決 初期状態 オペレータ（行為） 行為 ゴール検査 経路コスト
状態 や 行為の結果（状態遷移） をどのように記述したら良いか？ 　これまで学んできた「探索」による問題解決手法では，問題を 　　　初期状態 　　　オペレータ（行為） 　　　ゴール検査 　　　経路コスト の４つの情報で規定し，おもに探索アルゴリズムの性能を議論してきた． 　しかし，ここでは，「状態」や 「行為の結果（状態遷移）」をどのように記述したら良いか，という問題が置き去りにされている．探索アルゴリズムにおいては，状態とは抽象的なものであり，たとえば，整数によって表現された一連番号であってもかまわないし，また，それ以上のことを必要ともしていない． 　しかし，複雑な問題領域においては，探索アルゴリズム以前の問題として，解決すべき問題を探索問題として定式化すること自体が困難である．たとえば，状態の表現をどのようにすれば良いのだろうか？　また，行為の結果をどのように算出したら良いのだろうか？　明らかに，「状態」と「行為の結果」（状態遷移）を適切に記述するための一般的な方法が必要である．その基盤となるのが，「論理」の一般的な考え方とそれを扱う技術である． 論理

3 なぜ 人工知能 で 論理 (LOGIC)を学ぶのか．
なぜ人工知能で論理を学ぶのか(2/2) なぜ 人工知能 で 論理 (LOGIC)を学ぶのか． 知識表現言語としての論理　⇒　構文論，意味論 推論アルゴリズムとしての論理　 ⇒　推論規則 追加的な 知識 知識ベース 背景知識 知識 推論 アルゴリズム (= LOGIC) TELL 知識 ASK／ANSWER 　人工知能における「論理」の役割を説明しておく． 　一般に，人間がコンピュータに情報を与える「言語」といえば，すぐプログラミング言語が思いつく．それはコンピュータへの命令の列すなわちプログラムを具体的に記述したものである．しかし，そもそもAIの究極的な目的の１つは，そのようにいちいち命令しなくても，ふつうの言葉で意図を伝えれば，自動的に適切な命令を組み立てて実行してくれる知的な情報システムを目指しているのである．そのようなAIシステムでは，コンピュータと人間が日本語や英語などの自然言語で対話することを理想としている．その言語は必ずしもコンピュータへの命令を表したものではなく，AIシステムに何らかの知識を与えたり，解いて欲しい問題を与えたりするために使われる．AIシステムは獲得した知識を知識ベースと呼ばれる一種のデータベースに蓄える． 　ただ，残念ながら，コンピュータが自然言語を理解するという技術はまだ開発の途上にあり，現状ではそれをじゅうぶんに利用することはできない．そこで何らかの人工的な言語で，しかもプログラミング言語ではなく，知識を与えたり，問題を記述したり，質問したりするための知識表現言語と呼ばれる類の言語が必要となる．そのようなもののうちで，現在，最も中心的な役割を果たしているのが，論理に基づく言語なのである．つまり，ここでは論理とは言語のことである．したがって，それを理解するには，他のいろいろな言語を理解するのと同様に，正しい文を生成するための文法規則（構文論）や与えられた文を解釈する規則（意味論）を理解する必要がある．つまり，知識や問題を表現するという静的な側面が，AIにおける論理の第一の役割である． 　AIにおける論理の第二の役割は動的なものである．AIシステムは，与えられた知識ベース内の複数の知識を使って，新しい知識を動的に生成する機能が求められる．その機能を推論という．コンピュータに推論を行わせるアルゴリズムは，推論規則と呼ばれる論理的な規則に基づいている．したがって，ここでは論理とは推論アルゴリズムという計算手順を作り出すものとして働くことになる． 知識 知識表現言語 (=LOGIC) 　　　　　 推論された知識

4 いろいろな論理と推論方式(1/2) 完全な知識に基づく数学的な推論 命題論理：命題の真偽を１つの記号で表現
述語論理：オブジェクト間の「主語-述語-目的語」の 　　　　　　　　関係を表現 様相論理：必然性や可能性を表現(must, can, may) 時相論理：時間を表現(always, eventually) 　単に論理や推論といっても，AIではさまざまなものが考えられている． 　まず，数学の試験問題を解くときのように，問題を解決するための知識が正確ですべてそろっているとき，それは完全な知識であるという．そういう場合には，ギリシャ時代から発展してきて現在でも多くの科学で使われている標準的で数学的な論理と推論の方法がある．もっとも単純なのは，命題の真偽を１つの記号で表現する命題論理である．それをやや複雑にしたものとして，命題を，主語や目的語を表現する名詞（オブジェクト）とそれらの間の関係を表現する動詞（述語）などに分解して，複数の記号で１つの命題を構造的に表現する述語論理がある． 　そのほかにも，英語の助動詞 must が表す必然性や can, may が表す可能性を扱うことができる様相論理が研究されている．また，時間の概念を論理的に表現し，always（いつも～である）とか eventually（いつか必ず～となる）のような表現を可能とする時相論理は，ハードウェアやソフトウェアの設計や検証にも用いられつつある．

5 いろいろな論理と推論方式(2/2) 不確実な知識に基づく推論 ファジィ推論：あいまいで主観的な知識を扱う
確率推論：観測事実から命題が真である確率を計算 知識が欠けているときの推論 学習 帰納推論：多数の観測事実から一般法則を導く 仮説推論：観測事実を説明できる仮説を導く 　実際の応用システムでは，数学と異なり，すべての知識が正確であるとは限らない．そのような不確実な知識を扱うための推論手法として，ファジィ推論や確率推論がある．また，知識が欠けているときの推論手法として，帰納推論や仮説推論などがある．特に，帰納推論は，ＡＩにおける知識獲得や機械学習の分野と密接に関係している．

6 例題 魔宮の世界(1/10) 舞台と登場人物 格子の世界 (grid world) 落とし穴 黄金 ４ モンスター ３ ２ エージェント １
例題　魔宮の世界(1/10) 舞台と登場人物 格子の世界 (grid world) 落とし穴 黄金 ４ モンスター ３ ２ エージェント 　例題として，図のような「魔宮の世界」を考えよう． 　舞台はある洞窟をモデル化した４×４の格子からなっている．ＡＩの研究では，このようなモデルが良く用いられることが多く，一般に，格子の世界（グリッドワールド）と呼ばれている． 　登場人物は，「エージェント」と「モンスター」．そして，人物ではないが，「黄金」と「落とし穴」というオブジェクトが登場する． １ １ ２ ３ ４

7 魔宮の世界(2/10) アクションとゴール アクション 上下左右のいずれかに １マス進む 黄金を拾う 洞窟から脱出する ゴール
上下左右のいずれかに 　１マス進む 黄金を拾う 洞窟から脱出する ゴール モンスターと落とし穴を避けながら黄金を拾って，出発点に戻って脱出する 　　エージェントがとることのできる行為（アクション）はスライドに示されているとおりである．基本的には，上下左右のいずれかに 　１マス進むことを繰り返す．黄金のあるマスまで来るとそれを拾うことができる．その後，出発地点まで戻り，洞窟から脱出する． 　　エージェントのタスク（ゴール）は，モンスターと落とし穴を避けながら黄金を拾って，出発点に戻って脱出することである．

8 魔宮の世界(3/10) エージェントのセンサー モンスターのいる部屋およびそれに隣接した部屋では 異臭 (Stench) を感じる
魔宮の世界(3/10)　エージェントのセンサー モンスターのいる部屋およびそれに隣接した部屋では 異臭 (Stench) を感じる 壁にぶつかると 衝撃 (Bump) を感じる 黄金のある部屋では 黄金の光 (Glitter) を感じる 　　エージェントはつぎのような知覚能力（センサー）によって，自分の置かれている環境の情報の一部を知ることができる． 　(1)モンスターのいる部屋およびそれに隣接した部屋では異臭 (Stench) を感じる． 　(2)穴のある部屋およびそれに隣接した部屋では風 (Breeze) を感じる． 　(3)黄金のある部屋では黄金の光 (Glitter) を感じる． 　(4)この世界の周囲を囲んでいる壁にぶつかると衝撃 (Bump) を感じる． 穴のある部屋およびそれに隣接した部屋では 風 (Breeze) を感じる

9 魔宮の世界(4/10) シミュレーション ４ ３ ２ １ １ ２ ３ ４ (1,1)には異臭も風もない → (1,2),(2,1)はOK
魔宮の世界(4/10)　シミュレーション ４ ３ ２ OK １ 　では，エージェントがどのような判断のもとで行動したらよいか，考えてみよう． 　まず，(1,1)には異臭も風もないので，(1,2),(2,1)はOKである．エージェントは，その事実を記憶する．スライドでは，OKを表すフェイスマークを図に記入して，エージェントの記憶の状態を表示している． １ ２ ３ ４ (1,1)には異臭も風もない　→　(1,2),(2,1)はOK

10 魔宮の世界(5/10)　シミュレーション OK ４ ３ PIT ? ２ １ 　エージェントは(2,1)に進んだとしよう．そこで風を感知するので， 　　　(2,2)または(3,1)に落とし穴がある ということがわかる．エージェントはそれを記憶する．スライドでは， (2,2)および(3,1)のそれぞれに「落とし穴があるかもしれない」ことを表すマークを記入している． １ ２ ３ ４ (2,1)で風を感知　→　(2,2)または(3,1)に落とし穴がある

11 魔宮の世界(6/10) シミュレーション ４ ３ PIT ? ２ １ １ ２ ３ ４ (1,1)を経由して，(1,2)へ進む OK
魔宮の世界(6/10)　シミュレーション OK ４ ３ PIT ? ２ １ 　(2,2)と(3,1)は危険なので，エージェントは，安全とわかっている(1,1)を経由して，(1,2)へ進む． １ ２ ３ ４ (1,1)を経由して，(1,2)へ進む

12 魔宮の世界(7/10) シミュレーション ４ ３ PIT ? ２ MONSTER １ １ ２ ３ ４
魔宮の世界(7/10)　シミュレーション OK ４ ３ PIT ? ２ MONSTER １ 　(1,2)で異臭を感知するので， 　　　　　(1,1)or(2,2)or(1,3)にモンスターがいる ということがわかる．しかし，実際には， 　　　　　(1,1)にはモンスターはいない 　　　　　(2,2)にはモンスターがいるはずはない ということがわかる．なぜなら，(1,1)はさきほどまでいた場所であり，また，(2,2)にもしモンスターがいるなら，さきほど行った(2,1)で異臭を感じたはずだからである． 　ゆえに， 　　　　　(1,3)にモンスターがいる ということがわかる．スライドには，そのマークを記入してある． １ ２ ３ ４ (1,2)で異臭を感知　→　(1,1)or(2,2)or(1,3)にモンスターがいる (1,1),(2,2)にモンスターはいない　→　(1,3)にモンスターがいる

13 魔宮の世界(8/10) シミュレーション ４ ３ PIT ? PIT ２ MONSTER １ １ ２ ３ ４
魔宮の世界(8/10)　シミュレーション OK ４ ３ PIT ? PIT ２ MONSTER １ 　また，(1,2)に風がないことから， 　　　　　(2,2)には落とし穴がない ということがわかる．ところで，すでに３枚前のスライドで 　　　　　(2,2)または(3,1)に落とし穴がある ということがわかっていた．したがって， 　　　　　(3,1)に落とし穴がある ということがわかる． １ ２ ３ ４ (1,2)に風がない　→　(2,2)に落とし穴がない 　　　　　　　　　　　→　(3,1)に落とし穴がある

14 魔宮の世界(9/10) シミュレーション ４ ３ PIT ? PIT ２ MONSTER １ １ ２ ３ ４ （途中省略）
魔宮の世界(9/10)　シミュレーション OK ４ ３ PIT ? PIT ２ MONSTER １ 　その後，エージェントは安全が保証された(2,2)へ進み，（その後，いったん(3,2)へ進んでも，また(2,2)へ戻ってきて，）安全とわかっている(2,3)へ進んで黄金を手に入れることになる． １ ２ ３ ４ （途中省略） (2,3)まで進んで黄金を拾う

15 魔宮の世界(10/10) シミュレーション この例題においては， 異臭とモンスターを結び付ける背景知識 風と落とし穴を結び付ける背景知識
魔宮の世界(10/10)　シミュレーション 　この例題においては， 　異臭とモンスターを結び付ける背景知識 　風と落とし穴を結び付ける背景知識 　現場でセンサー入力から得た事実に関する知識 から論理的な推論を行うことによって， エージェントは適切な行動を決定することができている． 　この例題においては， 　　- 異臭とモンスター，および風と落とし穴を結び付ける背景知識 　　- 現場でセンサー入力から得た事実に関する知識 を論理的に組み合わせて推論を行うことによって， エージェントは適切な行動を決定することができている．

16 命題論理 (Propositional Logic)
　構文論 　意味論 　論理の最も基礎となる「命題論理」を学ぶ．ＡＩにおいて，「論理」は「知識表現言語」の役割を持っているのだったことを思い出そう．したがって，命題論理も言語である．一般に，言語を定義するには，構文論(syntax)と意味論(semantics)を規定する必要がある．そこで今回は，命題論理の構文論（論理式を記述する文法）と意味論（論理式が真が偽かを解釈する方法）を学ぶ．特に，もっとも重要な概念である論理的帰結と充足不能性について理解しよう．

17 命題論理の構文論（1/3）構文要素 命題論理の構文要素 論理定数： true ，false
構文要素を一定の規則で並べると論理式となる． 命題論理の構文要素 論理定数：　true ，false 命題記号：　それ以上分解できない命題（原始命題） 　　　　　　　　を表す記号．p, q, r など． 論理記号：　命題を結合して複合した命題を作る記号． 同値 等しい EQUIV 含意 ならば IMPLY 否定 でない NOT 選言 または OR 連言 かつ AND 　命題論理の文法を説明する．それは，論理式を作るための正しい規則からなっている． 　まず，論理式を作るための素材ともいえる構文要素を覚えてほしい．これは，論理定数，命題記号，論理記号の３つに分類される．その説明はこのスライドに書かれているとおりである．

18 命題論理の構文論（2/3）論理式 論理式 論理定数 は論理式である． true false 命題記号 は論理式である．
論理式： 原始命題を論理記号でつないだ文． 論理式 論理定数　は論理式である． true false 命題記号　は論理式である． が論理式ならば，　　　　 　　は論理式である． が論理式ならば，以下の４つも論理式である． 　これらの構文要素を適切な規則にしたがって並べた記号列が文法的に正しい論理式である．その規則はこのスライドに書かれた４つである． は論理式である． 例 は論理式でない．

19 命題論理の構文論（3/3）リテラル リテラル 正リテラル 命題記号 はリテラルである． 命題記号 はリテラルである． 負リテラル
命題記号　はリテラルである． 正リテラル 　　命題記号　はリテラルである． 負リテラル カッコの省略ルール 論理記号の優先順位 ∧と∨の結合則の利用 　１個の命題記号そのもの，または，その否定をリテラルという．とくに，前者を正リテラル，後者を負リテラルという． 　また，５つの論理記号の結合の優先順位をこのスライドのように約束し，不必要なカッコは省略してよいこととする．たとえば，(P∧Q）→Rは，∧が→より結合の優先順位が高いので，カッコを省略して， P∧Q→Rとしてよい． 　また， ∧だけ，あるいは∨だけが連続して結合している部分は，この論理記号の結合則 　　　 (P∧Q)∧R　＝　 P∧(Q∧R) 　　　 (P∨Q) ∨R　＝　 P∨(Q∨R) により，カッコによる結合の順番が意味を持たないことから，まとめてカッコを省略できる． （「結合則」が確かに成り立つことの確認は，正式には，後の「意味論」を待つ必要がある．） 例 のカッコを省略すると

20 休憩

21 命題論理の意味論（1/11）：解釈の概念 解釈 解釈： 論理式を真偽に対応付ける写像 論理式 （構文領域） 真偽値 （意味領域）
　文法的に正しい論理式が与えられたとして，それが何を意味するのかを決める規則を学ぶ．ここでいう「意味」とは，命題論理の場合，その論理式が表している命題が「真」なのか「偽」なのかということである． 　その基礎となる概念は，論理式を真偽に対応付けるための解釈というものである．スライドの図のように，論理式の集合（構文領域と呼ぶ）と真偽値の集合（意味領域と呼ぶ）を考える．解釈とは，構文領域に含まれる論理式の１つ１つを意味領域に含まれる真偽値に対応付けるもの（写像）である．そのような対応は組合せに応じてたくさんあるので，「解釈」もたくさんあることになる． 　しかし，つぎのような条件によって，実際には，命題変数にのみ対応（意味）を決めることにして，それ以外の論理式に対する対応（意味）は自動的に決まるようにする．その仕組みは，つぎの２つの条件を満たすように解釈を定めることである． 　１つめの条件は，true という論理式にはT(真)を対応付け，falseという論理式にはF(偽)を対応付けるということである．この条件は，true, falseの常識的な意味付けを要求している． 　２つめの条件は，not, and, or, →，⇔の５つの論理記号を用いて作られた論理式の意味は，その中に含まれる命題変数の意味に基づいて，計算によって自動的に求めるということである．その計算規則は，つぎのスライドで． 命題変数 p,q,.. の解釈だけは 自由に決められる．.

22 命題論理の意味論（2/11）：論理式の解釈 T F P Q P→Q P∨Q P∧Q Q P «
true の値はT（真）， false の値はF（偽） 　　　 　　　　の値は　　の値の逆． 　の値は，以下の真理値表に基づいて決める． T F P　 Q P→Q P∨Q P∧Q Q P 　このスライドがその計算規則である．これを使うと，どんな複雑な論理式の値も命題変数の値に基づいて計算することができる．

23 命題論理の意味論（3/11）：論理式の解釈 例 のとき のとき 　これは論理式の意味（真偽値）の計算例である．

24 命題論理の意味論（4/11）：等価な論理式 ￢(￢Ｐ) ＝ Ｐ 等価 P = Q :どんな解釈でも P と Q の真偽が一致
二重否定 ￢(￢Ｐ)　＝　Ｐ 交換則 Ｐ∧Ｑ　＝　Ｑ∧Ｐ P∨Ｑ　＝　Ｑ∨Ｐ 結合則 （Ｐ∧Ｑ）∧Ｒ　＝　Ｐ∧（Ｑ∧Ｒ） （Ｐ∨Ｑ）∨Ｒ　＝　Ｐ∨（Ｑ∨Ｒ） 分配則 Ｐ∧（Ｑ∨Ｒ）　＝　（Ｐ∧Ｑ）∨（Ｐ∧Ｒ） Ｐ∨（Ｑ∧Ｒ）　＝　（Ｐ∨Ｑ）∧（Ｐ∨Ｒ） ド・モルガンの法則 ￢ （Ｐ∧Ｑ）　＝　 (￢Ｐ) ∨ (￢Ｑ) ￢ （Ｐ∨Ｑ）　＝　 (￢Ｐ) ∧ (￢Ｑ) 　ここからは解釈との関連で特別な性質をもつ論理式について見ていこう． 　どんな解釈のもとでも，２つの論理式 P, Q の真偽が一致するとき，この２つの論理式は等価であるといい，P=Q と書く． 　よく知られている等価な論理式をスライドに示してある．いずれも常識的なものだが，特に，分配則の２つめの式においては，or が and に対して分配できることに注意しよう．（orを足し算，andを掛け算だと思っているとこの式は奇妙に感じるかもしれない．） 　ド・モルガンの法則を知らなかった人は，ここで必ず覚えておこう． 　いずれも，「すべての解釈について」，左辺と右辺の計算結果が一致することによって確認できる．（かなりの労苦を伴うが．）

25 命題論理の意味論（5/11）：含意と同値 P Q P→Q ￢P (￢P)∨Q T T T F T T F F F F F T T T T F
　同値（⇔）は二重含意ともいい，１つめの等式からわかるように，含意（→）が両方向に成り立つことを表す論理式と等価である． ここからは解釈との関連で特別な性質をもつ論理式について見ていこう． 　２つめの等式は，含意（→）を not と or で表現している．真理値表を使って，４通りのすべての解釈に対して，この論理式が真であることを確認している．この結果は，それ自体が重要で，覚えておく価値がある． 　このスライドの２つの結果から，含意と同値を含む論理式は，not, and, or だけを用いた等価な論理式で表現できることがわかる． F F T T T

26 命題論理の意味論（6/11）：恒真 恒真 どんな解釈のもとでも真 例 のとき 他の３つのケースも同様
恒真　どんな解釈のもとでも真 例 のとき 　どのような解釈のもとでも真である論理式は恒真であるという．このスライドの２つの例のうち，１つめは必ず真となることはすぐわかる．２つめがそうであることはすぐにはわからないので，４通りのすべての解釈に対して，この論理式が真であることを確認する必要がある．スライドでは，その１つだけを示している． 他の３つのケースも同様

27 命題論理の意味論（7/11）：充足不能と充足可能
充足不能　どんな解釈のもとでも偽 例 充足可能　ある解釈のもとで真 例 充足不能 充足可能 恒真 　どんな解釈のもとでも偽である論理式は充足不能であるという． 　ある解釈（少なくとも１つの解釈）のもとで真となる論理式は充足可能であるという．

28 命題論理の意味論（8/11）：論理的帰結 論理的帰結 のすべてを真とするどんな解釈のもとでも が真のとき， の論理的帰結 は 例
論理的帰結　 のすべてを真とするどんな解釈のもとでも が真のとき， の論理的帰結　 は 例 　論理式P1,P2,...,Pnのすべてが真となる解釈はいろいろあるだろうが，そのような解釈からどれを採用しても，その解釈のもとで論理式Qが真となるとき，QはP1,P2,...,Pnの論理的帰結であるといい，このスライドのような表記をする．論理式P1,P2,...,Pnのすべてが真となる解釈が１つに定まらなくてもQが真であることが確実に言えるという点で，論理的帰結という概念は，応用上，非常に重要である． 　論理的帰結かどうかを判断する一般的な方法は，定義にしたがって，つぎのようなものとなる． 　まず， P1,P2,...,Pnのすべてを真とする解釈をすべて求める．これは命題変数に真偽値を与えるすべての組合せについて，論理式の値を計算することによってできる．つぎに，それらの解釈ごとにQが真かどうかを計算する．どの解釈に対してもQが真ならば，定義によって，QはP1,P2,...,Pnの論理的帰結である．そうでなければ，Qは論理的帰結ではない．しかし，この方法はすべての解釈について論理式の真偽を計算するので多くの手間が必要であることに注意しよう．

29 命題論理の意味論（9/11）：演繹（えんえき）定理
演繹定理　 の論理的帰結　 は 必要十分 が恒真 背理法 必要十分 　これまで学んだ３つの概念，「恒真」，「充足不能」，「論理的帰結」には，このスライドのような関係が成り立つ．これを演繹定理という．特に， 「充足不能」のところが重要である．前提 P1,...,Pn に結論の否定 ￢Qを付け加えて，充足不能（矛盾）であることを示すことによって，Qが論理的帰結であることを示すことができる．これは，数学における「背理法」の考え方に通じている． が充足不能

30 命題論理の意味論（10/11）：例題 魔宮の世界 背景知識 (1,2) にモンスターがいるなら，(1,1) で異臭を感じる
命題論理の意味論（10/11）：例題　魔宮の世界 背景知識 (1,2) にモンスターがいるなら，(1,1) で異臭を感じる (1,2) に落とし穴があるなら，(1,1) で風を感じる (1,2) にモンスターも落とし穴もないなら，(1,2) はOK 事実 質問 (1,1) で異臭を感じない (1,2) はOKか？ 　魔宮の世界の例題の一部について，３つの背景知識とセンサーから得た２つの事実の論理的帰結によって，(1,2)がＯＫであることを示してみよう． (1,1) で風を感じない

31 命題論理の意味論（11/11）：論理的帰結の判定
しかし，これでは 効率が悪い！ 結論の否定 　25=32通りのすべての解釈について調べると 　　　　　(1) ∧(2)∧(3)∧(4)∧(5)∧(6) は充足不能 　結論の否定 ￢OK12 を背景知識と事実に追加し，３２通りすべての解釈について調べると，いずれの解釈のもとでも偽となるので，充足不能であることを確認できる．ゆえに，演繹定理より，OK12 は背景知識と事実の論理的帰結である． 　しかし，３２通りの解釈について調べるというのは明らかに効率が悪い．いかに効率良く充足不能性を調べるかという技術は次回以降に学ぶ主題である． ゆえに