이산수학 명제, 한정사

명제

이산수학 강의, 명제1-1

• 참 혹은 거짓을 판명할 수있는 선언적인 문장
• 종류
  • 사실명제: 관찰, 측정, 실험으로 판단되는 명제
    • ex)서울은 대한민국의 수도이다
  • 논리명제: 수학, 형식의 명제(컴퓨터에서 다루는 명제)
  • 복합명제: 단순명제의 조합으로 만들어지는 명제
    1. 부정, Not(￢ )
       • 명제의 진리값을 뒤집어줌
       • p⇒ 참
       • ￢p ⇒ 거짓
    2. 논리곱, And( ^ )
       • 그리고
       • p ^ q 일때 p,q모두 참일 경우에만 p ^ q⇒ 참 이다 나머지는 거짓
    3. 논리합, Or( v )
       • 또는
       • p v q 일때 p,q모두 거짓일 경우에만 p v q⇒ 거짓 이다 나머지는 참
    4. 배타적논리합, Exclusive or( ⊕ )
       • p, q가 다르면 참
       • p, q가 같으면 거짓
    5. 함축, 조건명제, Implication (→)
       • p → q : p일때 q이다
       • 조건 → 결과 (ex) 비가 올때 우산을 쓴다)
       • 참 → 거짓 ⇒ 거짓 나머지 경우는 참
    6. 쌍방 조건명제, Biconditional (↔)
       • p, q가 같으면 참
       • p, q가 다르면 거짓
       • ⊕와 반대
       • 잘 안쓰임
• 동치: 두 명제의 갑이 같으면 두 명제는 동일한 명제이다

---

명제의 표현

이산수학 명제1-2: 명제의 논리적 표현

• 명제는 주어와 술어로 구성되어있다

  ex) 3은 6보다 작다

• 명제는 변수를 포함한 함수로서 표현할 수 있다

  ex) x에 2를 더하면 3이다.
  p(x) : x+2=3

한정사

• 명제 함수 p(x)의 정의역은 한정사를 사용하여 표현할 수 있다.

• 종류

  • 전체한정(universal quantification) (all)

    • x가 갖는 모든 값에 대해서 p(x)가 참인 명제를 p(x)의 전체 한정이라고 한다
    • 기호: ∀x p(x)
      (하나라도 거짓이 되는 경우가 있으면 ∀x p(x)는 거짓이라함)

  • 존재한정(existention quantification) (some)
    - x가 갖는 값 중에서 p(x)가 참이 되게 하는 x가 존재하는 명제를 p(x)의 존재 한정이라고한다.
    - 기호: ∃x p(x)
    (하나라도 참이 되는 경우가 있으면 ∃x p(x)는 참이라 함)

    ex) 모든 사람 x에 대하여, 만일 x가 이 클래스의 학생이면 x는 C언어 인증 시험을 통과 하였다

    함수 S(x): "x가 이 클래스의 학생이다"
    함수 C(x): "학생 x는 C언어 인증 시험을 통과하였다"
    x의 정의구역: 이 클래스의 학생들
    함수 Q(x,y): "사람 x가 y를 통과하였다"

    ⇒ ∀x (S(x) → Q(x, C언어 인증시험))

• 부정 예시

  ex)모든 컴퓨터학과 학생들은 이산수학을 듣는다

  p(x): x는 이산수학을 듣는다
  x의 정의구역: 모든 컴퓨터학과 학생들
  ⇒ ∀x p(x)

  • (부분)부정:
    컴퓨터학과 학생이면서 이산수학을 듣지않는 학생도 있다
    ⇒ ~(∀x p(x)) = ∃x p(x)

    ex) 컴퓨터학과 학생들 중 이산수학을 듣는사람이 존재한다

    p(x): x는 이상수학을 듣는다
    x의 정의구역: 컴퓨터학과 학생들 (일부)
    ⇒ ∃x p(x)

  • (완전)부정:
    모든 컴퓨터학과 학생은 이산수학을 듣지 않는다
    ⇒ ~(∃x p(x)) = ∀x ~p(x)

중첩 한정사

• 한 명제에서 두개 이상의 한정사를 사용하는 경우

  ex)
  모든 실수에 대해서 x+y=y+x가 성립한다
  ⇒ ∀x ∀y (x+y=y+x)

  모든 실수 x,y에 대해서 x가 양수이고 y가 음수이면 x와 y의 곱은 음수이다
  ⇒ ∀x ∀y (((x>0)^(y<0))→ (x*y<0))