동치

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

논리학과 수학에서, 논리적 동치(同値, 영어: (logical) equivalence) 또는 동치란 두 명제의 진릿값이 항상 같은 것이다. 두 명제 $p$와 $q$가 동치라는 것은 두 명제가 서로 필요충분조건이라는 것과 같다. 즉 $p$가 참이면 $q$도 참이고, $p$가 거짓이면 $q$도 거짓임을 의미한다. 기호로는 $p\equiv q$ 또는 $p\Leftrightarrow q$로 쓴다. 실질적 동치(영어: material equivalence)도 같은 기호를 쓰는데, 논리적 동치와 실질적 동치는 비슷하지만 다른 개념이므로 문맥에 따라 적절하게 이해해야 한다.

논리적 동치

논리학에는 법칙 또는 성질로 부르는 많은 논리적 동치들이 존재하며, 아래 테이블은 그 중 일부를 논리식으로 나타낸 것이다. 기호의 의미는 수학 기호와 논리 기호에서 찾아볼 수 있으며, $p,q,r$은 명제이다. 예를 들어, 논리식 $p\wedge \top \equiv p$는

'$p$이고 항상 참이다'와 '$p$'는 동치이다.

라는 의미이다.

일반적인 논리적 동치

동치	이름
$p\wedge \top \equiv p$ $p\vee \bot \equiv p$	항등 법칙
$p\vee \top \equiv \top$ $p\wedge \bot \equiv \bot$	지배 법칙
$p\vee p\equiv p$ $p\wedge p\equiv p$	멱등 법칙
$\neg (\neg p)\equiv p$	이중 부정 법칙
$p\vee q\equiv q\vee p$ $p\wedge q\equiv q\wedge p$	교환 법칙
$(p\vee q)\vee r\equiv p\vee (q\vee r)$ $(p\wedge q)\wedge r\equiv p\wedge (q\wedge r)$	결합 법칙
$p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)$ $p\wedge (q\vee r)\equiv (p\wedge q)\vee (p\wedge r)$	분배 법칙
$\neg (p\wedge q)\equiv \neg p\vee \neg q$ $\neg (p\vee q)\equiv \neg p\wedge \neg q$	드 모르간의 법칙
$p\vee (p\wedge q)\equiv p$ $p\wedge (p\vee q)\equiv p$	흡수 법칙
$p\vee \neg p\equiv \top$ $p\wedge \neg p\equiv \bot$	부정 법칙

조건문을 포함하는 논리적 동치

1. $p\rightarrow q\equiv \neg p\vee q$
2. $p\rightarrow q\equiv \neg q\rightarrow \neg p$
3. $p\vee q\equiv \neg p\rightarrow q$
4. $p\wedge q\equiv \neg (p\rightarrow \neg q)$
5. $\neg (p\rightarrow q)\equiv p\wedge \neg q$
6. $(p\rightarrow q)\wedge (p\rightarrow r)\equiv p\rightarrow (q\wedge r)$
7. $(p\rightarrow q)\vee (p\rightarrow r)\equiv p\rightarrow (q\vee r)$
8. $(p\rightarrow r)\wedge (q\rightarrow r)\equiv (p\vee q)\rightarrow r$
9. $(p\rightarrow r)\vee (q\rightarrow r)\equiv (p\wedge q)\rightarrow r$

쌍조건문을 포함하는 논리적 동치

1. $p\leftrightarrow q\equiv (p\rightarrow q)\wedge (q\rightarrow p)$
2. $p\leftrightarrow q\equiv \neg p\leftrightarrow \neg q$
3. $p\leftrightarrow q\equiv (p\wedge q)\vee (\neg p\wedge \neg q)$
4. $\neg (p\leftrightarrow q)\equiv \neg p\leftrightarrow q$
5. $\neg (p\leftrightarrow q)\equiv p\leftrightarrow \neg q$
6. $\neg (p\leftrightarrow q)\equiv p\oplus q$

$\oplus$는 배타적 논리합이다.

실질적 동치와의 관계

논리적 동치는 실질적 동치와 다르기 때문에, 둘을 혼동해서는 안 된다.

두 명제 $p,q$가 실질적 동치(영어: material equivalence)임을 기호로 $p\leftrightarrow q$, $p\Leftrightarrow q$ 또는 $p\equiv q$로 쓴다. 이 논리식을 쌍조건문(영어: (logical) biconditional)이라 한다. 쌍조건문 $p\leftrightarrow q$는, $p$와 $q$가 동시에 참이거나 동시에 거짓일 때만 참이 되는 명제이다.

쌍조건문으로 나타내는 실질적 동치는 그 자체로 참이거나 거짓일 수 있는 명제이며, 논리적 동치는 두 명제가 항상 같은 진릿값을 가진다는 결론을 나타내는 메타언어이다. 즉 실질적 동치는 두 명제를 연결하여 하나의 새로운 명제를 만들어내는 논리 연산의 결과물이며, 논리적 동치는 그 문장이 항상 참임을 나타내는 관계이다. 다시 말해 $p$와 $q$가 논리적 동치라면, $p\leftrightarrow q$라는 쌍조건문은 항진명제가 된다.

같이 보기

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