論理演算

出典: フリー百科事典『ウィキペディア(Wikipedia)』
2014年5月15日 (木) 00:30時点におけるMoreNet (トーク)による版 (MoreNet (会話) による ID:51670926 の版を取り消し)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内検索

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

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

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

演算の種類

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

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

論理結合子

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

テンプレート:Logicalconnective テンプレート:Logicalconnective
テンプレート:Logicalconnective テンプレート:Logicalconnective
テンプレート:Logicalconnective テンプレート:Logicalconnective
テンプレート:Logicalconnective テンプレート:Logicalconnective
テンプレート:Logicalconnective テンプレート:Logicalconnective
テンプレート:Logicalconnective テンプレート:Logicalconnective
テンプレート:Logicalconnective テンプレート:Logicalconnective
テンプレート:Logicalconnective テンプレート:Logicalconnective

公式

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

<math>\begin{align} p \lor p &\equiv p \\ p \land p &\equiv p \\ \end{align}</math>

<math>\begin{align} p \lor q &\equiv q \lor p \\ p \land q &\equiv q \land p \\ \end{align}</math>

<math>\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}</math>

<math>\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}</math>

<math>\begin{align} p \lor(p \land q) &\equiv p \\ p \land(p \lor q) &\equiv p \\ \end{align}</math>

<math>\begin{align} \lnot(p \lor q) &\equiv (\lnot p)\land(\lnot q) \\ \lnot(p \land q) &\equiv (\lnot p)\lor(\lnot q) \\ \end{align}</math>

  • その他

<math>\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}</math>

関連項目

テンプレート:論理演算


テンプレート:Asbox