ブール代数

  • 2019/05/29 09:00

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

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

次に示すのはブール代数の公理系である. 公理系に関する詳細は証明理論 (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 とする.

Read More...

関係 (集合論)

  • 2019/03/15 09:00

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

一般的な関係

いま, 二つの要素の順序体を <a,b>\left\lt a, b\right\gt と書くこととする. 他の異なる順序体 <c,b>\left\lt c, b\right\gt に対し, 以下の通り定義する.

<a,b>=<c,d>:=a=c,b=dデカルト積=直積=A×B:={<a,b>aA,bB} \begin{aligned} \left\lt a,b\right\gt=\left\lt c,d\right\gt&:=&a=c, b=d\\ {\rm デカルト積} = {\rm 直積} = A\times B&:=&\left\{\left\lt a,b\right\gt\mid a\in A, b\in B\right\} \end{aligned}

このとき順序体の要素を nn 個に拡張したものを nn-tuple といい, 以下の通り定義する.

Read More...

放物運動

放物運動に関する復習と再現.

等加速度運動をする物体の位置関数の導出

時刻 t=0t=0 における物体の位置を x0{\boldsymbol x_0}, 速度を v0{\boldsymbol v_0} とし, 加速度を考慮しない等速運動の三次元空間上の一点に対する位置関数 x(t){\boldsymbol x}(t)x(t)=x0+v0t{\boldsymbol x}(t)={\boldsymbol x_0}+{\boldsymbol v_0}t とおく. このとき, 時間 t1t_1 から t2t_2 への変化量 x(t2)x(t1){\boldsymbol x}(t_2)-{\boldsymbol x}(t_1)Δt=t2t1\Delta t=t_2-t_1 で割れば, 時間経過に対する物体の位置の対比が得られる. これは正しく速度のことであるが, これは時間 t1t_1 に位置 x(t1){\boldsymbol x}(t_1), 時間 t2t_2 に位置 x(t2){\boldsymbol x}(t_2) にあった物体の平均速度である. いま時間 tt における物体の瞬間速度を知りたいとすると, Δt\Delta t が微小量となるように極限(t2t1Δt0t_2\to t_1\Leftrightarrow \Delta t\to 0)を取れば良い.Read More...


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

要旨

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

にまとまっています.

Read More...

LU 分解

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

Read More...