命題論理: 同値関係と標準形

n個の原子命題からなる論理式は、#Bn = 2^2^n 個あるf: 2^n → 2 なる関数と同一視できる。この同一視（意味論的同値関係）は、数学でいうところの同値関係（同一律、反射律、推移律を満たす）であるため、n個の原子命題からなる論理式全体からなる集合 Fn は意味論的同値関係によってパーティショニングすることができる。そして、各パーティションは、DNFもしくはCNFの形式の論理式で代表させることができる。別の言い方をすると、任意の論理式はDNFもしくはCNFと意味論的同値関係にある。

さらに、意味論的同値関係は、congruenceな関係でもある。それにより、論理式の一部を、意味論的同値関係にある別の論理式に置換してもよいという定理が得られる。

さらにさらに、δ: F→F を、帰納的に以下で定める。すなわち、 π→π, ￢α→￢δ(α), α∧β→δ(α)∨δ(β), α∨β→δ(α)∧δ(β)。このようなδで射影される二つの論理式 φ→ψを双対関係という。DNFとCNFは互いに双対関係であり、また、δδ=1である。