| 論理代数 |
<注意>
このページでは、数式を表示するためにMathJaxを使用しています。ブラウザの設定でスクリプト実行をブロックしている場合、ページ内の数式が正しく表示されません。
真理値と論理演算さて、普通の数同士に四則演算があるように、真理値同士にも論理演算と呼ばれる演算があります。論理演算はいくつか種類がありますが、重要なものだけを説明します。
1. 否定
-
定義
真理値を逆にする演算を否定という。
真理値$\ 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\ $とかく。
論理演算の性質-
定理
論理演算について、常に次の性質が成り立つ。
\[\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=1\\
P\lor 1=P\\
P\land (\lnot P)=0\\
P\lor (\lnot P)=1\\
\lnot(\lnot P)=P & \mbox{(二重否定)}\\
\end{array}
\]
-
定理 (否定論理和と否定論理積の完全性)
すべての論理演算は複数回の否定論理積または否定論理和だけの組み合わせで表現できる。
-
定理 (ド・モルガンの法則)
論理積および論理和とその否定について次の式が成り立つ。
\[
\lnot(P\lor Q)=(\lnot P)\land(\lnot Q)\\
\lnot(P\land Q)=(\lnot P)\lor(\lnot Q)
\]
任意の数値における論理演算-
定義
任意の整数$\ P,Q\ $に対し、これらの値に対する論理演算の結果は、これらの値を2進表現した場合の各ビットごとの論理演算の結果として求まる値とする。
-
例題
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}\]