이산수학: 연습 문제와 시험 문제

컴퓨터 과학과 모든 증명의 수학입니다. 명제논리와 한정자, 집합, 관계와 함수, 최단 경로와 신장 트리를 다루는 그래프, 그리고 RSA까지 이어지는 정수론을 배웁니다. 시험 문제는 정확한 답을 요구하므로 계산기보다 꼼꼼한 표나 그림이 더 중요합니다.

이 강의 무료로 연습하기이 강의 연습하기모의고사 보기매일 무료 문제 5개. 카드 등록이 필요 없습니다.

벼락치기 팩 (PDF)인쇄하기 좋은 공식 모음, 풀이 단계 요약, 전체 풀이가 있는 연습 문제.

이 강의의 주제

  1. 명제논리와 증명진리표 · 동치와 증명 방법 · 한정자와 논증계산 문제
  2. 집합, 관계, 함수벤 다이어그램과 부분집합 · 포함·배제와 관계 · 함수와 세기계산 문제
  3. 그래프 이론차수와 간선 · 오일러 경로와 트리 · 최단 경로와 신장 트리계산 문제
  4. 정수론과 모듈러 연산최대공약수와 나머지 · 역원과 합동식 · 모듈러 거듭제곱과 RSA계산 문제

이산수학 시험 팁

  • 진리표나 벤 다이어그램을 끝까지 써 보세요. 실수의 대부분은 행이나 영역 하나를 건너뛰어서 생깁니다.
  • 주장을 반박하려면 반례 하나로 충분하지만, 증명하려면 모든 경우를 확인하거나 일반적인 논증을 해야 합니다.
  • 모듈러 연산에서는 단계마다 나머지를 구하고, 나머지를 0부터 n − 1 사이로 유지하세요.

예제 풀이

명제논리와 증명쉬움
pq¬(p ∨ q) → q11100100

진리표에서 ¬(p ∨ q) → q이(가) 거짓이 되는 행은 정확히 하나입니다. 그 행을 클릭하세요.

¬(p ∨ q) → q
  1. 1p = 1, q = 1
  2. 2p = 1, q = 0
  3. 3p = 0, q = 1
  4. 4p = 0, q = 0
힌트 보기
  1. a → b는 a = 1이고 b = 0일 때만 0입니다. ¬a는 값을 뒤집습니다. a ∨ b는 둘 다 0일 때만 0입니다.
  2. 주 연결자를 먼저 따져 보세요. 전체 식이 0이(가) 되려면 양쪽이 무엇이어야 할까요?
  3. 각 부분에 열을 하나씩 주세요: p ∨ q; ¬(p ∨ q); ¬(p ∨ q) → q.
정답과 설명 보기

진리표: 서로 다른 변수가 n개인 식은 참값(1 = 참, 0 = 거짓)의 모든 조합마다 하나씩 2ⁿ개의 행을 가집니다. 안쪽부터 바깥쪽으로 작업하고 모든 부분식에 각각 열을 주세요. ¬a는 값을 뒤집습니다. a ∧ b는 둘 다 1일 때만 1입니다. a ∨ b는 둘 다 0일 때만 0입니다. a → b는 a = 1이고 b = 0일 때만 0입니다. a ↔ b는 양쪽이 같을 때 1입니다.

행별 진리표

p = 1, q = 1: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 1, q = 0: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 0, q = 1: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 0, q = 0: p ∨ q = 0, ¬(p ∨ q) = 1, ¬(p ∨ q) → q = 0

행

p = 0, q = 0 → ¬(p ∨ q) → q = 0

답

p = 0, q = 0
집합, 관계, 함수보통
UMPC

1학년 학생 53명 중 35명이 수학(M), 28명이 물리(P), 29명이 화학(C)에 합격했다. 20명이 M과 P에, 18명이 M과 C에, 10명이 P와 C에 합격했고 6명이 세 과목 모두에 합격했다. 세 집합 어디에도 속하지 않는 것은 몇 개인가?

|U| = 53

구하는 값: |(M ∪ P ∪ C)′|

힌트 보기
  1. 벤 다이어그램을 가운데에서 바깥쪽으로 채우세요. 먼저 세 집합 모두, 그다음 쌍, 그다음 한 집합씩.
  2. M와(과) P에만 속함(C에는 속하지 않음): 20 − 6 = 14. M에만 속함: 35 − 14 − 12 − 6 = 3.
  3. 적어도 한 집합: 35 + 28 + 29 − 20 − 18 − 10 + 6 = 50.
정답과 단계별 풀이 보기

집합과 벤 다이어그램: A ∪ B는 A 또는 B(또는 둘 다)에 속하는 원소, A ∩ B는 둘 다에 속하는 원소, A − B는 A의 원소 중 B에 속하지 않는 원소이고, 여집합 A′는 U의 원소 중 A에 속하지 않는 모든 것입니다. 벤 다이어그램에서 모든 집합식은 영역들의 합집합이므로 영역별로 세세요. 포함·배제: |A ∪ B| = |A| + |B| − |A ∩ B|, 그리고 |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

가운데와 쌍

M ∩ P ∩ C: 6
M ∩ P 만: 20 − 6 = 14
M ∩ C 만: 18 − 6 = 12
P ∩ C 만: 10 − 6 = 4

한 집합씩

M 만: 35 − 14 − 12 − 6 = 3
P 만: 28 − 14 − 4 − 6 = 4
C 만: 29 − 12 − 4 − 6 = 7

답

|M ∪ P ∪ C| = 50
|(M ∪ P ∪ C)′| = 53 − 50 = 3

답

|(M ∪ P ∪ C)′| = 3

연습 방법

  • “이 강의 연습하기”는 실제 시험처럼 모든 주제의 문제를 섞어서 냅니다.
  • 문제마다 값이 새로 바뀌므로 답이 아니라 푸는 방법을 익히게 됩니다.
  • 막혔나요? 먼저 작은 힌트를 열고, 필요할 때만 전체 해설을 보세요.
  • 모의고사는 제한 시간이 있고 힌트가 없으며, 끝나면 점수와 함께 전체 풀이를 검토할 수 있습니다.

관련 강의

컴퓨터과학 기초자료구조와 알고리즘미적분학 1기초통계학공업수학통계학 2: 추론 통계미분방정식공업수학 2
이 강의 무료로 연습하기이 강의 연습하기모의고사 보기매일 무료 문제 5개. 카드 등록이 필요 없습니다.