Bài giảng Toán cao cấp (A2)

153 trang vanle 3460

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán cao cấp (A2)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

bai_giang_toan_cao_cap_a2.pdf

Nội dung text: Bài giảng Toán cao cấp (A2)

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG - - - - - - - - - - - - - - BÀI GIẢNG TOÁN CAO CẤP (A2) Biên soạn : Ts. LÊ BÁ LONG Ths. ĐỖ PHI NGA Lưu hành nội bộ HÀ NỘI - 2006
LỜI NÓI ĐẦU Toán cao cấp A1, A2, A3 là chương trình toán đại cương dành cho sinh viên các nhóm ngành toán và nhóm ngành thuộc khối kỹ thuật. Nội dung của toán cao cấp A1, A3 chủ yếu là phép tính vi tích phân của hàm một hoặc nhiều biến, còn toán cao cấp A2 là các cấu trúc đại số và đại số tuyến tính. Có khá nhiều sách giáo khoa và tài liệu tham khảo viết về các chủ đề này. Tuy nhiên với phương thức đào tạo từ xa có những đặc thù riêng, đòi hỏi học viên làm việc độc lập nhiều hơn, do đó cần phải có tài liệu hướng dẫn học tập thích hợp cho từng môn học. Tập tài liệu hướng dẫn học môn toán cao cấp A2 này được biên soạn cũng nhằm mục đích trên. Tập tài liệu này được biên soạn theo chương trình qui định năm 2001 của Học viện Công nghệ Bưu Chính Viễn Thông. Nội dung của cuốn sách bám sát các giáo trình của các trường đại học kỹ thuật, giáo trình dành cho hệ chính qui của Học viện Công nghệ Bưu Chính Viễn Thông biên soạn năm 2001 và theo kinh nghiệm giảng dạy nhiều năm của tác giả. Chính vì thế, giáo trình này cũng có thể dùng làm tài liệu học tập, tài liệu tham khảo cho sinh viên của các trường, các ngành đại học và cao đẳng. Giáo trình được trình bày theo cách thích hợp đối với người tự học, đặc biệt phục vụ đắc lực cho công tác đào tạo từ xa. Trước khi nghiên cứu các nội dung chi tiết, người đọc nên xem phần giới thiệu của mỗi chương cũng như mục đích của chương (trong sách Hướng dẫn học tập Toán A2 đi kèm) để thấy được mục đích ý nghĩa, yêu cầu chính của chương đó. Trong mỗi chương, mỗi nội dung, người đọc có thể tự đọc và hiểu được cặn kẽ thông qua cách diễn đạt và chứng minh rõ ràng. Đặc biệt bạn đọc nên chú ý đến các nhận xét, bình luận để hiểu sâu hơn hoặc mở rộng tổng quát hơn các kết quả. Hầu hết các bài toán được xây dựng theo lược đồ: Đặt bài toán, chứng minh sự tồn tại lời giải bằng lý thuyết và cuối cùng nêu thuật toán giải quyết bài toán này. Các ví dụ là để minh hoạ trực tiếp khái niệm, định lý hoặc các thuật toán, vì vậy sẽ giúp người đọc dễ dàng hơn khi tiếp thu bài học. Giáo trình gồm 7 chương tương ứng với 4 đơn vị học trình (60 tiết): Chương I: Lô gích toán học, lý thuyết tập hợp, ánh xạ và các cấu trúc đại số. Chương II: Không gian véc tơ. Chương III: Ma trận. Chương IV: Định thức. Chương V: Hệ phương trình tuyến tính Chương VI: Ánh xạ tuyến tính. Chương VII: Không gian véc tơ Euclide và dạng toàn phương. Ngoài vai trò là công cụ cho các ngành khoa học khác, toán học còn được xem là một ngành khoa học có phương pháp tư duy lập luận chính xác chặt chẽ. Vì vậy việc học toán cũng giúp ta rèn luyện phương pháp tư duy. Các phương pháp này đã được giảng dạy và cung cấp
từng bước trong quá trình học tập ở phổ thông, nhưng trong chương I các vấn đề này được hệ thống hoá lại. Nội dung của chương I được xem là cơ sở, ngôn ngữ của toán học hiện đại. Một vài nội dung trong chương này đã được học ở phổ thông nhưng chỉ với mức độ đơn giản. Các cấu trúc đại số thì hoàn toàn mới và khá trừu tượng vì vậy đòi hỏi học viên phải đọc lại nhiều lần mới tiếp thu được. Các chương còn lại của giáo trình là đại số tuyến tính. Kiến thức của các chương liên hệ chặt chẽ với nhau, kết quả của chương này là công cụ của chương khác. Vì vậy học viên cần thấy được mối liên hệ này. Đặc điểm của môn học này là tính khái quát hoá và trừu tượng cao. Các khái niệm thường được khái quát hoá từ những kết quả của hình học giải tích ở phổ thông. Khi học ta nên liên hệ đến các kết quả đó. Tuy rằng tác giả đã rất cố gắng, song vì thời gian bị hạn hẹp cùng với yêu cầu cấp bách của Học viện, vì vậy các thiếu sót còn tồn tại trong giáo trình là điều khó tránh khỏi. Tác giả rất mong sự đóng góp ý kiến của bạn bè đồng nghiệp, học viên xa gần và xin cám ơn vì điều đó. Cuối cùng chúng tôi bày tỏ sự cám ơn đối với Ban Giám đốc Học viện Công nghệ Bưu Chính Viễn Thông, Trung tâm Đào tạo Bưu Chính Viễn Thông 1 và bạn bè đồng nghiệp đã khuyến khích động viên, tạo nhiều điều kiện thuận lợi để chúng tôi hoàn thành tập tài liệi này. Hà Nội, cuối năm 2004. Ts. Lê Bá Long Khoa cơ bản 1 Học Viện Công nghệ Bưu chính Viễn thông
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số 1. CHƯƠNG 1: MỞ ĐẦU VỀ LÔGÍC MỆNH ĐỀ, TẬP HỢP ÁNH XẠ VÀ CÁC CẤU TRÚC ĐẠI SỐ 1.1 SƠ LƯỢC VỀ LÔGÍC MỆNH ĐỀ 1.1.1 Mệnh đề Lôgíc mệnh đề là một hệ thống lôgích đơn giản nhất, với đơn vị cơ bản là các mệnh đề mang nội dung của các phán đoán, mỗi phán đoán được giả thiết là có một giá trị chân lý nhất định là đúng hoặc sai. Để chỉ các mệnh đề chưa xác định ta dùng các chữ cái p, q ,r và gọi chúng là các biến mệnh đề. Nếu mệnh đề p đúng ta cho p nhận giá trị 1 và p sai ta cho nhận giá trị 0. Giá trị 1 hoặc 0 được gọi là thể hiện của p . Mệnh đề phức hợp được xây dựng từ các mệnh đề đơn gián hơn bằng các phép liên kết lôgích mệnh đề. 1.1.2 Các phép liên kết lôgíc mệnh đề 1. Phép phủ định (negation): Phủ định của mệnh đề p là mệnh đề được ký hiệu p, đọc là không p . Mệnh đề p đúng khi p sai và p sai khi p đúng. 2. Phép hội (conjunction): Hội của hai mệnh đề p,q là mệnh đề được ký hiệu p ∧ q (đọc là p và q ). Mệnh đề p ∧ q chỉ đúng khi p và q cùng đúng. 3. Phép tuyển (disjunction): Tuyển của hai mệnh đề p,q là mệnh đề được ký hiệu p ∨ q (đọc là p hoặc q ). p ∨ q chỉ sai khi p và q cùng sai. 4. Phép kéo theo (implication): Mệnh đề p kéo theo q , ký hiệu p⇒ q , là mệnh đề chỉ sai khi p đúng q sai. 5. Phép tương đương (equivalence): Mệnh đề ()()p ⇒ q∧ q ⇒ p được gọi là mệnh đề p tương đương q , ký hiệu p⇔ q . Một công thức gồm các biến mệnh đề và các phép liên kết mệnh đề được gọi là một công thức mệnh đề. Bảng liệt kê các thể hiện của công thức mệnh đề được gọi là bảng chân trị. Từ định nghĩa của các phép liên kết mệnh đề ta có các bảng chân trị sau 5
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số p q p∧ q p∨ q p p 1 1 1 1 1 0 1 0 0 1 0 1 0 1 0 1 0 0 0 0 p q p⇒ q p q p⇒ q q ⇒ p p⇔ q 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1 1 0 1 1 0 0 0 0 1 0 0 1 1 1 Như vậy p⇔ q là một mệnh đề đúng khi cả hai mệnh đề p và q cùng đúng hoặc cùng sai và mệnh đề p⇔ q sai trong trường hợp ngược lại. Một công thức mệnh đề được gọi là hằng đúng nếu nó luôn nhận giá trị 1 trong mọi thể hiện của các biến mệnh đề có trong công thức. Ta ký hiệu mệnh đề tương đương hằng đúng là " ≡ " thay cho " ⇔ ". 1.1.3 Các tính chất Dùng bảng chân trị ta dễ dàng kiểm chứng các mệnh đề hằng đúng sau: 1) p≡ p luật phủ định kép. 2) ()()p⇒ q ≡ p ∨ q . 3) p ∧ q≡ q ∧p, p ∨ q≡ q ∨ p luật giao hoán. 4) p ∧ ()()q ∧ r ≡p ∧ q ∧ r p ∨()()q ∨r ≡p ∨q ∨ r luật kết hợp. 5) []p∧()()() q ∨ r ≡[ p ∧ q ∨ p∧ r ] []p∨ ()()() q∧ r≡[ p ∨ q∧ p∨ r ] luật phân phối. 6) Mệnh đề p ∨ p luôn đúng luật bài chung. p ∧ p luôn sai luật mâu thuẫn. 7) p∨ q ≡ p ∧ q p∧ q ≡ p ∨ q l uật De Morgan. 6
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số 8) p ⇒ q≡ q ⇒ p luật phản chứng. 9) p ∨ p ≡ p; p ∧ p ≡ p luật lũy đẳng. 10) p ∨();()p ∧q ≡ p p ∧ p ∨ q ≡ p luật hấp thu. 1.2 TẬP HỢP 1.2.1 Khái niệm tập hợp Khái niệm tập hợp và phần tử là khái niệm cơ bản của toán học, không thể định nghĩa qua các khái niệm đã biết. Các khái niệm "tập hợp", "phần tử" xét trong mối quan hệ phân tử của tập hợp trong lý thuyết tập hợp là giống với khái niệm "đường thẳng", "điểm" và quan hệ điểm trên đường thẳng được xét trong hình học. Nói một cách nôm na, ta có thể xem tập hợp như một sự tụ tập các vật, các đối tượng nào đó mà mỗi vật hay đối tượng là một phần tử của tập hợp. Có thể lấy ví dụ về các tập hợp có nội dung toán học hoặc không toán học. Chẳng hạn: tập hợp các số tự nhiên là tập hợp mà các phần tử của nó là các số 1,2,3 , còn tập hợp các cuốn sách trong thư viện của Học viện Công nghệ Bưu chính Viễn thông là tập hợp mà các phần tử của nó là các cuốn sách. Ta thường ký hiệu các tập hợp bởi các chữ in hoa A,B , X ,Y , còn các phần tử bởi các chữ thường x,y , Nếu phần tử x thuộc A ta ký hiệu x∈ A, nếu x không thuộc A ta ký hiệu x∉ A . Ta cũng nói tắt "tập" thay cho thuật ngữ "tập hợp". 1.2.2 Cách mô tả tập hợp Ta thường mô tả tập hợp theo hai cách sau: a) Liệt kê các phần tử của tập hợp Ví dụ 1.1: Tập các số tự nhiên lẻ nhỏ hơn 10 là { 9,7,5,3,1 }. 2 Tập hợp các nghiệm của phương trình x −1= 0 là {− 1,1 }. b) Nêu đặc trưng tính chất của các phần tử tạo thành tập hợp Ví dụ 1.2: Tập hợp các số tự nhiên chẵn P= { n ∈ n= 2 m , m∈} Hàm mệnh đề trên tập hợp D là một mệnh đề S()x phụ thuộc vào biến x ∈ D . Khi cho biến x một giá trị cụ thể thì ta được mệnh đề lôgích (mệnh đề chỉ nhận một trong hai giá trị hoặc đúng hoặc sai). Nếu S()x là một mệnh đề trên tập hợp D thì tập hợp các phần tử x ∈ D sao cho S()x đúng được ký hiệu {x∈ D S() x } và được gọi là miền đúng của hàm mệnh đề S()x . 2 i) Xét hàm mệnh đề S()x xác định trên tập các số tự nhiên : " x +1 là một số nguyên tố" thì S(1),S (2) đúng và S(3),S (4) sai 7
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số ii) Mỗi một phương trình là một hàm mệnh đề 2 { x∈ x −1 = 0} ={} − 1,1 . Để có hình ảnh trực quan về tập hợp, người ta thường biểu diễn tập hợp như là miền phẳng giới hạn bởi đường cong khép kín không tự cắt được gọi là giản đồ Ven. c) Một số tập hợp số thường gặp - Tập các số tự nhiên = {0, 1, 2, }. - Tập các số nguyên = {0,± 1,± 2, }. - Tập các số hữu tỉ = { p q q≠ 0, p , q∈ }. - Tập các số thực . 2 - Tập các số phức ={z = x + iy x, y ∈ ; i = − 1}. 1.2.3 Tập con Định nghĩa 1.1: Tập A được gọi là tập con của B nếu mọi phần tử của A đều là phần tử của B , khi đó ta ký hiệu A ⊂ B hay B ⊃ A. Khi A là tập con của B thì ta còn nói A bao hàm trong B hay B bao hàm A hay B chứa A. Ta có: ⊂ ⊂ ⊂ ⊂ . Định nghĩa 1.2: Hai tập A, B bằng nhau, ký hiệu A = B, khi và chỉ khi A ⊂ B và B ⊂ A. Như vậy để chứng minh A ⊂ B ta chỉ cần chứng minh x∈ A ⇒x ∈ B và vì vậy khi chứng minh A = B ta chỉ cần chứng minh x ∈ A ⇔ x ∈ B . Định nghĩa 1.3: Tập rỗng là tập không chứa phần tử nào, ký hiệu φ. Một cách hình thức ta có thể xem tập rỗng là tập con của mọi tập hợp. Tập hợp tất cả các tập con của X được ký hiệu P ()X . Vậy AX∈P () khi và chỉ khi A ⊂ X . Tập X là tập con của chính nó nên là phần tử lớn nhất còn φ là phần tử bé nhất trong P ()X . Ví dụ 1.3: X= {} a,, b c có P (),,,,,,,,,,X= {}φ {} abcabbccaX{ } { } { } { } { } . 8
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số 3 Ta thấy X có 3 phần tử thì P ()X có 2= 8 phần tử. Ta có thể chứng minh tổng quát n rằng nếu X có n phần tử thì P ()X có 2 phần tử. 1.2.4 Các phép toán trên các tập hợp 1. Phép hợp: Hợp của hai tập A và B , ký hiệu A ∪ B , là tập gồm các phần tử thuộc ít nhất một trong hai tập A, B . Vậy ()x∈ A ∪ B⇔ (( x∈ A)∨ ( x∈ B)). 2. Phép giao: Giao của hai tập A và B , ký hiệu A ∩ B , là tập gồm các phần tử thuộc đồng thời cả hai tập A, B . Vậy ()x∈ A ∩ B⇔ (( x∈ A) ∧ ( x∈ B)). 3. Hiệu của hai tập: Hiệu của hai tập A và B , ký hiệu A \ B hay A − B , là tập gồm các phần tử thuộc A nhưng không thuộc B . Vậy ()x∈ A\ B⇔ (( x∈ A) ∧ ( x∉ B)). Đặc biệt nếu B ⊂ X thì tập X \ B được gọi là phần bù của B trong X và B được ký hiệu là CX . Nếu tập X cố định và không sợ nhầm lẫn thì ta ký hiệu B thay cho B CX . Ta có thể minh hoạ các phép toán trên bằng giản đồ Ven: B A ∩ B A ∪ B CX Áp dụng lôgích mệnh đề ta dễ dàng kiểm chứng lại các tính chất sau: 1. A ∪ B = B ∪ A, A ∩ B = B ∩ A tính giao hoán. 2. A ∪()()B ∪C =A ∪B ∪ C , A ∩ ()()B ∩ C =A ∩ B ∩ C tính kết hợp. 3. A ∪ ()()()B ∩ C =A ∪ B ∩ A ∪ C , 9
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số A ∩()()()B ∪C =A ∩B ∪ A ∩ C tính phân bố. Giả sử A, B là hai tập con của X thì: 4. AAAAAXA=; ∪φ =; ∩ = 5. AAXAA∪ =; ∩ = φ 6. A ∪ B = A ∩ B ; A ∩ B = A ∪ B luật De Morgan AB∩ 7. ABABAABAABC\ = ∩ = ∩( ∩) =\() ∩ = A . 1.2.5 Lượng từ phổ biến và lượng từ tồn tại Giả sử S()x là một hàm mệnh đề xác định trên tập D có miền đúng DS() x ={ x ∈ D S() x }. Khi đó: a) Mệnh đề ∀x∈ D,()S x (đọc là với mọi x∈ D,()S x ) là một mệnh đề đúng nếu DDS() x = và sai trong trường hợp ngược lại. Ký hiệu ∀ (đọc là với mọi) được gọi là lượng từ phổ biến. Khi D đã xác định thì ta thường viết tắt ∀x,()S x hay (∀x),() S x . b) Mệnh đề ∃x∈ D,()S x (đọc là tồn tại x∈ D,()S x ) là một mệnh đề đúng nếu DS() x ≠ φ và sai trong trường hợp ngược lại. Ký hiệu ∃(đọc là tồn tại) được gọi là lượng từ tồn tại. Để chứng minh một mệnh đề với lượng từ phổ biến là đúng thì ta phải chứng minh đúng trong mọi trường hợp, còn với mệnh đề tồn tại ta chỉ cần chỉ ra một trường hợp đúng. c) Người ta mở rộng khái niệm lượng tử tồn tại với ký hiệu ∃!,()x∈ D S x (đọc là tồn tại duy nhất x ∈ D,()S x ) nếu DS() x có đúng một phần tử. d) Phép phủ định lượng từ ∀x ∈ D,() S x⇔( ∃ x ∈ D,() S x ) ∃x ∈ D,() S x⇔( ∀ x ∈ D,() S x ) (1.1) Ví dụ 1.4: Theo định nghĩa của giới hạn limf ( x ) = L ⇔∀ε >0, ∃δ > 0;∀x : 0 < x− a< δ ⇒ f() x − L < ε . x→ a 10
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số Sử dụng tính chất hằng đúng ()()p ⇒ q ≡ p ∨ q (xem tính chất 1.3) ta có 0 0, ∀δ > 0; ∃x :( 0 < x− a< δ )∧ ( f() x− L ≥ ε ). 1.2.6 Phép hợp và giao suy rộng Giả sử ()A là một họ các tập hợp. Ta định nghĩa A là tập gồm các phần tử thuộc i i∈ I U i i∈ I ít nhất một tập Ai nào đó và I Ai là tập gồm các phần tử thuộc mọi tập Ai . i∈ I Vậy (x∈ A) ⇔( ∃ i ∈ I; x ∈ A ) Ui∈I i 0 i0 x∈ A⇔( ∀ i ∈ I; x ∈ A ). (1.2) ( Ii∈I i ) i Ví dụ 1.5: An ={ x ∈ 0≤ x≤ n ( n + 1)} Bn ={ x ∈ −1 ( n+ 1)≤ x< 1+ 1 ( n + 1)} ∞ ∞ An = [0; 1) , Bn = []0; 1 . Un=1 In=1 1.2.7 Quan hệ 1.2.7.1 Tích Đề các của các tập hợp Định nghĩa 1.4: Tích Đề các của hai tập X , Y là tập, ký hiệu X ×Y , gồm các phần tử có dạng (,)x y trong đó x ∈ X và y∈Y . Vậy X× Y = {(,) x y x∈ X vµ y∈ Y}. (1.3) Ví dụ 1.6: X= { a,, b c}, Y = {1,2} X× Y= {}( a ,1),( b ,1),( c ,1),( a ,2),( b ,2),( c ,2) Ta dễ dàng chứng minh được rằng nếu X có n phần tử, Y có m phần tử thì X ×Y có n× m phần tử. 11
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số Cho XXX1, 2 , , n là n tập hợp nào đó, ta định nghĩa và ký hiệu tích Đề các của n tập hợp này như sau: X1× X 2 × × Xn = { ( x1 , x 2 , , xn ) x i∈ X i , i= 1,2, , n}. (1.4) Chú ý 1.1: n 1. Khi XXX= = = thì ta ký hiệu X thay cho XX× × . 1 n 142 43 n lÇn 2. Tích Đề các XXX× × × còn được ký hiệu X . 1 2 n ∏i∈I i 3. Giả sử (x1 , , xn )∈ X1 × × X n ; (x '1 , , x 'n )∈ X1 × × X n thì (x1 , , xn )= ( x '1 , , x 'n )⇔ x i= x ' i ,∀ i= 1, , n 4. Tích Đề các của các tập hợp không có tính giao hoán. 1.2.7.2 Quan hệ hai ngôi Định nghĩa 1.5: Cho tập X ≠ φ , mỗi tập con R ⊂ X × X được gọi là một quan hệ hai ngôi trên X . Với x, y∈ X mà (,)x y ∈ R ta nói x có quan hệ với y theo quan hệ R và ta viết xRy . Ví dụ 1.7: Ta xét các quan hệ sau trên tập các số: R1: xR 1 y⇔ xM y (x chia hết cho y) , ∀x, y∈ R2:xR 2 y⇔ ( x , y )= 1 (x và y nguyên tố cùng nhau) ∀x, y∈ R3: xR 3 y⇔ x≤ y (x nhỏ hơn hay bằng y) ∀x, y∈ R4: xR 4 y⇔ x− yM m , ∀x, y∈ . Ta ký hiệu x ≡ y(mod m ) và đọc là x đồng dư với y môđulô m. Định nghĩa 1.6: Quan hệ hai ngôi R trên X được gọi là có tính: a) Phản xạ, nếu xRx, ∀x ∈ X ; b) Đối xứng, nếu ∀x, y ∈ X mà xRy thì cũng có yRx ; c) Bắc cầu, nếu ∀x,,y z ∈ X mà xRy và yR z thì cũng có xRz ; d) Phản đối xứng, nếu ∀x, y∈ X mà xRy và yRx thì x = y . 12
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số Ví dụ 1.8: R1 phản đối xứng, bắc cầu nhưng không đối xứng, không phản xạ (vì 0 không chia hết cho 0). R2 đối xứng, không phản xạ, không phản xứng, không bắc cầu. R3 phản xạ, phản đối xứng, bắc cầu. R4 phản xạ, đối xứng, bắc cầu. 1.2.7.3 Quan hệ tương đương Định nghĩa 1.8: Quan hệ hai ngôi R trên X ≠ φ được gọi là quan hệ tương đương nếu có ba tính chất phản xạ, đối xứng, bắc cầu. Với quan hệ tương đương R ta thường viết x ~ y()R hoặc x ~ y thay cho xRy . Ta định nghĩa và ký hiệu lớp tương đương của phần tử x ∈ X là tập hợp x={ y ∈ X y~ x}. Mỗi phần tử bất kỳ của lớp tương đương x được gọi là phần tử đại diện của x . Người ta cũng ký hiệu lớp tương đương của x là cl()x . Hai lớp tương đương bất kỳ thì hoặc bằng nhau hoặc không giao nhau, nghĩa là x ∩ x' hoặc bằng x = x' hoặc bằng φ , nói cách khác các lớp tương đương tạo thành một phân hoạch các tập con của X. Tập tất cả các lớp tương đương được gọi là tập hợp thương, ký hiệu X ~ . Vậy X~ ={ x x ∈ X}. Ví dụ 1.9: Quan hệ R4 trong ví dụ 1.7 là một quan hệ tương đương gọi là quan hệ đồng dư môđulô m trên tập các số nguyên . Nếu x ~ y , ta viết x ≡ y(mod m ) . Ta ký hiệu tập thương gồm m số đồng dư môđulô m: m = {0, 1, ,m − 1}. Ví dụ 1.10: Trong tập hợp các véc tơ tự do trong không gian thì quan hệ "véc tơ ur bằng véc tơ vr " là một quan hệ tương đương. Nếu ta chọn gốc O cố định thì mỗi lớp tương đương bất kỳ đều có thể chọn véc tơ đại diện dạng OA . 1.2.7.4 Quan hệ thứ tự Định nghĩa 1.8: Quan hệ hai ngôi R trên X ≠ φ được gọi là quan hệ thứ tự nếu có ba tính chất phản xạ, phản đối xứng, bắc cầu. Ví dụ 1.11: 1) Trong , , , quan hệ ""x ≤ y là một quan hệ thứ tự. 13
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số 2) Trong quan hệ ""xM y là một quan hệ thứ tự. 3) Trong P ()X , tập hợp tất cả các tập con của X , quan hệ "tập con" ( A ⊂ B ) là một quan hệ thứ tự. Khái niệm quan hệ thứ tự được khái quát hoá từ khái niệm lớn hơn (hay đứng sau) trong các tập số, vì vậy theo thói quen người ta cũng dùng ký hiệu ""≤ cho quan hệ thứ tự bất kỳ. Quan hệ thứ tự ""≤ trên tập X được gọi là quan hệ thứ tự toàn phần nếu hai phần tử bất kỳ của X đều so sánh được với nhau. Nghĩa là với mọi x, y∈ X thì x ≤ y hoặc y ≤ x . Quan hệ thứ tự không toàn phần được gọi là quan hệ thứ tự bộ phận. Tập X với quan hệ thứ tự ""≤ được gọi là tập được sắp. Nếu ""≤ là quan hệ thứ tự toàn phần thì X được gọi là tập được sắp toàn phần hay sắp tuyến tính. Ví dụ 1.12: Các tập ( ,≤), ( ,≤ ), ( ,≤ ), (,) ≤ được sắp toàn phần, còn ( ,M) và (P (X ),⊂) được sắp bộ phận (nếu X có nhiều hơn 1 phần tử). Định nghĩa 1.9: Cho tập được sắp (,)X ≤ và tập con A ⊂ X . Tập A được gọi là bị chặn trên nếu tồn tại q∈ X sao cho a≤ q , với mọi a∈ A. Khi đó q được gọi là một chặn trên của A. Hiển nhiên rằng nếu q là một chặn trên của A thì mọi p ∈ X mà q ≤ p đều là chặn trên của A. Phần tử chặn trên nhỏ nhất q của A ( theo nghĩa q≤ q', với mọi chặn trên q' của A) được gọi là cận trên của A và được ký hiệu q = sup A . Rõ ràng phần tử cận trên nếu tồn tại là duy nhất. Tương tự tập A được gọi là bị chặn dưới nếu tồn tại p ∈ X sao cho p ≤ a , với mọi a∈ A. Phần tử chặn dưới lớn nhất được gọi là cận dưới của A và được ký hiệu inf A . Cận dưới nếu tồn tại cũng duy nhất. Nói chung sup A, inf A chưa chắc là phần tử của A. Nếu q =sup A ∈ A thì q được gọi là phần tử lớn nhất của A ký hiệu q = max A . Tương tự nếu p =inf A ∈ A thì p được gọi là phần tử bé nhất của A ký hiệu p = min A. Ví dụ 1.13: Trong (,) ≤ , tập A = [0;1) = {x∈ 0≤ x < 1} có 1= sup A ∉ A , inf A = 0∈ A do đó không tồn tại max A nhưng tồn tại min A = inf A = 0 . 14
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số 1.3 ÁNH XẠ 1.3.1 Định nghĩa và ví dụ Khái niệm ánh xạ được khái quát hoá từ khái niệm hàm số trong đó hàm số thường được cho dưới dạng công thức tính giá trị của hàm số phụ thuộc vào biến số. Chẳng hạn, hàm số y = 2x với x∈ là quy luật cho ứng 0a 0,1 a 2, 2a 4,3 a 6, Ta có thể định nghĩa ánh xạ một cách trực quan như sau: Định nghĩa 1.10: Một ánh xạ từ tập X vào tập Y là một quy luật cho tương ứng mỗi một phần tử x ∈ X với một phần tử duy nhất y = f ()x của Y . f Ta ký hiệu f: X⎯⎯→ Y hay X ⎯⎯→Y x a y = f ()x x a y = f ()x X được gọi là tập nguồn, Y được gọi là tập đích. Ví dụ 1.14: • • • • • • • • • • • • • • • • • • • • • • • • X Y X Y X Y Trong 3 tương ứng trên chỉ có tương ứng thứ 3 xác định một ánh xạ từ X vào Y . Ví dụ 1.15: Mỗi hàm số y = f ()x bất kỳ có thể được xem là ánh xạ từ tập D là miền xác định của y = f ()x vào . Chẳng hạn: * Hàm lôgarit y = ln x là ánh xạ ln :+ → x a y = ln x Hàm căn bậc hai y= x là ánh xạ :+ → xa y= x . Định nghĩa 1.11: Cho ánh xạ f : X → Y và A ⊂ X , B ⊂ Y . f()() A={ f x x ∈ A} (1.5) 15
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số được gọi là ảnh của A qua ánh xạ f . Nói riêng f ()X = Im f được gọi là tập ảnh hay tập giá trị của f . −1 f() B={ x ∈ X f() x ∈ B} (1.6) được gọi là nghịch ảnh của tập con B của Y . −1 −1 Khi B là tập hợp chỉ có một phần tử {y} thì ta viết f() y thay cho f({} y ). Vậy −1 f() y={ x ∈ X y = f() x }. (1.7) 1.3.2 Phân loại các ánh xạ Định nghĩa 1.12: 1) Ánh xạ f : X → Y được gọi là đơn ánh nếu ảnh của hai phần tử phân biệt là hai phần tử phân biệt. Nghĩa là: Với mọi x1,; x 2∈ X x 1≠ x 2⇒ f()() x 1≠ f x 2 hay một cách tương đương, với mọi x1,; x 2 ∈ X . f()() x1= f x 2 ⇒ x 1 = x 2 (1.8) 2) Ánh xạ f : X → Y được gọi là toàn ánh nếu mọi phần tử của Y là ảnh của phần tử nào đó của X . Nghĩa là f ()X = Y hay ∀y ∈Y, ∃x ∈ X sao cho y = f ()x . (1.9) 3) Ánh xạ f : X → Y vừa đơn ánh vừa toàn ánh được gọi là song ánh. Chú ý 1.2: Khi ánh xạ f : X → Y được cho dưới dạng công thức xác định ảnh y = f ()x thì ta có thể xác định tính chất đơn ánh, toàn ánh của ánh xạ f bằng cách giải phương trình: y = f (x ), y ∈Y (1.10) trong đó ta xem x là ẩn và y là tham biến. ♦ Nếu với mọi y∈Y phương trình (1.10) luôn có nghiệm x ∈ X thì ánh xạ f là toàn ánh. ♦ Nếu với mỗi y∈Y phương trình (1.10) có không quá 1 nghiệm x ∈ X thì ánh xạ f là đơn ánh. ♦ Nếu với mọi y∈Y phương trình (1.10) luôn có duy nhất nghiệm x ∈ X thì ánh xạ f là song ánh. 16
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số Ví dụ 1.16: Cho ánh xạ f : → xa y= f( x )= x ( x + 1) 2 2 Xét phương trình y= f( x ) = x ( x + 1) = x + x hay x+ x − y = 0. Biệt số Δ = 1+ 4y > 0 (vì y ∈). Phương trình luôn có 2 nghiệm thực x1 =( −1 + 1 + 4y) 2, x2 =( − 1 − 1 + 4y ) 2. Vì x2 f x 2 là các song ánh từ tập xác định lên miền giá trị của nó. Ví dụ 1.18: Giả sử A là tập con của X thì ánh xạ i : A → X xa i() x= x là một đơn ánh gọi là nhúng chính tắc. Đặc biệt khi A = X ánh xạ i được ký hiệu Id X gọi là ánh xạ đồng nhất của X . Ví dụ 1.19: Giả sử ~ là một quan hệ tương đương thì ánh xạ sau là một toàn ánh p: X → X ~ xa p() x= x 1.3.3 Ánh xạ ngược của một song ánh Định nghĩa 1.13: Giả sử f : X → Y là một song ánh khi đó với mỗi y ∈Y tồn tại duy nhất x ∈ X sao cho y = f ()x . Như vậy ta có thể xác định một ánh xạ từ Y vào X bằng cách cho ứng mỗi phần tử y ∈Y với phần tử duy nhất x ∈ X sao cho y = f (x) . Ánh xạ này được −1 gọi là ánh xạ ngược của f và được ký hiệu f . −1 −1 Vậy f: Y→ X và f() y= x ⇔ y = f() x . (1.11) −1 f cũng là một song ánh. 17
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số x Ví dụ 1.20: Hàm mũ y= a, a > 0, a ≠ 1 là một song ánh (vì hàm mũ đơn điệu chặt) có hàm ngược là hàm lôgarit x y= a ⇔ x = loga y . Ví dụ 1.21 Các hàm lượng giác ngược Xét hàm sin :[− π 2;π 2]→ [− 1;1] x a sin x đơn điệu tăng chặt và toàn ánh nên nó là một song ánh. Hàm ngược được ký hiệu arcsin :[]− 1;1 → [−π 2;π 2] y a arcsin y x= arcsin y⇔ y = sin x ,∀ x∈[− 1;1] , y ∈[−π 2;π 2]. Tương tự hàm cos :[][ 0;π → − 1;1] đơn điệu giảm chặt có hàm ngược arccos:[][− 1;1 → 0;π ]; x = arccos y⇔ y = cos x . Hàm ngược arctg, arcotg được xác định như sau x=arctg y ⇔ y =tg x , ∀ x ∈(− ∞ ;∞) ,y ∈(− π 2;π 2). x = arccot g y⇔ y= cot g x ,∀ x ∈(− ∞ ;∞) ,y ∈( 0;π ). 1.3.4 Hợp (tích) của hai ánh xạ f g Định nghĩa 1.14: Với hai ánh xạ X →Y →Z thì tương ứng x a g(f (x )) xác định một ánh xạ từ X vào Z được gọi là hợp (hay tích) của hai ánh xạ f và g , ký hiệu g o f . Vậy g o f : X → Z có công thức xác định ảnh g o f (x )= g (f (x )) . (1.12) Ví dụ 1.22: Cho f :,:→ g → với công thức xác định ảnh f (x )= sinx , 2 g( x )= 2 x + 4 . Ta có thể thiết lập hai hàm hợp g o f và f o g từ vào . 2 2 fo g( x )= sin(2 x + 4), go f ( x )= 2sin x + 4 . Qua ví dụ trên ta thấy nói chung f og ≠ g o f , nghĩa là phép hợp ánh xạ không có tính giao hoán. 18
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số −1 Nếu f : X → Y là một song ánh có ánh xạ ngược f: Y→ X , khi đó ta dễ dàng −1 −1 kiểm chứng rằng fo f= Id X và fo f= IdY . Hơn nữa ta có thể chứng minh được rằng ánh xạ f : X → Y là một song ánh khi và chỉ khi tồn tại ánh xạ g :Y → X sao cho −1 go f= Id X và fo g= IdY , lúc đó g= f . 1.3.5 Lực lượng của một tập hợp Khái niệm lực lượng của tập hợp có thể xem như là sự mở rộng khái niệm số phần tử của tập hợp. Định nghĩa 1.15: Hai tập hợp X ,Y được gọi là cùng lực lượng nếu tồn tại song ánh từ X lên Y . Tập cùng lực lượng với tập {1,2, ,n} được gọi là có lực lượng n . Vậy X có lực lượng n khi và chỉ khi X có n phần tử. n còn được gọi là bản số của X , ký hiệu Card X hay X . Quy ước lực lượng của φ là 0. Định nghĩa 1.16: Tập có lực lượng n hoặc 0 được gọi là các tập hữu hạn. Tập không hữu hạn được gọi là tập vô hạn. Tập có cùng lực lượng với tập các số tự nhiên hay hữu hạn được gọi là tập đếm được. Chú ý 1.3: 1) Tập vô hạn đếm được là tập cùng lực lượng với . 2) Bản thân tập là tập vô hạn đếm được. 3) Người ta chứng minh được , là tập vô hạn đếm được, còn tập không đếm được. 4) Giả sử X ,Y là hai tập hữu hạn cùng lực lượng. Khi đó ánh xạ f : X → Y là đơn ánh khi và chỉ khi là toàn ánh, do đó là một song ánh. 1.4 GIẢI TÍCH TỔ HỢP- NHỊ THỨC NEWTON 1.4.1 Hoán vị, phép thế Cho tập hữu hạn E= { x1, x 2 , xn}. Mỗi song ánh từ E lên E được gọi là một phép thế, còn ảnh của song ánh này được gọi là một hoán vị n phần tử của E . Nếu ta xếp các phần tử của E theo một thứ tự nào đó thì mỗi hoán vị là một sự đổi chỗ các phần tử này. Đặc biệt nếu E= {1,2, n} thì mỗi phép thế được ký hiệu bởi ma trận ⎡ 1 2 n ⎤ σ = ⎢ ⎥ (1.13) ⎣σ(1) σ (2) σ (n )⎦ 19
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số trong đó hàng trên là các số từ 1 đến n sắp theo thứ tự tăng dần, hàng dưới là ảnh tương ứng của nó qua song ánh σ . Còn [σ (1),σ (2), ,σ (n )] là hoán vị của phép thế σ . ⎡1 2 3 4⎤ Ví dụ 1.23: [4 2 1 3] là hoán vị từ phép thế σ = ⎢ ⎥ có σ (1)= 4, ⎣4 2 1 3⎦ σ (2)= 2 , σ (3)= 1, σ (4)= 3. Tập hợp {2,1 } có hai hoán vị là [1 2] và [2 1]. Tập hợp {3,2,1 } có sáu hoán vị là [1 2 3], [2 1 3], [31 2], [1 3 2], []2 3 1 và []3 2 1 . Với tập E= { x1, x 2 , , xn} thì có n cách chọn giá trị σ ()x1 , n −1 cách chọn giá trị σ ()x2 cho một phép thế σ bất kỳ. Vậy có n( n− 1)( n − 2) 1 = n ! hoán vị (phép thế) của tập n phần tử. 1.4.2 Chỉnh hợp Cho tập hợp hữu hạn có n phần tử E= { x1, x 2 , , xn} và tập hợp hữu hạn B = {}1,2, , p . Định nghĩa 1.17: Một chỉnh hợp lặp chập p các phần tử của E là ảnh của một ánh xạ từ B đến E . Ta cũng có thể xem một chỉnh hợp lặp chập p như một bộ gồm p thành phần là các phần tử có thể trùng nhau của E . Nói cách khác, một chỉnh hợp lặp chập p là một phần tử của tích p p Descartes E . Vậy số các chỉnh hợp lặp chập p của n vật là n . Ví dụ 1.24: Cho n vật E= { x1, x 2 , , xn} và tiến hành bốc có hoàn lại p lần theo cách sau: Bốc lần thứ nhất từ tập E được x , ta trả x lại cho E và bốc tiếp lần thứ hai Mỗi kết i1 i1 quả sau p lần bốc x, x , , x là một chỉnh hợp có lặp n chập p . ( i1 i 2 i p ) Định nghĩa 1.18: Một chỉnh hợp (không lặp) chập p gồm n phần tử của E ()p ≤ n là ảnh của một đơn ánh từ B vào E . Hai chỉnh hợp n chập p là khác nhau nếu: hoặc chúng có ít nhất một phần tử khác nhau, hoặc gồm p phần tử như nhau nhưng có thứ tự khác nhau. Như vậy ta có thể xem mỗi chỉnh hợp là một bộ có p thành phần gồm các phần tử khác nhau của E hay có thể xem như một cách sắp xếp n phần tử của E vào p vị trí. 20
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số Có n cách chọn vào vị trí thứ nhất, n −1 cách chọn vào vị trí thứ hai, và n − p +1 cách chọn vào vị trí thứ p . Vậy số các chỉnh hợp n chập p là p n! A= n( n − 1) ( n − p + 1) = (1.14) n (n− p )! 1.4.3 Tổ hợp Định nghĩa 1.19: Một tổ hợp n vật của E chập p là một cách lấy ra đồng thời p vật từ E có n vật. Như vậy ta có thể xem một tổ hợp n chập p là một tập con p phần tử của tập có n phần tử E . Nếu ta hoán vị p vật của một tổ hợp thì ta có các chỉnh hợp khác nhau của cùng p vật này. p Vậy ứng với một tổ hợp p vật có đúng p! chỉnh hợp của p vật này. Ký hiệu Cn là số các tổ hợp n chập p thì p p A n! C =n = . (1.15) n p! p!( n− p )! Ví dụ 1.25: a) Có bao nhiêu cách bầu một lớp trưởng, một lớp phó và một bí thư chi đoàn mà không kiêm nhiệm của một lớp có 50 học sinh. b) Có bao nhiêu cách bầu một ban chấp hành gồm một lớp trưởng, một lớp phó và một bí thư chi đoàn mà không kiêm nhiệm của một lớp có 50 học sinh. Giải: a) Mỗi kết quả bầu là một chỉnh hợp 50 chập 3. 3 Vậy có A50 =50 × 49 × 48 = 117.600 cách bầu. b) Mỗi kết quả bầu một ban chấp hành là một tổ hợp 50 chập 3. 3 50! 50× 49× 48 Vậy có C = = = 19.600 cách bầu. 50 3!47! 6 1.4.4 Nhị thức Niu-tơn n Xét đa thức bậc n : (x+ 1) = ( x + 1)( x + 1) ( x + 1) 14244 4344 n thõa sè Khai triển đa thức này ta được: n n n−1 n−2 (x+ 1) = x + an−1 x+ an−2 x + + 1 21
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số p Hệ số của x bằng số cách chọn p thừa số trong n thừa số trên. Mỗi cách chọn là một tổ p hợp n chập p , do đó ap= C n . n n n n−1 n− 1 p p 0 Vậy (x+ 1) = Cn x + Cn x + +Cn x + + Cn Thay x= a b (nếu b ≠ 0) ta có: n n n n n−1 n − 1 0 n p p n− p ()ab+ = CaCabn + n + + Cbn = ∑ Cabn (1.16) p=0 Công thức này được gọi là nhị thức Niu-tơn, đúng với mọi a, b∈ (kể cả trường hợp b = 0 ). 1.4.5 Sơ lược về phép đếm Khi muốn đếm số phần tử của các tập hữu hạn ta có thể áp dụng các cách đếm hoán vị, chỉnh hợp, tổ hợp và các công thức sau: a) ABABAB∪ + ∩ = + , (công thức cộng) (1.17) b) ABAB× = ⋅ , (công thức nhân) (1.18) B c) {}f: A→ B = A , (chỉnh hợp có lặp) (1.19) A d) P (A )= 2 , (1.20) e) Nếu f : A → B song ánh thì AB= . (1.21) Công thức cộng a) thường được sử dụng trong trường hợp đặc biệt khi A, B rời nhau A ∩B = φ , lúc đó ABAB∪ = + . Công thức nhân b) có thể mở rộng cho k tập bất kỳ AAAA1 × × k = 1 ⋅ ⋅ k (1.22) Hoặc nếu một hành động H gồm k giai đoạn AA1, , k . Mỗi giai đoạn Ai có thể thực hiện theo ni phương án thì cả thảy có n1 × × nk phương án thực hiện H. 22
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số Ví dụ 1.26: Cho mạch điện U 3 U 2 U1 A B a) Có bao nhiêu trạng thái của mạch. b) Có bao nhiêu trạng thái có thể của mạch để có dòng điện chạy từ A đến B Giải: Áp dụng công thức nhân ta có: 2 3 4 9 a) Số các trạng thái của mạch 2 .2 .2= 2= 512 . 2 b) Ở U1 có 2 trạng thái nhưng có 1 trạng thái dòng điện không qua được, do đó ở U1 3 4 có 3 trạng thái dòng điện qua được. Tương tự ở U 2 có 2− 1 và ở U3 có 2− 1 trạng thái dòng điện qua được. Vậy số các trạng thái của mạch có dòng điện chạy từ A đến B là 3× 7 × 15 = 315 . Ví dụ 1.27: Có bao nhiêu số tự nhiên viết dưới dạng thập phân có n chữ số (n ≥ 3) trong đó có đúng hai chữ số 8. Giải: Giả sử N là số tự nhiên có n chữ số mà chữ số thứ nhất bên trái khác chữ số 0 và có đúng hai chữ số 8. ♦Trường hợp 1: Nếu chữ số thứ nhất bên trái là chữ số 8 thì có n −1 vị trí để đặt chữ số 8 n−2 thứ hai, có 9 cách chọn cho mỗi chữ số ở n − 2 vị trí còn lại. Vậy có đúng (n − 1)9 số N thuộc loại này. 2 ♦Trường hợp 2: Nếu chữ số thứ nhất bên trái không phải là chữ số 8 thì có Cn−1 vị trí để đặt 2 chữ số 8, có 8 cách chọn chữ số cho vị trí thứ nhất, có 9 cách chọn cho mỗi chữ số ở n − 3 vị trí khác vị trí thứ nhất và hai vị trí đã chọn cho chữ số 8. Vậy có đúng 2 n−3 (n− 1)( n − 2) n−3 C ⋅8 ⋅ 9 = ⋅8 ⋅ 9 số N thuộc loại này. n−1 2 Sử dụng công thức cộng ta suy ra số các số tự nhiên cần tìm là: n−2 n−3 n−3 (n − 1)9 + 4(n − 1)( n − 2)9 = (4n + 1)( n − 1)9 23
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số Ví dụ 1.28: Trong mặt phẳng cho n đường thẳng đôi một cắt nhau và các giao điểm này khác nhau (n ≥ 4) . a) Tìm số các giao điểm của chúng. b) Tìm số các đường thẳng mới được tạo bởi các giao điểm trên. Giải: A D j n = 4 a) Số các giao điểm của n đường thẳng bằng số các cặp của n đường thẳng này. Vậy có 2 Cn giao điểm. 2 b) Xét tại điểm A bất kỳ trong Cn giao điểm của câu a). Tồn tại đúng hai đường trong n đường trên đi qua A là Di,; D j i< j . 2 Trên mỗi đường có đúng n −1 điểm trong số Cn giao điểm của câu a). Vậy trên DDi, j có 2(n − 1)− 1điểm, do đó có 2 (n− 2)( n − 3) C−(2( n − 1) − 1) = đường thẳng mới nối đến A. Vì mỗi đường n 2 thẳng mới đều nối hai điểm ở câu a) nên số đường thẳng mới là: 1 2 (n− 2)( n − 3) 1 C =n( n − 1)( n − 2)( n − 3) . 2 n 2 8 Ví dụ 1.29: Cho tập con A có p phần tử của tập E có n phần tử. Hãy đếm số các cặp (,)X Y các tập con của E sao cho: 24
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số X ∪Y = E, X ∩ Y ⊃ A (1.23) Giải: Ký hiệu B = E \ A. Đặt A = {()XYXYEXYA, ∪ = , ∩ ⊃ } B = {(XYXBYBXYB', ') '⊂ , ' ⊂ ; ' ∪ '= } Tương ứng f : AB→ ; f (,)(,)X Y a X ∩ B Y ∩ B là một song ánh. Mặt khác X ',',''⊂B Y ⊂B X ∪Y = B ⇔ B \ X '⊂ Y'. Vậy số các cặp (,)X Y thoả mãn điều kiện (1.23) cần tìm bằng bản số của tập {(",')"XYXBYBXY⊂ ,' ⊂ ," ⊂ '}. y' Với mỗi tập Y'⊂ B có bản số y' thì bản số của tập {XXY""'⊂ } là 2 ; Số các tập y' con Y'⊂ B có y' phần tử là Cn− p . Áp dụng công thức cộng suy ra bản số cần tìm là n− p y''y n− p ∑ 2 Cn− p = 3 . y'= 0 1.5 CÁC CẤU TRÚC ĐẠI SỐ 1.5.1 Luật hợp thành trong Định nghĩa 1.20: Một luật hợp thành trong trên tập X ≠ φ là ánh xạ từ X × X vào X . Ta thường ký hiệu :* XXX× → (,)*x y a x y Luật hợp thành trong kết hợp hai phần tử x, y của X thành một phần tử x ∗ y của X vì vậy luật hợp thành trong còn được gọi là phép toán hai ngôi. Ví dụ 1.30: Phép cộng và phép nhân là các luật hợp thành trong của các tập số , , , , . Ví dụ 1.31: Phép cộng véc tơ theo quy tắc hình bình hành là phép toán trong của tập R3 các véc tơ tự do trong không gian, nhưng tích vô hướng không phải là phép toán trong vì r r r r r r u⋅ v = u ⋅ vcos( u , v ) ∉ R3 . Định nghĩa 1.21: Luật hợp thành trong * của tập X được gọi là: 1) Có tính kết hợp nếu ∀x,,:()()y z∈ X x ∗ y∗ z = x ∗ y∗ z 25
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số 2) Có tính giao hoán nếu ∀x,:y∈ X x ∗ y= y ∗ x 3) Có phần tử trung hoà (hay có phần tử đơn vị) là e∈ X nếu ∀x ∈X : x ∗e = e ∗x = x 4) Giả sử * có phần tử trung hoà e∈ X . Phần tử x'∈ X được gọi là phần tử đối xứng của x ∈ X nếu x ∗ x''= x ∗x = e . Ta dễ dàng thấy rằng phần tử trung hoà có phần tử đối xứng là chính nó. Các phép hợp thành trong hai ví dụ trên đều có tính kết hợp và giao hoán. Số 0 là phần tử r trung hoà đối với phép cộng và 1 là phần tử trung hoà đối với phép nhân trong. Véc tơ 0 là phần tử trung hoà của phép toán cộng véc tơ trong R3 . Đối với phép cộng thì mọi phần tử x trong , , , đều có phần tử đối là − x . Phần tử đối của x ≠ 0 ứng với phép nhân trong , , là 1 x , nhưng mọi phần tử khác 0 trong với phép + không có phần tử đối. Tính chất 1.4: 1) Phần tử trung hoà nếu tồn tại là duy nhất. 2) Nếu * có tính kết hợp, thì phần tử đối của mỗi phần tử là duy nhất. 3) Nếu * có tính kết hợp và phần tử a có phần tử đối thì có luật giản ước: a ∗x =a ∗ y ⇒x = y và phương trình a ∗ x = b có duy nhất nghiệm x =a' ∗ b với a' là phần tử đối của a . Chứng minh: 1) Giả sử e và e' là hai phần tử trung hoà thì e''= e∗ e= e (dấu "=" thứ nhất có được do e là phần tử trung hoà, còn dấu "=" thứ hai là do e' là phần tử trung hoà). 2) Giả sử a có hai phần tử đối xứng là a' và a" , khi đó: aea'= ∗ '(")'"( = aaaaaa∗ ∗ = ∗ ∗ ')"= aea∗ = " . Theo thói quen ta thường ký hiệu các luật hợp thành trong có tính giao hoán bởi dấu ""+ , khi đó phần tử trung hoà được ký hiệu là 0 và phần tử đối của x là − x . Nếu ký hiệu luật hợp thành bởi dấu nhân "." thì phần tử trung hoà được ký hiệu 1 và gọi là phần tử đơn vị, phần tử đối của x là x−1. 1.5.2 Nhóm Định nghĩa 1.22: Giả sử G là tập khác trống với luật hợp thành *, cặp (G ,*) được gọi là một vị nhóm nếu thoả mãn hai điều kiện sau: G1: * có tính kết hợp. 26
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số G2: * có phần tử trung hoà e . Vị nhóm (G ,*) là một nhóm nếu thoả mãn thêm điều kiện: G3: Mọi phần tử của G đều có phần tử đối. Nhóm (G ,*) được gọi là nhóm giao hoán hay nhóm Abel nếu : G4: * có tính giao hoán. * Ví dụ 1.32: (,) + , (,) + , (,) + , (,) + , (,)R3 + , ( *,⋅ ) , ( *,⋅ ) , (,)+ ⋅ , * (,)+ ⋅ , ( *,⋅ ) là các nhóm Abel. Chú ý 1.5: Một nhóm là tập khác rỗng G với luật hợp thành * thoả mãn G1, G2, G3, nhưng nếu * đã xác định và không sợ nhầm lẫn thì ta nói tắt nhóm G thay cho nhóm (G ,*) . Định nghĩa 1.23: Đồng cấu nhóm từ nhóm (G ,*) vào nhóm (',)G là ánh xạ f :'GG→ sao cho ∀x,:()()()y ∈ G f x ∗y = f x f y . (1.24) Nếu f đơn ánh (toàn ánh, song ánh) thì f được gọi là đơn cấu (toàn cấu, đẳng cấu, một cách tương ứng). * * loga :+ → ; 0 <a ≠ 1 là một đẳng cấu nhóm từ nhóm (,)+ ⋅ lên nhóm (,) + . 1.5.3 Vành Định nghĩa 1.24: Giả sử trên tập A ≠ φ có hai luật hợp thành trong ký hiệu bởi dấu cộng và dấu nhân, khi đó (,,)A + ⋅ được gọi là một vành nếu: A1: (,)A + là một nhóm Abel, A2: Luật nhân có tính kết hợp, A3: Luật nhân có tính phân phối hai phía đối với luật cộng, nghĩa là: ∀x,,:()y z ∈A x ⋅y + z = x ⋅ y + x ⋅ z phân phối bên trái ∀x,,:()y z ∈A x +y ⋅ z = x ⋅ z+ y⋅ z phân phối bên phải Nếu thoả mãn thêm điều kiện: A4: Luật nhân có tính giao hoán thì (,,)A + ⋅ là vành giao hoán. A5: Luật nhân có phần tử đơn vị là 1 thì (,,)A + ⋅ là vành có đơn vị. 27
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số Chú ý 1.6: 1) Tồn tại vành giao hoán nhưng không có đơn vị và ngược lại. 2) Ta nói tắt vành A thay cho vành (,,)A + ⋅ . Định nghĩa 1.25: 1) Phần tử x ≠ 0 của A được gọi là ước của 0 nếu tồn tại y ∈A,y ≠ 0 sao cho x ⋅y = 0 ( 0 là phần tử trung hoà của luật cộng của vành (,,)A + ⋅ ). 2) Vành không có ước của 0 được gọi là vành nguyên. Vậy vành (,,)A + ⋅ là vành nguyên khi và chỉ khi mọi x, y ∈ A sao cho x ⋅y = 0 thì x = 0 hoặc y = 0 . Ví dụ 1.33: 1) (,,) + ⋅ là một vành nguyên. 2) Ký hiệu C[;]a b là tập hợp các hàm liên tục trên đoạn [;]a b . Ta định nghĩa phép cộng và phép nhân trong C[;]a b xác định như sau: ∀f, g ∈ C[;]a b : ( f+ g )( x )= f ( x )+ g ( x ); fg ( x )= f ( x ) g ( x ) Ta có thể kiểm chứng được rằng với hai phép toán này thì C[;]a b là một vành giao hoán có đơn vị và có ước của 0. 3) (K[ x ],+ , ⋅) là một vành nguyên, trong đó K[]x là tập các đa thức của biến x có hệ số thuộc vào vành số K = ,,, . 4) Tập n = mod n các số đồng dư môđulô n . Ta có thể chứng minh được rằng nếu x ≡ x'(modn ) , y≡ y'(mod n ) thì x +y ≡x'' + y(mod n ) và xy ≡ x''y(mod n ) . Vì vậy ta có thể định nghĩa phép cộng và phép nhân trong n bởi: x+ y = x + y và x⋅ y = x ⋅ y (1.25) Chẳng hạn 5(mod 7)+ 4(mod 7)= 2(mod 7) 5(mod 7)⋅ 4(mod 7) = − 1(mod 7)= 6(mod 7) . Với hai phép toán này (,,)n + ⋅ là một vành giao hoán có đơn vị. 28
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số 1.5.4 Trường Định nghĩa 1.26: Vành giao hoán có đơn vị (,,)K + ⋅ được gọi là một trường nếu mọi phần tử x ≠ 0 của K đều khả nghịch (có phần tử đối của luật nhân). Nghĩa là: K1: (,)K + là nhóm Abel, K2: (K *,⋅ ) là nhóm Abel, K* = K \ }0{ , K3: Luật nhân phân phối đối với luật cộng. Rõ ràng rằng mọi trường là vành nguyên, nhưng điều ngược lại không đúng. (,,) + ⋅ là một ví dụ về vành giao hoán nguyên có đơn vị nhưng không phải là trường. Ví dụ 1.34: (,,) + ⋅ , (,,) + ⋅ , (,,) + ⋅ là trường. Ví dụ 1.35: (,,)n + ⋅ là trường khi và chỉ khi n là số nguyên tố. Giải: Giả sử n là số nguyên tố và m ∈ n , m ≠ 0(modn ) thì (m , n )= 1 do đó tồn tại hai số nguyên u, v sao cho um+ vn = 1 (Định lý Bezout) ⇒u⋅ m = 1(modn ) . Vậy u là phần tử nghịch đảo của m . Ngược lại, nếu n là trường thì với mọi m ∈ ( 0 < m< n ) tồn tại m'∈ sao cho: m⋅ m'= 1⇒ mm '= 1+ kn⇒ ( m , n )= 1 Vậy n là số nguyên tố. 1.6 ĐẠI SỐ BOOLE Lý thuyết đại số Boole được George Boole (1815 - 1864) giới thiệu vào năm 1854 trong bài báo "Các quy luật của tư duy", trong đó kỹ thuật đại số được dùng để phân tích các quy luật của lôgích và các phương pháp suy diễn. Sau đó đại số Boole được áp dụng trong các lĩnh vực khác nhau của toán học như đại số, giải tích, xác suất Vào khoảng năm 1938, Claude Shannon (Clau Sê-nôn) ( một kỹ sư viễn thông người Mỹ) là người đầu tiên đã áp dụng đại số Boole vào lĩnh vực máy tính điện tử và lý thuyết mạng. 1.6.1 Định nghĩa và các tính chất cơ bản của đại số Boole Định nghĩa 1.27: Một đại số Boole (,,,')B ∨ ∧ là một tập khác trống B với hai phép toán hai ngôi ∨,: ∧B ×B → B và phép toán một ngôi :' B → B thoả mãn các tiên đề sau: • B1: ∨, ∧ có tính kết hợp, nghĩa là với mọi a,, b c∈ B 29
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số abc∨()(),()() ∨ = abcabc ∨ ∨ ∧ ∧ = abc∧ ∧ • B2: ∨, ∧ có tính giao hoán, nghĩa là với mọi a, b∈ B a∨ b = b ∨ a, a ∧ b = b ∧ a • B3: Tồn tại các phần tử không và phần tử đơn vị 0,1∈ B sao cho 0≠ 1 và với mọi a∈ B a∨0 = a , a∧ 1 = a • B4: Với mọi a∈ B thì a'∈ B là phần tử đối theo nghĩa là: a∨ a'= 1, a∧ a ' = 0 • B5: Luật ∨ phân phối đối với luật ∧ và luật ∧ phân phối đối với luật ∨ , nghĩa là với mọi a,, b c∈ B abc∨( ∧ ) = ( ab ∨ ) ∧ ( acabc ∨ ),∧ (∨ )= ( ab∧ )∨ ( ac ∧ ) . Ví dụ 1.36: Giả sử X ≠ φ , xét P ()X là tập các tập con của X . Các luật hợp thành ∨, ∧ là phép hợp, phép giao các tập con của X và phép toán một ngôi ' là phép lấy phần bù của tập con trong X . Khi đó (P (X ),∪ ,∩ ,') là đại số Boole với phần tử không là φ và phần tử đơn vị là chính tập X . Ví dụ 1.37: Xét B2 = {}0;1 tập gồm hai số 0 và 1. Ta định nghĩa: a∨ b = max( a , b ) , a∧ b = min( a , b ) , a'= 1− a thì (,,,')B2 ∨ ∧ là một đại số Boole. Ví dụ 1.38: Xét B4 = {0;1; a ; b }, ta định nghĩa các phép toán ∨ 0 1 a b ∧ 0 1 a b ' 0 0 1 a b 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 a b 1 0 a a1 a 1 a0 a a 0 a b b b1 1 b b0 b 0 b b a thì (,,,')B4 ∨ ∧ là đại số Boole. Định nghĩa 1.28: Hai công thức Boole trong đại số Boole (,,,')B ∨ ∧ được gọi là đối ngẫu nếu trong một công thức ta thay ∨, ∧ ,0,1, bằng ∧,∨ ,1,0 thì ta được công thức hai. Ví dụ 1.39: Hai công thức x ∧(y ∨ 1) và x ∨ (y ∧ 0) là đối ngẫu. 30
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số Trong mỗi tiên đề của hệ tiên đề B1-B5 của đại số Boole đều chứa từng cặp công thức đối ngẫu nhau, vì vậy ta có nguyên lý đối ngẫu sau: Nguyên lý đối ngẫu: Nếu một công thức của đại số Boole được chứng minh là đúng dựa trên cơ sở hệ tiên đề B1-B5 thì công thức đối ngẫu của chúng cũng đúng. Chẳng hạn, ta sẽ chứng minh a ∨1= 1, do đó theo nguyên lý đối ngẫu ta cũng có a ∧0 = 0 . Tính chất 1.7: Giả sử (,,,')B ∨ ∧ là đại số Boole với phần tử không và đơn vị là 0, 1 thì với mọi a, b∈ B ta có: 1) a∨ a = a , a∧ a = a ; 2) 0'= 1, 1'= 0 ; 3) a ∨1 = 1, a ∧0 = 0 ; 4) a∨() a ∧ b = a , a∧() a ∨ b= a ; (tính hấp thu) 5) Nếu tồn tại c ∈ B sao cho a∨ c= b∨ c và a∧ c= b∧ c thì a= b ; 6) Nếu a∨ b = 1 và a∧ b = 0 thì b= a'; (tính duy nhất của phần bù) 7) (a∨ b )' = a '∧ b ' và (a∧ b )'= a '∨ b ' . (công thức De Morgan) Chứng minh: Theo nguyên lý đối ngẫu ta chỉ cần chứng minh các đẳng thức thứ nhất từ 1)-7). 1) a 3= a ∨ 0 B ot e h = 4a ∨(') a ∧ a B o t e h =()(')a ∨ a ∧ a ∨ a theo B5 = 4(a ∨ a ) ∧ 1 B o t e h = 3a ∨ a B ot e h 2) 0' 3= 0' ∨ 0 B ot e h =1 theo B2,B4 3) a∨1 = a ∨ ( a ∨ a ') theo B4 = 1()'a ∨ a ∨ a B o t e h =a ∨ a' theo 1) = 41 tB o e h 31
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số 4) a∨( a ∧ b )= ( a∧ 1) ∨ ( a∧ b ) theo B3 = 5a ∧(1 ∨ b B ) o t e h =a ∧1 theo 1) = a theo B3 5) a= a ∨() a ∧ c theo 4) =a ∨() b ∧ c vì a∧ c= b∧ c =()()a ∨ b ∧ a ∨ c theo B5 =()()a ∨ b ∧ b ∨ c vì a∨ c= b∨ c = 5b ∨() a ∧ c B o t e h =b ∨() b ∧ c vì a∧ c= b∧ c = b theo 4) 6) Vì a∨ b = 1= a∨ a ' và a∧ b= 0= a∧ a ' , theo 5) suy ra b= a' . 7) Ta dễ dàng kiểm chứng (a∨ b ) ∨ ( a '∧ b ')= 1 và (a∨ b )∧ ( a '∧ b ') = 0, áp dụng 6) suy ra điều phải chứng minh. Áp dụng các tính chất này cùng với hệ tiên đề B1-B5 ta có thể đơn giản hoá các công thức Boole bất kỳ. Ví dụ 1.40: Đơn giản hoá công thức Boole ()(')(')x ∧ y ∨ x ∧ y ∨x ∨ y . Giải: Ta có (x ∧y ) ∨ (x ∧y ') = x ∧ (y∨ y ')= x ∧ 1 = x . ⇒()(')(')x ∧y ∨x ∧y ∨x ∨ y =x ∨(x ' ∨y ) = (x ∨x ') ∨ y= 1∨ y = 1. Ví dụ 1.41: Đơn giản hoá công thức Boole (x∧ y ')∨ [ x∧ ( y∧ z )']∨ z . Giải: Ta có (x∧ y ') ∨[] x ∧ ( y ∧ z )' ∨ z =(')(')(')x ∧ y ∨[] x ∧ y ∨ x∧ z∨ z =(')(')(')()(')xy ∧ ∨ xzzxy ∧ ∨ = ∧ ∨[ xzzz ∨ ∧ ∨ ] 32
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số =(x ∧ y ') ∨[] ( x ∨ z )∧ 1 =(')()(')x ∧ y ∨ x ∨ z= [ x∧ y∨ x] ∨ z= x∨ z . Ví dụ 1.42: Đơn giản công thức ()(')(')x ∧ y∧ z ∨ x ∧ y∧ z ∨ x ∧ y∧ z Giải: Ta có (x ∧y ∧ z ) ∨ (x ∧ y∧ z ')∨ (x '∧ y∧ z ) =[]()(')()(')xyz ∧ ∧ ∨ xyz∧ ∧ ∨ [ xyz∧ ∧ ∨ xyz∧ ∧ ] =[]()(')()(')x ∧ y ∧ z ∨ z ∨ [ y∧ z∧ x∨ x ] =()()()x ∧y ∨ y ∧ z= y ∧ x ∨ z . 1.6.2 Ứng dụng đại số Boole vào mạng chuyển mạch (switching networks) Ta chỉ xét các mạng gồm các chuyển mạch có hai trạng thái đóng (dòng điện đi qua được) và mở (dòng điện không qua được). Hai mạng đơn giản nhất là mạng song song cơ bản (basic parallel network) và mạng nối tiếp cơ bản (basic series network) được mô tả trong hình vẽ sau: x • • • • x y y mạng song song cơ bản (hình 1) mạng nối tiếp cơ bản (hình 2) Một mạng bất kỳ có thể nhận được bằng cách ghép nối tiếp hay song song các mạng cơ bản này. Ta ký hiệu các chuyển mạch bởi các chữ x,y , z , Nếu x ở trạng thái mở ta x cho nhận giá trị 0 và ở trạng thái đóng ta cho x nhận giá trị 1. Trong một mạng nếu hai chuyển mạch luôn cùng trạng thái thì ta ký hiệu cùng một chữ. Hai chuyển mạch có trạng thái luôn ngược nhau, nếu một chuyển mạch được ký hiệu là x thì chuyển mạch kia được ký hiệu là x'. Mạng song song (hình 1) nhận giá trị 1 khi có ít nhất một trong hai chuyển mạch x, y nhận giá trị 1, ta ký hiệu x ∨ y . Còn mạng nối tiếp (hình 2) nhận giá trị 1 khi cả hai chuyển mạch x, y nhận giá trị 1, ta ký hiệu x ∧ y . Như vậy x',,x ∨ y x ∧ y có thể được xem như các biến nhận giá trị trong đại số Boole B2 (ví dụ 1.37). Bằng phương pháp này ta có thể mô tả một mạng bất kỳ bởi một công thức Boole và ngược lại. Chẳng hạn mạng sau đây: 33
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số y • • z x y' tương ứng với công thức ()(')y∨ z ∨ x ∧ y . Còn công thức Boole ()()(')x ∧z ∨ y∧ z∨ y ∧x mô tả mạng: x z y z x y' Chú ý rằng trong các công thức cần xét ta thay (x ∨ y )' bởi x'∧ y' và (x ∧ y )' bởi x''∨ y . Hai mạng N1 và N2 được gọi là tương đương nếu nó thực hiện cùng một chức năng, nghĩa là với bất kỳ cách chọn các trạng thái đóng mở ở mọi vị trí chuyển mạch trong mạng thì trạng thái đầu vào và đầu ra của N1 và N2 đều như nhau. Ta có thể áp dụng đại số Boole để giải quyết hai vấn đề sau: 1.6.3 Với một mạng cho trước tìm mạng tương đương đơn giản hơn Ví dụ 1.43: Tìm mạng tương đương đơn giản hơn của mạng sau x y • z • x w y w Công thức Boole tương ứng: []()()x∨ z∧ y∨ [( x∧ w∨ w)∧ y]. 34
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số Ta có ()x ∧w ∨ w = w (luật hấp thu), do đó công thức trên có thể biến đổi thành ][][()x∨ z ∧ y ∨ w ∧ y =() x ∨ z ∨ w∧ y . Vậy ta có mạng tương đương đơn giản hơn x • • y z w Ví dụ 1.43: Tìm mạng tương đương đơn giản hơn của mạng sau: z x z y • • y x z x z' Công thức Boole tương ứng: []()(')()()z∧ x∨ ( x∧ y∨ z) ∧ z∨ x∧ z∨ y . Ta có []()(')()()z∧ x ∨() x ∧ y ∨ z∧ z∨ x∧ z∨ y =[]()()(')()z ∧ x ∨() x ∧ y ∨ x∧ z∧ [ z∨ x∧ y ] =[]()x ∧(')()() z ∧ z ∨ x ∧ y∧ [ z∨ x∧ y ] =x ∧[] z ∨ ()()() x∧ y= x ∧ z ∨ [ x∧ x∧ y ] =()()()x ∧z ∨x ∧y =x ∧z ∨ y Vậy ta có mạng tương đương đơn giản hơn z • • x y 35
Chương 1: Mở đầu về lôgíc mệnh đề, tập hợp ánh xạ và các cấu trúc đại số 1.6.4 Thiết kế một mạng thoả mãn các điều kiện cho trước Ví dụ 1.45: Thiết kế một mạng điện cho một bóng đèn ở cầu thang mà có thể bật tắt ở cả hai đầu cầu thang. Giải: Gọi x và y là hai công tắc ở hai đầu cầu thang. Theo yêu cầu đặt ra ta cần thiết kế một mạng điện sao cho khi thay đổi trạng thái của một trong hai vị trí x, y thì trạng thái của đầu ra (bóng đèn) phải thay đổi. Ta biết rằng, mỗi mệnh đề logic cũng nhận hai giá trị, vì vậy ta có thể xem mệnh đề như một biến nhận giá trị trong B2 (ví dụ 1.37). Ta biết rằng mệnh đề x ⇔ y chứa hai mệnh đề x, y và mệnh đề này thay đổi giá trị khi một trong hai mệnh đề x hay y thay đổi giá trị. Mặc dù mệnh đề x ⇔ y hay ()()x ⇒y ∧ y ⇒ x không phải là công thức Boole nhưng nó có công thức tương đương dưới dạng công thức Boole (')(')x ∨ y∧ y ∨x . Ta có: (')(')'(')(')('')()xy∨ ∧ yxxyx ∨ =[] ∧ ∨ ∨ [ yyx∧ ∧ ] = xy∧ ∨ yx ∧ . Vậy mạng cần tìm là x y x' y' 36
Chương 2: Không gian Véc tơ 2. CHƯƠNG 2: KHÔNG GIAN VÉC TƠ 2.1 KHÁI NIỆM KHÔNG GIAN VÉC TƠ 2.1.1 Định nghĩa và các ví dụ Định nghĩa 2.1: Giả sử V là tập khác φ , K là một trường. V được gọi là không gian véc tơ trên trường K nếu có hai phép toán: - Phép toán trong +: VVV × → (,)u va u+ v - Phép toán ngoài ⋅: K ×V → V (,)αua α u thoả mãn các tiên đề sau với mọi u,, v w∈V và α, β ∈ K V1) ()()u +v +w = u +v + w V2) Có 0 ∈V sao cho u+0 = 0 + u= u V3) Với mỗi u ∈V có −u ∈V sao cho u+ ()()− u= − u+ u = 0 V4) u+ v = v+ u V5) ()α + β u= α u+ β u V6) α()u +v =αu +αv V7) ()()αβ u= α β u V8) 1u= u , trong đó 1 là phần tử đơn vị của K . Khi K = thì V được gọi là không gian véc tơ thực. Khi K = thì V thì được gọi là không gian véc tơ phức. Các phần tử của V được gọi là các véc tơ, các phần tử của K được gọi là các phần tử vô hướng. 37
Chương 2: Không gian Véc tơ Bốn tiên đề đầu chứng tỏ (,)V + là nhóm Abel. Tiên đề V5),V6) nói rằng phép nhân số vô hướng với véc tơ phân phối đối với phép cộng của số vô hướng và phép cộng véc tơ. Tiên đề V7) là tính kết hợp của tích các số vô hướng với phép nhân với véc tơ. Ví dụ 2.1: Tập R3 các véc tơ tự do trong không gian (trong đó ta đồng nhất các véc tơ tương đẳng: các véc tơ cùng phương, cùng hướng, cùng độ dài). Xét phép cộng hai véc tơ theo quy tắc hình bình hành và tích một số thực với một véc tơ theo nghĩa thông thường thì R3 là không gian véc tơ thực. Ví dụ 2.2: Giả sử K là một trường, xét n K={} x = ( x1 , , xn ) x i ∈ K , i = 1, n Ta định nghĩa: (x1 , , xn )+ ( y1 , , yn )= ( x1+ y 1 , , xn+ y n ) α(x1 , , xn )= (α x1 , ,α xn ) , ∀α ∈ K Dễ dàng kiểm chứng lại hai phép toán này thoả mãn 8 tiên đề của không gian véc tơ có véc tơ không là 0 = (0, ,0) . 123 n phÇn tö n Khi K = ta có không gian véc tơ thực . n K = ta có không gian véc tơ phức . Ví dụ 2.3: Gọi C[a, b] là tập các hàm liên tục trên đoạn [a, b]⊂ . Ta định nghĩa phép toán cộng và nhân với số thực như sau: (f +g )(t ) =f (t ) + g (t ) , (αf )(t )= αf (t ) , ∀t∈[ a, b] Rõ ràng f + g, αf ∈C[]a, b , ∀f, g ∈C[]a, b , ∀α ∈ . Với hai phép toán này C[a, b] có cấu trúc không gian véc tơ thực với véc tơ không là 0(t )= 0, ∀ t ∈[] a , b . Ví dụ 2.4: Gọi Pn là tập các đa thức bậc ≤ n , n là số nguyên dương cho trước: n Pn ={ ppa =0 + at 1 + + ataan ;0 , 1 , , an ∈}. Ta định nghĩa phép cộng hai đa thức và phép nhân một số với một đa thức như phép cộng hàm số và phép nhân một số với hàm số trong Ví dụ 2.3 thì Pn là không gian véc tơ với véc tơ không là đa thức 0 . 38
Chương 2: Không gian Véc tơ Ví dụ 2.5: Gọi P là tập các đa thức n P=U Pn ={ ppaat =0 + 1 + + ataaan ;0 , 1 , ,n ∈ , n ∈ + } n∈+ Ta định nghĩa phép cộng là phép cộng hai đa thức và phép nhân với một số với đa thức theo nghĩa thông thường ở Ví dụ 2.4 thì P là không gian véc tơ và PPn ⊂ với mọi n ∈ + . 2.1.2 Tính chất 1) Vì (,)V + là một nhóm Abel nên véc tơ 0 và véc tơ đối − u của u là duy nhất với mọi u ∈V . 2) Có luật giản ước: u+ v = u+ w⇒ v= w . 3) Với mọi u ∈V , 0u = 0 , (− 1)u= − u . 4) Với mọi α ∈ K , α0= 0 . 5) Nếu αu = 0 thì α = 0 hoặc u = 0 . Chứng minh: 1) 2) Xem Tính chất 1.4. 3) Với mọi u ∈V , (0+ 0)u = 0 u+ 0 u . Mặt khác (0+ 0)u= 0 u= 0 u + 0 . Theo luật giản ước ta có 0u = 0 . Tương tự với mọi u ∈V , u+ ()− u= 0 = 0 u= (11)− u= 1 u+ (1)− u . Suy ra (− 1)u = − u . 4) 0 +α0 = α 0= α (0+ 0) = α 0+α 0 ⇒ α0= 0 ,∀α ∈ K . −1 5) Nếu αu = 0 và giả sử α ≠ 0 ⇒ ∃α ∈ K −1− 1 −1 0 =α0 = α ( αu )= ( α α )u= 1 u = u . Từ định nghĩa của không gian véc tơ ta có thể mở rộng các khái niệm sau: 1) Ta định nghĩa u −v :() =u + −v , khi đó u+ v = w ⇔ u= w− v . 2) Do tính kết hợp của phép cộng nên ta có thể định nghĩa theo qui nạp: n ∑uk = u1 + + un = ( u1 + + un−1 ) + u n . k =1 39
Chương 2: Không gian Véc tơ n Tương tự ∑αku k = α1 u 1 + +αnu n =( α1 u 1 + + αn−1u n − 1) + α n u n k =1 biểu thức này được gọi là một tổ hợp tuyến tính của các véc tơ u1, , un . Từ đây trở đi ta chỉ hạn chế xét các không gian véc tơ thực. 2.2 KHÔNG GIAN VÉC TƠ CON 2.2.1 Định nghĩa và ví dụ Định nghĩa 2.2: Giả sử (V ,+ ,.) là không gian véc tơ. Tập con W ≠ φ của V sao cho hai phép toán từ V thu hẹp vào W trở thành không gian véc tơ (thoả mãn các tiên đề V1-V8) thì W được gọi là không gian véc tơ con của V (hay nói tắt: không gian con của V ). Định lý sau đây chỉ ra rằng nếu 2 phép toán trong V có thể thu hẹp được vào W thì các tiên đề V1-V8 luôn thoả mãn, do đó W là không gian véc tơ con của V . Định lý 2.2: Giả sử W là tập con khác rỗng của V . Ba mệnh đề sau đây tương đương: (i) W không gian véc tơ con của V . (ii) Với mọi u, v∈ W , với mọi α ∈ thì u + v ∈W , αu ∈W (iii) Với mọi u, v∈ W , với mọi α, β ∈ thì αu + βv ∈W . Chứng minh: (i) ⇒ (ii): Hiển nhiên theo định nghĩa. (ii) ⇒ (iii): Với mọi u, v∈ W , với mọi α, β ∈ thì αu∈ W , βv ∈W ⇒ αu +βv ∈W . (iii) ⇒ (i): ∀u, v∈ W , ∀α ∈ : u + v = 1u + 1v ∈W , αu= α u+0 u ∈ W . Vậy phép cộng và phép nhân với số thực thu hẹp được từ V vào W . Hơn nữa W ≠ φ ⇒ ∃u ∈ W ⇒ 0= 0u + 0 u ∈ W ( tiên đề V2), với mọi u∈ W , − u = 0u + ( − 1)u ∈ W (tiên đề V3), các tiên đề còn lại hiển nhiên đúng. Vậy W là không gian véc tơ con của V . Ví dụ 2.6: Từ định lý trên ta thấy rằng mọi không gian véc tơ con của V đều phải chứa véc tơ 0 của V . Hơn nữa tập {}0 chỉ gồm véc tơ không và chính V cũng là các không gian véc tơ con của V . 3 3 Ví dụ 2.7: Tập {x= ( x1 , x 2 ,0) x 1 , x 2 ∈} ⊂ là không gian con của . 40
Chương 2: Không gian Véc tơ Ví dụ 2.8: Tập =f ∈ f( a )= 0 là không gian con của , C[]a, b 0 { C []a, b } C[]a, b nhưng tập =f ∈ f( a )= 1 không là không gian con của . C[]a, b 1 { C []a, b } C[]a, b Ví dụ 2.9: Pn là không gian con của Pm nếu n≤ m , trong đó Pn là không gian các đa thức bậc ≤ n . 2.2.2 Không gian con sinh bởi một họ véc tơ Định lý 2.3: Nếu (W ) là họ các không gian con của V thì W cũng là không gian i i∈ I I i i∈ I con của V . Chứng minh: Áp dụng Định lý 2.2. ta dễ dàng suy ra điều cần chứng minh. Từ Định lý 2.3 suy ra rằng với mọi tập con S bất kỳ của V luôn tồn tại không gian con W bé nhất của V chứa S . W chính là giao của tất cả các không gian con của V chứa S . Định nghĩa 2.4: Không gian W bé nhất chứa S được gọi là không gian sinh bởi hệ S , ký hiệu W = spanS , và S được gọi là hệ sinh của W . Định lý 2.4: W = spanS bằng tập hợp tất cả các tổ hợp tuyến tính của S . Chứng minh: Gọi W ' là tập tất cả các tổ hợp tuyến tính của S . Ta chứng minh W ' là không gian con bé nhất chứa S . (i) Với mọi u ∈ S thì u=1 u ∈ W ' vậy S ⊂ W '. (ii) u∈ W',', v ∈ W u = α1 u 1 + +αnu n , v= β1 v 1 + + βmv m ∈ W ' với u1, , un , v 1 , , v m ∈ S . Do đó γu+ δ v= γα1 u 1 + + γαnu n + δβ1 v 1 + + δβmv m ∈ W ' Vậy W ' là không gian con của V chứa S . Giả sử W" là không gian con của V chứa S . Với mọi u∈ W ' , u=α1 u 1 + + αnu n , u1 , , un ∈ S . Vì W" chứa S nên u1, , un ∈ W " ⇒ u= α1 u 1 + + αnu n ∈ W". Do đó WW'"⊂ . Nói cách khác W ' là không gian con nhỏ nhất của V chứa S . Vậy WW'= = spanS . 2.2.3 Tổng của một họ không gian véc tơ con Giả sử WW1, , n là n không gian con của V . Sử dụng định lý 2.2 ta chứng minh được tập {u1 + + un ∈ V u i∈ W i , i= 1, , n} cũng là một không gian véc tơ con của V . Ta gọi không gian véc tơ con này là tổng của các không gian con WW1, , n và ký hiệu WW1 + + n . 41
Chương 2: Không gian Véc tơ Vậy u∈ W1 + + Wn ⇔ u= u1 + + un , u i∈ W i ; i= 1, , n . (2.1) Tuy nhiên, nói chung cách viết trên không duy nhất . Ta có thể chứng minh được WW1 + + n = span(WW1 ∪ ∪ n ) (2.2) Một cách tổng quát ta định nghĩa tổng của một họ các không gian véc tơ con như sau. Định nghĩa 2.5: Nếu ()Wi i∈ I là họ các không gian con của V . Không gian con sinh bởi UWi được gọi là tổng của các không gian Wi , ký hiệu ∑Wi . i∈ I i∈I Vậy ∑Wi = span(Wi ) . Theo định lý 2.4 ta có i∈I iU∈I W= u + + u u ∈ W, i ∈ I , j = 1, , k ; k = 1,2, . (2.3) ∑ i { i1 ik i j i j j } i∈I Định nghĩa 2.6: Nếu mọi u∈ W1 + + Wn được viết một cách duy nhất dưới dạng u= u1 + + un , u i∈ W i , i= 1, , n thì tổng các không gian con này được gọi là tổng trực tiếp. Lúc đó ta ký hiệu WW1 ⊕ ⊕ n . Định lý 2.5: Giả sử WW1, 2 là hai không gian con của V , khi đó tổng hai không gian con này là tổng trực tiếp WW1⊕ 2 khi và chỉ khi W1∩W 2 = {0}. Chứng minh: (⇒): Giả sử WW1⊕ 2 , v∈ W1∩ W 2 thì v= 0+ v= v+ 0 ∈ W1⊕ W 2. Do cách viết duy nhất suy ra v = 0 . Vậy WW1∩ 2 = {0}. (⇐): Giả sử u= u1 + u 2 = v 1+ v 2∈ W 1+ W 2 thì u1− v 1 = v 2 − u 2 ∈ W 1 ∩ W 2 = {0} ⇒ u1= v 1, u 2= v 2 . Vậy tổng của hai không gian con là tổng trực tiếp WW1⊕ 2 . 2.3 ĐỘC LẬP TUYẾN TÍNH, PHỤ THUỘC TUYẾN TÍNH Ta xét các hệ véc tơ có tính chất là nếu một véc tơ bất kỳ biểu diễn được thành tổ hợp tuyến tính của hệ này thì cách viết đó là duy nhất. 42
Chương 2: Không gian Véc tơ Định nghĩa 2.7: Cho hệ n véc tơ S= { u1, , un} của V (các véc tơ này có thể trùng nhau). Hệ S được gọi là độc lập tuyến tính nếu từ: α1u 1 + +αnu n = 0,α1 , ,αn ∈ thì α1 = = αn = 0 . Hệ không độc lập tuyến tính được gọi là phụ thuộc tuyến tính. Vậy hệ S= { u1, , un} phụ thuộc tuyến tính khi và chỉ khi ta có thể tìm được α1, ,αn ∈ không đồng thời bằng 0 sao cho α1u 1 + +αnu n = 0 . 2 Ví dụ 2.10: Hệ {e1, e 2} trong đó e1 =(1,0), e2 = (0,1) ∈ là độc lập, vì nếu α1e 1+α 2 e 2 =(α 1 ,α 2 ) = (0,0) thì α1= α 2 = 0 . Ví dụ 2.11: • Hệ chứa véc tơ 0 là hệ phụ thuộc tuyến tính. • Hệ hai véc tơ {u1, u 2 } là hệ phụ thuộc tuyến tính khi và chỉ khi chúng tỷ lệ, nghĩa là u1= α u 2 hay u2= α u 1. • Trong R2 hai véc tơ phụ thuộc tuyến tính khi và chỉ khi cùng phương. • Trong R3 ba véc tơ phụ thuộc tuyến tính khi và chỉ khi đồng phẳng. Tính chất 2.6: 1) Hệ véc tơ chứa hệ con phụ thuộc tuyến tính là hệ phụ thuộc tuyến tính. Vì vậy, mọi hệ con của hệ độc lập tuyến tính là hệ độc lập tuyến tính. 2) Một hệ véc tơ là phụ thuộc tuyến tính khi và chỉ khi có một véc tơ là tổ hợp tuyến tính của các véc tơ còn lại. 3) Giả sử hệ {v1, , vn} độc lập tuyến tính. Khi đó hệ {v1, , vn , u} phụ thuộc tuyến tính khi và chỉ khi u là tổ hợp tuyến tính của các véc tơ {v1, , vn}, khi đó ta có thể biểu diễn duy nhất u= β1 v1 + + βnv n . Chứng minh: Ta chứng minh 3). (⇐): suy từ 2). (⇒): Giả sử {v1, , vn , u} phụ thuộc khi đó tồn tại các số β1', ,βn ',α ∈ không đồng thời bằng 0 sao cho β1'v 1 + + βn 'v n + α u = 0 , vì hệ {v1, , vn} độc lập nên β β α ≠ 0 , ⇒ u= −1 v − − n v . α 1 α n Hơn nữa giả sử u=β1 v 1 + + βnv n thì 43
Chương 2: Không gian Véc tơ β1' βn ' β1' βn ' 0 =−=+u u (β )v +++ (β )v ⇒+==+=β β 0 1 α 1 n α n 1 α n α β ' β ' Do đó β = − 1 , , β = − n . Vậy cách viết trên là duy nhất. 1 α n α 2.4 HẠNG CỦA MỘT HỆ HỮU HẠN CÁC VÉC TƠ 2.4.1 Hệ con độc lập tuyến tính tối đại Định nghĩa 2.8: Cho hệ S các véc tơ của không gian véc tơ V . Hệ con {}v1, , vn của hệ S được gọi là độc lập tuyến tính tối đại của S nếu nó là hệ độc lập tuyến tính và nếu thêm bất kỳ véc tơ nào của S thì ta có hệ phụ thuộc tuyến tính. Nói riêng hệ {v1, , vn} là hệ độc lập tuyến tính tối đại của V nếu hệ {v1, , vn} độc lập và nếu thêm bất kỳ véc tơ khác của V ta có hệ mới là phụ thuộc. Tính chất 2.7: 1) Nếu S' là hệ con độc lập tuyến tính tối đại của hệ S thì mọi véc tơ của S là tổ hợp tuyến tính các véc tơ của S' và cách biểu diễn thành tổ hợp tuyến tính là duy nhất (điều này suy từ tính chất 2.6 - 3)). 2) Giả sử {v1, , vn} là hệ con độc lập tuyến tính của một hệ hữu hạn S . Khi đó ta có thể bổ sung thêm để được một hệ con độc lập tuyến tính tối đại của S chứa {v1, , vn}. Thật vậy, nếu {v1, , vn} không tối đại thì tồn tại một véc tơ của S , ta ký hiệu vn+1, sao cho hệ {v1, , vn , v n+1} độc lập tuyến tính. Lập luận tương tự và vì hệ S hữu hạn nên quá trình bổ sung thêm này sẽ dừng lại, cuối cùng ta được hệ {v1, , vn , v n+1 , , v n+ k } độc lập tuyến tính tối đại của S . 2.4.2 Hạng của một hệ hữu hạn các véc tơ Bổ đề 2.8 (Định lý thế Steinitz (Xtêi-nít)): Nếu hệ S độc lập tuyến tính có n véc tơ và mỗi véc tơ của S là tổ hợp tuyến tính các véc tơ của hệ R có k véc tơ thì n ≤ k . Chứng minh: Giả sử S= {} v1, , vn , R= { u1, , uk }. Ta sẽ chứng minh rằng có thể thay dần các véc tơ của hệ R bằng các véc tơ của hệ S để có các hệ R1 , R2 , mà mỗi véc tơ của hệ S vẫn còn là tổ hợp tuyến tính của R1, R2 , Thật vậy, ta có v1=α 1 u 1 + + αkuk , v1 ≠ 0 (vì S độc lập) nên α1, ,αk ∈ không đồng thời bằng 0, ta giả sử α1 ≠ 0 (có thể đánh lại số thứ tự của R ), suy ra 1 α2 αk u1 = v1 − u2 − − uk . α1 α1 α1 44
Chương 2: Không gian Véc tơ Xét hệ R1= { v 1, u 2 , , uk }. Rõ ràng mọi véc tơ của S vẫn còn là tổ hợp tuyến tính các véc tơ của R1. Tương tự ta có v2= β 1 v 1+ β 2 u 2 + + βku k , vì {v1, v 2} độc lập nên β2, , βk ∈ không đồng thời bằng 0, ta giả sử β2 ≠ 0 . 1 β1 β3 βk Khi đó u2 = v2 − v1 − u3 − − uk . β2 β2 β2 β2 Xét hệ R2= { v 1, v 2 , u 3 , , uk }, mọi véc tơ của S cũng là tổ hợp tuyến tính các véc tơ của R2 . Nếu n > k , tiếp tục quá trình này cuối cùng ta được mọi véc tơ của S là tổ hợp tuyến tính các véc tơ của hệ Rk = { v1, v 2 , , vk }, là hệ con của S . Điều này mâu thuẫn với giả thiết hệ S độc lập tuyến tính. Vậy n ≤ k . Định lý 2.9: Mọi hệ con độc lập tuyến tính tối đại của hệ hữu hạn S các véc tơ của V đều có số phần tử bằng nhau. Chứng minh: Giả sử v, , v và v, , v là hai hệ con độc lập tuyến tính tối { i1 ik } { j1 jn } đại của hệ S . Từ tính tối đại của mỗi hệ, suy ra rằng mọi véc tơ của hệ này là tổ hợp tuyến tính các véc tơ của hệ kia. Do đó n ≤ k và k ≤ n , vậy n = k . Định nghĩa 2.9: Số các véc tơ của một hệ con độc lập tuyến tính tối đại của hệ S được gọi là hạng (rank) của S , ký hiệu r()S . Qui ước hệ chỉ có véc tơ 0 có hạng là 0. 2.5 CƠ SỞ, SỐ CHIỀU CỦA KHÔNG GIAN VÉC TƠ Định nghĩa 2.10: 1) Nếu không gian véc tơ V có một hệ sinh hữu hạn thì V được gọi là không gian hữu hạn sinh. 2) Mỗi hệ sinh độc lập tuyến tính của V được gọi là một cơ sở của V . Giáo trình này chỉ hạn chế xét các không gian hữu hạn sinh. Giả sử S= { v1, , vn} là hệ sinh của V thì với mọi u ∈V u= x1 v 1 + + xn v n , x1, , xn ∈ . 45
Chương 2: Không gian Véc tơ Định lý 2.10: Giả sử {e1, , en} là một hệ các véc tơ của V . Các mệnh đề sau là tương đương: (i) Hệ {e1, , en} là một cơ sở của V . (ii) Hệ {e1, , en} là hệ độc lập tuyến tính tối đại của V . (iii) Mọi véc tơ u ∈V tồn tại một cách viết duy nhất: u= x1 e 1 + + xn e n , x1, , xn ∈ . (2.4) Chứng minh: (i)⇒(ii): Hiển nhiên từ định nghĩa của cơ sở. (ii)⇒(iii): Suy từ tính chất 3.2 - 3). (iii)⇒(i): Rõ ràng {e1, , en} là hệ sinh. Ngoài ra nếu x1 e 1 + + xn e n = 0 , mặt khác 0 =0e1 + + 0 en . Do cách viết duy nhất suy ra x1 = = xn = 0 . Định nghĩa 2.11: (x1 , , xn ) trong (2.4) được gọi là toạ độ của véc tơ u trong cơ sở {}e1, , en . Ta ký hiệu toạ độ của véc tơ u trong cơ sở B = {e1, , en} là [u]B . Vậy nếu u thỏa mãn (2.4) thì [u]B = ( x1 , , xn ) (2.5) Định lý 2.11: Giả sử V là không gian hữu hạn sinh và {v1, , vk } là hệ độc lập tuyến tính các véc tơ của V . Khi đó có thể bổ sung thêm để có được hệ {v1, , vk , v k+1 , , v k + m} là một cơ sở của V . Chứng minh: Giả sử V có một hệ sinh có n véc tơ. Nếu S= { v1, , vk } không phải là cơ sở thì S không phải là hệ sinh, theo tính chất 2.6-3) tồn tại véc tơ, ta ký hiệu vk +1, sao cho hệ {v1, , vk , vk +1} độc lập tuyến tính. Tiếp tục quá trình này cuối cùng ta có hệ {v1, , vk , v k+1 , , v k +m} độc lập tuyến tính và là hệ sinh, k + m≤ n (theo Bổ đề 2.8). Vậy {}v1, , vk , v k+1 , , v k + m là một cơ sở cần tìm. Hệ quả 2.12: Mọi không gian hữu hạn sinh đều tồn tại cơ sở. Định lý 2.13: Số phần tử của mọi cơ sở của đều bằng nhau. Chứng minh: Áp dụng Bổ đề 2.8 ta có hai cơ sở bất kỳ của V đều có số phần tử bằng nhau. 46
Chương 2: Không gian Véc tơ Định nghĩa 2.12: Số véc tơ của một cơ sở của V được gọi là số chiều của V , ký hiệu dimV . Quy ước dim{0}= 0 . n Ví dụ 2.12: Trong không gian ta xét hệ B = {e1, , en} trong đó: e1 = (1,0, ,0) , e2 = (0,1, ,0) , ,en = (0,0, ,1) (2.6) n n là một cơ sở của gọi là cơ sở chính tắc. Vậy dim = n . n Ví dụ 2.13: Hệ B = {1,t , , t } là một cơ sở của Pn , gọi là cơ sở chính tắc. Vậy dim Pn = n +1. ∞ Chú ý 2.14: Không gian PP= U n là một ví dụ về không gian véc tơ không hữu hạn n=1 2 sinh. Thật vậy, hệ {1,t , t , } có vô hạn véc tơ và độc lập tuyến tính nên không thể là hữu hạn sinh. Định lý 2.15: Giả sử dimV = n và S= { v1, , vm} là hệ m véc tơ của V . Khi đó: (i) Nếu hệ S độc lập tuyến tính thì m≤ n . (ii) Nếu hệ S là hệ sinh của thì m≥ n . (iii) Nếu m= n thì hệ S độc lập tuyến tính khi và chỉ khi S là hệ sinh. Chứng minh: Gọi B là một cơ sở của V . Áp dụng bổ đề 2.8 cho hai hệ B và S suy ra các điều cần chứng minh. Định lý 2.16: Giả sử WW1, 2 là hai không gian con của V thì dimWW1 +dim 2 = dim(WW1+ 2 )+ dim(WW1I 2 ) (2.7) Đặc biệt: dim(WW1⊕ 2 )= dimWW1 + dim 2 (2.8) Chứng minh: Giả sử {e1, , el } là một cơ sở của WW1I 2 (nếu WW1I 2 = φ thì l = 0 ). Theo định lý 2.11 ta có thể bổ sung thêm để {e1, , el , u 1 , , u m} là một cơ sở của W1 và {}e1, , el , v 1 , , v k là một cơ sở của W2 . Với mọi v∈ W1+ W 2 thì: vxxe=(1 + ' 1 ) 1 + + ( xxeyul + ' l ) l + 1 1 + + yuzvm m + 1 1 + + zvk k . Vậy {e1, , el , u 1 , , u m , v 1 , , vk } là hệ sinh của WW1+ 2 . Mặt khác, giả sử xe1 1 + + xeyul l +1 1 + + yum m + zv1 1 + + zvk k = 0 47
Chương 2: Không gian Véc tơ thì xe1 1 + + xeyul l +1 1 + + yum m = − zv1 1 − − zvWWk k ∈ 1I 2 . ⇒ −z1 v 1 − − zk v k = t1 e 1 + + tl e l ∈ W1I W 2 ⇒ z1 v 1 + + zk vk + t1 e 1 + + tl e l = 0 ⇒ z1 = = zk = t1 = = tl = 0 ⇒ x1 = = xl = y1 = = ym = 0 . Vậy {}e1, , el , u 1 , , u m , v1 , , v k là một cơ sở của WW1+ 2 . dimW1 +dim W2 = 2 l + m+ k= dim( W1+ W 2 )+ dim(WW1I 2 ) . Định lý 2.17: Giả sử S là hệ hữu hạn các véc tơ của V . Khi đó (i) r(S )= dimW , với W = spanS . (ii) Khi thực hiện một số hữu hạn các phép biến đổi sơ cấp sau lên hệ S : • Nhân một số khác 0 với một véc tơ của hệ S ; • Cộng vào một véc tơ của hệ S một tổ hợp tuyến tính các véc tơ khác của S ; thì hệ S biến thành hệ S' có r()(')S = r S . Chứng minh: (i) Giả sử S0 là hệ con độc lập tuyến tính tối đại của S thì S0 cũng sinh ra W , do đó S0 là một cơ sở của W ⇒ r()S = số véc tơ của SW0 = dim . (ii) Nếu W= s panS, W '= s panS ' thì WW= ' ⇒ r(S )= r (S ') . Nhận xét 2.18: Để tìm hạng của hệ véc tơ {v1, v 2 , , vn} ta có thể sử dụng 2 cách sau: 1) Áp dụng định lý 2.17 bằng cách thực hiện các phép biến đổi sơ cấp lên hệ véc tơ đã cho để đưa về hệ véc tơ mà ta dễ dàng nhận được hạng của nó. Khi thực hành ta có thể viết tọa độ các véc tơ thành một bảng, mỗi véc tơ nằm trên một hàng, sau đó biến đổi để bảng số này có dạng tam giác. 2) Áp dụng tính chất 2.6 theo từng bước như sau: 1. Loại các véc tơ vi = 0 , 2. Giả sử v1 ≠ 0 , loại các véc tơ vi tỉ lệ với v1, 3. Giả sử v, , v độc lập, khi đó v, , v , v độc lập khi và chỉ khi { i1 ik } { i1 ik j } v không biểu diễn thành tổ hợp tuyến tính của v, , v . j { i1 ik } Ví dụ 2.14: Tìm hạng của hệ véc tơ sau: v1 = (1,1,1,1),v2 = (1, − 1,1, − 1),v3 = (1,3,1,3), 48
Chương 2: Không gian Véc tơ v4 = (1,2,0,2),v5 = (1,2,1,2). Giải: • Cách1: ⎧1 1 1 1 ⎧1 1 1 1 ⎪1− 1 1 − 1 ⎪0− 2 0 − 2 ⎪ ⎪ ⎨1 3 1 3 → ⎨0 2 0 2 ⎪1 2 0 2 ⎪0 1− 1 1 ⎪ ⎪ ⎩⎪1 2 1 2 ⎩⎪0 0 1 0 (Hàng1 → hàng 1, hàng 2 - hàng1 → hàng 2, hàng 3 - hàng1 → hàng 3, hàng 4 - hàng1 → hàng 4, hàng 5 - hàng4 → hàng 5) ⎧1 1 1 1 ⎧1 1 1 1 ⎪0− 2 0 − 2 ⎪0 1 0 1 ⎪ ⎪ → ⎨0 0 0 0 → ⎨0 0 1 0 ⎪0 0 0 0 ⎪0 0 0 0 ⎪ ⎪ ⎩⎪0 0 1 0 ⎩⎪0 0 0 0 (Hàng 3 + hàng 2 → hàng 3, hàng 4 +(1/2) hàng 2 - hàng 5 → hàng 4). (-1/2hàng 2 → hàng 2, hàng 5 → hàng 3). Vậy hệ véc tơ có hạng là 3. • Cách 2: v1, v 2 không tỉ lệ nên độc lập. Nếu v3= xv 1+ y v 2 thì ⎧x+ y = 1 ⎪ ⎪x− y = 3 ⎨ ⇒x = 2,y = − 1. ⎪x+ y = 1 ⎩⎪x− y = 3 Vậy v3= 2 v 1− v 2 . Nghĩa là {v1,, v 2 v 3} phụ thuộc. ⎧x+ y = 1 ⎪ ⎪x− y = 2 Nếu v4= xv 1+ y v 2 thì ⎨ , hệ vô nghiệm. Vậy {v1,, v 2 v 4} độc lập. ⎪x+ y = 0 ⎩⎪x− y = 2 49
Chương 2: Không gian Véc tơ Nếu v5= xv 1 + y v 2 + zv 4 thì ⎧x+ y + z = 1 ⎪ ⎪x− y +2 z = 2 ⎨ ⇒x = 3/ 2,y = − 1/ 2,z = 0 . ⎪x+ y = 1 ⎩⎪x− y +2 z = 2 Vậy v5=3/ 2 v 1 − 1/ 2 v 2 . Nghĩa là {v1,,, v 2 v 4 v 5} phụ thuộc. Vậy {v1,, v 2 v 4} là một hệ con độc lập tuyến tính tối đại của {v1,,,, v 2 v 3 v 4 v 5}. 50
Chương 3: Ma trận 3. CHƯƠNG 3: MA TRẬN 3.1 KHÁI NIỆM MA TRẬN Định nghĩa 3.1: Một bảng số có m hàng n cột ⎡ a11 a 12 a1n ⎤ ⎢ ⎥ a21 a 22 a2n A = ⎢ ⎥ (3.1) ⎢ MMOM ⎥ ⎢ ⎥ ⎣am1 a m 2 amn ⎦ được gọi là một ma trận cỡ m× n . aij là phần tử ở hàng thứ i và cộtj . Khi aij ∈,, ∀ i j thì A được gọi là ma trận nguyên, aij ∈,,∀ i j thì A được gọi là ma trận phức. Nếu không chỉ rõ aij thì ta quy ước A là ma trận thực. Ma trận A cỡ m× n có thể được viết tắt dạng i= ,1 m A= a hay A= a (3.2) []ij j= ,1 n [ ij ]m× n Khi m= n ta nói A là ma trận vuông cấp n . Tập hợp tất cả các ma trận cỡ m× n được ký hiệu Mm× n . Tập hợp tất cả các ma trận vuông cấp n được ký hiệu Mn . ⎡ 0− 1 π ⎤ Ví dụ 3.1: ⎢ ⎥ là ma trận cỡ 2× 3. ⎣− 3 2 5⎦ Hai ma trận cùng cỡ A= a , B= b bằng nhau, ký hiệu A = B , khi và []ij m× n [ ij ]m× n chỉ khi aij= b ij với mọi i=1, m ; j = 1, n . 51
Chương 3: Ma trận 3.2 CÁC PHÉP TOÁN MA TRẬN 3.2.1 Phép cộng Cho hai ma trận cùng cỡ A= a , B= b []ij m× n [ ij ]m× n Tổng của hai ma trận A, B là ma trận cùng cỡ được ký hiệu và định nghĩa bởi A+ B = c, c= a + b với mọi i=1, m ; j= 1, n . []ij m× n ij ij ij (3.3) ⎡2− 3 0 ⎤ ⎡ 0 8 5⎤ ⎡2 5 5⎤ Ví dụ 3.2: ⎢ ⎥ + ⎢ ⎥ = ⎢ ⎥ . ⎣9 4− 1⎦ ⎣− 3 1 7⎦ ⎣6 5 6⎦ 3.2.2 Phép nhân ma trận với một số Cho ma trận A= a cỡ m× n , và số thực k . Ta định nghĩa và ký hiệu [ ij ]m× n kA= ka . (3.4) [ ij ]m× n 1 ⎡1 2− 1 0 ⎤ ⎡1 4− 1 2 0⎤ Ví dụ 3.3: ⎢ ⎥ = ⎢ ⎥ . 2 ⎣ 3− 8 10⎦ ⎣3 2− 4 5⎦ Tính chất 3.1: Các tính chất sau đây đúng đối với các ma trận cùng cỡ: 1) A +()()B +C =A +B + C ; 2) Ma trận có các phần tử đều bằng 0 gọi là ma trận không và ký hiệu 0 . Khi đó: A +0 = 0 +A = A; 3) A +( −A ) = 0 , trong đó −A = − a ; [ ij ]m× n 4) A +B =B + A. Vậy (,)Mm× n + là một nhóm Abel. Ta cũng kiểm chứng được các tính chất sau đúng với mọi số thực k,h với mọi ma trận A= a , B= b cỡ m× n : []ij m× n [ ij ]m× n 5) k()A +B =kA + kB ; 6) ()k +h A =kA + hA ; 52
Chương 3: Ma trận 7) k()()hA= kh A ; 8) 1A = A. Với 8 tính chất này tập Mm× n là không gian véc tơ. Ký hiệu Eij là ma trận cỡ m× n có các phần tử đều bằng 0 ngoại trừ phần tử ở hàng i cột j bằng 1 thì hệ các ma trận {Eij i=1, m ; j = 1, n } là một cơ sở của Mm× n . Vậy dim Mm× n =m × n . 3.2.3 Phép nhân ma trận Định nghĩa 3.2: Tích hai ma trận A= a và B= b là ma trận cỡ [ ij ]m× p [ ij ]p× n m×n được ký hiệu và định nghĩa bởi AB= c , trong đó [ ij ]m× n p cij= ∑ a ik b kj với mọi i=1, m ; j = 1, n . (3.5) k =1 Vậy phần tử ở hàng thứ i cột thứ j của AB bằng tổng của tích các phần tử của hàng thứ i của A với các phần tử tương ứng của cột thứ j của B . j ⎡ ⎤ ⎡ ⎤ ⎡ b1 j ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ b ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ 2 j ⎥ i ⎢ cij ⎥ = ⎢ ai1 a i 2 aip ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣⎢ ⎦⎥ ⎣⎢ ⎦⎥ ⎣ bpj ⎦ ⎡ 1 3⎤ ⎡ 1− 2 3⎤⎢ ⎥ ⎡9 15⎤ Ví dụ 3.4: ⎢ ⎥ −1 0 = ⎢ ⎥ . ⎣−1 2 5⎦⎢ ⎥ ⎣7 17⎦ ⎣⎢ 2 4⎦⎥ ⎡2⎤ ⎡2 8− 4⎤ ⎢ ⎥[]1 4− 2 = ⎢ ⎥ . ⎣3⎦ ⎣3 12− 6⎦ 53
Chương 3: Ma trận Ta thấy rằng tích của hai ma trận A và B định nghĩa được khi số cột của A bằng số hàng của B . Vì vậy có thể định nghĩa AB nhưng không định nghĩa được BA nếu số cột của B không bằng số hàng của A. Khi A, B là hai ma trận vuông cùng cấp thì ta có đồng thời AB và BA. Mặc dầu vậy chưa chắc có đẳng thức AB = BA, nói cách khác tích ma trận không có tính giao hoán. Chẳng hạn, xét ⎡−1 0 0K 0⎤ ⎡1 2 0K 0⎤ ⎢ 2 3 0 0⎥ ⎢3 0 0 0⎥ ⎢ K ⎥ ⎢ K ⎥ A = ⎢ 0 0 0K 0⎥ B = ⎢0 0 0K 0⎥ ⎢ ⎥ ⎢ ⎥ ⎢ MMMOM⎥ ⎢MMMOM⎥ ⎣⎢ 0 0 0 0 0⎦⎥ ⎣⎢0 0 0 0 0⎦⎥ ⎡−1 − 2 0K 0⎤ ⎡ 3 6 0K 0⎤ ⎢ ⎥ ⎢ ⎥ 11 4 0K 0 − 3 0 0K 0 ⎢ ⎥ ⎢ ⎥ AB = ⎢ 0 0 0K 0⎥ ≠ BA = ⎢ 0 0 0K 0⎥ ⎢ ⎥ ⎢ ⎥ ⎢ MMMOM⎥ ⎢ MMMOM⎥ ⎣⎢ 0 0 0 0 0⎦⎥ ⎣⎢ 0 0 0 0 0⎦⎥ Tính chất 3.2: Giả sử A,,B C là các ma trận với số cột số hàng thích hợp để các phép toán sau xác định được thì ta có các đẳng thức: 1) A()()BC = AB C tính kết hợp. 2) A()B +C =AB + AC tính phân phối bên trái phép nhân ma trận với phép cộng. 3) ()B +C A =BA + CA tính phân phối bên phải phép nhân ma trận với phép cộng. 4) Với mọi k∈ , k ( AB )= ( kA ) B= A ( kB ) . 5) Với mọi số tự nhiên dương n ta xét ma trận In vuông cấp n có các phần tử trên đường chéo bằng 1 và các phần tử ở vị trí khác đều bằng 0. ⎡1 ⎤ ⎢ ⎥ I = n ⎢ O ⎥ ⎣⎢ 1⎦⎥ 54
Chương 3: Ma trận Khi đó với mọi ma trận A cỡ m× n ta có Im A= A= AIn . Ma trận In được gọi là ma trận đơn vị cấp n. Từ các tính chất trên ta thấy tập hợp các ma trận vuông cấp n ≥ 2 cùng với phép cộng và nhân ma trận (Mn ,+ ,.) là một vành không giao hoán, có đơn vị và không nguyên vì có ước của 0. Chẳng hạn ⎡1 2 0K 0⎤ ⎡ 2− 6 0K 0⎤ ⎢2 4 0 0⎥ ⎢−1 3 0 0⎥ ⎢ K ⎥ ⎢ K ⎥ A = ⎢0 0 0K 0⎥ B = ⎢ 0 0 0K 0⎥ ⎢ ⎥ ⎢ ⎥ ⎢MMMOM⎥ ⎢ MMMOM⎥ ⎣⎢0 0 0 0 0⎦⎥ ⎣⎢ 0 0 0 0 0⎦⎥ A,B ≠ 0 nhưng AB = 0. 3.2.4 Ma trận chuyển vị Định nghĩa 3.3: Cho ma trận A cỡ m× n , nếu ta đổi các hàng của ma trận A thành các cột (và do đó các cột thành các hàng) thì ta được ma trận mới cỡ n× m , gọi là ma trận chuyển vị t của ma trận trên A, ký hiệu A t A= c ; c= a i = 1, n j = 1, m . (3.6) []ij n× m ij ji ⎡− 4 1⎤ ⎢ ⎥ t ⎡− 4 2 5⎤ Ví dụ 3.5: A = 2 0 ; A = ⎢ ⎥ . ⎢ ⎥ ⎣ 1 0 9⎦ ⎣⎢ 5 9⎦⎥ Tính chất 3.3: t t t 1) ()ABAB+ = + . t t 2) ()kA= kA . t t t 3) ()AB= B A . Định nghĩa 3.4: t 1) Nếu A = A thì A được gọi là ma trận đối xứng ( A là ma trận vuông có các phần tử đối xứng nhau qua đường chéo thứ nhất). 55
Chương 3: Ma trận t 2) A = −A thì A được gọi là phản đối xứng (hay đối xứng lệch) ( A là ma trận vuông có các phần tử đối xứng và trái dấu qua đường chéo thứ nhất, các phần tử trên đường chéo thứ nhất bằng 0). 3.3 MA TRẬN CỦA MỘT HỆ VÉC TƠ TRONG MỘT CƠ SỞ NÀO ĐÓ Giả sử V là không gian n chiều với một cơ sở B = {e1, en}. {v1, , vm} là một hệ véc tơ của V có toạ độ trong cơ sở B : n vj= ∑ a ij e i , j= 1, m i=1 Khi đó ma trận A= a có các cột là các toạ độ của các véc tơ {}v, , v trong []ij n× m 1 m cơ sở B được gọi là ma trận của hệ véc tơ {v1, , vm} trong cơ sở B . Ngược lại, với ma trận A cỡ n× m cho trước thì ta có hệ m véc tơ mà toạ độ của nó trong cơ sở B là các cột của A. Vậy khi không gian véc tơ V với cơ sở cố định B = {e1, en} thì có tương ứng 1 - 1 giữa các ma trận cỡ n× m với các hệ m véc tơ của V . Ma trận chuyển cơ sở Giả sử B = {}e1, en , B'= {e'1 , e 'n} là hai cơ sở của V . Ma trận của hệ véc tơ B' trong cơ sở B được gọi là ma trận chuyển từ cơ sở B sang cơ sở B'. Nghĩa là nếu n e'j= ∑ t ij e i , j= 1, n thì P= [ tij ] (3.7) i=1 là ma trận chuyển từ cơ sở B sang B'. n n Khi đó với véc tơ bất kỳ u ∈V ;u=∑ xi e i = ∑ x''i e i . i=1 i=1 Ta có: []x= t x' (3.8) i n×1 [ ij ]n× n [ j ]n×1 (3.8) được gọi là công thức đổi tọa độ Nếu A,'A lần lượt là ma trận của {v1, , vm} trong cơ sở B , B' thì A = PA' (3.9) 56
Chương 3: Ma trận 3.4 HẠNG CỦA MA TRẬN Định nghĩa 3.5: Ta gọi hạng của ma trận A, ký hiệu r()A , là hạng của các véc tơ cột của A. Phương pháp tìm hạng của ma trận bằng phép biến đổi sơ cấp Hạng r()S của một hệ véc tơ S của không gian V là số véc tơ của một hệ con độc lập tuyến tính tối đại của S hay là chiều của spanS (xem Định lý 2.17). Vì vậy khi ta thực hiện liên tiếp các phép biến đổi sau, gọi là các phép biến đổi sơ cấp, thì spanS không đổi do đó hạng của hệ không thay đổi: 1) Đổi chỗ cho nhau hai véc tơ của hệ. 2) Nhân vào một véc tơ của hệ một số khác 0 . 3) Cộng vào một véc tơ của hệ một tổ hợp tuyến tính các véc tơ khác của hệ. Vì vậy để tìm hạng của một ma trận ta thực hiện các biến đổi sơ cấp lên các cột (sau này ta sẽ chứng minh được rằng ta cũng có thể biến đổi theo các hàng) để đưa ma trận về dạng tam giác, từ đó suy ra hạng của ma trận. Ví dụ 3.6: 3c1+ c 2 → c 2 ⎡ 1− 3 4 2 ⎤ ⎡ 1 0 0 0⎤ 4c+ c → c A = ⎢ 2 1 1 4 ⎥ 1 3 3 ⎢ 2 7− 7 0⎥ ⎢ ⎥ ⎢ ⎥ −2c1 + c 4 → c 4 ⎣⎢−1 − 2 1 − 2⎦⎥ ⎣⎢−1 − 5 5 0⎦⎥ c1 → c1 ⎡ 1 0 0 0⎤ c2→ c 2 ⎢ ⎥ 2 7 0 0 ⎢ ⎥ c2+ c 3 → c 3 ⎣⎢−1 − 5 0 0⎦⎥ Vậy r(A )= 2 . c→ c1 c1→ c 4 1 ⎡−1 2 1− 1 1 ⎤ ⎡1− 1 1 − 1 2 ⎤ c+ c → c ⎢ ⎥ c2→ c 5 ⎢ ⎥ 1 2 2 a −1 1 − 1 − 1 c→ c 1− 1 − 1a − 1 −c + c → c B = ⎢ ⎥ 3 1 ⎢ ⎥ 1 3 3 c→ c ⎢ 1a 0 1 1 ⎥ 4 2 ⎢0 1 1 1 a ⎥ c1+ c 4 → c 4 ⎢ ⎥ c5→ c 3 ⎢ ⎥ −2c + c → c ⎣ 1 2 2− 1 1 ⎦ ⎣2− 1 1 1 2 ⎦ 1 5 5 57
Chương 3: Ma trận c→ c 1 1 ⎡1 0 0 0 0⎤ c → c ⎡1 0 0 0 0 ⎤ ⎢ ⎥ 2 3 ⎢ ⎥ 1 0 − 2 a + 1 − 3 c → c 1 − 2 0 0 0 ⎢ ⎥ 3 2 ⎢ ⎥ −(a + 3) c +( a + 1) c +2 c → c ⎢0 1 1 1 a⎥ 2 3 4 4⎢0 1 1 0 0 ⎥ ⎢ ⎥ (3-2a)c -3c +2c → c ⎢ ⎥ ⎣2 1 − 1 3 − 2 ⎦ 2 3 5 5 ⎣2 − 1 1 2 − 2a 2 − 2 a⎦ ⎧4 nÕu a ≠ 1 Vậy r() B = ⎨ . ⎩3 nÕu a =1 Xét các ma trận vuông cấp n sau: ⎡1 ⎤ ⎧0 i≠ j ⎢ λ ⎥ hµng k ⎢ ⎥ ⎪ R(,) kλ =[] aij = aij = ⎨1 i= j ≠ k (3.10) ⎢ ⎥ ⎪ ⎢ ⎥ ⎩λ i= j = k ⎣ 1⎦ cột k ⎡1 ⎤ ⎢ 0 1 ⎥ hµng i ⎢ ⎥ P(,) i j=[] akl = ⎢ ⎥ ⎢ ⎥ ⎢ 1 0 ⎥ hµng j ⎣⎢ 1⎦⎥ cột i cột j ⎧1 k= l ≠ i; j ⎪ 0 k= l vµ b»ng i hay j ⎪ akl = ⎨1 k= i, l = j (3.11) ⎪1 k= j, l = i ⎪ ⎩⎪0 trong c¸c tr− êng hîp kh¸c 58
Chương 3: Ma trận ⎡1 ⎤ ⎢ 1 ⎥ ⎢ ⎥ Q(,,) i jλ =[] akl = ⎢ ⎥ ⎢ ⎥ ⎢ λ 1 ⎥ hµng i ⎣⎢ 1⎦⎥ cột j ⎧1 k= l ⎪ akl = ⎨λ k= i , l = j (3.12) ⎪ ⎩0 trong c¸c tr− êng hîp kh¸c Tính chất 3.5: Ta dễ dàng kiểm tra được: a) Nếu nhân R(,)k λ vào bên phải của ma trận A thì ma trận tích AR(,)k λ có được bằng cách nhân thêm λ vào cột k của ma trận A. ⎡ a b c ⎤⎡1 0 0⎤ ⎡ aλ b c ⎤ ⎢ ⎥⎢ ⎥ ⎢ ⎥ a''' b c 0λ 0 = a'''λ b c ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎣⎢a""" b c ⎦⎥⎣⎢0 0 1⎦⎥ ⎣⎢a"""λ b c ⎦⎥ b) Nếu nhân P(,)i j vào bên phải của ma trận A thì ma trận tích AP(,)i j có được bằng cách đổi chỗ hai cột i vàj của A cho nhau. ⎡ a b c ⎤⎡0 1 0⎤ ⎡ b a c ⎤ ⎢ ⎥⎢ ⎥ ⎢ ⎥ a''' b c 1 0 0 = b''' a c ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎣⎢a""" b c ⎦⎥⎣⎢0 0 1⎦⎥ ⎣⎢b""" a c ⎦⎥ c) Nếu nhân Q(,,) i j λ vào bên phải của ma trận A thì ma trận tích AQ(,,)i j λ có được bằng cách nhân λ vào cột i và cộng vào cột j của ma trận A. ⎡ a b c ⎤⎡1 0 0⎤ ⎡ a+ λ c b c ⎤ ⎢ ⎥⎢ ⎥ ⎢ ⎥ a''' b c 0 1 0 = a''''+λ c b c ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎣⎢a""" b c ⎦⎥⎣⎢λ 0 1⎦⎥ ⎣⎢a""""+λ c b c ⎦⎥ 59
Chương 3: Ma trận d) Nếu nhân P,,Q R vào bên trái của ma trận A thì ta có các kết quả tương tự như trên, trong đó các tác động lên hàng đổi thành tác động lên cột và ngược lại. Chẳng hạn ⎡1 0 0⎤⎡ a b c ⎤ ⎡ a b c ⎤ ⎢ ⎥⎢ ⎥ ⎢ ⎥ 0λ 0 a''' b c = λa''' λ b λ c ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎣⎢0 0 1⎦⎥⎣⎢a""" b c ⎦⎥ ⎣⎢ a""" b c ⎦⎥ ⎡1 0 0⎤⎡ a b c ⎤ ⎡ a b c ⎤ ⎢ ⎥⎢ ⎥ ⎢ ⎥ 0 1 0 a''' b c = a''' b c . ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎣⎢0λ 1⎦⎥⎣⎢a""" b c ⎦⎥ ⎣⎢λa'"'"'"+ a λ b + b λ c + c ⎦⎥ 60
Chương 4: Định thức 4. CHƯƠNG 4: ĐỊNH THỨC 4.1 HOÁN VỊ VÀ PHÉP THẾ Định nghĩa 4.1: 1) Mỗi song ánh σ :{} 1,2, ,n → { 1,2, ,n} được gọi là một phép thế bậc n. Ta thường ký hiệu một phép thế bằng một ma trận có hàng thứ nhất là các số 1,2, ,n sắp theo thứ tự tăng dần còn hàng thứ hai là ảnh của nó: ⎡ 1 2 n ⎤ σ = ⎢ ⎥ ⎣σ(1) σ (2) σ (n )⎦ 2) Ảnh của một phép thế được gọi là hoán vị. Với phép thế σ ta có hoán vị tương ứng []σ (1)σ (2) σ (n ) . 3) Dấu của phép thế: Cho hoán vị []σ (1)σ (2) σ (n ) , nếu có cặp i σ j thì ta nói có một nghịch thế của σ . Giả sử k là số các nghịch thế của σ , ta định nghĩa và ký hiệu dấu của phép thế σ là k sgnσ = ( − 1) (4.1) Ta dễ dàng kiểm chứng được rằng tập các phép thế bậc n với luật hợp thành là phép hợp của hai ánh xạ tạo thành một nhóm không giao hoán, gọi là nhóm đối xứng bậc n, ký hiệu Sn . Trong chương 1 ta đã biết tập Sn có đúng n! phần tử. Chẳng hạn S2 có 2 phần tử, S3 có 6 phần tử ⎡1 2 3⎤ Ví dụ 4.1: Hoán vị [1 3 2] ứng với phép thế σ = ⎢ ⎥ có một nghịch thế. Vậy ⎣1 3 2⎦ 1 sgnσ = ( − 1) = − 1 . Để tìm số các nghịch thế k của phép thế σ ta thực hiện các bước sau: Trong hoán vị [σ (1)σ (2) σ (n )] có i1 là giá trị sao cho σ (i1 )= 1. 61
Chương 4: Định thức ♦ Gọi k1 là số các số trong []σ (1)σ (2) σ (n ) đứng trước σ (i1 )= 1; ♦ Xoá số σ (i1 )= 1, tồn tại i2 sao cho σ (i2 )= 2 , gọi k2 là số các số còn lại trong []σ (1)σ (2) σ (n ) đứng trước σ (i2 )= 2 ; ♦ Xoá số σ (i2 )= 2 và tiếp tục đếm như thế Cuối cùng số các nghịch thế của σ là: k= k1+ k 2 + + kn−1 Ví dụ 4.2: Hoán vị []3 4 2 1 có k1 = 3, k2 = 2 , k3 = 0 . 5 Vậy k = 5 và sgnσ = ( − 1) = − 1 . Tính chất 4.1: 1) Cặp (i ,j ), i ≠ j là một nghịch thế của phép thế σ ( nghĩa là i σ j ) σ ()()i−σ j khi và chỉ khi dấu của bằng −1. Vậy i− j ⎛σ()()i− σ j ⎞ sgnσ = dÊu⎜ ⎟ . (4.2) ∏ ⎜ i− j ⎟ 1≤i ≠ j ≤ n ⎝ ⎠ 2) Chuyển vị σ = [i0 j 0 ] là phép thế chỉ biến đổi hai phần tử i0, j 0 cho nhau và giữ nguyên các phần tử còn lại: ⎡1 2 i0 j 0 n⎤ σ = ⎢ ⎥ (4.3) ⎣1 2 j0 i 0 n⎦ Dễ dàng tính được: k= = k = 0 , k= j− i , 1 i0 −1 i0 0 0 ki +1 = =k j −1 = 1, kj = = kn = 0 ⇒ k= 2( j0− i 0 )− 1 0 0 0 k Vậy sgnσ = ( − 1) = − 1. 3) Với mọi σ ,:μ ∈ Sn sgn(σ o μ )= sgnσ sgn μ . (4.4) Thật vậy, khi (,)i j chạy khắp tập {1,2, ,n}×{ 1,2, , n}{ \ (1,1), ,(n , n ) } thì (μ (i ),μ (j )) cũng chạy khắp tập này. Do đó: 62
Chương 4: Định thức ⎛σ()()i− σ j ⎞ ⎛σ( μ (i ))− σ ( μ ( j )) ⎞ sgnσ = dÊu⎜ ⎟ = dÊu⎜ ⎟ ∏ ⎜ i− j ⎟ ∏ ⎜ μ()()i− μ j ⎟ 1≤i ≠ j ≤ n ⎝ ⎠ 1≤μ (i ) ≠ μ ( j ) ≤ n ⎝ ⎠ ⎛σ( μ (i ))− σ ( μ ( j )) ⎞ = dÊu⎜ ⎟ . ∏ ⎜ μ()()i− μ j ⎟ 1≤i ≠ j ≤ n ⎝ ⎠ ⎛σ( μ (i ))− σ ( μ ( j )) ⎞ ⎛ μ()()i− μ j ⎞ sgnσ sgn μ = dÊu⎜ ⎟ ⋅ dÊu⎜ ⎟ ∏ ⎜ μ()()i− μ j ⎟ ∏ ⎜ i− j ⎟ 1≤i ≠ j ≤ n ⎝ ⎠ 1≤i ≠ j ≤ n ⎝ ⎠ ⎛σ( μ (i ))− σ ( μ ( j )) ⎞ = dÊu⎜ ⎟ = sgn()σ μ . ∏ ⎜ i− j ⎟ o 1≤i ≠ j ≤ n ⎝ ⎠ 4) Với mọi chuyển vị [i0 j 0 ] (xem 4.3) và phép thế σ : sgnσ o []i0 j 0 = −sgnσ . 4.2 ĐỊNH THỨC ⎧ ax+ by= c Khi giải hệ phương trình tuyến tính ⎨ ta tính các định thức ⎩ a''' x+ b y = c a b c b a c D = =ab'' − ba , D = =cb'' − bc , D = =ac'' − ca . a'' b x c'' b y a'' c ⎡a11 a 12 ⎤ Như vậy định thức của ma trận A = ⎢ ⎥ vuông cấp 2 là ⎣a21 a 22 ⎦ a11 a 12 A = =a11 a 22 − a 12 a 21. a21 a 22 ⎡1 2⎤ ⎡1 2⎤ Mặt khác nhóm đối xứng S2 có 2 phần tử là σ1 = ⎢ ⎥ và σ 2 = ⎢ ⎥ có dấu ⎣1 2⎦ ⎣2 1⎦ sgnσ1 = 1 , sgnσ 2 = − 1 . Vậy a11 a 12 A = =a11 a 22 − a 12 a 21 a21 a 22 63
Chương 4: Định thức = sgnσ a a + sgnσ a a = sgnσ a a . 11σ1 (1)2 σ 1 (2) 21σ2 (1)2 σ 2 (2) ∑ 1σ (1) 2 σ (2) σ∈S2 Ta mở rộng định nghĩa này cho ma trận vuông cấp n bất kỳ như sau. Định nghĩa 4.2: Định thức của ma trận vuông A= a được ký hiệu là [ ij ]n× n det A hay A và định nghĩa bởi biểu thức: det A = ∑sgnσ ⋅ a1σ (1) an σ ( n ) (4.5) σ∈Sn Như vậy định thức của ma trận vuông A= a là tổng tất cả các tích gồm n phần tử [ ij ]n× n trên n hàng mà ở trên n cột khác nhau của ma trận A và nhân với +1 hoặc -1. Ví dụ 4.3: a) Nhóm đối xứng S2 có 6 phần tử là (xem ví dụ 1.23 chương 1) ⎡1 2 3⎤ ⎡1 2 3⎤ ⎡1 2 3⎤ σ1 = ⎢ ⎥ , σ 2 = ⎢ ⎥ , σ3 = ⎢ ⎥ , ⎣1 2 3⎦ ⎣1 3 2⎦ ⎣2 1 3⎦ ⎡1 2 3⎤ ⎡1 2 3⎤ ⎡1 2 3⎤ σ 4 = ⎢ ⎥ , σ5 = ⎢ ⎥ , σ 6 = ⎢ ⎥ . ⎣2 3 1⎦ ⎣3 1 2⎦ ⎣3 2 1⎦ có dấu sgnσ1= sgnσ 4 = sgnσ 5 = 1 , sgnσ 2= sgnσ 3= sgnσ 6 = − 1 . Vậy a11 a 12 a 13 a21 a 22 a 23 = ∑sgnσ a1σ (1) a 2 σ (2) a 3 σ (3) σ∈S a31 a 32 a 33 3 = a11 a 22 a 33− a 11 a 23 a 32− a 12 a 21 a 33 (4.6) + a12 a 23 a 31+ a 13 a 21 a 32− a 13 a 22 a 31. a11 a 12 a 13 a1n a22 a 23 a2n b) Tính định thức Dn = a33 a3n OM ann 64
Chương 4: Định thức ⎡1 2 n⎤ 0 Xét phép thế σ 0 = ⎢ ⎥ có sgnσ 0 =( −1) = 1. ⎣1 2 n⎦ Với mọi σ ∈ Sn , nếu σ ≠ σ 0 thì tồn tại k sao cho σ ()k ≠ k ⇒ tồn tại k' sao cho σ (k ')< k ' ⇒ ak'σ ( k ') = 0 ⇒ a1σ (1) an σ ( n ) = 0 . Vậy Dn = ∑sgnσ ⋅ a1σ (1) an σ ( n )=sgnσ 0 ⋅a 11 ann = a11 ann . (4.7) σ∈Sn a11 a21 a 22 Tương tự D'n = a31 a 32 a 33 = a11 ann . (4.8) MMMO an1 a n 2 a n 3 ann a1n a2,n− 1 a 2 n c) Tính định thức D"n = NMM an−1,2 an−1 n an1 a n 2 ann ⎡1 2 n⎤ Xét phép thế σ1 = ⎢ ⎥ thoả mãn σ1(k )+ k= n + 1, ∀k =1, ,n . ⎣n n −1 1⎦ Ta dễ dàng tính được k1 = n −1, k2 = n− 2, , kn−1 = 1 ⇒ k =1+ + (n− 1)= n ( n − 1) 2 n( n− 1) 2 ⇒sgnσ1 = ( − 1) . Mặt khác với mọi σ ∈ Sn , nếu σ ≠ σ1 thì tồn tại k sao cho σ (k )+k <n + 1 ⇒ akσ () k = 0 ⇒ a1σ (1) an σ ( n ) = 0 . Vậy D"n = ∑ sgnσ ⋅ a1σ (1) an σ ( n )=sgnσ 1 ⋅ an 1 a k , n− k a 1 n σ∈Sn n( n− 1) 2 =( − 1) an1 a k , n− k a 1 n (4.9) Tương tự 65
Chương 4: Định thức a11 a 12 a1n− 1 a 1 n a21 a 22 a2n− 1 n( n− 1) 2 D"'n = MMN =( − 1) an1 a k , n− k a 1 n . (4.10) MN an1 Định nghĩa 4.3: Định thức của ma trận A= a của hệ véc tơ {v, , v } ứng với [ ij ]n× n 1 n cơ sở B trong không gian véc tơ V cũng được gọi là định thức của hệ véc tơ {}v1, , vn và ký hiệu DB {} v1, , vn . Vậy DB {} v1, , vn = det A . (4.11) 4.3 CÁC TÍNH CHẤT CƠ BẢN CỦA ĐỊNH THỨC Tính chất 4.2: 1) Nếu đổi chỗ hai hàng của ma trận thì định thức đổi dấu: ⎧aij nÕu i≠ k, m ⎪ A= a , A''= a , a' = a nÕu i= m thì det A '= −det A. []ij n× n []ij n× n ij ⎨ kj ⎪ ⎩⎪amj nÕu i= k Thật vậy: detA '= ∑ sgnσ ⋅ a '1σ (1) a 'k σ ( k ) a ' mσ ( m ) a ' nσ ( n ) σ∈Sn = ∑sgnσ ⋅ a1σ (1) am σ ( k ) a k σ ( m ) a n σ ( n ) σ∈Sn = ∑sgnσ ⋅ a1'(1)σ ak σ '() k a mσ '() m a nσ '() n σ∈Sn = −∑sgnσ ' ⋅a1'(1)σ am σ '() k a k σ '() m a nσ '() n = −det A σ '∈Sn trong đó σ '= σ o []k m . 2) Định thức có tính chất tuyến tính đối với mỗi hàng: Cho hai ma trận A= a , B= b và ma trận C= c có hàng thứ k []ij n× n [ ij ]n× n [ ij ]n× n là tổ hợp tuyến tính của hàng thứ k của A và B . 66
Chương 4: Định thức ⎪⎧cij= a ij= b ij nÕu i≠ k Nghĩa là ⎨ ⎩⎪ckj=α a kj + β b kj ; víi mäi j=1, , n . thì det C =α det A + β det B . Thật vậy: detC = ∑sgnσ ⋅ c1σ (1) ck σ ( k ) c n σ ( n ) σ∈Sn = ∑sgnσ ⋅ a1σ (1) (α akσ ( k )+ β b kσ ( k )) a nσ ( n ) σ∈Sn =α∑sgn σ ⋅ a1σ (1) ak σ ( k ) a n σ ( n ) + β∑sgn σ ⋅ b1σ (1) bk σ ( k ) b n σ ( n ) σ∈Sn σ∈Sn =α det A + β det B . 3) Từ 1) và 2) suy ra rằng trong một ma trận có hai hàng tỷ lệ thì định thức bằng 0. 4) Nếu ta cộng vào một hàng một tổ hợp tuyến tính các hàng khác thì định thức không thay đổi. 5) Định thức của ma trận chuyển vị bằng định thức của ma trận đó: t Giả sử A= a , A= a' , a' = a ,i,j = 1, ,n []ij n× n []ij n× n ij ji t thì det A = det A. t det A = ∑sgnσ ⋅ a '1σ (1) a 'k σ ( k ) a ' n σ ( n ) σ∈Sn = ∑sgnσ ⋅ aσ(1)1 a σ (k ) k a σ ( n ) n σ∈Sn = sgnσ ⋅ a a a ∑ 1σ −1 (1)kσ −1 ( k ) nσ −1 ( n ) σ∈Sn −1 = sgnσ ⋅ a a a = det A ∑ 1σ −1 (1)kσ −1 ( k ) nσ −1 ( n ) σ∈Sn −1 vì sgnσ= sgn σ . 67
Chương 4: Định thức 6) Từ 5) suy ra rằng các tính chất của định thức đúng với hàng thì cũng đúng với cột và ngược lại. Vì vậy ta chỉ cần chứng minh các định lý về định thức đúng với hàng. Chẳng hạn, từ 4) suy ra nếu ta cộng vào một cột một tổ hợp tuyến tính các cột khác thì định thức không thay đổi. Định thức của mọi hệ véc tơ phụ thuộc tuyến tính đều bằng 0. a11 a1n 7) det(A )(mod p )= ∑ sgnσ a1σ (1) an σ ( n ) = MOM (4.12) σ∈S n an1 ann Ví dụ 4.4: a 1 1 1 a+ n −1 1 1 1 1a 1 1 a+ n −1 a 1 1 a) Dn = 1 1a 1 = a+ n −1 1 a 1 (cộng các cột vào cột 1) MMMOMMMMOM 1 1 1 a a+ n −1 1 1 a 1 1 1 1 1 0 0 0 1a 1 1 1a − 1 0 0 =(a + n − 1) 1 1a 1 =(a + n − 1) 1 0a − 1 0 MMMOM MMMOM 1 1 1 a 1 0 0 a − 1 n−1 ⇒Dn =( a + n − 1)( a − 1) . b) A= a với a = ±1 []ij n× n ij 1 1 det(A )(mod2) = MOM = 0(mod2) ⇒ det A chẵn. 1 1 4.4 CÁC CÁCH TÍNH ĐỊNH THỨC 4.4.1 Khai triển theo hàng, theo cột Nếu ta nhóm theo cột thứ j công thức (4.5) thì ta được: 68
Chương 4: Định thức ⎛ ⎞ ⎜ ⎟ det A= a1 j sgnσ ⋅ a2σ (2) a 3 σ (3) an σ ( n ) + ⎜ ∑ ⎟ ⎝σ∈Sn , σ (1) = j ⎠ ⎛ ⎞ ⎜ ⎟ + a2 j sgnσ ⋅ a1σ (1) a 3 σ (3) an σ ( n ) + + ⎜ ∑ ⎟ ⎝σ∈Sn , σ (2) = j ⎠ ⎛ ⎞ ⎜ ⎟ + a sgnσ ⋅ a a a . nj ⎜ ∑ 1(1)2(2)σ σ n− 1(σ n − 1) ⎟ ⎝σ∈Sn ,() σ n = j ⎠ Vì vậy định thức của ma trận A được viết lại dưới dạng det A= a1j A 1 j+ + a nj A nj (4.13) gọi là công thức khai triển của A theo cột thứ j. Aij được gọi là phần bù đại số c ủa aij . i+ j Định lý 4.3: Aij =( − 1) Mij (4.14) Trong đó Mij là định thức của ma trận cấp n-1 có được bằng cách xoá hàng i cột j của ma trận A. Chứng minh: Trước hết ta chứng minh AM11= 11. Ta có: A11 = ∑sgnσ a2σ (2) anσ ( n ) = ∑sgnσ 'a2σ '(2) anσ '( n ) = M11 σ∈Sn , σ (1) = 1 σ '∈Sn−1 với σ'= σ {2, ,n} là phép thế trong tập hợp {2, ,n}. Trường hợp Aij bất kỳ, ta thực hiện i-1 lần đổi chỗ các hàng và j-1 lần đổi chỗ các cột để đưa về hàng 1 cột 1. (i− 1) + ( j − 1) i+ j Do đó Aij =( − 1) Mij =( − 1) Mij . Công thức khai triển theo hàng i được suy từ tính chất 3.7: 6) 69
Chương 4: Định thức det A= ai1 A i 1 + + ain A in (4.15) −c + c → c 1 2 3 4 1 3 3 1 2 2 2 −2c + c → c 1 0 1 2 1 4 4 1 0 0 0 Ví dụ 4.5: D = = 3− 1 − 1 0 3− 1 − 4 − 6 1 2 0− 5 1 2− 1 − 7 2 2 2 2 0 0 2+ 1 =( − 1) ⋅ 1 ⋅ −1 − 4 − 6 = − −1 − 3 − 5 2− 1 − 7 2− 3 − 9 1 5 =( − 2)( − 3)( − 1) = −6(9 − 5) = − 24 . 1 9 4.4.2 Định lý khai triển Laplace (theo k hàng k cột) Từ ma trận A= a ta để ý k hàng: i, , i và k cột: j, , j . []ij n× n 1 k 1 k Giao của k hàng k cột này là một ma trận cấp k. Định thức của ma trận này được ký hiệu là j1, , jk M . Nếu từ ma trận A ta xoá đi k hàng i1, , ik và k cột j1, , jk thì ta có ma trận con i1, , ik j, , j cấp n-k. Định thức của ma trận này được ký hiệu là M 1 k và i1, , ik j, , j i+ + i + j + + j j, , j A 1 k =( − 1) 1 k 1 k M 1 k (4.16) i1, , ik i1, , ik j, , j được gọi là phần bù đại số của M 1 k . i1, , ik ⎡a11 a 12 a 13 a 14 ⎤ ⎢ ⎥ a21 a 22 a 23 a 24 Ví dụ 4.6: A = ⎢ ⎥ ⎢a31 a 32 a 33 a 34 ⎥ ⎢ ⎥ ⎣a41 a 42 a 43 a 44 ⎦ 23 a12 a 13 23 1+ 3 + 2 + 3 a21 a 24 a21 a 24 Có M13 = , A13 =( − 1) = − . a32 a 33 a41 a 44 a41 a 44 70
Chương 4: Định thức Định lý 4.4 (Laplace): 1) Khai triển k hàng i1, , ik : j, , j j, , j det A = MA1 k 1 k (4.17) ∑ i1, , ik i1, , ik 1≤j1 < < jk ≤ n Định thức của A bằng tổng tất cả các định thức con cấp k nằm trên k hàng i1, , ik nhân với phần bù đại số tương ứng của nó. 2) Khai triển k cột j1, , jk : j, , j j, , j det A = MA1 k 1 k (4.18) ∑ i1, , ik i1, , ik 1≤i1 < < ik ≤ n Định thức của A bằng tổng tất cả các định thức con cấp k nằm trên k cột j1, , jk nhân với phần bù đại số tương ứng của nó. Đặc biệt khi k =1 ta có công thức khai triển theo hàng và theo cột (3.4). Chứng minh: Trường hợp i1 =1, , ik = k : 1, ,k M1, ,k = ∑sgnσ ⋅ a1σ (1) ak σ ( k ) σ∈Sk 1, ,k 1, ,k M 1, ,k = ∑sgnσ '⋅ak+1σ '( k + 1) a nσ '( n ) = A1, ,k σ '∈Sn− k Ứng với mỗi phép thế σ của tập {1, ,k} và σ ' của {k+1, , n} thì phép thế μ có hoán vị tương ứng [σ (1), ,σ (k ),σ ( k + 1), ,σ (n )] có số các nghịch thế bằng số các nghịch thế của σ cộng với số các nghịch thế của σ '. Do đó sgnμ = sgnσ ⋅ sgnσ ' . Vì vậy mỗi tích sgnσ ⋅ a1σ (1) ak σ ( k ) ⋅ sgnσ '⋅ak+1σ '( k + 1) a nσ '( n ) 1, ,k 1, ,k là một hạng tử trong tổng của det A. Nói cách khác MM1, ,k 1, ,k chỉ bao gồm các hạng tử của det A; nó là một bộ phận trong biểu thức tổng của det A. Trường hợp tổng quát j, , j j, , j M 1 k , ta biến đổi hàng và cột của det A để đưa M 1 k về định thức con bậc k góc i1, , ik i1, , ik trên bên trái. Ta thực hiện i1 −1 lần đổi chỗ hàng thứ i1 để đưa về hàng thứ 1, , ik −1 lần đổi 71
Chương 4: Định thức chỗ hàng thứ ik để đưa về hàng thứ k. Tương tự đổi chỗ j1 −1, , jk − 1 lần để đưa các cột j1, , jk về các cột 1, , k. Vì vậy định thức đổi dấu (i −1) + + (i − 1) + ( j −1) + + (j − 1) i+ + i +j + + j (− 1) 1 k 1 k =( − 1) 1 k 1 k . j, , j j1, , jk 1 k Khi đổi vị trí như vậy định thức bù của M vẫn là M i, , i . i1, , ik 1 k j, , j i+ + i + j + + j j, , j Do đó A 1 k =( − 1) 1 k 1 k M 1 k , như vậy các hạng tử của i1, , ik i1, , ik j, , j j, , j M 1 k ⋅ A 1 k cũng chỉ là các hạng tử của det A . i1, , ik i1, , ik j, , j j, , j Mặt khác mỗi M 1 k ⋅ A 1 k có k!(n − k )! hạng tử. Số các định thức con i1, , ik i1, , ik j1, , jk k M trên k hàng i1, , ik bằng số các tổ hợp n chập k và bằng Cn . Các hạng tử của i1, , ik j, , j j, , j j' , , j ' j' , , j ' M 1 k ⋅ A 1 k và M 1 k ⋅ A 1 k khác nhau từng đôi một nếu i1, , ik i1, , ik i1, , ik i1, , ik {}{j1, , jk ≠ j '1 , , j 'k }. j1, , jk j1, , jk k Do đó tổng MA có Cn k!( n− k )! = n ! hạng tử phân ∑ i1, , ik i1, , ik 1≤j1 < < jk ≤ n biệt của det A nhưng det A cũng chỉ có n! hạng tử. Vậy mỗi hạng tử của det A đều là hạng tử j, , j j, , j nào đó của một trong những M 1 k ⋅ A 1 k với 1≤ j < < j ≤ n . Vậy ta có i1, , ik i1, , ik 1 k đẳng thức (3.6). Công thức khai triển theo cột (3.7) được chứng minh trực tiếp hoàn toàn tương tự cách trên t hoặc có thể suy ra từ kết quả trên và áp dụng tính chất det A = det A . a11 a1k 0 0 MOMMOM ak1 akk 0 0 Ví dụ 4.7: Dn = ak +11 ak+1 k a k + 1 k + 1 ak+1 n MOMMOM an1 ank a kk +1 ann 72
Chương 4: Định thức a11 a1k ak+1 k + 1 ak+1 n = MOMMOM ak1 akk ank +1 ann j1, , jk Vì M1, ,k = 0 nếu {}j1, , jk ≠ { 1, , k}. Ví dụ 4.8: Với mọi ma trận cùng cấp A, B luôn có det AB = det Adet B . Thật vậy, giả sử A= a , B= b , []ij n× n [ ij ]n× n n C= AB = c , c= a b []ij n× n ij∑ ik kj k =1 Xét định thức cấp 2n: 0 0 aij 0 0 D = 2n −1 −1 bij −1 Khai triển Laplace theo n hàng đầu ta có DAB2n = det det . Mặt khác, nhân b11 với cột 1, b21 với cột 2, , bn1với cột n của D2n xong cộng tất cả vào cột n+1 thì định thức D2n trở thành: a11 a1n c 11 0 0 MOMMOM an1 ann c n1 0 0 D2n = −1 0 b12 b 1n −1 MOM −1 0 bn2 b nn 73
Chương 4: Định thức Tiếp tục biến đổi tương tự như trên cuối cùng được: a11 a1n c 11 c1n MOMMOM an1 ann c n1 cnn D = 2n −1 0 0 −1 −1 0 0 Khai triển Laplace theo n hàng cuối ta được: −1 c11 c1n 1+ 2 + +n + n + 1 + + 2 n D2n =( − 1) −1 MOM −1 cn1 cnn 2n (2 n+ 1) +n =( − 1) 2 ⋅detCC = det . 4.5 ỨNG DỤNG ĐỊNH THỨC ĐỂ TÌM MA TRẬN NGHỊCH ĐẢO 4.5.1 Định nghĩa ma trận nghịch đảo Ta đã biết vành (Mn ,+ ,.) các ma trận vuông cấp n là không nguyên, vì vậy với ma trận vuông cho trước chưa chắc đã có ma trận nghịch đảo đối với phép nhân ma trận. Định nghĩa 4.4: Ma trận vuông A được gọi là khả nghịch nếu tồn tại ma trận vuông cùng cấp B sao cho AB =BA = I . Phép nhân ma trận có tính kết hợp nên ma trận B ở định nghĩa trên nếu tồn tại thì duy −1 nhất, ta gọi ma trận này là ma trận nghịch đảo của A, ký hiệu A . 4.5.2 Điều kiện cần và đủ để tồn tại ma trận nghịch đảo Định lý 4.5: (điều kiện cần) Nếu A khả nghịch thì det A ≠ 0 (lúc đó ta nói ma trận A không suy biến). −1 −1 −1 Chứng minh: AA = I ⇒ det Adet A = det AA = det I = 1. 74
Chương 4: Định thức 1 Do đó det A = ≠ 0 . det A−1 Định nghĩa 4.5: Ma trận BA= , trong đó A là phần bù đại số của phần tử a []ij n× n ij ij của ma trận A= a , được gọi là ma trận phụ hợp của A. []ij n× n Định lý 4.6: (điều kiện đủ) Nếu det A ≠ 0 thì A khả nghịch và −1 1 t A = B , (4.19) det A với B là ma trận phụ hợp của A. Chứng minh: Khai triển định thức của ma trận A theo hàng thứ k ta được: ak1 A k 1 + + akn A kn = det A Vậy ai1 Ak 1 + + ain A kn là khai triển theo hàng thứ k của định thức của ma trận có được bằng cách thay hàng thứ k của A bởi hàng thứ i của A, do đó bằng 0. ⎧det A nÕu i= k t Tóm lại ai1 A k 1 + + ain A kn = ⎨ ⇒ AB = (detAI ) . ⎩0 nÕu i≠ k Tương tự, khai triển theo cột ta có: ⎧det A nÕu i= k t a1i A 1 k + + ani A nk = ⎨ ⇒ BAAI= (det ) . (4.20) ⎩0 nÕu i≠ k −1 −1 Hệ quả 4.7: Nếu BA = I hoặc AB = I thì tồn tại A và A = B . −1 Chứng minh: BA = I ⇒ det A ≠ 0 ⇒ ∃A và −1 −1− 1 B= B()() AA = BA A= A . ⎡1 2 3⎤ ⎢ ⎥ Ví dụ 4.9: Ma trận A = 2 5 3 có det A = − 1. ⎢ ⎥ ⎣⎢1 0 8⎦⎥ 1+ 1 5 3 1+ 2 2 3 A =( − 1) = 40 , A =( − 1) = −13, 11 0 8 12 1 8 75
Chương 4: Định thức 1+ 3 2 5 2+ 1 2 3 A =( − 1) = −5 , A =( − 1) = −16 , 13 1 0 21 0 8 2+ 2 1 3 2+ 3 1 2 A =( − 1) = 5 , A =( − 1) = 2, 22 1 8 23 1 0 3+ 1 2 3 3+ 2 1 3 A =( − 1) = −9 , A =( − 1) = 3 , 31 5 3 32 2 3 3+ 3 1 2 A =( − 1) =1 , 33 2 5 Vậy t ⎡ 40− 13 − 5⎤ ⎡ 40− 16 − 9⎤ ⎡− 40 16 9 ⎤ −1 1 ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ A = −16 5 2 = − −13 5 3 = 13− 5 − 3 . −1⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣⎢ − 9 3 1 ⎦⎥ ⎣⎢ − 5 2 1 ⎦⎥ ⎣⎢ 5− 2 − 1⎦⎥ 4.5.3 Tìm ma trận nghịch đảo theo phương pháp Gauss-Jordan Khi ta thực hiện liên tiếp các phép biến đổi sơ cấp lên các hàng của ma trận A để đưa A về ma trận đơn vị, theo tính chất 3.5 chương 3 thì điều này cũng có nghĩa là ta nhân bên trái của A các ma trận sao cho EEAI1 k = , trong đó EE1, , k là các ma trận dạng R(,)k λ , −1 P(,)i j , Q(,,) i j λ (xem 3.10, 3.11, 3.12). Mặt khác theo Hệ quả 4.7 thì AEE= 1 k . Cũng với lập luận như trên ta có: EEEEI1 k = 1 k là ma trận có được bằng cách thực hiện bởi cùng các phép biến đổi sơ cấp tương ứng như đã thực hiện đối với ma trận A lên −1 các hàng của ma trận đơn vị I . Vì vậy để tìm ma trận A ta thực hiện các bước sau: 1) Viết ma trận đơn vị I bên phải ma trận A: AI 2) Thực hiện các phép biến đổi sơ cấp đồng thời lên các hàng của AI để đưa ma trận A ở vế trái về ma trận đơn vị. −1 3) Khi vế trái trở thành ma trận đơn vị thì vế phải là ma trận A . −1 AI → → IA . (4.21) 76
Chương 4: Định thức ⎡1 2 3⎤ −1 ⎢ ⎥ Ví dụ 4.10: Tìm A với A = 2 5 3 ⎢ ⎥ ⎣⎢1 0 8⎦⎥ 1 2 3 1 0 0 h1→ h 1 1 2 3 1 0 0 −2h1 + h2 → h 2 2 5 3 0 1 0 −h1 + h3 → h 3 0 1− 3 − 2 1 0 1 0 8 0 0 1 → 0− 2 5 −1 0 1 h→ h 1 2 3 1 0 0 h1→ h 1 1 2 3 1 0 0 1 1 −h → h h→ h 2 2 2 2 0 1− 3 − 2 1 0 −h3 → h 3 0 1− 3 − 2 1 0 2h2+ h 3 → h 3 → → 0 0− 1 − 5 2 1 0 0 1 5− 2 − 1 −3h3 + h 1 → h 1 1 2 0 − 14 6 3 −3h2 + h 1 → h 1 1 0 0 − 40 16 9 3h+ h → h h2→ h 2 3 2 2 0 1 0 13− 5 − 3 h→ h 0 1 0 13− 5 − 3 h3→ h 3 3 3 → 0 0 1 5− 2 − 1 → 0 0 1 5− 2 − 1 ⎡− 40 16 9 ⎤ −1 ⎢ ⎥ Vậy A = 13− 5 − 3 . ⎢ ⎥ ⎣⎢ 5− 2 − 1⎦⎥ −1 −1 Chú ý 4.8: Tìm A theo phương pháp Gauss-Jordan sẽ dễ dàng khi các phần tử của A là các số nguyên ( thường gặp khi det A = ± 1). 4.6 TÌM HẠNG CỦA MA TRẬN BẰNG ĐỊNH THỨC Từ tính chất 4.2 ta biết rằng định thức của một hệ phụ thuộc tuyến tính bằng 0. Do đó nếu định thức DB {} v1, , vn ≠ 0 thì hệ {v1, , vn} độc lập tuyến tính. Ngược lại, giả sử hệ {v1, , vn} độc lập tuyến tính, ta sẽ chứng minh n DB {} v1, , vn ≠ 0 . Thật vậy, giả sử vj= ∑ a ij e i , A= [ aij ] , i=1 det A= DB {} v1, , vn , vì hệ {v1, , vn} độc lập tuyến tính nên nó là một cơ sở của V . 77
Chương 4: Định thức n Vậy ta có ej= ∑ b ij v i , B= [ bij ] ⇒ AB = I ⇒ det A ≠ 0 . (4.22) i=1 Định lý 4.9: Hệ {v1, , vn} độc lập khi và chỉ khi DB { v1, , vn}≠ 0 . Định lý 4.10: Giả sử A= [] aij là một ma trận cỡ m× n . Nếu có định thức con cấp p khác 0 và mọi định thức con cấp p +1 bao quanh nó đều bằng 0 thì r()A = p . Chứng minh: Không mất tính tổng quát ta có thể giả thiết định thức con cấp p góc trái 1, , p M1, , p ≠ 0 . Khi đó p véc tơ cột đầu độc lập tuyến tính, vì nếu có một véc tơ là tổ hợp tuyến 1, , p tính của p −1 véc tơ còn lại thì mâu thuẫn với giả thiết M1, , p ≠ 0 , do đó r()A ≥ p . Ta cần chứng minh bất đẳng thức ngược lại. Với mọi k =1, ,m ; s =p +1, , n ; Xét ma trận cấp p +1: ⎡a11 a1p a 1 s ⎤ ⎢a a a ⎥ ⎢ 21 2p 2 s ⎥ B = ⎢ MMMMM ⎥ ⎢ ⎥ ⎢a p1 app a ps ⎥ ⎢ ⎥ ⎣ak1 akp a ks ⎦ Khi k ≤ p : Ma trận B có hai hàng bằng nhau, do đó det B = 0 . 1, , p Khi k > p : det B = 0 , vì det B là định thức cấp p +1 bao M1, , p . Mặt khác khai triển theo hàng cuối ta được dạng sau: 1, , p ak1μ 1 + +akpμ p + a ks M1, , p = 0 ⇒ aks=λ1 a k 1 + + λ pa kp , với mọi k = 1, 2, , m Vì vậy véc tơ cột vs là tổ hợp tuyến tính của p véc tơ cột đầu. Vậy r()A ≤ p . t Hệ quả 4.11: A là một ma trận cỡ m× n thì r( A )= r ( A ) ≤ min() m , n . 78