2005/04/20 志村先生 1. 命題論理 日常で用いられている命題を表現 ( 操作 ) することが目的 言語 ( 命題論理で用いられている記号 [ や、その生成規則 ] ) 命題変数 命題変数は、命題を表現する記号 命題変数は、小英文字で表現し、無限個あるとする p, q, r .. p_1, p_2, ... 論理記号 論理式を組合せて、新しい論理式を作るための記号(次の四つ) \and, \or, \imp, \not 補助記号 (括弧) (, ) # \imp は、「ならば」を表す # 「ならば」には、人によって、色々な流儀がある # \rightarrow は別の用途で用いたいので、ここでは \imp を使う 命題の種類 ( 二種類 ) 元になる命題 (原子命題 : atomic formula) 命題変数が表現している命題 これ以上分割できない命題 基本となる命題 # True/False が単独で決定される命題 (?) 複合化した命題 原子命題と論理記号により作られる命題 論理式の帰納的定義 ( 1 が 帰納法に於ける step 1, 2-5 が step 2 ) 1. 命題変数は論理式である 2. A, B が論理式ならば (A) \and (B) も論理式 3. A, B が論理式ならば (A) \or (B) も論理式 4. A, B が論理式ならば (A) \imp (B) も論理式 5. A が論理式ならば \not (A) も論理式 # [注意] A, B は、論理式を表現する「メタ変数」 『()』を付けるのは、論理記号の結合の関係を明確にするため # 上記の 2-5 の(論理式の構文)規則から解ること # => 論理記号は、必ず、論理式につけられた括弧の外につく 括弧を付けないと、2 から 5 の規則をどの順番に適用したか解らない [例 1] (\not (p)) \imp ((q) \and (r)) /\ / \ / \ / \imp \ / \ / \ \not (p) (q) \and (r) | /\ | / \ | / \ \not / \and \ | / \ p q r [例 2] (\not ((p) \imp (q)) \and (r) /\ / \ / \ / \and \ / \ / \ \not ((p)\imp(q)) r | | \not | | (p)\imp(q) /\ / \ / \ / \imp \ / \ p q しかし、括弧が沢山あるのは、人間にとって => 論理記号の優先順位(結合力の強さ)を付けることによって、 (不必要な..)括弧を省略する 省略法 ( 結合の優先順位 ) \not > \and > \or > \imp [例 1] \not p \imp q \and r [例 2] \not (p \imp q) \and r == 論理式の正しさ Bool 代数 \TWO \TWO = ( {0,1}, \cap, \cup, =>, ~, 1, 0 ) \cap, \cup, => は、 {0,1} 上の二項演算 x \cup y | 1 0 ---------+--------- 1 | 1 1 0 | 1 0 x \cap y | 1 0 ---------+--------- 1 | 1 0 0 | 0 0 x => y | 1 0 ---------+--------- 1 | 1 0 0 | 1 1 x | ~x ---------+--------- 1 | 0 0 | 1 [気持] 1 : 真 0 : 偽 \cup : or \cap : and => : ならば ~ : 否定 == # 論理式の真偽を決定するには.. 命題変数の真偽を决める必要がある しかし、実際には、命題変数が真や偽になるのは、その命題変数が表している 具体的な命題を知らなければ、决めることができない。 # 実際は、具体的に命題が確定しても、本当にそれから、真偽が決るという保証もない 形式的に、命題変数に、(その命題変数が何に対応するかを考えずに..) 真偽値を与える仕組を考える => 付値 付値 ( valuation ) v : 命題変数に 1 または 0 を対応させる関数 v(p) = 1 「命題変数 p が真」 v(q) = 0 「命題変数 q が偽」 # v は、命題変数にだけ、定義されていることに注意 # v の定義域は、命題変数の集合 付値 v の拡張 1. A が命題変数の時 v'(A) = v(A) 2. A が (B)\and(C) の形 # この表現は、次のことを意味する # 論理式の帰納的定義から.. # A は論理式 # B, C も論理式 # B, C は、A の「前」に定義されている # したがって、 # v'(B), v'(C) の値も、ここでは既に定義されているはず !! v'(A) = v'(B) \cup v'(C) 3. A が (B)\or(C) の形 v'(A) = v'(B) \cap v'(C) 4. A が (B)\imp(C) の形 v'(A) = v'(B) => v'(C) 4. A が \not(B) の形 v'(A) = ~ v'(B) # v'(A) を A の構成に関する帰納法で定義する 以下、v' を単に v で表現する # v' は v の定義域が拡大されただけなので、同じ記号で表してしまう。 # [ここまで] 数学入門の真偽表と命題論理の所を、きちんと書いただけ == 恒真式 論理式 A が恒真式 def 任意の付値 v に対しても、 v(A) = 1 となる # 普通の (恒真式でない..) 論理式 B は、通常、付値 v が変れば、 # 真にも偽にもなりうる [恒真式の例] A \imp A [A \imp A が恒真式であることの証明] v を勝手な付値とする v の定義により v(A \imp A) = v(A) => v(A) => の真偽表は =>| 1 0 --+----- 1 | 1 0 0 | 1 1 なので、v を v(A) の値で、場合分けし v(A) = 1 の時 v(A \imp A) = v(A) => v(A) = 1 => 1 = 1 v(A) = 0 の時 v(A \imp A) = v(A) => v(A) = 0 => 0 = 1 よって、いずれの場合も v(A \imp A) = 1 即ち、 A \imp A は恒真式 恒真式の例 A \and \not A A \imp ( B \imp A ) (A \imp (B \imp C)) \imp ((A \imp B) \imp (A \imp C)) A \and B \imp A, A \and B \imp B (A \imp B) \and (A \imp C) \imp (A \imp (B \and C)) A \imp B \or A, B \imp B \or A (A \imp C) \and (B \imp C) \imp (A \and B \imp C)) (A \imp B) \and (A \imp \not B) \imp \not A # A \equ B で (A \imp B)\and(B \imp A) を表す (同値の記号) # この記号は、\imp より、結合力が小さい A \and B \equ B \and A A \or B \equ B \or A A \and (B \and C) \equ (A \and B) \and C A \or (B \or C) \equ (A \or B) \or C == [問題] 論理式 A が与えられた時、 A が恒真式 かどうかを判定できるか ? # 具体的に A に含まれる論理変数の個数が有限個 n ならば、その # 命題変数にそれぞれ真/偽を当てて、その組合せ ( 2^n ) を調べれば済む # しかし、一般に、付値 v は、無限個ある命題変数へ、0,1 を割り当てるので # v 自身も無限のバリエーションがある。これの全てを調べることはできない。 [補題] 論理式 A と付値 v1, v2 が与えられたとき A に現れる任意の 命題変数 p に対して v_1(p) = v_2(p) ならば v_1(A) = v_2(A) である。 [証明] A の構成に関する帰納法による 1. A が命題変数 p の時 v_1(A) = v_1(p) = v_2(p) = v_2(A) 2. A が B \and C の形の時 B に現れる命題変数 と C に現れる命題変数 は、A にも現れる したがって、 B に現れる任意の命題変数 p について v_1(p) = v_2(p) C に現れる任意の命題変数 p について v_1(p) = v_2(p) よって、帰納法の仮定により v_1(B) = v_2(B) v_1(C) = v_2(C) これより、 v_1(A) = v_1(B) \cap v_1(C) = v_2(B) \cap v_2(C) = v_2(B) 他の場合 2-5 に関しても同様。 # 上記の[補題]を利用することにより、[問題]に関しては次のようなことが解る A に現れる命題変数を p_1, p_2, .., p_n とすれば 2^n 個の付値 v に対して v(A)=1 を確かめれば、A の恒真性を確認できる => 真理表による恒真式の判定 [例] (p \imp (q \imp r)) \imp (q \imp (p \imp r)) v(p) 1 1 1 1 0 0 0 0 v(q) 1 1 0 0 1 1 0 0 v(r) 1 0 1 0 1 0 1 0 v(q \imp r) 1 0 1 1 1 0 0 0 v(p \imp r) 1 0 1 0 1 1 1 1 v(p \imp (q \imp r)) 1 0 1 1 1 1 1 1 == しかし、現実の世界では、人間は、真偽表を考えることは殆どない 普通は「証明」する # 場合分けの時に真偽表を使うことはたまにあるが.. 真偽表は、面倒クサい ( なぜなら、2^n なので、直に表が爆発する !! ) # 真偽表は、論理式の外 ( 付値と、真偽表.. ) で、真偽を判定している # 「恒真式である」ことと「証明できる」ことの間には、どのような関係があるだろうか ? A が恒真式 ( 意味論的な概念 ) A が証明できる ( 構文論的な概念 ) # 「証明をする」ということは.. ? 次のような「推論」を行うこと ## 以下の図は、「推論形式」を表している A, A \imp B ----------- A と A \imp B が成立すれば B が成立する B A \imp B, B \imp C ------------------ A から B が導け、B から C が導ける A \imp C ならば A から C が導ける A, B -------- A と B が共に正しければ、A \and B も正しい A \and B [証明] 基本となる「正しい」論理式から推論を適用していって、新な「正しい」論理式を導く過程 # 基本となる「正しい」論理式を普通「公理」と呼ぶ == 次回 真理表とは、別の方法で証明できる論理式の概念を定め、それが恒真 式と一致していることを示す