論理演算

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

論理演算(ろんりえんざん、logical operation, logical connection)あるいはブール演算(ブールえんざん、boolean operation)とは、「」と「」の二つの真理値と呼ばれる)だけを持つ集合における演算である。(これらの演算によって上記の集合はとなり、ブール環と呼ばれる)

否定(NOT)論理和(OR)論理積(AND)排他的論理和(XOR)含意同値などがある。

数理論理学プログラミング言語などで使われる。プログラミング言語では通常の論理演算のほか、数値のビット毎に論理演算を行なう演算があり、これは特にビット演算という。

演算の種類[編集]

論理演算には、一つの入力の演算(否定(NOT))と、二つの入力の演算(→#論理結合子)とがある。それ以上の数の入力はこれらの演算を組み合わせて演算する。

二つの入力の論理演算の全ては否定(NOT)・論理和(OR)論理積(AND)の演算を組み合わせて演算できることから、これら三つの演算は論理演算の基礎とされている。これら三つの演算もなお、否定論理和(NOR)あるいは否定論理積(NAND)のどちらか一方を複数用いることで演算できる。その場合、二つの入力に同じ値を入力することで否定(NOT)を演算し、またド・モルガンの法則を用いて論理和と論理積とを交換することで論理和と論理積を演算する。

論理結合子[編集]

二つの二値入力 PQ に対し、以下の16種類の論理演算がある。

矛盾
記法 等価式 真理値表 ベン図
\bot P \wedge ¬P
  Q
0 1
P 0    0   0 
1    0   0 
Venn0000.svg


トートロジー
記法 等価式 真理値表 ベン図
\top P \vee ¬P
  Q
0 1
P 0    1   1 
1    1   1 
Venn1111.svg


論理積
記法 等価式 真理値表 ベン図
P \wedge Q
P & Q
P AND Q
P \not\rightarrow¬Q
¬P \not\leftarrow Q
¬P \downarrow ¬Q
  Q
0 1
P 0    0   0 
1    0   1 
Venn0001.svg


否定論理積
記法 等価式 真理値表 ベン図
PQ
P | Q
P NAND Q
P → ¬Q
¬PQ
¬P \lor ¬Q
  Q
0 1
P 0    1   1 
1    1   0 
Venn1110.svg


非含意
記法 等価式 真理値表 ベン図
P \not\rightarrow Q
P \not\supset Q
P & ¬Q
¬PQ
¬P \not\leftarrow ¬Q
  Q
0 1
P 0    0   0 
1    1   0 
Venn0100.svg


含意 (条件式)
記法 等価式 真理値表 ベン図
PQ
P \supset Q
P ↑ ¬Q
¬P \lor Q
¬P ← ¬Q
  Q
0 1
P 0    1   1 
1    0   1 
Venn1011.svg


命題 P
記法 等価式 真理値表 ベン図
P                   
  Q
0 1
P 0    0   0 
1    1   1 
Venn0101.svg


否定 P
記法 等価式 真理値表 ベン図
¬P                   
  Q
0 1
P 0    1   1 
1    0   0 
Venn1010.svg


逆非含意
記法 等価式 真理値表 ベン図
P \not\leftarrow Q
P \not\subset Q
P ↓ ¬Q
¬P & Q
¬P \not\rightarrow ¬Q
  Q
0 1
P 0    0   1 
1    0   0 
Venn0010.svg


逆含意
記法 等価式 真理値表 ベン図
P \leftarrow Q
P \subset Q
P \lor ¬Q
¬PQ
¬P → ¬Q
  Q
0 1
P 0    1   0 
1    1   1 
Venn1101.svg


命題 Q
記法 等価式 真理値表 ベン図
Q                   
  Q
0 1
P 0    0   1 
1    0   1 
Venn0011.svg


否定 Q
記法 等価式 真理値表 ベン図
¬Q                   
  Q
0 1
P 0    1   0 
1    1   0 
Venn1100.svg


排他的論理和
記法 等価式 真理値表 ベン図
P \not\leftrightarrow Q
P \not\equiv Q
P \oplus Q
P XOR Q
P \leftrightarrow ¬Q
¬P \leftrightarrow Q
¬P \not\leftrightarrow ¬Q
  Q
0 1
P 0    0   1 
1    1   0 
Venn0110.svg


同値 (必要十分条件)
記法 等価式 真理値表 ベン図
P \leftrightarrow Q
PQ
P XNOR Q
P IFF Q
P \not\leftrightarrow ¬Q
¬P \not\leftrightarrow Q
¬P \leftrightarrow ¬Q
  Q
0 1
P 0    1   0 
1    0   1 
Venn1001.svg


論理和
記法 等価式 真理値表 ベン図
P \lor Q
P OR Q
P \leftarrow ¬Q
¬PQ
¬P ↑ ¬Q
  Q
0 1
P 0    0   1 
1    1   1 
Venn0111.svg


否定論理和
記法 等価式 真理値表 ベン図
PQ
P NOR Q
P \not\leftarrow ¬Q
¬P \not\rightarrow Q
¬P & ¬Q
  Q
0 1
P 0    1   0 
1    0   0 
Venn1000.svg


公式[編集]

論理和 (OR) = \lor論理積 (AND) = \land否定 (NOT) = \lnotとした場合、以下の法則が成り立つ。

\begin{align}
p \lor p &\equiv p \\
p \land p &\equiv p \\
\end{align}

\begin{align}
p \lor q &\equiv q \lor p \\
p \land q &\equiv q \land p \\
\end{align}

\begin{align}
p \lor(q \lor r) &\equiv (p \lor q)\lor r \\
p \land(q \land r) &\equiv (p \land q)\land r \\
\end{align}

\begin{align}
p \lor(q \land r) &\equiv (p \lor q)\land(p \lor r) \\
p \land(q \lor r) &\equiv (p \land q)\lor(p \land r) \\
\end{align}

\begin{align}
p \lor(p \land q) &\equiv p \\
p \land(p \lor q) &\equiv p \\
\end{align}

\begin{align}
\lnot(p \lor q) &\equiv (\lnot p)\land(\lnot q) \\
\lnot(p \land q) &\equiv (\lnot p)\lor(\lnot q) \\
\end{align}

  • その他

\begin{align}
&p \lor 0 \equiv p \\
&p \land 0 \equiv 0 \\
&p \lor 1 \equiv 1 \\
&p \land 1 \equiv p \\
&p \lor (\lnot p) \equiv 1 \\
&p \land (\lnot p) \equiv 0 \\
&\lnot(\lnot p) \equiv p \\
\end{align}

関連項目[編集]