プログラマの数学の2章を読んで論理値再入門した
- 作者: 結城浩
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2005/03/24
- メディア: 大型本
- 購入: 41人 クリック: 707回
- この商品を含むブログ (396件) を見る
結城浩さんの本。非常に分かりやすく解説してくれている。
その中でも論理式を整理する、ド•モルガンの法則とカルノー図の説明が分かりやすかった。こういうのは情報処理試験以来。すぐ思い出せるように、自分用のメモがてら少し紹介する。
(雑な説明なのは、僕のせいです。本書はクオリティ高いです。)
ド•モルガンの法則
高校生の数学で出てきたはず。真、偽、論理和、論理積の関係を反転させることで、式の変換ができるってやつ。
公式
(¬A)∨(¬B) = ¬(A∧B) (¬A)∧(¬B) = ¬(A∨B)
確かめてみる
rspecで確かめてみた。
- コード
describe 'ドモルガンテスト' do describe '!a || !b == !(a && b)' do [true, false].each do |a| [true, false].each do |b| context "a:#{a}, b:#{b}" do subject { !a || !b } let(:expect_result) { !(a && b) } it { expect(subject).to eq expect_result } end end end end describe '!a && !b == !(a || b)' do [true, false].each do |a| [true, false].each do |b| context "a:#{a}, b:#{b}" do subject { !a || !b } let(:expect_result) { !(a && b) } it { expect(subject).to eq expect_result } end end end end end
- 結果
▶ rspec --format documentation --color ドモルガンテスト !a || !b == !(a && b) a:true, b:true should eq false a:true, b:false should eq true a:false, b:true should eq true a:false, b:false should eq true !a && !b == !(a || b) a:true, b:true should eq false a:true, b:false should eq true a:false, b:true should eq true a:false, b:false should eq true Finished in 0.00453 seconds (files took 0.18092 seconds to load) 8 examples, 0 failures
OK。
ところで公式覚えるの大変なんだけど
って高校生の時の僕は絶対思ってた。
それが、双対性という性質を使うともはや公式を覚える必要はない。
双対性とは互いに対になっている2つの対象の間の関係のこと。(wikipediaより。http://ja.wikipedia.org/wiki/%E5%8F%8C%E5%AF%BE)
ここでは下記のような関係になる。
- A ⇆ ¬A
- B ⇆ ¬B
- ∧ ⇆ ∨
この関係を論理値の全ての項にそれぞれ当てはめると、元の式の否定を作ることができる。
つまりA∨B
の否定は(¬A)∧(¬B)
になる。
つまり¬(A∨B) = (¬A)∧(¬B)
が成り立つことになる。
これぞまさにド•モルガンの法則だ。
カルノー図
論理積で構成される各項を、論理和でつなげているような論理式を整理するのに役立つ手法。
と字で書くと難しいけど、プログラムではよくある。
こんな感じのやつ。
if (a && b) || (a && !b) || (!a && !b) # ここに処理書いたりする end
こういう複雑な式を単純化できる。
やってみる
試しに下記の式を単純化してみる。
(a && b) || (a && !b) || (!a && !b)
これは、下記のいずれかの条件に適合する場合にtrueということだ。
a && b a && !b !a && !b
まずは全ての組み合わせを表で表す。
こうなる。
a/b | True | False |
---|---|---|
True | ○ | ○ |
False | ○ |
先ほど出した3つの条件を見て、それぞれ当てはまるところに○を入れている。
これでカルノー図は完成だ。
単純化する
まず上の式で、aがtrueの場合の時を見てみる。
すると、Aがtrueの時は必ず条件に適合しているということが分かる。
次にBがfalseの時を見てみる。
すると、Bがfalseの時は必ず条件に適合していることが分かる。
そして、これで全ての○を網羅している。
つまり(a && b) || (a && !b) || (!a && !b)
はa || !b
と単純化できることになる。
確かめてみる
これもrspecで確かめてみた。
- コード
describe 'カルノー図テスト' do describe '(a && b) || (a && !b) || (!a && !b) == a || !b' do [true, false].each do |a| [true, false].each do |b| context "a:#{a}, b:#{b}" do subject { (a && b) || (a && !b) || (!a && !b) } let(:expect_result) { a || !b } it { expect(subject).to eq expect_result } end end end end end
- 結果
▶ rspec --format documentation --color カルノー図テスト (a && b) || (a && !b) || (!a && !b) == a || !b a:true, b:true should eq true a:true, b:false should eq true a:false, b:true should eq false a:false, b:false should eq true Finished in 0.00507 seconds (files took 0.26202 seconds to load) 4 examples, 0 failures
OK。
終わりに
言い訳をすると、僕は文系出身のプログラマなので、数学は苦手だ。もっと正直に言えば、怠けていたので数学ができない。
こんな僕でも楽しく数学再入門させてくれる本書は、すごく良い本だと思う。