Category

discrete_mathematics

6 published posts

06. 알고리즘, 함수의 증가, 알고리즘의 복잡도

알고리즘을 이해하려면 무엇을 계산하는지뿐 아니라 왜 맞는지, 입력이 커질 때 얼마나 많은 일을 하는지도 봐야 한다. 검색과 정렬을 직접 따라가고, 반복 횟수를 함수로 표현하면 빅오 표기법이 무엇을 설명하는지 분명해진다. 특히 알고리즘 하나가 느리다는 사실과 문제 자체가 어렵다는 주장은 구별해야 한다.

05. 함수, 수열과 합, 행렬

수열은 정수 인덱스를 입력으로 받는 함수이고, 행렬은 수를 행과 열에 맞춰 배열한 구조다. 바닥·천장 함수로 정수 단위의 자원을 계산하고, 점화식으로 반복되는 변화를 표현하고, 행렬로 여러 관계와 방정식을 한꺼번에 다룰 수 있다. 정의를 실제 계산에 적용하면서 각 구조의 성질을 살펴보자.

04. 집합과 집합의 연산, 함수의 기초

집합은 어떤 대상이 포함되는지를, 함수는 한 대상이 다른 대상으로 어떻게 대응되는지를 표현한다. 원소와 부분집합, 공역과 치역처럼 비슷해 보이는 말을 구별해야 이후의 계산과 증명도 정확해진다. 집합 연산을 논리식으로 풀어 보고, 함수의 성질을 정의역과 공역까지 포함해 판단해 보자.

03. 추론 규칙과 증명 방법

수학적 증명은 그럴듯한 예를 많이 모으는 일이 아니라, 주어진 가정에서 결론이 반드시 따라온다는 것을 보이는 과정이다. 추론 규칙은 그 과정의 작은 단위이고, 직접증명·대우증명·귀류법은 여러 단계를 구성하는 방법이다. 어떤 조건을 가정했는지, 그 조건을 어디에서 사용했는지 드러내며 쓰는 것이 중요하다.

02. 술어 논리, 한정 기호, 논리회로

명제 논리만으로는 “모든 사람은 죽는다”와 “소크라테스는 사람이다” 사이의 관계를 표현하기 어렵다. 문장 전체에 참과 거짓을 붙이는 데서 더 나아가, 대상의 성질과 대상 사이의 관계를 나타내는 술어가 필요하다. 여기에 “모든”과 “적어도 하나”를 나타내는 한정 기호를 붙이면 수학적 주장과 시스템의 조건을 정확하게 쓸 수…

01. 명제 논리, 응용, 명제의 동치

명제 논리는 문장이 참인지 거짓인지, 그리고 여러 문장을 연결했을 때 어떤 결론이 나오는지를 다룬다. 조건문의 방향을 정확히 읽는 것에서 시작해 진리표, 동치 변형, 시스템 명세와 충족가능성까지 연결해 보자.