03. 명제(Proposition)

 

3. 1. 명제(Proposition)

 

- 명제(Proposition) : 객관적인 기준으로 참과 거짓을 구분할 수 있는 문장.

 

- 진리 값(Truth Value): True, False 를 나타내는 값.

 

- 진리표(Truth Table): 각 명제의 진리 값에 따른 논리연산의 결과를 보여주는 표.

 

- 논리연산자(Logical Operation)

 

  1) 부정(NOT, ~ p or ¬p) : p가 아니다.

 

  2) 논리곱(AND, p ∧ q) : p와 q가 모두 T일 때,  p ∧ q 는 T.

 

  3) 논리합(OR, p ∨ q) : p와 q중 어느 하나가 T일 때, p ∨ q 는 T.

 

  4) 배타적 논리합(Exclusive OR, XOR, p ⊕ q) : p와 q중 어느 하나만 T일 때 참이 되고, 그렇지 않으면 F.

 

      p ⊕ q = (~p ∧ q) ∨ (p ∧ ~q).

 

 

- 합성명제(Compound Proposition): 하나 이상의 명제들이 논리연산자에 의해 결합된 명제.

 

- 항진명제(Tautology): 합성명제의 진리값이 항상 T인 명제.

 

- 모순명제(Contradiction): 합성명제의 진리값이 항상 F인 명제.

 

- 사건명제(Contingency): 항진명제도 모순명제도 아닌 합성명제.

 

 

- 조건명제 or 조건(Conditional Proposition, if p, then q) : p → q.

 

p	q	p → q
T	T	T
T	F	F
F	T	T
F	F	T

 

- 조건명제와 합성명제는 문장의 의미 자체는 생각 하지 않고, 오로지 T or F만 신경쓰면 된다.

 

 

- 쌍방조건명제(Biconditional Proposition) : p ↔ q.

 

   p ↔ q = (p → q) ∧ (q → p).

 

p	q	p ↔ q
T	T	T
T	F	F
F	T	F
F	F	T

 

- 논리연산자의 우선순위 : ( )  =>  ¬   =>  ∧  =>  ∨  =>  →  =>  ↔.

 

 

- 어떤 조건명제 p → q 에 대하여

 

  1) 역(Converse) : q → p.

 

  2) 이(Inverse) : ~ p → ~ q.

 

  3) 대우(Contraposition) : ~ q → ~ p.

 

---

 

3. 2. 논리적 동치(Logically Equivalence)

 

- 논리적 동치(Logically Equivalence, P ≡ Q): 두 개의 합성명제 P와 Q의 진리값이 서로 같은 경우.

 

- 논리적 동치는 진리표를 이용해 비교하거나, 논리적 동치법칙을 이용하여 식을 간단하게 바꾸는 방법이 있다.

 

---

 

3. 3. 변수를 포함한 명제(Proposition Containing Variables)

 

- 명제함수(Propositional Function, P(x)) : 변수 x를 포함하고 있는 명제.

 

- 논의 영역(Domain of Discourse, D): 명제 함수에 포함된 변수 x의 범위.

 

- 전체한정자(Universal Quantifier, ∀): 논의 영역의 모든 값.

 

- 존재한정자(Existential Quantifier, ∃): 논의 영역의 어떤 값.

 

- 한정자에 의해 범위가 제한되는 변수를 Binding Variable이라 하고 그렇지 않는 변수를 Free Variable.

 

- ∀xP(x)는 x가 정의된 범위의 모든 원소에 대해 P(x)가 참이어야 참이고, 하나라도 거짓이 있으면 거짓이 된다.   

 

 ∃xP(x)는 x가 정의된 범위의 모든 원소 중 하나라도 참이면 P(x)가 참이 되고, 반대로 모두 거짓이면 거짓이 된다.

 

 

- ∀x∀yP(x, y): 모든 x는 모든 y와 대응하여 P(x, y) 이다.

 

- ∀x∃yP(x, y): 모든 x는 적어도 하나의 y와 대응하여 P(x, y) 이다.

 

 

- ∀x(P(x) ∧ Q(x)) ≡ ∀xP(x) ∧ ∀xQ(x). [∃x 와 ∨ 일 때도 성립]

 

- ¬(∀xP(x)) ≡ ∃x(¬P(x)) / ¬(∃xP(x)) ≡ ∀x(¬P(x)).

 

---

 

3. 4. 추론(Inference)

 

- 추론(Inference): 참인 명제를 근거로 하여 다른 명제가 참임을 유도하는 방식.

 

- 전제(Hypothesis): 결론의 근거가 되는 명제, 진리값이 T인 명제.

 

- 결론(Conclusion): 주어진 전제에 의해 유도된 명제.

 

---