[CS 1-2 | 이산수학] 증명 5주차

2022. 9. 22. 02:23·CS 대학강의
반응형

증명관련 용어 정리

  • 가설
    • 어떤 부분적 증거나 휴리스틱한 논증, 또는 전문가의 직관에 근거하여 참이라고 주장되는 문장

  • 증명
    • 어떤 정리가 참이라는 것을 입증하는 유효한 논증

      # 증명 과정에서 사용할 수 있는 것
      • 참이라고 가정한 공리
      • 증명하려는 정리의 전제들
      • 이미 증명된 정리들

  • 정리
    • 그것이 참임을 보일 수 있는 하나의 진술
이전에 증명된 사실로, 증명 과정에서 새로운 진술의 진리값을 추론할 때 사용한다.

 

  • 주장
    • 상대적으로 덜 중요한 정리

  • 보조정리
    • 증명하는데 도움이 되는 약간 덜 중요한 정리

  • 따름정리
    • 증명된 정리로 부터 직접적으로 귀결될 수 있는 정리

 

"가설이 증명되면, 그 가설을 정리라 한다."


정리 증명 방법

  • 수학적 정리들의 경우 전칭 기호를 생략하고 표현하는 경우가 많다.

  • 정리는 다음과 같이 단계를 거쳐 증명한다.
    • 대상 영역의 일반적 원소를 선택
    • 이 원소가 문제의 성질을 갖는지 확인한다.
    • 전칭 일반화를 적용하여 모든 원소에 대해 성립함을 보여준다.
      "정의역에 포함한 모든 a에 대해 P(a)는 참이면, ∀xP(x)는 참이다."

증명 - 직접 증명

  • 정리의 전제로부터 결론에 도달하는 방식
    • 전제들로부터 시작하여 일련의 연역 과정을 거쳐 최종적으로 결론에 이른다.
      연역 과정이란, 가설을 설정하고 법칙을 도출하는 과정에서 귀납적인 과정
  • 예를 들어 조건문 p -> q에 대해 직접 증명한다면
    • 만약 p가 참이라면 q가 참일 수 밖에 없음을 보인다.

      p가 참이면서 동시에 q가 거짓인 경우는 절대 없다. (조건문의 진리표)
      p -> q는 참인 경우만 존재한다.
  • p가 참이라고 가정하고 추론 규칙들을 적용해 q가 참임을 보인다.

  • 증명 과정에서 p가 참이라고 가정하는 공리와 정의들, 그 전에 증명된 증명들, 추론 규칙 등이 사용된다.

직접 증명은 주어진 전제로부터 일정한 증명 과정을 거쳐 최종적으로 결론에 이르는 증명이다.

 

 

# 직접 증명 예제

 


증명 - 대우에 의한 증명

  • 전제로부터 결론을 직접 도출하지 않은 형태의 증명을 간접 증명이라 한다.
    • 대우에 의한 증명은 간접 증명 기법 중 하나이다.

  • 대우에 의한 증명은 문장 p -> q가 문장 ¬q -> ¬p와 동치라는 사실을 이용한다.
    • p -> q 대신 ¬q -> ¬p가 참임을 보인다.
    • 가정은 p대신 ¬q를 취한다.
    • 공리, 정의, 이전에 증명된 정리, 추론 규칙 등을 사용하여 ¬p가 참임을 보인다.
문장 p -> q에 대해 참임을 증명할 때, p에 대한 진리값은 없고, ¬q에 대한 참인 진리값이 존재할 때,
대우에 대한 증명을 사용해 p -> q가 참임을 증명한다. (논리적 동치 성질을 활용한 증명법)

 

# 대우에 의한 증명 예제

 

 

 


공허한 증명

  • 조건문 p -> q에 대해 증명할 때
    • p가 거짓이라면 해당 조건문이 참임을 쉽게 알 수 있다.

    • 즉, p가 거짓임을 보일 수 있다면, 조건문 p -> q가 참임을 즉시 증명할 수 있다.

    • 이것을 공허한 증명이라고 한다.
주어진 전제로부터 별다른 추론 과정없이, 증명의 결과가 즉시 나오는 증명을 공허한 증명이라고 한다.

 

자명한 증명

  • 조건문 p -> q에 대해 증명할 때
    • q가 참이라면 해당 조건문이 참임을 쉽게 알 수 있다.

    • 즉, q가 참임을 보일 수 있다면, 조건문 p -> q가 참임을 증명할 수 있다.

    • 이것을 자명한 증명이라고 한다.

모순에 의한 증명 - 간접 증명

  • p가 참이라는 것을 증명하고 싶다면
    • ¬p -> q를 참으로 만드는 모순 q를 구했다고 가정한다.
    • "q가 모순이다"는 "q는 항상 거짓이다."라는 의미한다.
    • q는 거짓이고 ¬p -> q는 참이라면 ¬p는 거짓이 되므로, p는 참이 된다.
    • 여기서 핵심은 "모순인 q를 어떻게 구할 것인가"이다.

 


동치 증명

  • 상호 조건문 p <-> q의 형태를 갖고 있는 정리를 증명하려면
    p -> q와 q -> p가 모두 참이라는 것을 각각 증명해야 된다.

반례 증명

  • 어떤 명제가 참 또는 거짓임을 입증하기 어려운 경우에 효과적인 증명 방법이다.

  • 주어진 명제에서 모순이 되는 간단한 하나의 예를 보임으로써 비교적 쉽게 증명할 수 있다.

 

주어진 전제로부터 결론을 증명하기 어려운 경우,
반례 증명을 통해 하나의 사례를 찾아서 증명을 할 수가 있다.
대체로 전칭한정 기호가 사용된 문장에서 반례 증명을 쓴다.

잘못된 증명

  • 주어진 전제로부터 증명을 수행할 때, 수학적 규칙을 고려하지 않고 전개한 증명은 잘못된 증명이다.
    a - b = 0 이 참이라고 주어졌을 때 a - b로 나누는 전략은 잘못된 증명이다.

  • 논점 회피 오류
    • 증명의 과정에서 증명하려는 진술이 참이라는 것에 근거한다.

    • 어떤 진술이 그 자체를 사용하거나, 그 자체와 동치임을 보임으로써 증명하고자 할 때 발생한다.

    • 순환 추론이라고도 한다.

정리해서, 잘못된 증명은
수학적 규칙을 고려하지 않고 전개된 전략이거나,
추론된 진술을 토대로 별다른 증명없이 동치라고 생각할 때 잘못된 증명이 발생한다.
반응형

'CS 대학강의' 카테고리의 다른 글

프로그램 설계 방법론 - #04 [클래스 상속]  (0) 2022.09.22
[CS 1-2 | 오픈소스 SW 기초] 리눅스 CLI 명령어 실습 2주차  (0) 2022.09.22
[CS 1-2 | 이산수학] 추론 4주차  (0) 2022.09.22
[CS 1-2 | 이산수학] 중첩 한정기호 3주차  (0) 2022.09.22
[CS 1-2 | 대학생을 위한 실용금융] 환율과 주식 3주차  (0) 2022.09.21
'CS 대학강의' 카테고리의 다른 글
  • 프로그램 설계 방법론 - #04 [클래스 상속]
  • [CS 1-2 | 오픈소스 SW 기초] 리눅스 CLI 명령어 실습 2주차
  • [CS 1-2 | 이산수학] 추론 4주차
  • [CS 1-2 | 이산수학] 중첩 한정기호 3주차
욱22
욱22
우기의 모든 걸 기록합니다.
    반응형
  • 욱22
    우기 때 만나요
    욱22
  • 전체
    오늘
    어제
    • 우기 때 만나요 (265) N
      • 💭 경험&생각 (49) N
      • 🌤 일상&취미 (12)
      • 📖 북로그 (29)
      • 백엔드 개발 (27)
      • 📚 스터디 (33)
        • 비즈니스 (0)
        • 프론트엔드 (9)
        • 디자인 (4)
        • 데이터베이스 (8)
        • 데이터 분석 (0)
        • 인공지능 (2)
        • 알고리즘 (10)
      • CS 대학강의 (78)
      • 🌤 프로젝트 (0)
        • UMC 2기: 동네 (15)
        • UMC 3기: 당신의 발자취 (6)
        • ERICA: 스타트업톤 (9)
        • ERICA: 또래튜터링 (2)
      • 🌤 대외활동 (5)
  • 링크

    • Github
  • 인기 글

  • 최근 글

  • 태그

    객체지향 프로그래밍
    파이썬
    티스토리챌린지
    디자인베이스
    자기계발
    안드로이드
    Kotlin
    대학생 대외활동
    오블완
    스타트업
    드럼 레슨
    드럼
    백준
    java
    자료구조
    생각정리
    AWS
    창업
    대학생 개발 프로젝트
    디자인
  • 최근 댓글

  • hELLO· Designed By정상우.v4.10.1
욱22
[CS 1-2 | 이산수학] 증명 5주차
상단으로

티스토리툴바