ブール代数

  • 2019/05/29 09:00

ブール代数は古典論理における命題論理と密接に関連している. 結論からいえば, 両者の違いは歴史的な背景ぐらいであり, 殆どの場合は同等の理論であるということができる1. ブール代数はその応用として論理回路の構築に直接役立つことから, 計算機科学, とくにハードウェアの分野において重宝される代数系の 1 つである.

目次

  1. ブール代数の公理とその定理
  2. 標準形
    1. 加法標準形, 主加法標準形
    2. 乗法標準形, 主乗法標準形
  3. 簡単化
    1. カルノー図
    2. クワイン・マクラスキー法
    3. ペトリック法
  4. ブール代数の例
  5. 参考文献

ブール代数の公理とその定理

次に示すのはブール代数の公理系である. 公理系に関する詳細は証明理論 (TODO) の冒頭を参照のこと.

ブール代数

半順序集合 (B,,,,0,1)(B,\lor,\land,',0,1) が可補分配ならば, (B,,,,0,1)(B,\lor,\land,',0,1) はブール代数である. すなわち, x,y,zBx,y,z\in B に対して, 次のすべての公理を満たした (B,,,,0,1)(B,\lor,\land,',0,1) はブール代数である.

  1. 可換律\htmlId{boolean_algebra1}{\rm 可換律}: xy=yx,xy=yxx\land y=y\land x,x\lor y=y\lor x
  2. 分配律\htmlId{boolean_algebra2}{\rm 分配律}: (xy)z=(xz)(yz),(xy)z=(xz)(yz)(x\lor y)\land z=(x\land z)\lor(y\land z),(x\land y)\lor z=(x\lor z)\land(y\lor z)
  3. 同一律\htmlId{boolean_algebra3}{\rm 同一律}: xL^\forall x\in L に対して x1=x,x0=xx\land 1=x,x\lor 0=x. ここで 11 は最大限, 単位元である. 00 は最小限, 零元である.
  4. 補元律\htmlId{boolean_algebra4}{\rm 補元律}: xL s.t. xL,xx=1,xx=0^\exists x'\in L\ {\rm s.t.}\ ^\forall x\in L, x\lor x'=1, x\land x'=0

また, この 1,01,0 からのみ成る集合をブール領域, ブール代数の下に書かれた式をブール式, nNn\in\mathbb{N} 個のブール領域の引数をとり, 1 個のブール領域の値となる関数 f:BnBf:B^n\to B をブール関数という. 例えば, 2 変数ブール関数 f(x1,x2)f(x_1,x_2) では x1,x2x_1,x_2 がそれぞれ 1,01,0 のいずれかとなるので, 24=162^4=16 通りの 2 変数ブール式が存在することとなる. 以下, 演算の優先順序は左結合性で ,,',\land,\lor の順とする. ただし, 括弧内の演算はより優先される.

さてブール代数の公理における乗法 \land と加法 \lor, および 1,01, 0 をそれぞれ入れ替えると, 再びブール代数の公理である. これは双対の原理という公理である.

双対の原理

ブール代数で成立する文/式は, そこに現れるすべての ,,0,1\lor ,\land,0,1 をそれぞれ ,,1,0\land,\lor ,1,0 で置き換えても成立する.

これらの公理から補元の一意性, べき等律, 有界律, 吸収律, 結合律, 対合律, ド・モルガンの法則, シャノンの展開定理が導出可能である. 以下 x,y,zBx,y,z\in B とする.


関係 (集合論)

  • 2019/03/15 09:00

関係 (集合論) について復習.

目次

  1. 一般的な関係
  2. 主な二項関係の規則
    1. 主な二項関係
  3. ハッセ図
  4. 半順序集合の拡張
  5. 参考文献

最小二乗法で始めるカーブフィッティング

要旨

本エントリー(WIP)はカーブフィッティング全般に関して記述したものであり, それぞれの原理, 性質について学んだ際のメモとして, より単純なものから広く浅く挙げています. 極力ないようにはしていますが, 本内容は独学で得た知見より書いておりますので, 一部正確さが欠けている可能性があることは否めません. 何かありましたら, コメント等で指摘していただけるとありがたいです. また, 本エントリ内における近似およびプロット等に関する実装は次のリポジトリ

にまとまっています.

目次

  1. 要旨
  2. 線形回帰
    1. 線形最小二乗法
  3. 一般逆行列
    1. 最小二乗形一般逆行列
    2. 最小ノルム形一般逆行列
    3. 制限つき最小二乗法
    4. オーバーフィッティングと正則化およびその評価
    5. 誤差分布が正規分布でない場合の線形回帰
    6. 最小刈込み二乗法
    7. 参考文献

LU 分解

LU 分解に関して初歩的な内容から網羅的にまとめた.

目次

  1. ガウスの消去法
  2. ガウス・ジョルダン法
  3. ピボッティング
  4. LU 分解
  5. 参考文献