12 -- 2 1 2009 5,,.,.,.. 1, 2, 3,., 4),, 4, 5),. 4, 6, 7).,, R A B, 8, (a) A, B 9), (b) {a (a, b) R b B }, {b (a, b) R a A } 10, 11, 12) 2. (a). 11, 13, R S {(a, c) (a, b) R, (b, c) S } (c) R S 14), 1, 15, (d) S R 16) 2. (d). f : X Y. 1, 6, 9,, (e) Y 17) 3, 4, 8, 10, 11, 12, 18, 19), (f) X f (X)., codomain range, (g) Y codomain 7, 9, 14, 16, 19, 20, 21) 3, 4, 8, 9, 10, 11, 12,, (h) f (X) range 15)., (e) (g), (f) (h)., (e) (g). 1-5 2.,.,,.. 1-1. 2,, 1-2, 1-3. 1-4.. 1-5. c 2014 1/(14)
12 -- 2 -- 1 1--1 2009 5 1--1--1 set element a A A a A a A 1 extensional definition, { } A = {1, 2, 3, 4, 5, 6, 7, 8, 9} 9 1, 2, 3, 4, 5, 6, 7, 8, 9... A A = {1, 2,..., 9} {1, 2, 3,...} intensional definition. : { }. x predicate P(x) {x P(x)} A = {2, 4, 6, 8, 10} A = {x x 2 10 } A = {2x x 1 5 } 1-4-3 2 finite set infinite 1-5 A A #A 0 empty set {} 3 A B A B subset A B B A A B A B A B A B A = B A B A B A B A B A B proper subset A B A : A A. : A B B C A C. (1 1) (1 2) 4 family F S F 14, 19) c 2014 2/(14)
A F A A F a A F a F order 5 N : N = {0, 1, 2,...} Z : Q : R : C : 1--1--2 A, B 2 1 A, B {x x A x B} A B union A B A, B, C : A = A = A. (1 3) : A A = A. (1 4) : A B = B A. (1 5) : (A B) C = A (B C). (1 6) A 1,, A n A 1 A n I i A i I i A i A i I index set i I 2 A, B {x x A x B} A B intersection A B A, B, C : A = A =. (1 7) : A A = A. (1 8) : A B = B A. (1 9) : (A B) C = A (B C). (1 10) A 1,, A n A 1 A n c 2014 3/(14)
I A i i I A B = A B disjoint A,B A B A + B A B direct sum A, B, C A (B C) = (A B) (A C). A (B C) = (A B) (A C). (1 11) (1 12) A (A B) = A. A (A B) = A. (1 13) (1 14) 3 A B {x x A x B} A B difference A B A B A\B 4 A B (A B) (B A) P Q symmetric difference P Q A B A B 1--1--3 A U U A U A complement U U universal set U U A A A A A c U A U = U, U =. (1 15) : A A = U, A A =. (1 16) : A = A. (1 17) 1--1--4 De Morgan's laws A, B A B = A B. A B = A B. (1 18) (1 19) U c 2014 4/(14)
1--1--5 A A power set 2 A P(A) 2 A = {S S A} A = {1, 2, 3} 2 A = {, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}} 2 A, A 2 A 2 A = 2 A. (1 20) c 2014 5/(14)
12 -- 2 -- 1 1--2 2009 5 1--2--1 A, B a A, b B (a, b) ordered pair A B {(a, b) a A b B} A B direct product Cartesian product A B A A = A =. (1 21) A, B A B = A B. (1 22) 1--2--2 2 A,B A B R A B 2 binary relation 2 A R domain B codomain A R A A A (a, b) R R(a, b) arb R A B {(b, a) (a, b) R} B A R inverse relation R 1 R, S R = S 1--2--3 2 A 2 1 a A (a, a) R R reflexive 2 (a, b) R (b, a) R R symmetric 3 (a, b) R a b (b, a) R R antisymmetric 4 (a, b) R, (b, c) R (a, c) R R transitive 1--2--4 A B R A B B C S B C R S c 2014 6/(14)
{(a, c) R(a, b) S (b, c)} A C R S composition S R R A B S B C T C D T (S R) = (T S ) R. (1 23) n 2 R n R n n = 1 R 1 = R n = 0 R 0 = {(a, a) a A} R 0 identity relation 1--2--5 R A S R P A P S R S S S R P- P-closure R transitive closure reflexive transitive closure P P- R + R R + = R 1 R 2 R 3 = R = R 0 R 1 R 2 = 1--2--6 i=1 i=0 R i R i (1 24) (1 25) equivalence relation a A, {b A a b} a equivalence class [a] a [a] representative A A F A partition S F S = A S, T F S T S T = A a, b A [a] = [b] [a] [b] = I A F = {[i] i I} A A = [i] F A quotient set A/ i I A F R = {(a, b) S F a S b S } 1--2--7 partial order A A partially ordered set, poset, A, ) ( 14, 15, 17) c 2014 7/(14)
1 (A, ) a, b A a b a b a b (A, ) Hasse diagram 1. A a b a b 2. a b a, b a c b c a, b 1 1 (2 {1,2,3}, ) {1, 2} {1} {1, 2, 3} {1, 3} {2} {2, 3} {3} 1 1 2 a, b a b b a a b comparable incomparable A S S S chain S S S antichain 3 B A a 0 B a 0 a a B a 0 B maximal B a a 0 a B a 0 B minimal B a 0 B a 0 B a 0 a a B a 0 B maximum B a 0 B a a 0 a B a 0 B minimum B 1--2--8 (A, ) total order linear order (A, ) totally ordered set (A, ) A quasi-order c 2014 8/(14)
12 -- 2 -- 1 1--3 2009 5 1--3--1 X Y X Y mapping function f : X Y X domain Y codomain X = dom( f ), Y = codom( f ) f, g dom( f ) = dom(g), codom( f ) = codom(g), x dom( f ) f (x) = g(x) f = g 1 f A dom( f ) f A restriction f A f f A extension 2 f : X Y x X y Y y x image y = f (x) f : x y A X, f (A) = {y x A y = f (x)} f A A = X f (X) f range( f ) f : X Y B Y X {x x X, f (x) B} B f inverse image preimage f 1 (B) 1--3--2 f : X Y, g : Y Z x X g( f (x)) f g composition g f g f X Z g f : X Z f, g, h g f h g, h (g f ) = (h g) f, 1--3--3 1 f : X Y x 1, x 2 X x 1 x 2 f (x 1 ) f (x 2 ) f injection 1 1 one-to-one f, g g f f, g g f f g 2 f : X Y y Y f (x) = y x X f (X) = Y f surjection onto f, g g f f, g g f g f c 2014 9/(14)
3 bijection f, g g f f, g g f f g X f : X X X permutation 1--3--4 f : X Y y Y y = f (x) x X y x f inverse mapping f 1 f 1 ( f 1 ) 1 ( f 1 ) 1 = f 1--3--5 x dom( f ) a codom( f ) f (dom( f )) = {a} f constant function 1--3--6 f : X Y x X f (x) = x f identity function c 2014 10/(14)
12 -- 2 -- 1 1--4 2009 5 1--4--1 P(n) n 7 7-2 mathematical induction n N P(n) 1 n N P(n) 1. P(0) 2. n P(n) P(n + 1) 1. 2. 2 P(n) 2 (1) n N P(n) 1. P(0) 2. k n P(k) P(n + 1) 3 m, n N P(m, n) 1. P(0, 0) 2. m, n P(m, n) P(m + 1, n) P(m, n + 1) 1--4--2 Giuseppe Peano, 1858 1932 N Peano axioms c 2014 11/(14)
N 1. N 0 0 N 2. σ : N N σ(n) n (a) σ m n σ(m) σ(n) (b) σ(n) = 0 n N 0 (c) N S 0 n S σ(n) S S = N 2(c) n S 2(c) N 1--4--3 recursive definition S, a S S 0 S (S 0 ) b S S c S inductive definition c 2014 12/(14)
12 -- 2 -- 1 1--5 2009 5 1--5--1 2 2, 19) 1 A n {1, 2,..., n} A 2, 4, 9) 2 A A A A N N {0} f (n) = n + 1 N (1), N 1--5--2 A B A B equipotent A B cardinality A n {1, 2,..., n} A = n N ℵ 0 ℵ 0 countable set countably infinite set at most countable set uncountable set R 1), Information & computing 61,, 1992. 2) C.L. Liu,,,,, 1995. 3),,, Information&Computing 21,, 1999. 4),, E13,, 2008. J. W. R. Dedekind, 1831 1916 14, 20, 21) c 2014 13/(14)
5),,, 2007. 6),,, 1995. 7) R. Garnier and J. Taylor, Discrete Mathematics for New Technology 2nd edition, Taylor & Francis, 2001. 8),,,, 1995. 9),,,,,, 2007. 10) R. Johnsonbaugh, Discrete Mathematics The Jk Computer Science and Mathematics Series, 5th edition, Prentice Hall College Div., 2000. 11),,, 15,, 2006. 12), Information Science & Engineering F1,, 2008. 13),,,, 1993. 14) J.L. Hein, Discrete Mathematics 2nd edition, Jones & Bartlett Publishers, 2003. 15) J.K. Truss, Discrete Mathematics for Computer Scientists International Computer Science Series, 2nd edition, Addison-Wesley, 1999. 16) D.E. Ensley and J.W. Crawley, Discrete Mathematics, Textbook and Student Solutions Manual: Mathematical Reasoning and Proof with Puzzles, Patterns, and Games, Wiley, 2006. 17) R.J. McEliece, R.B. Ash, and C. Ash, Introduction to Discrete Mathematics, International Edition, 1989. 18),,, 1997. 19),,,, 1,, 2008. 20) R.P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction 4th edition, Addison-Wesley, 1999. 21) K.A. Ross and C.R. Wright, Discrete Mathematics 5th edition, Prentice Hall, 2002. c 2014 14/(14)