동치

다른 뜻에 대해서는 동치 (동음이의) 문서를 참고하십시오.

논리학에서, 동치(同値, 영어: equivalence) 또는 논리적 동치(論理的同値, 영어: logical equivalence)는 두 명제가 참인지 여부가 항상 같은 관계이다.

정의

1차 논리의 두 공식 $\phi$, $\psi$가 다음 두 조건을 만족시키면, 두 공식이 서로 동치(영어: equivalent)라고 한다.

• $\phi \models \psi$. 즉, 모든 1차 논리 구조 $M$ 및 $\phi$, $\psi$의 자유 변수의 치환 ${\vec {x}}\mapsto {\vec {a}}$에 대하여, 만약 $M\models \phi [{\vec {a}}/{\vec {x}}]$라면, $M\models \psi [{\vec {a}}/{\vec {x}}]$
• $\psi \models \phi$. 즉, 모든 1차 논리 구조 $M$ 및 $\psi$, $\phi$의 자유 변수의 치환 ${\vec {x}}\mapsto {\vec {a}}$에 대하여, 만약 $M\models \psi [{\vec {a}}/{\vec {x}}]$라면, $M\models \phi [{\vec {a}}/{\vec {x}}]$

괴델의 완전성 정리에 따라, 이는 $\phi$, $\psi$가 다음 두 조건을 만족시키는 것과 같다.

• $\phi \vdash \psi$. 즉, $\psi$의 $\phi$를 가정한 증명이 존재한다.
• $\psi \vdash \phi$. 즉, $\phi$의 $\psi$를 가정한 증명이 존재한다.

실질 쌍조건문과의 관계

실질 쌍조건문 $\iff$은 실질 동치라고도 불리며, 이는 1차 논리의 기호 가운데 하나다. 두 공식 $\phi$와 $\psi$에 대하여, 실질 쌍조건문 $\phi \iff \psi$ 역시 공식이다. 만약 두 1차 논리 공식 $\phi$와 $\psi$가 동치라면, $\phi \iff \psi$는 모든 구조에서 참이다. 반대로, 만약 $\phi \iff \psi$가 모든 구조에서 참이라면, $\phi$와 $\psi$는 동치이다. 괴델의 완전성 정리에 따라, 만약 $\phi$와 $\psi$가 동치라면 $\phi \iff \psi$의 공집합을 가정한 증명이 존재하며, 반대로 만약 $\phi \iff \psi$의 공집합을 가정한 증명이 존재한다면 $\phi$와 $\psi$는 동치이다. 따라서, $\phi$와 $\psi$가 동치임은 기호로

$\models \;\phi \iff \psi$

또는

$\vdash \;\phi \iff \psi$

와 같이 나타낼 수 있다.

성질

논리적 동치는 동치 관계의 원형이다. 구체적으로,

• 모든 공식 $\phi$에 대하여 $\models \;\phi \iff \phi$이다.
• 만약 $\models \;\phi \iff \psi$라면, $\models \;\psi \iff \phi$이다.
• 만약 $\models \;\phi \iff \psi$이며 $\models \;\psi \iff \chi$라면, $\models \;\phi \iff \chi$이다.

만약

$\models \;\phi \iff \phi '$

$\models \;\psi \iff \psi '$

라면,

$\models \;(\phi \lor \psi )\iff (\phi '\lor \psi ')$

$\models \;(\phi \land \psi )\iff (\phi '\land \psi ')$

$\models \;(\phi \implies \psi )\iff (\phi '\implies \psi ')$

$\models \;(\lnot \phi )\iff (\lnot \phi ')$

이며, 변수 $x$에 대하여

$\models \;(\forall x\colon \phi )\iff (\forall x\colon \phi ')$

$\models \;(\exists x\colon \phi )\iff (\exists x\colon \phi ')$

이다.

예

1차 논리의 두 공식 사이의 동치의 예로는 다음을 들 수 있다. 여기서, $\phi$는 임의의 공식, $\top$는 항상 참인 공식, $\bot$는 항상 거짓인 공식을 나타낸다.

• 교환 법칙
  • $\models \;(\phi \lor \psi )\iff (\psi \lor \phi )$
  • $\models \;(\phi \land \psi )\iff (\psi \land \phi )$
• 결합 법칙
  • $\models \;((\phi \lor \psi )\lor \chi )\iff (\phi \lor (\psi \lor \chi ))$
  • $\models \;((\phi \land \psi )\land \chi )\iff (\phi \land (\psi \land \chi ))$
• 항등원
  • $\models \;(\phi \lor \bot )\iff \phi$
  • $\models \;(\phi \land \top )\iff \phi$
• 분배 법칙
  • $\models \;(\phi \lor (\psi \land \chi ))\iff ((\phi \lor \psi )\land (\phi \lor \chi ))$
  • $\models \;(\phi \land (\psi \lor \chi ))\iff ((\phi \land \psi )\lor (\phi \land \chi ))$
• 흡수 법칙
  • $\models \;(\phi \lor (\phi \land \psi ))\iff \phi$
  • $\models \;(\phi \land (\phi \lor \psi ))\iff \phi$
• 이중 부정의 소거
  • $\models \;(\lnot \lnot \phi )\iff \phi$
• 드 모르간의 법칙
  • $\models \;(\lnot \phi \land \lnot \psi )\iff \lnot (\phi \lor \psi )$
  • $\models \;(\lnot \phi \lor \lnot \psi )\iff \lnot (\phi \land \psi )$
• 참과 거짓의 관계
  • $\models \;(\lnot \top )\iff \bot$
  • $\models \;(\lnot \bot )\iff \top$
• 실질 조건문의 정의
  • $\models \;(\phi \implies \psi )\iff (\lnot \phi \lor \psi )$
• 실질 쌍조건문의 정의
  • $\models \;(\phi \iff \psi )\iff ((\phi \implies \psi )\land (\psi \implies \phi ))$

특히, 명제 논리의 공식들은 논리적 동치 아래 불 대수를 이룬다.

추가로, 한정 기호가 등장하는 공식들 사이에 다음과 같은 동치가 있다. 여기서, $\phi$에는 $\forall x\colon$가 등장하지 않으며, $\psi$에는 $x$가 등장하지 않는다.

• 드 모르간의 법칙
  • $\models \;(\lnot \exists x\colon \phi )\iff (\forall x\colon \lnot \phi )$
  • $\models \;(\lnot \forall x\colon \phi )\iff (\exists x\colon \lnot \phi )$
• 분배 법칙
  • $\models \;((\exists x\colon \phi )\lor \psi )\iff (\exists x\colon (\phi \lor \psi ))$
  • $\models \;((\forall x\colon \phi )\lor \psi )\iff (\forall x\colon (\phi \lor \psi ))$
  • $\models \;((\exists x\colon \phi )\land \psi )\iff (\exists x\colon (\phi \land \psi ))$
  • $\models \;((\forall x\colon \phi )\land \psi )\iff (\forall x\colon (\phi \land \psi ))$

이는 1차 논리 공식의 프리넥스 표준형을 구하는 과정을 나타낸다.

같이 보기

• 논리적 귀결
• 필요충분조건