集合と論理演算

要点と定義

集合は、条件を満たす要素の集まりです。全体集合を S、その部分集合を A,B とすると、補集合 \bar A は S のうち A に属さない要素、差集合 A-B は A に属し B に属さない要素です。したがって \bar A-B=\bar A\cap\bar B は、どちらにも属さない要素を表します。補集合は全体集合 S を前提とし、和集合と積集合を取り違えないようにします。

論理演算では、0と1をそれぞれ偽と真として扱います。論理積は両方が1のときだけ1、論理和は少なくとも一方が1なら1、否定は0と1を反転します。直列につないだ二つのスイッチで、両方がオンのときだけ出力が1になる動作は論理積で表せます。

論理式は、真理値表や条件の組合せから評価できます。含意 P\to Q は、前件が真で後件が偽のときだけ偽です。たとえば P,Q が真なら、P\to\bar Q は偽、Q\to\bar P も偽です。偽を前件とする含意は後件の真偽にかかわらず真なので、その性質から式全体を判定できます。

適用条件と例

固定長の二進数では、各桁の重みを使って値を表します。二桁 x_1x_2 の値は 2x_1+x_2 です。桁を入れ替えた値は 2x_2+x_1。元の値を x とすると、x_1=\operatorname{int}(x/2)、x_2=x-2\operatorname{int}(x/2) なので、入れ替え後は 2x-3\operatorname{int}(x/2) です。これは二桁の非負整数で、intが小数部分を切り捨てる条件の下で成り立ちます。

8ビットの値を0から255までに保って1ずつ進める例では、255を二進数のマスクとして使えます。255は下位8桁がすべて1なので、(n+1)\operatorname{AND}255 は n<255 では増加後の値を保ち、255では桁あふれした上位桁を落として0にします。マスクの幅と対象の値の範囲が一致していることが条件です。

状態の変化を論理式で表すときは、今回と前回の値を区別します。今回を a、前回を b とし、0から1への変化だけを検出するなら a\land\bar b です。例えば今回1・前回0なら1、今回0・前回1なら0となります。周期的に値を読み取るなど、二つの値が比較できる前提で使います。

カルノー図では、隣接する1のまとまりから、まとまりの中で変化しない変数だけを式に残します。例えば、4つのセルで B=1,D=1 が共通なら、そのまとまりは B\land D です。まとまりを作る際は、図の配置に従って隣接を判断し、0のセルを含めないようにします。