プログラマの数学の2章を読んで論理値再入門した

プログラマの数学

プログラマの数学

結城浩さんの本。非常に分かりやすく解説してくれている。

その中でも論理式を整理する、ド•モルガンの法則とカルノー図の説明が分かりやすかった。こういうのは情報処理試験以来。すぐ思い出せるように、自分用のメモがてら少し紹介する。

(雑な説明なのは、僕のせいです。本書はクオリティ高いです。)

ド•モルガンの法則

高校生の数学で出てきたはず。真、偽、論理和論理積の関係を反転させることで、式の変換ができるってやつ。

公式

(¬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。

終わりに

言い訳をすると、僕は文系出身のプログラマなので、数学は苦手だ。もっと正直に言えば、怠けていたので数学ができない。

こんな僕でも楽しく数学再入門させてくれる本書は、すごく良い本だと思う。