방송대 이산수학 15강: 문제를 구조로 바꾸는 통합 복습
이산수학의 여러 공식은 문제마다 따로 꺼내 쓰는 암기 목록이 아닙니다. 현실의 문제에서 핵심만 추상화하고, 참인 주장을 세우고, 적절한 구조로 표현하고, 계산이나 탐색으로 답을 얻은 뒤 그 결과를 검증하는 하나의 문제 해결 체계입니다. 이 글은 1강부터 14강까지의 개념을 이 흐름 위에 다시 배치하여, 문제의 단서만 보고도 어떤 도구를 선택하고 어떤 조건을 확인해야 하는지 판단하도록 돕습니다.
문제의 단서가 사용할 수학 도구를 결정한다
같은 상황도 무엇을 묻느냐에 따라 필요한 구조가 달라집니다. “가능한 배치가 몇 개인가”는 조합론, “모든 지점을 연결하는 최소 비용은 얼마인가”는 그래프와 트리, “입력 문자열을 받아들일 것인가”는 오토마타의 문제입니다. 먼저 질문의 동사와 보존해야 할 정보를 찾으면 장 이름을 외우지 않아도 도구를 고를 수 있습니다.
| 문제의 단서 | 우선 선택할 구조 | 핵심 확인 | 대표 결과 |
|---|---|---|---|
| 참인지, 결론이 따라오는지 | 논리·증명 | 전제, 한정자, 추론 규칙 | 유효한 결론 |
| 대상을 묶고 포함 관계를 따지는지 | 집합 | 원소, 부분집합, 교집합 | 분류와 대수적 관계 |
| 표 형태 수치나 연립 조건을 바꾸는지 | 행렬 | 차원, 행·열 대응 | 변환과 해 |
| 대상 사이의 연결 또는 대응을 묻는지 | 관계·함수 | 순서쌍, 정의역, 치역 | 동치류·역함수 |
| 참·거짓 회로식을 줄이는지 | 부울대수 | 논리연산과 쌍대성 | 간소화된 논리회로 |
| 경로·연결·최소 비용을 찾는지 | 그래프·트리 | 변과 꼭지점, 사이클, 가중치 | 최단 경로·최소 신장 트리 |
| 경우의 수·확률·큰 정수를 계산하는지 | 조합론·정수론 | 순서, 중복, 소수, 모듈로 | 개수·확률·나머지 |
| 상태가 입력이나 확률로 변하는지 | 오토마타·마르코프 연쇄 | 상태, 전이, 수용 조건 | 문자열 판정·n단계 확률 |
첫 판단: 대상 자체보다 질문이 요구하는 출력에 주목하십시오. 사람과 도로가 주어져도 팀 수를 세면 조합론이고, 이동 경로를 찾으면 그래프입니다.
추상화는 현실을 버리는 것이 아니라 핵심을 남기는 일이다
이산수학은 연속적으로 변하는 양보다 서로 구분되는 수학적 구조를 다룹니다. 문제 해결은 현실의 모든 세부를 그대로 옮기는 데서 시작하지 않습니다. 수학적 모델링은 해결에 필요한 대상을 수학적 도구로 표현하는 과정이고, 추상화는 관련 없는 정보를 제거하거나 단순화해 핵심만 남기는 과정입니다. 컴퓨터가 처리할 자료와 연산으로 바꾸면 정보 모델링이 됩니다.
학습을 위해 캠퍼스의 강의실 이동 문제를 가정해 보겠습니다. 벽 색과 날씨는 경로 계산에 필요하지 않으므로 제거하고, 강의실을 꼭지점, 이동 통로를 변, 이동 시간을 가중치로 남기면 가중 그래프가 됩니다. 반대로 출입 권한을 판단하려면 통로의 길이보다 학생 집합, 강의 수강 집합, 허가 조건이 중요합니다. 같은 현실이라도 질문이 바뀌면 모델도 바뀝니다.
알고리즘은 선택한 모델에서 답을 얻는 명확한 절차입니다. 프로그래밍 언어, 순서도, 의사코드는 알고리즘을 모호하지 않게 표현하는 수단입니다. 모델이 잘못되면 알고리즘이 정확히 실행되어도 현실의 질문에는 틀린 답을 냅니다. 따라서 입력, 출력, 남길 조건, 버릴 조건을 먼저 적는 습관이 중요합니다.
논리와 증명은 모델에서 얻은 결론을 지킨다
명제는 참과 거짓을 구분할 수 있는 문장이나 수식입니다. 논리합 p∨q, 논리곱 p∧q, 부정 ¬p, 배타적 논리합을 사용해 합성명제를 만들고, 조건명제 p→q와 쌍조건명제 p↔q로 관계를 표현합니다. 모든 진리값 배정에서 같은 값을 가지면 논리적 동치이고, 언제나 참이면 항진명제, 언제나 거짓이면 모순명제입니다.
변수가 들어간 명제함수는 값을 정해야 진리값이 결정됩니다. 전체한정자 ∀는 모든 원소, 존재한정자 ∃는 적어도 하나의 원소를 뜻합니다. ¬∀x P(x)는 ∀x ¬P(x)가 아니라 ∃x ¬P(x)와 같습니다. “모든 학생이 제출했다”의 부정은 “아무도 제출하지 않았다”가 아니라 “제출하지 않은 학생이 적어도 한 명 있다”입니다.
참인 전제에서 논리적 과정을 거쳐 결론을 얻는 것이 추론이며, 전제를 참이라 가정했을 때 결론이 항상 참이면 유효추론입니다. 증명은 이 정당성을 구체화합니다.
| 증명 방법 | 적합한 목표 | 출발점 | 대표 실패 |
|---|---|---|---|
| 직접증명 | p→q | p를 가정해 q를 도출 | 결론을 먼저 가정함 |
| 수학적 귀납법 | 모든 자연수 n에 대한 명제 | 기본단계, 귀납가정, 귀납단계 | 기본단계를 생략함 |
| 대우증명 | 직접 전개가 어려운 조건명제 | ¬q→¬p | 역 q→p를 증명함 |
| 모순증명 | 부정 가정이 모순을 만드는 명제 | 결론의 부정 | 모순과 단순한 불편함을 혼동함 |
| 반례 | 전칭명제의 거짓 판정 | 조건을 만족하는 한 사례 | 조건을 어긴 사례를 제시함 |
공리는 다른 명제를 증명하는 기본 가정이고, 정리는 공리와 이미 증명된 사실에서 입증된 명제입니다. 전수증명, 조합적 증명, 존재증명, 컴퓨터를 이용한 증명도 목표와 가능한 정보에 따라 선택합니다.
논리·집합·부울대수는 같은 법칙을 다른 기호로 말한다
논리, 집합, 부울대수는 표현 대상은 다르지만 대수 구조가 닮았습니다. 참인 조건을 만족하는 원소들의 집합을 생각하면 논리합은 합집합, 논리곱은 교집합, 부정은 여집합에 대응합니다. 이를 알면 세 장의 공식을 따로 외우지 않고 하나의 법칙을 다른 표기로 번역할 수 있습니다.
| 논리 | 집합 | 부울대수 | 공통 의미 |
|---|---|---|---|
T, F | U, ∅ | 1, 0 | 전체/참과 없음/거짓 |
p∨q | A∪B | X+Y | 둘 중 하나 이상 |
p∧q | A∩B | XY | 둘 다 만족 |
¬p | Ac | X̅ | 보수 또는 부정 |
| 드 모르간 법칙 | (A∪B)c=Ac∩Bc | (X+Y)̅=X̅Y̅ | 연산을 바꾸며 각 항을 부정 |
집합에서는 원소 나열법과 조건 제시법으로 대상을 표현하고, 부분집합·진부분집합·상등을 구분합니다. 집합의 분할은 서로 겹치지 않는 부분집합들이 전체를 이루는 구조이며, 멱집합은 모든 부분집합의 집합입니다. 유한집합 A, B에는 |A∪B|=|A|+|B|−|A∩B|가 성립합니다. 겹치는 원소를 두 번 센 것을 한 번 빼는 원리입니다.
부울대수의 간소화는 단순히 식을 짧게 쓰는 문제가 아닙니다. 복잡한 부울함수와 대응하는 논리회로를 더 간단한 함수와 회로로 바꾸는 작업입니다. 항등·보수·멱등·흡수·분배 법칙과 쌍대성 원리를 사용하되, 일반 산술의 +와 부울 논리합을 같은 연산으로 착각해서는 안 됩니다.
행렬은 표 형태의 관계와 계산을 한꺼번에 다룬다
m×n 행렬은 m개의 행과 n개의 열로 이루어진 수의 배열이며 aij는 i행 j열의 원소입니다. 행렬의 합과 차는 같은 위치 원소끼리 계산하므로 두 행렬의 크기가 같아야 합니다. 스칼라곱은 모든 원소에 같은 수를 곱합니다.
행렬곱 AB=C에서는 A의 열 수와 B의 행 수가 같아야 하며, cij=Σk=1naikbkj입니다. 직접 구성한 예에서 A가 2×3, B가 3×4이면 AB는 가능하고 결과는 2×4입니다. 그러나 BA는 B의 열 수 4와 A의 행 수 2가 달라 정의되지 않습니다. 숫자의 개수보다 안쪽 차원의 일치가 판단 기준입니다.
가우스 소거법은 행 교환, 0이 아닌 상수배, 한 행의 배수를 다른 행에 더하는 기본행연산으로 행제형 또는 소거 행제형 행렬을 만듭니다. 정방·대각·단위·대칭·역대칭·삼각·전치·역행렬은 모양이나 연산 성질에 따라 구분합니다. 역행렬은 정방행렬이라고 모두 존재하는 것이 아니라 행렬식 등 가역 조건을 만족해야 합니다.
0과 1로 이루어진 부울행렬은 관계와 그래프를 표현할 때 특히 유용합니다. 일반 산술 덧셈·곱셈 대신 논리합과 논리곱을 사용한 부울합, 부울교차, 부울곱으로 도달 가능성 같은 구조를 계산합니다.
관계와 함수는 대응을 얼마나 엄격하게 제한하는지가 다르다
A에서 B로의 관계 R은 곱집합 A×B의 부분집합입니다. 즉 가능한 순서쌍 가운데 실제로 연결된 쌍을 고른 것입니다. 관계는 순서쌍 집합, 화살표 도표, 방향 그래프, 부울행렬로 표현할 수 있으며 표현이 바뀌어도 포함된 순서쌍은 같아야 합니다.
A 위의 관계에서 반사성은 모든 x에 xRx, 대칭성은 xRy이면 yRx, 추이성은 xRy이고 yRz이면 xRz인 성질입니다. 세 성질을 모두 만족하면 동치관계이고, 서로 동치인 원소들이 동치류를 이룹니다. 역관계는 순서쌍의 방향을 바꾸고, 합성관계는 중간 대상을 거쳐 연결합니다.
함수는 관계 중에서도 정의역의 각 원소가 공역의 원소 하나에 정확히 대응하는 경우입니다. 전사함수는 공역의 모든 원소가 적어도 한 번 대응되고, 단사함수는 서로 다른 입력이 서로 다른 출력으로 갑니다. 전단사는 두 조건을 모두 만족하며 역함수가 존재합니다.
그림 판독 순서: 먼저 각 입력에서 화살표가 정확히 하나인지 보아 함수 여부를 판단합니다. 그다음 출력이 빠짐없이 덮였는지로 전사, 서로 합쳐지는 화살표가 없는지로 단사를 판정합니다. 함수도 아닌 대응에 전사·단사 이름부터 붙이지 않습니다.
함수의 합성은 한 함수의 출력을 다음 함수의 입력으로 이어 붙입니다. 계승함수, 바닥함수, 천장함수, 나머지 함수는 이산수학에서 정수 구조를 표현하는 대표 함수입니다. 바닥은 해당 실수 이하의 가장 큰 정수, 천장은 해당 실수 이상의 가장 작은 정수이므로 음수에서 방향을 반대로 기억하지 않도록 주의합니다.
그래프는 연결을, 트리는 사이클 없는 핵심 연결을 남긴다
그래프 G=(V,E)는 꼭지점 집합 V와 변 집합 E로 이루어집니다. 방향 유무, 루프와 병렬 변의 허용 여부에 따라 종류가 달라집니다. 부분 그래프는 꼭지점과 변 일부를 고르고, 신장 부분 그래프는 모든 꼭지점을 유지한 채 변 일부를 고릅니다. 차수는 꼭지점에 닿은 변 수이며 방향 그래프에서는 진입차수와 진출차수를 구분합니다.
워크는 꼭지점과 변을 따라 이동한 일반적인 열이고, 트레일은 변을 반복하지 않으며, 경로는 꼭지점을 반복하지 않습니다. 오일러 투어는 시작점과 종점이 같고 모든 변을 한 번씩 지나는 트레일입니다. 해밀턴 경로는 모든 꼭지점을 한 번씩 지나는 경로이며, 닫히면 해밀턴 사이클입니다. 하나는 변 전체, 다른 하나는 꼭지점 전체가 기준입니다.
연결 그래프는 임의의 두 꼭지점 사이에 경로가 있습니다. 완전 그래프는 서로 다른 모든 꼭지점 쌍이 변으로 연결되고, 이분 그래프는 꼭지점을 두 집합으로 나누어 같은 집합 내부에는 변이 없게 할 수 있습니다. 모든 꼭지점의 차수가 k이면 k-정규 그래프입니다. 그래프는 발생행렬, 인접행렬, 인접리스트로 표현할 수 있으며, 희소 그래프에는 보통 인접리스트가 불필요한 0을 덜 저장합니다.
평면 그래프는 변이 서로 교차하지 않게 다시 그릴 수 있는 그래프입니다. 가중 그래프는 변에 실수값인 가중치를 붙이고, 데이크스트라 알고리즘은 주어진 출발점에서 최단 경로를 찾는 데 사용합니다. 단순히 가장 작은 변들을 전체에서 고르는 것은 최단 경로의 연결성을 보장하지 않습니다.
트리 문제는 n−1과 사이클 금지를 불변조건으로 삼는다
트리는 사이클이 없는 단순 연결 그래프입니다. 꼭지점이 n개인 연결 그래프가 트리일 필요충분조건 가운데 하나는 변이 정확히 n−1개라는 것입니다. 변 수만 맞고 연결되지 않았다면 트리가 아닙니다.
루트를 정하면 부모·자식·형제·단말 노드·내부 노드·레벨·높이가 생깁니다. 이진 트리는 공집합이거나 각 노드가 최대 두 개의 좌우 서브트리를 갖는 루트 트리입니다. 높이 h의 포화 이진 트리 노드 수는 Σi=0h2i=2h+1−1이고, n개 노드를 가장 촘촘히 배치한 최소 높이는 ⌊log₂n⌋입니다.
이진 탐색 트리는 각 노드의 왼쪽 서브트리 키가 작고 오른쪽 서브트리 키가 큰 구조입니다. 삽입 순서에 따라 모양과 탐색 비용이 달라지므로, 부모 하나만 비교하지 말고 조상에서 누적된 상한과 하한을 확인해야 합니다.
최소 신장 트리(MST)는 모든 꼭지점을 포함하는 신장 트리 중 총가중치가 가장 작은 트리입니다. Kruskal 알고리즘은 전체 변을 가중치 순으로 보며 사이클을 만들지 않는 변을 선택하고, Prim 알고리즘은 현재 트리와 바깥 꼭지점을 잇는 최소 경계 변으로 확장합니다. 둘 다 끝에는 n개 꼭지점과 n−1개 변, 연결, 무사이클 조건을 만족해야 합니다.
세기 문제는 순서·중복·겹침을 먼저 판정한다
동시에 연속되는 선택은 곱의 법칙, 서로 다른 경우를 합치는 선택은 합의 법칙을 사용합니다. 두 사건이 겹치면 N(A∪B)=N(A)+N(B)−N(A∩B)로 중복을 제거합니다. “또는”이라는 말만 보고 무조건 더하면 겹치는 경우를 두 번 셀 수 있습니다.
| 선택 상황 | 순서 | 중복 | 도구 |
|---|---|---|---|
| n개 중 r개를 줄 세움 | 고려 | 허용 안 함 | P(n,r)=n!/(n−r)! |
| n종류에서 r번 선택 | 고려 | 허용 | nr |
| 원형으로 배치 | 회전은 같은 배치 | 허용 안 함 | (n−1)! |
| n개 중 r개 집합을 선택 | 무시 | 허용 안 함 | C(n,r)=n!/[r!(n−r)!] |
이항정리 (x+y)n=Σk=0nC(n,k)xn−kyk는 전개항의 선택을 조합으로 연결합니다. 유한하고 모든 결과가 같은 가능성을 갖는 표본공간 S에서 사건 E의 수학적 확률은 P(E)=|E|/|S|이고, P(B)>0일 때 조건부확률은 P(A|B)=P(A∩B)/P(B)입니다.
점화식은 수열 항 사이의 관계를 나타내며, 점화식을 푼다는 것은 일반항을 n에 관한 식으로 표현한다는 뜻입니다. 비둘기집 원리는 N개 물체를 k개 상자에 넣으면 적어도 한 상자에 ⌈N/k⌉개 이상이 들어간다고 보장합니다. 어느 상자인지는 알려 주지 않아도 존재 자체는 증명합니다.
정수론은 큰 수를 나머지와 소수 구조로 줄인다
양의 정수 b에 대해 정수 a는 유일하게 a=bq+r, 0≤r<b로 표현됩니다. 유클리드 알고리즘은 gcd(a,b)=gcd(b,r)을 반복해 최대공약수를 구합니다. a≡b (mod m)은 m이 a−b를 나눈다는 뜻이며, 같은 나머지를 가진 수들의 계산을 작은 대표값으로 바꿉니다.
소수는 1과 자기 자신만 양의 약수로 가지는 1보다 큰 정수이고, 1은 소수도 합성수도 아닙니다. 산술의 기본정리는 2 이상의 모든 정수가 순서를 제외하면 소수의 곱으로 유일하게 표현된다고 말합니다. 합성수 n은 √n 이하의 소인수를 가지므로 소수 판정 범위를 줄일 수 있습니다.
소수 p가 a를 나누지 않으면 페르마의 소정리에 따라 ap−1≡1 (mod p)입니다. 큰 거듭제곱은 지수를 이진수로 바꾸고 반복 제곱하면서 매 단계 나머지를 취하면 수의 폭발을 막을 수 있습니다. 이 최대공약수, 소수, 합동, 모듈로 거듭제곱이 RSA 암호의 수학적 기반을 이룹니다.
경계 오류: 합동식의 공통인수는 보통 등식처럼 무조건 약분할 수 없습니다. 공통인수와 모듈로의 최대공약수가 1인지 먼저 확인해야 하며, 그렇지 않으면 모듈로도 함께 줄어듭니다.
오토마타와 형식 언어는 계산 가능한 절차를 상태와 규칙으로 닫는다
오토마타는 입력을 받으며 상태를 바꾸는 자동 장치의 수학적 모델입니다. 일반 유한 오토마타는 입력·출력·상태와 전이·출력 함수 등으로 표현하고, 문자열 인식에 초점을 둔 결정적 유한 오토마타(DFA)는 각 상태와 입력 기호에 다음 상태가 하나로 정해집니다. 비결정적 유한 오토마타(NFA)는 가능한 다음 상태의 집합과 ε-전이를 허용합니다. NFA의 여러 경로 중 하나라도 수용 상태에 도달하면 문자열을 받아들입니다.
마르코프 연쇄는 현재 상태가 주어졌을 때 다음 상태의 확률이 그 이전 역사와 무관하다는 마르코프 성질을 가진 이산확률과정입니다. 상태전이도와 전이확률행렬로 표현하며, n단계 전이확률행렬은 채프만·콜모고로프 관계에 따라 P(n)=P(n−1)P=Pn으로 구합니다. 행렬곱은 가능한 중간 상태를 모두 합산하는 역할을 합니다.
형식 언어는 유한한 기호 집합인 알파벳에서 만든 문자열들의 집합입니다. Σn은 길이 n의 문자열, Σ+는 길이 1 이상인 문자열, Σ*는 빈 문자열 ε를 포함한 모든 유한 문자열을 뜻합니다. 형식 문법 G=(V,T,P,S)는 변수, 단말기호, 생성규칙, 시작기호로 언어 L(G)를 정의합니다.
촘스키 계층은 생성규칙의 제약에 따라 무제약 문법(Type 0), 문맥 의존 문법(Type 1), 문맥 자유 문법(Type 2), 정규 문법(Type 3)으로 나눕니다. 숫자가 커질수록 더 일반적이라는 뜻이 아니라 Type 0이 가장 제약이 적고 Type 3이 가장 제한적입니다.
통합 문제는 표현·조건·연산·검산의 네 칸으로 푼다
한 문제에 여러 단원이 섞이면 공식부터 찾지 말고 네 칸의 풀이 장부를 만드십시오.
- 표현: 집합, 행렬, 그래프, 함수, 상태 중 무엇으로 바꿀지 정합니다.
- 조건: 전사·단사, 연결·무사이클, 순서·중복, 소수·서로소처럼 정리의 전제를 적습니다.
- 연산: 행렬곱, 탐색, 계수법칙, 모듈로 거듭제곱, 상태전이를 수행합니다.
- 검산: 차원, 개수, 변 수, 확률합, 나머지 범위, 수용 상태를 확인합니다.
직접 구성한 통합 예로, 특정 수강생만 이용하는 셔틀 경로와 출입 코드를 설계한다고 가정합니다. 수강생 분류는 집합, 학생과 강의의 연결은 관계, 각 학생에게 코드 하나를 배정하는 규칙은 함수, 셔틀 노선은 가중 그래프, 최소 연결망은 트리, 가능한 코드 수는 조합론, 코드의 나머지 계산은 정수론, 입력 코드의 형식 판정은 오토마타가 담당합니다. 개념들이 경쟁하는 것이 아니라 문제의 서로 다른 층을 나누어 맡습니다.
최종 자가 점검: “왜 이 구조인가?”, “정리의 전제가 모두 있는가?”, “연산 뒤에도 구조의 불변조건이 유지되는가?”, “결과를 반례나 경계값으로 다시 확인했는가?”에 답할 수 있으면 단원 통합 문제도 흔들리지 않습니다.
핵심 개념 정리
- 표현 층: 추상화로 핵심을 남기고 집합·행렬·그래프·상태 중 질문에 맞는 모델을 선택한다.
- 정당화 층: 명제와 한정자를 정확히 읽고 목표의 형태에 맞는 증명법으로 결론을 보장한다.
- 구조 층: 관계는 순서쌍의 부분집합, 함수는 입력마다 출력 하나를 강제한 특별한 관계다.
- 연결 층: 그래프는 일반 연결, 트리는 연결과 무사이클, 오토마타는 상태 사이 전이를 표현한다.
- 계산 층: 순서·중복·겹침은 계수 도구를, 소수·최대공약수·합동은 정수 계산 도구를 결정한다.
- 검산 층: 행렬 차원, 트리의 n−1개 변, 확률의 분모, 합동의 모듈로, 오토마타의 수용 상태를 되짚는다.
새 문제를 만나면 단원 이름을 먼저 떠올리기보다 무엇을 남겨야 하는지 묻고 구조를 선택하십시오. 이어서 적용할 정리의 전제를 명시하고, 구조에 맞는 연산을 수행하며, 마지막에는 그 구조의 불변조건으로 검산합니다. 이산수학의 14개 주제는 이 네 단계에서 표현 언어, 정당화 방법, 계산 도구, 실행 모델로 서로 연결됩니다.
예상문제 10선
1. 여러 도시를 모두 연결하면서 도로 건설비의 합을 최소화하려 한다. 가장 직접적인 모델과 목표는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
- ① 오답: 멱집합은 가능한 부분집합 전체를 나타내며 도로의 연결과 비용 최소화를 직접 모델링하지 않는다.
- ② 오답: 진리표는 명제의 참·거짓을 분석하지만 거리나 연결 구조를 보존하지 않는다.
- ③ 정답: 도시를 꼭지점, 도로와 비용을 가중 변으로 놓으면 모든 꼭지점을 최소 총비용으로 잇는 MST 문제가 된다.
- ④ 오답: 형식 문법은 문자열의 생성 규칙을 정의하는 도구다.
2. “모든 정수 x에 대해 P(x)가 참이다”의 부정으로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
- ① 정답: 전체한정자의 부정은 존재한정자로 바뀌고 명제함수도 부정되어
∃x¬P(x)가 된다. - ② 오답: 한 개의 반례만 있어도 원래 전칭명제는 거짓이므로 모든 원소가 실패할 필요는 없다.
- ③ 오답: 원래 명제가 참이어도 함께 성립할 수 있어 부정이 아니다.
- ④ 오답: 정의역이 정수로 주어졌으므로 한정자 규칙으로 명확히 부정할 수 있다.
3. 직접증명보다 대우증명이 자연스러운 목표를 올바르게 변형한 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
- ① 오답: 이는 역이며 원래 조건명제와 일반적으로 동치가 아니다.
- ② 오답: 이는 이이고 원래 명제와 같은 진리값을 보장하지 않는다.
- ③ 오답: 함축을 논리곱으로 바꾸면 명제의 참 조건이 달라진다.
- ④ 정답: 대우는 원래 조건명제와 논리적으로 동치이므로 이를 증명해도 목표가 성립한다.
4. A가 3×2 행렬이고 B가 2×4 행렬일 때 옳은 설명은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
- ① 오답: 곱의 순서에 따라 안쪽 차원이 달라져 가능 여부와 결과 크기가 달라진다.
- ② 정답: AB의 안쪽 차원 2가 일치해 바깥 차원 3×4가 남지만, BA는 4와 3이 맞지 않는다.
- ③ 오답: 결과 크기는 첫 행렬의 행 수와 둘째 행렬의 열 수로 결정된다.
- ④ 오답: 가능 여부를 판단할 안쪽 차원의 순서를 반대로 읽었다.
5. 화살표 도표가 주어졌을 때 전단사 여부를 판정하는 순서로 가장 적절한 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
- ① 정답: 함수 조건을 먼저 확인하고 전사와 단사를 모두 만족해야 전단사와 역함수를 논할 수 있다.
- ② 오답: 입력 하나가 출력 둘로 가면 중복이 없어 보여도 함수가 아니다.
- ③ 오답: 집합 크기가 같아도 실제 대응이 빠지거나 겹칠 수 있다.
- ④ 오답: 역관계가 함수가 되려면 원래 대응이 전단사인지 확인해야 한다.
6. 오일러 투어와 해밀턴 사이클을 구분한 설명으로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
- ① 오답: 해밀턴 문제는 변의 전수 사용이 아니라 꼭지점의 한 번 방문을 요구한다.
- ② 오답: 두 개념의 판단 대상을 서로 바꾸어 설명했다.
- ③ 정답: 변 중심과 꼭지점 중심이라는 차이가 두 순회를 구분하는 핵심이다.
- ④ 오답: 사이클은 닫힌 경로이므로 시작점과 종점이 같다.
7. 꼭지점 8개를 모두 포함하고 사이클이 없는 연결 그래프의 변 수는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
- ① 오답: 8개 꼭지점을 6개 변만으로 모두 연결하면 적어도 두 연결성분이 남는다.
- ② 정답: 연결되고 사이클이 없는 트리는 n개 꼭지점에 정확히 n−1개의 변을 가진다.
- ③ 오답: 트리에 변 하나를 더하면 기존 두 꼭지점 사이 경로와 함께 사이클이 생긴다.
- ④ 오답: 28은 단순 완전 그래프
K₈의 변 수이지 트리의 변 수가 아니다.
8. 서로 다른 7명 중 회장과 부회장을 한 명씩 뽑는 방법의 수는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
- ① 오답: 두 직책 각각의 후보 수를 단순히 더하면 연속 선택의 조합을 세지 못한다.
- ② 오답:
C(7,2)는 두 사람만 고르고 직책 순서를 구분하지 않은 값이다. - ③ 오답: 첫 사람을 뽑은 뒤 남은 후보가 6명이라는 조건을 올바르게 반영하지 않았다.
- ④ 정답: 직책이 달라 순서를 고려하므로
P(7,2)=7×6=42다.
9. NFA가 입력 문자열을 수용하는 조건으로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
- ① 오답: NFA는 여러 가능한 상태와 경로를 동시에 고려하므로 끝 상태가 모두 같을 필요가 없다.
- ② 정답: 입력을 모두 처리한 뒤 가능한 경로 중 적어도 하나가 수용 상태에 도달하면 수용한다.
- ③ 오답: 다음 상태가 하나로 정해지는 것은 DFA의 결정성 조건이다.
- ④ 오답: 일반적으로 입력에 따른 상태전이를 수행한 결과로 수용 여부를 판정한다.
10. 여러 단원이 섞인 문제를 해결하는 순서로 가장 적절한 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
- ① 오답: 표현과 구조를 정하기 전의 계산은 보존해야 할 정보를 놓치며 조건을 삭제하면 정리를 적용할 수 없다.
- ② 오답: 모델과 전제를 나중에 확인하면 맞지 않는 공식을 정확히 계산하는 오류가 생긴다.
- ③ 정답: 무엇으로 나타낼지, 정리가 성립하는지, 어떻게 계산할지, 결과가 구조를 지키는지를 차례로 확인한다.
- ④ 오답: 반례는 검증 도구가 될 수 있지만 원래 질문과 필요한 계산을 임의로 없애서는 안 된다.
참고 자료와 작성 기준
이 글은 해당 차시 강의자료를 바탕으로 학습 목적에 맞게 재구성한 비공식 학습자료입니다. 1강부터 14강까지의 내용을 문제 해결 단계에 따라 다시 연결하고, 도구 선택 기준과 경계 오류를 중심으로 통합 복습할 수 있게 구성했습니다.
- 작성·편집: 올에이클래스 학습연구팀
- 주요 근거: 한국방송통신대학교 이산수학 15강 「이산수학 학습내용 정리」 강의자료 98쪽(2021) :codex-file-citation{path="K1. 컴퓨터과학과/1. 재검토필요/2-1 이산수학/1. 강의록/이산수학_강의록_15강.pdf" purpose="source"}
- 자료 성격: 강의자료의 정의와 범위를 바탕으로 재구성한 비공식 학습자료
- 편집 원칙: 올에이클래스 편집 정책
- 최종 내용 검토: 2026-09-06
댓글
댓글 쓰기