論理の流刑地

地獄の底を、爆笑しながら闊歩する

ブール代数分析をふわっと

ふわとろ高級オムライスがたべたい

Motivation

「どうせ簡単だろ」とタカを括ってあんまり勉強してなかった手法シリーズなので。
なんとなくの感触で過信してちゃんと時間かけないのは恥ずべきことなんだよな...

てことで下らへん見て勉強する...

◆文献list

  1. 石田淳(2017)『集合論による社会的カテゴリーの展開』(第3-4章)
  2. Caren & Panofsky , 2005 , "A Technique for Adding Temporality to Qualitative Comparative Analysis"(URL)

基本定理

全部網羅的に書いてもあれなので、自分が躓いたところだけメモ

まず基本的な定理(前提となるもの)

交換律: x+y = y + x, x\cdot y = y \cdot x
分配率: x + ( y \cdot z) = (x + y ) \cdot ( x + z)
同一律x\cdot I = x , \ \ x + O = x
補元律:x+\bar{x} = 1, \ \ x\cdot \bar{x} = O

基本的定理のコロラリー

べき等律: x+x = x, \  \  , x\cdot x = x
有界律: x + I = I , \ x \cdot O =O
吸収律: x\cdot(x+y) = x, \  x + (x \cdot y ) = x
結合律(省略)、対合律(省略)

覚えとくと便利なこと

相対原理
ブール代数の任意の性質は、+と・,x\bar{x}を入れ替えても成立する

ブール代数における順序関係
 xy=x \Leftrightarrow x+y =y
が成り立っているとき、順序関係 x \leq yが成り立っているとする。

ブール関数の簡単化(いわゆるcsQCAのやってることはだいたいコレ)

「ブール関数の簡単化」とは、標準積和形(最小項*1の和によるブール関数の表現式)からスタートして、できるだけ項数と各々の項を構成する変数の数が少ない式を求めること、である。

その過程は、

  1. 主項の導出
  2. 最小積和形の導出

の2ステップを踏む*2

主項の導出

Definition:
まず、最初の段階では標準積和形から、最小化定理とベキ等律を繰り返し適用して、これ以上簡単化できないところまで式を変形する。
こうして得られる式の各項を主項(prime implicant)という(石田 2017: 65-66)

具体的には

  1. ハミング重み(最小項に含まれる1の数)の算出
  2. ハミング重みが1つだけ異なる最小項の総当たり比較→最小化定理による変数の削減
  3. 最小化定理が適用できなくなるまで、第二段階の変数削減を繰り返し行う

という形で行う。
 D = ABC + ABc + Abc + abc = AB + Ac +bcみたいな感じで。

最小積和形の導出

Definition
最小積和形とは、主項数が最も少なく、かつ主項数が同じであれば変数の数が最も少なくなるような表現式のことである
(石田 2017: 66-67)

この導出は、主項選択表を用いることでおこなう。

主項選択表とは、表側に前段階で導出した主項、表頭に最小項をおいた表である。

[STEP1]
行(主項)が列(最小項)を包含している場合、該当するセルに〇をつける。
i行j列のセルの場合「最小項j\leq主項i、が成り立ってるとき〇をつける」ということである。

[STEP2]
必須項(最小項をもれなく包含するために不可欠な主項)に◎をつける
「主項選択表を縦にみて、1つしか〇のつけられない最小項が必須項である」(同:67)
必須項を選ぶことで、求める最小積和項となる(必須項がない場合や複数の組み合わせがあるときもある)。

発展的な話題

上で挙げたCaren&Panofsky(2005)はQCAに時間軸(イベントの順番)を導入したTQCAなるものを提唱している。
一通り論文を読んだが、①順番を定義すること、②「イベントが起きなかった」ことの取り扱いがやや特殊であること、を除けば難しくはなさそうだ。

おわりに

この記事を書き終わったら、羽生さんが若手の伸び盛り佐々木大地五段相手に深夜の千日手指し直し局を制しておられた。
わたしのような老兵もまだ頑張らねばなー。


Relaxing Breath of the Wild music with rain

Enjoy!!

*1:ブール関数を構成するブール変数or補元で構成される項。3変数だったらXyZとかxyzとか。

*2:クワイン・マクラスキー法と呼ぶらしい