로표기한다. 논리곱 ( ): 나는내차를운전할것이고나는늦을것이다., 를논리합 (disjunction) 은복합명제 ' or ' 에해당하며 로표기한다. 논리합 ( ): 나는내차를운전하거나나는늦을것이다. 4. 다음명제의참, 거짓을밝혀라. (1) 이고 3은양의정수이다. 참 (T

Transcription

1 제 1 장기초 1.1 논리연습문제 다음중명제인것을모두고르면? 1 2는양수인가? 2 -+5=0 3 논리를공부하라. 4 1월에는눈이내린다. 5 봄이오면꽃이핀다. 명제란감탄문, 명령문, 의문문이아닌어떠한사실을전달하는데사용되는문장, 참이나거짓중하나만을진리값으로갖는평서문을말한다. 따라서 1은의문문, 2은 x의값이명시되지않았기에 3은명령문이므로명제가될수없다. 41월이되어야눈이내리는지아닌지알수있다는있으나참또는거짓둘중의하나만을가지며평서문이므로명제이다. 5 봄이오면꽃이피는것은사실이므로참인평서문으로명제이다. 2. 다음명제의부정을구하여라. (1) (2) 4는짝수이고 6은홀수이다. 4는홀수이거나 6은짝수이다. (3) 내일비가오거나내일눈이내릴것이다. 의부정은 이므로 내일비도오지않고내일눈도내리지않을것이다. (4) 당신이운전을한다면나는걸어갈것이다. 복합명제로 의부정은 ~ 이다. 그러므로 당신이운전을하고나는걸어가지않는다. 3. 와 의논리곱과논리합을각각구하여라. (1) 논리곱 : 이고 논리합 : 이거나 (2) 나는부자다 나는행복하다 논리곱 : 나는부자이고나는행복하다. 논리합 : 나는부자이거나나는행복하다. (3) : 나는내차를운전할것이다. : 나는늦을것이다., 를명제라할때 와 의논리곱 (conjunction) 은복합명제 ' and ' 에해당하며 - 1 -

2 로표기한다. 논리곱 ( ): 나는내차를운전할것이고나는늦을것이다., 를논리합 (disjunction) 은복합명제 ' or ' 에해당하며 로표기한다. 논리합 ( ): 나는내차를운전하거나나는늦을것이다. 4. 다음명제의참, 거짓을밝혀라. (1) 이고 3은양의정수이다. 참 (T) (2) 이고 3은양의정수이다. 거짓 (F) (3) 이고 3은양의정수가아니다. 거짓 (F) (4) 이고 3은양의정수가아니다. 거짓 (F) (5) 이거나 3은양의정수이다. 참 (T) (6) 이거나 3은양의정수이다. 참 (T) (7) 이거나 3은양의정수가아니다. 참 (T) (8) 이거나 3은양의정수가아니다. 거짓 (F) 을 2 3, 를 3은양의정수가아니다. 라고하면논리합으로 로표기한다. 논리합은, 모두가거짓이면 은거짓이므로명제 와 가모두거짓이므로거짓 (F) 이된다. 5. 다음함의의역과대우를각각구하라. (1) 이면나는중국사람이아니다. 의역은 이고대우는 이다. 역 : 내가중국사람이아니면 2+2=4이다. 대우 : 내가중국사람이면 2+2 4이다. (2) 내가대통령이아니면나는걸어갈것이다. 역 : 내가걸어가면, 나는대통령이아니다. 대우 : 내가걸어가지않으면, 나는대통령이이다. (3) 시간이넉넉하고피곤하지않다면나는백화점에갈것이다. 역 : 내가백화점에간다면시간이넉넉하고피곤하지않은것이다. 대우 : 내가백화점에가지않는다면시간이넉넉하지않거나피곤한것이다. (4) 돈이많다면나는차를사고또집을살것이다. 라는함의에대하여, 이함의의역은 이고대우는 ~ ~ 이다. 역 ( ) : 내가차를사고또집을산다면돈이많은것이다. 대우 (~ ~ ) : 내가차를안사거나또집을안산다면돈이없는것이다. 다음의명제,, 에대하여답하라. : 나는이산수학을공부한다. : 나는영화를보러간다. : 나는기분이좋다. 6. 다음명제를명제변수와논리연결자로나타내라

3 (1) 나는기분이좋지않으면영화를보러간다. (2) 나는영화를보러가지않으며이산수학을공부한다. 나는영화를보러간다. 나는이산수학을공부한다. 라고하면, ~ (3) 나는영화를보러가면이산수학을공부하지않는다. ~ (4) 나는이산수학을공부하지않으면기분이좋지않다. 나는이산수학을공부하지않으면 -> ~ 기분이좋지않다. -> ~ 따라서답은 (~) (~ ) 가된다. 7. 다음명제에해당하는문장을작성하라. : 나는이산수학을공부한다. : 나는영화를보러간다. : 나는기분이좋다. (1) 나는이산수학을공부하지않고영화를보러간다. (2) 내기분이좋으면, 이산수학을공부하거나영화를보러간다. (3) 내기분이좋지않으면, 영화를보러가지않거나이산수학을공부한다. (4) 내가영화를보러가면서이산수학을공부하지않는것은내가기분이좋다는것과논리적으로같다. 또는내가영화를보러가면서이산수학을공부하지않는것은내가기분이좋을필요충분조건이다. 8. 진리표를이용하여항진명제와모순명제인것을찾아라. 명제변수의값에관계없이항상참인명제를항진명제 (tautology) 라하고항상거짓인명제를모순명제 (contradiction, absurdity) 라고한다. 어떤명제가항진명제인지모순명제인지는진리표를구하면알수있다. 진리표에서해당명제에대한진리값이명제변수에관계없이모두참이면항진명제이고반대로모두거짓이면모순명제이다. (1) T F F F 모순명제이다. (2) - 3 -

4 T T T T T F T T F T F T F F T T 항진명제이다. (3) T T T T T F T T F T F F F F T T (4) T T F T T F T T F T F T F F F F (5) T T T F T T F F F F F T F T T F F F F F (6) T T T T T F F T F T F T F F F T 항진명제이다. (7) T T T T T F F F F T F T F F F T 9. 표 1-8 에나와있는명제들이모두항진명제임을보여라. (8) ~( ) ~ ~ ~( ) ~ ~ ~ ~ ~( ) ~ ~ T T T F F F F T T F F T F T T T F T F T T F T T F F F T T T T T - 4 -

5 명제변수의값에관계없이항상참이되므로항진명제이다. 10. 표 1-9 에나와있는함의들이모두항진명제임을보여라. (8) (( ) ( )) ( ) ( ) ( ) (( ) ( )) ( ) T T T T T T T T T T F T F F F T T F T F T F T T T F F F T F F T F T T T T T T T F T F T F F T T F F T T T T T T F F F T T T T T 명제변수의값에관계없이항상참이되므로항진명제이다. 1.1 논리기출문제 [2008 기말 ] ( 해설 ) 항진명제란명제변수의값에관계없이항상참인명제를말한다. 11 페이지에있는 [ 표 1-8] 에는동치연결자가포함된중요한항진명제가나와있다. 1 의경우 : 표 6) 번째분배법칙에해당된다. 2 의경우 : 표 7) 번째이중부정에해당된다. 3 의경우 : 표 8) 번째드모르강법칙을나타내고자한것인데, 잘못된값이다. 드모르강법칙은괄호가없어지면서부정기호가각명제에붙어서논리합의경우는논리곱으로연산이바뀌며, 논리곱의경우는논리합으로연산이바뀌는법칙이다. 잘못된항진명제를수정하면 이된다. 4 의경우 : 표 9) 번째에해당된다. 그러므로정답은 3 번이다. [2009 출석시험대체 ] 26. 보기의문장이나식중에서명제인것을바르게묶은것은? - 5 -

6 < 보기 > ㄱ. 서울은한국의수도이다. ㄴ. 그사람은똑똑하다. ㄷ. 나는거짓말쟁이다. ㄹ. 1 ㄱ, ㄴ 2 ㄴ, ㄷ 3 ㄷ, ㄹ 4 ㄱ, ㄹ ( 해설 ) 명제란논리에서참이나거짓둘중의하나로확실하게판정할수있는평서문을말한다. 명제가갖는참혹은거짓의값을진리값이라한다. ᄀ의경우 : 논리값이참인평서문이므로명제라할수있다. ᄂ의경우 : 논리적으로판단을내릴수없는문장으로참이나거짓둘중의값을가진다고할수없으므로명제가될수없다. ᄃ의경우 : 패러독스 (paradox) 이므로명제라할수없다. 패러독스란참의값을부여하면거짓인것으로드러나고, 거짓의값을부여하면참인것으로드러나는문장을말한다. 패러독스는진리값을부여할수없으므로명제가아니다. ᄅ의경우 : 논리값이거짓인평서문이므로명제라할수있다. 그러므로정답은 4 번이다

7 1.2 술어논리연습문제 다음명제를적절한기호를써서나타내라. (1) 모든개는짖는다. 개 는짖는다 (2) 어떤동물은물속에서산다. 동물 는물속에서산다 (3) 모든정수 에대하여 이다. (4) 인정수 가존재한다. 3= 의조건을만족하는정수 0이존재한다. 그러므로 [3=] 로나타낼수있다. 2. 위의 1번문제 (3), (4) 의부정을부정연산자를쓰지않고나타내라. (3) 모든정수 에대하여 이다. (4) 인정수 가존재한다. 정수 0 이외의다른정수를대입할경우 3 조건을만족하지않으므로, 모든정수 가 3= 를만족하지않는다. 라고하면, [3 ] 로나타낼수있다. 3. 다음을부정연산자가없는형태로바꾸라. (1) (2) 4. 정수집합에대하여술어를다음과같이정의한다. 다음문장을논리기호로써나타내라. (1) 이면모든 에대하여 이다. 또는 (2) 이면 이고 이다. (3) 이면, 인 가존재한다. (4) 모든, 에대하여 인 가존재한다. 또는 5. 이성립함을 을이용하여증명하라. 에서 와 는임의의명제이므로이를각각 와 로대치하면다음과같다. 동치연산자양쪽의부정을취하면다음과같다

8 이를간단히하면 를얻는다. 6. 다음명제가참임을보여라. (2) 교재 20쪽식 (1.4) 에의해 따라서 교재 20쪽의식 (1.5) 에서와같이변수 는명제 와관계없는식이므로, 1.2 술어논리기출문제 [2006 동계계절 ] 1 P(x, y, z) 를 x+y=z로정의할때, P는술어이지만, P(1, 2, 3) 은명제이다. 2 P(x) 를참이도록하는 x가존재한다 는 x P(x) 로표현한다. 3 x y[x는 y의짝이다 ] 는 어떤 y는모든 x가 y의짝이다. 를의미한다. 4 ~ xp(x) x[~p(x)] ( 해설 ) 1의경우 : P(1, 2, 3) 이나 P(2, 3, 4) 는명제이다. P(1, 2, 3) 은참의진리값을가지는평서문이고, P(2, 3, 4) 는거짓의값을가지는평서문이기때문이다. 2의경우 : 이문장은그러한 x가존재하면참이고그렇지않으면거짓이므로명제이다. 기호 가 존재한다 (there exists)' 를의미하며 어떤 (for some)' 의의미로도쓸수있다. 즉, 위의문장은 어떤 x에대하여 P(x) 이다. 로도해설할수있다. 를존재한정자 (existential quantifier) 라고한다. 3의경우 : 모든 x에대하여 x와짝인 y가존재한다. 를의미한다. 짝이없는학생은없으므로이것은참인명제이다. 어떤 y는모든 x가 y의짝이다. 를의미하기위해서는 y x 와같은명제이어야한다. 4의경우 : 일반적으로 ~ xp(x) 는 P(x) 가거짓인 x가존재한다는것과같으므로전체한정자의부정은다음과같이바꾸어나타낼수있다. ~ xp(x) x[~p(x)] 그러므로정답은 3 번이다

9 [2009 출석시험대체 ] 27. 다음의문장을한정자를써서나타낸것이다. 올바르지않은것은? 문장 한정자 1 모든 에대하여 이다. 2 어떤 에대하여 이다. 3 명수가좋아하는사람이있다. 명수는 라는사람을좋아한다 4 어떤 는모든 가 의짝이다. 는 의짝이다 ( 해설 ) 1의경우 : 모든 y에대한것이므로 모든 (for all)' 을의미하는전체한정자 (universal quantifier) 를사용하여야한다. 는맞는표현이다. 2의경우 : 어떤 a에대한것이므로 어떤 (for some)' 의의미라도사용할수있는존재한정자 (existential quantifier) 를사용하여야한다. 는맞는표현이다. 3의경우 : 명수가모두를좋아하는것이아니라좋아하는어떤사람이존재하는것이므로전체한정자가아닌존재한정자를사용하여야한다. 명수는 라는사람을좋아한다이맞는표현이다. 4의경우 : 모든 x가 y의짝 이라고하였으므로 x에대해서는전체한정자를사용하여야하고, 앞에는 어떤 y 는이라고하였으므로앞에있는 y에대해서는존재한정자를사용하여야한다. 는 의짝이다 는맞는표현이다. 그러므로정답은 3 번이다

10 1.3 추론방법연습문제 다음주장이올바른지밝혀라. (1) 유도 근거전제전제 1과 2에분리법적용 3에간략법적용전제 4와 5에분리법적용 (2) 유도 근거전제전제 1과 2에분리법적용 (3) 유도 근거전제가정 1과 2에분리법적용 3에간략법적용전제 4와 5에분리법적용 (4)

11 유도 1., ~ ~ 근거추가전제전제 2와 3에분리법적용전제전제 5와 6에이접 3단논법적용 4와 7로부터 (5) 유도 ~ 3. ~ ~ 6. ~ 7. ~( ) 8. ( ) 9. ~ 근거전제전제 1과 2에분리법적용전제전제 4와 5에제거법적용 3과 6으로부터전제 7과 8로부터 2. 다음문항에주어지는전제들로부터도출할수있는결론들을나열하라. (1) 환경보호는후손을위하여좋은일이다. 후손을위하여좋은것은나에게도좋다. 환경보호는자원을재활용하면된다. 1 환경보호는나에게도좋다. 2 자원의재활용은후손을위하여좋다. 3 자원의재활용은나에게도좋다. (2) 이산수학을공부하면즐겁다. 즐거우면날씨가맑다. 지금날씨가흐리다. : 이산수학을공부한다. : 나는즐겁다. : 날씨가맑다

12 유도 ~ 7. ~ 근거전제전제가언적 3단논법전제동치전제 5와 3에제거법 결론 : 이산수학을공부하지않는다. (3) 모든짝수는 2의배수다. 10은짝수이고 7은홀수다. 10은 2의배수다. (4) 영희가양심이있다면그는빚을갚는다. 영희는빚을갚지않았다. : 영희가양심이있다. : 영희는빚을갚는다. 유도 ~ 3. ~ 4. ~ 5. ~ 근거전제전제 1과 2에제거법전제동치 결론 : 영희는양심이없다. 3. 다음함의에대하여생각해보자. (1) 이것이잘못된것임을보여라. 를 는짝수다., 를 는홀수다. 라고하자. 함의의후건을참으로하는, 즉홀수이면서짝수인수는존재하지않으므로이함의는거짓이다. (2) 위함의를다음과같이증명했다고하자. 이증명과정에서무엇이잘못된것인지를밝혀라. 은참이지만 은항상참이라고할수없다. 즉, 이라고해서 인것은아니다. 4. 다음중올바른주장인것을찾아라. 올바른주장에대하여는논증과정을구하고, 잘못 된주장은어디에서오류가발생했는지밝혀라

13 (1) 오늘이일요일이면나는영희나철수를만난다. 영희가바쁘면영희를만날수없다. 오늘은일요일이고영희는바쁘다. 따라서나는철수를만난다. P, Q, R, S를다음과같다고하자. P : 오늘은일요일이다. Q : 나는영희를만난다. R : 나는철수를만난다. S : 영희는바쁘다. 문제의주장을다음과같이나타낼수있다. 이것에대하여논증을해본다. 유도 근거전제전제 1과 2에분리법적용전제전제 4와 5에분리법적용 3과 6에이접 3단논법적용 1.3 추론방법기출문제 [2008 출석시험대체 ] M(x) : x는남자이다. W(x) : x는여자이다. A(x) : x는성인이다. V(x) : x는투표권이있다. 1 남자가존재한다면여자도존재한다. : xm(x) xw(x) 2 투표권이있는모든사람은성인이다. : x[v(x) A(x)] 3 성인인모든남자는투표권이있다. : x[(a(x) M(x)) V(x)] 4 모든사람은남자이거나여자이다 : x[m(x) W(x)]

14 ( 해설 ) 1 의경우 : 존재한정자와함의 ( ) 를사용한것으로 만약 P 이면 Q 이다. 가성립하는명제이다. 남자가존재한다는것은존재한정자를사용하여 xm(x) 라고표현할수있고, 여자가존재한다는것은 xw(x) 라고표현할수있다. 2 의경우 : 투표권이있는성인을표현하면 V(x) A(x) 이된다. 문제에서는모든사람이성인이라고하였으므로전체한정자를추가하여표현한다. x[v(x) A(x)] 은맞는표현이다. 3 의경우 : 성인중에서남자를찾아야하므로논리곱연산자를사용하여 A(x) M(x) 과같이표현한다. 찾은남자들이투표권이있으므로 (A(x) M(x)) V(x) 과같이명제를표현할수있다. 여기서도모든남자에관한명제이므로전체한정자를추가하여준다. x[(a(x) M(x)) V(x)] 은맞는표현이다. 4 의경우 : 남자이거나여자라고하였으므로논리합연산자를사용하여 M(x) W(x) 과같이표현한다. 다음으로모든사람에관한것이므로존재한정자가아닌전체한정자를사용하여야한다. 그러므로 x[m(x) W(x)] 이맞는표현이다. 그러므로정답은 4 번이다. [2009 기말 ] M(x) : x 는사람이다. D(x) : x 는박사이다. W(x) : x 는여자이다. T(x) : x 는조교이다. 1 사람인박사가존재한다 : 2 모두가여자인것은아니다 : 3 조교가아닌사람은박사이다 : 4 박사인모든여자는조교이다 :

15 ( 해설 ) 1 의경우 : 사람이면서박사가존재하는것이므로논리곱연산자와존재한정자를사용한다. 는맞는표현이다. 2 의경우 : 대상이모두가되므로존재한정자가아닌전체한정자를사용하여야한다. 즉, 이맞는표현이다. 3 의경우 : 조교가아닌사람은박사라고하였으므로 과같이표현된다. 이명제는어떤특정이아니라모든것에해당되므로전체한정자를추가한다. 이맞는표현이다. 4 의경우 : 박사이면서여자이어야하므로논리곱연산자를사용합니다. 과같이표현할수있다. 박사이면서모든여자가조교라고하였으므로전체한정자를추가하면, 이맞는표현이다. 그러므로정답은 1 번이다

16 1.4 증명방법연습문제 다음함의의역과대우를각각구하라. 의역은 이고대우는 이다. (1) 이면나는중국사람이아니다. 역 : 내가중국사람이아니면 2+2=4이다. 대우 : 내가중국사람이면 2+2 4이다. (3) 시간이넉넉하고피곤하지않다면나는백화점에갈것이다. 역 : 내가백화점에간다면시간이넉넉하고피곤하지않은것이다. 대우 : 내가백화점에가지않는다면시간이넉넉하지않거나피곤한것이다. 2. 다음명제를반증법으로증명하라. 명제의반대예를찾아명제가거짓임을보이는증명방법인반증법에대한문제이다. 하나의반대예를제시하면충분하다. (1) 4개의직각을갖는도형은정사각형이다. 직사각형도직각이 4개이다. (2) 양이아닌실수는음수이다. 0 (3) 빨간머리의사람은모두키가크거나눈이파랗다. 실제로그렇지않은사람을우리가쉽게찾을수있다. (4) 빨간머리의사람은모두키가크고눈이파랗다. 실제로그렇지않은사람을우리가쉽게찾을수있다. 3. 홀수의곱은홀수임을직접증명법으로증명하라. 두홀수를 이라하자. 그러면이둘의곱은다음과같다. 그러므로두홀수의곱도홀수이다. 4. 홀수의곱은홀수임을모순증명법으로증명하라. 두수 p, q가홀수라는가설과곱 pq가짝수라는결론이모순이됨을보인다. 곱 pq가짝수라면 pq는 2로나누어떨어져야한다. 이것은 p나 q 중하나이상이 2의배수가되어야함을뜻한다. 이것은 p, q가홀수라는가설과모순이되므로홀수의곱은짝수가될수없다. 5. 가양수이면 도양수임을대우증명법으로증명하라. x+1이양수가아니면 x는양수가아님을증명하면된다. x+1이양수가아니면 x+1 0 이므로 x -1 로된다. 따라서 x는양수가아니다

17 6. 가양수이면 일필요충분조건이 임을증명하라. ⅰ) 가정으로부터 를 라하면 라할수있다. 양변을제곱하면 이고 는양수이므로 은참이다. ⅱ) 를대우증명법을이용하여증명하면, 을증명한다. 이므로 (는양수 ) 라할수있다. 이되고, 와 는모두양수이므로 이다. 따라서 는참이다. 7. 양의정수 에대하여 이 3 의배수임을증명하라. 수학적귀납법으로증명한다. 1) 기본단계 : 기본단계 : n=1 일경우 이므로 3 의배수이다. 2) 귀납단계 : 귀납단계 : 이 3 의배수라고가정하면 도 3 의배수로됨 을보이면된다. 는정수 귀납가설에 의하여 즉 도 3 의배수이므로귀납단계도참이다. 기본단계와귀납단계가참이므로수학적귀납법에의해증명되었다 8. 양의정수 에대하여다음이성립함을증명하라. 기본단계인 은 = = 2 이므로명백히참이다. 다음 가참임을가정하고 인 (4k-2)+4( )-2=2 이참임을보인다. 의등호왼쪽항으로부터귀납가설인 를써서오른쪽항을다음과같이유도할수있다 (4k-2)+4( )-2= +4( )-2 = +4+2 = = 이므로성립한다 인양의정수 에대하여 임을증명하라

18 ⅰ) 인경우, (4): 이므로 (4) 는참이다. ⅱ) 인정수에대해 (): 임을가정하고, 임을 보인다. 이다. 양변을 2 로나누면, 따라서, 은참이다. 이고 이므로 이다. 10. 수학적귀납법에의한다음의증명에서틀린점을지적하라. 양의정수 에대하여 =+1 임을증명하려고한다. (k) 가참이라가정하면 k=k+1이다. 식의양변에 1을더하면 k+1=k+2 이므로 (k+1) 이참이다. 그러므로성립한다. 기본단계인 을증명하지않았다. 일때, 1=1+1 이다. 따라서, (k) 가참이라가정할수없다. 12. 양의정수 에대하여다음이성립함을수학적귀납법을써서증명하라 = 기본단계인 은 1 = 다음 가참임을가정하고 인 =1 이므로명백히참이다 = + 이참임을보인다. 의등호왼쪽항으로부터귀납가설인 를써서오른쪽항을다음과같이 유도할수있다 = + = + =

19 = = = = 1.4 증명방법기출문제 [2006 동계계절 ] 123 양의정수 n 에대하여 n 이홀수일필요충분조건은 5n+6 이홀수로되는것임을증명하라. [ 풀이 ] 먼저 n 이 ( 1 ) 이면 5n+6 이홀수임을보인다. n 이 ( 1 ) 라면 k 를양의정수라할때 ( 2 ) 로나타낼수있다. 그렇다면 5n+6 = 5(2k-1)+6 = 10k+1 로되어 5n+6 도홀수이다. 다음은그 ( 3 ) 을증명한다. 5n+6 이홀수라면 5n 은홀수이어야한다. 또한홀수 홀수 = 홀수, 홀수 짝수 = 짝수이므로 5n 이홀수가되려면 n 이홀수이어야한다. 따라서그 ( 3 ) 도성립한다. 1 홀수, n=2k-1, 역 3 짝수, n=2k-1, 대우 2 홀수, n=2k, 역 4 짝수, n=2k, 대우 ( 해설 ) 교재 34 페이지예제 1.28 에서증명단계를확인할수있다. 정리가 P 일필요충분조건은 Q 이다. 의형태로나타나는것도많다. 이명제는쌍조건 P Q 에해당한다. P Q 를증명하려면 P Q 가참임과동시에 Q P 도참임을보이면된다. 그러므로정답은 1 번이다. [2009 출석시험대체 ] 28. 다음의증명을보고증명법의종류와 ( ㄱ ), ( ㄴ ) 에알맞은것을고르시오

20 < 증명 > 인정수 에대하여 임을증명하라. 풀이 기본단계는 가참임을보이면된다. 는 이므로참이다. 다음 에대하여 가참임을가정하고 ( ㄱ ) 이참임을보인다. ( ㄴ ) 그러므로모든 에대하여 이성립한다 증명법 ( ㄱ ) ( ㄴ ) 1 대우증명법 2 대우증명법 3 수학적귀납법 4 수학적귀납법 ( 해설 ) 교재 33 페이지예제 1.26 에서증명단계를확인할수있다. 문제에서제시하는증명은수학적귀납법으로 i 보다큰모든정수 n 에대하여 이성립한다. 와같은형태의정리를증명하는데적절한것으로서기본단계와귀납단계가참임을보임에의하여증명하는방법이다. 그러므로정답은 4 번이다

21 1.5 집합연습문제 전체집합 ={1,2,,10} 이고 ={1,4,7,10}, ={1,2,3,4,5}, ={2,4,6,8} 일때다음집 합의원소를열거하라. (1) = {1,2,3,4,5,7,10} (2) = {2,4} (3) = {7,10} (4) = {2,3,5} (5) = U={1,2,,10} 이므로 {2,3,5,6,8,9} (6) - = {1,3,5,7,9,10} (7) = (8) = (9) = (10) = (11) = (12) ( ) ={1,4} (13) = {6,8} (14) ( )- = {1} (15) = {2,3,4,5,6,7,8,9,10} (16) ( )-( -) = {1,2,3,4,5,7,10} ( )={1,2,3,4,5,7,10} ( -)={6,8} 이므로, ( )-( -)={1,2,3,4,5,7,10} 이다. 2. ={1,2}, ={a,b,c} 일때다음각집합의원소를열거하고카디낼리티를각각구하여라 (1) = {(1,a), (1,b), (1,c), (2,a), (2,b), (2,c)}, 카디낼리티는 6이다. (2) = {(a,1), (a,2), (b,1), (b,2), (c,1), (c,2)}, 카디낼리티는 6이다. (3) = {(1,1), (1,2), (2,1), (2,2)}, 카디낼리티는 4이다. (4) = {(a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (b,b)}, 카디낼리티는 9이다. 3. ={1,2}, ={a}, ={,} 일때다음집합의원소와카디낼리티를각각구하라. (1) = {(1,a,α), (1,a,β), (2,a,α), (2,a,β)}, 카디낼리티 : = 4 (2) = {(1,a,a), (2,a,a)}, 카디낼리티 : = 2 (3) = {(a,1,a,),(a,1,a,),(a,2,a,),(a,2,a,)} 카디낼리티 : = 4 4. 다음각집합에대하여모든분할을구하여라

22 (1) {1} = {{1}} (2) {1, 2} = {{1,2}}, {{1},{2}} (3) {a, b, c} = {{a,b,c}}, {{a,b},{c}}, {{a,c},{b}}, {{b,c},{a}}, {{a},{b},{c}} (4) {a, b, c, d} = {{a,b,c,d}}, {{a,b,c},{d}}, {{a,b,d},{c}}, {{a,c,d},{b}}, {{b,c,d},{a}}, {{a,b},{c,d}}, {{a,c},{b,d}}, {{a,d},{b,c}}, {{a},{b},{c},{d}} 5. 다음이참인지거짓인지를밝혀라. (1) 참 (2) 거짓 (3) 참 (4) 참 6. ({a,b,c,d}) 의원소를나열하고 {a,b,c,d} 의진부분집합에해당하는것을지적하라. 또 ({a,b,c,d}) 의카디낼리티를구하여라. ({a,b,c,d}) 의원소는,{a},{b},{c},{d},{a,b},{a,c},{a,d},{b,c},{b,d},{c,d},{a,b,c}, {a,b,d},{a,c,d},{b,c,d},{a,b,c,d} 이다. {a,b,c,d} 를제외한모든집합은진부분집합이다. 카디넬리티는 이므로 2 =16이다. 7. 의원소가 10개이면 의원소의개수는얼마인가? 또 의진부분집합은몇개인가? 에서 를제외한모든것이진부분집합이므로 개다. 8., 가공집합이아니면서 = 가성립한다면 와 는어떠한집합인가? 9. A={1,2,3,4,5}, B={1,3,5} 라고하자. B 와서로소인 A 의모든부분집합을열거하라., {2}, {4}, {2,4} 10. 집합,, 가있을때 와 가서로소이면 와 도서로소임을벤도형으 로보여라. 다음의벤도형에서보는바와같이 이므로서로소이다. A A C C B C B

23 11. 에대하여정리 1.3-(1) 과유사한공식을구하라. 12. 가원소인집합을구하라. 공집합을원소로하는집합으로서공집합과는다르다. 13. 이라하자. 다음집합을구하라. (1) 이들중 를부분집합으로가지는집합 A, B, C (2) 이들중 를원소로하는집합 B, C 14. 는양의정수집합이다. 2 에대하여 ={ 2, } 라정의하면 - 는무엇에해당하는가? 양의정수중 1과자기자신이외의약수를갖지않는수의집합 15. 다음이성립함을보여라. (1) ( 드모르강의법칙 ) ( 교환법칙 ) (2) ( 드모르강의법칙 ) ( 드모르강의법칙 ) ( 보법칙 ) ( 교환법칙 ) 16. 국어수강생은 25 명이고, 이산수학수강생은 27 명이다. 또두과목모두를수강하는 학생은 15 명이다. 이두과목의수강생을모두합치면몇명인가? 국어수강생 (25 명 ) + 이산수학수강생 (27 명 ) - 모두수강하는학생 (15 명 ) = 37 명 1.5 집합기출문제 [2009 기말 ] a b c d e f 1 abcdef 2 a bc de ff a

24 3 a b cd f e 4 a b c d e f ( 해설 ) 집합 A 의분할 (partition) 란 A 를겹치지않게나눈부분집합들의집합을말한다. 즉, 이 A 의분할이면 1 에대하여 이며 ( 공집합이아니어야하며 ) 2 에대하여 이고 ( 쌍별로서로소여야하며 ) 3 ( 모두합할경우원래의집합으로돌아가야한다.) 이다. 보기 2 의경우는 f 와 a 의원소가중복됨으로서로소에해당되지않아서분할이될수없는경우가된다. 그러므로정답은 2 번이다. [2009 기말 ] ( 해설 ) 대등차집합 그러므로정답은 4 번이다

25 제 2 장정수및행렬 2.1 정수나눗셈과소수연습문제 다음을소인수분해하라. (1) 80 (2) 1024 (3) 다음이소수임을보여라. (1) 101 = 보다작으며 11보다작은소수로는 2,3,5,7이다. 이들은모두 101을정제할수없으므로 101은소수이다. (2) 641 = 보다작으며 26보다작은소수로는 2,3,5,7,11,13,17,19,23이다. 이들은모두 641을정제할수없으므로 641은소수이다. (3) 89 = 보다작으며 10보다작은소수로는 2,3,5,7이다. 이들은모두 89를정제할수없으므로 89는소수이다. 4. 다음나눗셈의몫과나머지를구하라. (1) 20/3 몫 6, 나머지 2 (2) -20/3 몫 -7, 나머지 1 5. 다음의각쌍에대한최대공약수와최소공배수를각각구하라. (1) 2700, gcd 900, lcm (2) 0, 10 gcd 10, lcm 정의할수없음 (3) 100, 100 gcd 100, lcm

26 6. 10 보다작은양의정수중에서 10 과서로소인것을모두열거하라. 1, 3, 7, 9 7. 다음을계산하라. (1) 120 mod 7 1 (2) 120 mod (3) -120 mod 7 6 (4) -120 mod 정리 2.6을증명하라. 정리 2.6 에대하여 gcd 이다. ⅰ)와는 를공약수로가지므로 이라할수있고, 이라할수있다. ⅱ) ⅰ) 에서 과 은서로소이다. 따라서, ⅰ),ⅱ) 로부터 이다. 9. 법 7 에대하여 4 와합동인 4 보다큰수를작은것부터세개만보여라. 11, 18, 유클리드호제법으로문제 5의정수쌍에대한최대공약수를구하라. (1) 2700, = = = 따라서, 최대공약수는 900이다. (2) 0,10 0= 따라서, 최대공약수는 10 이다. (3) 100, = 따라서, 최대공약수는 100 이다

27 11. a, b, c, d가양의정수일때다음을증명하라. (1) 이고 이면 이다 이고 이면, 인양의정수 이존재한다. 이제 는 이므로 이다. 12. 양의정수 a, b, c, d 에대하여다음을증명하라. (1) gcd 이면 gcd 이다 gcd 이라고하자. 그러면, 이된다. 여기서 은양의 정수이다. 따라서, 으로되어 gcd 이다. 이것은 gcd 라는 것과모순이된다. 13. a, b, c는양의정수이고 a와 b는서로소라고하자. 이고 이면 임을증명하라. 이고 이다. 에서 이고 이다. 와는서로소이므로 이고 이다. 따라서, 이고 는참이다. 14. 이라는사실을이용하여 이소수이면 는소수임을증명하라. 모순증명법으로증명한다. 가소수가아니라고하면 인양의정수 이존재한다. 그러면 이되는데, 이것은문제에주어진것과같이두항의곱으로나타낼수있으므로 이소수가아닌것이된다. 따라서문제의전제와모순이된다. 15. a와 b는정수이고, n과 m은 1보다큰정수로서 이라고하자. mod 이면 mod 임을증명하라. 또이것의역은성립하는지알아보자. 이므로, 이다 식 1과 2에 를대입하면 과 2 에서 와를 으로나누었을때나머지는모두 이다. 따라서, 은참이다

28 16. a, b, n, m은정수이고 이라고할때다음을증명하라. (1) mod mod 이므로 이고 이다. 이고 이다. 이고 이므로 은참이다. 17. (1) mod 의값과 mod mod mod 의값을비교해보라. mod mod (2) 정수 m, n, k 에대하여 mod mod mod mod 임을증명하라. mod mod mod mod 나 모두정수라는사실로부터다음과같이증명된다. mod mod mod mod mod mod 2.1 정수나눗셈과소수기출문제 [2008 출석시험대체 ] 1 a b이고모든 x, y Z에대하여 a bx이다 2 a b이고 b c이면 a c이다. 3 a b이고 b a이면 a=b이거나 a=-b이다. 4 a b이고 a c이면, 모든 x, y Z에대하여 b (ax+cy) 이다. ( 해설 ) 이고 일경우에, 으로하는정수 이존재하면 는 를정제 ( 整除, divisivility) 한다 라고한다. 이를 로표기한다. 정제에관한몇가지성질은정리 2.1 에서확인할수있다. 1 의경우 : 정리 (4) 에해당된다. 2 의경우 : 정리 (2) 에해당된다. 3 의경우 : 정리 (3) 에해당된다. 4 의경우 : 정리 (5) 와관련된내용으로잘못되었다. 이고 이므로 으로나타낼수있다. 그러면 이므로 이다. 즉, 이고 이면모든 에대하여 이다. 가맞다. 그러므로정답은 4 번이다. [2009 출석시험대체 ]

29 ( 해설 ) 나눗셈알고리즘에서나머지는 0 보다큰정수이어야한다. -36=5(-8)+4 몫은 (-8) 이되고나머지는 (4) 가된다. 그러므로정답은 4 번이다

30 2.2 행렬연습문제 행렬,, 일때, 를각각구하 라., A+C는 A와 C의행렬크기가서로다르므로정의되지않는다. 2. 일때, x, y, z를각각구하라. 양변을각각하나의행렬로만들면 이다. 따라서 이어야한다. 이들연립방정식을풀면 이다. 3. 행렬, 일때, 를만족하는실수 c, k를각각 구하라. 이므로 이다. 4. 행렬,, 일때, AB와 BA를각각구하라. 5. 행렬 A, B, C가다음과같을때, 행렬의곱 (A+B)C와 AC+BC를구해서 (A+B)C=AC+BC임을확인하라.,,,,, 따라서 는성립한다. 6. 행렬,, 일때, 4A-2(B-C) 를계산하라

31 7. 행렬, 일때, 를만족시키는행렬 X를구하라. 8. 행렬,, 일때, 를만족시키는실수 x, y의 값을각각구하라. 따라서 이다. 이연립방정식을풀면 이다. 9. 임의의 행렬 A에대하여 AB=5A인 행렬 B를구하라. 라하자. 이며, 이를계산하면 이다. 따라서 이어야한다. 각식을 a, b, c, d에대하여정리하면 가되며, 이들은임의의 a, b, c, d에대한항등식이므로 이어야한다. 그러므로 이다. 10. 행렬, 일때, 가성립하기위한 x, y의값을각각구하 라. 이고, 이다. 따라서 이다

32 이연립방정식을풀면 이다. 11. 행렬 일때, 멱행렬 과전치행렬 를각각구하라. 12., 일때. 및 를각각구하라., 는정의되지않는다. 13. 행렬 일때, 양의정수 에대하여 을구하는공식을구하라. 14. 불행렬 A, B 가다음과같을때, 와 를각각구하라.,, 15. 불행렬 A, B가다음과같을때, 와 를각각구하라.,, 는정의되지않는다. 16. 불행렬 A, B 가다음과같을때, 와 를각각구하라

33 , 는정의되지않는다. 이다. 17. 불행렬 A, B 가다음과같을때, 를구하라., 18. 불행렬 A 가다음과같을때, 모든양의정수 n 에대하여불멱행렬 을구하라., 따라서 인모든양의정수에대하여 임을알수있다. 2.2 행렬기출문제 [2009 출석시험대체 ]

34 ( 해설 ) 행렬 의멱행렬 (power of matrix) 는 를 번곱한것이다. 단, 이다. 를 번곱한것 그러므로정답은 1 번이다. [2009 기말 ] 1 = 2 = 3 = 4 = ( 해설 ) 1의경우 : 2의경우 : 3의경우 : 4의경우 : 그러므로정답은 1 번이다

35 제 3 장관계와함수 3.1 관계연습문제 다음관계를순서쌍의집합과표로각각나타내라. 에서의관계 로서 이면 이다. 순서쌍의집합 : 2. 다음관계를그래프와행렬로각각나타내라. (1) 에서 로의관계 (2) 에서 3. 앞의문제 1, 2의역관계를각각구하라. 문제 1의역관계 : 문제 2-(1) 의역관계 : 문제 2-(2) 의역관계 : 4., 일때다음에주어진각각의조건을만족하는순서쌍 로각관계가구성된다. 각관계를순서쌍의집합으로나타내라. (1) (2) (3) (4) gcd

36 5. 위의문제 4 의각관계를그래프로나타내라. (1) 6. 위의문제 4 의각관계를행렬로나타내라. (2) 각행은 1, 2, 3, 4 가순서대로대응하고, 각열은 1, 2, 3, 4, 5 가순서대로대응하 는것으로하면다음과같다. 7. 다음관계는양의정수집합에서정의되었다. 이관계들의성질 ( 반사성, 대칭성, 추이성, 반대칭성, 비반사성 ) 을밝혀라. (1) 이면 반대칭 (2) 이면 비반사, 반대칭, 추이 (3) 이면 반사, 반대칭, 추이 (4) 이면 비반사, 대칭 (5) gcd 이면 대칭 (6) mod 이면 반사, 대칭, 추이 8. 는공집합이아니라고하자. 의멱집합 에서의관계 를 이면 인것으로정의하자. 추이성, 반사성, 대칭성, 반대칭성중이관계가가지는성질은무엇인가? 모든 에대하여 이므로반사적이다. 모든 에대하여 이면 인한 이므로반대칭적이다. 또모든 에대하여 이고 이면 이므로추이적이다. 9. 집합 에서의관계 가대칭적이고추이적이면반사적이라는다음의논중에서잘못된 점은무엇인가?

37 대칭성에의하여 이다. 이는 이면서 임을의미하므로추이성에의해서 이어야한다. 따라서 는반사적이다. 모든 에대하여 인 가존재하는것은아니므로모든 에대하여 가아니다. 10. 와 를집합 에서의관계라하자. 다음의문장들이사실인지아닌지를밝혀라. 만약거짓인경우에는예를하나제시하라. (1) 가반사적이면 도반사적이다. 옳다. (2) 가반사적이면 도반사적이다. 옳다. (3) 가반사적이면 도반사적이다. 옳다. (4) 가반사적이면 도반사적이다. 옳다. (5) 가추이적이면 도추이적이다. 그르다., 인경우 (7) 가추이적이면 도추이적이다. 그르다. 이면추이적이다. 그런데 이고 이 의원소가아니므로추이적이아니다. (8) 가추이적이면 도추이적이다. 그르다., 인경우 (9) 가대칭적이면 도대칭적이다. 옳다. (10) 가대칭적이면 도대칭적이다. 옳다. (11) 가대칭적이면 도대칭적이다. 옳다. (12) 가대칭적이면 도대칭적이다. 그르다., 인경우 11. 관계 과 에대하여 와 을각각구하라. 3.1 관계기출문제

38 [2009 기말 ] 반사적 : 모든 x A 에대하여 xrx 가성립하는경우관계 R 는반사적이다. 대칭적 : 모든 x,y A 에대하여 xry yrx 가성립하는경우관계 R 는대칭적이다. 추이적 : 모든 x,y,z A 에대하여 (xry yrz) xrz 가성립하는경우관계 R 는추이적이다. 반대칭적 : 모든 x,y A 에대하여 (xry yrx) (x=y) 가성립하는경우관계 R 는반대칭적이다. 비반사적 : 모든 x A 에대하여 (x,x) R 가성립하는경우관계 R 는비반사적이다. 1 관계 은반대칭적이지않다. 2 관계 은대칭적이지않다. 3 관계 은반사적이다. 4 관계 은추이적이다. ( 해설 ) 1 의경우 : 에대하여 가성립하는경우이므로반대칭적이다. 2 의경우 : 에대하여 가성립하므로대칭적이다. 3 의경우 : 반사적이되기위해서는 b, c, d 에대하여도 가성립해야하는데, 보기에서는 만포함되어있으므로반사적이지않다. 도포함되어야한다. 4 의경우 : 추이성은 이고 이면, 로되어야함을의미한다. 에대하여 가성립한다. 여기서는 만존재하므로모두추이적이라할수있다. 그러므로정답은 4 번이다. [2009 기말 ] 1 관계 은반대칭적이지않다. 2 관계 은대칭적이지않다. 3 관계 은반사적이다. 4 관계 은추이적이다

39 ( 해설 ) 공관계는모든 에대하여 이다. 즉, 대칭적이되기위한정의와반대칭적이되기위한정의의함의전건이항상거짓이므로가능한모든 에대하여함의가모두참이된다. 따라서 은대칭적임과동시에반대칭적이라할수있다. 그러므로 1과 2는잘못되었다. 또한 에대하여 가 에속하지않으므로반사적이지않다. 그러므로 3번보기도잘못되었다. 공관계에서의추이성은조건의함의전건을만족하는것이하나도없어서추이성도함께갖는다고할수있다. 그러므로정답은 4 번이다

40 3.2 반순서와동치관계연습문제 다음과같은 에서의관계 가반순서관계임을보이고, 하세도표를그려라. (1) 반사성, 반대칭성, 추이성을조사한다. 모든 에대하여 이므로반사적이다. 또한 에대하여 이없고, 에대하여 이없고, 마찬가지로 에대하여원소의순서를거꾸로한순서쌍이관계에없으므로반대칭적이다. 한편 에대하여 가있고, 에대하여 가관계에있으므로추이적이다. 하세도표를다음과같다. (2) (1) 과유사하다. 하세도표는다음과같다. 2. 가포셋임을보여라. 에서 가반순서관계임을보이면된다. 모든 에대하여 이므로반사적이다. 에대하여 이므로반대칭적이다. 또한 에대하여 이므로추이적이다. 따라서 는포셋이다. 3. 포셋 에서비교가능한원소쌍과비교불가능한원소쌍의예를각각세개만열거하라. 비교가능한원소쌍의예 : 1과 2, 2와 4, 3과 6 비교불가능한원소쌍의예 : 2와 3, 3과 4, 4와 5 4. 관계의그래프에서그관계가반순서관계임을나타내주는특징으로는어떠한것들이있는가? 또그그래프가동치관계에대한것이라면특징으로는어떠한것들이있는가? 반순서관계의그래프 : 모든점마다루프가존재해야하며, 서로다른점을잇는선이있으면그반대방향의선은존재하지않아야한다. 또한 에서 로가는선과 에서 로가는선이있으면 에서 로바로가는선도존재해야한다. 동치관계의그래프 : 모든점마다루프가존재해야하며, 서로다른점을잇는선이있

41 으면그반대방향의선도함께존재해야한다. 또한 에서 로가는선과 에서 로가 는선이있으면 에서 로바로가는선도존재해야한다. 5. 다음은 에서의관계이다. 반순서관계인것을골라라. 또그것에대한하세도표를구하라. (1) 관계를갖는것이없으므로반순서관계가아니다. (2) {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)} 은반사적, 대칭적, 추이적이므로반순서관계가아니다. (3) (1,2), (2,1) 이대칭적이므로반순서관계가아니다. (4) 추이적이나반사적, 반대칭적이지않으므로반순서관계가아니다. (5) (1,2),(2,3) 이나 (1,3) 이존재하지않아추이적이지않다. 그러므로반순서관계가아니다. (6) 반순서관계이다. 하세도표는다음과같이단지세점으로만이루어진다. 6. 가포셋이면 도포셋임을보여라. 이포셋이면 에서 는반사성, 반대칭성, 추이성을갖는다. 가반사적이므로모든 에대하여 이다. 인 이면 가반대칭적이므로 이고 이며 이다. 그러므로 는반대칭적이다. 또한 이고 이면 이므로 이고 이면 로되어 도추이적이다. 이상과같이 도반사성, 반대칭성, 추이성을가지므로 는반순서관계이며따라서 는포셋이다. 7. 라고하자. 라는관계에대하여 에서의사전식순서상 보 다작은것을모두나열하라. 8. 에서의다음의관계가동치관계인지를밝히고동치관계이면동치류를구하라. 단, 이다. (1) 동치관계

42 (2) 동치관계아님 (3) 동치관계 (4) 동치관계 9. A를영어의모든단어의집합이라하자. 에서의관계 가 와 의문자수가같으면 인것으로정의한다. 이 가동치관계임을보이고 computer' 의동치류를구하라. 모든단어는자기자신과문자수가같으므로 는반사적이다. 가 와문자수가같다면 가 와문자수가같으므로 는대칭적이다. 또한 가 와문자수가같고, 가 와문자수가같다면 는 와문자수가같으므로추이적이다. 이와같이 는반사적이고대칭적이며추이적이므로동치관계이다. [computer] = { 여덟문자로구성되는모든단어 } 이다. 10. 다음의분할에해당하는동치관계와동치류 [1], [2], [3], [4] 를각각구하라. (1) (2) (3) 11. 를 8비트이진수집합이라하자. 의원소 과 의처음 4비트가같으면 인관계 에대하여 가동치관계임을보여라. 또상이한동치류들은어떠한것들이있는가? 모든 8비트이진수는자기자신과처음 4비트가같으므로반사적이다. 두 8비트이진수, 에대하여 이 와처음 4비트가같다면 는 과처음 4비트가같으므로대칭적이다. 또 이 와첫 4비트가같고 가 와첫 4비트가같다면당연히 은 와첫 4비트가같아야하므로추이적이다. 따라서동치관계이다. 상이한동치류들은다음과같다

43 12. 과 를 에서의동치관계라하자. (1) 가 에서의동치관계임을보여라. 가 에서동치관계이므로 역시반사성, 대칭성, 추이성을모두만족. 그러므로 도 에서의동치관계이다. (2) 의동치류를 의동치류와 의동치류로나타내라. 을 의동치류, 를 의동치류라할때, 의동치류 이다. 3.2 반순서와동치관계기출문제 [2009 출석시험대체 ] c b d a

44 ( 해설 ) 집합 에서의관계 가반사적이고반대칭적이며추이적이라면 는반순서관계이다. 1의경우 : 와 에대하여 이므로추이적이지않다. 그러므로반순서관계라할수없다. 2의경우 : 와 에대하여 이므로추이적이지않다. 그러므로반순서관계라할수없다. 3의경우 : 이므로반사적이라할수없다. 그러므로반순서관계도아니다. 4의경우 : 가모두관계 에있으므로반사적이다. 또한자기자신으로이루어지는쌍외에는 와 가모두함께 에있는쌍이존재하지않으므로반대칭적이다. 한편추이성조사대상이될만한순서쌍을골라보면 와 뿐이다. 이에대하여 이므로 는추이적이다. 이상과같이 는반사적, 반대칭적, 추이적이므로 는반순서관계이다. 반순서관계를하세도표로나타내기위해서는우선, 관계그래프를그린다. (a) 가이관계의그래프이다. 다음이그래프에서루프를제거하고화살표가모두위로향하도록그린다. (b) 가그결과이다. 이제여기서추이조건의후건에해당하는화살표를골라보면 a에서 c로가는화살표하나가있다. 이를제거하고화살표를단순한선으로바꾸면 (c) 가된다. 이것이구하고자하는하세도표이다. 그러므로정답은 4 번이다. [2008 출석시험대체 ] 1 R={(a, a), (a, b), (a, c), (b, b), (b, c)} 2 R={(a, a), (a, b), (b, b), (b, c), (c, c)} 3 R={(a, a), (b,b), (a, c), (c, c), (a, b)} 4 R={(a, a), (a, b), (a, c), (b, b), (b, c), (c, c)}

45 ( 해설 ) 집합 에서의관계 가반사적이고반대칭적이며추이적이라면 는반순서관계이다. 1 의경우 : 이므로반사적이라할수없다. 그러므로반순서관계도아니다. 2 의경우 : 와 에대하여 이므로추이적이지않다. 그러므로반순서관계라할수없다. 3 의경우 : 4 의경우 : 추이조건의후건에해당하는화살표를골라보면 a 에서 c 로가는화살표 하나가있다. 이를제거하고화살표를단순한선으로바꾸면 (c) 가된다. 그러므로정답은 3 번이다

46 3.3 함수연습문제 다음각관계가 에서 로의함수인지를밝혀라. 함수이면정의역과치역을구하고전사함수인지단사함수인지를결정하라. 또전단사함수인경우에는역함수를구하라. (1) 함수, 전사도단사도아님. 정의역 :, 치역 : (2) 함수아님. (3) 전단사함수정의역 :, 치역 :, 역함수 : (4) 함수아님 (5) 함수. 전사도단사도아님. 정의역 :, 치역 : 2. 에서 로의함수 와 에서 로의함수 에대하여 와 를각각순서쌍의집합으로나타내라. 3., 일때 인모든함수 를구하라. 그리고이함수들의 대응형태 ( 전사, 단사, 전단사 ) 를밝혀라. A 에서 B 로의함수는다음과같이 8 개이며대응형태도함께표시되었다 단사 전사 4. 다음값을구하라. (1) 3 (2) -3 (3)

47 5. 다음식은 이거나 임을보여라. 의소수부를 로나타내기로하자. 즉, 이다. 이 4의배수이면 이고, 이때 이므로 이다. 이면 이고, 이면 이다. 이상으로부터 이 4 의배수이거나 이면주어진식은 이고나머지경우는 이다. 6. 가실수일때다음이성립함을보여라. 이고 이므로다음식이성립한다. 은정수이므로주어진식이성립한다. 7. 로정의된함수 가있다고하자. (1) 는단사이나전사는아닌함수임을보여라. 의치역은짝수이다. 홀수에대응하는정의역의원소가없으므로전사함수는아니다. 한편 라하면 이어서 가되므로단사함수이다. (2) 전사이나단사는아닌함수 를구하라. 8. 와 가단사함수이면 도단사함수임을보여라. 라고하자. 그러면 이다. 는단사함수이므로 이 어야한다. 또한단사함수이므로 이어야한다. 따라서 도단사함수이다. 9. 와 가전사함수이면 도전사함수임을보여라. 전사함수는치역이공역과같은함수이므로 임을보이면된다. 10. 를 로정의하자. 역함수 를구하라

48 11. 이고 일때 를구하라. 12. 와 가실수에서실수로의함수이고 일때 와 를각각구하라. 13. 이고둘다가역적이라고할때 임을보여라. 는 에서 로의함수이다. 정리 3.3에의하여 이다. 따라서 임을보이면된다. 14. 임을보여라. 이므로 을나누면주어진식이참임을알수있다. 15. 과 중어느것이더빠르게증가하는함수인가? 로부터 이면 이고 이커질수록그차이는훨씬커진다. 따라 서 이더빠르게증가하는함수이다. 3.3 함수기출문제 [2009 출석시험대체 ]

49 ( 해설 ) 이다. 대입을해보면, 그러므로정답은 3 번이다. [2009 출석시험대체 ] ( 해설 ) 가전단사함수라고하자. 그러면역관계 는 에서 로의함수가된다. 이함수를 의역함수라하고 로표기한다. 1의경우 : 에서 로의함수에서 의모든원소에대한순서쌍이존재하지않으므로 (c의경우 ) 역함수가성립되지않는다. 2의경우 : 에서 로의함수에서 의모든원소에대한순서쌍이모두존재하므로역함수라할수있다. 3의경우 : 에서 로의함수에서 의모든원소에대한순서쌍이존재하지않으므로 (d의경우 ) 역함수가성립되지않는다. 4의경우 : 에서 로의함수에서 의모든원소에대하여하나의값만정의되지않고 2개의원소와대응하므로 (b의경우 ) 역함수가성립되지않는다. 그러므로정답은 2 번이다

50 제 4 장계수법칙 4.1 기본계수법칙연습문제 외출용으로넥타이를 8개, 와이셔츠를 6벌, 상의를 4벌, 하의를 5벌가지고있는사람이있다. 이사람의상이한옷차림새의종류를구하라. 곱법칙을적용하면 로시작하는 8 비트이진수의개수를구하라 이나 000 으로시작하는 8 비트이진수의개수를구하라. 4. 둘째번이나넷째번비트가 1인 8비트이진수의개수를구하라. ( 둘째번이 1인경우의수 ) + ( 넷째번이 1인경우의수 ) - ( 둘째번과넷째번이동시에 1인경우의수 ) 5. 1 이두번만나타나는 8 비트이진수의개수를구하라. 6. 이씨, 김씨, 박씨, 최씨, 정씨, 조씨로구성된 6인위원회의위원중에서의장, 간사, 회계를 1명씩뽑는문제이다. 다음을구하라. (1) 맡기는방법의수 (2) 이씨나김씨가의장이되도록맡기는방법의수 (3) 박씨가반드시세자리중한자리를차지하도록맡기는방법의수 (4) 최씨와정씨둘다직을반드시차지하도록맡기는방법의수 7. 가, 나, 다 의세도시가있는데 가 와 나 간에는 5개의도로가, 나 와 다 간에는 4개의도로가있다. ( 가 에서 다 로갈때나돌아올때는반드시 나 를경유하기로한다.) 다음물음에답하라. (1) 가 에서 나 를경유하여 다 까지갈때취할수있는상이한경로의종류는몇가지인가? (2) 가 에서 다 까지간후다시 가 로돌아오는경우경로의종류는몇가지인가?

51 (3) 위의 (2) 에서돌아올때는갈때와다른도로를이용해야한다면어떻게되는가? 8. A, B, C, D, E의다섯문자중에서네문자를취하여길이 4인문자열을만들려고한다. 다음을구하라. (1) 중복이허용된다면나타날수있는상이한문자열의개수 (2) 중복이허용되지않는경우상이한문자열의가짓수 (3) 중복이허용되는경우 AB로시작되는상이한문자열의가짓수 (4) 중복이허용되지않는경우 AB로시작되는상이한문자열의가짓수 (5) 중복이허용되는경우 AB로시작하지않는상이한문자열의가짓수 9. 를 개원소의집합, 를 개원소의집합이라할때 에서 로의상이한함수는 몇가지인가? 상이한 개에서중복을허용하여 개를취하는것과같으므로 가지다 과같이왼쪽방향으로읽어도오른쪽방향으로읽어도같은것을회문 ( 回文, palindrome) 이라한다. 예를들어두자리십진수에는 10의자리에 0이올수없으므로 11, 22, 33,, 99의아홉가지가있다. 다음물음에답하라. (1) 세자리십진수에는회문이몇가지인가? (2) 네자리십진수에는회문이몇가지인가? 11. 다섯자리십진수 ( 상위자리가 0으로시작될수없음 ) 중각자리의숫자가다르면서홀수인것의개수를구하라. 최하위자리에는 1, 3, 5, 7, 9의 5가지숫자가올수있고최상위자리에는최하위자리의수와 0을제외한 8가지가올수있다. 그리고 10의자리에는 8가지, 의자리에는 7가지, 자리에는 6가지가올수있다. 따라서 개다. 4.1 기본계수법칙기출문제 [2007 기말 ]

52 ( 해설 ) 곱법칙 : 사건 가발생할수있는경우의수가차례로 라고할때, 이사건들이이번호순으로일어날수있는모든경우의수는 이다. 축구부, 배구부, 야구부, 족구부, 수영부를선택하는사건으로생각할수있다. 그러므로곱법칙에의하여상이한식단의종류는 가지다. 그러므로정답은 3 번이다. [2006 기말 ] ( 해설 ) 밥, 나물, 생선, 찌개, 김치를선택하는사건으로생각할수있다. 그러므로곱법칙에의하여상이한식단의종류는 가지다. 그러므로정답은 1 번이다

53 4.2 순열과조합연습문제 라고하자. 다음물음에답하라. (1) 의 3-순열의개수를구하라. (2) 의 3-순열을모두나열하라. 123, 124, 132, 134, 142, 143, 213, 214, 231, 234, 241, 243, 312, 314, 321, 324, 341, 342, 412, 413, 421, 423, 431, 432 (3) 의 3-조합의개수를구하라. (4) 의 3-조합을모두나열하라. 2. 9명중에서의장, 부의장, 간사를각한명씩뽑는방법의수를구하라. 첫번째뽑히는사람은의장, 두번째는부의장, 세번째는서기등으로순서가있는경우로생각해야하므로 이된다. 3. 9명중에서 3명의위원을뽑는방법의수를구하라. 2번과는달리뽑아놓기만하면되므로순서가없는것으로생각하면되므로 이된다. 4. idiom 에있는문자를나열하여만들수있는상이한문자열의가짓수를구하라. 가두개이고나머지는모두한개다. 일단ㄷ두개의 가서로다른것으로간주하여 나열하고이를 2 로나누면된다. 따라서 이다 이 4 개만있는 8 비트문자열의개수를구하라. 6. 여섯명의남성과다섯명의여성으로구성된단체가있다. 다음을구하라. (1) 최소한한명의남자가포함된 4인위원회를구성하는방법의수 (2) 남자가 1인이하인 4인위원회를구성하는방법의수 (3) 남녀가모두포함된 4인위원회를구성하는방법의수 7. 음이아닌정수 에대하여 임을증명하라

54 이다. 즉, 이다. 이식의양변을 에대하여미분하고 을대입하면된 다. 8. 의전개식에서 의계수를구하라. 9. 의전개식에서 의계수를구하라. 10. 의전개식에서 의계수를구하라 비트이진수중에서 1 도세개이상, 0 도세개이상들어있는것의개수를구하라 이 6 개, 1 이 8 개인 14 비트이진수로서 0 다음에는반드시 1 이나타나는이진수의개 수를구하라 다음그림은도로망을나타낸것이다. 오른쪽혹은아래방향으로만갈수있다면 A 에 서 B 까지의상이한경로의종류는몇가지인가? 오른쪽방향을 1, 아래방향을 0 이라하면 8 비트이진수중 1 이네번나타나는이진수 의개수를구하는문제로바꿀수있다. 따라서 이다. 4.2 순열과조합기출문제 [2009 기말 ]

55 ( 해설 ) 총 10명중에서 3명을뽑아서순서대로각직을맡기는것을볼수있으므로, 그가짓수는 이다. 그러므로정답은 4 번이다. [2007 기말 ] ( 해설 ) [ 정리 4.1] 개상이한원소의집합에대한 r- 순열의개수 는다음과같다. 정리 4.1 에의하여 이다. 그러므로정답은 3 번이다

56 4.3 일반순열과일반조합연습문제 다음과같은단어가있다. 각문자의순서를바꾸어만들수있는상이한단어의개수를 구하라. (1) mississippi (2) madam (3) entities (4) salespersons 권의상이한책을세명의학생 A, B, C 에게나누어주려고한다. A 에게 4 권, B 에게 4 권, C 에게 2 권을나누어주는방법의수를구하라. 3. 과일가게에서사과, 배, 귤을적절히골라사려고한다. 다음을구하라. (1) 세종류중에서 10개를선택하는방법의수 (2) 10개의과일중에하나이상의사과가포함되어야한다면선택하는방법의수 (3) 사과는하나이상, 배와귤은각각둘이상이포함되도록하여 10개의과일을선택하는방법의수 4. 방정식 에대하여다음의주어진조건에맞는정수해의개수를각각구하라. (1) (2) (3) (4)

57 5. 1부터 사이의정수중각자리의숫자의합이 12인것은몇개인가? 를그수의각자리의숫자라하면다음식 에대한 를만족하는정수해를구하면된다. 를만족하는정수해는 개다. 한편 일때의정수해는 개이므로모든 에대하여는 개이다. 따라서구하는답은 개이다. 6. 서로다른만화책 20 권이있다. 다음을구하라. (1) A, B 에세각각 3 권씩, C, D, E 에게각각 4 권씩, F 에게 2 권을나누어주는방법의수 (2) A, B, C, D 네명에게각각 5 권씩나누어주는방법의수 (3) 똑같은 6 개의상자에 3, 3, 4, 4, 4, 2 권씩나누어넣는방법의수 (4) 똑같은 4 개의상자에 5 권씩나누어넣는방법의수 권의동일한책을 6 명의학생에게나누어주는방법의수를구하라 개의동일한공을 12개의서로다른상자에넣는데다음과같은조건을지켜야한다면나타날수있는서로다른경우의수는몇가지인가? (1) 상자에하나의공만을넣을수있는경우 (2) 상자에공을 10개까지넣을수있는경우 9. 0 이다섯개, 1 이두개, 7 이세개로이루어진열자리십진수는모두몇개인가? 맨왼쪽자리에 1이올때 맨왼쪽자리에 7이올때 따라서구하는개수는 1260 이다. 10. 이 의배수임을증명하라. 각형별로 개의동일한물체로구성된상이한 형의 개의물체집합에대한순열의

58 수를생각해보라. 11. 의전개식에대하여다음물음에답하라. (1) 의계수는얼마인가? ( 힌드 : 일반순열을이용한다.) (2) 전개식에서 + 로연결된총항수는얼마인가? 12. 다음의루프가수행된후변수 의값은얼마인가? for ( from 1 to ) for ( from 1 to ) for ( from 1 to ) for ( from 1 to ) 루프의수행횟수를구하면된다. 다음조건을만족하는모든 에대하여 값을증가시키는지정문이수행된다. 따라서루프수행횟수는집합 에서네개를중복선택하는방법의수와같다 ( 선택한것을앞의조건에따라배열하면각 에해당한다.). 그러므로수행횟수는정리 4.7에의하여 이고이것이 의값이다. 4.3 일반순열과일반조합기출문제 [2008 기말 ]

59 ( 해설 ) 중복물체의조합을일반조합이라한다. [ 정리 4.7] 가 개원소의집합일때중복을허용하여 에서 개의원소를뽑는무순서선택의수 는 이다. 사과 배 귤 이라고하면, 에서 5 개의원소를뽑는일반조합이므로정리 4.7 에의 하여다음과같이계산할수있다. 그러므로정답은 4 번이다. [2005 기말 ] ( 해설 ) 책 10 개의순서를고정시키고 A 4 개, B 1 개, C 3 개, D 2 개의순열을생각한다. 예를들 어 AABCCDAACD 는 A 에게는 1, 2, 7, 8 번의책을나누어주고, B 에게는 3 번의책을 나누어주고, C 에게는 4, 5, 9 번의책을, D 에게는 6, 10 번의책을나누어주는것이다. 따라서이문제는 AAAABCCCDD 의순열을구하는것으로바꾸어생각할수있으므로 이다. 그러므로정답은 2 번이다

60 4.4 비둘기집원리연습문제 태어난요일이같은사람이반드시존재하려면최소몇명이모여야하는가? 8 명 2. 를양의정수의일부를취한집합이라하자. 13 으로나눈나머지가같은수가반드시 존재하려면 의가디낼리티는얼마이상이어야하는가? 을넘지않는양의정수중에서 개중에는약수관계를갖는두수가반드시존 재함을보여라. 예제 4.22 의방법으로증명하면된다. 4. 가전사함수이면 임을비둘기집원리에의하여보여라. 전사함수는모든 에대하여 가되는 가있어야한다. 라고가정하자. 는전사함수이므로모든 에대하여 로되는 가반드시존재한다. 이는비둘기집원리에의하여어떤 에대하여는 으로되는 가둘이상이어야한다. 이것은전사함수라는전제와모순이되므로 이어야한다. 5. 태어난달이같은사람이 10 명이상이라는것을보장할수있으려면몇명이모여야하 는가? 명이상 6. 과목의성적을수, 우, 미, 양, 가의다섯등급으로매길때다섯명이상이같은등급을 받는경우가존재한다는것이보장되려면학생수는최소몇명이어야하는가? 비둘기집원리기출문제 [2008 기말 ]

61 ( 해설 ) [ 정리 4.9] 일반화비둘기집원리 마리의비둘기와 개의비둘기집이있다면 마리이상이들어있는비둘기집 이반드시존재한다. * 증명 * 모든비둘기집에 마리이하가들어있다고가정하자. 그러면비둘기 집에들어있는비둘기의총수는 으로되어비둘기가 마리라는것과모순이된다. 따라서 마리이상이들어있는 비둘기집이반드시존재한다. 정리 4.9에의하여 이므로최소 7명은생일이같다. 그러므로정답은 4 번이다

62 4.5 이산확률연습문제 앞뒷면이있는동전이있다. 이것을두번던졌을때두번모두앞면일확률을구하라 장의뒤집어진화투에서한장을임의로잡을때솔광이잡힐확률을구하라. 3. 주사위를두번던졌을때나온숫자의합이 7 이될확률을구하라. 4. 화투에서 4 장을임의로택할때그 4 장이모두다른달이될확률을구하라 과 100 사이의정수에서임의로하나를고를때이것이 2 의배수이거나 5 의배수일확 률을구하라. 6. 앞뒷면이있는동전을두번던졌을때두번모두앞면이아닐확률을구하라 세장의카드가있다. 한장의카드에는 A가표시되었고다른두장의카드에는아무표시도없다. 주인은이카드를덮어서섞어놓고고객이이중에서한장을고르도록한다. 주인은카드가덮인상태에서도카드의내용을알수있다고가정하자. 주인은고객이선택하지않은두장중에서항상아무것도없는한장을보여주고고객이다시한번선택할기회를준다. 이때고객은자기가처음선택한카드를계속선택하는것이좋겠는가, 아니면다른한장으로바꾸어선택하는것이좋겠는가, 아니면어떻게하든마찬가지결과로나타날것인가? 그리고이때맞힐확률을구하라. ( 이것은 Monty Hall Three Door Puzzle이라고하는문제이다.) 바꾸어선택하는것이더좋다. 이때맞힐확률은 이다. 4.5 이산확률기출문제 [2008 기말 ]

63 ( 해설 ) [ 정리 4.10] 를표본공간이라하고 라고하자. * 증명 * 모든순열의개수는 이다. 빨강공과주황공이인접할순열의개수는 이다. 정리 4.10 에의하여서로떨어져있을확률은 이다. 그러므로정답은 2 번이다

64 제 5 장점화식 5.1 점화식연습문제 연리 8% 인예금에 1000원을투자했다. 을 년후의원리금이라할때 에대한점화식과초기조건을구하라. 2. 을상이한 개의물체에대한순열의개수라할때 에대한점화식과초기조건을 구하라. 3. 을 개원소의집합에대한부분집합의개수라할때이에대한점화식과초기조건을구하라. 원소의집합에서 원소의집합으로바뀌면부분집합의개수가 2배가되므로 이고초기조건은 이다. 4. 을평면이 개의선분으로나누어진영역의수라고하자. 각선분의쌍은한점에서교차하지만어떤교차점이든셋이상의선분이지날수없다. 에대한점화식을구하라. n개의선분은평면을 영역으로나눈다. 여기에 n+1번째선 L을추가하면가정에의하여다른 n개의선과교차할것이다. 이선 L을따라나가는경우 L은원래의영역을둘로나눌것이며지나치는영역은 n+1개일것이므로 이다 6. 자리십진수중에서 0 이잇달아나타나지않는것의개수를 이라하자. 을점화식으로나타내라 이셋이상연속해서나타나지않는길이 인비트열의개수를 이라할때 을점 화식으로나타내라. 10. 어떤마라톤경기의참석자가 명이었다. 이들에게는접수순으로상의에등번호가부여되었으며불참한사람이한명도없었고모두완주했다고가정하자. 마라톤경기가끝난후모두다른사람의상의와바꾸어입기로하였다. 명이바꾸어입는방법의수를 이라하면다음의점화식이성립함을보여라

65 은 에대한순열 에서 에대하여 인경우의수이다. 이러한순열을뒤바뀐순열이라한다. 에대한순열중 형태의뒤바뀐순열이 개라고가정하자. 그러면 2를 3으로바꾼 형태의뒤바뀐순열도 개이며따라서 를 2부터 사이의정수라고할때 형태의뒤바뀐순열도 개일것이다. 그러므로다음이성립한다. 식 (1) 이제뒤바뀐순열 을다음의경우로나눌수있다. 식 (2) 단, 식 (3) 식 (2) 에서 에있는 개의숫자는모두제자리를벗어났으므로 에대한뒤ㅣ바뀐순열이며따라서이러한경우는 가지가있다. 식 (3) 에서 은모두제자리를벗어난, 2를제외한 1부터 까지의정수에대한뒤바뀐순열이므로이러한경우는 가지가있다. 그러므로 가되며식 (1) 에대입함ㄴ다음의결과를얻는다. 5.1 점화식기출문제 [2007 기말 ]

66 ( 해설 ) 개월이지난후의토끼쌍의수를 으로나타내자. 그러면 이다. 이것은피보나치수열의초기조건이다. 번째달과비교하여 번째달에늘어난토끼쌍의수인 은 번째달에이미있던토끼쌍이낳은새끼수이다. 즉, 가되며이를정돈하면 가된다. 이점화식은앞의초기조건과함께피보나치수열을정의한식이다. 피보나치수열의앞에서부터나열하면다음과같다. 즉, 1 년후에는 233 쌍이될것이다. 그러므로정답은 4 번이다. [2006 기말 ] ( 해설 ) 원리금이 1년후에는전년도의 1.1배가되므로 이라는점화식으로나타낼수있으며초기조건은다음과같이최초의원금이다. 그러므로정답은 1 번이다

67 5.2 점화식의해연습문제 다음에초기조건및점화식이주어졌다. 이들에대한해를반복법으로구하라. (1) (2) (3) (4) 2. 다음에초기조건및점화식이주어졌다. 이들에대한해를선형동차점화식에대한해법 을써서구하라. (1) 의근은 0.5 와 5 이다. 따라서일반해는다음과같다. 이것에초기조건을대입하면다음을얻는다. 이것을풀면 이다. 따라서구하는해는다음과같다. (2) (3) (4) 으로놓으면주어진식은 로된다. 이로부터구한답은다음 과같다

68 3. 방정식 의해가 이면 은 의해임을증명하라. 을주어진식에대입한다. 그러면다음과같이된다. 따라서 이주어진점화식의해이다. 4. 3번문제의결과를이용하여다음점화식의해를구하라. 이것은차수가 3인선형동차점화식의예이다. 2차의경우를확장하여특성방정식을세우고특성근을구하여풀면된다. 특성방정식은다음과같다. 이식은 으로인수분해되므로 이다. 따라서 이며, 여기에초기조건을대입하여계산하면답은다음과같다. 5.2 점화식의해기출문제 [2009 기말 ]

69 ,, 위의식을다음과같이바꾼다. 여기에다음과같이반복법을적용한다. (a)... 즉, 다음과같은점화식이얻어진다. 여기에다시다음과같은반복법을적용하여해를구한다. (b)... 1 (a) :, (b) 2 (a) :, (b) 3 (a) :, (b) 4 (a) :, (b)

70 ( 해설 ) 에대한해를구하는풀이는다음과같다. [ 풀이 ] 주어진식을다음과같이바꾼다. 여기에다음과같이반복법을적용한다. 즉, 다음과같은점화식이얻어진다. 여기에다시다음과같은반복법을적용하여해를구한다. 그러므로정답은 1 번이다. [2008 기말 ]

71 ( 해설 ) 반복적으로다음과같이대치하여구한다. 그러므로정답은 1 번이다

72 제 6 장그래프이론 6.1 서론연습문제 다음그래프의정점 1 에서시작하는사이클을모두구하라. 1231, 1241, 1321, 1341, 1421, 1431, 12341, 12431, 13241, 13421, 14231, 를정점 의차수라고할때 인네정점의그 래프를그려라. v 1 v 2 v 4 v 3 3. 다섯개의정점과세개의연결성분을갖는비연결그래프를그려라. 5. 을임의의양의정수라할때모든정점의차수가 인그래프를그리는방법을설명하 라. 개의정점을취하고이들을모두연결한다. 6. 다음그래프에대하여물음에주어진정점의순차열이경로, 단순경로, 회로, 단순회로에 해당하는지를밝혀라. (1) 경로, 회로 (2) 경로, 단순경로

73 (3) 아무것도아님 (4) 회로 ( 사이클 ), 단순회로 ( 단순사이클 ) (5) 아무것도아님 (6) 회로 ( 사이클 ) (7) 경로, 단순경로 7. 다음의설명이참인지거짓인지를밝혀라. 만약거짓이면반대예를하나제시하고, 참이면그이유를밝혀라. (1) 와 를그래프 의상이한정점이라하자. 만약 에서 로의경로가있으면 에서 로의단순경로가존재한다. 참다음의경로 에서와같이 가다시나타나면 를제거한다. (2) 그래프 의정점 에대하여 가사이클에포함되면 는단순사이클에포함된다. 참이유는 (1) 의경우와동일 8. 를그려라. 9. 의간선의개수를계산하는공식을구하라. 10. 을그려라

74 11. 의간선의개수를계산하는공식을구하라. 6.1 서론기출문제 [2008 기말 ] 1 그래프의모든간선을꼭한번씩만거치는사이클을오일러사이클이라한다. 또한그래프의간선을꼭한번씩거치는경로를오일러경로라한다. 2 그래프의모든정점을한번이상씩거치는사이클을해밀턴사이클이라한다. 또한그래프의모든정점을한번이상씩거치는경로를해밀턴경로라한다. 3 모든정점쌍이간선으로연결된그래프를완전그래프라한다. 4 모든정점쌍간에경로가존재하는그래프를연결그래프라한다. ( 해설 ) 1 의경우 : 그래프의모든간선을꼭한번씩만거치는사이클을오일러사이클이라한다. 또한그래프의간선을꼭한번씩거치를경로를오일러경로라고한다. 2 의경우 : 정점이아닌간선이옳은설명이다. 3 의경우 : 모든정점쌍이간선으로연결된그래프를완전그래프라고하며정점이 개인완전그래프를 으로표기한다. 4 의경우 : 모든정점쌍간에경로가존재하는그래프를연결그래프 (connected graph) 라고한다. 연결그래프중에서특히사이클이없는연결그래프를나무 (tree) 라고한다. 그러므로정답은 2 번이다. [2006 동계계절수업 ]

75 ( 해설 ) [ 정리 6.1] 를단순그래프라하면 이다. 차수의합은 이므로정리 6.1 에의하여간선은 10 개이다. 그러므로정답은 2 번이다

76 6.2 그래프의표현방법연습문제 다음의각그래프에대하여인접리스트, 인접행렬, 부수행렬을각각구하라. (1) 인접리스트 정점 인접정점 인접행렬 부수행렬 (2) 인접리스트 정점 인접정점 인접행렬 부수행렬 (3) 인접리스트 정점 인접정점 인접행렬 부수행렬

77 2. 다음방향그래프에대한인접행렬을구하라. (1) (2) 3. 다음의인접행렬에해당하는그래프를구하라. (1) b c a e d (2)

78 a b c d e 4. 어떤그래프의인접행렬 가정사각행렬이고다음과같은형태라고하자. 여기서부분 행렬 역시정사각행렬로서영행렬이라면그래프는어떠한모양이겠는가? 이분그래프 모든정점의차수가 2 이므로, 이므로, 간선의총수는 n(v)*2=2n 에서 간선의수는 n 이다. n 개의정점과 n 개의간선으로이루어지는차수가 2 인단순그래프는다 각형이다 위의 4 번문제에서 을제외한부분행렬이영행렬이라면그그래프는어떠한모양 인가? 공통정점이없는두부분그래프로구성된그래프이다. 6. 다음의부수행렬에대응하는그래프를그려라. (1)

79 7. 부수행렬에서일부의행이모두 0 이라면이에대응하는그래프의모양은어떠한가? 그정점에부수된간선이없다. 즉, 고립정점들로나타난다. 6.2 그래프의표현방법기출문제 [2009 기말 ] ( 해설 ) 그래프 는루프는존재하지만평행간선은없다고하고 이라고하자. 를나타낸인접행렬 (adjacency matrix) 을 라하면 는 불행렬이다. 이그래프의인접행렬 는정점이 4개이므로 행렬이필요하다. 를구하려면먼저정점을행과열에대응시켜야한다. 여기서는정점 를이순서대로행과열에대응시키기로하자. 다음에는첫번째정점인 로부터이것에인접한정점을찾는다. 그림의경우 가 의인접한정점이다. 따라서 은 1이고나머지 1행의원소인 는 0이다. 나머지정점도마찬가지방법으로하면된다. 그러므로정답은 1 번이다. [2008 기말 ] a b c e d

80 3 4 ( 해설 ) 그래프 는루프는존재하지만평행간선은없다고하고 이라고하자. 를나타낸인접행렬 (adjacency matrix) 을 라하면 는 불행렬이다. 이그래프의인접행렬 는정점이 5개이므로 행렬이필요하다. 를구하려면먼저정점을행과열에대응시켜야한다. 여기서는정점 를이순서대로행과열에대응시키기로하자. 다음에는첫번째정점인 로부터이것에인접한정점을찾는다. 그림의경우 가 의인접한정점이다. 따라서 은 1이고나머지 1행의원소인 는 0이다. 나머지정점도마찬가지방법으로하면된다. 그러므로정답은 4 번이다

81 6.3 오일러사이클과해밀턴사이클연습문제 다음각그래프에대하여오일러사이클또는오일러경로를구하라. (1) ( 다른것도있을수있음.) (2) ( 다른것도있을수있음.) 2. 이오일러사이클을가지는경우는어느때인가? 이홀수일때 의모든정점의차수는 이다. 따라서 이홀수이면모든정점의 차수가짝수로된다. 3. 다음의그래프들에대하여해밀턴사이클을찾아라. 만약해밀턴사이클이없으면해밀 턴경로를찾아라. 에는해밀턴사이클은없지만 는해밀턴경로이다. 에는해밀턴사이클 이있으며 가그중하나이다. 에는해밀턴사이클도해밀턴경로도없다. 4. 인 에는해밀턴사이클이존재함을보여라. i) 기본단계 에해밀턴사이클이존재함을보이면된다. 정점 3개로만들수있는완전그래프는삼각형밖에존재하지않고, 삼각형은완전그래프이고해밀턴사이클이존재한다. ii) 다음 인경우에대하여 에해밀턴사이클이존재한다고가정하고 에도해밀턴사이클이존재하는것을보인다. 가정에의해 는 1,2,3,...k,1로이루어지는해밀턴사이클이존재한다. 이때,

82 은 의모든정점과간선으로직접연결된새로운정점 k+1이추가되어이루어지는완전그래프이다. 따라서, 정점 k+1은정점 k와간선이존재한다. 또한 k+1은정점 1과도간선이존재한다. 즉, 1,2,3,...k,k+1,1의해밀턴사이클이존재한다. 따라서모든 에대하여 은해밀턴사이클이존재한다. 6.3 오일러사이클과해밀턴사이클기출문제 [2008 기말 ] 1 오일러사이클은없으며, 해밀턴사이클은존재한다. 2 오일러사이클은존재하고, 해밀턴사이클은존재하지않는다. 3 오일러사이클과해밀턴사이클이모두존재한다. 4 오일러사이클과해밀턴사이클이모두존재하지않는다. ( 해설 ) [ 정리 6.2] 고립정점이없는그래프 에오일러사이클이있을필요충분조건은다음두조건을모두만족하는것이다. ᄀ 는연결되었다. ᄂ각정점의차수는짝수이다. 위의그래프의경우는정리 6.2 에의하여홀수차수의정점이둘이므로오일러사이클은 없다고할수있다. 그리고해밀턴사이클이존재한다. 예를들어 의경우모든정점을꼭한번 씩거치므로해밀턴사이클이라할수있다. 여기에서맨끝의 1 을제거하면해밀턴경로 가된다. 그러므로정답은 1 번이다. [2006 동계계절수업 ]

83 ( 해설 ) 그래프의모든정점을꼭한번씩거치는사이클을해밀턴사이클이라한다. 위의보기에서해밀턴사이클이존재하는것은 3 번이해당된다. 그러므로정답은 3 번이다

84 6.4 동형그래프연습문제 다음각문항의두그래프가동형인지를조사하라. 동형이면본문의정의에있는 를구 하고, 동형이아니면두그래프의서로다른불변자를밝혀라. (1) 동형이다. (2) 동형이다. (3) 동형이다. (4) 에는차수 2 의정점이있으나 에는없으므로동형이아니다

85 (5) 에는길이 3 의단순사이클이둘이나 에는하나밖에없으므로동형이아니다. 2. 정점이 4 개인비동형단순그래프는모두몇개가나올수있는가? 11 개 3. 아래에주어진두그래프가동형인지를밝혀라. 동형이아니다. 4. 단순그래프 의보 ( 補 ) 그래프 는 와정점은같으나간선은 에없는것들만으로이루어진다. 과 를단순그래프라고하자. 과 가동형일필요충분조건이 과 가동형인것임을보여라. 과 가동형이라고가정하고 가동형사상이라고하자. 정의 6.3에의하여다음이성립한다. 그러므로 과 에대하여도 가동형사상이다. 역으로 과 가동형이고 가동형사상이라고가정해도앞의과정과유사하게 가 과 의동형사상임을보일수있다. 6.4 동형그래프기출문제 [2005 기말 ] 1 그래프의모든정점을꼭한번씩거치는사이클을해밀턴사이클이라한다. 2 고립정점이없는그래프 G에오일러사이클이있을필요충분조건은 G에짝수

86 차수의정점이꼭두개인것이다. 3 그래프 G에오일러경로가존재할필요충분조건은 G가연결그래프이고각정점의차수가짝수인것이다. 4 그래프에서정점과간선의연결관계와관계없이, 정점의수나, 간선의수가같은경우를동형그래프라한다. ( 해설 ) 1 의경우 : 그래프의모든정점을꼭한번씩거치는사이클을해밀턴사이클이라한다. 또한그래프의모든정점을꼭한번씩거치는경로를해밀턴경로라고한다. 2 의경우 : 고립정점이없는그래프 에오일러사이클이있을필요충분조건은다음두조건을모두만족하는것이다. ᄀ 는연결되었다. ᄂ각정점의차수는짝수이다. 3 의경우 : 그래프 에오일러경로가존재할필요충분조건은 가연결그래프이고 에홀수차수의정점이꼭두개인것이다. 4 의경우 : 그래프 는정점의집합과정점을연결하는간선의집합에의하여정의됨을이미알고있다. 정점과간선의연결관계는같지만겉모양이다른그래프를여러가지만들수있다. 즉, 수학에서는두개의대상이근본적으로동일구조를가질때동형 ( 同型, isomorphic) 이라고한다. 동형그래프의수학적정의는다음과같다. * 두단순그래프 가있다고하자. 모든 에대하여 일필요충분조건이 이도록하는전단사함수 가존재한다면 과 는동형이라고한다. 그리고이때의 를동형사상 (isomorphism) 이라고한다. 그러므로정답은 1 번이다

87 6.5 최단경로연습문제 다음의가중그래프에대하여각문항의정점쌍사이의최단경로와최단경로의길이를각 각구하라. (1) (2) (3) (4) (5) 2. 연결된가중그래프 G에서모든정점쌍간의최단경로의길이를구하는알고리즘을작성하라. 그래프 G의정점은 이라고하자. 또간선이없는정점 간의 는 로되어있다고가정한다. for ( from 1 to ) for ( from 1 to ) DIST ; for ( from 1 to ) for ( from 1 to ) for ( from 1 to ) if (DIST +DIST < DIST ) DIST DIST + DIST 3. 다음의알고리즘은연결된가중그래프와정점 와 를입력으로받아 LENGTH에 부터 까지의최단경로의길이를계산해놓을목적으로작성된것이다. 이알고리즘이목적에맞게정확하다면정확성을증명하고, 정확하지않다면예를하나제시하라. { LENGTH 0; ; 모든정점; while ( ) { ; 가중치 가최소인 를선택 ; LENGTH LENGTH + ; ;

88 } } 정확하지않음. 5 a b c 60 z 4. 사이클이없는연결된가중그래프 G에서주어진정점쌍간의최장경로의길이를구하는알고리즘을작성하라. 알고리즘 6.1의줄 5의조건을 로하고줄 6의최소를최대로고치고, 줄 9의 min 을 max로고친다. 5. 사이클이없는연결된가중그래프 G 의한정점에서다른모든정점으로의최장경로의 길이를구하는알고리즘을작성하라. 알고리즘 6.1 의줄 6 의최소를최대로고치고, 줄 9 의 min 을 max 로고친다. 6. 사이클이없는연결된가중그래프에서모든정점쌍간의최장경로의길이를구하는알고 리즘을작성하라. 위의 2 번을참고하여작성한다. 8. 알고리즘 6.1 은가중치가음인경우에도최단경로를계산할수있는가? 불가능 6.5 최단경로기출문제 [2005 기말 ]

89 1 (c)-(d)-(b)-(a)-(e) 3 (e)-(a)-(b)-(d)-(c) 2 (a)-(b)-(c)-(d)-(e) 4 (e)-(a)-(b)-(c)-(d)

90 ( 해설 ) [ 알고리즘 6.1] 다익스트라의최단경로알고리즘 /* 이알고리즘은연결된가중그래프 의정점 에서다른모든정점까지의최단경로의길이를구한다. 간선 의가중치는 이며정점 에서 까지의거리르 에나타내기로한다. 수행이완료되면 는 에서 까지의최단경로의길이가된다. */ for 모든정점 의값이최소인정점 를선택 for에인접한모든정점 min 알고리즘 6.1을적용해보자. while 루프에들어가면맨처음 가선택되고 가 에서제거되며 에인접한정점 와 의거리 이다음과같이수정된다. min min 보기 (c) 가이상태를나타낸다. 이제루프의처음으로다시돌아가정점이 에있으므로 에있는정점중저리가최소인정점 를선택한다. 를 에서제거하고 의인접정점 의거리를수정하면보기 (d) 와같이된다. 루프를더반복하면보기 (b), (a) 를얻는다. (a) 의상태에서루프를더만복하여정점 의순서로선택되어수행이완료된상태가 (e) 이다. 이렇게알고리즘의수행이완료되면예를들어 는 5가되므로 에서 까지의최단경로의길이는 5 이며최단경로는 이다. 그러므로정답은 1 번이다

91 6.6 경로의존재연습문제 다음과같이인접행렬로표현된그래프에대하여앞의식 (6.3) 을써서도달행렬을구 하라. (1) (2) 3. 방향그래프의도달행렬을이용하여사이클을검출하는방법을구하라. 정점 가사이클에포함될필요충분조건은 이다. 6.6 경로의존재기출문제 [2009 기말 ]

92 ( 해설 ) 위의방향그래프의인접행렬은 이다. 그러므로정답은 2 번이다. [2008 기말 ]

93 ( 해설 ) 위의방향그래프의인접행렬은 이다. 그러므로정답은 4 번이다

94 6.7 나무연습문제 인접행렬로주어진다음의각그래프가나무에해당하는지를조사해보라. (1) (2) 나무아님 나무 6. 차수 2, 3, 4 의정점이각각하나인자유나무가있다. 차수 1 인정점의개수를구하라. 5 개 7. 뿌리나무에서간선의개수 와차수의총합사이에는어떠한관계가성립하는가? 8. 다음그림중에서전이진나무인것은? 4 번 9. 잎이 10 개인전이진나무의내부정점의개수는얼마인가? 9 개 10. 전 3 진나무에서내부정점이 10 개이면전체정점의개수는얼마인가? 31 개 11. 전 진나무에서잎이 개일때전체정점의개수 을계산하는공식을구하라. 12. 높이가 10 인전이진나무가가질수있는잎의최대개수는얼마인가?

95 잎이 5 개인균형적전이진나무의경우높이는얼마인가? 높이가 5 인균형적전이진나무가되려면잎은최소몇개이어야하는가? 17 개 15. 예제 6.30 의게임에서알아맞힐숫자의범위가 1~100 일때정확한답을보장할수있 는최소추측횟수는얼마인가? 이를위하여필요한판정나무의 4 수준까지를그려라. 7 번 6.7 나무기출문제 [2009 기말 ] ( 해설 ) 전 진나무의정점의개수가, 내부정점의개수가, 잎의개수가 이라고하면다음이 성립한다. (1) (2) (3) 그러므로정답은 2 번이다. [2007 기말 ] 1 나무의정점중의하나가뿌리로지정된나무를뿌리나무라한다. 2 자식이없는정점은뿌리이고, 잎이아닌정점을내부정점이라한다. 3 뿌리나무에서정점의차수는자식의개수로정의된다. 4 사이클이없는단순연결그래프를나무라고한다

96 ( 해설 ) 1의경우 : 뿌리나무 (rooted tree) 란나무의정점중의하나가뿌리 (root) 로지정된나무이다. 뿌리로지정된정점 는나무의제일위쪽에오며기타다른정점은 의밑에위치한다. 2의경우 : 자식이없는정점을잎이라하고, 잎이아닌정점을내부정점이라한다. 3의경우 : 뿌리나무에서는정점의차수가자식의개수로정의된다. 4의경우 : 사이클이없는단순연결그래프를나무 (tree) 라고한다. 그러므로정답은 2 번이다

97 제 7 장불대수 7.1 불대수, 불식, 불함수연습문제 정리 7.1 의멱등법칙및흡수법칙을증명하라. 진리표를만들어증명하면된다. 2. 정리 7.1을이용하여다음등식을증명하라. (1) (3) 3. 불연산자 NAND는다음과같이정의된다. {NAND} 이완전연산자집합임을보여라. NAND만으로곱, 합, 보수를행할수있음을보이면된다. 4. 다음진리표에해당하는함수를정규합형으로표현하라. (1) (3)

98 다음불식에대한정규합형을구하라. (1) (2) (3) (4)

99 (5) 6. 위의 4 번문제의함수를정규곱형으로나타내라. (2) 7.1 불대수, 불식, 불함수기출문제 [2009 기말 ] ( 해설 ) 항등식이성립하는경우는, 항등법칙, 교환법칙, 결합법칙, 분배법칙, 멱등법칙, 흡수법칙, 보법칙, 드모르강법칙이있다. ( 교재 247 페이지 ) 1 의경우 : 보법칙으로 로맞는답이다. 2 의경우 : 항등법칙으로 가맞다. 그러므로틀렸다. 3 의경우 : 항등법칙으로 로맞는답이다. 4 의경우 : 보법칙으로 로맞는답이다. 그러므로정답은 2 번이다

100 [2009 기말 ] x y z f(x,y,z) ( 해설 ) 맥스텀은함수값이 0인행이다. 이러한행에서변수값을반대로해석한다. 0값을가진행에해당하는맥스텀은 에해당하며이맥스텀들을곱하면정규곱형, 즉합의곱형을다음과같이구할수있다. 그러므로정답은 4 번이다

101 7.2 불대수와조합회로연습문제 다음불식에해당하는회로를구하라. (1) x y z (2) x y z (3) x y z 2. 다음과동치인회로를구하라. (1) 와동치인것중의하나는 이므로이에대한회로를그린다. 4. NOR 연산은다음과같이정의된다. 이거나 일때 기타 (2) {NOR} 가완전연산자집합임을보여라. (3) 적절한 NOR 게이트의기호를정의하고위의 2 번문제에대하여 NOR 게이트만을쓴 회로를구하라. NOR 게이트는보통다음과같이표시된다

102 제 8 장자동장치와언어와문법 8.1 유한상태기계연습문제 다음과같은유한상태기계 에대하여상태도형을구하라. 초기상태는 인것으로가정한다. (1) (2) 다음의각유한상태기계에대하여, 초기상태, 상태표를구하라. (1)

103 초기상태 (2) 초기상태 (3) 초기상태 다음의각입력문자열과유한상태기계에대하여출력문자열을구하라. (1) : 연습문제 1-(1) 의기계 1001 (2) : 연습문제 1-(2) 의기계

104 (3) : 연습문제 1-(3) 의기계 (4) : 연습문제 2-(1) 의기계 (5) : 연습문제 1-(3) 의기계 비트열이입력될때다음의성질을만족하는유한상태기계를설계하라. (1) 1 이짝수개입력되었으면 0 을출력하고홀수개이면 1 을출력 (2) 셋이상의 1 이입력되면 1 을출력하고그렇지않으면 0 을출력 (3) 110 이들어온이후부터는 1 을출력하고그외의경우는 0 을출력 (4) 110 이들어올때마다 1 을출력하고그외의경우는 0 을출력 5. 을비트열이라하고다음의유한상태기계가있다고하자

105 최하위비트로부터입력하여얻어지는비트열의역순은 의 2 의보수임을보여라. 가입력되면첫 1 까지는 의순으로그대로출력되며, 그다음부 터는 가출력된다. 이것은 의 2 의보수이다. 8.1 유한상태기계기출문제 [2009 기말 ] /1 0/1 ( 해설 ) 유한상태기계는간단한수학적모델로서, 기계는어떤상태에있게되고이때입력이들어오면이입력에반응하여출력을내고다음상태로간다. 여기서상태는 0 과 1 이있다. 상태는동그라미로표현한다. 0 의상태에서입력으로 0 이올경우문자가같으므로출력도 0 이된다. 입력과출력에관해서는 입력 / 출력 으로표현한다. 0 의상태에서입력으로 1 이올경우문자가다르므로출력은 1 이된다. 1 의상태도위와같은방법으로할경우 4 번의상태도형이된다. 그러므로정답은 4 번이다. [2009 기말 ] g M=(I, O, Q, f, g, q 0 ) Q f g I a b a b

106 a/0 b/1 b/1 a/1 b/1 b/1 q 0 q 1 q 0 q 1 1 a/0 2 a/1 a/1 b/0 b/1 a/0 b/1 b/0 q 0 q 1 q 0 q 1 3 a/1 4 a/1 ( 해설 ) 위의표를해석하면다음과같다. 상태는 이고 가초기상태이다. 따라서두개의원을그리고 의원왼쪽에화살표를붙인다. 다음으로상태표에따라입력, 출력이붙은화살표를추가하면 4번의상태도형이완성된다. 그러므로정답은 4 번이다

107 8.2 결정적유한상태자동장치연습문제 다음의각유한상태기계가결정적유한상태자동장치임을보이고상태도형을결정적유 한상태자동장치의상태도형으로바꾸라. (1) 에대한모든내향간선은출력이 yes 이고 에대한모든내향간선의출력은 no 이다. 따라서이유한상태기계는유한상태자동장치이다. 가수락상태이다. 2. 결정적유한상태자동장치의상태도형을유한상태기계의상태도형으로바꾸라. (1) 3. 결정적유한상태자동장치 의상태도형을그려라. (1)

108 4. 다음의각문항에주어진문자열이다음에주어진결정적유한상태자동장치에의해수락되는지를밝혀라. (1) : 그림 8-5 수락 (2) : 연습문제 2-(1) 수락 (3) : 연습문제 2-(2) 수락 5. 문자집합 에서의문자열 가연습문제 2-(1) 의결정적유한상태자동장치에의해수락될필요충분조건은 가 로끝나는것임을보여라. 로끝나는문자열 가입력되면 가들어오기전에어느상태에있었든지상태 에서끝난다. 이것은세상태모두를조사해보면알수있다. 한편 는수락상태이므로 는수락된다. 가문제 2-(1) 의자동장치에의하여수락된다고사정하자. 그러면상태 에서끝난다. 따라서마지막문자는 이어야한다. 또한그앞의상태는 이나 이어야한다. 이두상태모두그상태로오기위해서는반드시 가입력되어야한다. 따라서마지막두문자는 이다. 6. 문자집합 에서다음과같은공이아닌문자열을수락하는결정적유한상태자동장 치의상태도형을구하라. (2) 가하나이상인문자열 (3) 가정확히두개인문자열 (4) 로시작되는문자열

109 (5) 다음에반드시 가나오는문자열 (6) 로끝나는문자열 7. 을연습문제 2-(2) 의결정적유한상태자동장치가수락하는문자열의집합이라하고, 를 에서의공 (null) 이아닌모든문자열의집합이라하자. 을수락하는결정적유한상태자동장치를설계하라. 수락상태를비수락상태로, 비수락상태를수락상태로바꾼다. 8.2 결정적유한상태자동장치기출문제 [2009 기말 ]

110 ( 해설 ) 유한상태자동장치는유한상태기계의특수한경우로서결정적유한상태자동장치와 비결정적유한상태자동장치의두종류가있다. 결정적유한상태자동장치는간단히 DFA로나타내는경우가많다. DFA는 FSM과비교하여출력이없고, 대신에수락상태라는것이추가되었음을알수있다. DFA를 FSM과마찬가지로상태표로써나타낼수도있고상태도형으로써나타낼수도있다. 상태도형으로나타내는경우수락상태는이중원으로표시한다. N 의상태에서시작하여 T 의상태로끝남을증명하면된다. 4 의경우는 N 의상태에서는화살표로옮겨가는상황이 0 밖에없음을확인할수있다. 그 러므로 1 의값으로시작할수없다. 그러므로정답은 4 번이다. [2006 기말 ] 0 1 0,1 N O 1 T ( 해설 ) 1 의경우 : N, O, T, T, T 의상태순서를확인할수있다. 2, 3, 4 의경우 : 수락을완료하는 T 의상태에서끝나지않으므로수락하지않는다. 그러므로정답은 1 번이다

111 8.3 비결정적유한상태자동장치연습문제 다음의 NFA 가 (1) bbb, (2) baba 를수락하는지를밝혀라. (1) 수락, (2) 수락 2. 다음의 NFA 가수락하는문자열의집합은무엇인가? 3. 로시작되는영어단어들을수락하는 NFA 를다음과같이설계하였다. 이것이잘못 된것임을보이고올바른 NFA 를제시하라. 에알파벳의모든문자에대하여자기자신으로되돌아오는화살표가있어야한다. 4. 다음비트열을수락하는 NFA 를설계하라. (1) 101 로끝나는비트열 (2) 100 이나 01 로시작되는비트열 (3) 100 이나 01 이포함된비트열

112 (4) 모든 1 의앞뒤에 0 이있는비트열 6. 앞의문제 1의 NFA를 DFA로고쳐라. NFA의초기상태는다음의 (a) 에서시작한다. 상태 q0에서 b가들어오면, 상태 q1과 q2로전이할수있으므로그림 (b) 로된다. 그림 (b) 에서 a가들어오면, 상태 q1가전이할수있는상태는 {q2} 이고, 상태 q2가전이할수있는상태는 {q0} 이다. 따라서상태 {q1,q2} 에서 a가들어올경우, 전이가능한상태집합은 {q0,q2} 이다. 그리고 b가들어오면, q1가전이할수있는상태는 {q0,q1} 이고, 상태 q2가전이할수있는상태가없다. 따라서상태 {q1,q2} 에서 b가들어올경우, 전이가능한상태집합은 {q1,q2} 이다. 즉, 그림 (c) 가된다. 그림 (c) 에서상태 {q0,q2} 에 a가들어오면, 전이가능한상태는 {q0} 이고, b가들어오면전이가능한상태집합은 {q1, q2} 이다. 즉, 그림 (d) 가된다. 또한그림 (d) 에서상태집합 {q0, q1} 에 a가들어오면, 전이가능한상태집합은 {q2} 이고 b가들어오면 {q0, q1, q2} 이다. 그림 (e) 에서상태집합 {q2} 에 a가들어오면 {q0} 로전이하고, b가들어오면상태가전이되지않는다. 따라서그림 (f) 가된다. 그림 (f) 에서상태집합 {q0, q1, q2} 에서 a가들어오면상태집합 {q0, q2} 로전이하고, b가들어오면 {q0, q1, q2} 로전이한다. (a) (b) (c)

113 (d) (e) (f) (g)

114 8.3 비결정적유한상태자동장치기출문제 [2009 기말 ] 1 abccc 3 abc 2 abcb 4 bc ( 해설 ) NFA는다음상태가정의되지않은입력이들어오면더이상입력을받아들이지않고정지한다. 한편 NFA는동일이름의외향간선이여럿이면스스로최선의하나를택하여전이할수있는능력이있다. 이것이바로 비결정적 이라는성질이다. 달리설명하면 NFA 의경우어떤입력에대하여초기상태로부터의경로가여러개존재할수있는데이중어느한경로만이라도수락상태에서끝나면그입력은수락된다. 1의경우 : 상태순서는 0, 1, 1, 2, 2, 2, 2 이다. 2의경우 : 마지막 b를수락할수없다. 3의경우 : 상태순서는 0, 1, 1, 2, 2 이다. 4의경우 : 상태순서는 0, 1, 2, 2 이다. 그러므로정답은 2 번이다. [2006 기말 ] b c 0 a 1 ε 2 1 ab 2 abbc 3 abccb 4 abbbccc ( 해설 ) 1의경우 : 상태순서는 0, 1, 1, 2 이다. 2의경우 : 상태순서는 0, 1, 1, 1, 2, 2 이다. 3의경우 : 마지막 b를수락할수없다. 4의경우 : 상태순서는 0, 1, 1, 1, 1, 2, 2, 2, 2 이다. 그러므로정답은 3 번이다

115 8.4 언어와문법연습문제 다음에주어진문법이어떠한형식에속하는지를밝혀라. (1) 문맥무관형, 문맥의존형, 무제한 (2) 문맥의존형, 무제한 (3) 정규형, 문맥무관형, 문맥의존형, 무제한 2. 다음에주어진문자열이해당문법 의 에속함을보여라. (1), 연습문제 1-(1) (2), 연습문제 1-(2) (3), 연습문제 1-(3) 3. 다음에주어진 에대하여 일필요충분조건은 가공문자열이아니고 가짝수개인것임을증명하라. 의생성은임의개수의 를만들어낸다. 이들을제외하면다음과같은유도만이가능하다. 4. 다음에주어진성질을갖는문자열을만들어내는문법을작성하라. (1) 에서의문자열로 1로끝나는것 생성들만열거하면다음과같다. (2) 에서의문자열로 10로시작하는것 (3) 에서의문자열로 01이포함된것 (4) 에서의문자열로공문자열이아닌모든문자열

116 6. 다음의언어가문맥무관형임을보여라. 이언어에해당하는생성을구해보면다음과같다. 이규칙은문맥무관형에속한다. 8.4 언어와문법기출문제 [2009 기말 ] 1 L(G) = {011} 2 L(G) = {010, 001} 3 L(G) = {01, 0011} 4 L(G) = {00, 11, 0011} ( 해설 ) 에서시작하여첫번째생성을 번적용하고마지막으로두번째생성을적용하면다음과같은유도가가능하다. 따라서 은정수이다. 이 1 일경우에는 이되고, 이 2 일경우에는 이된다. 즉, 의개수만큼 0 과 1 이반복된다. 이에해당하는 3 의경우로 0 과 1 이같은횟수로반복되고있다. 그러므로정답은 3 번이다. [2009 기말 ]

117 ( 해설 ) 첫번째생성우측에비최종기호가중간에나오므로정규문법은아니다. 생성좌측에하나의비최종기호만이나타나므로문맥무관형문법이다. 로부터의유도는다음과같은하나뿐이다. 따라서 은정수이다. 가문맥무관형이므로 는문맥무관형언어이다. 그러므로정답은 4 번이다

118 8.5 언어와자동장치연습문제 절의연습문제 2 의 DFA 에해당하는정규문법을구하라. (1) 절의연습문제 3 의 DFA 에해당하는정규문법을구하라. (1) 3. 다음의정규문법에의해만들어지는문자열을수락하는 DFA 를구하라. (1) 8.4 절의예제 8.23 (2) 8.4 절의연습문제 1-(3) 8.5 언어와자동장치기출문제 [2007 기말 ]

119 ( 해설 ) 정규문법의최종기호는입력기호인 로취하고비최종기호는자동장치의상태인 와 를취한다. 초기상태 는시작기호가된다. 생성은방향간선으로부터구한다. 만약상태 에서 으로가는, 이름이 인간선이있으면다음과같은생성을만든다. 따라서문제에있는그림에대한생성은다음과같다. ( 식 1) 또상태 에서수락상태로가는이름이 인간선이있으면다음의생성을추가한다. 문제의경우에는다음의두생성이추가된다. ( 식 2) 그러므로 이고 가 ( 식 1) 과 ( 식 2) 로이루어질때문법 는문제에있는그림의자동장치가수락하는문자열의집합과동일한언어 를만들어낸다. 그러므로정답은 2 번이다

120 8.6 튜링기계연습문제 어느한부분에만 1 이연속적으로나타나는테이프가있다. 이부분외에는모두빈칸이 다. 지금헤드가좌단의 1 에위치하고있다. 이 1 의길이를두배로늘리고헤드를 1 의좌 단에위치시킨상태에서정지하는튜링기계를설계하라. (1) 새기호 와 를추가한다. 프로그램리스트는다음과같다. 시작상태는 이다. *** 새 1 의탐색 1. 을찾았음 2. 탐색계속 3. 탐색계속 4. 탐색완료 *** 의추가 5. 추가 6. 이동계속 7. 이동계속 *** 와 를 1 로 8. 로변경 9. 로변경 10. 완료 2. 현재위치로부터오른쪽에있는 0과 1의순차열을각각 와 의순차열로바꾸는튜링기계를설계하라. A가시작상태이다 테이프에 개, 개씩의 1의순차열이하나의빈칸을사이에두고나타날때이둘을 개의 1의순차열로더하는튜링기계를설계하라. 헤드가앞선 1의맨왼쪽에있다고가정한다. 중간의빈칸을 1로만들고우단의 1을지운후헤드를원위치시킨다. 시작상태는 A이다

121