명제 논리

1. 개요[편집]

---

명제논리(命題論理, propositional logic) 혹은 문장논리(文章論理, sentential logic)는 명제 혹은 문장들 간의 논리적 관계를 다룬다. 즉 예를 들어 <소크라테스는 사람이다>라는 명제를 기호화한다면, 이를 그냥 통째로 "P"로 표시할 뿐 더이상 쪼개 들어가질 않는다. 이런 명제들은 알파벳 대문자 (e.g. P, Q, R ...)로 기호화하는 것이 관례다. 명제 논리는 양화 논리의 특수한 경우로 생각할 수 있다.
[math( )]

명제논리는 결정가능(decidable)하다. 즉 임의의 명제 논리식이 타당한지 (혹은 두 명제 논리식 간에 논리적 도출 관계가 성립하는지) 여부는 기계적으로 판단할 수 있다. 아래에서 설명될 진리표(truth-table)를 사용하는 것이 그런 기계적 판단 방식의 대표적인 예시다. 논리식의 타당성을 기계적으로 판단할 수 있다는 것은, 명제 논리 체계에서는 동어반복적 문장이 곧 타당한 문장이며, 타당한 문장이 곧 동어반복적 문장이라는 것이다.

2. 명제 논리에서의 해석[편집]

---

명제 논리에서의 해석(interpretation)은 각 명제에 진리값을 할당하는 것이다. 예를 들어 [math((P\;\&\;Q\;\&\;R))]이라는 문장이 있다고 생각해보자. 여기서 각 명제에 [math(T)]를 할당하는 것은 한 가지 해석이다. 각각의 명제는 [math(T)]이거나 [math(F)]일 수 있으므로, [math(n)]개의 명제가 있는 문장은 [math(2^n)]개의 해석이 가능하다. 즉 이상의 예에서는 다음과 같은 여덟 가지의 해석이 가능하다는 것이다.

1. [math(\{T,\,T,\,T\})]
2. [math(\{T,\,T,\,F\})]
3. [math(\{T,\,F,\,T\})]
4. [math(\{T,\,F,\,F\})]
5. [math(\{F,\,T,\,T\})]
6. [math(\{F,\,T,\,F\})]
7. [math(\{F,\,F,\,T\})]
8. [math(\{F,\,F,\,F\})]

이러한 해석의 정의에 따라 명제 논리에서의 타당성, 귀결, 일관성이 다음과 같이 정의될 수 있다.

• 문장 [math(\phi)]가 모든 해석 하에서 참일 경우 문장 [math(\phi)]는 타당하다.
• 문장 [math(\phi)]와 문장집합 [math(\Gamma)]에 대해, [math(\Gamma)]의 모든 문장들을 참이게 하면서 [math(\phi)]를 거짓이게 하는 해석이 존재하지 않을 경우 [math(\phi)]는 [math(\Gamma)]의 귀결이다.
• 문장집합 [math(\Gamma)]에 대해, [math(\Gamma)]의 모든 문장들을 참이게 하는 해석이 하나라도 존재할 경우 [math(\Gamma)]는 일관적이다.

3. 명제논리 연결사[편집]

---

명제 논리에서 연결사(connective)는 한 개 이상의 명제 기호에 덧붙여짐으로써 해당 명제(들)에 새로운 의미를 더한다. 꼭 복수의 명제들을 '연결'할 필요없이 하나의 명제에만 붙는 연결사도 있음을 유의하라(예. [math(\sim)]).

연결사를 포함하지 않은 명제를 단순 명제라고 하며, 단순 명제와 하나 이상의 논리 연결사로 구성되는 명제를 복합 명제라고 한다[4]. 복잡한 구조를 가진 복합 명제들에서는 두 개 이상의 논리 연결사와 괄호들이 사용되기도 하는데, 이때 주요 부분을 연결해 주는 논리 연결사를 ‘주 논리 연결사’라고 한다.

아래에 언급된 명제 연결사들은 일반적으로 명제 논리에서 등장하는 연결사들이다.

이들의 의미는 진리표를 통해 엄밀하게 규정될 수 있다. 진리표는 피연산자의 진리치(참=T, 거짓=F)에 따라 연결사가 덧붙여진 새로운 명제의 진리치가 어떤 것이 되는지를 표시해준다.

예를 들어 임의의 2항 연결사인 ⊙가 어떻게 진리표를 통해 정의되는지 알아보기 위해 다음 예시를 참고하라:


해당 진리표는 ⊙의 진리표를 도식화시킨 것이다. 앞의 두 열은 피연산자인 명제 P와 Q가 갖는 진리치의 모든 가능한 배열을 망라한 것이다. 이때 가능한 배열의 경우의 수는 4이므로, 곧 행의 수가 넷이다. 마지막 세 번째 열은 이런 4가지 경우의 수 각각마다 ⊙가 붙었을 때의 연산 결과를 나타내며, 그 결과인 변수 α, β, γ, δ의 값 또한 각각 T 혹은 F다. 즉 이때 α, β, γ, δ이 어떤 값을 갖느냐에 따라 연결사 ⊙의 성격이 정의된다.

더불어 아래 명제 연결사만이 명제 논리의 확고부동한 연결사라고 생각할 필요는 없다. 예를 들어 [math(\vee, \wedge)]가 [math(\neg, \to)]에 의해 정의될 수 있음은 명백하며, 극단적으로는 하나의 연결사만으로도 모든 명제 논리를 포괄하는 것도 가능하다(예. Sheffer Stroke '|').

이하의 연결사 설명은 원칙적으로 메타 문장인 그리스어 문자로 기술되어야 하지만, 편의상 영문 알파벳 대문자로 기술한다.

3.1. 부정 (NOT; ¬, ~, -)[편집]

---

Negation ([math(\sim)] 혹은 [math(\neg)] 혹은 -)
예를 들어 "망치를 가져와라" 라고 했을 때, 망치가 아닌 무엇인가를 가지고 가는 경우에 해당한다.

3.2. 선언 (OR; ∨) [편집]

---

BEJ48의 노래에 대한 내용은 宣言 문서 참고하십시오.




選言 Disjunction 논리합 ([math(\vee)]) [6]

[math(P\vee Q)]라고 하면 [math(P)], [math(Q)] 중 적어도 하나는 성립한다는 것을 뜻한다. 둘 중 하나만 성립하는 것이 아니며, [math(P)]와 [math(Q)] 둘 모두 성립해도 된다. 이때 [math(P)]와 [math(Q)]를 "선언지(disjunct)"라고 부르기도 한다.
예를 들어 "망치 또는 빠루를 가져와라"라고 했을 때, 망치를 가져 와도 참이고, 빠루를 가져 와도 참이며, 망치와 빠루를 들고 와도 참이다.
진리표는 다음과 같다.

"∨"는 한국어의 "혹은", 영어의 "or"에 대응하는 것 같지만, 일상 언어 표현들의 경우 두 선언지 가운데 하나를 선택해야만 하는 것 같은 직관이 있다. 예를 들어 "망치를 사용하시겠습니까, 혹은 빠루를 사용하시겠습니까?"라고 물어봤을 땐 망치와 빠루 중 하나만을 선택해야할 것 같다. 하지만 위에서 나타나다시피 "∨"를 쓴 문장인 "(망치를 쓴다) ∨ (빠루를 쓴다)"는 망치만 휘둘러도, 빠루를 휘둘러도, 망치와 빠루를 둘 다 양손에 하나씩 들고 사용해도 된다.
이러한 직관이 나타나는 이유는 우리말에서는 흔히 "그리고"와 "또는"을 다른 의미로 구분하기 때문이다.[7] 일상적으로 우리는 "또는"을 "그리고"와 다른 의미로 구별하기 때문에(즉, '또는'을 배타적 선언으로 인식하기 때문에) 망치 또는 빠루를 가져오라는 말을 들었을 때 "망치 그리고 빠루를 가져간다"는 선택지를 배제하게 되고, 마찬가지로 이를 요청한 쪽에서도 둘 다 시행하는 경우는 생각하지 않는다. 그렇지만 논리기술적으로는 P와 Q 둘 중의 하나 혹은(∨) P와 Q 둘 모두를 포함하는 기호를 만들어두는 것이 편리하기 때문에 해당 선택지도 포함하게 되므로 헷갈리지 말도록 하자.
영어에서는 양쪽 다 선택하는 or both와 같은 표현을 뒤에 붙이기도 한다.

3.2.1. 배타적 선언 (XOR; ⊕)[편집]

---

Exclusive OR 배타 논리합 ([math(\oplus)]')

'둘 중 하나'만을 지시하는 선언문. 즉 "[math(P\oplus Q)]"가 참이면 [math(P)]와 [math(Q)] 둘 중 하나만 참이다. 이는 [math(\wedge)]와 [math(\vee)] 기호를 통해 정의될 수 있다. 즉 "[math(P\oplus Q)]"는 "[math((P\vee Q)\wedge{\sim}(P\wedge Q))]"와 동치다.

[math(P)]와 [math(Q)] 모두 참일 때는 거짓임을 볼 수 있다. 또한 [math(P\vee Q)]는 [math({\sim}({\sim}P\wedge{\sim}Q))]와 동치이므로, 선언문은 [math(\wedge)]와 [math(\sim)]만을 이용해 나타낼 수도 있다.

수학(하) 에서의 집합단원의 대칭차집합과 대응된다고 볼 수 있다.

3.3. 연언 (AND; ∧, &)[편집]

---

連言 Conjunction 논리곱 ([math(\wedge)] 혹은 [math(\&)]) [8]

[math(P\wedge Q)]는 [math(P)], [math(Q)] 모두 참일 때에만 참이다. 이때 [math(P)]와 [math(Q)]를 "연언지(conjunct)"라고 부른다. 한국어에선 "-와/과 -", "-이고 -다", "-이며 -다" 등에 대응한다. 예를 들어 "망치와 빠루를 가져와라"라고 했을 때, 망치와 빠루 모두 들고 와야 참이 되는 것과 같다. [math(\sim)]와 [math(\vee)]를 이용해 나타내면 [math({\sim}({\sim}P\vee{\sim}Q))]이다.

3.4. 조건문(If ... Then ...; →, ⊃, Ɔ[9]

이때 '⊃'는 집합론에서의 진부분집합을 나타내는 기호와 생김새가 비슷하지만 완전히 다른 개체임에 유의할 것. 즉 변항이 명제라는게 확실한 경우 "[math(\phi)]⊃[math(\psi)]"라는 표현을 볼 경우 이건 (수학처럼) "[math(\phi\leftarrow\psi)]"로 봐야 하는 게 아니라 정반대인 "[math(\phi\to\psi)]"로 이해해야한다. 따라서 "[math(P\to Q)]"는 "[math(P)]⊃[math(Q)]"와 같은 의미지, 수학에서 흔히 알고 있는 "[math(P\subset Q)]"가 아니다. "[math(\phi)]이면 [math(\psi)]다"라는 조건문이 부분집합 관계와 같은 것으로 생각하기 쉽기에 "[math(\phi\to\psi)]"를 "[math(\phi\subset\psi)]"라고 써야한다고 착각할 수 있다. 이 때문에 해외에서는 [math(\text{Ɔ})]로 구분해서 쓰는 경우도 있었다.

)[편집]

---

실질 조건문(material conditional) ([math(\to)], [math(\supset)], [math(\text{Ɔ})])

[math(P\to Q)]는 [math(P)]가 거짓이거나 [math(Q)]가 참인 경우 오직 그 경우에 참이다. 즉 [math(P)]가 참이고 [math(Q)]가 거짓인 경우를 제외하면 모두 참이다. 이때 [math(P)]를 "전건(antecedent)", [math(Q)]를 "후건(consequent)"이라고 부른다.


동치 문서에도 나와 있듯이, 실질 조건 문장은 정의상 선언 문장과 논리적 동치다.

[math(\left(p\to q\right)\equiv\left(\neg p\vee q\right))]

3.4.1. 자연 언어 조건문과의 괴리[편집]

---

조건문은 영어의 "If --- then ..." 구문이나 한국어의 "만약 ---면, ...다" 같은 표현에 대응한다. 하지만 실질 조건문은 이런 자연 언어의 쓰임새를 포착하는데 실패하고는 한다. 다음이 그 대표적인 예시다.

"만약 태양계 행성이 5개라면, 라멘의 원조는 일본이 아니다."

실질 조건문으로 분석할 경우 해당 문장은 참이다(진리표의 5행에 해당;F, F, T). 태양계 행성은 5개가 아니기 때문이다. 하지만 한국어 모국어 화자들은 대개 그러한 결과를 부조리하게 여긴다.

  자세한 내용은 조건문 문서를 참고하십시오.

3.5. 쌍조건문(If and Only If; ↔, iff)[편집]

---

쌍조건문(biconditional)

[math(P\leftrightarrow Q)]는 '[math(P)]인 경우 그리고 그 경우에만 [math(Q)]이다'라는 의미이다. '[math(P)]와 [math(Q)]가 동치이다', '[math(P)]이면 [math(Q)]이고 [math(Q)]이면 [math(P)]이다'와 같이 표현하기도 한다. [math((P\to Q)\;\&\;(Q\to P))]와 동치이다. [math(P)]와 [math(Q)]의 진리값이 같을 때 T가 할당된다.
예를 들어서, '누군가 총각인 경우에 오직 그 경우에만 결혼하지 않은 남자다'라는 문장은 쌍조건문이다.

3.6. 모순(Contradiction; ⊥, c)[10]

모순은 하나의 명제로 도입될 수 있지만, 무조건 거짓을 뱉는 연산자로 볼 수도 있다.

[편집]

---

'Falsum' 혹은 'Bottom'이라고도 부른다. 무조건 거짓. 무조건 참은 "Top"이라고도 부르며 [math(\top)]를 쓴다. 참은 True의 T or t모양을 따왔고, 거짓은 이 모양을 뒤집은 것이다. 표준적인 명제논리에서는 연결사가 아니다.

4. 추론과 명제논리 추론 규칙[편집]

---

귀결이 문장과 문장 사이의 의미론적 관계를 다룬다면, 추론(inference) 혹은 도출(deriviation)은 오직 형식적인 관계만을 다루는 것이다. 다른 표현으로 하자면 귀결은 의미론적(semantic) 작업이고 추론은 통사론적(syntactic) 작업이다. 추론은 귀결과는 달리 문장의 진리값이나 해석에 의존하지 않는다. 오직 형식적인 규칙만을 따라 수행하는 작업일 뿐이다. 그리고 그러한 형식적 추론이 의미론적인 귀결 관계를 보장한다는 것은 건전성 정리에 의해 증명되어 있다.

공집합으로부터 추론가능한 문장을 논리학적 정리라고 하며, 논리학적 정리인 문장은 논리적으로 타당하다. 즉, 모든 해석 하에서 참이다.

이하 내용은 명제 논리의 추론/증명 체계 중 하나인 게르하르트 겐첸(Gerhard Gentzen)[11]의 자연 연역(Natural Deduction) 방식을 소개한 것이다. 자연연역과 동등하게 강력한 추론/증명 체계로 역시 겐첸이 고안한 귀결 연산(sequent calculus)이 있고, 이와 살짝 다른 방식으로는 힐베르트 체계(Hilbert system)가 있다.

아래 규칙에서 E는 제거(elemination), I는 도입(Introduction)을 뜻한다. [math(P\Rightarrow Q)]는 명제 [math(Q)]가 가정 [math(P)]에 의존한다는 것을 뜻하는 반면, [math(P_{1},\,P_{2}\vdash Q)][12]는 [math(P_{1})], [math(P_{2})]로부터 [math(Q)]를 추론해낼 수 있다는 규칙을 나타낸다[13].

이하의 추론 규칙들은 원칙적으로 메타 문장인 그리스 문자로 기술해야 하지만, 편의상 영문 대문자로 대체한다.

4.1. 전건 긍정[편집]

---

[math({\to}{\rm E}:P\to Q,\,P\vdash Q)]

Modus Ponens

조건문이 참이고 그 전건이 참이라면, 후건은 참이다. [math({\rm MP})](modus ponens)라고 쓰기도 한다

4.1.1. 가언 삼단논법[편집]

---

[math({\rm HS}:P\to Q,\,Q\to R\vdash P\to R)]

Hypothetical syllogism

4.2. 후건 부정[편집]

---

[math({\rm MT}:P\to Q,\,\neg Q\vdash\neg P)]

Modus Tollens

4.3. 조건 도입[편집]

---

[math({\to}{\rm I}:P\Rightarrow Q\vdash P\to Q)]

Conditional Proof

[math({\rm CP})]라고도 한다. 주어진 전제로부터 어떤 명제를 도출할 수 있다면, 전제 [math(P)]를 전건(antecedent)으로, 도출된 명제 [math(Q)]를 후건(consequent)으로 갖는 조건문이 증명가능하다.

유사 사례: 어떤 문장이 앞서서 나타난다면, 그 문장을 후건으로 갖는 조건문을 쓸 수 있다. 이것은 1차 술어논리의 추론 규칙으로 활용된다.

4.4. 선언 제거[편집]

---

[math(\vee{\rm E}:P\vee Q,\,P\to R,\,Q\to R\vdash R)]

Disjunction elimination

양도논법이라고도 한다.

4.4.1. 선언적 삼단논법[편집]

---

[math({\rm DS}:P\vee Q,\,\neg P\vdash Q)][14]

[math(P\vee Q,\,P\vdash\neg Q)]는 논리적으로 맞지 않는 추론이다. 예를 들어, '모 위키러는 스 1 유저이거나 스 2 유저이다.'라는 문장에서, 그 위키러가 스 1 유저이면서 동시에 스 2 유저일 수 있으므로 '그 위키러는 스 1 유저이기 때문에 스 2 유저가 아니다'는 옳지 않은 추론이다. 하지만 '모 위키러는 중학생이거나 고등학생이다'라는 문장에서는, '중학생'과 '고등학생'이 상호 배타적이므로, 이때는 중학생을 긍정함으로써 그 위키러가 고등학생이 아니라는 것을 유도할 수 있다.

Disjunctive syllogism

선언지 제거라고도 한다.

4.4.2. 복합 양도 논법[편집]

---

[math({\rm CD}:P\to Q,\,R\to S,\,P\vee R\vdash Q\vee S)]

Constructive dilemma

dilemma라는 이름에서 눈치챘겠지만 위의 선언지 제거법과 마찬가지로, 복합양도논법은 딜레마로 연결될 수 있는 위험을 항상 안고 있다. 예를 들어 '거짓말을 하면 신이 널 싫어하고, 참말을 하면 사람들이 널 싫어하므로 뭘 하든지 넌 미움받게 된다'는 잘못된 복합양도논법으로, 딜레마이다. 이 딜레마는 '참말을 하면 신이 사랑하고, 거짓말을 하면 사람들이 좋아하므로 언제나 난 이득이다'라는 식으로 바꿀 수 있다. 마찬가지로 위의 결혼/독신 문제도, '독신녀로 산다면 부모님께서 기뻐하고 결혼하면 남친이 기뻐하니 둘 다 이득이다.'라는 식으로 바꿀 수 있다.

4.5. 선언 도입[편집]

---

[math(\vee{\rm I}:P\vdash P\vee Q:P\vdash Q\vee P)]

Disjunction introduction[15]

한 명제가 참이라면, 이 명제를 부분으로 갖는 선언문은 참임을 의미한다.

4.6. 연언 제거[편집]

---

[math(\wedge{\rm E}:P\wedge Q\vdash P:P\wedge Q\vdash Q)]

Conjunction elimination[16]

한 연언문이 참이라면, 그 연언문을 구성하는 부분 명제들은 모두 참이다.

4.7. 연언 도입[편집]

---

[math(\wedge{\rm I}:P,\,Q\vdash P\wedge Q)]

Conjunction introduction[17]

참인 명제들로 구성되는 연언문은 참이다.

4.8. 간접 귀류법[편집]

---

[math(\neg{\rm E}:\neg P\Rightarrow\bot\vdash P)]

직관주의자들은 이 규칙을 거부한다. 거칠게 설명해, 명제 [math(P)]의 부정에 대한 부정이 증명되더라도 명제 P가 증명가능한 것은 아니기 때문이다. 직관주의 논리에서 [math(\neg P)]의 증명이 존재하기 위한 필요충분조건은 [math(P\to\bot)]의 증명[18]이 존재하는 것이다. 따라서, [math(\neg\neg P)]가 증명가능하다는 것은 [math(\neg P\to\bot)]의 증명이 존재하는 경우이고, 이로부터 [math(P)]에 대한 증명이 있으리라는 보장이 없기 때문에, 직관주의 논리에서 간접적 귀류법은 논리적 법칙이 될 수 없다. 직관주의 논리에서 참 개념이 증명가능 개념으로 대체된다는 것을 안다면 위 설명이 이해가 될 것이다.

4.8.1. 이중 부정 제거[편집]

---

[math(\neg\neg P \vdash P)]

4.8.2. 간접 추리법[편집]

---

[math(P\to\neg P\vdash\neg P)]

유사 사례로 '클라비우스의 법칙'이 있다: [math((\neg P \to P) \vdash P)]

4.9. 직접 귀류법[편집]

---

[math(\neg{\rm I}:P\Rightarrow\bot\vdash\neg P)]

조건 도입규칙의 한 예로 볼 수 있다.

4.10. 폭발 원리[편집]

---

[math(\bot{\rm E}:\bot\vdash P)]

Principle of explosion, Ex Falso Quodlibet[20]

이것은 직관주의 논리학에서 받아들이는 원리로, 표준적인 자연연역 체계에서는 도출 규칙으로 다루지 않는다. 간단히 설명하면, 모순으로부터 모든 명제가 도출된다는 것이다. 직관주의 논리가 아닌 자연연역에서는 도출 규칙이 아닌 정리로, 다음과 같이 증명된다.

1. [math(P\wedge\neg P)] (전제)
2. [math(P\wedge\neg P\vdash P)] (연언 제거)
3. [math(P\vdash P\vee Q)] (선언 도입)
4. [math(P\wedge\neg P)](전제) [math(\vdash\neg P)] (연언 제거)
5. [math(P\vee Q,\,\neg P\vdash Q)] (선언적 삼단논법)
6. [math(\therefore P\wedge\neg P\vdash Q)]

쉽게 풀어서 설명해보면,

1. 서로 모순되는 두 명제를 만들고, 둘다 참이라고 가정한다.

1. 다음으로 방금 만든 명제를 이용해 선언명제를 하나 만든다.

1. 그러나 처음에 '삼각형의 내각의 합이 180도가 아니다'라는 명제 역시 참이라고 했으므로 이 선언명제의 전건은 거짓이다.
2. 방금 이 선언명제가 참이라는 것을 증명했으므로 전건이 거짓인데도 참이 되기 위해서는 후건(1=2이다) 역시 참이 되어야 한다.
3. (2)~(4)를 통해 명제 '1=2이다'는 참으로 증명되었다.

이는 중세 논리학에서 이미 발견되고 있는 증명으로, 중세 논리학 교과서에는 다음과 같은 증명이 실려 있다.


이처럼 모든 명제는 모순의 귀결이기 때문에, 표준적인 논리 체계 하에서 모순이 타당할 수 있다고 인정하게 되면 그 논리체계는 모든 문장이 참이 되는 공허한 체계가 된다. 대신 보조도출에서 모순을 참으로 가정하고 그로부터 결론을 이끌어내는 방식은 사용할 수 있다.

5. 추론 전략[편집]

---

모든 명제 논리의 증명을 기계적인 알고리즘을 통해 해결하는 방법은 존재하지 않는다. 그렇기 때문에 명제 논리의 증명에는 직관력이 필요할 수밖에 없다. 그러나 직관의 필요성을 인정한다고 할지라도, 효과적인 전략을 제시할 수 없는 것은 아니다. 이하의 전략은 많은 논리적 증명에서 유효하게 사용될 수 있다.

1. 선언문이 나오면 선언 제거를 활용하라.
2. 얻고자 하는 문장과 반대되는 가정을 한 다음 그로부터 가정의 부정을 도출하기 위해 귀류법을 활용하라.

이상의 두 전략은 아주 유용하며, 예시로는 다음과 같은 선언적 삼단논법(disjunctive syllogism)의 증명을 들 수 있다.

(1) P ∨ Q 전제
(2) ~P 전제
(3) ~Q 가정/~E
(4) P 가정/∨E
(5) P {4} 반복
(6) Q 가정/∨E
(7) ~P 가정/~E
(8) Q {6} 반복
(9) ~Q {3} 반복
(10) P {7}~{9} ~E
(11) P {1}, {4}~{5}, {6}~{9} ∨E
(12) ~P {2} 반복
(13) Q {3}~{12} ~E

또한 다음과 같은 전략이 제시될 수 있다.

3. 얻고자 하는 결론이 조건문 형태라면 조건 도입과 조건문화를 응용하라.
4. 얻고자 하는 결론이 쌍조건문 형태라면, 조건문 각각을 증명하고 쌍조건화 규칙을 적용하라.(ex: P iff Q를 증명하기 위해 P를 가정하고 Q가 따라나오는 것와 Q를 가정하면 P가 따라나온다는 것을 각각 증명하라.)

6. 논리적 동치[편집]

---

표준 명제 논리에서 문장 [math(\phi)]와 [math(\psi)]가 논리적 동치인 것의 필요충분조건은 다음과 같다:

• 의미론/모형이론적 규정: [math(\phi \leftrightarrow \psi)]이 타당함(i.e. 모든 모형에서 참임).
• 구문론/증명이론적 규정: [math(\phi \vdash \psi,\, \psi \vdash \phi)]

명제 논리에서 도출되는 대표적인 논리적 동치 사례들을 참조하기 위해선 해당 링크 참조

7. 관련 문서[편집]

---

• 논리 연산
• 양화 논리