情報数学１ 第5-1章 命題論理式の論理演算と真偽値 香川大学工学部 富永浩之 [email protected] 概 要 ■ 命題と真偽値 真偽値 真・偽 素命題 複合命題 論理結合子 命題変数 命題定数 論理演算子 論理式 ■ 論理演算子の意味と真偽値 否定・連言・選言・含意・環和・同値 ■ 部分式構成によるボトムアップの真偽値計算 命題変数への割当 論理式の真偽値表 部分式構成 ボトムアップ 部分評価 カルノー表 ドントケア表記 ■ 部分式分解によるトップダウンの真偽値計算 部分式分解 AND/OR分岐 トップダウン 第01節 [1] 命題と真偽 ● 命題と真偽 命題 真偽 意味内容が明確で、真偽を定め得る言明 (平叙文) 真 (正しい) と 偽 (正しくない) 真「14は7で割り切れる」 偽「3は偶数である」 素命題 複合命題 論理結合子 単文で表される最小単位の命題 素命題を論理結合子で組み合わせた複雑な命題 命題の組合せに用いる接続語句を抽象化したもの かつ または でない ならば ● 記号論理学≒数理論理学 記号論理学 論理概念を抽象的に捉え、記号で表現 数理論理学 論理の一般的な性質を数学的な手法で研究 論理式 命題 真偽値 真偽 命題変数 素命題 論理演算子 論理結合子 第01節 [2] 命題変数と真偽値 ● 真偽値 ● 命題変数 第01節 [3] 論理演算子 演算の名称 英語名 記号 読み方 英語表現 意味 他の記法 否定 negation ￢ P Pでない not P Pが成立しないとき成立 ～ P 連言(論理積) conjunction P ∧ Q PかつQ P and Q PとQのどちらもが成立 P ＆ Q P ・ Q 選言(論理和) disjunction P ∨ Q PまたはQ P or Q PとQの 少なくとも一方が成立 P ｜ Q P ＋ Q 環和 (排他的論理和) exclusive or P ▽ Q PとQの一方 P xor Q PとQの どちらか一方のみ成立 含意 implication P → Q PならばQ Pが成立するときは 必ずQも成立 P ⇒ Q P ⊃ Q 同値 equivalence P △ Q PとQは同値 P iff Q PもQも同時に 成立か不成立 P ⇔ Q P ≡ Q P imply Q 第01節 [4] 論理学の歴史と発展 古典論理学 古代ギリシャ 哲学的議論の基礎 アリストテレスが集大成 中世論理学 中世ヨーロッパ 神学やスコラ哲学の基礎 神の存在証明 記号論理学 記号論理 17世紀後半～ 科学革命と共に ライプニッツが記号を発明 数学的手法の導入 数理論理学 19世紀後半～ 数学の基礎付として 解析学(無限の定義) 集合論(逆理の回避) 証明の形式化 情報論理学 20世紀前半～ 計算機の原理として ブール代数と論理回路 計算モデル 人工知能と自動推論 第02節 [1] 連言と選言 ● 連言 (合接) 論理積 AND P∧Q PかつQ P and Q P と Q の両方が成り立つ 交換律 結合律 冪等律 P∧Q と Q∧P は、論理的に等しい (P∧Q)∧R と P∧(Q∧R) は、論理的に等しい (括弧を省略できる) P∧P は P に、論理的に等しい ● 選言 (離接) 論理和 OR P∨Q PまたはQ P or Q P と Q の少なくとも一方が成り立つ 交換律 結合律 冪等律 P∨Q と Q∨P は、論理的に等しい (P∨Q)∨R と P∨(Q∨R) は、論理的に等しい (括弧を省略できる) P∨P は P に、論理的に等しい 双対性 連言と選言の性質は類似 第02節 [2] 否定と含意 ● 否定 論理否定 NOT ￢P Pでない not P P が成り立たない 右結合 対合律 ￢￢P は ￢(￢P) を表す 二重否定 ￢￢P は P に論理的に等しい ● 含意 (仮言) 論理含意 IMP P→Q PならばQ P が成り立つとき Q も成り立つ P が成り立たないとき Q の真偽はどちらでもよい 非対称 右結合 P→Q と Q→P は、論理的に異なる P→Q→R は P→(Q→R) に、論理的に等しい P imp Q 第02節 [3] 環和と同値 ● 環和 排他的論理和 XOR P▽Q P と Q のどちらか一方が成り立つ 両方が成り立つときは偽になる 包括的論理和 P∨Q と混同しない 交換律 結合律 ● 同値 PかQ P xor Q コーヒーか紅茶が付く 両方× 排他的 XOR 砂糖かミルクを入れる 両方○ 包括的 OR P▽Q と Q▽P は、論理的に等しい (P▽Q)▽R と P▽(Q▽R) は、論理的に等しい (括弧を省略できる) 論理的同値 EQU P△Q PすなわちQ P iff Q P と Q は真偽が一致する 両方が成り立つか、両方が成り立たない 両向きの含意であり、 P→Q かつ Q →P である 交換律 結合律 P△Q と Q△P は、論理的に等しい (P△Q)△R と P△(Q△R) は、論理的に等しい (括弧を省略できる) 第03節 [1] 論理演算子と真偽値 否定 1 ; P 0 P 0 ; P 1 連言 1 ; P Q 1 PQ else 0 ; P∧Q Q 0 Q 1 P 0 0 0 P 1 0 1 選言 0 ; P Q 0 PQ else 1 ; P∨Q Q 0 Q 1 P 0 0 1 P 1 1 1 含意 0 ; P 1, Q 0 P Q else 1 ; P→Q Q 0 Q 1 P 0 1 1 P 1 0 1 環和 1 ; P Q P▽Q 0 ; else P▽Q Q 0 Q 1 P 0 0 1 P 1 1 0 同値 1 ; P Q PQ 0 ; else P△Q Q 0 Q 1 P 0 1 0 P 1 0 1 第04節 [1] 割当による論理式の真偽値 論理式 A を構成する各命題変数の真偽値を与えると、A 全体の真偽値も定まる。 論理式の真偽値を定める命題変数の真偽値の組を割当て[valuation]という。 与えられた割当てに対し、論理式 A の真偽値を求めるには、 各論理演算子の定義に従って計算していく。 |(Ｐ∨￢Ｑ)→(Ｒ∨Ｐ∧Ｑ)| <|P|,|Q|,|R|>＝<0,0,1> のとき、与式の真偽値？ － － － － － ０ │０ １ ０ ０ 第0ステップ 命題変数への真偽値の代入 │ └┘ │ └─┘ │ １ │ ０ ① └──┘ └──┘ １ １ ② └─────┘ １ ③ 最後に適用する論理演算子での値が式全体の値 ──────────── |(Ｐ∨￢Ｑ)→(Ｒ∨Ｐ∧Ｑ)| ＝ １ ②① ③ ② ① ステップ ０１１０ １ １１０００ 各部分式の値 (ステップごとの計算を1行にまとめたもの) 第04節 [2] 論理式の真偽値表 論理式の性質を調べるには、 全ての割当てに対してその論理式の真偽値を調べてみる必要がある。 具体的には、命題変数の真偽値の全ての組合せを列挙し、 各割当てに対して部分から全体へと論理式の真偽値を計算していく。 その過程および結果を表として記述したものが真偽値表[truth value table]である。 ステップ ２ ０ １０ ￢ (P ∧ Q) ３ → ０２ １０ P Q 0 0 1 0 0 0 1 0 1 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 1 0 0 1 1 1 1 0 0 1 0 1 1 1 1 1 1 0 1 P0 P1 Q0 1 1 Q1 0 1 (P ∨￢ Q) 真偽値表の結果である論理式の真偽値の一覧については、 カルノー表で図示すると視覚的にも分かりやすい。 ただし、カルノー表において、命題変数の真偽値の組合せは、 00, 01, 11, 10 のように、グレイ符号の順に並べる。 こうすると、命題変数ごとに真の部分および偽の部分の領域が連結するようになる。 第05節 [1] 論理式構成による真偽値表の求め方 論理式の真偽値表において、命題変数の真偽値の全ての組合せを重複も漏れもなく列 挙するには、P,Q,Rの真偽値の並びをビット列とみて、 二進数のインクリメントと同様に0と1を当てはめていけばよい。 また、図表のステップ欄のように、真偽値を求める順序を明記しておくとよい。 ただし、n個の命題変数を含む論理式では、2^n通りの真偽値の組を調べなければなら ない(n＝4で、16通り)。nが大きくなれば、実際に真偽値表を作成するのは困難である。 ステップ ０ １０ P Q R (P ∨ Q) ４ ０ ３ ０ ２ １ ０ P0 → (R ∨ ( P ∧ ￢ Q)) P1 R0 R1 R1 R0 0 0 0 0 0 0 1 0 0 0 0 1 0 Q0 1 1 1 1 0 0 1 0 0 0 1 1 1 0 0 1 0 Q1 0 1 1 0 0 1 0 0 1 1 0 0 0 0 0 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 第05節 [1] 論理演算の部分評価 連言 選言 含意 0 ; P 0 PQ Q ; else P∧Q P 0 P 1 Q 0 0 0 Q 1 0 1 1 ; P 1 PQ Q ; else P∨Q P 0 P 1 Q 0 0 1 Q 1 1 1 1 ; P 1 PQ Q ; else P→Q P 0 P 1 Q 0 1 0 Q 1 1 1 第05節 [2] ドントケア表記 [1] で真、[0] で偽となる任意の論理式を表し、[*] は真偽どちらでもよいことを表す。 [*] のように、真偽値を不定のままにしておく記法をドントケア表記[don't care notation]という。 これらの性質を用いると、真偽値表の作成過程において、部分式の不要な計算を省略できる。 ○ 連言 |[0]∧[*]| ＝ |[*]∧[0]| ＝ 0 一方が偽ならば他方に関らず偽 ○ 選言 |[1]∨[*]| ＝ |[*]∨[1]| ＝ 1 一方が真ならば他方に関らず真 ○ 含意 |[0]→[*]| ＝ |[*]→[1]| ＝ 1 前件が偽または後件が真ならば他方に関らず真 一般に、引数の一部のみの値で全体の値が求まることを部分評価[partial evaluation]という。 連言は偽のとき、選言と含意は真のとき、部分評価が行える。 部分評価は、プログラム言語における計算にも関連する。 C言語のコード if ( p != 0 && n%p == 0 ) { return p; } で、 p＝0 のときもエラーにならないのは、C言語の論理演算子 && が部分評価だからである。 なお、関数は部分評価ではないため、論理演算子 AND, OR を関数で定義することはできない。 関数として my_and(x, y) { return x && y; } と定義しても、 my_and(p!=0, n%p==0) と呼び出すと、第2引数でエラーとなる。 第05節 [3] ドントケア表記による真偽値表の解法 論理式の真偽値表において、命題変数の真偽値の全ての組合せを重複も漏れもなく列 挙するには、P,Q,Rの真偽値の並びをビット列とみて、 二進数のインクリメントと同様に0と1を当てはめていけばよい。 また、図表のステップ欄のように、真偽値を求める順序を明記しておくとよい。 ただし、n個の命題変数を含む論理式では、2^n通りの真偽値の組を調べなければなら ない(n＝4で、16通り)。nが大きくなれば、実際に真偽値表を作成するのは困難である。 ステップ ０ １０ P Q R (P ∨ Q) ４ ０ ３ ０ ２ １ ０ → (R ∨ ( P ∧ ￢ Q)) 0 0 0 0 0 0 1 ＊ 0 0 1 0 0 0 1 ＊ 0 1 0 ＊ 1 1 0 0 0 0 1 1 ＊ 1 1 1 1 1 1 0 0 1 1 ＊ 1 0 1 1 0 1 1 1 ＊ 1 1 1 1 1 0 1 1 ＊ 0 0 0 1 1 1 1 1 ＊ 1 1 1 0 0 ＊ ＊ 1 1 1 0 0 1 ＊ 1 0 ＊ 論与式の前提部 P∨Q が偽となるとき、 与式は真となるので、帰結部 R∨(P∧￢Q) の 真偽値を求める必要はない。 P∨Qが真のとき、与式の真偽値は、 R∨(P∧￢Q) の真偽値に等しくなる。 さらに、R が真のとき、 第2部分式 P∧￢Q の真偽値によらず、真となる。 Rが偽のとき、 P∧￢Q の真偽値が与式の真偽値に等しくなる。 第06節 [1] 論理演算の引数への分解 連言 選言 |P∧Q|＝1 |P∨Q|＝1 AND |P|＝1 |Q|＝1 |P∧Q|＝0 OR |P|＝0 OR |P|＝1 |Q|＝1 |P∨Q|＝0 |P|＝0 |P→Q|＝1 否定 |￢P|＝1 OR AND |Q|＝0 含意 |Q|＝0 |P|＝0 |Q|＝1 |P→Q|＝0 |P|＝0 |￢P|＝0 AND |P|＝1 |Q|＝0 |P|＝1 ・ 論理演算の真偽値を、引数の真偽値の AND/OR で表す ・ 真(1)になるときと、偽(0)になるときで分ける 第06節 [2] 部分式分解による真偽値表の解法 |(P→Q)∨(￢Q∧R)|＝1 |(P∨Q)∧￢(Q→R)|＝1 OR AND |P→Q|＝1 |￢Q∧R|＝1 OR AND |P|＝0 |Q|＝1 |￢Q|＝1 |P∨Q|＝1 |￢(Q→R)|＝1 OR |R|＝1 |P|＝1 |Q|＝1 |Q→R|＝0 AND |Q|＝0 (P→Q)∨(￢Q∧R) 与式が真となるのは P→Q が真 ① または ￢Q∧R が真 ② ①のとき、Pが偽またはQが真 ②のとき、Qが偽かつRが真 よって、領域①と②の合併部分 P0 Q0 Q1 R0 ① ① |Q|＝1 (P∨Q)∧￢(Q→R) 与式が真となるのは P∨Q が真 ① かつ ￢(Q→R) が真 すなわち Q→R が偽② ①のとき、PまたはQが真 ②のとき、Qが真かつRが偽 よって、領域①と②の共通部分 P1 R1 R1 R0 ①② ② ① ① ① |R|＝0 P0 R0 Q0 Q1 P1 R1 ①② ① R1 ① ① R0 ① ①② 第08節 [3] トップダウンによる真偽値表の解法 全ての割当てに対して論理式の真偽値表を求める過程を逆に見ると、 与えられた論理式を真とするような割当てを求める操作にもなっている。 前者が数式への値の代入に相当するのに対し、後者は方程式を解くことに相当する。 与えられた論理式を真とするような割当ては、 論理式の構成に従って全体から部分へと分解し、トップダウンに求めていく。 ただし、素領域からのカルノー表の再構成は、逆向きのボトムアップとなる。 [1] 対象とする論理式の最も外側にある論理演算子に着目し、 その引数となっている各部分式に対し、 [2] 論理演算子の性質から満たすべき真偽値の可能性を場合分け条件として与え、 [3] より簡単な論理式の真偽値を考える問題に帰着させる。 「かつ」と「または」を混同しないように注意する。 [4] 求まった条件を組み合わせて再構成し、 領域に関する集合演算と同様にしてカルノー表に図示していく。 第09節 [1] 環和と同値の引数による分解 環和 同値 |P▽Q|＝1 |P△Q|＝1 OR OR |P∧￢Q|＝1 |￢P∧Q|＝1 AND |P|＝1 AND |￢Q|＝1 |￢P|＝1 |Q|＝0 |P|＝0 |P∧Q|＝1 |￢P∧￢Q|＝1 AND |Q|＝1 |P|＝1 AND |Q|＝1 |P▽Q|＝0 OR |P|＝0 |￢Q|＝1 |P|＝0 |Q|＝0 |P△Q|＝0 AND |P∧￢Q|＝0 |￢P|＝1 AND |￢P∨Q|＝0 |P∧Q|＝0 OR |￢Q|＝0 |￢P|＝0 |Q|＝1 |P|＝1 OR |Q|＝0 |P|＝0 |￢P∧￢Q|＝0 OR |Q|＝0 |￢P|＝0 |￢Q|＝0 |P|＝1 |Q|＝1
© Copyright 2024 ExpyDoc
