동치
덤프버전 :
분류
同値 / Equivalence
1. 집합론에서의 동치관계[편집]
논리학 및 집합론에서의 이항 관계의 일종. 자세한 사항은 항목 참조
2. 논리학에서의 동치[편집]
논리학에서 두 식 혹은 문장 간에 성립하는 관계. 상기한 동치관계의 일종이라고도 볼 수 있다. 크게 실질적 동치와 논리적 동치로 나뉜다.
2.1. 실질적 동치[편집]
두 문장 간에 필요충분조건이 성립하는 경우를 두고 두 문장 간에 실질적 동치(material equivalence)가 성립한다고 말한다. 즉 두 문장 [math(P)]와 [math(Q)]가 동치일 경우 오직 그 경우에 [math(P \leftrightarrow Q)]는 참이다. 동일률이라고도 한다.
명제 논리 언어 [math(P \leftrightarrow Q)]의 참 여부는 주어진 모형/해석에 따라 달라지므로, 곧 두 문장 간의 실질적 동치 여부는 모형/해석 여부에 따라 달라진다. 즉 두 문장 간의 실질적 동치는 두 문장의 형식에 의한 것일 필요가 없다. 자세한 사항은 필요충분조건 항목 참조.
2.2. 논리적 동치[편집]
문장 [math(P)]가 문장 [math(Q)]의 논리적 귀결이며, 또한 반대로 [math(Q)]가 [math(P)]의 논리적 귀결인 것을 두고 두 문장 [math(P)]와 [math(Q)] 간에 논리적 동치(logical equivalence)가 성립한다고 말한다.
의미론/모형이론적으로 말하자면 [math(P)]와 [math(Q)]는 모든 모형/해석에서 진리치가 같을 경우 오직 그 경우에 논리적으로 동치다. 따라서 논리적 동치는 실질적 동치이지만, 그 역은 성립하지 않는다. 즉 일상적으로 말하자면 두 문장 간의 논리적 동치는 두 문장의 형식에 의한 것이라고 말할 수 있다[1] .
2.2.1. 논리적 동치의 예시[편집]
표준적인 명제 논리에서 도출되는 대표적인 논리적 동치의 예시들은 다음과 같다.
2.2.1.1. 이중부정[편집]
[math(p\equiv \neg \left(\neg p \right) )]
2.2.1.2. 결합규칙[편집]
[math(\left[p \wedge \left(q \wedge r \right) \right] \equiv \left[\left(p \wedge q \right) \wedge r \right] )]
[math(\left[p \vee \left(q \vee r \right) \right] \equiv \left[\left( p \vee q \right) \vee r \right] )]
[math(\left[p \vee \left(q \vee r \right) \right] \equiv \left[\left( p \vee q \right) \vee r \right] )]
2.2.1.3. 한마디법(동어반복)[편집]
[math(\left(p \wedge p \right)\equiv p )]
[math(\left(p \vee p \right)\equiv p )]
[math(\left(p \vee p \right)\equiv p )]
2.2.1.4. 분배규칙[편집]
[math( \left[p \wedge \left( q \vee r\right)\right] \equiv \left[\left( p \wedge q \right) \vee \left( p \wedge r \right)\right] )]
[math( \left[p \vee \left( q \wedge r \right)\right] \equiv \left[\left( p \vee q \right) \wedge \left( p \vee r \right) \right] )]
[math( \left[p \vee \left( q \wedge r \right)\right] \equiv \left[\left( p \vee q \right) \wedge \left( p \vee r \right) \right] )]
2.2.1.5. 드모르간 규칙[편집]
[math( \neg \left(p \vee q \right) \equiv \left( \neg p \wedge \neg q \right) )]
[math( \neg \left(p \wedge q \right) \equiv \left( \neg p \vee \neg q \right) )]
[math( \neg \left(p \wedge q \right) \equiv \left( \neg p \vee \neg q \right) )]
2.2.1.6. 자리뒤집기[편집]
[math( \left( p \rightarrow q \right) \equiv \left( \neg q \rightarrow \neg p \right) )]
2.2.1.7. 자리바꾸기[편집]
[math( \left( p \leftrightarrow q \right) \equiv \left( q \leftrightarrow p \right) )]
[math( \left( p \wedge q \right) \equiv \left( q \wedge p \right) )]
[math( \left( p \vee q \right) \equiv \left( q \vee p \right) )]
[math( \left( p \wedge q \right) \equiv \left( q \wedge p \right) )]
[math( \left( p \vee q \right) \equiv \left( q \vee p \right) )]
2.2.1.8. 전건규칙[편집]
[math( \left[ \left( p \wedge q \right) \rightarrow r \right] \equiv \left[ p \rightarrow \left( q \rightarrow r \right) \right] )]
2.2.1.9. 선언화/조건화(단순함축)[편집]
[math( \left( p \rightarrow q \right) \equiv \left( \neg p \vee q \right) )]
2.2.1.10. 조건문의 정의(단순함언)[편집]
[math( \left( p \rightarrow q \right) \equiv \neg \left( p \wedge \neg q \right) )]
2.2.1.11. 쌍조건문의 정의(단순동치)[편집]
[math( \left( p \leftrightarrow q \right) \equiv \left[ \left( p \rightarrow q \right) \wedge \left( q \rightarrow p \right) \right] )]
2.2.1.12. 쌍조건문의 부정[편집]
[math( \neg \left( p \leftrightarrow q \right) \equiv \left( p \leftrightarrow \neg q \right) )]
이 문서의 내용 중 전체 또는 일부는 2023-11-24 07:48:01에 나무위키 동치 문서에서 가져왔습니다.