이산수학 #1강: 명제

신흥철 교수님의 이산수학 1강을 듣고 정리하였습니다.

이산수학

• 불연속을 다루는 수학이다.

• 1과 0을 다루는 수학이다.

  • 1: 전원이 켜졌을 때, 참
  • 0: 전원이 꺼졌을 때, 거짓

명제

명제의 정의

명제 (Proposition)

참이나 거짓으로 구분할 수 있는 문장이나 수식(영어 소문자 p, q, r 등으로 표현)

• ex) 컴퓨터 가격은 비싸다. => 명제가 아니다.
  • 가치판단 개입
• ex) x + 1 = 2 => 명제가 아니다.
  • x가 어떤 값이냐에 따라서 참이 될 수도 있고, 거짓이 될 수도 있기 때문이다.

진릿값(Truth Value)

참(True, 1)이나 거짓(False, 0)을 가리키는 값

• ex) 2^n = n^2 을 만족하는 정수 n이 하나 이상 존재한다.
  • 명제이고 진리값은 참이다. n이 2일 경우가 있기 때문이다.

논리연산자(명제의 결합)

부정(Negation: NOT, ¬p 또는 ~p)

명제 p에 대하여 p가 아니다도 명제

논리곱(Conjunction: AND, p^q)

명제 p, q의 진리값이 모두 참일 때 참이 되고, 그렇지 않을 때는 거짓이 되는 명제

논리합(Disjunction: OR, p∨q)

명제 p, q의 진릿값이 모두 거짓일 때 거짓이 되고, 그렇지 않을 때는 참이 되는 명제

배타적 논리합(Exclusive OR: XOR, p⊕q)

명제 p, q의 진릿값 중 하나만 참일 때 참이 되고, 그렇지 않을때는 거짓이 되는 명제

합성명제

합성명제(Compound Proposition)

• 하나 이상의 명제들이 결합되어 만들어진 명제
• 논리 연산자(Logical Operators; AND, OR, NOT 등)를 이용해 명제를 결합

항진명제(Tautology) T

• 구성명제 진릿값에 상관없이 항상 참인 합성명제
• p ∨ ¬p

모순명제(Contradiction) F

• 구성명제 진릿값에 상관없이 항상 거짓인 합성명제
• p ^ ¬p

사건명제(Contingency)

• 항진명제도 모순명제도 아닌 합성명제

1

• 지배법칙: 거짓이 AND를 지배하고, 참 값이 OR를 지배한다.

• 항등명제: 어떤 값에 연산해도 같은 값이 나오는 명제 (예: x + 0 = x)

합성명제 ¬(p∧q)⊕(¬p∨q)에 대한 진리표

함축(조건명제)

함축(Implecation, 조건명제) p → q

• 명제 p, q에 대해 p가 조건/원인으로 제시되고, q가 결론/결과로 제시되는 명제
• 조건이 참이고 결론이 거짓일 때만 전체 함축(조건)명제는 거짓이 된다.

• p → q 에서 p가 참일 때 반드시 q가 참인 경우
  • p ⇒ q
  • p는 q의 충분조건, q는 p의 필요조건
• 예시) p: 비가 온다. q: 우산을 가지고 간다.
  • 비가 오면 우산을 가지고 간다. (참)
  • 비가 오는데 우산을 가지고 가지 않는다. (거짓)
  • 비가 오지 않아도 우산을 가지고 간다. (참)
  • 비가 오지 않으면 우산을 가지고 가지 않는다. (참)

쌍방조건명제(Biconditional) p ↔ q

• 명제 p와 q가 조건이면서 결론인 명제

• 조건과 결론의 진릿값이 같을 때만 참이 된다.

• p ↔ q 에서 p가 참일 때 q가 참인 동시에, q가 참일 때 p가 참인 경우
  • p ⇔ q
  • p, q는 서로 필요충분조건

역, 이, 대우

• 역(Converse): q → p: 조건이 결론이 되고 결론이 조건이 된다.

• 이(Inverse): ¬p → ¬q: 조건과 결론을 모두 부정한다.

• 대우(Contraposition): ¬q → ¬p: 조건과 결론을 바꾸면서 모두 부정한다. (역 + 이)