否定論理積 (nand) とは、論理学における結合子の一つであり、NAND と表記される[1]。棒記号「|」が使われる時には、発見者の名前にちなんだシェーファーの棒 (Sheffer stroke) とも呼ばれる。上矢印記号「↑」が使われることもある。
真理表
| A | B | A$ \mid $B |
|---|---|---|
| 真 | 真 | 偽 |
| 真 | 偽 | 真 |
| 偽 | 真 | 真 |
| 偽 | 偽 | 真 |
特徴
否定論理積は、否定論理和と共に、1つで十全あるシェーファー関数である。
証明
否定論理積だけで十全であることを証明するためには、否定論理積で全ての真理関数が表現できることを示せばよい。十全の項目によれば、$ \lnot, \land $は十全であることが既に分かっている。従って、$ \lnot, \land $の論理的同値を否定論理積のみで作りだせればよい。
- $ \lnot A \Leftrightarrow (A \mid A) $
- $ A \land B \Leftrightarrow (A \mid B) \mid (A \mid B) $
否定論理積だけで、$ \lnot, \land $が表現できた。よって、否定論理積のみで十全にすることが可能である。
出典
- ↑ Weisstein, Eric W. "NAND." From MathWorld--A Wolfram Web Resource.
