논리

명제 논리란?

명제 논리란 "문장 구조"를 모델링하는데 사용되며, "문장 논리"라고도 부른다.
정의 : 명제(proposition)는 참 또는 거짓 중의 하나의 값 많을 갖는 문장이다.

명제를 기호로 나타낸다.
• it is raining. (p)
• it is cold. (q)

연산자를 사용하여 복잡한 문장 구조를 나타낸다.
• it is not raining (¬p)
• it is raining and it is cold. (p⋀q)
• it is raining or it is cold. (p⋁q)
• if it is raining, the it is cold. (p➝q)
• it is raining, if and only if it is cold. (p↔︎q)

사용된 연산자 : ¬, ⋀, ⋁, ➝, ↔︎

연산자 의미

부정(negation)

• ¬p
• not p

논리곱(conjunction, 연접)

• p⋀q
• p and q

논리합(disjunction, 이접)

• p⋁q
• p or q

조건(conditional, 함축)

• p➝q
• if p, then q
• p는 전건(antecedent), 가정(hypothesis)
• q는 후건(consequent), 결론(conclusion)

쌍 조건(bi-conditional)

• p↔︎q
• p if and only if q

타당한 논리식

논리식 분류

타당(valid, tautology) : 모든 경우에 참
만족불능*(unsatisfiable, contradiction) : 모든 경우에 거짓
만족가능(satisfiable, contingency) : 참인 경우가 존재

논리적 동치 관계

𝜜와 𝜝의 값이 모든 경우에 동일하다면, 둘은 논리적 동치 관계이다.
𝜜 ≡ 𝜝 iff 𝜜➝𝜝 ∧ 𝜝➝𝜜

대표적인 논리적 동치

• 드모르강
¬(𝑝∨𝑞) ≡ ¬𝑝∧¬𝑞
¬(𝑝∧𝑞) ≡ ¬𝑝∨¬𝑞

• 대우(contrapositive)
𝑝 ➝ 𝑞 ≡ ¬𝑞 ➝ ¬𝑝

• 이중 부정
¬¬𝑝 ≡ 𝑝

타당한 논리식의 표현

모든 해석에서 참인 논리식을 타당한 논리식이라고 한다.
⊨𝐴는 논리식𝐴가 타당하다는 표시이다.

• ⊨ 𝑝∨¬𝑝
• ⊨((𝑝 ➝ 𝑞) ∧ ¬𝑞) ➝ ¬𝑝

타당한 논증

타당한 논증 : 전제가 모두 참이면, 결론도 반드시 참이어야 한다.
타당한 논증과 타당한 조건문은 같은 개념이다.

• 𝐴1, ⋯, 𝐴𝑛 ⊨ 𝐵 iff ⊨ 𝐴1 ∧ ⋯ ∧ 𝐴𝑛 → 𝐵

진리표를 이용한 타당한 논증의 판정

방법 1
• 전제가 모두 참인 행에 대해서, 결론도 참인지 확인한다.

방법 2
• 모든 전제를 논리곱으로 연결한다.
• 논리곱으로 연결된 전제와 결론을 조건으로 연결한다.
• 전체 논리식이 타당함을 보인다.

타당한 논증 유형

•긍정 논법(modus ponens)
A → B, A |= A

•부정 논법(modus tollens)
A → B, ¬B |= ¬A

•선언적 삼단 논법(disjunctive syllogisms)
A ∨ B, ¬A |= B (또는 A ∨ B, ¬B |= A)

•삼단 논법(hypothetical syllogism)
A → B, B → C |= A → C

•딜레마(dilemma)
A ∨ B, A → C, B → C |= C

•접속사 제거(conjunctive simplifications)
A ∧ B |= A (또는 A ∧ B |= B)

•분리 소개(disjunctive additions)
A |= A ∨ B (또는 B |= A ∨ B)

•접속사 추가(conjunctive addition)
A, B |= A ∧ B