Download Tài Liệu, Giáo Trình, Bài Giảng Toán Rời Rạc Chọn Lọc

Bài giảng “Toán rời rạc 1” có cấu trúc gồm 5 chương trình bày các nội dung: Logic, tập hợp và ứng dụng; bài toán đếm; bài toán liệt kê; bài toán tối ưu; bài toán tồn tại. Cuối mỗi chương đều có các bài tập ôn tập giúp người học củng cố kiến thức. Mời các bạn cùng tham khảo.

Đang xem: Bài giảng toán rời rạc

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG ———-———- KHOA CÔNG NGHỆ THÔNG TIN 1 BÀI GIẢNG IT TOÁN RỜI RẠC 1PT Hà Nội 2013 LỜI GIỚI THIỆU Toán rời rạc là lĩnh vực nghiên cứu và xử lý các đối tượng rời rạc. Toán rời rạcdùng để đếm, quan sát, và xử lý mối quan hệ giữa các đối tượng trong các tập hợp khácnhau. Bản chất tính toán trên máy tính là rời rạc. Chính vì vậy, toán học rời rạc được xemlà môn học kinh điển cho sinh viên các ngành Công nghệ thông tin và Điện tử Viễnthông. Tài liệu hướng dẫn môn học toán học rời rạc được xây dựng dựa trên cơ sở kinhnghiệm giảng dạy môn học và kế thừa những nội dung từ giáo trình “Toán học rời rạcứng dụng trong tin học” của Kenneth Rossen. Tài liệu được trình bày thành hai phần: Lýthuyết tổ hợp (Toán rời rạc 1) và Lý thuyết đồ thị (Toán rời rạc 2). Phần I trình bày những kiến thức cơ bản về lý thuyết tổ hợp thông qua việc giảiquyết bốn bài toán cơ bản đó là: Bài toán đếm, Bài toán tồn tại, Bài toán liệt kê và Bàitoán tối ưu. Phần II trình bày những kiến thức cơ bản về Lý thuyết đồ thị: khái niệm, địnhnghĩa, các thuật toán trên đồ thị, đồ thị Euler, đồ thị Hamilton. Một số bài toán có ứngdụng thực tiễn quan trọng khác của lý thuyết đồ thị cũng được chú trọng giải quyết đó làBài toán tô màu đồ thị, Bài toán tìm đường đi ngắn nhất và Bài toán luồng cực đại trongmạng. IT Trong mỗi phần của tài liệu, chúng tôi cố gắng trình bày ngắn gọn trực tiếp vàobản chất của vấn đề. Các thuật toán được trình bày và cài bằng ngôn ngữ lập trình C++.Mặc dù đã rất cẩn trọng trong quá trình biên soạn, tuy nhiên tài liệu không tránh khỏinhững thiếu sót và hạn chế. Chúng tôi rất mong được sự góp ý quí báu của tất cả đọc giả PTvà các bạn đồng nghiệp. Hà nội, tháng 10 năm 2013 2 MỤC LỤCCHƯƠNG 1. LOGIC, TẬP HỢP VÀ ỨNG DỤNG…………………………………….. 5 1.1. Giới thiệu chung ……………………………………………………………………………………… 5 1.2. Những kiến thức cơ bản về Logic mệnh đề ………………………………………………….. 6 1.2.1. Định nghĩa & phép toán …………………………………………………………………….. 6 1.2.2. Sự tương đương giữa các mệnh đề ……………………………………………………….. 7 1.2.3. Dạng chuẩn tắc………………………………………………………………………………….. 9 1.3. Vị từ và lượng từ……………………………………………………………………………………. 10 1.4. Một số ứng dụng trên máy tính ………………………………………………………………… 12 1.5. Những kiến thức cơ bản về lý thuyết tập hợp ……………………………………………… 15 1.5.1. Khái niệm & định nghĩa ……………………………………………………………………. 15 1.5.2. Các phép toán trên tập hợp ………………………………………………………………… 16 1.5.3. Các hằng đẳng thức trên tập hợp ………………………………………………………… 17 1.6. Biểu diễn tập hợp trên máy tính ……………………………………………………………….. 18 IT 1.7. Những nội dung cần ghi nhớ ……………………………………………………………………. 19BÀI TẬP CHƯƠNG 1………………………………………………………………………….. 19CHƯƠNG 2. BÀI TOÁN ĐẾM……………………………………………………………… 21 2.1. Những nguyên lý đếm cơ bản…………………………………………………………………… 21 PT 2.1.1. Nguyên lý cộng ……………………………………………………………………………….. 21 2.1.2. Nguyên lý nhân ……………………………………………………………………………….. 22 2.2. Nguyên lý bù trừ ……………………………………………………………………………………. 24 2.3. Đếm các hoán vị và tổ hợp………………………………………………………………………. 27 2.3.1. Chỉnh hợp lặp………………………………………………………………………………….. 27 2.3.2. Chỉnh hợp không lặp ………………………………………………………………………… 27 2.3.3. Hoán vị ………………………………………………………………………………………….. 28 2.3.4. Tổ hợp……………………………………………………………………………………………. 28 2.3.5. Tổ hợp lặp………………………………………………………………………………………. 30 2.4. Hệ thức truy hồi …………………………………………………………………………………….. 31 2.4.1. Định nghĩa và ví dụ ………………………………………………………………………….. 31 2.4.2. Giải công thức truy hồi tuyến tính thuần nhất với hệ số hằng số ………………. 34 2.5. Qui về các bài toán đơn giản ……………………………………………………………………. 38 2.6. Phương pháp liệt kê ……………………………………………………………………………….. 40BÀI TẬP CHƯƠNG 2………………………………………………………………………….. 43CHƯƠNG 3. BÀI TOÁN LIỆT KÊ………………………………………………………… 45 3.1- Giới thiệu bài toán …………………………………………………………………………………. 45 3.2. Thuật toán và độ phức tạp tính toán ………………………………………………………….. 46 3.2.1. Ví dụ và Định nghĩa …………………………………………………………………………. 46 3 3.2.2. Phương pháp biểu diễn thuật toán: ……………………………………………………… 46 3.2.3. Độ phức tạp tính toán ……………………………………………………………………….. 48 3.2.4. Qui tắc xác định độ phức tạp thuật toán……………………………………………….. 51 3.3. Phương pháp sinh ………………………………………………………………………………….. 52 3.4. Thuật toán quay lui (Back track) ……………………………………………………………… 63 3.5. Những nội dung cần ghi nhớ ……………………………………………………………………. 69BÀI TẬP CHƯƠNG 3………………………………………………………………………….. 70CHƯƠNG 4. BÀI TOÁN TỐI ƯU …………………………………………………………. 73 4.1. Giới thiệu bài toán …………………………………………………………………………………. 73 4.2. Phương pháp duyệt toàn bộ……………………………………………………………………… 76 4.3. Thuật toán nhánh cận ……………………………………………………………………………… 79 4.4. Kỹ thuật rút gọn giải quyết bài toán người du lịch……………………………………….. 90 4.4.1.Thủ tục rút gọn…………………………………………………………………………………. 91 4.4.2.Thủ tục chọn cạnh phân nhánh (r,c)……………………………………………………… 94 4.4.3.Thuật toán nhánh cận giải bài toán người du lịch……………………………………. 99 4.5. Những điểm cần ghi nhớ ……………………………………………………………………….. 100 ITBÀI TẬP CHƯƠNG 4………………………………………………………………………… 100CHƯƠNG 5. BÀI TOÁN TỒN TẠI ……………………………………………………… 103 4.1. Giới thiệu bài toán ……………………………………………………………………………….. 103 5.2. Phương pháp phản chứng………………………………………………………………………. 106 PT 5.3 Nguyên lý Dirichlet……………………………………………………………………………….. 107 5.4. Những nội dung cần ghi nhớ ………………………………………………………………….. 108BÀI TẬP…………………………………………………………………………………………… 109 4 CHƯƠNG 1. LOGIC, TẬP HỢP VÀ ỨNG DỤNG Nội dung chính của chương này đề cập đến những kiến thức cơ bản về logic mệnh đề,lý thuyết tập hợp và ứng dụng. Nội dung chính của chương bao gồm:  Logic mệnh đề và ứng dụng.  Logic vị từ và ứng dụng.  Lý thuyết tập hợp và ứng dụng.  Một số ứng dụng của logic và tập hợp trong tin học.  Bài tập chương 1. Bạn đọc có thể tìm thấy những kiến thức sâu hơn và chi tiết hơn trong các tài liệu <1>và <2> của tài liệu tham khảo.1.1. Giới thiệu chung IT Tổ hợp là một lĩnh vực quan trọng của toán học rời rạc đề cập tới nhiều vấn đềkhác nhau của toán học. Lý thuyết Tổ hợp nghiên cứu việc phân bố các phần tử vào cáctập hợp. Thông thường các phần tử của tập hợp là hữu hạn và việc phân bố chúng phải PTthoả mãn những điều kiện nhất định nào đó tuỳ theo yêu cầu của bài toán. Mỗi cách phânbố được coi là một “cấu hình của tổ hợp”. Các cấu hình tổ hợp được xem xét như một lờigiải của bài toán đếm, bài toán liệt kê, bài toán tồn tại hay bài toán tối ưu. Bài toán đếm: đây là dạng bài toán nhằm trả lời câu hỏi “có bao nhiêu cấu hìnhthoả mãn điều kiện đã nêu?”. Bài toán đếm được áp dụng có hiệu quả vào những côngviệc mang tính chất đánh giá như xác suất xảy ra của một sự kiện, thời gian tính toán hayđộ phức tạp của một chương trình máy tính. Bài toán liệt kê: bài toán liệt kê quan tâm đến tất cả các cấu hình có thể có được,vì vậy lời giải của nó được biểu diễn dưới dạng thuật toán “vét cạn” tất cả các cấu hình.Bài toán liệt kê thường được làm nền cho nhiều bài toán khác. Hiện nay, một số bài toántồn tại, bài toán tối ưu, bài toán đếm vẫn chưa có cách nào giải quyết ngoài phương phápliệt kê. Phương pháp liệt kê càng trở nên quan trọng hơn khi nó được hỗ trợ bởi các hệthống máy tính. Bài toán tối ưu: khác với bài toán liệt kê, bài toán tối ưu chỉ quan tâm tới cấuhình “tốt nhất” theo một nghĩa nào đó. Đây là một bài toán có nhiều ứng dụng thực tiễnđược giải quyết bằng lý thuyết tổ hợp. Bài toán tồn tại: nếu như bài toán đếm thực hiện đếm bao nhiêu cấu hình có thểcó, bài toán liệt kê xem xét tất cả các cấu hình có thể có, bài toán tối ưu chỉ ra một cấuhình tốt nhất. Bài toán tồn tại hướng đến giải quyết những vấn đề còn nghi vấn. Điều này 5có nghĩa là ngay kể cả vấn đề có hay không một cấu hình cũng chưa biết. Những bài toánnày thường là những bài toán khó. Do vậy máy tính được xem là công cụ hữu hiệu nhấtgiải quyết bài toán tồn tại.1.2. Những kiến thức cơ bản về Logic mệnh đề Các qui tắc cơ bản của Logic cho ta ý nghĩa chính xác của các mệnh đề. Nhữngqui tắc của logic chính là công cụ cơ sở để chúng ta có thể xây dựng nên các ngôn ngữlập trình, các bảng mạch máy tính, kiểm chứng tính đúng đắn của chương trình và nhiềuứng dụng quan trọng khác.1.2.1. Định nghĩa & phép toán Đối tượng nghiên cứu của logic là các mệnh đề. Một mệnh đề được hiểu là mộtcâu khẳng định hoặc đúng hoặc sai chứ không thể vừa đúng vừa sai.Ví dụ: Những câu khẳng định sau đây là một mệnh đề: “Hà nội là thủ đô của Việt nam.” 1+1 =2 2+2=3 IT Các mệnh đề “ Hà nội là thủ đô của việt nam”, “ 1 +1 =2 “ là những mệnh đềđúng, mệnh đề “2 +2 =3” là sai. Nhưng những câu trong ví dụ sau sẽ không phải là một PTmệnh đề vì nó những câu đó không cho ta khẳng định đúng cũng chẳng cho ta khẳng địnhsai. “Bây giờ là mấy giờ ?” “Hãy suy nghĩ điều này cho kỹ lưỡng” x +1 =2 x+y=z Ta ký hiệu những chữ cái A, B, C, D, p, q, r, s . . . là những mệnh đề. Giá trị củamột mệnh đề đúng được ký hiệu là T, giá trị mệnh đề sai được ký hiệu là F. Tập giá trị T,F còn được gọi là giá trị chân lý của một mệnh đề.Định nghĩa 1. Cho p là một mệnh đề. Phép phủ định mệnh đề p cũng là một mệnh đề(ký hiệu là p hoặc p). Mệnh đề p có giá trị F khi và chỉ khi mệnh đề p nhận giá trị T,nhận giá trị F khi và chỉ khi p nhận giá trị T.Định nghĩa 2. Cho p và q là hai mệnh đề. Phép hội giữa mệnh đề p với mệnh đề q là mộtmệnh đề (ký hiệu p  q ). Mệnh đề p  q có giá trị T khi và chỉ khi p, q nhận giá trị T, cógiá trị F khi và chỉ khi hoặc p, q, hoặc cả hai nhận giá trị F. 6Định nghĩa 3. Cho p và q là hai mệnh đề. Phép tuyển giữa mệnh đề p với mệnh đề q làmột mệnh đề (ký hiệu p p). Mệnh đề p p có giá trị T khi và chỉ khi ít nhất một tronghai mệnh đề p, q nhận giá trị T, có giá trị F khi và chỉ khi cả p, q đều nhận giá trị F.Định nghĩa 4. Cho p và q là hai mệnh đề. Phép tuyển loại giữa mệnh p với mệnh đề q(được ký hiệu là pq) là một mệnh đề. Mệnh đề pq chỉ đúng khi một trong p hoặc qđúng và sai trong các trường hợp khác còn lại.Định nghĩa 5. Cho p và q là hai mệnh đề. Phép kéo theo giữa mệnh đề p với mệnh đề q(ký hiệu p  q) là một mệnh đề. Mệnh đề p  q nhận giá T khi và chỉ khi p và q nhậngiá trị F hoặc p và q cùng nhận giá trị T. Mệnh đề pq nhận giá trị F khi và chỉ khi pnhận giá trị T và q nhận giá trị F.Định nghĩa 6. Cho p và q là hai mệnh đề. Phép tương đương giữa mệnh đề p với mệnhđề q là một mệnh đề (ký hiệu p  q). Mệnh đề p  q có giá trị đúng khi p và q có cùnggiá trị chân lý và sai trong các trường hợp khác còn lại. Các phép toán : , , , , ,  có thể được định nghĩa thông qua bảng giá trịchân lý sau: p p pq IT Bảng 1.1: Bảng giá trị chân lý của các phép toán , , , , ,  q pq pq pq p q PT T T F T T F T T T F F F T T F F F T T F T T T F F F T F F F T T1.2.2. Sự tương đương giữa các mệnh đề Một vấn đề hết sức quan trọng trong lập luận toán học là việc thay thế một mệnhđề bằng một mệnh đề khác có cùng giá trị chân lý. Hai mệnh đề có cùng một giá trị chânlý chúng ta có thể hiểu theo cách thông thường là chúng tương đương nhau về ngữ nghĩa.Do vậy, ta sẽ tiếp cận và phân loại các mệnh đề phức hợp thông qua các giá trị chân lýcủa chúng.Định nghĩa 7. Một mệnh đề phức hợp luôn luôn đúng với bất kể các giá trị chân lý củacác mệnh đề thành phần được gọi là hằng đúng (tautology). Một mệnh đề luôn luôn saivới mọi giá trị chân lý của các mệnh đề thành phần được gọi là mâu thuẫn.Ví dụ: mệnh đề phức hợp p  p là hằng đúng, p  p là mâu thuẫn vì giá trị chân lý củacác mệnh đề trên luôn luôn đúng, hoặc luôn luôn sai như được chỉ ra trong bảng 1.2. 7 Bảng 1.2. Ví dụ về mệnh đề hằng đúng & mệnh đề mâu thuẫn p p pp p p T F T F F T T FĐịnh nghĩa 8. Hai mệnh đề p, q được gọi là tương đương logic với nhau (ký hiệu : pq,hoặc p  q , hoặc p=q) khi và chỉ khi các cột cho giá trị chân lý của chúng giống nhau.Hay mệnh đề pq là hằng đúng.Ví dụ 1. Hai mệnh đề  p  q  và p  q là tương đương logic vì các cột giá trị chân lýcủa chúng được thể hiện qua bảng sau: Bảng 1.3. Bảng giá trị chân lý đối với  p  q  và p  q p q pq  p  q p q pq T T F F T F T F T T T F IT T F F F F F T T F T F T T F F F PT Dùng bảng giá trị chân lý để chứng minh tính tương đương logic giữa hai mệnh đềphức hợp cho ta một phương pháp trực quan dễ hiểu. Tuy nhiên, với những mệnh đềlogic phức hợp có k mệnh đề thành phần thì cần tới 2k tổ hợp các bộ giá trị chân lý khácnhau. Do đó, dùng bảng chân lý để chứng minh tính tương đương logic giữa hai mệnh đềphức hợp gặp nhiều khó khăn. Trong trường hợp này ta có thể chứng minh tính tươnglogic bằng việc thay thế một mệnh đề phức hợp bằng những tương đương logic có trước. Bằng phương pháp bảng chân lý, dễ dàng chứng minh được sự tương đương củacác công thức dưới đây: p q  p  q pq  (pq)(qp) p  p Bảng 1.4. Bảng các tương đương logic TƯƠNG ĐƯƠNG TÊN GỌIpTp Luật đồng nhất 8pFppTT Luật nuốtpFFppp Luật luỹ đẳngpppp p Luật phủ định képpqqp Luật giao hoánpqqp(p  q)  r  p  ( q  r) Luật kết hợp(p  q)  r  p ( q  r)p  ( q  r)  (p  q )  (p  r) Luật phân phốip  ( q  r)  (p  q)  (p  r) p  q p  q  pq pq   IT Luật De Morgan PTVí dụ: Chứng minh p  p  q  p  q ?Chứng minh:   p pq  p pq    p p q   theo luật De Morgan thứ 2  p pq   theo luật De Morgan thứ 2  p  p   p  q  theo luật phủ định kép  F  p  q theo luật phân phối   p  q  F tương đương tiện ích  p  q  Điều cần chứng minh.1.2.3. Dạng chuẩn tắc Các công thức (mệnh đề) tương đương được xem như các biểu diễn khác nhau củacùng một mệnh đề. Để dễ dàng viết các chương trình máy tính thao tác trên các côngthức, chúng ta cần chuẩn hóa các công thức, đưa chúng về dạng biểu diễn chuẩn đượcgọi là dạng chuẩn hội. Một công thức được gọi là ở dạng chuẩn hội nếu nó là hội của các 9mệnh đề tuyển. Phương pháp để biến đổi một công thức bất kỳ về dạng chuẩn hội bằngcách áp dụng các thủ tục sau:  Bỏ các phép kéo theo () bằng cách thay (pq) bởi p  q .  Chuyển các phép phủ định ( ) vào sát các ký hiệu mệnh đề bằng cách áp dụng luật De Morgan và thay p bởi p.  Áp dụng luật phân phối thay các công thức có dạng (p(qr)) bởi (pq)(pr).Ví dụ. Ta chuẩn hóa công thức  p  q   r  s .Lời giải.  p  q   r  s    p  q  r  s       pq  r s   p  q   r  s  Như vậy công thức p  q  r  p  q  s  . IT  p  q  r  p  q  s  p  q   r  s  được đưa về dạng chuẩn hội là PT1.3. Vị từ và lượng từ Trong toán học hay trong các chương trình máy tính chúng ta rất hay gặp nhữngkhẳng định chưa phải là một mệnh đề. Những khẳng định đó đều có liên quan đến cácbiến. Chẳng hạn khẳng đinh: P(x) = “x > 3” không phải là một mệnh đề nhưng tại những giá trị cụ thể của x=x0nào đó thì P(x0) lại là một mệnh đề. Hoặc trong những đoạn chương trình gặp câu lệnh: if ( x > 3 ) then x:= x +1; thì chương trình sẽ đặt giá trị cụ thể của biến x vào P(x), nếu mệnh đề P(x) cho giátrị đúng x sẽ được tăng lên 1 bởi câu lệnh x:=x+1, P(x) có giá trị sai giá trị của x đượcgiữ nguyên sau khi thực hiện câu lệnh if. Chúng ta có thể phân tích mỗi khẳng định thành hai phần chủ ngữ và vị ngữ (hayvị từ), trong câu “ x lớn hơn 3” thì x là chủ ngữ, “ lớn hơn 3” là vị ngữ. Hàm P(x) đượcgọi là hàm mệnh đề. Một hàm mệnh đề có thể có một hoặc nhiều biến. Giá trị chân lýcủa hàm mệnh đề tại những giá trị cụ thể của biến được xác định như những mệnh đềthông thường.

Xem Thêm : Tải Đồ Án Kiến Trúc Thư Viện Ý Tưởng, Đồ Án Kiến Trúc K7

Xem thêm: Điểm Chuẩn Đại Học Kinh Tế Luật Tp Hcm 2016 : Trường Đh Kinh Tế

Xem thêm: Tạp Chí Khoa Học – Trường Đại Học Sư Phạm Hà Nội 2

Ví dụ. Cho Q(x, y, z) là hàm mệnh đề xác định câu x2 = y2 +z2 hãy xác định giá trịchân lý của các mệnh đề Q (3, 2, 1), Q ( 5, 4, 3)? 10Lời giải. Đặt giá trị cụ thể của x , y , z vào Q(x,y,z) ta có : Q(3,2,1) là mệnh đề “32 = 22 + 12” là sai do đó Q(3,2,1) là mệnh đề sai. Trong đó,Q (5, 4, 3) là mệnh đề “ 52 = 42 + 32” là mệnh đề đúng. Tổng quát, giả sử M là một tập hợp các phần tử nào đó. M thường được gọi làtrường hay miền xác định của các phẩn tử thuộc M. Khi đó, biểu thức P(x) gọi là vị từxác định trên trường M nếu khi thay x bởi một phần tử bất kỳ của trường M thì P(x) sẽ trởthành một mệnh đề trên trường M. Khi tất cả các biến của hàm mệnh đề đều được gán những giá trị cụ thể, thì mệnhđề tạo ra sẽ xác định giá trị chân lý. Tuy nhiên, có một phương pháp quan trọng khác đểbiến một hàm mệnh đề thành một mệnh đề mà không cần phải kiểm chứng mọi giá trịchân lý của hàm mệnh đề tương ứng với các giá trị của biến thuộc trường đang xét.Phương pháp đó gọi là sự lượng hoá hay lượng từ. Chúng ta xét hai lượng từ quan trọnglà lượng từ với mọi (ký hiệu :), lượng từ tồn tại (ký hiệu : ).Định nghĩa 1. Lượng từ với mọi của P(x) ký hiệu là x P(x) là một mệnh đề “ P(x) đúng ITvới mọi phần tử x thuộc trường đang xét”. Ví dụ. Cho hàm mệnh đề P(x) = x2 + x + 41 là nguyên tố. Xác định giá trị chânlý của mệnh đề  P(x) với x thuộc không gian bao gồm các số tự nhiên <0..39>. Lời giải. Vì P(x) đúng với mọi giá trị của x  <0..39>   P(x) là đúng. PT Ví dụ : Cho P(x) là hàm mệnh đề “ x + 1 > x”. Xác định giá trị chân lý của mệnhđề  x P(x), trong không gian các số thực. Lời giải : Vì P(x) đúng với mọi số thực x nên x P(x) là đúng. Định nghĩa 2. Lượng từ tồn tại của hàm mệnh đề P(x) (được ký hiệu là: x P(x) )là một mệnh đề “ Tồn tại một phần tử x trong không gian sao cho P(x) là đúng “. Ví dụ: Cho P(x) là hàm mệnh đề “x > 3”. Hãy tìm giá trị chân lý của mệnh đề  xP(x) trong không gian các số thực. Lời giải: Vì P(4) là “ 4 > 3” đúng nên  x P(x) là đúng. Ví dụ: Cho Q(x) là “ x + 1 > x”. Hãy tìm giá trị chân lý của mệnh đề  x Q(x)trong không gian các số thực. Lời giải: vì Q(x) sai với mọi x  R nên mệnh đề  x Q(x) là sai. Bảng 1.5: Giá trị chân lý của lượng từ , x P(x) P(x) đúng với mọi x Có một giá trị của x để P(x) saix P(x) Có một giá trị của x để P(x) đúng P(x) sai với mọi x 11Dịch những câu thông thường thành biểu thức logic: Dịch một câu được phát biểubằng ngôn ngữ tự nhiên (câu hỏi thông thường) thành một biểu thức logic có vai trò hếtsức quan trọng trong xây dựng các ngôn ngữ lập trình, chương trình dịch và xử lý ngônngữ tự nhiên. Quá trình dịch một câu từ ngôn ngữ tự nhiên thành một biểu thức sẽ làmmất đi tính tự nhiên của ngôn ngữ vì đa số các ngôn ngữ đều không rõ ràng, nhưng mộtbiểu thức logic lại rất rõ ràng chặt chẽ từ cú pháp thể hiện đến ngữ nghĩa của câu. Điềunày dẫn đến phải có một tập hợp các giả thiết hợp lý dựa trên một hàm xác định ngữnghĩa cuả câu đó. Một khi câu đã được chuyển dịch thành biểu thức logic, chúng ta cóthể xác định được giá trị chân lý của biểu thức logic, thao tác trên biểu thức logic, biếnđổi tương đương trên biểu thức logic. Chúng ta sẽ minh hoạ việc dịch một câu thôngthường thành biểu thức logic thông qua những sau. Ví dụ dịch câu “Bạn không được lái xe máy nếu bạn cao dưới 1.5 mét trừ phi bạntrên 18 tuổi” thành biểu thức logic.Lời giải. Ta gọi p là câu : Bạn được lái xe máy. q là câu : Bạn cao dưới 1.5m. r là câu IT : Bạn trên 18 tuổi. Khi đó: Câu hỏi trên được dịch là: (q  r )  p Ví dụ: Dịch câu “ Tất cả các sinh viên học tin học đều học môn toán học rời rạc” PT Lời giải: Gọi P(x) là câu “x cần học môn toán học rời rạc” và x được xác địnhtrong không gian của các sinh viên học tin học. Khi đó chúng ta có thể phát biểu:x P(x). Ví dụ: Dịch câu “Có một sinh viên ở lớp này ít nhất đã ở tất cả các phòng của ítnhất một nhà trong ký túc xá”. Lời giải : Gọi tập sinh viên trong lớp là không gian xác định sinh viên x, tập cácnhà trong ký túc xá là không gian xác định căn nhà y, tập các phòng là không gian xácđịnh phòng z. Ta gọi P(z,y) là “ z thuộc y”, Q(x,z) là “ x đã ở z”. Khi đó ta có thể phátbiểu :  x  y  z (P(z,y)  Q(x,z));1.4. Một số ứng dụng trên máy tính Các phép toán bít: Các hệ thống máy tính thường dùng các bit (binary digit) đểbiểu diễn thông tin. Một bít có hai giá trị chân lý hoặc 0 hoặc 1. Vì giá trị chân lý của mộtbiểu thức logic cũng có hai giá trị hoặc đúng (T) hoặc sai (F). Nếu ta coi giá trị đúng cógiá trị 1 và giá trị sai là 0 thì các phép toán với các bít trong máy tính được tương ứng vớicác liên từ logic. 12 Một xâu bít (hoặc xâu nhị phân) là dãy không hoặc nhiều bít. Chiều dài của xâu làsố các bít trong xâu đó. Ví dụ xâu nhị 101010011 có độ dài là 9. Một số nguyên đuợcbiểu diễn như một xâu nhị phân có độ dài 16 bít. Các phép toán với bít được xây dựng trên các xâu bít có cùng độ dài, bao gồm :AND bít (phép và cấp bít), OR (phép hoặc cấp bít), XOR (phép tuyển loại trừ cấp bít). Vídụ: cho hai xâu bít 01101 10110 và 11000 11101 hãy tìm xâu AND bít, OR bít, XOR bít. Bảng 1.5. Các phép toán cấp bít ứng dụng trong ngôn ngữ LT Giá trị của A Giá trị của B A and B A or B A xor B A = 13 =1100 B = 8=1000 1000 1101 0101Thuật toán các phép tính số nguyên: Các thuật toán thực hiện các phép tính với các sốnguyên khi dùng khai triển nhị phân là hết sức quan trọng trong bộ xử lý số học của máytính. Như chúng ta đã biết, thực chất các số nguyên được biểu diễn trong máy tính là cácxâu bít nhị phân, do vậy chúng ta có thể sử dụng biểu diễn nhị phân của các số để thựchiện các phép tính. Giả sử khai triển nhị phân của các số nguyên a và b tương ứng là: IT a = (an-1an-2 . . .a1a0)2 , b = (bn-1bn-2 . . .b1b0)2 . Khai triển của a và b có đúng n bít (chấp nhận những bít 0 ở đầu để làm đặc n bít).Xét bài toán cộng hai số nguyên viết ở dạng nhị phân. Thủ tục thực hiện việc cộng cũnggiống như làm trên giấy thông thường. Phương pháp này tiến hành bằng cách cộng các PTbít nhị phân tương ứng có nhớ để tính tổng hai số nguyên. Sau đây là mô tả chi tiết choquá trình cộng hai xâu bít nhị phân. Để cộng a với b, trước hết ta cộng hai bít phải nhất, nghĩa là: a0 + b0 = c0*2 + s0; trong đó s0 là bít phải nhất của số nguyên tổng a + b, c0 là sốcần để nhớ nó có thể bằng 0 hoặc 1. Sau đó ta cộng hai bít tiếp theo và số nhớ: a1 + b1 + c0 = c1*2 + s1; s1 là bít tiếp theo của số a + b, c1 là số nhớ. Tiếp tục quátrình này bằng cách cộng các bít tương ứng trong khai triển nhị phân và số nhớ, ở giaiđoạn cuối cùng : an-1 + bn-1 + cn-2 = cn-1 * 2 + sn-1. Bít cuối cùng của tổng là cn-1. Khi đókhai triển nhị phân của tổng a + b là (snan-1 . . .s1s0)2.Ví dụ: cộng a =(1110)2, b = (1011)2Lời giải: Trước hết lấy: a0 + b0 = 0 + 1 = 0 * 2 + 1  c0=0, s0 = 1 Tiếp tục: a1 + b1 + c0 = 1 + 1 + 0 = 1 * 2 + 0  c1=1, s1 = 0 a2 + b2 + c1 = 1 + 0 + 1 = 1 * 2 + 0  c2=1, s2 = 0 13 a3 + b3 + c2 = 1 + 1 + 1 = 1 * 2 + 1  c3=1, s3 = 1 Cuối cùng: s4 = c3 = 1  a + b = (11001)2Thuật toán cộng: void Cong(a , b: positive integer) { /*a = (an-1an-2 . . .a1a0)2 , b = (bn-1bn-2 . . .b1b0)2 */ c=0; for (j=0 ; j n-1; j++) { d= <( aj + bj + c)/ 2>; sj = aj + bj + c – 2d; c = d; } sn = c; khai triển nhị phân của tổng là (snan-1 . . .s1s0)2; } ITThuật toán nhân: Để nhân hai số nguyên n bít a, b ta bắt đầu từ việc phân tích: a = (an-1an-2. . .a1a0), b = (bn-1bn-2. . .b1b0) Ta có thể tính a.b từ phương trình trên. Trước hết, ta nhận thấy abj = a nếu bj=1,abj=0 nếu bj=0. Mỗi lần tính ta nhân với 2 j hay dịch chuyển sang trái j bít 0 bằng cáchthêm j bít 0 vào bên trái kết quả nhận được. Cuối cùng, cộng n số nguyên abj 2j (j=0..n-1) PTta nhận được a.b. Ví dụ sau đây sẽ minh hoạ cho thuật toán nhân: Ví dụ: Tìm tích của a = (110)2, b= (101)2 Giải: Ta nhận thấy ab020 = (110)2*1*20 = (110)2 ab121 = (110)2*0*21 = (0000)2 ab222 = (110)2*1*22 = (11000)2Sử dụng thuật toán tính tổng hai số nguyên a, b có biểu diễn n bít ta nhận được(ta có thểthêm số 0 vào đầu mỗi toán hạng): (0 110)2 + (0000)2 = (0110)2 ; (0 0110)2 + (11000)2 = (11110)2 = ab. Thuật toán nhân hai số nguyên n bít có thể được mô phỏng như sau:void Nhan( a, b : Positive integer){ /* khai triển nhị phân tương ứng của a = (an-1an-2. . .a1a0), b = (bn-1bn-2. . .b1b0) */ for (j=0; j n-1; j++) { if ( ( bj==1) 14 cj = a * 2j; /* a được dịch trái j bít 0 */ else cj =0; } /*c0, c1.., cn-1 là những tích riêng của abj 2j(j=0..n-1 */ p=0; for ( j=0 ; j n-1; j++) p= p + cj; /* p là giá trị của tích ab */}1.5. Những kiến thức cơ bản về lý thuyết tập hợp1.5.1. Khái niệm & định nghĩa Các tập hợp dùng để nhóm các đối tượng lại với nhau. Thông thường, các đốitượng trong tập hợp có các tính chất tương tự nhau. Ví dụ, tất cả sinh viên mới nhập ITtrường tạo nên một tập hợp, tất cả sinh viên thuộc khoa Công nghệ thông tin là một tậphợp, các số tự nhiên, các số thực cũng tạo nên các tập hợp. Chú ý rằng, thuật ngữ đốitượng được dùng ở đây không chỉ rõ cụ thể một đối tượng nào, sự mô tả một tập hợp nàođó hoàn toàn mang tính trực giác về các đối tượng.Định nghĩa 1. Tập các đối tượng trong một tập hợp được gọi là các phần tử của tập hợp. PTCác tập hợp thường được ký hiệu bởi những chữ cái in hoa đậm như A, B, X, Y . . ., cácphần tử thuộc tập hợp hay được ký hiệu bởi các chữ cái in thường như a, b, c, u, v . . . Đểchỉ a là phần tử của tập hợp A ta viết a A, trái lại nếu a không thuộc A ta viết a A. Tập hợp không chứa bất kỳ một phần tử nào được gọi là tập rỗng (ký hiệu là hoặc { }). Tập hợp A được gọi là bằng tập hợp B khi và chỉ khi chúng có cùng chung cácphần tử và được ký hiệu là A=B. Ví dụ tập A={ 1, 3, 5 } sẽ bằng tập B = { 3, 5, 1 }.Định nghĩa 2. Tập A được gọi là một tập con của tập hợp B và ký hiệu là AB khi vàchỉ khi mỗi phần tử của A là một phần tử của B. Hay A  B khi và chỉ khi lượng từ  x (x A  x  B) cho ta giá trị đúng. Từ định nghĩa trên chúng ta rút ra một số hệ quả sau: Tập rỗng  là tập con của mọi tập hợp. Mọi tập hợp là tập con của chính nó. Nếu A B và B  A thì A=B hay mệnh đề : x (x A  xB )   x (xB  x  A) cho ta giá trị đúng. Nếu A B và AB thì ta nói A là tập con thực sự của B và ký hiệu là AB. 15Định nghĩa 3. Cho S là một tập hợp. Nếu S có chính xác n phần tử phân biệt trong S, vớin là số nguyên không âm thì ta nói S là một tập hữu hạn và n được gọi là bản số của S.Bản số của S được ký hiệu là |S | hay N(S).Định nghĩa 4. Cho tập hợp S. Tập luỹ thừa của S ký hiệu là P(S) là tập tất cả các tập concủa S. Ví dụ S = { 0, 1, 2 }  P(S) ={ , {0}, {1}, {2}, {0,1}, {0, 2}, {1, 2} {0, 1, 2}}.Định nghĩa 5. Dãy sắp thứ tự (a1, a2,.., an) là một tập hợp sắp thứ tự có a1 là phần tử thứnhất, a2 là phần tử thứ 2, .., an là phần tử thứ n. Chúng ta nói hai dãy sắp thứ tự là bằngnhau khi và chỉ khi các phần tử tương ứng của chúng là bằng nhau. Nói cách khác (a1,a2,.., an) bằng (b1, b2,.., bn) khi và chỉ khi ai = bi với mọi i =1, 2, ..n.Định nghĩa 6. Cho A và B là hai tập hợp. Tích đề các của A và B được ký hiệu là AB,là tập hợp của tất cả các cặp (a,b) với aA, b B. Hay có thể biểu diễn bằng biểu thức: A  B = { (a, b) | a A, b B }Định nghĩa 7. Tích đề các của các tập A1, A2, . ., An được ký hiệu là A1A2..An là tậphợp của dãy sắp thứ tự (a1, a2,.., an) trong đó aiAi với i = 1, 2,..n. Nói cách khác:1.5.2. Các phép toán trên tập hợp IT A1A2..An = { (a1, a2,.., an) | aiAi với i = 1, 2,..n } Các tập hợp có thể được tổ hợp với nhau theo nhiều cách khác nhau thông qua các PTphép toán trên tập hợp. Các phép toán trên tập hợp bao gồm: Phép hợp (Union), phépgiao (Intersection), phép trừ (Minus).Định nghĩa 1. Cho A và B là hai tập hợp. Hợp của A và B được ký hiệu là AB, là tậpchứa tất cả các phần tử hoặc thuộc tập hợp A hoặc thuộc tập hợp B. Nói cách khác: AB = { x | x  A  x B }Định nghĩa 2. Cho A và B là hai tập hợp. Giao của A và B được ký hiệu là AB, là tậpchứa tất cả các phần tử thuộc A và thuộc B. Nói cách khác: AB = { x | x  A  x B }Định nghĩa 3. Hai tập hợp A và B được gọi là rời nhau nếu giao của chúng là tập rỗng(AB =  ).Định nghĩa 4. Cho A và B là hai tập hợp. Hiệu của A và B là tập hợp đuợc ký hiệu là A-B, có các phần tử thuộc tập hợp A nhưng không thuộc tập hợp B. Hiệu của A và B cònđược gọi là phần bù của B đối với A. Nói cách khác: A – B = { x | x A  x B }Định nghĩa 5. Cho tập hợp A. Ta gọi A là phần bù của A là một tập hợp bao gồm nhữngphần tử không thuộc A. 16 A  x | x  AĐịnh nghĩa 6. Cho các tập hợp A1, A2, . ., An. Hợp của các tập hợp là tập hợp chứa tất cảcác phần tử thuộc ít nhất một trong số các tập hợp Ai ( i=1, 2, . ., n). Ký hiệu: n  Αι  Α  Α    Α n 1 2 i 1Định nghĩa 7: Cho các tập hợp A1, A2, . ., An. Giao của các tập hợp là tập hợp chứa cácphần tử thuộc tất cả n tập hợp Ai ( i=1, 2, . ., n). n  Ai  A1 A 2 .. A n i 11.5.3. Các hằng đẳng thức trên tập hợpMỗi tập con của tập hợp tương ứng với một tính chất xác định trên tập hợp đã cho đượcgọi là mệnh đề. Với tương ứng này, các phép toán trên tập hợp được chuyển sang cácphép toán của logic mệnh đề: IT Phủ định của A, ký hiệu A (hay NOT A) tương ứng với phần bù A . Tuyển của A và B, ký hiệu A  B (hay A or B) tương ứng với A  B. Hội của A và B, ký hiệu A  B (hay A and B) tương ứng với A  B. PT Các mệnh đề cùng với các phép toán trên nó lập thành một đại số mệnh đề (hay đại sốlogic). Như thế, đại số tập hợp và đại số logic là hai đại số đẳng cấu với nhau (nhữngmệnh đề phát biểu trên đại số logic tương đương với mệnh đề phát biểu trên đại số tậphợp). Với những trường hợp cụ thể, tuỳ theo tình huống, một bài toán có thể được phátbiểu bằng ngôn ngữ của đại số logic hay ngôn ngữ của đại số tập hợp. Bảng 1.6 thể hiệnmột số hằng đẳng thức của đại số tập hợp. Bảng 1.6. Một số hằng đẳng thức trên tập hợp HẰNG ĐẲNG THỨC TÊN GỌIA=A Luật đồng nhấtA  U = A (U là tập vũ trụ)AU=U Luật nuốtA=AAA = A Luật luỹ đẳngAA=A 17A =A Luật bùAB=BA Luật giao hoánAB=BAA  (B  C) = (A B)C Luật kết hợpA (B  C) = (AB)  CA  (B  C) = (A  B)  (A  C ) Luật phân phốiA  (B  C) = (A  B)  (A  C)AB  A B Luật De MorganAB  A B1.6. Biểu diễn tập hợp trên máy tính Có nhiều cách khác nhau để biểu diễn tập hợp trên máy tính, phương pháp phổ ITbiến là lưu trữ các phần tử của tập hợp không sắp thứ tự. Với việc lưu trữ bằng phươngpháp này, ngoài những lãng phí bộ nhớ không cần thiết, thì quá trình tính hợp, giao, hiệucác tập hợp gặp nhiều khó khăn và mất nhiều thời gian vì mỗi phép tính đòi hỏi nhiềuthao tác tìm kiếm trên các phần tử. Một phương pháp lưu trữ các phần tử bằng cáchbiểu diễn có thứ tự của các phần tử của một tập vũ trụ tỏ ra hiệu quả hơn rất nhiều trong PTquá trình tính toán. Giả sử tập vũ trụ U là hữu hạn gồm n phần tử(hữu hạn được hiểu theo nghĩa cácphần tử của U lưu trữ được trong bộ nhớ máy tính). Giả sử ta muốn biểu diễn tập hợpA U. Trước hết ta chọn một thứ tự tuỳ ý nào đó đối với các phần tử của tập vũ trụ U,giả sử ta được bộ có thứ tự a1,a2, . ., an. Sau đó xây dựng một xâu bít nhị phân có độ dài n,sao cho nếu bít thứ i có giá trị 1 thì phần tử aiA, nếu ai =0 thì aiA (i=1,2..,n). Ví dụ sausẽ minh hoạ kỹ thuật biểu diễn tập hợp bằng xâu bít nhị phân. Ví dụ. Giả sử U = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }. Hãy biểu diễn tập hợp A  U là 1- Tập các số nguyên lẻ A U. 2- Tập các số nguyên chẵn BU. 3- Tập các số nguyên nhỏ hơn 5 C U. 4- Tìm A  B 5- Tìm AC . . . Lời giải. Trước hết ta coi thứ tự các phần tử được sắp xếp theo thứ tự tăng dần tức ai=i (i=1,2,..,10). Khi đó : 18 1. Xâu bít biểu diễn các số lẻ trong U ( {1, 3, 5, 7, 9 } ) là xâu có độ dài n = 10 trong đó các bít ở vị trí thứ 1, 3, 5, 7, 9 có giá trị là 1, các bít còn lại có giá trị là 0. Từ đó ta có xâu bít biểu diễn tập hợp A là: 1 0 1 0 1 0 1 0 1 0. 2. Xâu bít biểu diễn các số chẵn trong U ( {2, 4, 6, 8, 10 } ) là xâu có độ dài n = 10 trong đó các bít ở vị trí thứ 2, 4, 6, 8, 10 có giá trị là 1, các bít còn lại có giá trị là 0. Từ đó ta có xâu bít biểu diễn tập hợp B là: 0 1 0 1 0 1 0 1 0 1. 3. Xâu bít biểu diễn các số nhỏ hơn 5 trong U ( {1, 2, 3, 4 } ) là xâu có độ dài n = 10 trong đó các bít ở vị trí thứ 1, 2, 3, 4 có giá trị là 1, các bít còn lại có giá trị là 0. Từ đó ta có xâu bít biểu diễn tập hợp C là: 1 1 1 1 0 0 0 0 0 0. 4. Xâu bít biểu diễn tập hợp A  B là : (1 0 1 0 1 0 1 0 1 0  0 1 0 1 0 1 0 1 0 1) là xâu 1 1 1 1 1 1 1 1 1 1. Như vậy, A  B = U. 5. Tương tự như vậy với A  C  (1 0 1 0 1 0 1 0 1 0  1 1 1 1 0 0 0 0 0 0) là xâu 1 0 1 0 0 0 0 0 0 0. Như vậy A  C = { 1, 3 }1.7. Những nội dung cần ghi nhớ ITCần hiểu và nắm vững được những nội dung sau:  Các phép toán hội, tuyển, tuyển loại, suy ra, kéo theo của logic mệnh đề.  Các phương pháp chứng minh định lý dùng bảng chân lý và các tương đương locgic. PT  Phương pháp biểu diễn các câu hỏi thông thường bằng logic vị từ.  Định nghĩa và các phép toán trên tập hợp.  Phương pháp biểu diễn tập hợp trên máy tính BÀI TẬP CHƯƠNG 11. Lập bảng giá trị chân lý cho các mệnh đề phức hợp sau: a) (p  q)  (qp) b) (p q) (q p) c) (p  q)  (p  q ) d) (p  q)  (p  q ) e) (p q)  (p  q ) f) ( p  q )  (pq) g) ( p  q)  r h) (p  q)  r i) (p  q)  ( q r) j) ( p  q ) (qr) 192- Dùng bảng chân lý chứng minh: a) Luật giao hoán pqqp pqqp b) Luật kết hợp (p  q)  r  p  ( q  r) ( p  q)  r  p (q  r) c) Luật phân phối p  (q  r)  (p  q)  (p  r)3- Chứng minh các công thức sau đây là đồng nhất đúng bằng cách lập bảng giá trị chân lý: a) ( X(YZ)) ((X Y)(XZ)); b) (XY)((XZ)(X(YZ))); c) (XZ) ((YZ)((XY)Z)). IT4. Chứng minh các công thức sau đây là tương đương logic a) X  (Y1  Y2  …  Yn  ( X  Y1 )  ( X  Y2 )  …  ( X  Yn ) PT b) X  (Y1  Y2  …  Yn  ( X  Y1 )  ( X  Y2 )  …  ( X  Yn ) c) ( X 1  X 2    X n  X1  X1   X n d) X1  X 2  X n  X1  X 2   X n5. Cho A, B, C là các tập hợp. Chứng minh rằng: a) A B C  A B C b) ( A  B  C )  ( A  B) c) ( A  B)  C  ( A  C ) d ) ( A  C )  (C  B )   e) ( B  A)  (C  A)  ( B  C )  A f) A B  A B g ) ( A  B)  ( A  B  A 20