離散数学Ｉ 第3回 茨城大学工学部 佐々木稔
今回のお話 命題
命題 命題 例 明確に真（T = true）か偽（F = false）かが判断できる文 「 10 は円周率 π の良い近似値である」 「 10 は円周率 π の良い近似値である」 10 =3.162277… , π = 3.141592… 良い近似値だと思う人と思わない人がいる 「 10 < π である」 誰もが明らかに誤り（偽）と判断できる
集合による命題の表現 「x は π の良い近似値である」 「x は π より小さい」 {x∈R: x は π の良い近似値である} 人によって判断が異なるため、集合にならない 「x は π より小さい」 {x∈R: x < π} 集合を成しているので、 10 が入らないと断定できる
論理和・論理積 2つの命題 P, Q から、論理和と論理積を定義 論理和 P∨Q 論理積 P∧Q 否定 ￢P
例題2.1 自然数 n についての2つの命題 P =「n は偶数である」と Q =「n は3の倍数である」に対して、P∧Q, P∨Q, ￢P を簡潔に述べよ。
例題2.1 自然数 n についての2つの命題 P =「n は偶数である」と Q =「n は3の倍数である」に対して、P∧Q, P∨Q, ￢P を簡潔に述べよ。 P∧Q = 「n は偶数で、かつ3の倍数である」 P∨Q = 「n は偶数か、または3の倍数である」 ￢P = 「n は偶数ではない」 = 「n は奇数である」
例題2.2 2つの命題 P, Q に対して、次のドモルガンの法則が成り立つことを示せ。ここで、否定記号￢ は ∨や∧より優先され、括弧を省略することができる。
例題2.2 2つの命題 P, Q に対して、次のドモルガンの法則が成り立つことを示せ。 全体集合を U, 命題 X を真とする要素の集合を X とする。￢X が真となる要素の集合は ￢(P∨Q ) が真となる要素の集合は 𝑃∪𝑄 に対応 例題1.2より、 𝑃∪𝑄 = 𝑃 ∩ 𝑄 であるから、最初の等号が成り立つ。同様に、2つ目も成り立つ。
論理 複雑な命題に含まれる論理演算子 「P ならば Q」、「P ⇒ Q」 論理和、論理積、否定、「～ならば～」 「もし整数xが3の倍数なら、2xは6の倍数である」 「もし P(x) が成り立てば、Q(x) も成り立つ」 P(x) が真となる x について、Q(x) の真偽を問う 仮定部分が偽の場合は、結論部分の真偽は問題にせず、全体的に真となる
真理値表 個別の命題 P, Q の真偽の組合せを考える p ～p T F 各組合せに対し、複合命題全体の真偽を求める 真理値表を作成して、全体の真偽を求める p ～p T F
真理値表 p q p∨q p∧q p⇒q p⇔q p q T F
￢P∨Q の真理値表 P Q ￢P ￢P∨Q T F
命題論理の性質 2つの命題 P⇒Q, ￢P∨Q の真理値表 どの組合せでも、どちらも同じ結論 2つの命題は同値である P⇒Q = ￢P∨Q
今日の練習問題 18ページ 問題2.2 (1)～(4) 18ページ 問題2.3 20ページ 問題2.5 18ページ 問題2.2 (1)～(4) 18ページ 問題2.3 20ページ 問題2.5 提出用紙に学籍番号、氏名、答案を書いて、できれば提出してください。