論理演算

真偽値に対する演算。

演算	記号	真になる条件
否定	$\neg P$	$P$ が偽
論理積	$P\wedge Q$	両方真
論理和	$P\vee Q$	どちらか真
排他的論理和	$P\oplus ︎Q$	ちょうど一方が真
含意	$P\to Q$	$P$ が偽、または $Q$ が真

ド・モルガンの法則#

$$\neg (P\wedge Q)=\neg P\vee \neg Q,\neg (P\vee Q)=\neg P\wedge \neg Q$$

否定を内側に押し込むと and と or が入れ替わる。 集合の補集合でも同じ形が成り立つ。

完全性#

NAND だけですべての論理演算を表せる（機能的完全性）。 $\neg P=P\uparrow P$、$P\wedge Q=\neg (P\uparrow Q)$ など。 デジタル回路が NAND を基本素子にできるのはこの性質による。

量子ゲートとの違い#

古典の論理演算は多くが不可逆（AND は 2 ビットから 1 ビット）。 量子ゲートは全単射でなければならないため、 そのままでは使えない。

Toffoli ゲート（CCNOT）は 3 ビットを 3 ビットに写す可逆な演算で、 これ 1 つで古典の論理演算をすべて可逆に実現できる。 量子回路で古典計算を行うときの土台になる。

参考文献#

• Kenneth H. Rosen. Discrete Mathematics and Its Applications, 8th ed. McGraw-Hill, 2019. https://www.mheducation.com/highered/product/discrete-mathematics-applications-rosen/M9781259676512.html
• Michael A. Nielsen, Isaac L. Chuang. Quantum Computation and Quantum Information, §1.4, §3.2. Cambridge University Press, 2010. https://doi.org/10.1017/CBO9780511976667