이산수학 2. 명제와 연산자 - swkim0128/PARA GitHub Wiki

type: 이산수학 archive: false

명제

이산수학 강의, 명제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: 명제의 논리적 표현

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

3은 6보다 작다

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

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)는 참이라 함)

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

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

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

  • 부정 예시

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

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

    컴퓨터학과 학생들 중 이산수학을 듣는사람이 존재한다
    p(x): x는 이상수학을 듣는다 x의 정의구역: 컴퓨터학과 학생들 (일부) ⇒ ∃x p(x)

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

중첩 한정사

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

모든 실수에 대해서 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))

⚠️ **GitHub.com Fallback** ⚠️