동치

최근 수정 시각: (5년 전)
분류
同値 / Equivalence
목차
1. 집합론에서의 동치관계2. 논리학에서의 동치
2.1. 실질적 동치2.2. 논리적 동치
2.2.1. 논리적 동치의 예시
2.2.1.1. 이중부정2.2.1.2. 결합규칙2.2.1.3. 한마디법(동어반복)2.2.1.4. 분배규칙2.2.1.5. 드모르간 규칙2.2.1.6. 자리뒤집기2.2.1.7. 자리바꾸기2.2.1.8. 전건규칙2.2.1.9. 선언화/조건화(단순함축)2.2.1.10. 조건문의 정의(단순함언)2.2.1.11. 쌍조건문의 정의(단순동치)2.2.1.12. 쌍조건문의 부정

1. 집합론에서의 동치관계 [편집]

논리학 및 집합론에서의 이항 관계의 일종. 자세한 사항은 항목 참조

2. 논리학에서의 동치 [편집]

논리학에서 두 식 혹은 문장 간에 성립하는 관계. 상기한 동치관계의 일종이라고도 볼 수 있다. 크게 실질적 동치와 논리적 동치로 나뉜다.

2.1. 실질적 동치 [편집]

두 문장 간에 필요충분조건이 성립하는 경우를 두고 두 문장 간에 실질적 동치(material equivalence)가 성립한다고 말한다. 즉 두 문장 PP와 QQ가 동치일 경우 오직 그 경우에 P↔QP \leftrightarrow Q는 참이다. 동일률이라고도 한다.

명제 논리 언어 P↔QP \leftrightarrow Q의 참 여부는 주어진 모형/해석에 따라 달라지므로, 곧 두 문장 간의 실질적 동치 여부는 모형/해석 여부에 따라 달라진다. 즉 두 문장 간의 실질적 동치는 두 문장의 형식에 의한 것일 필요가 없다. 자세한 사항은 필요충분조건 항목 참조.

2.2. 논리적 동치 [편집]

문장 PP가 문장 QQ의 논리적 귀결이며, 또한 반대로 QQ가 PP의 논리적 귀결인 것을 두고 두 문장 PP와 QQ 간에 논리적 동치(logical equivalence)가 성립한다고 말한다.

의미론/모형이론적으로 말하자면 PP와 QQ는 모든 모형/해석에서 진리치가 같을 경우 오직 그 경우에 논리적으로 동치다. 따라서 논리적 동치는 실질적 동치이지만, 그 역은 성립하지 않는다. 즉 일상적으로 말하자면 두 문장 간의 논리적 동치는 두 문장의 형식에 의한 것이라고 말할 수 있다[1].

2.2.1. 논리적 동치의 예시 [편집]

표준적인 명제 논리에서 도출되는 대표적인 논리적 동치의 예시들은 다음과 같다.
2.2.1.1. 이중부정 [편집]
P≡¬(¬p)P\equiv \neg \left(\neg p \right)
2.2.1.2. 결합규칙 [편집]
[p&(q&r)]≡[(p&q)&r]\left[p \& \left(q \& r \right) \right] \equiv \left[\left(p \& q \right) \& r \right]
[p∨(q∨r)]≡[(p∨q)∨r]\left[p \vee \left(q \vee r \right) \right] \equiv \left[\left( p \vee q \right) \vee r \right]
2.2.1.3. 한마디법(동어반복) [편집]
(p&p)≡p\left(p \& p \right)\equiv p
(p∨p)≡p\left(p \vee p \right)\equiv p
2.2.1.4. 분배규칙 [편집]
[p&(q∨r)]≡[(p&q)∨(p&r)] \left[p \& \left( q \vee r\right)\right] \equiv \left[\left( p \& q \right) \vee \left( p \& r \right)\right]
[p∨(q&r)]≡[(p∨q)&(p∨r)] \left[p \vee \left( q \& r \right)\right] \equiv \left[\left( p \vee q \right) \& \left( p \vee r \right) \right]
2.2.1.5. 드모르간 규칙 [편집]
¬(p∨q)≡(¬p&¬q) \neg \left(p \vee q \right) \equiv \left( \neg p \& \neg q \right)
¬(p&q)≡(¬p∨¬q) \neg \left(p \& q \right) \equiv \left( \neg p \vee \neg q \right)
2.2.1.6. 자리뒤집기 [편집]
(p→q)≡(¬q→¬p) \left( p \rightarrow q \right) \equiv \left( \neg q \rightarrow \neg p \right)
2.2.1.7. 자리바꾸기 [편집]
(p↔q)≡(q↔p) \left( p \leftrightarrow q \right) \equiv \left( q \leftrightarrow p \right)
(p&q)≡(q&p) \left( p \& q \right) \equiv \left( q \& p \right)
(p∨q)≡(q∨p) \left( p \vee q \right) \equiv \left( q \vee p \right)
2.2.1.8. 전건규칙 [편집]
[(p&q)→r]≡[p→(q→r)] \left[ \left( p \& q \right) \rightarrow r \right] \equiv \left[ p \rightarrow \left( q \rightarrow r \right) \right]
2.2.1.9. 선언화/조건화(단순함축) [편집]
(p→q)≡(¬p∨q) \left( p \rightarrow q \right) \equiv \left( \neg p \vee q \right)
2.2.1.10. 조건문의 정의(단순함언) [편집]
(p→q)≡¬(p&¬q) \left( p \rightarrow q \right) \equiv \neg \left( p \& \neg q \right)
2.2.1.11. 쌍조건문의 정의(단순동치) [편집]
(p↔q)≡[(p→q)&(q→p)] \left( p \leftrightarrow q \right) \equiv \left[ \left( p \rightarrow q \right) \& \left( q \rightarrow p \right) \right]
2.2.1.12. 쌍조건문의 부정 [편집]
¬(p↔q)≡(p↔¬q) \neg \left( p \leftrightarrow q \right) \equiv \left( p \leftrightarrow \neg q \right)
[1] 논리적 동치는 두 문장의 의미에 의해서 참이 된다고 말하는 경우도 있는데, 이는 언어철학적으로는 논란이 있는 주장이다. 의미에 의해서 참이 되는 것을 두고 "분석적 참"이라고 부르는데, 분석적 참과 논리적 참은 명백히 다른 것으로 보이기 때문이다. 콰인 참조.

라이선스를 별도로 명시하지 않은 문서는 CC BY-NC-SA 2.0 KR에 따라 이용할 수 있습니다.
기여하신 문서의 저작권은 각 기여자에게 있으며, 각 기여자는 기여하신 부분의 저작권을 갖습니다.

문서의 기여자는 역사 탭에서 확인할 수 있습니다.
접두어의 N: - 나무위키 사용자, R: - 리그베다 위키의 사용자를 뜻합니다.
자세한 사항은 나무위키에서 동일한 문서의 역사를 참고하시기 바랍니다.