論理回路シミュレータ

@season1618

自己紹介

  • 所属

    • 情報理工1年
    • アルゴリズム班(競プロやってない)
    • CTF班(CTFやってない)
  • じゃあ何をやってるのか

    • わ、わかんないッピ...

論理回路シミュレータを作った

主な機能

  • 論理回路を作ると真理値表ができる。
  • 真理値表を作ると論理回路ができる。
    • DNF: 選言標準形
    • CNF: 連言標準形
    • minimize: 最小化(クワイン・マクラスキー法)

サイト: https://season1618.github.io/logic-circuit/
リポジトリ: https://github.com/season1618/logic-circuit

遊び

真理値表にグレイコードを突っ込んだ様子。
特に意味はない。

グレイコードとは、数値の符号化法のひとつで、前後に隣接する符号間のハミング距離が必ず1であるという特性を持つ。
Wikipedia

クワイン・マクラスキー法

論理式を簡単化するアルゴリズム

選言標準形で

aˉbcˉdˉ+abˉcˉdˉ+abˉcˉd+abˉcdˉ+abˉcd+abcˉdˉ+abcd\bar{a}b\bar{c}\bar{d} + a\bar{b}\bar{c}\bar{d} + a\bar{b}\bar{c}d + a\bar{b}c\bar{d} + a\bar{b}cd + ab\bar{c}\bar{d} + abcd

を簡単化する。

step 1.まとめられるやつを全部まとめる

  1. aˉbcˉdˉ\bar{a}b\bar{c}\bar{d}
  2. abˉcˉdˉa\bar{b}\bar{c}\bar{d}
  3. abˉcˉda\bar{b}\bar{c}d
  4. abˉcdˉa\bar{b}c\bar{d}
  5. abˉcda\bar{b}cd
  6. abcˉdˉab\bar{c}\bar{d}
  7. abcdabcd
  • bcˉdˉb\bar{c}\bar{d} 1,6

aˉbcˉdˉ+abcˉdˉbcˉdˉ\bar{a}b\bar{c}\bar{d} + ab\bar{c}\bar{d} \rightarrow b\bar{c}\bar{d}

step 1.まとめられるやつを全部まとめる

  1. aˉbcˉdˉ\bar{a}b\bar{c}\bar{d}
  2. abˉcˉdˉa\bar{b}\bar{c}\bar{d}
  3. abˉcˉda\bar{b}\bar{c}d
  4. abˉcdˉa\bar{b}c\bar{d}
  5. abˉcda\bar{b}cd
  6. abcˉdˉab\bar{c}\bar{d}
  7. abcdabcd
  • bcˉdˉb\bar{c}\bar{d} 1,6
  • abˉcˉa\bar{b}\bar{c} 2,3

abˉcˉdˉ+abˉcˉdabˉcˉa\bar{b}\bar{c}\bar{d} + a\bar{b}\bar{c}d \rightarrow a\bar{b}\bar{c}

step 1.まとめられるやつを全部まとめる

  1. aˉbcˉdˉ\bar{a}b\bar{c}\bar{d}
  2. abˉcˉdˉa\bar{b}\bar{c}\bar{d}
  3. abˉcˉda\bar{b}\bar{c}d
  4. abˉcdˉa\bar{b}c\bar{d}
  5. abˉcda\bar{b}cd
  6. abcˉdˉab\bar{c}\bar{d}
  7. abcdabcd
  • bcˉdˉb\bar{c}\bar{d} 1,6
  • abˉcˉa\bar{b}\bar{c} 2,3
  • abˉdˉa\bar{b}\bar{d} 2,4
  • acˉdˉa\bar{c}\bar{d} 2,6
  • abˉda\bar{b}d 3,5
  • abˉca\bar{b}c 4,5
  • acdacd 5,7

step 1.まとめられるやつを全部まとめる

  1. aˉbcˉdˉ\bar{a}b\bar{c}\bar{d}
  2. abˉcˉdˉa\bar{b}\bar{c}\bar{d}
  3. abˉcˉda\bar{b}\bar{c}d
  4. abˉcdˉa\bar{b}c\bar{d}
  5. abˉcda\bar{b}cd
  6. abcˉdˉab\bar{c}\bar{d}
  7. abcdabcd
  • bcˉdˉb\bar{c}\bar{d} 1,6
  • abˉcˉa\bar{b}\bar{c} 2,3
  • abˉdˉa\bar{b}\bar{d} 2,4
  • acˉdˉa\bar{c}\bar{d} 2,6
  • abˉda\bar{b}d 3,5
  • abˉca\bar{b}c 4,5
  • acdacd 5,7
  • abˉa\bar{b} 2,3,4,5

abˉcˉ+abˉcabˉa\bar{b}\bar{c} + a\bar{b}c \rightarrow a\bar{b}
abˉdˉ+abˉdabˉa\bar{b}\bar{d} + a\bar{b}d \rightarrow a\bar{b}

step 2.それ以上まとめられない項を列挙する。

  • bcˉdˉb\bar{c}\bar{d} 1,6
  • acˉdˉa\bar{c}\bar{d} 2,6
  • acdacd 5,7
  • abˉa\bar{b} 2,3,4,5

この中からいくつか選んで論理和を取れば良い。

step 3.組合せを全探索

項数が最小のものを求めると

bcˉdˉ+acd+abˉb\bar{c}\bar{d} + acd + a\bar{b}

が得られる。

ご視聴ありがとうございました。