論理演算のソースを表示

'''論理演算'''（ろんりえんざん、logical operation）は、[[論理式 (数学)|論理式]]において、[[論理演算子]]などで表現される論理関数（[[ブール関数]]）を評価し（正確には、関数適用を評価し<ref>たとえば、三角関数の sin などといった関数それ自体が「関数」であり、sin(3.14) などのように関数と実引数とを結びつけること and・or 結びつけたものを「関数適用」と言う。</ref>）、変数（変項）さらには論理式全体の値を求める演算である。

[[非古典論理]]など他にも多くの論理の体系があるが、ここでは[[古典論理]]のうちの[[命題論理]]、特にそれを形式化した[[ブール論理]]に話を絞る。従って対象がとる値は[[真理値]]の2値のみに限られる。また、その真理値の集合（真理値集合）と演算（演算子）は[[ブール代数]]を構成する。

コンピュータの[[プロセッサ]]や[[プログラミング言語]]で多用されるものに、[[ブーリアン型]]を対象とした通常の論理演算の他に、ワード等の[[ビット]]毎に論理演算を行なう演算があり、[[ビット演算]]という。

なお、[[証明論]]的には、[[公理]]と[[推論規則]]に従って論理式を変形（書き換え）する演算がある（[[証明論#証明計算の種類]]）。

== 演算の種類 ==
ここでは1出力の関数のみを扱う。2出力以上の関数は、（実装はともかく）論理的には1出力の関数を並べるだけであり自明と言ってよいであろう。以下では、真理値の記号は {0, 1} とする。

=== 1入力 ===
1入力1出力のブール関数は以下の4通りのみ。最後の入力の反転（NOT）以外はごく直感的。
* 入力がなんであれ、常に 0 を出力する
* 入力がなんであれ、常に 1 を出力する
* 入力がなんであれ、入力と同じ値をそのまま出力する
* 入力が 0 であれば 1 を、入力が 1 であれば 0 を出力する。すなわち入力の反転（「否定」とも言う）を出力する ('''NOT'''あるいはinversion、以下では ¬ の記号を使う)

=== 2入力 ===
2つの入力 ''P''、''Q'' に対し、以下の16通りが全てである。

この節、および以降に続く節では、[[論理和|和]]に ∨、[[論理積|積]]に ∧ の記号を使う。
<center>
{| style="border: none;"
|-
| {{logicalconnective
  |main=矛盾
  |title=矛盾
  |notation=<math>\bot</math>
  |equivalents=''P'' <math>\wedge</math> ¬''P''
  |truthtable-00=0
  |truthtable-01=0
  |truthtable-10=0
  |truthtable-11=0
  |image=Venn0000.svg
}}
| {{logicalconnective
  |main=恒真式
  |title=恒真
  |notation=<math>\top</math>
  |equivalents=''P'' <math>\vee</math> ¬''P''
  |truthtable-00=1
  |truthtable-01=1
  |truthtable-10=1
  |truthtable-11=1
  |image=Venn1111.svg
}}
|-
| {{logicalconnective
  |main=論理積
  |title=論理積
  |notation=''P'' <math>\wedge</math> ''Q''<br/>''P'' & ''Q''<br/>''P''&nbsp;AND&nbsp;''Q''
  |equivalents=''P'' <math>\not\rightarrow</math>¬''Q'' <br/> ¬''P'' <math>\not\leftarrow</math> ''Q'' <br/> ¬''P'' <math>\downarrow</math> ¬''Q''
  |truthtable-00=0
  |truthtable-01=0
  |truthtable-10=0
  |truthtable-11=1
  |image=Venn0001.svg
}}
|{{logicalconnective
  |main=否定論理積
  |title=否定論理積
  |notation=''P'' ↑ ''Q''<br/>''P'' &#124; ''Q'' <br/>''P''&nbsp;NAND&nbsp;''Q'' 
  |equivalents=''P'' → ¬''Q'' <br/> ¬''P'' ← ''Q''<br/>¬''P'' {{or-}} ¬''Q''
  |truthtable-00=1
  |truthtable-01=1
  |truthtable-10=1
  |truthtable-11=0
  |image=Venn1110.svg
}}
|-
| {{logicalconnective
  |main=非含意
  |title=非含意
  |notation=''P'' <math>\not\rightarrow</math> ''Q'' <br/> ''P'' <math>\not\supset</math> ''Q''
  |equivalents=''P'' & ¬''Q'' <br/> ¬''P'' ↓ ''Q'' <br/> ¬''P'' <math>\not\leftarrow</math> ¬''Q''
  |truthtable-00=0
  |truthtable-01=0
  |truthtable-10=1
  |truthtable-11=0
  |image=Venn0100.svg
}}
|{{logicalconnective
  |main=論理包含
  |title=含意 (条件式)
  |notation=''P'' → ''Q'' <br/> ''P'' <math>\supset</math> ''Q''
  |equivalents=''P'' ↑ ¬''Q'' <br/> ¬''P'' {{or-}} ''Q'' <br/> ¬''P'' ← ¬''Q''
  |truthtable-00=1
  |truthtable-01=1
  |truthtable-10=0
  |truthtable-11=1
  |image=Venn1011.svg
}}
|-
| {{logicalconnective
  |main=命題
  |title=命題 ''P''
  |notation=''P''
  |equivalents=&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
  |truthtable-00=0
  |truthtable-01=0
  |truthtable-10=1
  |truthtable-11=1
  |image=Venn0101.svg
}}
|{{logicalconnective
  |main=否定
  |title=否定 ''P''
  |notation=¬''P''
  |equivalents=&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
  |truthtable-00=1
  |truthtable-01=1
  |truthtable-10=0
  |truthtable-11=0
  |image=Venn1010.svg
}}
|-
| {{logicalconnective
  |main=逆非含意
  |title=逆非含意
  |notation=''P'' <math>\not\leftarrow</math> ''Q'' <br/> ''P'' <math>\not\subset</math> ''Q''
  |equivalents=''P'' ↓ ¬''Q'' <br/> ¬''P'' & ''Q'' <br/> ¬''P'' <math>\not\rightarrow</math> ¬''Q''
  |truthtable-00=0
  |truthtable-01=1
  |truthtable-10=0
  |truthtable-11=0
  |image=Venn0010.svg
}}
|{{logicalconnective
  |main=逆含意
  |title=逆含意
  |notation=''P'' <math>\leftarrow</math> ''Q'' <br/> ''P'' <math>\subset</math> ''Q''
  |equivalents=''P'' {{or-}} ¬''Q'' <br/> ¬''P'' ↑ ''Q'' <br/> ¬''P'' → ¬''Q''
  |truthtable-00=1
  |truthtable-01=0
  |truthtable-10=1
  |truthtable-11=1
  |image=Venn1101.svg
}}
|-
| {{logicalconnective
  |main=命題
  |title=命題 ''Q''
  |notation=''Q''
  |equivalents=&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
  |truthtable-00=0
  |truthtable-01=1
  |truthtable-10=0
  |truthtable-11=1
  |image=Venn0011.svg
}}
|{{logicalconnective
  |main=否定
  |title=否定 ''Q''
  |notation=¬''Q''
  |equivalents=&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
  |truthtable-00=1
  |truthtable-01=0
  |truthtable-10=1
  |truthtable-11=0
  |image=Venn1100.svg
}}
|-
| {{logicalconnective
  |main=排他的論理和
  |title=排他的論理和
  |notation=''P'' <math>\not\leftrightarrow</math> ''Q'' <br/> ''P'' <math>\not\equiv</math> ''Q'' <br/> ''P'' <math>\oplus</math> ''Q''<br/>''P''&nbsp;XOR&nbsp;''Q''
  |equivalents=''P'' {{eqv}} ¬''Q'' <br/> ¬''P'' {{eqv}} ''Q'' <br/> ¬''P'' <math>\not\leftrightarrow</math> ¬''Q''
  |truthtable-00=0
  |truthtable-01=1
  |truthtable-10=1
  |truthtable-11=0
  |image=Venn0110.svg
}}
|{{logicalconnective
  |main=同値
  |title=同値 (必要十分条件)
  |notation=''P'' {{eqv}} ''Q'' <br> ''P'' ≡ ''Q''<br>''P''&nbsp;XNOR&nbsp;''Q''<br> ''P''&nbsp;IFF&nbsp;''Q''
  |equivalents=''P'' <math>\not\leftrightarrow</math> ¬''Q'' <br/> ¬''P'' <math>\not\leftrightarrow</math> ''Q'' <br/> ¬''P'' {{eqv}} ¬''Q''
  |truthtable-00=1
  |truthtable-01=0
  |truthtable-10=0
  |truthtable-11=1
  |image=Venn1001.svg
}}
|-
| {{logicalconnective
  |main=論理和
  |title=論理和
  |notation=''P'' {{or-}} ''Q''<br/>''P''&nbsp;OR&nbsp;''Q''
  |equivalents=''P'' <math>\leftarrow</math> ¬''Q'' <br/> ¬''P'' → ''Q'' <br/> ¬''P'' ↑ ¬''Q''
  |truthtable-00=0
  |truthtable-01=1
  |truthtable-10=1
  |truthtable-11=1
  |image=Venn0111.svg
}}
|{{logicalconnective
  |main=否定論理和
  |title=否定論理和
  |notation=''P'' ↓ ''Q''<br/>''P''&nbsp;NOR&nbsp;''Q''
  |equivalents=''P'' <math>\not\leftarrow</math> ¬''Q'' <br/> ¬''P'' <math>\not\rightarrow</math> ''Q'' <br/> ¬''P'' & ¬''Q''
  |truthtable-00=1
  |truthtable-01=0
  |truthtable-10=0
  |truthtable-11=0
  |image=Venn1000.svg
}}
|}
</center>

==定理==
以上の演算に対して成り立っている定理として、以下のようなものがある。（証明論的には（「命題論理の証明論」）、以下の等式のいくつかに相当する[[公理]] and・or [[推論規則]]が採用される）
*[[冪等|べき等則]]
<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>

== その他 ==
その他の話題

=== 完全性 ===
{{seealso|否定論理積#完全性}}
（詳細は英語版記事 [[:en:Functional completeness]] を参照のこと）以上の演算のうち、ごく少数の種類の演算の組み合わせによって、任意の演算を「実装」することができる。そのような演算の組の性質を functional completeness という。∨ と ∧ だけでは完全ではなく、必ず ¬ も必要である。一方 ¬ があれば、∨ と ∧ はどちらか一方でも良い。さらに興味深いものとして、¬ と ∨ あるいは ∧ の組合せである、[[否定論理積]]（[[NANDゲート|NAND]]）や[[否定論理和]]（[[NORゲート|NOR]]）は、それ一つだけで完全である。なお、→ の記号が使われることが多い「ならば」（imply、[[論理包含]]）は微妙な点があり（たとえば、演算子だけでなく定数入力を必要とする）、英語版Wikipediaの Implicational propositional calculus の記事（[[:en:Implicational propositional calculus]]）では「virtual completeness」と表現している。

== 注 ==
<references/>

==関連項目==
*[[カルノー図]]
*[[ド・モルガンの法則]]
*[[真理値]]
*[[マスク (情報工学)]]
*[[数学]] - [[数理論理学]]
*[[論理学]]
*[[論理回路]]
*[[ブール関数]] - [[ブール代数]]
*[[ベン図]] - [[オイラー図]]
*[[ブーリアン演算]]
*[[プログラミング言語]]
*[[数学記号の表#記号論理の記号]]

{{論理演算}}
{{Mathematical logic}}

{{sci-stub}}

{{Normdaten}}
{{DEFAULTSORT:ろんりえんさん}}
[[Category:論理結合子|*]]
[[Category:論理記号|*]]
[[Category:命題論理]]
[[Category:数学に関する記事]]