본문 바로가기

수학/🫥 이산수학5

수학적 귀납법(Mathematical Induction) 톺아보기 여태까지 기초적인 증명을 다뤘지만, 이 증명 외에도 자주 쓰이는 증명이 있다. 수학적 귀납법이라고 불리는 이 증명 방식은, 고등학교에서도 다룰 만큼 유명한 증명방식이지만, 생각지도 못한 곳에서 자주 튀어나오는, 꼭 익혀둬야 할 증명방식이다. 수학적 귀납법이란? 수학적 귀납법은 다른 증명들과 마찬가지로, 명제가 사실임을 보이는 과정이다. 그 중에서도 특히, 자연수에서만 성립한다. 수학적 귀납법은 도미노와 비슷하다. 수학적 귀납법은 크게 2가지 과정으로 나뉘어 진다. 다음과 같은 명제가 있다고 하자. ∀n ∈ N P (n) : 자연수인 모든 n에 대하여, P(n)이 성립한다. 1. 이 명제가 가장 작은 조건(일반적으로 1)에서 성립함을 보인다. (즉, P(1)) 2. 이 명제가 어떤 n에서 성립한다면, n+.. 2021. 6. 14.
수학에서 말하는 증명(Proof)이란 뭘까? 수학의 꽃은 증명이라고 한다. 이산수학에서도 증명은 상당히 중요한 파트 중 하나이다. 오늘은 증명의 정의와 증명이 어떻게 이루어지는지 알아보자! 증명이 도대체 뭐길래? 증명이란 쉽게 말해서 수학적으로 명제가 확실함을 밝히는 과정이다. 조금 더 정확하고 있어보이게 말하자면, 주어진 공리나 이미 증명된 정리로부터 특정 명제나 논리적으로 타당함을 이끌어 내는 과정이라고 볼 수 있다. 여기서 몇 가지 용어를 정리해야 한다. 1. 공리란, 증명할 필요없이 사실로 받아드리는 명제를 말한다. 2. 정리란, 공리로부터 증명된 공리가 아닌 명제를 말한다. 즉, 증명이란 공리가 사실이라면 이 명제는 논리적으로 반드시 사실임을 보이는 과정이다. 증명의 종류 수학에서 가장 많이 쓰이는 증명은 크게 4가지가 있다. 직접증명(D.. 2021. 6. 11.
논리학 - 술어논리 (1차논리) 우리는 명제논리에서, 논리학은 참과 거짓을 구분할 수 있는 명제를 다룬다는 것과, 그 명제들을 논리 연산자를 사용해 더 복잡한 명제로 만든다는 것을 배웠다. 그 과정에서 잠깐 "x는 사람이다" 같은 x의 값에 따라서 사실이 될 수도, 거짓이 될 수도 있는 문장을 다뤘는데, 오늘은 이런 빈사(사실일 수도 거짓일 수도 있는 문장)을 어떻게 명제로 할 수 있는지 알아보고자 한다. 술어 논리는 왜 중요할까? 술어 논리가 중요한 이유는 우리가 흔히 사용하는 문장의 형태는 미지수(모르는 것)을 포함하고 있기 때문이다. 이러한 명제를 논리학적으로 다루기 위해서는 술어 논리를 배워야 한다. 보편 양화사와 존재 양화사 술어 논리는 미지수가 포함된 문장의 범위를 한정시켜서 명제(참과 거짓이 구분 가능)로 만드는 것이다. .. 2021. 6. 10.
논리학 - 명제논리 (0차논리) 과학은 수학의 언어로 써져 있다고 한다. 이 말은 과학을 하는 과정에서 각종 수학적 기법을 사용하고, 과학적 관계를 묘사할 때도 수학의 언어와 수식을 사용하기 때문이다. 그렇다면 수학의 언어는 뭘까? 수학의 언어는 논리학이다. 오늘은 논리학에 대해서 알아보자. 논리학의 기초 논리학은 뭐가 맞고 뭐가 틀린지를 엄밀하게 판단하기 위해 발전한 학문이다. 즉, 논리학의 대상은 참과 거짓이 확실해야 한다. 명제(Statement)는 참이거나 거짓, 둘 중 하나인 문장이다. "1 + 1 = 2" 는 명제일까? 명제이다. 특히, 참인(사실인) 명제이다. "1 + 1 = 3" 은 명제일까? 놀랍게도 이것 또한 명제이다. 특히, 거짓인 명제이다. "1 + 1 은 쉽다" 는 명제일까? 아니다! 의견은 참과 거짓이 없기 때.. 2021. 3. 26.
프로그래머가 되기 위해 알아야 한다고 하는 이산수학이란 무엇일까? 초등학교 때 부터 시작해 고등학교 3학년까지 우리는 10년 넘게 수학을 붙들고 있지만, 이산수학이라는 용어도 그렇고, 이산수학 내용이 우리에게는 많이 낯설 수 밖에 없습니다. 그도 그럴게, 학교에서 배우는 수학은 보통 연속수학(Continous Mathematics)이라고 불리우는, 연속된 대상을 다루는 경우가 많기 때문입니다. 연속된 대상이라는게 뭘까요? 1과 2를 상상해 보세요. 1과 2 사이에는 1.1, 1.2, 1.3 등 소수가 무한히 많습니다. 즉, 연속적입니다. 셀 수가 없습니다. 이와는 반대로 이산수학은 자연수(1, 2, 3 ...), 정수(마이너스, 0, 자연수를 합친 것) 같이 딱딱 나눌 수 있는 대상을 다룹니다. 정수나 자연수 뿐만 아니라 경우의 수나, 논리학 같은 대상이 이런 이산수학.. 2021. 3. 26.

티스토리툴바