古典論理の完全論理函數族
代表的な論理函數
table:1 in 1 out
in id ¬
0 0 1
1 1 0
table:2 in 1 out
in ⊥ NOR XOR NAND ∧ ≡ snd ⊃ fst ⊂ ∨ ⊤
00 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
01 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
10 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
11 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
逆 (converse)
snd←→fst
⊃←→⊂
名が附いてゐる他の 2 in 1 out の論理函數は自己逆
從ふと、$ A\supset Bは「$ Bがないならば$ Aがない、$ Aがあるとき$ Bがある」と讀める
滅「$ Bがあるならば$ Aがある、$ Aがないとき$ Bがない」
「$ Bがあるならば$ Aがある」
$ 0\subset 1=0,$ 1\subset 1=1
「$ Aがないとき$ Bがない」
$ 0\subset 0=1,$ 1\subset 0=0
集「$ Bがないならば$ Aがない、$ Aがあるとき$ Bがある」
「$ Bがないならば$ Aがない」
$ 0\supset 0=1,$ 0\supset 1=0
「$ Aがあるとき$ Bがある」
$ 1\supset 0=0,$ 1\supset 1=1
完全論理函數族
$ m入力$ n出力の全ての論理函數を合成で表現できる論理函數の集合 例
$ \{\land,\lor,\neg\}
$ \{\land,\neg\}
$ \{\lor,\neg\}
$ \{{\rm NAND}\}
$ \{{\rm NOR}\}
$ \{\supset,\bot\}
2 in 2 out
table:2 in 2 out
in CNOT
00 00
01 01
10 11
11 10
制御 not gate (CNOT (controlled not) gate。controlled-X gate。controlled-bit-flip gate。Feynman gate。controlled Pauli-X)
$ {\rm CNOT}(x,y)=(x,x{\rm XOR}y)
3 in 3 out
table:3 in 3 out
in CCNOT Fredkin
000 000 000
001 001 001
010 010 010
011 011 011
100 100 100
101 101 110
110 111 101
111 110 111
Toffoli gate (CCNOT (controlled-controlled-not) gate)
$ {\rm CCNOT}(x,y,z)=(x,y,(x\land y){\rm XOR}z)
機能的に完全である
Fredkin gate (controlled-swap gate。conservative logic gate)
$ {\rm Fredkin}(x,y,z)=(x,(\neg x\land y)\lor(x\land z),(x\land y)\lor(\neg x\land z))
機能的に完全である
論理函數$ F(x_1,x_2,\dots,x_n)が$ F(0,x_2,\dots,x_n)\le F(1,x_2,\dots,x_n)ならば、$ Fは變數$ x_1に關して單調增加すると言ふ
論理函數$ F(x_1,x_2,\dots,x_n)が全ての變數に關して單調增加するならば、$ Fを單調增加函數 (monotone increasing function。正函數 (positive function)) と呼ぶ
論理積・論理和だけで表現できる
論理函數$ F(x_1,x_2,\dots,x_n)が$ F(0,x_2,\dots,x_n)\ge F(1,x_2,\dots,x_n)ならば、$ Fは變數$ x_1に關して單調減少すると言ふ
論理函數$ F(x_1,x_2,\dots,x_n)が全ての變數に關して單調減少するならば、$ Fを單調減少函數 (monotone decreasing function。負函數 (negative function)) と呼ぶ
單調增加函數と單調減少函數を合はせて單調函數と呼ぶ 論理函數$ F(x_1,x_2,\dots,x_n)の全ての變數が、各々に關して單調增加するもしくは單調減少するならば、$ Fを unate 函數 (unate function) と呼ぶ
雙對
$ F(x_1,\dots,x_n)の雙對とは$ \neg F(\neg x_1,\dots,\neg x_n)を言ふ
$ x_1\supset x_2の雙對は$ \neg(x_1\subset x_2)、つまり對偶 標準形
選言標準形 (DNF) (disjunctive normal form。積和標準形 (canonical sum-of-products form)。加法標準形。主加法標準形。最小項展開 (minterm expansion)) $ (x_1\lor\dots\lor x_l)\land\dots\land(x_m\lor\dots\lor x_n)
Shannon 展開 (Shannon's expansion)
節標準形 (CNF (clausal normal form))
連言標準形 (CNF) (conjunctive normal form。和積標準形 (canonical product-of-sums form)。乘法標準形。主乘法標準形。最大項展開 (maxterm expansion)) $ (x_1\land\dots\land x_l)\lor\dots\lor(x_m\land\dots\land x_n)
否定標準形 (NNF (negation normal form))
環和標準形 (RSNF (RNF。ring sum normal form)。リード・マラー標準形 (Reed-Muller canonical form)。ANF (algebraic normal form))
Davio 展開
正極性 Davio 展開 (positive Davio's expansion)
負極性 Davio 展開 (negative Davio's expansion)
冠頭標準形 (prenex normal form)
Skolem 標準形 (Skolem normal form)