情報科学 › コンピュータサイエンス基礎 › コンピュータアーキテクチャとCPUの構造

加法標準形と AND・OR・NOT の完全性

定理 2.3（「コンピュータアーキテクチャとCPUの構造」§2） ・ ✓公理まで証明済み

n≥1n \ge 1 とし、f:{0,1}n→{0,1}f : \{0,1\}^n \to \{0,1\} を任意のブール関数とします。このとき ff は、変数 x1,…,xnx_1, \ldots, x_n と演算 ∧,∨,¬\land, \lor, \lnot のみを用いた式で表せます。具体的には、a=(a1,…,an)∈{0,1}na = (a_1,\ldots,a_n) \in \{0,1\}^n に対し

ma(x1,…,xn)=⋀i=1nxiai,x1=x,x0=¬xm_a(x_1,\ldots,x_n) = \bigwedge_{i=1}^{n} x_i^{a_i}, \qquad x^1 = x,\quad x^0 = \lnot x

と定めると、ff が恒等的に 00 でない場合には

f(x1,…,xn)=⋁a∈f−1(1)ma(x1,…,xn)f(x_1,\ldots,x_n) = \bigvee_{a \in f^{-1}(1)} m_a(x_1,\ldots,x_n)

が成り立ちます。ff が恒等的に 00 の場合は f=x1∧¬x1f = x_1 \land \lnot x_1 と表せます。

本文で読む（証明と前後の説明）→

閉包の状態

✓ 公理まで証明済み

証明が使う定理を 前提 としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています。

印の意味: ✓公理まで証明済み ・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は 閉包の状況。

前提をたどる 証明が使う定理・定義

証明は Rikai の他の定理を参照していません（定義と論理だけで示されています）。

これを使っている定理 証明で参照している 1 件

関連するノック 4 問