否定論理積

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

否定論理積(ひていろんりせき)とは、与えられた複数の命題のうちに偽であるものが含まれることを示す論理演算である。NANDと表記される。別の表記法として、Henry M. Shefferが1913年に導入したシェファーの棒記号(Sheffer stroke、記号 "|" で表す)や矢印の「↑」を用いる表記法もある。

性質[編集]

完全性[編集]

一般に、いくつかの限られた種類の論理演算を任意個組み合わせることにより、任意のブール関数を構成可能であることを、その演算の組は functionally complete であるという(詳細は英語版記事 en:Functional completeness を参照)。ANDとORはどちらも単調であるため「ANDとOR」だけでは完全にならず、NOTを加える必要がある。一方「ANDとNOT」や「ORとNOT」は完全であり、ANDとNOTの組合せであるNAND(や、NOR(否定論理和))はそれひとつだけで完全である。以下にNOT・AND・ORのNANDのみによる構成を示す。

  • NOT A = A NAND A
  • A AND B = NOT ( A NAND B ) = ( A NAND B ) NAND ( A NAND B )
  • A OR B = ( NOT A ) NAND ( NOT B ) = ( A NAND A ) NAND ( B NAND B )

真理値表[編集]

否定論理積の真理値表

命題 P 命題 Q P NAND Q

ベン図[編集]

否定論理積のベン図

否定論理積のベン図

応用[編集]

NANDゲートなどの記事を参照。

関連項目[編集]