이산수학 기초

Ja_an·2021년 7월 12일
1

이산수학

목록 보기
1/13

이산수학개요

이산수학 강좌 1강 - 이산수학 개요 (Discrete Mathematics Tutorial For Beginners #1)

  • 이산수학 (Discrete Mathematics)
    • 불연속적 수학
    • 참과 거짓으로 살펴보는 컴퓨터 수학
    • 보편적인 컴퓨터 수학
  • 왜 필요한가
    • 이산수학이란 불연속적인 숫자를 다루는 수학이기 때문에
      컴퓨터를 구성하는 0과 1의 불연속적인 데이터흐름을 다루기에 적합한 수학적 사고를 기를 수 있음
    • 이산수학에서 다루는 수학적 귀납법 등의 기초개념이 알고리즘에 반복적으로 출현

명제와 연산자

이산수학 강좌 2강 - 명제와 연산자 (Discrete Mathematics Tutorial For Beginners #2)

  • 명제
    • 참 혹은 거짓으로 진리를 명확하게 구분할 수 있는 문장
    • ex)
      • 아이유는 이쁘다 → 명제X
      • 1은 짝수이다 → 명제O (거짓)
      • 고양이는 동물이다 → 명제O(참)
  • 연산자
    • 명제를 연산하기 위한 도구
    • 기본 연산자의 종류
      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가 다르면 거짓
        • ⊕와 반대
        • 잘 안쓰임

진리표와 역, 이, 대우

이산수학 강좌 3강 - 역, 이, 대우 (Discrete Mathematics Tutorial For Beginners #3)

  • 진리표

    • 각 명제 사이의 관계식의 진리값을 보여주는 표
    • ex)
  • 역, 이, 대우

    • 조건명제에서 사용함
    • 하나의 명제를 변형해 표현함
    • 본 명제
      p → q

    • q → p

    • ¬p → ¬q
    • 대우
      ¬q → ¬p
      대우가 참이면 본 명제도 참 ( 대우와 본 명제는 반드시 같은 명제를 가짐)
    • 왜 쓰는가
      • 증명을 돕기 위함
      • 증명하기 어려운 본 명제를 대우를 이용해 증명 가능
    • ex)
      • 명제 "30이 10보다 크다면, 30은 50보다 작다"
      • p: 30>10
      • q: 30<50
      • p → q : 30이 10보다 크다면, 30은 50보다 작다 ⇒ 참 → 참 ⇒
      • 역:
        q → p : 30이 50보다 작다면, 30은 10보다 크다 ⇒
      • 이:
        ¬p → ¬q : 30이 10보다 작거나 같다면, 30은 50보다 크거나 같다 ⇒
      • 대우:
        ¬q → ¬p : 30이 50보다 크거나 같으면, 30은 10보다 작거나 같다 ⇒
      • 역, 이는 본 명제와 다른 명제가 나올 수 있지만 대우는 반드시 같은 명제를 가짐

동치

이산수학 강좌 4강 - 동치 (Discrete Mathematics Tutorial For Beginners #4)

  • 동치
    • 논리적으로 일치한다
    • 같은 의미를 가진 더 쉬운 명제를 발견하는데 사용
      • ex) 2+2+2+2+2+2+2+2+2+2 와 2*10 은 동치이다
    • 동치법칙

      + 함축 법칙: p → q === ~p v q
      ex)
      • (p→q)^(p→~q)를 동치법칙을 이용한 간소화하라
        (p→q)^(p→~q)
        ⇒ (~p v q)^(~p v ~q) : 함축법칙
        ⇒ ~p v (q ^ ~q) : 분배법칙
        ⇒ ~p v F : 부정법칙
        ⇒ ~p : 항등법칙
profile
주말은 쉬어요

0개의 댓글