Tài liệu Giáo trình đại số

GHM Ỉ1 48 HỌC VIỆN CÔNG NGHỆ Bưu CHÍNH VlỀN THÔNG PGS. TS. LÊ BÁ LONG Giáo trình ĐẠI số NHÀ XUẤT BẢN THÔNG TIN VÀ TRUYỂN THÔNG QD24 HM 09 LỜI NÓI ĐẦU Đại số (Toán cao cấp A2) là một trong các học phần đầu tiên của chưong trình toán cao cấp bắt buộc dành cho sinh viên năm thứ nhất thuộc các nhóm ngành kỹ thuật. Để phục vụ nhu cầu giáo trình cho sinh viên học tập. lỉọc viện Công nghệ Buu chính Viễn thông phối hợp với Nhà xuất bản Thông tin và Truyền thông xuất bàn “Giáo trình Đại s ổ ” do PGS.TS. Lê Bá Long biên soạn. Giáo trình được biên soạn trên nền chương trình khung của Bộ Giáo dục - Đào tạo và theo đề cương chương trình cùa Học viện Công nghệ Bưu chính Viễn thông phê duyệt năm 2007 cho hệ đào tạo chính qui, và có sự tham kháo các giáo trình của các trường đại học kỳ thuật, cùng kinh nghiệm giảng dạy nhiều năm của tác giá. Giáo trình gồm 7 chương: Chương ỉ: Logic toán học. lý thuyết tập hợp, ánh xạ và các cấu trúc đại số Chương 2: Không gian véc tơ Chương J. Ma trận Chưrmg 4' Định thức Chương 5: Hệ phương trình tuyến tính Chương 6: Ảnh xạ tuyến tính Chương 7: Không gian véc tơ Euclide và dạng toàn phươ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. Trước khi nghiên cứu các nội dung chi tiết, bạn đọc nên xem phần giới thiệu cùa mồi chương cũng như mục đích cùa từng chương để thấy được mục đích ý nghTa, yêu cầu chính của chương đó. Trong mồi chương, mỗi nội dung, bạn đọ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 dọc nên chú ý đến các nhận xét. binh luận đê hiêu sâu hơn hoặc mở rộnu tôim quát hơn các kết quá. Hầu hết các bài toán trong giáo trinh này dược xây dựng theo lược đồ: Đặt bài toán, chứng minh sự tồn tại lời giai 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à>. Các ví dụ là để minh họa 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. Cuối mỗi chương đều có các bài tập sắp xếp từ dễ đến khó. Các bài tập dề chi kiểm tra trực tiếp nội dung vừa học, còn các bài tập khó đòi hoi phải sử dụng các kiến thức tổng hợp. Giáo trình này được viết chung cho ba ngành Diện từ, Viễn thông và Công nghệ Thông tin. vì vậy trong quá trình giảng dạy và học tập có thể lựa chọn nội dung trọng tâm và nội dung tham kháo tùy thuộc vào ngành. Sinh viên cùa ba ngành này có khá năng sử dụng tốt công cụ công nghệ thông tin trong quá trinh học tập. Vì vậy tác giả rất có ý thức trình bày các khái niệm và kết quả dưới dạng thích hợp nhất đế người học có thể hình thành thuật toán và lập trình. Ngoài ra giáo trình sẽ là tài liệu học tập và tham khảo hữu ích cho sinh viên cua lất cả các trường đại học và cao đẩng kỳ thuật trong cả nước Tuy ràng tác già đã rất cố gắng trong quá trình biên soạn, song khó tránh khỏi thiếu sót. Rất mong nhận được sự góp ý cua bạn bè đồng nghiệp và bạn đọc. Mọi ý kiến góp ý xin gứi về Khoa Cơ bán 1H ụt viện Công nghệ Đưu chínli Viẽii lliùiig. Xin trân trọng giới thiệu cùng bạn đọc! HỌC VIỆN CÓNG NGHỆ Bưu CHỈNH VIẼN THÔNG MỤC LỤC Lời nói đ a u .......................................................................................................3 Chưo-ng 1: MÓ ĐÀU VÈ LOGIC MỆNH ĐÈ, TẬP HỢP ÁNH XẠ VÀ CÁC CÁU TRÚC ĐẠI S Ổ ....................................................... 11 1.1. Sơ lưọc về logic mệnh đ ề ................................................................. 13 1.1.1 Mệnh đề.........................................................................................13 1.1.2 Các phép liên kết logic mệnh đ ề ............................................... 14 1.1.3 Các tính chất................................................................................. 15 1.2. Tập họp................................................................................................. 16 1.2.1 Khái niệm tập hcrp....................................................................... 16 1.2.2 Cách mô tà tập h ợ p .....................................................................17 1.2.3 Các tập họp số thường gặp......................................................... 18 1.2.4 Tập con..........................................................................................18 1.2.5 Các phép toán trên các tập h ợ p ................................................. 19 1.2.6 Lượng từ phố biến và lượng từ tồn tạ i ......................................21 1.2.7 Phép hcTp và giao suy rộng.........................................................22 1.3. Tích Descartes và quan h ệ ............................................................... 23 1.3.1 1 ích Dcscartes cùa các tập hợp................................................. 23 1.3.2 Quan hệ hai n gôi.........................................................................24 1.3.3 Quan hệ iương đương................................................................. 25 1.3.4 Quan hệ thứ tự............................................................................. 26 1.4. Ánh x ạ ................................................................................................... 28 1.4.1 Định nghĩa và ví d ụ .....................................................................28 1.4.2 Phân loại các ánh x ạ.................................................................... 31 1.4.3 Ánh xạ ngược cùa một song ánh...............................................34 1.4.4 Hợp của hai ánh xạ......................................................................35 1.4.5 Lực lượng cùa một tập hợ p........................................................36 1.5. So lưọc về phép đếm, giải tích tổ hụp - nhị thức Nen ton........37 1.5.1 Sơ lược về phép đếm................................................................... 3 7 1.5.2 Hoán vị, phép th ế ........................................................................ 38 1.5.3 Chình hợp..................................................................................... 39 1.5.4 Tổ h ợ p ........................................................................................... 41 1.5.5 Nhị thức Nevvton......................................................................... 42 1.6. Các cấu trúc đại số..............................................................................44 1.6 .1 Luật hợp thành trong...................................................................44 1.6.2 Nhóm.............................................................................................46 1.6.3 Vành.............................................................................................. 47 1.6.4 Trưòng...........................................................................................50 1.7. Đại số Boole.......................................................................................... 51 1.7.1 Định nghĩa và các tính chất cơ bán cùa đại số Boole.............. 51 1.7.2 Công thức Boole, hàm Boole và nguyên lý đối n g ẫ u .............52 1.7.3 Phương pháp xây dựng hàm Boole thỏa mãn giá trị cho trước...........................................................56 1.7.4 ủ n g dụng đại số Boole vào mạng chuyển m ạch.......................57 Bài lập chươnỊĩ I .......................................................................................... 62 Chương 2: KHÔNG GIAN VÉC T ơ ........................................................... 71 2.1. Khái niệm không gian véc t ơ ............................................................72 2.1.1 Định nghĩa và các ví dụ............................................................... 72 2.1.2 Tính chất........................................................................................ 75 2.2. Không gian véc tơ c o n ........................................................................76 2.2.1 Định nghTa và ví d ụ ..................................................................... 76 2.2.2 Không gian véc rơ con sinh bớimột hệ véc tơ...........................78 2.2.3 Tông cùa một họ không gian véc tơ co n ................................... 80 2.3. Độc lập tuyến tính, phụ thuộc tuyến tính...................................... 82 2.4. Hạng của một hệ hữu hạn các véc t ơ ..............................................84 2.4.1 Hệ con dộc lập tuyến tính tối đ ạ i ...............................................84 2.4.2 Hạng cứa một hệ hĩai hạn các véc t ơ ......................................85 2.5. Co' sở, số chiều của không gian véc tơ.............................................87 Bùi lập cìnarng 2 .......................................................................................... 94 Chương 3: MA TRẬN.................................................................................. 103 3.1. Khái niệm ma trận............................................................................ 105 3.2. Các phép toán ma trận.....................................................................106 3.2.1 Phép cộng ma trận......................................................................106 3.2.2 Phép nhân một số với ma trận.................................................. 106 3.2.3 Phép nhân ma trận...................................................................... 108 3.2.4 Đa thức ma trận...........................................................................111 3.2.5 Ma trận chuyển vị....................................................................... 111 3.3. Ma trận của một hệ véc t ơ ...............................................................112 3.3.1 Định nghĩa ma trận cua một hệ véc t ữ .................................... 112 3.3.2 Ma trận chuyển cơ s ờ .................................................................113 3.4. Hạng của ma tr ậ n ..............................................................................115 3.4.1 Định nghĩa và cách tìm hạng của ma trận bàng phép biển đối sơ cấp......................................................... 115 3.4.2 Các ma trận tưcmg ứng với các phépbiến đổi sơ c ấ p .......... 116 Bùi lập chiamg 3 .........................................................................................119 Chưong4: DỊNH THỨC..............................................................................125 4.1. Hoán vị và phép th ế .......................................................................... 126 4.2. Định nghĩa định thức........................................................................ 130 4.3. Các tính chất cơ bản của định th ứ c.............................................134 4.4. Các cách tính định th ứ c ...................................................................137 4.4.1 Khai triến theo hàng, theo c ộ t...................................................137 4.4.2 Định lý khai triển Laplace (theo khàng k cột).........................139 4.5. ủ n g dụnng định thức để tìm ma trận nghịch đ ả o .....................145 4.5.1 Dịnh nghĩa ma trận nghịch đ ả o ................................................ 145 4.5.2 Điều kiện cần và đủ để tồn tại ma trận nghịch đ á o ............... 145 4.5.3 Tìm ma trận nghịch đảo theo phương pháp Gauss-Jordan.. 148 4.6. Tìm hạng của ma trận bằng định thức........................................ 150 Bài tập chương 4 ........................................................................................ 154 Chương 5: HỆ PHƯƠNG TRÌNH TUYẾN T ĨN H .................................. 163 5.1. Khái niệm về hệ phưoìig trình tuyến tín h ................................... 165 5.1.1 Dạng tổng quát cùa hệ phương trinh tuyến tính.....................165 5.1.2 Dạng ma trận cùa hệ phương trình tuyến tính........................ 166 5.1.3 Dạng véc tơcúa hệ phương trinh tuyến tính........................ 166 5.2. Định lý tồn tại nghiệm................................................................... 167 5.3. Phưong pháp Cramer....................................................................... 168 5.3.1 Hệ Cramer và cách giái............................................................. 168 5.3.2 Giải hệ phương trình tuyến tính trường hợp tổng q u á t...... 169 5.4. PhưoTig pháp ma trận nghịch đảo.................................................. 171 5.5. Giải hệ phưoìig trình tuyến tính bằng phưoìig pháp khử G au ss............................................................................................172 5.6. Hệ phưong trình tuyến tính thuầnnhất...................................... 177 Bùi tập chương 5 .........................................................................................183 Chương 6: ÁNH XẠ TUYÊN TÍNH......................................................... 189 6.1. Khái niệm ánh xạ tuyến tính........................................................... 190 6.1.1 Định nghĩa và ví d ụ ....................................................................190 6 .1.2 Các tính chất................................................................................ 192 6 .1.3 Các phép toán cùa các ánh xạ tuyến tín h ................................ 194 6.2. Nhân và ảnh của ánh xạ tuyến tính............................................... 196 6.3. Toàn cấu, đơn cấu, đẳng c ấ u .......................................................... 199 6.3.1 Toàn cẩu.......................................................................................199 6.3.2 Dơn c ấ u ...................................................................................... 200 6.3.3 [)ãng cấu......................................................................................201 6.4. Ánh xạ tuyến tính và ma trận.......................................................203 6.4 . 1 Ma trận cùa ánh xạ tuyến tính................................................. 203 6.4.2 Ma trận cùa ánh xạ tuyến tính trong các cơ sở khác nhau .. 208 6.4.3 Biêu thức tọa độ cùa ánh xạ tuyến tính.................................. 212 6.4.4 Anh xạ tuyến tính và hệ phưong trinh tuyến tín h ................213 6.5. Chéo hoá ma trận............................................................................. 216 6.5.1 Không gian con bất b iế n .......................................................... 217 6.5.2 Véc tơ riêng, giá trị riêng......................................................... 217 6.5.3 Đa thức đặc trưng...................................................................... 219 6.5.4 Tự đồng cấu chéo hoá đ u ợ c .....................................................223 6.5.5 Thuật toán chéo h o á ..................................................................225 Bùi tập chương 6 ........................................................................................234 ChưoTig 7: KHÔNG GIAN VÉC Tơ EUCLIDE VÀ DẠNG TOÀN PHƯƠNG........................................... !...................... 247 7.1. Dạng song tuyến tính....................................................................... 250 7.1.1 Định nghĩa dạng song tuyến tín h ............................................ 250 7.1.2 Ma trận và biểu thức toạ độ cùa dạng songtuyếntính........... 251 7.1.3 Biểu thức toạ độ của dạng song tuyến tính trong các cơ sở khác nhau........................................................ 252 7.2. Dạng toàn phương............................................................................254 7.2.1 Định nghTa dạng toàn phương..................................................254 7.2.2 Dạng cực của dạng toàn phương............................................. 255 7.2.3 Ma trận và biều thức toạ độ cùa dạng toànphương............. 255 7.2.4 Biểu thức toạ độ dạng chính tác cúa dạng toàn phương.... 256 7.2.5 Đưa về dạng chính tẳc theo phương pháp Lagrang..............257 7.2.6 Đưa về dạng chính tấc theo phương pháp Jacobi.................. 260 7.2.7 Luật quán tín h ............................................................................265 7.3. Tích vô hưóng, không gian véc to Euclide................................. 269 7.3.1 Định nghTa vô hướng và tính chắt........................................... 269 7.3.2 Trực giao - trực chuân hoá Gram-Shmidt...............................271 7.3.3 Cơ sở trực ch u ẩn ........................................................................274 7.3.4 Không gian con trực giao, phần bù trực giao......................... 275 7.4. Ma trận trực giao và ánh xạ tuyến tínhtrực giao..................... 278 7.4.1 Ma trận trực giao........................................................................278 7.4.2 Ánh xạ luyến tính trực giao...................................................... 280 7.4.3 Ma trận cùa tự đăng cấu trực giao............................................ 281 7.5. Chéo hoá trực giao ma trận - tự đồng cấu đổi xứng................ 283 7.5.1 Bài toán chéo hoá trực giao.......................................................283 7.5.2 Tự đồng cấu đối xứng............................................................... 283 7.5.3 Ma trận cúạ một tự đồng cấu đối xứng trong một cơ sớ trực chuẩn.......................................................284 7.5.4 Thuật toán chéo hoá trục giao.................................................. 287 7.5.5 Đưa biểu thức toạ độ cùa dạng toàn phưomg về dạng chính tẩc bàng phuơng pháp chéo hóa trực giao.................................... 289 7.6. Đường bậc 2 trong mật phang và mặt bộc 2 trong không gian ...........................................................................................290 7.6.1 Hệ toạ độ trực chuấn trong mặt phăng.................................... 290 7.6.2 Hệ toạ độ trực chuân trong không gian....................................295 Bài tập chươnịỊ 7 .........................................................................................305 Hướng dẫn giải bài tập.............................................................................315 Phụ lục 1 .......................................................................................................377 Phụ lục 2 .......................................................................................................384 Băng tra c ứ u ............................................................................................... 389 Tài liệu tham khảo..................................................................................... 394 ChưoTig I MỞ ĐẦU VỀ LOGIC MỆNH ĐỀ, TẬP HỢP, ÁNH XA VÀ CÁC CẤU TRÚC ĐAI số Toán học là một ngành khoa học lý thuyết được phái triên trên cư sờ tuân thu nghiêm ngặt các qui luật lập luận cua lư duy logic hinh thức. Các qui luật cơ bán cua logic hinh thức đã dược phát triền từ thời Aristote (Anì-xtốt) (thế kv thứ III trước Công nguvên) cùng với sự phát triên rực rờ cua văn minh cô Hy Lạp. Tuy nhiên mãi đến thế ký XVll với những còng trình cua De Morgan (Đờ Moócgan), Boole ... thì logic hinh thức mói có một cấu Irúc đại số đẹp đẽ và cùng với lý thuyết tập hợp giúp làm chính xác hoá các khái niệm toán học và thúc đẩy toán học phát triến mạnh mẽ. Việc nấm vững logic hình thức không những giúp sinh viên học tốt môn toán mà còn C(S thê vận dụng trong thực tế và biết lập luận một cách chính xác. Học tốt môn logic là cơ sớ dê học lốt đại số lỉoole. vận dụng đê giai các bài toán về sơ đồ còng tãc rưlc. kv thuậl sỏ và công ngliộ ihông tin. Yêu câu cùa phân này là phai nắm vừng khái niệm mệnh đề toán học. các phép liên kết mệnh đề và các tính chất của chúng. Khái niệm lập hcifp. ánh xạ và các cẩu trúc đại số là các khái niệm cơ ban; vừa là công cụ vừa là ngôn ngừ cùa toán học hiện đại. Vì vai trò nền táng cúa nó nên khái niệm lập hợp được đưa rất sớm vào chưc^ng irình toán phố thông (toán IcVp 6 ). Khái niệm lập htTp được Cantor (Cãng-to) đưa ra vào cuối thế kv XIX. Sau đỏ được chính xác hoá bàng hệ liên đề về tập hcTp. Có thề tiếp thu lý thuyết tập hợp theo 12 ( iicìo trình Dại sỏ nhiêu mức dộ kliác nhau, Chúng la chi tiòp cận lÝ lhu\êt tập hợp ơ mức dộ trực quan kcl iiợp với các phep loán lotiic hình iliức như "\á". "hoặc", phép kéo theo, phép tương dương, lượng từ phô biến, lượng lừ tồn tại. Với các phép toán logic này ta có tương ứng các phép loán giao. hợp. hiệu các tập hợp con của các tập hợp. rrẽn cư sơ lích Descartes (ỉ)ề-các) cua hai tập hcTp ta có khái niệm quan hệ hai ngôi mà hai Irường hợp đặc biệt là quan hệ tương đương và quan hệ thứ tự. Quan hệ tưcTng đưưna được dùng đc phân một tập nào đó thành các lớp không giao nhau, gọi là phàn hoạch cua tập đó. Quan hệ đồng dư modulo p là một quan hệ tưưng dircTim trong tập các số ngu\ên. Tập thưcTng cua nó là tập 2 , các số nguyên modulo p. Tập 2 ^ , có nhiều ứng dụng trong lý thu\et mậi mà. \ê an toàn mạng. Quan hệ thứ tự dược dùng đê sẩp xếp các đổi tượng cần xét theo mội thứ tự dựa trên tiêu chuân nào đó. Quan hệ < trone các tập ín.tp so là các quan hệ thứ tự. Khái niệm ánh xạ là sự mơ rộng khái niệm hàm số dã được biết. Khái niệm nàv giúp ta mô tá các phép tưOTg ứng từ một tập này đén tập kia thoa mãn điều kiện ràng mồi phần tư cua tập nguồn chí cho ứng với một phần tư duy nhất cua tập đích và rnọi phân lứ cùa tập nguồn dều được cho ứng với phần tư cua tập đích. {) dâu có tương ứng thì ta có thê mô la được dưới ngôn ngừ ánh xạ. Sứ dụng khái niệm ánh xạ và tập hợp la khao sát các vấn dề cua giái tích tổ hợp. dỏ là các phương pháp dếm số phần tư cua tập hợp. Giải tích tồ hợp được áp dụng đế giái quyết các bài toán xác suất thống kê và toán học rời rạc. Chúne ta có thê ihực hiện các phóp toán: cộng các số. hàm số. đa thức, véc tơ hoặc nhân các số. hàm số. da iliức... Như vậy la có thê thực hiện các phép loán nà\ trên các dổi tượng khác nhau. C'ái chung cho mỗi phép toán cộng hay nhân ở irên là các tính chất giao hoán, kết hợp, phân bố... Một tập hợp có phép loán thoá mãn điều kiện nào đó ( 'hiarn^ I : Xííí đau IV loịỊÌc mệnh ííè. lập hợp... 13 dược gọi là có câu trúc dại sô tương ứng. Các câu trúc dại sô quan trọng thường gặp là nhỏm. vành, trường, không gian véc tơ. Dại số học là một ngành cua loán học nghiên cứu các cấu trúc đại sổ. Lý thuvết Nhỏm dược Hvarisl Cìaiois ((ìaloa) dưa ra vào đầu thế ki XIX trong công trình "Trong những điều kiện nào thi một phưtĩng trinh đại số cỏ thể giai dược?", trong đó Galoa vận dụng lý thuyết nhóm để giái quvết. Trên cơ sơ lý thuyết nhóm người la phái triên các cấu trúc đại số khác. Việc nghiên cứu các câu trúc dại số giúp ta tách ra khoi các dối lượng cụ thê mà thấy được cái chung cua từng cấu trúc dê khao sát các tính chất, các đặc trưng cua chúng. Chàng hạn. tập các ma trận vuông cùng cấp. các lự dồng cấu tuvến tính, các đa thức... có cấu trúc vành không nguyên nên có những tính chất chune nào đó. Các câu trúc đại so cỏ tính khái quát hoá và trừu tượng cao vì vậy người ta nghĩ ràng khó áp dụng vào thực tiễn. l u\ nhiên thực tế cho thấy dại số Boole được ứng dụng rất hiệu qua trong việc giái quyết các bài toán về sơ dồ mạch điện, trong công nghệ thông tin và kv thuật số. Lý thuvết nhóm dược ứng dụng vào cơ học lượng từ. Lv thuyết vị nhóm và vành được ứng dụng trong lý thuyết mật mã. lý thuyết Ỏtômál. rhưíTng 1 trình hày một cách sơ krợc các cấu trúc: Nhóm. vành. trưcTng và đại số Boole. Các chương còn lại cua cuốn sách này liên quan đến đại số tuvến tính. 1.1 SO LƯỢC VÈ LOGIC MỆNH ĐÈ 1.1.1 Mệnh đề Logic mệnh đè là một hệ thống logic đơn gian nhất, với đcTrn 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. 14 Cĩiủo irinh ỉ)ại sô t)ê chi các mệnh dê cliưa xác dịnli la dùng các chừ cái p. (Ị. r... và gọi chúng là các biến mệnh dề. Nếu mệnh dề p dúng ta cho p nhận giá trị 1 và p sai ta cho nhận giá trị 0. (ìiá trị I hoặc 0 dược gọi là thé hiện cua p . Mệnh đê phức hợp dược xây dựng lừ các mệnh đê dơn gian hơn bâng các phép liên két logic mệnh dè. 1.1.2 Các phép liên kết logic mệnh đề /. Phép phu định (negation): Phu định cua mệnh đê p lù mệnh đê được ký hiệu p đọc là không p . Mệnh đê p dúrm khi p sai và p sai khi p đúng. 2. Phép hội (conịunction); Hội cua hai mệnh đê p, q là mệnh đê đirợc ký' hiệu p ^ q (đọc là p và q). Mệnh đề p ^ q chi đủng khi p và q cùng đúna. i. Phép tuyên (disịuncũon): Tuyên cua hai mệnh đê p. Cị là mệnh đê được kỹ' hiệu p ^ q (đọc lò p hoặc q). p\^cỊ chi 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 => <7 . là mệnh dc chi sai khi p dũng q sai. 5. Phép tưov^ đinmg (equivalcnce): Mệnh đê ị p => q) A (q => p ) được gọi là mệnh đề p tin m ọ , đ ư o n ^ q . ký hiệu p <=>C Ị . MỘI công ihức gồm các biến mệnh đề và các phép liên kèl 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 dè dirợc gọi là háng chán trị cùa công thức đó. Từ định nghía cua các phép liên kết mệnh dề ta có các báng chân trị tưcmg ứng sau: 15 ( 'hudnịỊ l : Mo ííâii vê loịỊÌc mệnh đô. tập hợp... p p 1 0 0 1 p pz=>q p pACf p^q 1 1 1 1 1 {) ơ 1 0 1 0 1 0 0 0 0 p ^q p p p o 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 (3 1 0 0 1 1 1 Như vậv /7 <=> í/ 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 o 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 với 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ưcTTie đưtmg hàng đúng là " = " thay cho " <=> 1.1.3 Các tính chất Dùng bàng chân irị ta dễ dàng kiểm chứng các mệnh đề hằng đúng sau: luật phú định kép. \) p = p 2) {p=>cỊ) = { p v q). 3) p /\ q = Cf A p. p 4) p A .{q Aỉ - ) V q = q \/ p luật giao hoán. = (p A q ) A r : p \ / ( q\ / r) = ( p v r 5 ) [ p A ( í / V /•)] = [ ( /? A ợ ) v ( / ? A r ) luật kết hợp. 16 (iiáo írinh Dọi .vô p V ịq A r)] = ị( p V cị) A ị p V r) 6 ) Mệnh đề p p V A p luôn dũng luật hùi tri/níỊ. p luôn sai 7) p \ / q = p /\ LỊ : p ACỊ luật phân phôi. ìiiật mỏu thuần. = q luật De Morgan. luật phan chứng, 9) p v p = p: p \iì) p v ị p A p =p A q ) = p: luật lũy đãn^. p A ( p v q ) = p ìuặr hdp thu. 1.2 TẠP HỢP 1.2.1 Khái niệm tập họp Khái niệm "tập hc.yp". "phần tứ" và "thuộc" là các 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ếl. Các khái niệm "tập họp", "phần tứ" xét trong mối quan hệ phần lư cua tập hợp trong lÝ ihuyếl tập hợp là giống với khái niệm "đường thãng". "điêm" và quan hệ điêni thuộc đường thăng dược xét trong hình học. Một cách trực quan, ta có thế xem tập hợp như một sự tụ lập các vậl, các đối lượng nào dó mà mỗi vật hav đối tượng là một phan tư cua tập hợp. Tập hcTp dirợc dặc trưng lính chất ràng một phàn tứ bất kỳ chỉ có thể hoặc ihuộc hoặc không thuộc tập hcrp. Có thê lấ>' ví dụ về các tập hợp cỏ nội dung toán học hoặc không loá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ử cua nó là các số 0. 1. 2, 3. ... còn tập hợp các cuốn sách troníỉ ihư viện cua Học \ iộn Công nghệ Bưu chính Viễn ihòng là tập hợp mà các phần lừ cúa nỏ là các cuốn sách của Học viện. Ta ký hiệu các tập hợp bơi các chừ in hoa /í, B.... X , K.... còn các phần tứ bởi các chữ thưÌTTig ký hiệu .V .V. V.... Nếu .V là phần tư cúa tập A ta e A và nói A* thuộc Ả . nếu -V không là phần tư của A ta ký 17 Chươríịỉ, l : M ơ đầu vè ìoịiic mệnh đề, tập hợp... hiệu x í A và nói A' không thuộc A . Ta cũng nói tắt "tập" thay cho thuậl ngữ "tập hcyp". Định nghĩa 1.1: Hai tập hợp A. B băng nhau, ký' hiệu A = B . nếu mọi p hán tư cùa A là phán tử của B và ngược lại mọi phán tứ cùa B là phan tứ của A . 1.2.2 Cách mô tả tập họp 'ĩ'a thường mô tả tập htrp theo các cách sau: a) Liệt kê tất cà các phần từ của tập hcTp trong dấu ngoặc nhọn Ví dụ 1.1: Tập các sổ tự nhiên lẻ nhỏ hơn 10 là {l, 3, 5, 7, 9 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 Có những tập hợp không thề liệt kê các phần tứ cùa chủng, khi đó ta mô tả tập hợp này bằng cách đặc trưng các tính chất cùa phần tử tạo nên tập hợp. Ví dụ 1.2; Tập hợp các sổ tự nhiên chằn : p = Ịa7 €N| n = 2 m, m eNỊ . Tập hợp có thể được mô tả bằng cách nêu tính chất đặc trưng cúa các phàn lử thông qua khái niệm hàm m ệnh đề. Hàm mệnh đề xác định trong tập hợp D là một mệnh đề S{x) phụ thuộc vào biến x e D . Khi cho biến X một giá trị cụ thể thì ta được mệnh đề logic (mệnh đề chỉ nhận một trong hai giá trị hoặc đúng hoặc sai). Giá sứ Ẵ'(.v) là một mệnh đề xác định trong tập hợp D, ta gọi tập hợp các phần tử x e D sao cho mệnh đề S{ x) và ký hiệu đủng là miền đúng cùa hàm Giáọ trình Dại ,w 18 Ví dụ 1.3: i) Xét hàm mệnh đề S( x) xác định trên tập các sổ tự nhiên N: " x ' + 1 là một số nguyên tố" thì .S'(l).5(2) đúng và 5 (3 ),5 (4 ) sai... ii) Mỗi một phương trinh có thể xem là một hàm mệnh đề có miền đúng là tập nghiệm. Ị. v 6 Z | x ' - 1 = o | = {-1, 1}. c) Gián đồ Venn: Đê có hình anh 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 đưcmg cong khép kín không tự cất được gọi là ẹián đồ Venn. Cần chú ý rằng gián đồ Venn chi là hình ánh trực quan minh họa một tập hợp nào đó. Giản đồ Venn biểu diễn tập A không phải là tập A,vì vậy không thể sử dụng giản đồ Venn trong phép chứng minh. 1.2.3 Các tập họp số thưòTig gặp - Tập các số tự nhiên N = | 0 , 1. 2. . . . | . - Tập các số nguyên 2 = {0, ± 1, ± 2,...}. - Tập các số hữu ti Q = Ị p Ịq q ^ 0 , p ,q . - Tập các số thực IR (gồm các số hữu tỉ và vô ti). - Tập các số pVìức c Ị z - -V-t- /v X. V’ fciR. = -1 Ị . 1.2.4 Tập con Định nghĩa 1.2: 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 a B hoặc A. Khi A là tập con của B ihì ta còn nói A chứa trong B hay B chửa A hay B bao hàm A . Tacó: N c Z c Q c l R c C . 19 Chương 1: M ớ đầu về ÌOỊỊÌC mệnh để. tập hợp... Từ định nghĩa 1.1 và 1.2 ta có : A = B khi và chi khi A d B và Bcz A . Như vậy đề chứng minh /4 c ổ ta chi cần chứng minh : X e A=> X e B . Do đó để chứng minh A = B ta chi cần chứng minh: Xe A o Xe B . Định nghĩa 1.3: Tập rong là tập không chứa phan từ nào, ký> hiệu 0 . 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. Ví dụ 1.4: Xél X = ịxe2L\x^ = 4 ,jr lẻ | thì X = 0 . Tập hợp tất cả các tập con cùa X được kỷ hiệu Vậy A G '/ ( A ') khi và chỉ khi A d X . Với mọi tập X : 0 là tập con của X và X là tập con chính nó, vl vậy 0,x . A dX (1.1) Ví dụ 1.5: X = {a ,h ,c) có .lP (X ) = [ ĩ ã, [ a] , [ b] , [ c ] , [ a, b\ , [ b, c } , [ c , a] , X] . Ví dụ trên cho thấy nếu A" có 3 phần tử thì ’f { X ) có 2^ = 8 phần từ. Ta có thề chứng minh tổng quát ràng nếu X có n phần tử thì ' f ( X ) có 2" phần tử (bài tập 1.19). 1.2.5 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 k j B. là tập gồm các phần tứ thuộc ít nhất một trong hai tập A , B . {xeA^B)<^{{xeA)w{xeB)). (1.2)