전단사 함수는 단사성과 전사성을 동시에 만족하는 함수이다. 정의역과 공역의 원소가 하나씩 정확히 대응한다. 단사는 서로 다른 입력이 같은 출력으로 합쳐지지 않는 성질이고, 전사는 공역의 모든 원소가 어떤 입력의 출력이 되는 성질이다. 유한한 학생 목록과 좌석 목록 사이에 학생마다 다른 좌석을 배정하고 빈 좌석도 없다면 전단사 대응이다. 단사·전사는 함수식만이 아니라 정의역과 공역에 의존한다. 전단사 함수에는 역함수가 있지만 정
동치 관계는 반사성·대칭성·추이성을 모두 만족하는 이항 관계이다. 같은 것으로 취급할 대상을 묶는 수학적 기준을 제공한다. 동치인 원소들을 모은 동치류는 전체 집합을 서로 겹치지 않는 부분들로 나눈다. 대표 원소를 골라 같은 부류를 표현할 수 있다. 정수를 3으로 나눈 나머지가 같다는 관계는 동치 관계이다. 정수들은 나머지가 0, 1, 2인 세 부류로 나뉜다. 비슷하다는 일상적인 기준이 항상 동치 관계인 것은 아니다. 두 값의
데카르트 곱 A×B는 A의 원소와 B의 원소를 순서쌍으로 결합한 집합이다. 순서쌍 (a,b)에서 첫 성분과 둘째 성분의 역할을 구별한다. 유한 집합이면 결과의 크기는 |A|×|B|이다. 색상 3개와 크기 4개를 결합하면 12개의 상품 선택 조합을 표현할 수 있다. 이는 선택 가능한 모든 조합이 유효하다는 모형이다. A×B와 B×A는 일반적으로 같은 집합이 아니다. 일부 조합만 허용하려면 데카르트 곱의 부분집합으로 관계를 정의한
멱집합은 주어진 집합의 모든 부분집합을 원소로 갖는 집합이다. 원소가 n개인 유한 집합의 멱집합 크기는 2ⁿ이다. 각 원소를 포함하거나 제외하는 두 선택으로 부분집합을 구분할 수 있다. {a,b}의 멱집합은 빈 집합, {a}, {b}, {a,b}를 원소로 갖는다. 기능의 활성화 조합을 열거하는 모형으로 활용할 수 있다. 멱집합에는 원래 집합과 빈 집합도 포함된다. n이 커지면 모든 조합을 실제 메모리에 생성하는 비용이 급격히
집합은 구별 가능한 원소들의 모임이다. 원소의 나열 순서와 같은 원소의 반복은 집합을 바꾸지 않는다. 원소 관계, 부분집합 관계, 합집합·교집합·차집합 등의 연산으로 대상을 다룬다. 수학적 집합과 특정 언어의 set 구현은 구별한다. {1,2,2}와 {2,1}은 수학적으로 같은 집합이다. 사용자 권한을 원소로 두면 두 역할의 공통 권한을 교집합으로 표현할 수 있다. 원소로 속한다는 것과 부분집합이라는 것은 다른 관계다. 빈 집
귀류법은 주장하려는 명제의 부정을 가정한 뒤 모순을 도출하여 원래 명제를 증명하는 방법이다. 가정과 이미 알려진 사실을 연결해 동시에 참일 수 없는 결론을 얻는다. 무엇과 무엇이 모순되는지 마지막에 분명히 제시한다. 소수가 유한 개라고 가정하고 그 소수들을 모두 곱한 값에 1을 더하면, 목록의 소수들로 나누어떨어지지 않는 수를 얻는 논증이 대표적이다. 원래 명제가 성립하지 않는다고 가정하는 것과 원하는 결론을 몰래 전제하는 것
수학적 귀납법은 시작 경우가 성립하고 한 단계의 성립이 다음 단계로 이어짐을 보여 명제의 전체 성립을 증명하는 방법이다. 기초 단계와 귀납 단계를 모두 증명한다. 귀납 가정은 증명하려는 전체 결론을 미리 참이라고 가정하는 것이 아니라 특정 단계의 조건이다. 1부터 n까지의 합 공식을 증명할 때 n=1을 확인하고, n=k에서 성립한다고 두어 k+1을 더한 식이 다음 공식과 같음을 보인다. 몇 개의 수치가 맞는다는 관찰만으로 귀납
진리표는 입력 명제의 가능한 진릿값 조합과 논리식의 결과를 표로 나열한 것이다. 명제 변수가 n개이면 가능한 조합은 2ⁿ개이다. 모든 경우의 결과를 비교해 논리식의 동치나 항진성을 검사할 수 있다. p와 q의 논리곱은 둘 다 참일 때만 참이고 논리합은 적어도 하나가 참이면 참이다. 네 가지 조합을 표로 확인할 수 있다. 변수가 늘면 표가 지수적으로 커진다. 간단한 조건식 검증에는 유용하지만 큰 논리 문제에서는 다른 증명이나 자
술어 논리는 대상에 관한 성질과 관계를 변수 및 한정자로 표현하는 논리 체계이다. P(x) 같은 술어와 모든 대상을 뜻하는 전칭, 어떤 대상이 존재함을 뜻하는 존재 한정자를 사용한다. 변수의 논의 영역을 정해야 의미가 명확해진다. 모든 사용자는 식별자를 가진다는 문장과 어떤 사용자는 관리자라는 문장은 서로 다른 한정자를 사용한다. 모든 x에 대해 어떤 y가 존재한다는 것과 모든 x에 공통인 y 하나가 존재한다는 것은 다르다.
명제 논리는 참이나 거짓으로 판단할 수 있는 명제와 논리 연결사의 관계를 다루는 논리 체계이다. 부정·논리곱·논리합·함의 등으로 복합 명제를 구성한다. 명제의 내부 구조보다 각각의 진릿값이 전체 식에 미치는 영향을 살핀다. p가 비가 온다, q가 우산을 쓴다라면 p→q는 비가 오는데 우산을 쓰지 않는 경우에 거짓이다. 수학적 함의는 일상 언어의 인과관계와 같지 않다. 전제가 거짓일 때의 진릿값과 필요조건·충분조건의 방향을 구별
