ソフトウェア科学特論: 命題論理

Table of Contents

1 概要

本稿では,命題論理に関し以下の内容を説明する.

  • 命題論理式
  • 真理値

1.1 注意

本Webページ(およびPDF)の作成には Emacs org-mode を用いており, 数式等の表示は MathJax を用いています. IEでは正しく表示されないことがあるため, Firefox, Safari等のWebブラウザでJavaScriptを有効にしてお使いください. また org-info.js を利用しており, 「m」キーをタイプするとinfoモードでの表示になります. 利用できるショートカットは「?」で表示されます.

1.2 参考文献

  • 小野寛晰著 『情報科学における論理』日本評論社,1994 (Amazon)

2 命題論理式

2.1 命題論理式の記号

  • 命題定数 (propositional constants)
    • \(\F\)   (偽; false)
    • \(\T\)   (真; true)
  • 命題変数 (propositional variables; Boolean variables)
    • \(p\), \(q\), \(r\), …, \(p_1\), \(q_1\), \(r_1\), …
  • 論理結合子 (logical connectives)
    記号意味
    \(\land\)かつ, 連言and, conjunction
    \(\lor\)または, 選言or, disjunction
    \(\imp\)ならば, 含意implies, implication
    \(\neg\)でない, 否定not, negation

2.2 命題論理式の定義

命題論理式 (propositional formula)を以下のように再帰的に定義する.

  • 命題定数および命題変数は命題論理式である.
  • \(A\), \(B\) が命題論理式の時,以下は命題論理式である. \[ (A \land B) \qquad (A \lor B) \qquad (A \imp B) \qquad (\neg A) \] これらは複合論理式 (compound formula) と呼ばれる.

2.3 BNFによる定義

以下は,命題論理式の構文カテゴリ F をBNFで定義したものである.

F ::= "\(\F\)"   |   "\(\T\)"   |   P   |  
   "("  F  "∧"  F  ")"   |   "("  F  "∨"  F  ")"   |   "("  F  "⇒"  F  ")"   |   "("  "¬"  F  ")"

  • P は命題変数の構文カテゴリである.
  • "α" は終端記号を表す.

2.4 練習問題

以下の各文字列について命題論理式として正しいか間違っているかを答えよ.

  1. \(p\)
    (解答例)

    正しい

  2. \((p \mathrel{\&} q)\)
    (解答例)

    間違っている. \((p \land q)\) ならば正しい.

  3. \(\neg p\)
    (解答例)

    間違っている. \((\neg p)\) ならば正しい.

  4. \((\neg p)\)
    (解答例)

    正しい

  5. \(\neg (p)\)
    (解答例)

    間違っている. \((\neg p)\) ならば正しい.

  6. \((p)\)
    (解答例)

    間違っている. \(p\) ならば正しい.

  7. \((p \land q \lor r)\)
    (解答例)

    間違っている. \((p \land (q \lor r))\) あるいは \(((p \land q) \lor r)\) ならば正しい.

  8. \(((\neg p) \land (q \imp r))\)
    (解答例)

    正しい

2.5 抽象構文による定義

上記の命題論理式の再帰的な定義やBNFによる定義は, 命題論理式の文字列上の表記 (具象構文; concrete syntax) を規定した定義である.

しかし,コンパイラやトランスレータ等の言語処理系のアルゴリズムについて議論する時は, 具象構文ではなく,計算機中の内部的な表現に着目したほうが都合が良い. たとえば,命題論理式の具象構文にはカッコが現れるが, 計算機中の内部表現では構文木が使用されておりカッコ自体は現れない.

そこで構文木等の内部表現に対応した 抽象構文 (abstract syntax) だけを規定することもある.

命題論理式は,以下の抽象構文で定義される表現である. \begin{eqnarray*} F & ::= & \F \:\mid\; \T \:\mid\; P \:\mid\; F\ \land\ F \;\mid\; F\ \lor\ F \;\mid\; F\ \imp\ F \;\mid\; \neg\ F \end{eqnarray*}

2.6 論理結合子の優先度

以下の規則に従い,命題論理式のカッコを省略する.

  • \(\neg\) は最も高い優先度を持つとする. たとえば \((\neg A \land B)\) は \(((\neg A) \land B)\) を表す.
  • \(\land\), \(\lor\), \(\imp\) は右結合的とする. たとえば \((A \land B \land C)\) は \((A \land (B \land C))\) を表す.
  • 一番外側のカッコは省略できる.

2.7 部分論理式

命題論理式 \(A\) の 部分論理式 (subformula)を以下のように再帰的に定義する.

  • \(A\) 自身は \(A\) の部分論理式である.
  • \(A\) が \((B \land C)\) あるいは \((B \lor C)\) あるいは \((B \imp C)\) の形をしている時, \(B\) と \(C\) の部分論理式は \(A\) の部分論理式である.
  • \(A\) が \((\neg B)\) の形をしている時, \(B\) の部分論理式は \(A\) の部分論理式である.

2.8 練習問題

以下の各命題論理式について,部分論理式をすべて答えよ.

  1. \((\neg q)\)
    (解答例)

    \(q\), \((\neg q)\)

  2. \(((\neg q) \imp r)\)
    (解答例)

    上に加えて \(r\), \(((\neg q) \imp r)\)

  3. \(((\neg p) \land ((\neg q) \imp r))\)
    (解答例)

    上に加えて \(p\), \((\neg p)\), \(((\neg p) \land ((\neg q) \imp r))\)

3 真理値

  • 命題論理式の 真理値 (truth value)は, 命題変数の値を定めることで計算できる.
  • 命題論理式の真理値を以下の記号で表す.
    • \(\FV\) (偽; false)
    • \(\TV\) (真; true)
  • \(\F\) と \(\T\) を用いていない点に注意する. 構文 (syntax)と意味 (semantics)を明確に区別するため, それぞれで異なった記号を用いる.
  • 命題論理式の真理値は,その直接の部分論理式の真理値から 一意的に定めることができる.
\(A\)\(B\)\(A \land B\)\(A \lor B\)\(A \imp B\)
\(\FV\)\(\FV\)\(\FV\)\(\FV\)\(\TV\)
\(\FV\)\(\TV\)\(\FV\)\(\TV\)\(\TV\)
\(\TV\)\(\FV\)\(\FV\)\(\TV\)\(\FV\)
\(\TV\)\(\TV\)\(\TV\)\(\TV\)\(\TV\)
\(A\)\(\neg A\)
\(\FV\)\(\TV\)
\(\TV\)\(\FV\)

3.1 真理値表

  • 命題論理式の真理値は,その命題論理式中に現れる命題変数の真理値で定まる.
  • それを表にしたものを 真理値表 (truth table)と呼ぶ.
  • 以下は \(\neg p\lor q\) の真理値表の例である.
\(p\)\(q\)\(\neg p\)\(\neg p\lor q\)
\(\FV\)\(\FV\)\(\TV\)\(\TV\)
\(\FV\)\(\TV\)\(\TV\)\(\TV\)
\(\TV\)\(\FV\)\(\FV\)\(\FV\)
\(\TV\)\(\TV\)\(\FV\)\(\TV\)

3.2 練習問題

  1. \((\neg p\land q)\lor(p\land \neg q)\) の真理値表を示せ.
  2. \((p\lor q)\land \neg(p\land q)\) の真理値表を示せ.
  3. \(p\imp q \imp p\) の真理値表を示せ.
  4. \((p \land q)\lor(q \land r)\lor(r \land p)\) の真理値表を示せ.
  5. \(n\) 個の異なる命題変数を含む命題論理式の真理値表は何行になるか.

3.3 論理的に同値

  • 2つの命題論理式が同一の真理値表を持つ時, 2つの命題論理式は 論理的に同値 (logically equivalent) であると呼ばれる (数学的な定義は以下で述べる).
  • 命題論理式の真理値表が \(\TV\) のみを含む時, その命題論理式は 恒真 (valid)あるいは トートロジー (tautology) であると呼ばれる (数学的な定義は以下で述べる).
  • 与えられた命題論理式の真理値表のサイズは有限である. したがって,与えられた命題論理式の恒真性は 決定可能 (decidable) である. すなわち,与えられた命題論理式の恒真性を判定する 有限ステップで停止するアルゴリズムが存在する.

3.4 真理値割当

  • 命題変数に真理値を割り当てる関数を 真理値割当 (truth assignment)あるいは 付値 (valuation) という.
  • 真理値割当 \(v\) の定義域は, 以下のようにして命題論理式に一意的に拡張できる ("\(\Llra\)" は "if and only if" を表す). \begin{eqnarray*} v(\F)=\FV \\ v(\T)=\TV \\ v(A)=v(A) && (A \mbox{が命題変数の時}) \\ v(A \land B)=\TV & \Llra & v(A)=\TV\ \mbox{かつ}\ v(B)=\TV \\ v(A \lor B)=\TV & \Llra & v(A)=\TV\ \mbox{または}\ v(B)=\TV \\ v(A \imp B)=\TV & \Llra & v(A)=\FV\ \mbox{または}\ v(B)=\TV \\ v(\neg A)=\TV & \Llra & v(A)=\FV \end{eqnarray*}
  • あるいは,\(\land\), \(\lor\), \(\neg\) で表される真理値上の関数を定義しておけば, 以下のようにも定義できる. \begin{eqnarray*} v(\F) & = & \FV \\ v(\T) & = & \TV \\ v(A) & = & v(A) \quad (A \mbox{が命題変数の時}) \\ v(A \land B) & = & v(A) \land v(B) \\ v(A \lor B) & = & v(A) \lor v(B) \\ v(A \imp B) & = & \neg v(A) \lor v(B) \\ v(\neg A) & = & \neg v(A) \end{eqnarray*}

3.4.1

\(v\) は \(v(p)=\FV\) と \(v(q)=\FV\) を満たす真理値割当とする. 以下より \(v(\neg p \lor q) = \TV\) である. \begin{eqnarray*} v(\neg p \lor q) & = & v(\neg p) \lor v(q) \\ & = & \neg v(p) \lor v(q) \\ & = & \neg \FV \lor \FV \\ & = & \TV \lor \FV \\ & = & \TV \end{eqnarray*}

3.4.2

\(v\) は \(v(p)=\TV\) と \(v(q)=\FV\) を満たす真理値割当とする. 以下より \(v(\neg p \lor q) = \FV\) である. \begin{eqnarray*} v(\neg p \lor q) & = & v(\neg p) \lor v(q) \\ & = & \neg v(p) \lor v(q) \\ & = & \neg \TV \lor \FV \\ & = & \FV \lor \FV \\ & = & \FV \end{eqnarray*}

3.5 充足可能性と恒真性

3.5.1 充足可能性の定義

命題論理式 \(A\) が, ある真理値割当 \(v\) について \(v(A)=\TV\) となる時, \(v\) は \(A\) を 充足する (satisfies) といい, \(v \vDash A\) で表す.

命題論理式 \(A\) について, \(A\) を充足する真理値割当が存在する時, \(A\) は 充足可能 (satisfiable) であるという. 命題論理式が充足可能でない時, 充足不能 (unsatisfialbe) であるという.

3.5.2 恒真性の定義

命題論理式 \(A\) が, 任意の真理値割当により充足される時, \(A\) は 恒真 (valid) であると呼ばれ, \(\vDash A\) で表す.

3.5.3 SAT

  • Satisfiability Testing (SAT) は, 与えられた命題論理式が充足可能か充足不能かを判定する 判定問題 (決定問題; decision problem)である.
  • 決定問題は,その任意の入力について, 高々 \(O(n^{k})\) (ただし \(n\) は入力の長さ,\(k\) はある正の定数) のステップで結果を計算する決定性チューリング機械 (deterministic Turing machine) が存在する時, 多項式時間で可解であるといわれる.
  • 多項式時間で可解な決定問題のクラスを P で表す.
  • 非決定性チューリングマシン (non-deterministic Turing machine)で 多項式時間で可解な決定問題のクラスを NP で表す. 明らかに P \(\subseteq\) NP である.
  • P = NP か否かは計算機科学の中心的な問題である.
  • SATは,すべての真理値割当を考慮することで 指数時間 (exponential time) で解くことができる.
  • 疑問: SAT \(\in\) P だろうか?
  • Cook は 1971年に SAT (厳密には3-SAT)が NP-完全であることを証明した. すなわち,SATが多項式時間で可解であれば, クラス NP のすべての問題が多項式時間で可解となることを示した.

SAT \(\in\) P \(\Llra\) P = NP

  • したがって,SATを多項式時間で解くアルゴリズムを発見すれば, P = NP を証明したことになり,チューリング賞受賞確実である!

3.5.4 充足可能性と恒真性の関係

任意の命題論理式 \(A\) について以下が成り立つ. \begin{eqnarray*} A\ \mbox{が充足不能} & \Llra & \neg A\ \mbox{が恒真.} \end{eqnarray*}

証明
(\(\Lra\))

\(A\) が充足不能であるから \(v(A)=\TV\) となる真理値割当 \(v\) は存在しない. すなわち,任意の真理値割当 \(v\) について \(v(A)=\FV\) である. したがって,任意の真理値割当 \(v\) について \(v(\neg A)=\TV\) であり, \(\neg A\) は恒真である.

(\(\Lla\))

\(\neg A\) が恒真であるから, 任意の真理値割当 \(v\) について \(v(\neg A)=\TV\) である. したがって,任意の真理値割当 \(v\) について \(v(A)=\FV\) であり, \(A\) は充足不能である.

3.6 練習問題

  1. 以下の各命題論理式について恒真性,充足可能性を答えよ.
    • \((p\land q)\imp (p\lor r)\)
    • \(p\land q\)
    • \(p\land \neg p\)
    • \(\neg p\lor p\)
    • \(((p \imp q) \imp p) \imp p\) (パース律)
  2. 以下を証明するか反例を示せ. \begin{eqnarray*} A\ \mbox{と}\ B\ \mbox{が充足可能} & \Lra & A \land B\ \mbox{が充足可能} \end{eqnarray*}
    (解答例)

    \(p\) と \(\neg p\) はそれぞれ充足可能だが, \(p \land \neg p\) は充足可能ではない.

  3. 以下を証明するか反例を示せ. \begin{eqnarray*} A \land B\ \mbox{が充足可能} & \Lra & A\ \mbox{と}\ B\ \mbox{が充足可能} \end{eqnarray*}
    (解答例)

    \(A \land B\) が充足可能ならば, ある真理値割当 \(v\) について \(v(A \land B)=\TV\) である. したがって,その \(v\) について \(v(A)=\TV\), \(v(B)=\TV\) なので \(A\) も \(B\) も充足可能である.

  4. 以下を証明するか反例を示せ. \begin{eqnarray*} A \imp B\ \mbox{と}\ A\ \mbox{が充足可能} & \Lra & B\ \mbox{が充足可能} \end{eqnarray*}
    (解答例)

    \(p \imp (q \land \neg q)\) と \(p\) はそれぞれ充足可能だが, \(q \land \neg q\) は充足可能ではない.

  5. 以下を証明するか反例を示せ. \begin{eqnarray*} A \imp B\ \mbox{が恒真かつ}\ A\ \mbox{が充足可能} & \Lra & B\ \mbox{が充足可能} \end{eqnarray*}
    (解答例)

    \(A\) が充足可能より ある真理値割当 \(v\) について \(v(A)=\TV\) である. さらに \(A \imp B\) が恒真より \(v(A \imp B)=\TV\) である. したがって \(v(B)=\TV\) であり \(B\) は充足可能である.

3.7 論理的同値

3.7.1 論理的同値の定義

  • \(A \equ B\) を \((A \imp B) \land (B \imp A)\) の省略記法とする.
  • 任意の真理値割当 \(v\) に対して以下が成り立つことは容易に確認できる. \begin{eqnarray*} v(A \equ B)=\TV & \Llra & v(A)=v(B) \end{eqnarray*}
  • また,命題論理式上の関係 \(\Equ\) を以下のように定義する. \begin{eqnarray*} A \Equ B & \Def & \mbox{任意の真理値割当 $v$ に対し}\ v(A)=v(B) \end{eqnarray*}
  • 以下が成り立つことは容易に確認できる. \begin{eqnarray*} A \Equ B & \Llra & A \equ B\ \mbox{が恒真} \end{eqnarray*}

3.7.2 同値関係であることの確認

以下に示すように \(\Equ\) は同値関係である. すなわち \(\Equ\) は, 命題論理式上の 反射的 (reflexive),対称的 (symmetric),推移的 (transitive) な関係である.

\(A \Equ B\) の時, \(A\) は \(B\) と 論理的に同値 であるといわれる.

命題論理式上の関係 \(\Equ\) について以下が成り立つ.

  • 任意の命題論理式 \(A\) について \(A \Equ A\) である.
  • 任意の命題論理式 \(A\), \(B\) について, \(A \Equ B\) ならば \(B \Equ A\) である.
  • 任意の命題論理式 \(A\), \(B\), \(C\) について, \(A \Equ B\) かつ \(B \Equ C\) ならば \(A \Equ C\) である.
証明

読者の学習のために省略する.

3.7.3 論理的同値の例

零元\(A\land\F \Equ \F\)
\(A\lor \T \Equ \T\)
単位元\(A\land\T \Equ A\)
\(A\lor \F \Equ A\)
巾等律\(A\land A \Equ A\)
\(A\lor A \Equ A\)
交換律\(A\land B \Equ B\land A\)
\(A\lor B \Equ B\lor A\)
結合律\(A\land(B\land C) \Equ (A\land B)\land C\)
\(A\lor (B\lor C) \Equ (A\lor B)\lor C\)
分配律\(A\land(B\lor C)\Equ(A\land B)\lor (A\land C)\)
\(A\lor(B\land C)\Equ(A\lor B)\land(A\lor C)\)
二重否定\(\neg\neg A \Equ A\)
矛盾律\(A\land \neg A \Equ \F\)
排中律\(A\lor \neg A \Equ \T\)
ド・モルガン律\(\neg(A\land B)\Equ\neg{A}\lor \neg{B}\)
\(\neg(A\lor B)\Equ\neg{A}\land\neg{B}\)
吸収律\(A\land (A \lor B) \Equ A\)
\(A\lor (A \land B) \Equ A\)
対偶\(A\imp B \Equ \neg B\imp \neg A\)
その他\(A\imp B \Equ \neg A\lor B\)
\(\neg A \Equ A\imp \F\)

3.8 練習問題

  1. 上の同値関係を,両辺の真理値表を書いて確かめよ.
  2. 上の同値関係を,以下の集合演算への対応を用いて解釈せよ. \begin{eqnarray*} \F & \llra & \emptyset\ \mbox{(空集合)} \\ \T & \llra & \mbox{U}\ \mbox{(全体集合)} \\ \land & \llra & \cap\ \mbox{(共通集合)} \\ \lor & \llra & \cup\ \mbox{(和集合)} \\ \neg & \llra & ()^{c}\ \mbox{(補集合)} \end{eqnarray*}
  3. 上の同値関係を,以下の演算への対応を用いて解釈せよ. \begin{eqnarray*} \F & \llra & 0 \\ \T & \llra & 1 \\ \land & \llra & \min \\ \lor & \llra & \max \\ \neg & \llra & 1-x \end{eqnarray*}

3.9 論理式の代入

命題論理式の部分論理式を, それと論理的に同値な論理式で置き換えても, 元の命題論理式と論理的に同値である.

3.9.1 文脈

文脈 (context) は,以下の抽象構文で定義される表現である. \begin{eqnarray*} C & ::= & [] \;\mid\; \F \:\mid\; \T \:\mid\; P \:\mid\; C\ \land\ C \;\mid\; C\ \lor\ C \;\mid\; C\ \imp\ C \;\mid\; \neg\ C \end{eqnarray*} 構文要素 \([]\) は ホール (hole) と呼ばれる.

  • 文脈は命題論理式ではない.
  • 逆に命題論理式はホールのない文脈である.
  • 文脈を \(C[]\) で表記する.
  • \(C[A]\) は文脈 \(C[]\) 中のすべてのホールを命題論理式 \(A\) で置き換えた 命題論理式を表す.

3.9.2 命題論理式の代入の定理

任意の文脈 \(C[]\) および任意の命題論理式 \(A\), \(B\) について 以下が成り立つ. \begin{eqnarray*} A\Equ B & \Lra & C[A] \Equ C[B] \end{eqnarray*}

  • 上の定理を用いれば, 命題論理式中の部分論理式を, 論理的に同値な論理式で置き換えることができる.
3.9.2.1 証明

文脈 \(C[]\) の 構造的帰納法 (structural induction) で証明する. すなわち \(A \Equ B\) および \(C[]\) の任意の真部分文脈について 結論が成り立っていると仮定し, \(C[A] \Equ C[B]\) であることを示す.

  1. \(C[]\) が \(\F\) か \(\T\) か命題変数の時, \(C[A]\) と \(C[B]\) は同一であり \(C[A] \Equ C[B]\) である.
  2. \(C[]\) がホールの時, \(C[A]\) は \(A\) に等しく, \(C[B]\) は \(B\) に等しい. したがって \(A \Equ B\) より \(C[A] \Equ C[B]\) である.
  3. \(C[]\) が \(D[] \land E[]\) の形の時, 帰納法の仮定より \(D[A] \Equ D[B]\) および \(E[A] \Equ E[B]\) である. すなわち任意の真理値割当 \(v\) に対して \(v(D[A])=v(D[B])\) および \(v(E[A])=v(E[B])\) である. したがって任意の真理値割当 \(v\) に対して以下が成立し, \(C[A] \Equ C[B]\) である. \begin{eqnarray*} v(C[A]) & = & v(D[A] \land E[A]) \\ & = & v(D[A]) \land v(E[A]) \\ & = & v(D[B]) \land v(E[B]) \\ & = & v(D[B] \land E[B]) \\ & = & v(C[B]) \end{eqnarray*}
  4. \(C[]\) が \(D[] \lor E[]\), \(D[] \imp E[]\), \(\neg D[]\) の形の場合も 同様にして \(C[A] \Equ C[B]\) が示される.

以上が文脈の形のすべての場合であることから, 任意の文脈 \(C[]\) について \(C[A] \Equ C[B]\) であることが示された.

3.9.3 論理式の代入の例

\begin{eqnarray*} && (\neg A\land B)\lor(A\land \neg B) \\ &\Equ& ((\neg A\land B)\lor A)\land((\neg A\land B)\lor \neg B) \quad \mbox{(分配律)}\\ &\Equ& (A\lor(\neg A\land B))\land(\neg B\lor(\neg A\land B)) \quad \mbox{(交換律)}\\ &\Equ& ((A\lor\neg A)\land(A\lor B))\land((\neg B\lor \neg A)\land(\neg B\lor B)) \quad \mbox{(分配律)}\\ &\Equ& (\T\land(A\lor B))\land((\neg B\lor \neg A)\land\T) \quad \mbox{(単位元)}\\ &\Equ& (A\lor B)\land(\neg B\lor \neg A) \quad \mbox{(矛盾律)}\\ &\Equ& (A\lor B)\land(\neg A\lor \neg B) \quad \mbox{(交換律)}\\ &\Equ& (A\lor B)\land\neg(A\land B) \quad \mbox{(ド・モルガン律)} \end{eqnarray*}

3.10 練習問題

「論理的同値の例」で示した同値関係を用いて,以下のそれぞれを示せ.

  1. \(A \land B \Equ \neg(\neg A \lor \neg B)\)
  2. \(A \lor B \Equ \neg(\neg A \land \neg B)\)
  3. \(A\imp (B\imp C) \Equ (A\land B)\imp C\)
  4. \((A\land B)\imp (C\lor D) \Equ \neg A\lor \neg B\lor C \lor D\)
  5. \((\neg A\lor \neg B)\land(\neg A\lor B)\land(A\lor\neg B)\land(A\lor B) \Equ \F\)

3.11 双対性

\(A\) は論理結合子 \(\imp\) を含まない命題論理式とする. \(A\) 中の \(\F\) を \(\T\) に, \(\T\) を \(\F\) に, \(\land\) を \(\lor\) に, \(\lor\) を \(\land\) に置き換えた命題論理式を \(A\) の 双対な論理式 (dual formula) という.

3.11.1 補題

双対性定理を示す前に,以下の補題を示す.

\(A\) は \(\imp\) を含まない命題論理式とし, \(A'\) はその双対な論理式とする.また \(v\) と \(v'\) は,任意の命題変数 \(p\) について \(v'(p)=\neg v(p)\) を満たす真理値割当とする.この時,以下が成り立つ. \begin{eqnarray*} v(A) & = & \neg v'(A') \end{eqnarray*}

証明

省略.

3.11.2 練習問題

  1. 上の補題の証明を完成させよ.

3.11.3 双対定理

\(\imp\) を含まない命題論理式 \(A\), \(B\) の双対な論理式をそれぞれ \(A'\), \(B'\) とする.この時,以下が成り立つ. \begin{eqnarray*} A \Equ B & \Llra & A' \Equ B' \end{eqnarray*}

3.11.4 練習問題

  1. 上の双対定理の証明を完成させよ.

4 標準形

4.1 与えられた真理値表を持つ命題論理式

真理値表の節では,任意の命題論理式について,その真理値表を求める方法を学んだ.

では逆に,真理値表が与えられた時に,そのような真理値表を持つ論理式を 求めることは可能だろうか. たとえば,以下のような真理値表を持つ論理式 \(X\) はどのようなものだろうか.

\(p\)\(q\)\(X\)
\(\FV\)\(\FV\)\(\TV\)
\(\FV\)\(\TV\)\(\FV\)
\(\TV\)\(\FV\)\(\FV\)
\(\TV\)\(\TV\)\(\TV\)

これは,以下の真理値表を眺めることで解決できる.

\(p\)\(q\)\(\neg p\land\neg q\)\(\neg p\land q\)\(p\land\neg q\)\(p\land q\)
\(\FV\)\(\FV\)\(\TV\)\(\FV\)\(\FV\)\(\FV\)
\(\FV\)\(\TV\)\(\FV\)\(\TV\)\(\FV\)\(\FV\)
\(\TV\)\(\FV\)\(\FV\)\(\FV\)\(\TV\)\(\FV\)
\(\TV\)\(\TV\)\(\FV\)\(\FV\)\(\FV\)\(\TV\)

上の真理値表より \(\neg p\land \neg q\) は, \(p\) と \(q\) が共に偽の時のみ真になる論理式であることがわかる. また \(p \land q\) は \(p\) と \(q\) が共に真の時のみ真になる論理式であることがわかる.

したがって \(X\) は \(p\) と \(q\) が共に偽の時および共に真の時のみ真になる論理式であるから, \((\neg p\land \neg q)\lor(p \land q)\) として表すことができる.

4.2 練習問題

  1. 以下の真理値表を持つ論理式 \(Y\) を上の方法で求めよ.
    \(p\)\(q\)\(Y\)
    \(\FV\)\(\FV\)\(\TV\)
    \(\FV\)\(\TV\)\(\FV\)
    \(\TV\)\(\FV\)\(\TV\)
    \(\TV\)\(\TV\)\(\TV\)
  2. 以下の真理値表を持つ論理式 \(Z\) を上の方法で求めよ. この真理値表に対応する論理回路は多数決回路と呼ばれ, \(p+q+r \ge 2\) を表している.
    \(p\)\(q\)\(r\)\(Z\)
    \(\FV\)\(\FV\)\(\FV\)\(\FV\)
    \(\FV\)\(\FV\)\(\TV\)\(\FV\)
    \(\FV\)\(\TV\)\(\FV\)\(\FV\)
    \(\FV\)\(\TV\)\(\TV\)\(\TV\)
    \(\TV\)\(\FV\)\(\FV\)\(\FV\)
    \(\TV\)\(\FV\)\(\TV\)\(\TV\)
    \(\TV\)\(\TV\)\(\FV\)\(\TV\)
    \(\TV\)\(\TV\)\(\TV\)\(\TV\)
  3. \(p+q+r \le 1\) を表す命題論理式を求めよ.
  4. \(p+q+r = 1\) を表す命題論理式を求めよ.
  5. \(p+q+r = 2\) を表す命題論理式を求めよ.

4.3 双対な論理式に着目する

また,同様に以下の真理値表を用い,上の方法と双対的に偽の場合に着目すれば, \(X\) を \((p\lor \neg q)\land(\neg p \lor q)\) として表すことができる.

\(p\)\(q\)\(p\lor q\)\(p\lor\neg q\)\(\neg p\lor q\)\(\neg p\lor\neg q\)
\(\FV\)\(\FV\)\(\FV\)\(\TV\)\(\TV\)\(\TV\)
\(\FV\)\(\TV\)\(\TV\)\(\FV\)\(\TV\)\(\TV\)
\(\TV\)\(\FV\)\(\TV\)\(\TV\)\(\FV\)\(\TV\)
\(\TV\)\(\TV\)\(\TV\)\(\TV\)\(\TV\)\(\FV\)

4.4 練習問題

  1. 上の練習問題の \(Z\) をこちらの方法で求めよ.
  2. \(p+q+r \le 1\) を表す命題論理式を求めよ.
  3. \(p+q+r = 1\) を表す命題論理式を求めよ.
  4. \(p+q+r = 2\) を表す命題論理式を求めよ.

4.5 選言標準形と連言標準形

一つ目の方法では, 命題変数あるいは命題変数の否定のいくつかを連言 (\(\land\))で結び, それらをさらに選言 (\(\lor\))で結んだ式が得られている (たとえば \((\neg p\land \neg q)\lor(p \land q)\)). このような形の論理式は, 選言標準形あるいは 加法標準形,積和標準形と呼ばれる.

二つ目の方法では, 命題変数あるいは命題変数の否定のいくつかを選言 (\(\lor\))で結び, それらをさらに連言 (\(\land\))で結んだ式が得られている (たとえば \((p\lor \neg q)\land(\neg p \lor q)\)). このような形の論理式は, 連言標準形あるいは 乗法標準形,和積標準形と呼ばれる.

選言標準形と連言標準形の定義

命題定数, 命題変数あるいは命題変数の否定を リテラル (literal)と呼ぶ. 一つ以上のリテラルの連言を 連言節 (conjunctive clause), 一つ以上のリテラルの選言を 選言節 (disjunctive clause)と呼ぶ. 一つ以上の連言節の選言を 選言標準形 (DNF; Disjunctive Normal Form), 一つ以上の選言節の連言を 連言標準形 (CNF; Conjunctive Normal Form)と呼ぶ.

  • ここでは命題定数もリテラルに含めているが, 後述のように集合による表現を用いれば命題定数を含める必要はない.
  • 命題変数のリテラルは 正リテラル (positive literal)と呼ばれ, 命題変数の否定のリテラルは 負リテラル (negative literal)と呼ばれる.
  • あるリテラルに対して, その否定のリテラルを 相補リテラル (complimentary literal)と呼ぶ. すなわち \(p\) と \(\neg p\) は互いに他の相補リテラルである.
  • 一つのリテラルからなる節は 単位節 (unit clause)と呼ばれる.

4.6 論理関数と標準形

一般に \(n\) 個の真理値を入力として一つの真理値を定める関数を, \(n\) 変数の 論理関数 という. これまでの議論から,以下のことがわかる.

任意の \(n\) 変数論理関数は, \(n\) 個の命題変数を含む選言標準形および連言標準形の命題論理式として表現できる. したがって,任意の命題論理式は, それと論理的に同値な選言標準形および連言標準形の命題論理式として表現できる.

  • 一つの論理式が,選言標準形でもあり連言標準形でもある場合があることに注意する. たとえば \(p \lor q\) は選言標準形でもあり連言標準形でもある.
  • また,ある論理式と同値な標準形は一つに限らないことにも注意する. \(p \lor q\) は,それ自体が選言標準形であるが, \(p \lor q \Equ (\neg p \land q)\lor(p \land \neg q)\lor(p \land q)\) であり, 右辺は別の選言標準形である.

4.7 式の変形による方法

上では,真理値表を用いて標準形を求めたが,式の変形によって求めることもできる.

4.7.1 否定標準形

そのために,以下の手順に従い, まず 否定標準形 (NNF, Negation Normal Form)を求める.

否定標準形は,以下の抽象構文で定義される命題論理式である. \begin{eqnarray*} N & ::= & \F \:\mid\; \T \:\mid\; P \:\mid\; \neg\ P \:\mid\; N\ \land\ N \;\mid\; N\ \lor\ N \end{eqnarray*}

すなわち,否定標準形は \(\imp\) を含まず, また \(\neg\) が命題変数の前に高々一つだけ現れる命題論理式である.

与えられた命題論理式から,それと論理的に同値な否定標準形を求める方法は, 以下の通りである.

  1. 以下の同値関係を用い,左辺を右辺の式で置き換えることによって, 元の論理式から \(\imp\) を削除する. \begin{eqnarray*} A \imp B & \Equ & \neg A \lor B \end{eqnarray*}
  2. 以下の同値関係を繰り返し用い,否定が命題変数の前に高々一つだけ現れるようにする. \begin{eqnarray*} \neg \F & \Equ & \T \\ \neg \T & \Equ & \F \\ \neg \neg A & \Equ & A \\ \neg (A \land B) & \Equ & \neg A \lor \neg B \\ \neg (A \lor B) & \Equ & \neg A \land \neg B \end{eqnarray*}

4.7.2 否定標準形から選言標準形と連言標準形を求める

否定標準形に対して, 以下の分配法則(および交換法則と結合法則)を繰り返し用いることで, 選言標準形を求めることができる. \begin{eqnarray*} A \land (B \lor C) & \Equ & (A \land B) \lor (A \land C) \end{eqnarray*} 同様に,否定標準形に対して, 以下の分配法則(および交換法則と結合法則)を繰り返し用いることで, 連言標準形を求めることができる. \begin{eqnarray*} A \lor (B \land C) & \Equ & (A \lor B) \land (A \lor C) \end{eqnarray*} なお,必要に応じて以下を用いることで,より簡潔な標準形を求めることができる. \begin{eqnarray*} A \land \F & \Equ & \F \\ A \lor \T & \Equ & \T \\ A \land \T & \Equ & A \\ A \lor \F & \Equ & A \\ A \land A & \Equ & A \\ A \lor A & \Equ & A \\ A \land \neg A & \Equ & \F \\ A \lor \neg A & \Equ & \T \end{eqnarray*}

4.8 練習問題

  1. \(p\imp q\) の選言標準形,連言標準形を求めよ.
  2. \((p\lor q)\land \neg(p\land q)\) の選言標準形,連言標準形を求めよ.
  3. 任意の命題論理式は, 論理結合子として \(\neg\) と \(\land\) のみを含む同値な命題論理式として表現できることを示せ. (ヒント: \(\lor\) が \(\neg\) と \(\land\) で表せることを示す)
  4. 任意の命題論理式は, 論理結合子として \(\neg\) と \(\lor\) のみを含む同値な命題論理式として表現できることを示せ. (ヒント: \(\land\) が \(\neg\) と \(\lor\) で表せることを示す)
  5. 任意の命題論理式は, 論理結合子として \(\imp\) のみを含む同値な命題論理式として表現できることを示せ. (ヒント: \(\neg A \Equ A \imp \F\) を用いる)
  6. 選言標準形の充足可能性は簡単に判定できる.なぜか.
  7. 連言標準形の恒真性は簡単に判定できる.なぜか.
  8. \(p+q+r \ge 2\) を表す命題論理式の選言標準形,連言標準形を求めよ.
  9. \(p+q+r = 1\) を表す命題論理式の選言標準形,連言標準形を求めよ.
  10. \(p+q+r = 2\) を表す命題論理式の選言標準形,連言標準形を求めよ.

4.9 標準形の集合表現

選言標準形に現れる連言節は複数のリテラルの連言, 連言標準形に現れる選言節は複数のリテラルの選言であるが, これらをリテラルの集合として表現することがある.

たとえば連言節 \(\neg p \land q\) を集合 \(\{\neg p, q\}\) で表す. 選言節 \(\neg p \lor q\) も同じく \(\{\neg p, q\}\) となるが, 選言標準形と連言標準形のどちらに着目しているかが明確であれば, 混乱は生じない. また連言節 \(p \land p\) は集合で表現すれば \(\{p\}\) となるが, \(p \land p \Equ p\) であるので問題ない.

選言標準形あるいは連言標準形自体も, 連言節あるいは選言節の集合 (リテラルの集合の集合)として表現できる.

たとえば選言標準形 \((\neg p \land q) \lor (p \land \neg q)\) は \(\{\{\neg p, q\}, \{p, \neg q\}\}\) と表される. また連言標準形 \((p \lor q) \land (\neg p \lor \neg q)\) は \(\{\{p, q\}, \{\neg p, \neg q\}\}\) と表される.

この時 \(\F\) および \(\T\) を不要にできる点に注意する.

まず,選言標準形について考える. 連言節中の \(\T\) は \(A \land \T \Equ A\) より削除できる. また,連言節中の \(\F\) は \(A \land \F \Equ \F\) より連言節自体が \(\F\) と論理的に同値になり, \(A \lor \F \Equ A\) より選言標準形からその連言節を削除できる. したがって連言節および選言標準形とその集合表現の関係は以下のようになる (\(C_i\) は連言節あるいはその集合表現,\(L_j\) はリテラル).

連言節\(\{\}\)\(\Equ\)\(\T\)
連言節\(\{L_1, L_2, \ldots, L_n\}\)\(\Equ\)\(L_1 \land L_2 \land \cdots \land L_n\)
選言標準形\(\{\}\)\(\Equ\)\(\F\)
選言標準形\(\{C_1, C_2, \ldots, C_m\}\)\(\Equ\)\(C_1 \lor C_2 \lor \cdots \lor C_m\)

選言標準形の集合表現で,空集合 \(\{\}\) は \(\F\) を表し, 空集合の集合 \(\{\{\}\}\) は \(\T\) を表すことに注意する.

同様に連言標準形では, 選言節中の \(\F\) は \(A \lor \F \Equ A\) より削除できる. また,選言節中の \(\T\) は \(A \lor \T \Equ \T\) より選言節自体が \(\T\) と論理的に同値になり, \(A \land \T \Equ A\) より連言標準形からその選言節を削除できる. したがって選言節および連言標準形とその集合表現の関係は以下のようになる (\(C_i\) は選言節あるいはその集合表現,\(L_j\) はリテラル).

選言節\(\{\}\)\(\Equ\)\(\F\)
選言節\(\{L_1, L_2, \ldots, L_n\}\)\(\Equ\)\(L_1 \lor L_2 \lor \cdots \lor L_n\)
連言標準形\(\{\}\)\(\Equ\)\(\T\)
連言標準形\(\{C_1, C_2,\ldots, C_m\}\)\(\Equ\)\(C_1 \land C_2 \land \cdots \land C_m\)

連言標準形の集合表現で,空集合 \(\{\}\) は \(\T\) を表し, 空集合の集合 \(\{\{\}\}\) は \(\F\) を表す.

4.10 練習問題

  1. 選言標準形の集合表現 \(\{C_1, C_2, \ldots, C_m\}\) で, ある \(C_i\) が空集合の時,その選言標準形は \(\T\) と論理的に同値であることを示せ.
  2. 連言標準形の集合表現 \(\{C_1, C_2, \ldots, C_m\}\) で, ある \(C_i\) が空集合の時,その連言標準形は \(\F\) と論理的に同値であることを示せ.

4.11 充足同値

DNF や CNF の標準形を求める場合, 分配法則の適用により元の命題論理式よりもかなりサイズの大きな論理式となってしまう.

このことは,SATソルバーのようなプログラムを利用する点で問題となる. SATソルバーは CNF で与えられた命題論理式の充足可能性を高速に判定するプログラムだが, 元の問題を CNF に変換する手間が大きくては役に立たない.

後述のTseitin変換は,与えられた命題論理式をそれと充足可能性が一致する論理式に変換する. 論理的に同値な論理式に変換するのに比較して, より小さなサイズの論理式に変換できる点が特徴である. このような変換を 充足同値 (equi-satisifiable) な変換という.

4.11.1 充足同値な変換の定義

命題論理式 \(A\) を \(A'\) に変換する時,以下を満たす変換を充足同値な変換と呼ぶ.

   \(A\) が充足可能 \(\Llra\) \(A'\) が充足可能

充足同値な関係を以下のように表す.

   \(A \EquSat A'\)

4.11.2 CNF節集合の簡単化

CNF である節集合について, 以下の簡単化を行うことができる.

4.11.2.1 定数除去

定数除去 (constant elimination)は, 命題定数を除去する簡単化である.

すなわち以下の同値関係を用いて命題定数を除去する. \begin{eqnarray*} A \land \F & \Equ & \F \\ A \lor \T & \Equ & \T \\ A \land \T & \Equ & A \\ A \lor \F & \Equ & A \end{eqnarray*}

4.11.2.2 純リテラル除去

純リテラル除去 (pure literal elimination)は, 正リテラルあるいは負リテラルとしてのみ現れているリテラルを含む節を除去する簡単化である.

たとえばCNF \(\{\{p,q\},\{p,\neg q,\neg t\},\{\neg p,r,\neg t\}\}\) において, \(p\), \(q\) は正負双方のリテラルが出現しているが, \(r\) は正リテラルのみ \(t\) は負リテラルのみが出現している. \(v(r)=\TV\), \(v(t)=\FV\) とすれば,これらのリテラルを含む節は充足できる. したがって,\(r\) および \(\neg t\) を含む節を除去しても充足同値である. \begin{eqnarray*} \{\{p,q\},\{p,\neg q,\neg t\},\{\neg p,r,\neg t\}\} & \EquSat & \{\{p,q\}\} \end{eqnarray*} 論理的に同値な変換ではなく,CNFに対しての充足同値な変換であることに注意する.

4.11.2.3 トートロジー除去

トートロジー除去 (tautology elimination)は, トートロジーの(すなわち恒真な) CNF の節を除去する簡単化である.

たとえば選言節 \(\{p, \neg p, q\}\) には, \(p\) と \(\neg p\) という相補リテラル対が含まれている. \(A \lor \neg A \Equ \T\) また \(A \lor \T \Equ \T\) なので, 相補リテラル対の含まれている選言節は \(\T\) と論理的に同値である. さらに \(A \land \T \Equ A\) であるので, そのような選言節は CNF から削除できる.

4.11.2.4 包摂除去

包摂除去 (subsumption elimination)は, 包摂関係にある選言節の一方を CNF から除去する簡単化である.

たとえば CNF に \(\{p,q,r\}\) と \(\{p,q\}\) の二つの選言節が含まれている場合, \((p \lor q) \imp (p \lor q \lor r)\) の包摂関係が成り立ち, 以下の同値関係が成立する. \begin{eqnarray*} (p \lor q) \land (p \lor q \lor r) & \Equ & p \lor q \end{eqnarray*} したがって選言節 \(\{p,q,r\}\) を除去できる.

4.11.3 Tseitin変換

Tseitin変換は1968年に G. S. Tseitin によって導入された充足同値な変換方法である.

命題論理式 \((p_1 \land p_2 \land \cdots \land p_m) \lor (q_1 \land q_2 \land \cdots \land q_n)\) を \(A\) で表す. \(A\) を論理的に同値な CNF に変換すると \(\bigwedge_{i=1..m,j=1..n}\ (p_i \lor q_j)\) のように \(m n\) 個の選言節が生じる.

ここで新しい命題変数 \(r\) を導入し, \(p_1 \land p_2 \land \cdots \land p_m\) を \(r\) で置き換えるとともに, \(r\) と \(p_1 \land p_2 \land \cdots \land p_m\) が同値であることを表す論理式を追加する. また \(q_1 \land q_2 \land \cdots \land q_n\) についても同様に新しい命題変数 \(s\) に置き換えると, 以下の論理式 \(A'\) が得られる. \[ (r \lor s) \land (r \equ (p_1 \land p_2 \land \cdots \land p_m)) \land (s \equ (q_1 \land q_2 \land \cdots \land q_n)) \] この論理式 \(A'\) は元の命題論理式 \(A\) と充足同値である.

このことを確かめよう. \(A\) が充足可能とする. \(A\) を充足する真理値割当を \(v\) とすると,以下のように定義した真理値割当 \(v'\) は \(A'\) を充足する. \begin{eqnarray*} v'(p_i) & = & v(p_i) \\ v'(q_j) & = & v(q_j) \\ v'(r) & = & v(p_1 \land p_2 \land \cdots \land p_m) \\ v'(s) & = & v(q_1 \land q_2 \land \cdots \land q_n) \end{eqnarray*} 逆に \(A'\) が真理値割当 \(v'\) により充足可能とする. \(v'\) の定義域から命題変数 \(r\) と \(s\) を取り除いた真理値割当を \(v\) とすると, \(v\) は \(A\) を充足する.

命題論理式 \(A'\) は,以下のような CNF に簡単に変換できる. \begin{eqnarray*} & & (r \lor s) \\ & \land & (r \lor \neg p_1 \lor \cdots \lor \neg p_m) \land (\neg r \lor p_1) \land \cdots \land (\neg r \lor p_m) \\ & \land & (s \lor \neg q_1 \lor \cdots \lor \neg q_n) \land (\neg s \lor q_1) \land \cdots \land (\neg s \lor q_n) \end{eqnarray*} 2行目の \(r \lor \neg p_1 \lor \cdots \lor \neg p_m\) は \((p_1 \land \cdots \land p_m) \imp r\) に対応し, \((\neg r \lor p_1) \land \cdots \land (\neg r \lor p_m)\) は \(r \imp (p_1 \land \cdots \land p_m)\) に対応する. 3行目も同様である.

このようにTseitin変換を用いると 元の命題論理式に 比例したサイズの CNF を求めることができる.

またさらに以下のような最適化が可能である.

同一論理式は,同一命題変数に置換えできる. たとえば上の例で \(p_1 \land \cdots \land p_m\) が 他の部分にも現れている場合, そこも同じ命題変数 \(r\) で置換えて良い. また条件 \(r \equ (p_1 \land p_2 \land \cdots \land p_m)\) の追加は 一度だけで十分である.

元の命題論理式が否定標準形 (NNF)の場合, 複合論理式を置換の条件は片方向だけで良い. 上の例の \(A\) は NNF なので, 以下の論理式 \(A''\) でも充足同値である (\(r\) と \(s\) の条件が両方向でなく片方向になっている). \[ (r \lor s) \land (r \imp (p_1 \land p_2 \land \cdots \land p_m)) \land (s \imp (q_1 \land q_2 \land \cdots \land q_n)) \] \(A''\) は,以下のような CNF に変換できる. \begin{eqnarray*} & & (r \lor s) \\ & \land & (\neg r \lor p_1) \land \cdots \land (\neg r \lor p_m) \\ & \land & (\neg s \lor q_1) \land \cdots \land (\neg s \lor q_n) \end{eqnarray*}

4.11.4 練習問題

  1. 上の \(A''\) が \(A\) と充足同値であることを確認せよ.
  2. \((p_1 \land p_2 \land p_3)\lor(q_1 \land q_2 \land q_3)\) を分配律を用いて論理的に同値な CNF に変換した場合, 9つの節からなる論理式が得られる. Tseitin変換を用いると7つの節からなる論理式になる.それはどんな論理式か.
  3. 上のTseitin変換で \((p_1 \land p_2 \land p_3)\) の部分だけを新しい命題変数 \(r\) で置き換え, \(r \lor (q_1 \land q_2 \land q_3)\) に分配律を適用して CNF に変換する方法も考えられる. この場合の節の個数は6である.どんな論理式か.

Date:

Author: 田村直之

Org version 7.8.02 with Emacs version 24

Validate XHTML 1.0