数理論理学第2回

数理論理学第2回
茨城大学工学部情報工学科
佐々木稔
前回までのあらすじ




命題
基本命題
複合命題
命題変数
 配布資料は以下からダウンロードできます
 http://sas.cis.ibaraki.ac.jp/logic/
前回の問題
 以下の各文に対し、日常生活における常識
から考えて、命題として適当かどうか判別しま
しょう。また、判別した理由も記述してください。
a. 太郎は日本人である。
b. 三角形 ABC は正三角形である。したがって、そ
の各内角は60度である。
c. この文書の意味が分かる人はここにいますか？
d. 昼間である、もしくは、空が曇っているならば、星
は見えない．
前回の問題
a. 太郎は日本人である。
適当
b. 三角形 ABC は正三角形である。したがって、その各内
角は60度である。
適当
c. この文書の意味が分かる人はここにいますか？
適当ではない
d. 昼間である、もしくは、空が曇っているならば、星は見えな
い。
適当
今週のお題
 論理式
 真理値表
 命題論理式の性質
論理式
 いくつかの命題変数を論理記号で結び付けた
もの
 表記
 P、 Q、 R、 …(大文字の記号)
例
 P:「彼は8月の最初の週に生まれた」
 Q:「彼は獅子座だ」
 R:「三角形 ABC は正三角形である」
論理記号(1/2)
 選言、論理和 (or)
 p∨q、
p または q
 連言、論理積 (and)
 p∧q、
p かつ q
 否定 (not)
 ～p、￢p
 排他的論理和 (xor)
 p
q
論理記号(2/2)
 含意 (implicature)
 p ⇒ q、 p ならば q、 q⊃p
 同値 (equivalence)
 p ⇔ q、 p ならば q、かつそのときに q ならば p、
 p≡q
論理式の例
 P:「今日は木曜日、または金曜日である。」
 p:「今日は木曜日である。」
 q:「今日は金曜日である。」
 P=p∨q
 Q:「彼は8月の最初の週に生まれたのだから、
彼は獅子座だ。」
 r:「彼は8月の最初の週に生まれた」
 s:「彼は獅子座だ」
 Q=r⇒s
真理値表
 論理式とその真偽値との対応表
 複雑な論理式の真理値を求めるときに有効
p
～p
T
F
F
T
真理値表(これらは覚えておきましょう)
p q
p∨q
p∧q
p⇒q
p⇔q
T T
T
T
T
T
F
T F
T
F
F
F
T
F T
T
F
T
F
T
F
F
F
T
T
F
F
p
q
真理値表
p
q p⇒q q⇒p ～(q⇒p) (p⇒q)⇒～(q⇒p)
T
T
T
T
F
F
T
F
F
T
F
T
F
T
T
F
T
T
F
F
T
T
F
F
命題論理式の性質(1/7)
1. 同一律
 p ∨ p ∨・・・∨ p ＝ p
 p ∧ p ∧・・・∧ p ＝ p
 p⇔p
2. 交換律
 p∨q＝q∨p
 p∧q＝q∧p
命題論理式の性質(2/7)
3. 結合律
 (p ∨ q) ∨ r ＝ p ∨ (q ∨ r)
 (p ∧ q) ∧ r ＝ p ∧ (q ∧ r)
4. 分配律
 p ∨ (q ∧ r) ＝ (p ∨ q) ∧ (p ∨ r)
 p ∧ (q ∨ r) ＝ (p ∧ q) ∨ (p ∧ r)
命題論理式の性質(3/7)
5. ド・モルガンの定理
 ～(p ∧ q) ＝～p ∨ ～q
 ～(p ∨ q) ＝～p ∧ ～q
6. 吸収律
 p ∧ (p ∨ q) ＝ p
 p ∨ (p ∧ q) ＝ p
7. 二重否定
 ～～p = p
命題論理式の性質(4/7)
8. 排中律
 p ∨ ～p = T
9. 矛盾律
 p ∧ ～p = F
10.真偽の性質




T
T
F
F
∧
∨
∧
∨
p
p
p
p
＝
＝
＝
＝
p
T
F
p
命題論理式の性質(5/7)
11.含意の除去
 p ⇒ q = ～p ∨ q = ～(p ∧ ～q)
12.同値の除去
 p ⇔ q = (p ⇒ q) ∧ (q ⇒ p)
= (p ∧ q) ∨ (～p ∧ ～q)
13.推移律
 ((p ⇒ q) ∧ (q ⇒ r)) ⇒ (p ⇒ r)
 ((p ⇔ q) ∧ (q ⇔ r)) ⇒ (p ⇔ r)
命題論理式の性質(6/7)
14.背理法
 p ⇒ ～p = ～p
15.対偶
 p ⇒ q = ～q ⇒ ～p
16.同値の性質
 p ⇔ q = ～p ⇔ ～q
 ～(p ⇔ q) = (p ⇔ ～q)
命題論理式の性質(7/7)
17.含意の性質




T
F
p
p
⇒
⇒
⇒
⇒
p
p
T
F
＝
＝
＝
＝
p
T
T
～p
論理式の簡単化
＝
＝
＝
＝
～((p ⇒ q) ⇒ ～(q ⇒ p))
～(～(p ⇒ q) ∨ ～(q ⇒ p))
※ 11.含意の除去
～～(p ⇒ q) ∧ ～～(q ⇒ p)
※ 6.ド・モルガンの法則
(p ⇒ q) ∧ (q ⇒ p)
※ 7.二重否定
p⇔q
※ 12.同値の除去
論理式の簡単化
((～p ∨ q) ∨ r) ∧ ((q ∨ r) ⇒ s)
＝ (～p ∨ (q ∨ r)) ∧ ((q ∨ r) ⇒ s)
※ 3.結合律
＝ (p ⇒ (q ∨ r)) ∧ ((q ∨ r) ⇒ s)
※ 11.含意の除去
＝p⇒s
※ 13.推移律
練習問題
 (p ⇒ q)∧(p ⇒ ～q)=～p を証明しなさい。
練習問題の解答例１
p q p⇒q q⇒~p
(p⇒q)∧(q⇒~p)
~p
T T
T
F
F
F
T F
F
T
F
F
F T
T
T
T
T
F F
T
T
T
T
練習問題の解答例２
 (p ⇒ q) ∧ (p ⇒ ～q)
=
=
=
=
=
=
=
(～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 ∨ q) ∧ (～p ∨ ～q)
= ～p ∨ (q ∧ ～q)
= ～p ∨ F
= ～p

Download Report