正準表現

  • どのようなブール関数でも少なくとも一つもつブール式を正準表現という
  • 出力が1の値の行に注目
    • その行のリテラルを論理積でくっつける
    • それらをさらに論理和でくっつける
  • AND, OR, NOTであらゆるブール関数が表現できることがわかる
  • NANDでAND, OR, NOTを表すことができるのであらゆるブール関数はNANDだけで作ることができる