数理論理学 第3回 茨城大学工学部情報工学科 佐々木 稔
前回までのあらすじ 論理式 真理値表 命題論理式の性質 配布資料は以下からダウンロードできます http://sas.cis.ibaraki.ac.jp/logic/
前回の問題 (p ⇒ q)∧(p ⇒ ～q)=～p を証明しなさい。
練習問題の解答例１ p q p⇒q q⇒~p (p⇒q)∧(q⇒~p) ~p T F
練習問題の解答例２ (p ⇒ q) ∧ (p ⇒ ～q) = ～p = (～p ∨ q) ∧ (～p ∨ ～q) = ((～p ∨ q) ∧ ～p) ∨ ((～p ∨ q) ∧ ～q) = (～p ∨ (q ∧ ～p)) ∨ ((～p ∧ ～q) ∨ F) = ～p ∨ (q ∧ ～p) ∨ (～p ∧ ～q) = ～p ∨ (～p ∧ (q ∨ ～q)) = ～p ∨ (～p ∧ T) = ～p ∨ ～p = ～p
練習問題の解答例３ (p ⇒ q) ∧ (p ⇒ ～q) = ～p = (～p ∨ q) ∧ (～p ∨ ～q) = ～p ∨ (q ∧ ～q) = ～p ∨ F = ～p
今週のお題 命題論理式の解釈 恒真式（トートロジー） 論理式の標準形 決定問題
命題論理式の解釈 命題論理式の値 真か偽の値をとる 式に含まれる基本命題の真偽で決まる 論理式を解釈する 論理式全体の真偽値を決める
解釈の例 2つの命題 p, q を考える このとき、 『「6は素数である」ならば、「太陽は西に沈ま」ない』 を考えると、 p は T q は F 『「6は素数である」ならば、「太陽は西に沈ま」ない』 を考えると、 q ⇒ ～p は T
解釈の例 p q p⇒q q⇒p ～(q⇒p) (p⇒q)⇒～(q⇒p) T F
恒真式（トートロジー） 命題変数の真偽値によらず常に真となる論理式 p を別の論理式で置き換えても成り立つ p ∨ ～p p ⇒ p (p ⇒ q) ∨ ～(p ⇒ q) (p ⇒ q) ⇒ (p ⇒ q) (p ⇒ q) ⇔ (p ⇒ q)
恒偽式 命題変数の真偽値によらず常に偽となる論理式 充足不能と呼ばれる 充足可能 p ∧ ～p = F 解釈によって真偽値が真になるものが存在
論理式の標準形 選言標準形と連言標準形（節形式） 選言標準形 連言標準形（節形式） 論理式の相互比較が簡単に行うことができる P = P1 ∨ P2 ∨・・・∨ Pn ただし、 Pi = pi1 ∧ pi2 ∧ ・・・∧ pim pij はリテラル（p か ～p のいずれかの形） 連言標準形（節形式） P = P1 ∧ P2 ∧ ・・・ ∧ Pn ただし、 Pi = pi1 ∨ pi2 ∨ ・・・ ∨ pim
標準形への変換アルゴリズム（1/2） 論理記号 ⇒、⇔ を ∨、∧ に変換 論理式の前にある否定記号を基本論理式の直前に移動する 含意の除去： P ⇒ Q = ～P ∨ Q 同値の除去： P ⇔ Q = (P∧Q)∨(～P∧～Q) 論理式の前にある否定記号を基本論理式の直前に移動する 二重否定：～（～p） = p ド・モルガンの定理 ～(p ∧ q) ＝ ～p ∨ ～q ～(p ∨ q) ＝ ～p ∧ ～q
標準形への変換アルゴリズム（2/2） 選言標準形、または連言標準形に変形する 論理式の性質を利用して簡単化する 分配律： p ∨ (q ∧ r) ＝ (p ∨ q) ∧ (p ∨ r) p ∧ (q ∨ r) ＝ (p ∧ q) ∨ (p ∧ r) 論理式の性質を利用して簡単化する
標準形への変換例1 選言標準形 連言標準形
標準形への変換例2 を連言標準形に書き換える
標準形への変換例3 を連言標準形に書き換える
決定問題 論理式が恒真式かどうか決定する問題 解法 真理値表 命題変数の数が多くなると手間がかかる 意味の木（semantic tree）
意味の木 論理式 P = (p1, p2, ・・・, pn) ひとつの命題変数に真偽を当てはめる 当てはめた論理式を簡単化する pi (i = 1, ・・・, n) は命題変数 ひとつの命題変数に真偽を当てはめる 真の場合、偽の場合に場合分け 当てはめた論理式を簡単化する 残りの命題変数について繰り返す
意味の木 pi ~pi
意味の木の例1 P ~P Q ~Q
意味の木の例2 P ~P Q ~Q
練習問題３ 次の論理式がトートロジーであるかどうかを意味の木を利用して判定せよ。 P ⇒ (Q ∨ ～R)