論理積と論理和
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2018/01/28 04:15 UTC 版)
論理積と論理和の規則は、 ( ∀ x ϕ ) ∧ ψ {\displaystyle (\forall x\phi )\land \psi } は ∀ x ( ϕ ∧ ψ ) {\displaystyle \forall x(\phi \land \psi )} と等価 ( ∀ x ϕ ) ∨ ψ {\displaystyle (\forall x\phi )\lor \psi } は ∀ x ( ϕ ∨ ψ ) {\displaystyle \forall x(\phi \lor \psi )} と等価 ( ∃ x ϕ ) ∧ ψ {\displaystyle (\exists x\phi )\land \psi } は ∃ x ( ϕ ∧ ψ ) {\displaystyle \exists x(\phi \land \psi )} と等価 ( ∃ x ϕ ) ∨ ψ {\displaystyle (\exists x\phi )\lor \psi } は ∃ x ( ϕ ∨ ψ ) {\displaystyle \exists x(\phi \lor \psi )} と等価 である。これらの規則は、x が ψ の中で自由変項として現れない場合に妥当である。もし x が ψ の中に自由変項として現れた場合、他の自由変項と置き換える必要がある。 例えば、環の言語で、 ( ∃ x ( x 2 = 1 ) ) ∧ ( 0 = y ) {\displaystyle (\exists x(x^{2}=1))\land (0=y)} は ∃ x ( x 2 = 1 ∧ 0 = y ) {\displaystyle \exists x(x^{2}=1\land 0=y)} と等価である。 ( ∃ x ( x 2 = 1 ) ) ∧ ( 0 = x ) {\displaystyle (\exists x(x^{2}=1))\land (0=x)} は ∃ x ( x 2 = 1 ∧ 0 = x ) {\displaystyle \exists x(x^{2}=1\land 0=x)} と等価ではない。 左の式は、自由変項 x が 0 のとき任意の環で真だが、右の式には自由変項がなく、どんな環でも偽である。
※この「論理積と論理和」の解説は、「冠頭標準形」の解説の一部です。
「論理積と論理和」を含む「冠頭標準形」の記事については、「冠頭標準形」の概要を参照ください。
- 論理積と論理和のページへのリンク