論理代数
論理代数系(ブール代数)と論理演算について説明します。
<注意>
このページでは、数式を表示するためにMathJaxを使用しています。ブラウザの設定でスクリプト実行をブロックしている場合、ページ内の数式が正しく表示されません。
真理値と論理演算
ある命題が正しいか、正しくないか、といった、「はい」と「いいえ」の2択だけで物事を考えていくことを考えます。数学にこのような分野があり、ブール代数あるいはブール論理と呼ばれます。なお、術語としては「はい」「いいえ」ではおかしいので「真(true)」と「偽(false)」を使い、この2つを真理値と言います。さらに、これらの値はそれぞれ数字の1,0に対応させられることがしばしば行われます。
さて、普通の数同士に四則演算があるように、真理値同士にも論理演算と呼ばれる演算があります。論理演算はいくつか種類がありますが、重要なものだけを説明します。
- 否定
定義
真理値を逆にする演算を否定という。
真理値\(\ P\ \)の否定は、\(\ \lnot P,\ !P,\ \mathrm{NOT}\ P\ \)とかく
- 論理積
定義
2つの真理値\(\ P,Q\ \)がともに真のときだけ真となり、それ以外の場合は偽となるような演算を論理積という。
真理値\(\ P,Q\ \)の論理積は、\(\ P \land Q,\ P\&Q,\ P\ \mathrm{AND}\ Q\ \)とかく
- 論理和
定義
2つの真理値\(\ P,Q\ \)がともに偽のときだけ偽となり、それ以外の場合は真となるような演算を論理和という。
真理値\(\ P,Q\ \)の論理和は、\(\ P \lor Q,\ P|Q,\ P\ \mathrm{OR}\ Q\ \)とかく
- 否定論理積
定義
論理積の否定を否定論理積という。
真理値\(\ P,Q\ \)の否定論理積は、\(\ P \uparrow Q,\ P\ \mathrm{NAND}\ Q\ \)とかく
- 否定論理和
定義
論理和の否定を否定論理和という。
真理値\(\ P,Q\ \)の否定論理和は、\(\ P \downarrow Q,\ P\ \mathrm{NOR}\ Q\ \)とかく
- 排他的論理和
定義
2つの真理値\(\ P,Q\ \)が互いに異なる値のときだけ真となり、それ以外の場合は偽となるような演算を排他的論理和という。
真理値\(\ P,Q\ \)の排他的論理和は、\(\ P \not\leftrightarrow Q,\ P \not\equiv Q,\ P\oplus Q,\ P\ \mathrm{XOR}\ Q\ \)とかく。
- 同値(必要十分条件)
定義
排他的論理和の否定を同値または必要十分条件という。
真理値\(\ P,Q\ \)の同値は、\(\ P \leftrightarrow Q,\ P \equiv Q,\ P\ \mathrm{XNOR}\ Q,\ P\ \mathrm{IFF}\ Q\ \)とかく。
それぞれの論理演算の結果が真になる範囲を、ベン図で塗って表したものです。
左の円の中が\(\ P\ \)が真、右の円の中が\(\ Q\ \)が真の範囲です。
論理演算の性質
普通の数の四則演算にさまざまな性質があるのと同様に、論理演算にもさまざまな性質があります。
定理
\[\begin{array}{ll} {P\land P=P\\ P\lor P=P} & \mbox{(冪等則)}\\ {P\land Q=Q\land P\\ P\lor Q=Q\lor P} & \mbox{(交換則)}\\ {(P\land Q)\land R=P\land(Q\land R) \\ (P\lor Q)\lor R=P\lor (Q\lor R)} & \mbox{(結合則)}\\ {P\lor(Q\land R)=(P\lor Q)\land(P\lor R)\\ P\land(Q\lor R)=(P\land Q)\lor(P\land R)} & \mbox{(分配則)}\\ {P\lor(P\land Q)=P\\ P\land(P\lor Q)=P} & \mbox{(吸収則)}\\ P\land 0=0\\ P\lor 0=P\\ P\land 1=P\\ P\lor 1=1\\ P\land (\lnot P)=0\\ P\lor (\lnot P)=1\\ \lnot(\lnot P)=P & \mbox{(二重否定)}\\ \end{array} \]
論理演算について、常に次の性質が成り立つ。
さらに、論理演算には次の重要な性質があります。
定理 (否定論理和と否定論理積の完全性)
すべての論理演算は複数回の否定論理積または否定論理和だけの組み合わせで表現できる。
定理 (ド・モルガンの法則)
\[\begin{gathered} \lnot(P\lor Q)=(\lnot P)\land(\lnot Q)\\ \lnot(P\land Q)=(\lnot P)\lor(\lnot Q) \end{gathered}\]
論理積および論理和とその否定について次の式が成り立つ。
\(\ \lnot P\ \)と\(\ \lnot Q\ \)の共通部分は、\(\ P\lor Q\ \)の外側と一致します。これが1つ目の式です。
任意の数値における論理演算
ここまでは、真理値における論理演算を考えました。実は、これを応用することで任意の整数に対する論理演算を考えることができます。
定義
任意の整数\(\ P,Q\ \)に対し、これらの値に対する論理演算の結果は、これらの値を2進表現した場合の各ビットごとの論理演算の結果として求まる値とする。
同じ桁のビットごとに論理演算を適用する(空位は当然0として考える)ことで、論理演算のすべての性質を損なうことなく一般の整数に拡張します。たとえば2つの数174と231の論理和、論理積、排他的論理和は次のようになります。
例題
2数174および231に対し、論理和、論理積、排他的論理和を計算せよ。174は2進表現で0b10101110、231は2進表現で0b11100111であるので、
\[\begin{array}{lll} \begin{array}{ll} & 1010\ 1110\\ \mathrm{OR} & 1110\ 0111\\ \hline & 1110\ 1111=239 \end{array} & \begin{array}{ll} & 1010\ 1110\\ \mathrm{AND} & 1110\ 0111\\ \hline & 1010\ 0110=166 \end{array} & \begin{array}{ll} & 1010\ 1110\\ \mathrm{XOR} & 1110\ 0111\\ \hline & 0100\ 1001=73 \end{array} \end{array}\]
上の2つの数の同じ位置のビットどうしに、論理演算をしています。
なお、任意の数に対する論理否定も同様にして定義でき、それは結局ビット反転の操作そのものです。