Giáo Trình Toán Rời Rạc - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.pdf) (51 trang)

Trang chủ

Khoa Học Tự Nhiên

Toán học

Giáo trình toán rời rạc

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (581.2 KB, 51 trang )

GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌC Biên soạn : Gv. Phạm Phúc Thịnh 1Chương 1 : CƠ SỞ LOGIC I. Khái niệm mệnh đề và chân trị 1. Các khái niệm Mệnh đề toán học là các phát biểu để diễn đạt một ý tưởng trọn vẹn và ta có thể khẳng định một cách khách quan là nó đúng hoặc sai. Tính chất cốt yếu của một mệnh đề là nó đúng hoặc sai, và không thể vừa đúng vừa sai. Giá trị đúng hoặc sai của một mệnh đề được gọi là chân trị của mệnh đề. Về mặt ký hiệu, ta thường dùng các mẫu tự (như p, q, r, ) để ký hiệu cho các mệnh đề, và chúng cũng được dùng để ký hiệu cho các biến logic, tức là các biến lấy giá trị đúng hoặc sai. Chân trị “đúng” thường được viết là 1, và chân trị “sai” được viết là 0. 2. Mệnh đề sơ cấp – mệnh đề phức hợp Mệnh đề sơ cấp là các “nguyên tử” theo nghĩa là nó không thể được phân tích thành một hay nhiều (từ hai trở lên) mệnh đề thành phần đơn giản hơn. Mệnh đề phức hợp là mệnh đề được tạo thành từ một hay nhiều mệnh đề khác bằng cách sử dụng các liên kết logic như từ “không” dùng trong việc phủ định một mệnh đề, các từ nối: “và”, “hay”, “hoặc”, “suy ra”, v.v II. Các phép toán mệnh đề 1. Bảng chân trị Các phép toán logic được định nghĩa bằng bảng chân trị (truth table). Bảng chân trị xác định chân trị của mệnh đề phức hợp theo từng trường hợp của các chân trị của các mệnh đề sơ cấp tạo thành mệnh đề phức hợp Tác dụng của bảng chân trị • Kê ra sự liên hệ chân trị giữa mệnh đề phức hợp với chân trị của các mệnh đề sơ cấp cấu thành nó, • liệt kê sự liên hệ chân trị giữa các mệnh với các mệnh đề đơn giản hơn cấu thành chúng. 2. Phép phủ định Cho p là một mệnh đề, chúng ta dùng ký hiệu ¬¬¬¬p để chỉ mệnh đề phủ định của mệnh đề p. “Sự phủ định” được định nghĩa bởi bảng chân trị sau đây: P ¬¬¬¬p 1 0 0 1 Ký hiệu ¬ được đọc là “không” Mệnh đề phủ định ¬ p có chân trị là đúng (1) khi mệnh đề p có chân trị sai (0), ngược lại ¬ p có chân trị sai (0) khi p có chân trị đúng (1). 3. Phép hội Cho p và q là hai mệnh đề. Ta ký hiệu mệnh đề “p hay q” là p Λ q. Phép “và”, ký hiệu là Λ , được định nghĩa bởi bảng chân trị sau đây: p q p Λ q 0 0 0 0 1 0 GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌ Nhận xét: Bằng cách l• Các mệnh đề p v• Mệnh đề pΛ¬ 4. Phép tuyển Cho p và q là hai mhiệu là ∨ , được định nghĩa bNhận xét : • Cho p là một m• Người ta còn sCho p và q là hai mPhép “tuyển lođây: Chân trị của mệnh đềđề p ⊕q đúng khi trong 2 msai. 5. Phép kéo theo Phép kéo theo, ký hikiện có dạng : “nếu . . . thphát biểu “nếu p thì q”. Phép toán kéo theo đây: NG TIN HỌC Biên so1 0 0 1 1 1 ằng cách lập bảng chân trị, ta có: đề p và p Λ p luôn có cùng chân trị. Λ¬ p luôn có chân trị bằng 0 (tức là một mệnh Cho p và q là hai mệnh đề. Ta ký hiệu mệnh đề “p hay q” là pĩa bởi bảng chân trị sau đây: p q p ∨ q 0 0 0 0 1 1 1 0 1 1 1 1 ột mệnh đề,ta có mệnh đề p ∨¬ p luôn luôn đòn sử dụng phép “tuyển loại” trong việc liCho p và q là hai mệnh đề. Ta ký hiệu mệnh đề “p tuyển loại”, ký hiệu là ⊕, được định nghĩa bởp q p q 0 0 0 0 1 1 1 0 1 1 1 0 ệnh đề p ⊕q phụ thuộc vào các chân trị của 2 múng khi trong 2 mệnh đề p và q có một mệnh đề đúng, mPhép kéo theo, ký hiệu bởi → , được đưa ra để mô hình cho lou . . . thì . . .”. Cho p và q là 2 mệnh đề, ta sẽ viếì q”. Phép toán kéo theo → được định nghĩa bởp q p → q 0 0 1 0 1 1 Biên soạn : Gv. Phạm Phúc Thịnh 2ệnh đề luôn sai). à p∨q. Phép “hay”, ký p luôn luôn đúng. ệc liên kết các mệnh đề. tuyển loại q” là p⊕q. ĩa bởi bảng chân trị sau ủa 2 mệnh đề p, q : mệnh đề đúng, một mệnh đề ình cho loại phát biểu điều ẽ viết p→ q để diễn đạt ĩa bởi bảng chân trị sau GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌ Mệnh đề p → q, đưkhác sau đây: “q nếu p”; “p chp”. 6. Phép kéo theo 2 chiều Phép kéo theo 2 chihình cho loại phát biểu điều kiq là 2 mệnh đề, ta viết p ↔đương được định nghĩa bởMệnh đề p ↔q, đưdạng khác sau đây: “p khi và ch7. Ðộ ưu tiên của các toán tTương tự như đối vớtrong các biểu thức logic, ta toán tử logic:¬ (không) , ∧ ¬ ∧ , ∨ → ↔ trong đó, các toán tử liệt kIII. Dạng mệnh đề vTrong phép tính mệnh • Các mệnh đề hay các giá tr• Các biến mệnh • Các phép toán logic, và ccủa các phép toán.Giả sử E, F là 2 biểu thức logic, khi logic. Ví dụ: Biểu thức E(p,q,r) = (((p, q, r là các biến mệnh đề. 1. Bảng chân trị của một biBảng chân trị của mộtheo các trường hợp về chân trtheo các bộ giá trị của bộ biếVí dụ 1: Bảng chân trmệnh đề p,q như sau: NG TIN HỌC Biên so1 0 0 1 1 1 q, được đọc là “nếu p thì q”, còn được phát biu p”; “p chỉ nếu q”; “p là điều kiện đủ cho q”. “q l Phép kéo theo 2 chiều hay phép tương đương, ký hiệu bởi↔điều kiện hai chiều có dạng : “. . . nếu và ch↔q để diễn đạt phát biểu “p nếu và chỉ nếu q”. Phép toán tĩa bởi bảng chân trị sau đây: p q p↔q 0 0 1 0 1 0 1 0 0 1 1 1 được đọc là “p nếu và chỉ nếu q”, còn được phát bip khi và chỉ khi q”; “p la‘ điều kiện cần va‘ đủ cho q”a các toán tử logic. ối với các phép toán số học, để tránh phải dùng nhic logic, ta đưa ra một thứ tự ưu tiên trong việc tính toán. (và), ∨ (hay), → (kéo theo), ↔ ( tương đươử liệt kê trên cùng dòng có cùng độ ưu tiên. đề và các luật logic ệnh đề ta cũng có các biểu thức logic được xây dđề hay các giá trị hằng. ệnh đề. Các phép toán logic, và cả các dấu ngoặc “( )” để chỉác phép toán. ức logic, khi ấy ¬ E, E ∧ F, E → F, E ↔ F cức E(p,q,r) = (((¬ p) ∨ q)→ (r ∧ s)) là một biểu th ột biểu thức logic ủa một biểu thức logic là bảng liệt kê chân trề chân trị của tất cả các biến mệnh đề trong biộ biến mệnh đề. ng chân trị của các biểu thức logic p→ q và ¬ p Biên soạn : Gv. Phạm Phúc Thịnh 3c phát biểu dưới các dạng cho q”. “q là điều kiện cần cho ↔, được đưa ra để mô à chỉ nếu . . .”. Cho p và ỉ ếu q”. Phép toán tương ợc phát biểu dưới các đủ cho q”. ùng nhiều dấu ngoặc c tính toán. Ở trên ta có 5 ng đương) ợc xây dựng từ : để chỉ rõ thứ tự thực hiện F cũng là các biểu thức t biểu thức logic trong đó ê chân trị của biểu thức logic trong biểu thức logic hay p ∨ q theo các biến GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌC Biên soạn : Gv. Phạm Phúc Thịnh 4P q p→ → → → q ¬ p ¬ p ∨ q 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 1 0 1 2. Sự tương đương logic Hai biểu thức logic E và F theo các biến mệnh đề nào đó được gọi là tương đương logic khi E và F luôn luôn có cùng chân trị trong mọi trường hợp chân trị của bộ biến mệnh đề. Khi đó ta viết: E ⇔ Fđọc là “E tương đương với F”. Như vậy, theo định nghĩa ta có thể kiểm tra xem 2 biểu thức logic có tương đương hay không bằng cách lập bảng chân trị của các biểu thức logic. 3. Biểu thức hằng đúng, biểu thức hằng sai Biểu thức logic E được gọi là hằng đúng nếu chân trị của E luôn luôn bằng 1 (đúng) trong mọi trường hợp về chân trị của các biến mệnh đề trong biểu thức E. Nói một cách khác, E là một hằng đúng khi ta có: E ⇔1. Biểu thức logic E được gọi là hằng sai nếu chân trị của E luôn luôn bằng 0 (sai) trong mọi trường hợp về chân trị của các biến mệnh đề trong biểu thức E. Nói một cách khác, E là một hằng đúng khi ta có: E ⇔ 0. Ta có thể kiểm tra xem một biểu thức logic có phải là hằng đúng (hằng sai) hay không bằng cách lập bảng chân trị của các biểu thức logic. Lưu ý: Giả sử E và F là 2 biểu thức logic. Khi đó, E tương đương logic với F (tức là ta có E ⇔ F) khi và chỉ khi biểu thức logic E ↔ F là hằng đúng (tức là E ↔F ⇔1). Nếu E ⇔ F và F ⇔ G thì E ⇔ G. 4. Các luật logic Các luật logic là cơ sở để ta thực hiện các biến đổi trên một biểu thức logic để có được một biểu thức logic mới tương đương logic với biểu thức logic có trước. a. Các luật về phép phủ định • ¬¬ p ⇔ p (luật phủ định của phủ định) • ¬ 1 ⇔ 0 • ¬ 0 ⇔ 1 b. Luật giao hoán • p ∧ q ⇔ q ∧ p • p ∨ q ⇔ q ∨ p c. Luật kết hợp • p ∧ (q ∧ r) ⇔ (p ∧ q) ∧ r • p ∨ (q ∨ r) ⇔ (p ∨ q) ∨ r d. Luật phân bố • p ∧ (q ∨ r) ⇔ (p ∨ q) ∧ (p ∨ r) • p ∨ (q ∧ r) ⇔ (p ∧ q) ∨ (p ∧ r) e. Luật De Morgan GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌC Biên soạn : Gv. Phạm Phúc Thịnh 5• ¬ (p ∧ q) ⇔¬ p ∨¬ q • ¬ (p ∨ q) ⇔¬ p ∧¬ q f. Luật về phần tử bù • p ∨¬ p ⇔ 1 • p ∧¬ p ⇔ 0 g. Luật kéo theo • p → q ⇔¬ p ∨ q h. Luật tương đương • p ↔ q ⇔ (p → q) ∧ (q → p) i. Các luật đơn giản của phép tuyển • p ∨ p ⇔ p (tính lũy đẳng của phép tuyển) • p ∨ 1 ⇔ 1 (luật này còn được gọi là luật thống trị) • p ∨ 0 ⇔ p (luật này còn được gọi là luật trung hòa) • p ∨ (p ∧ q) ⇔ p (luật này còn được gọi là luật hấp thụ) j. Các luật đơn giản của phép hội • p ∧ p ⇔ p (tính lũy đẳng của phép hội) • p ∧ 1 ⇔ p (luật này còn được gọi là luật trung hòa) • p ∧ 0 ⇔ 0 (luật này còn được gọi là luật thống trị) • p ∧ (p ∨ q) ⇔ p (luật này còn được gọi là luật hấp thụ) Những luật trên được chọn lựa để làm cơ sở cho chúng ta thực hiện các biến đổi logic, suy luận và chứng minh. 5. Các qui tắc thay thế Dưới đây là các qui tắc để cho ta có thể suy ra những biểu thức logic mới hay tìm ra các biểu thức logic tương đương với một biểu thức logic cho trước. a. Qui tắc 1 Trong một biểu thức logic E, nếu ta thay thế một biểu thức con bởi một biểu thức logic tương đương với biểu thức con đó thì ta sẽ được một biểu thức mới E’ tương đương với biểu thức E. b. Qui tắc 2 Giả sử biểu thức logic E là một hằng đúng. Nếu ta thay thế một biến mệnh đề p bởi một biểu thức logic tuỳ ý thì ta sẽ được một biểu thức logic mới E’ cũng là một hằng đúng. c. Các ví dụ áp dụng Ví dụ 1: Chứng minh rằng (p → q) ⇔ (¬ q →¬ p). Ví dụ 2: Chứng minh rằng biểu thức ((p → q) ∧ p) → q là một hằng đúng. Ví dụ 3: Chứng minh rằng biểu thứcp ∧ q → plà một hằng đúng. Ví dụ 4: Chứng minh rằng biểu thứcp → p ∨ qlà một mệnh đề hằng đúng. Nhận xét:Các ví dụ trên cho ta thấy một quan hệ khác giữa các mệnh đề phức hợp hay các mệnh đề : quan hệ “suy ra”. Khi mệnh đề p → q là hằng đúng, ta nói rằng p suy ra q (về mặt logic). Chúng ta sẽ dùng ký hiệu ⇒ để chỉ quan hệ “suy ra”. Quan hệ suy ra nầy có tính truyền (hay bắc cầu), nhưng không có tính chất đối xứng. IV. Quy tắc suy diễn 1. Định nghĩa GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌC Biên soạn : Gv. Phạm Phúc Thịnh 6Tuy có nhiều kỹ thuật, nhiều phương pháp chứng minh khác nhau, nhưng trong chứng minh trong toán học ta thường thấy những lý luận dẫn xuất có dạng: Nếu p1 và p2 và . . . và pn thì q. Dạng lý luận nầy được xem là hợp lý (được chấp nhận là đúng) khi ta có biểu thức (p1∧ p2∧ . . . ∧ pn) → q là hằng đúng. Ta gọi dạng lý luận trên là một luật suy diễn Người ta cũng thường viết luật suy diễn trên theo các cách sau đây : • Cách 1: Biểu thức hằng đúng (p1∧ p2∧ . . . ∧ pn) → q ⇔ 1 • Cách 2: Dòng suy diễn (p1∧ p2∧ . . . ∧ pn) ⇒ q • Cách 3: Mô hình suy diễn p1 . . . . pn ∴∴∴∴ q Các biểu thức logic p1, p2, . . ., pn trong luật suy diễn trên được gọi là giả thiết (hay tiền đề), và biểu thức q được gọi là kết luận. Ví dụ : Giả sử p và q là các biến logic. Xác định xem mô hình sau đây có phải là một luật suy diễn hay không? p → q p ∴ q Giải: Lập bảng chân trị ta có: P Q p→ q (p→ q)∧ p ((p→ q) ∧ p)→ q 0 0 1 0 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 Bảng chân trị cho thấy biểu thức ((p→ q) ∧ p)→ q là hằng đúng. Do đó, mô hình suy luận trên đúng là một luật suy diễn. 2. Kiểm tra một qui tắc suy diễn Ðể kiểm tra một qui tắc suy diễn xem có đúng hay không ta có thể sử dụng một trong các phương pháp sau đây: a. Phương pháp 1: Lập bảng chân trị. Thiết lập biểu thức logic tương ứng của qui tắc suy diễn và lặp bảng chân trị của biểu thức đó để xem nó có phải là hằng đúng hay không. Trong trường hợp biểu thức logic là hằng đúng thì ta kết luận qui tắc suy diễn là đúng. Ngược lại, ta kết luận qui tắc suy diễn là sai. Ví dụ: Kiểm tra qui tắc suy diễn sau đây(p→ q) ∧ p ⇒ q b. Phương pháp 2: Chứng minh bằng cách sử dụng các luật logic. Thiết lập biểu thức logic tương ứng của qui tắc suy diễn và chứng minh biểu thức là hằng đúng bằng cách áp dụng các luật logic và các qui tắc thay thế. GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌC Biên soạn : Gv. Phạm Phúc Thịnh 7Ví dụ: Kiểm tra qui tắc suy diễn sau đây: (p→ q) ∧ p ⇒ q Ghi chú: Ðể kiểm tra một qui tắc suy diễn ta còn có thể kết hợp 2 phương pháp trên và áp dụng cả những luật suy diễn đã biết trước. 3. Các qui tắc suy diễn cơ bản a. Qui tắc Modus Ponens (p→ q) ∧ p →q hoặc là viết dưới dạng mô hình suy diễn p → q p −−−−−−−− ∴ q b. Qui tắc Modus Tollens (p→ q) ∧ q → ¬ p hoặc là viết dưới dạng mô hình suy diễn p → q ¬ q −−−−−− ∴¬ p c. Tam đoạn luận (p→ q) ∧ (q→ r) ∧ (p→ r) hoặc là viết dưới dạng mô hình suy diễn p → q q→ r −−−−−−− ∴ p→ r d. Qui tắc chứng minh bằng phản chứng p → q ⇒ (p → ¬q) → 0 Qui tắc nầy cho phép ta chứng minh (p → ¬q) → 0 thay cho p → q. Nói cách khác, nếu ta thêm giả thiết phụ vào tiền đề p mà chứng minh được có sự mâu thuẫn thì ta có thể kết luận q từ tiền đề p. e. Qui tắc chứng minh theo trường hợp (p1→ q) ∧ (p2→ q) ∧ . . . ∧ (pn→ q) ⇒ (p1∨ p2∨ . . . ∨ pn) → q hoặc là viết dưới dạng mô hình suy diễn p1→ q p2→ q . . . pn→ q −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− ∴∴∴∴ (p1∨ p2∨ . . . ∨ pn) → q f. Kiểm tra một phép suy luận cụ thể Ðể kiểm tra một suy luận cụ thể là đúng hay không, ta căn cứ vào các qui tắc suy diễn (luật suy diễn). V. Ðịnh nghĩa vị từ và lượng từ 1. Ðịnh nghĩa vị từ: GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌC Biên soạn : Gv. Phạm Phúc Thịnh 8Một vị từ là một phát biểu p(x, y, …) phụ thuộc theo các biến x, y, … lấy giá trị trên các miền xác định A, B, … nào đó. Khi thay thế các biến trong vị từ bởi các giá trị cụ thể a, b, … thuộc các miền xác định thì ta được một mệnh đề p(a, b, …) có chân trị đúng hoặc sai. Gọi B là tập hợp gồm có hai giá trị : Sai (ký hiệu bởi 0), và Ðúng (ký hiệu bởi 1). Một vị từ p(x, y, …) có thể lấy 1 trong 2 giá trị của tập B. Ví dụ: P(n) ≡ “n là một số nguyên tố” là một vị từ trên tập hợp các số tự nhiên (hoặc trên tập hợp các số nguyên). Ta có thể thấy rằng: P(1) = 0, tức là P(1) ≡ “1 là một số nguyên tố” là một mệnh đề sai. P(2) = 1, tức là P(2) ≡ “2 là một số nguyên tố” là một mệnh đề đúng. P(12) = 0, tức là P(12) ≡ “12 là một số nguyên tố” là một mệnh đề sai. P(17) = 1, tức là P(17) ≡ “17 là một số nguyên tố” là một mệnh đề đúng. 2. Các phép toán trên các vị từ Cho p(x, y, …) là một vị từ theo các biến x, y, … . Phủ định của p, ký hiệu là ¬p, là một vị từ mà khi thay các biến x, y, … bởi các phần tử cụ thể a, b, … tương ứng thì ta được mệnh đề ¬(p(a, b, …)). Nói một cách khác, vị từ ¬p được định nghĩa bởi:(¬ p) (x, y, …) = ¬(p(x, y, …)) Cho p(x, y, …) và q(x, y, …) là các vị từ theo các biến x, y, … . Phép hội của p và q, ký hiệu là p→ q, là một vị từ mà khi thay các biến x, y, … bởi các phần tử cụ thể a, b, … tương ứng thì ta được mệnh đề p(a, b, …) → q(a, b, …). Nói một cách khác, vị từ p∧q được định nghĩa bởi:(p ∧ q) (x, y, …) = p (x, y, …) ∧ q (x, y, …) Một cách tương tự, các phép toán tuyển, kéo theo và tương đương của 2 vị từ p và q có thể được định nghĩa như sau: (p ∨ q) (x, y, …) = p (x, y, …) ∨ q (x, y, …) (p → q) (x, y, …) = p (x, y, …) → q (x, y, …) (p ↔ q) (x, y, …) = p (x, y, …) ↔ q (x, y, …) VI. Các lượng từ và các mệnh đề có lượng từ 1. Khái niệm Lượng từ “với mọi” và “tồn tại” (hay “có ít nhất một”)là từ dùng để diễn tả vị từ đúng đối với mọi giá trị thuộc miền xác định hay chỉ đúng với một phần các giá trị thuộc miền xác định. Cho P(n) là một vị từ theo biến số tự nhiên n. • Phát biểu “với mọi n ∈N, P(n)” có nghĩa là P có giá trị đúng trên toàn bộ miền xác định. Ký hiệu “ ∀ “ để thay thế cho lượng từ “với mọi”. • Phát biểu “Có (ít nhất) một n ∈N, P(n)” có nghĩa là P có giá trị đúng đối với một hay một số giá trị nào đó thuộc miền xác định. Ký hiệu “∃ “ để thay thế cho lượng từ “có ít nhất một”. Lượng từ nầy còn được đọc một cách khác là “tồn tại”. Trong nhiều phát biểu người ta còn dùng cụm từ “tồn tại duy nhất”, ký hiệu bởi ∃∃∃∃!, như là một sự lượng từ hóa đặc biệt. Các Ví dụ: • Cho vị từ P(n) ≡ “n là một số nguyên tố”. Mệnh đề “Với mọi số tự nhiên n ta có n là nguyên tố” có thể được viết như sau:∀ n ∈N : P(n)và mệnh đề nầy có chân trị là 0 (sai). • Mệnh đề “Với mọi số nguyên n ta có 2n-1 là một số lẻ” có thể được viết dưới dạng ký hiệu như sau:∀ n ∈Z : 2n-1 lẻvà mệnh đề nầy có chân trị là 1 (đúng). GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌC Biên soạn : Gv. Phạm Phúc Thịnh 9• Mệnh đề “Ta có x2> 0, với mọi số thực x khác 0” có thể được viết là ∀ x ∈R - { 0} : x2> 0 và mệnh đề nầy có chân trị là 1 (đúng). 2. Qui tắc phủ định mệnh đề có lượng từ Dựa vào cách xác định chân trị của các mệnh đề có lượng từ, ta có các qui tắc phủ định mệnh đề có lượng từ sau đây: • ¬ (∀ x : P(x)) ≡∃ x : ¬ P(x) (1) • ¬ (∃ x : P(x)) ≡∀ x : ¬ P(x) (2) Ghi chú : Từ các qui tắc trên ta có thể nói chung về qui tắc phủ định mệnh đề có lượng từ như sau: Nếu trong một mệnh đề có lượng từ ta thay thế lượng từ ∀ bởi lượng từ ∃ , lượng từ ∃ bởi lượng từ ∀ , và biểu thức vị từ được thay thế bởi phủ định của nó thì ta sẽ được mệnh đề phủ định của mệnh đề có lượng từ ban đầu. Qui tắc nầy cũng áp dụng được cho các mệnh đề với nhiều lượng từ. 3. Một số qui tắc dùng trong suy luận a. Thay đổi thứ tự lượng từ hóa của 2 biến Cho một vị từ p(x, y) theo 2 biến x, y. Nếu lượng từ hóa cả 2 biến x, y trong đó ta lượng từ hóa biến y trước và lượng từ hóa biến x sau thì sẽ được 4 mệnh sau đây: • x, ∀ y : p(x,y) • x, ∀ y : p(x,y) • x, ∀ y : p(x,y) • x, ∀ y : p(x,y) Tương tự ta cũng có 4 mệnh đề lượng từ hóa từ vị từ p(x, y) trong đó ta lượng từ hóa biến x trước và lượng từ hóa biến y sau: • y, ∀ x : p(x,y) • y, ∀ x : p(x,y) • y, ∀ x : p(x,y) • y, ∀ x : p(x,y) b. Ðịnh lý: Giả sử p(x, y) là một vị từ theo 2 biến x, y thì các mệnh đề sau là đúng • (∀ x, ∀ y : p(x,y) ) ↔ (∀ y, ∀ x : p(x,y) ) • (∃ x, ∃ y : p(x,y) ) ↔ (∃ y, ∃ x : p(x,y) ) • (∃ x, ∀ y : p(x,y) ) → (∀ y, ∃ x : p(x,y) ) c. Qui tắc đặc biệt hóa phổ dụng Giả sử một mệnh đề có lượng từ trong đó biến x với miền xác định là A, được lượng từ hóa và bị buộc bởi lượng từ phổ dụng ∀ , và mệnh đề là đúng. Khi đó nếu thay thế x bởi a ∈ A thì ta sẽ được một mệnh đề đúng. d. Qui tắc tổng quát hóa phổ dụng Qui tắc: Nếu ta thay thế biến x trong vị từ P(x) bởi một phần tử a cố định nhưng tùy ý thộc miền xác định của biến x mà mệnh đề nhận được có chân trị là đúng, tức là P(a) = 1, thì mệnh đề lượng từ hóa∀ x : P(x)là một mệnh đề đúng. Từ các qui tắc trên ta có thể chứng minh được một số tính chất suy diễn được phát biểu trong các mệnh đề sau đây: • Mệnh đề 1: Cho p(x) và q(x) là các vị từ theo biến x lấy giá trị trong tập hợp A (miền xác định của biến x là tập hợp A), và a là một phần tử cố định tùy ý thuộc A. Khi ấy ta có qui tắc suy diễn sau đây: ∀ x : p(x) → q(x) GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌC Biên soạn : Gv. Phạm Phúc Thịnh 10p(a) −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− ∴∴∴∴ q(a) • Mệnh đề 2: Cho p(x), q(x) và r(x) là các vị từ theo biến x lấy giá trị trong tập hợp A (miền xác định của biến x là tập hợp A). Ta có qui tắc suy diễn sau đây: ∀ x : p(x) → q(x) ∀ x : q(x) → r(x) −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− ∴∴∴∴∀ x : p(x) → r(x) 4. Dị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ểu bằ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ết sứ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ôn ngữ 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àm mấ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ột biể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ều nà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ông thường thành biểu thức logic thông qua những sau. a. Ví dụ 1 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ạn trên 18 tuổi” thành biểu thức logic. 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 : Bạn trên 18 tuổi. Khi đó: Câu hỏi trên được dịch là: (q ∧∧∧∧ ¬r) → ¬p b. Ví dụ 2 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” 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 định trong 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) c. 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 ít nhất một nhà trong ký túc xá”. 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ác nhà 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át biểu: ∃∃∃∃ x ∃∃∃∃ y ∀∀∀∀ z (P(z,y) → Q(x,z)); VII. Tập hợp - Các phép toán tập hợp 1. Khái niệm tập hợp GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌC Biên soạn : Gv. Phạm Phúc Thịnh 11Tập hợp là một trong các khái niệm cơ bản của Toán học. Khái niệm tập hợp không được định nghĩa mà chỉ được mô tả qua các ví dụ: Tập hợp các học sinh của một lớp học, tập hợp các cầu thủ của một đội bóng, tập hợp các cuốn sách trên một giá sách, tập hợp các số tự nhiên, Các đối tượng cấu thành một tập hợp được gọi là các phần tử của tập hợp đó. Người ta thường kí hiệu các tập hợp bởi các chữ A, B, C, X, Y, Z, và các phần tử của tập hợp bởi các chữ a, b, c, x, y, z, Nếu a là một phần tử của tập hợp A thì ta viết a ∈ A (đọc là a thuộc tập hợp A). Nếu a không phải là một phần tử của tập hợp A thì ta viết a∉ A (đọc là a không thuộc tập hợp A). 2. Biểu diễn một tập hợp Có hai cách biểu diễn một tập hợp: • Cách thứ nhất là liệt kê tất cả các phần tử của tập hợp. Tập hợp A gồm bốn số tự nhiên 1, 3, 5, 7 được viết là: A = {1, 3, 5, 7}. • Cách thứ hai là nêu lên một tính chất chung của các phần tử của tập hợp, nhờ đó có thể nhận biết được các phần tử của tập hợp và các đối tượng không phải là những phần tử của nó. Chẳng hạn, C = {x / x là ước số của 8} Người ta thường biểu thị tập hợp A bởi một đường cong kín gọi là lược đồ Venn. 3. Tập hợp con, các tập hợp bằng nhau a. Tập hợp con : Tập hợp A được gọi là một tập con của tập hợp X nếu mọi phần tử của A đều là những phần tử của X. Ký hiệu : A ⊂X (1) hoặc X⊃A(2) (đọc là X chứa A) Ký hiệu⊂được gọi là dấu bao hàm. Hệ thức (1) hoặc (2) gọi là một bao hàm thức. Định lý : tập hợp có n phần tử có cả thảy 2n tập hợp con. b. Các tập hợp bằng nhau Tập hợp A và tập hợp B được gọi là bằng nhau khi và chỉ khi A⊂Bvà B⊂A c. Với các tập hợp bất kì A, B, C, ta có: • φ⊂A, • A ⊂A, • Nếu A ⊂B và B ⊂C thì A ⊂C, • Nếu A ≠B thì A ⊄B 4. Các phép toán trên tập hợp a. Giao của các tập hợp Giao của hai tập hợp A và B là tập hợp tạo nên bởi các phần tử chung của hai tập hợp đó, kí hiệu là: A ∩ B (đọc là A giao B) Từ định nghĩa của A ∩ B suy ra rằng x ∈ A ∩ B ⇔ x ∈ A và x ∈ B Từ định nghĩa giao của hai tập hợp, dễ dàng chứng minh được các đẳng thức sau với các tập hợp bất kì A, B, C, ta có: • A ∩ B = B ∩ A, • (A ∩ B) ∩ C = A ∩ (B ∩ C), • ∅ ∩ A = ∅ • A ∩ A = A b. Hợp của các tập hợp Hợp của hai tập hợp A và B là tập hợp tạo nên bởi các phần tử thuộc ít nhất một trong hai tập hợp đó, kí hiệu là A ∪ B (đọc là A hợp B). Từ định nghĩa của A ∪ B suy ra rằng x ∈ A ∪ B  x ∈ A hoặc x ∈ B. Từ định nghĩa của hợp các tập hợp dễ dàng suy ra với các tập hợp bất kì A, B, C, • A ∪ B = B ∪ A, • (A ∪ B) ∪ C = A ∪ (B ∪ C), 1 2 4 8 Tập hợp C GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌC Biên soạn : Gv. Phạm Phúc Thịnh Trang 12 • ∅∪ A = A, • A ∪ A = A. c. Hiệu của hai tập hợp Hiệu của hai tập hợp A và B là tập hợp các phần tử thuộc A nhưng không thuộc B, kí hiệu là A \ B (đọc là A trừ B). Từ định nghĩa của A \ B suy ra:x ∈ A \ B ⇔ x ∈ A và x ∉ B Với các tập hợp bất kì A, B, C, D, ta có: • A \ B ⊂ A • Nếu A ⊂ B và C ⊂ D thì A \ D ⊂ B \ C • Nếu C ⊂ D thì A \ D A \ C • A ⊂ B ⇔ A \ B = ∅. d. Phần bù của một tập hợp Cho tập hợp X và A là một tập con của X. Tập hợp X \ A được gọi là phần bù của A và được kí hiệu là ܥܣ Từ định nghĩa phần bù của một tập hợp suy ra rằng Nếu X là một tập hợp và A ⊂ X thì với mọi x ∈ X, x ∈ CA ⇔ x ∉ A. Với các tập con bất kì A, B của không gian X, ta có: • X ∩ A = A, • X ∪ A = X, • CX = ∅, • C∅ = X, • CCA = A, • A ⊂ B ⇔ CB ⊂ CA. e. Tích Descartes của các tập hợp Cho hai tập hợp X và Y,tập hợp tất cả các cặp thứ tự (x, y) trong đó x ∈ X, y ∈ Y gọi là tích Descartes của hai tập hợp X, Y và được kí hiệu là X x Y. Như vậy, X x Y = {(x, y) : x ∈ X, y ∈ Y}. Cho m tập hợp X1, X2, , Xm. Tập hợp các dãy m phần tử (x1, x2, , xm),trong đó x1 ∈ X1, x2 ∈ X2, , xn ∈ Xm gọi là tích Đêcác của m tập hợp X1,X2, , Xm và được kí hiệu là X1 x X2 x x Xm. X1 x X2 x x Xm = {(x1, x2, , xm) : x1 ∈ X1, xm ∈ Xm}. Nếu X1 = X2 = = Xm thì tập hợp X1 x X2 x x Xm được kí hiệu là Xm. Như vậy Xm là tập hợp các dãy m phần tử (x1, x2, , xm), trong đó x1, , xm∈ X. VIII. Khái niệm Ánh xạ 1. Định nghĩa Giả sử X và Y là hai tập hợp. một ánh xạ f từ X vào Y là một quy tắc cho ta với mỗi phần tử x ∈ X, tồn tại một phầntử duy nhất y ∈ Y sao cho y=f(x). Ánh xạ f từ tập hợp X vào tập hợp Y được kí hiệu là:f : X → Y. Nếu x là một phần tử của tập hợp X thì phần tử y của tập hợp Y sao cho y=f(x) y được gọi là ảnh của x qua ánh xạ f. 2. Ánh xạ bằng nhau Giả sử X và Y là hai tập hợp, f và g là hai ánh xạ từ X vào Y. Ta nói rằnghai ánh xạ f và g là bằng nhau, và viết f = g, nếu f (x) = g (x) với mọi x∈∈∈∈X. 3. Ánh xạ hợp Cho 2 ánh xạ f : X → Y g : Y → Z Ánh xạ hợp h của f và g là ánh xạ từ X vào Z xác định bởi: h : X → Z x h(x) = g(f(x)) Ta viết h = g o f. 4. Ảnh và ảnh ngược GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌC Biên soạn : Gv. Phạm Phúc Thịnh Trang 13 a. Định nghĩa Cho ánh xạ f từ X vào Y và A ⊂ X, B ⊂ Y. Ta định nghĩa: f(A) = {f(x) | x ∈ A} = {y ∈ Y |∃x ∈ A, y = f(x)} ∀y ∈ Y, y ∈ f(A) ⇔∃x ∈ A, y = f(x); ∀y ∈ Y, y ∉ f(A) ⇔∀x ∈ A, y ≠ f(x). f–1(B) = {x ∈ X | f(x) ∈ B} ∀x ∈ X, x ∈ f–1(B) ⇔ f(x) ∈ B; ∀x ∈ X, x ∉ f–1(B) ⇔ f(x) ∉ B. Ta thường ký hiệu f(X) bởi Imf và f-1({y}) bởi f-1(y). Imf được gọi là ảnh của ánh xạ f. b. Tính chất: f(A1∪ A2) = f(A1) ∪ f(A2); f(A1∩ A2) ⊂ f(A1) ∩ f(A2); f(A1 \ A2) ⊃ f(A1) \ f(A2); f–1(B1∪ B2) = f–1(B1) ∪ f–1(B2); f–1(B1∩ B2) = f–1(B1) ∩ f–1(B2); f–1(B1 \ B2) = f–1(B1) \ f–1(B2). 5. Phân loại ánh xạ a. Đơn ánh Ta nói f : X → Y là một đơn ánh nếu hai phần tử khác nhau bất kỳ của X đều có ảnh khác nhau, nghĩa là: ∀x, x' ∈ X, x ≠ x' ⇒ f(x) ≠ f(x' ) b. Toàn ánh Ta nói f : X → Y là một toàn ánh nếu Imf = Y c. Song ánh Ta nói f : X → Y là một song ánh nếu f vừa là đơn ánh vừa là toàn ánh. IX. Lực lượng của tập hợp 1. Định nghĩa lực lượng của tập hợp Mỗi tập A ta đặt tương ứng với một đối tượng |A| gọi là lực lượng của tập A ,sao cho |A| = |B| khi và chỉ khi tồn tại song ánh từ A vào B. Lực lượng của tập A còn được gọi là bản số của A và ký hiệu là cardA. Lực lượng của tập rỗng là số 0 Lực lượng của tập {1,2,…,n} là n. 2. Định nghĩa tập hợp hữu hạn-vô hạn Tập hợp A được gọi là tập hữu hạn nêu ta có thể đếm được hết các phần tử của tập hợp này. Nếu mãi vẫn còn những phần tử của A không được đếm tới thì tập A được gọi là tập vô hạn. 3. Tập hợp đếm được a. Định nghĩa 1 : Lực lượng của tập số tự nhiên N được gọi là lực lượng đếm được. b. Định nghĩa 2 : Hai tập hợp A và B được gọi là tương đương nhau nếu có thể thiết lập một song ánh giữa 2 tập hợp này. Ký hiệu A ~B c. Định nghĩa 3 : Một tập hợp tương đương với tập hợp N được gọi là tập hợp đếm được GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌC Biên soạn : Gv. Phạm Phúc Thịnh Trang 14 d. Định nghĩa 4 : Tập hợp không đếm được là một tập hợp vô hạn và không là tập hợp đếm được/ X. Quy nạp toán học – Định nghĩa đệ quy 1. Quy nạp toán học a. Khái niệm Quy nạp là kết luận đi từ trường hợp riêng đi tới trường hợp tổng quát. Nghĩa là, kết luận tổng quát dựa trên việc nghiên cứu các tính chất của nhiều sự kiện, nhiều thí nghiệm hay nhiều quan sát riêng lẻ. Nếu kết luận chung dựa vào nghiên cứu tất cả các sự kiện riêng (các đối tượng, các hình, các số, vv…) thì quy nạp được gọi là đầy đủ hay hoàn chỉnh. Nếu kết luận chung dựa vào nghiên cứu một phần của tâp hợp tất cả các sự kiện (các đối tượng) thì quy nạp được gọi là không đầy đủ hay không hoàn chỉnh. b. Cơ sở toán của nguyên lý quy nạp Nếu W là một tính chất được xác định trên tập hợp tất cả các số tự nhiên sao cho W(1) (1 có tính chất W), đối với một số tự nhiên n nếu W(n) thì W(n+1) ( nếu n có tính chất W thì n+1 có tính chất W), thì mọi số tự nhiên đều có tính chất W. 2. Các định lý về quy nạp a. Định lý 1. Nếu W là một tính chất được xác định trong tập hợp của tất cả các số tự nhiên sao cho W (1) (1 có tính chất W) đối với mọi số tự nhiên n: nếu W(k) (k có tính chất W) với mọi số tự nhiên k: sao cho thì W(n+1) (n+1 có tính chất W), thì mọi số tự nhiên đều có tính chất W. b. Định lý 2. Nếu là φ hàm mệnh đề của biến x biến thiên trên tập hợp tất cả các số tự nhiên sao cho ϕ(1) (1 thoả mãn mệnh đề φ(x)) đối với mọi số tự nhiên n : nếu ϕ(k) (k thoả mãn ϕ(x)) đối với mọi số tự nhiên k sao cho , thì φ(n+1) (n+1 thỏa mãn φ(x)), thì mọi số tự nhiên thỏa mãn hàm mệnh đề φ(x). 3. Thuật toán đệ quy a. Khái niệm đệ quy Một thuật toán được gọi là đệ quy nếu nó giải bài toán bằng cách rút gọn liên tiếp bài toán ban đầu tới bài toán cũng như vậy nhưng có dữ liệu đầu vào nhỏ hơn. Ví dụ: Tìm thuật toán đệ quy tính UCLN của hai số nguyên a,b không âm và a > b. procedure UCLN (a,b: các số nguyên không âm, a > b) if b = 0 then UCLN (a,b) := a else UCLN (a,b) := UCLN (a mod b, b) b. Đệ quy và lặp: Ví dụ. Thủ tục đệ quy sau đây cho ta giá trị của n! với n là số nguyên dương. procedure factorial (n: positive integer) if n = 1 then factorial(n) := 1 else factorial(n) := n * factorial(n-1) GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌC Biên soạn : Gv. Phạm Phúc Thịnh Trang 15 Thông thường để tính một dãy các giá trị được định nghĩa bằng đệ quy, nếu dùng phương pháp lặp thì số các phép tính sẽ ít hơn là dùng thuật toán đệ quy (trừ khi dùng các máy đệ quy chuyên dụng). Ta sẽ xem xét bài toán tính số hạng thứ n của dãy Fibonacci. procedure fibonacci (n: nguyên không âm) if n = 0 then fibonacci(n) := 0 else if n = 1 then fibonacci(n) := 1 else fibonacci(n) := fibonacci(n - 1) + fibonacci(n - 2) Theo thuật toán này, để tìm fn ta biểu diễn fn = fn-1 + fn-2. Sau đó thay thế cả hai số này bằng tổng của hai số Fibonacci bậc thấp hơn, cứ tiếp tục như vậy cho tới khi f0 và f1 xuất hiện thì được thay bằng các giá trị của chúng theo định nghĩa. Do đó để tính fn cần fn+1-1 phép cộng. Bây giờ ta sẽ tính các phép toán cần dùng để tính fn khi sử dụng phương pháp lặp. Thủ tục này khởi tạo x là f0 = 0 và y là f1 = 1. Khi vòng lặp được duyệt qua tổng của x và y được gán cho biến phụ z. Sau đó x được gán giá trị của y và y được gán giá trị của z. Vậy sau khi đi qua vòng lặp lần 1, ta có x = f1 và y = f0 + f1 = f2. Khi qua vòng lặp lần n-1 thì x = fn-1. Như vậy chỉ có n – 1 phép cộng được dùng để tìm fn khi n > 1. procedure Iterative fibonacci (n: nguyên không âm) if n = 0 then y := 0 else begin x := 0 ; y := 1 for i := 1 to n - 1 begin z := x + y x := y ; y := z end end {y là số Fibonacci thứ n} Ta đã chỉ ra rằng số các phép toán dùng trong thuật toán đệ quy nhiều hơn khi dùng phương pháp lặp. Tuy nhiên đôi khi người ta vẫn thích dùng thủ tục đệ quy hơn ngay cả khi nó tỏ ra kém hiệu quả so với thủ tục lặp. Đặc biệt, có những bài toán chỉ có thể giải bằng thủ tục đệ quy mà không thể giải bằng thủ tục lặp. GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌC Biên soạn : Gv. Phạm Phúc Thịnh Trang 16 Chương 2 : PHÉP ĐẾM I. Phép Đếm 1. Định nghĩa: Cho A là một tập hợp khác rỗng. Nếu tồn tại một số nguyên dương n và một song ánh f từ A vào { 1, 2, . . ., n} thì ta nói A là một tập hợp hữu hạn và A có n phần tử. Khi đó song ánh f : A →{ 1, 2, . . ., n} được xem là một phép đếm tập hợp A. Tập hợp rỗng có số phần tử là 0, và cũng được xem là tập hữu hạn. Số phần tử của một tập hợp hữu hạn A được ký hiệu là | A |. Nếu tập hợp A không hữu hạn, ta nói A là một tập vô hạn và viết| A | = ∞ 2. Tính chất: Cho A và B là các tập hợp hữu hạn. Giả sử tồn tại đơn ánh từ A vào B. Khi ấy ta có: | A | ≤ | B |. II. Nguyên lý cộng 1. Mệnh đề: Cho A và B là 2 tập hợp hữu hạn rời nhau, nghĩa là A ∩ B = ∅ . Khi ấy ta có:| A ∪ B | = | A | + | B | Một cách tổng quát: Nếu A1, A2, , An là các tập hợp hữu hạn rời nhau, nghĩa là phần giao của hai tập hợp bất kỳ trong n tập hợp là rỗng, thì số phần tử của phần hội của các tập hợp trên bằng tổng của các số lượng phần tử trong mỗi tập hợp: | A1∪ A2∪ . . . ∪ An | = | A1 | + | A2 | + . . . + | An | Ghi chú: Trong trường hợp đối với hai tập hợp hữu hạn A và B tùy ý thì ta có: | A ∪ B | = | A | + | B | - | A ∩ B | Tính chất nầy có thể mở rộng cho trường hợp đối với n tập hợp tùy ý A1, A2, , An như sau:| A1∪ A2∪ . . . ∪ An | = Σ1≤ r≤ n | Ar | - Σ1≤ r< s≤ n | Ar ∩ As | + Σ1≤ r< s< t ≤ n | Ar ∩ As ∩ At | - . . . + (-1)n | A1∩ A2∩ . . . ∩ An | 2. Nguyên lý cộng : Giả sử ta phải thực hiện công việc và để thực hiện công việc nầy ta có thể chọn một trong hai biện pháp khác nhau theo nghĩa là cách thực hiện biện pháp thứ nhất luôn luôn khác cách thực hiện biện pháp thứ hai. Biện pháp thứ nhất có n cách thực hiện, và đối với biện pháp thứ hai ta có m cách thực hiện. Vậy ta có n+m cách thực hiện công việc. Ví dụ: Xác định giá trị của k sau khi đoạn chương trình sau đây được thực hiện xong k := 0 for i1 := 1 to n1 do k := k + 1; for i2 := 1 to n2 do k := k + 1; . . . for im := 1 to nm do k := k + 1; Lời giải. Giá trị của k ban đầu là 0. Sau đó là m vòng lặp khác nhau. Mỗi thao tác lặp trong một vòng lặp là cộng thêm 1 vào k. Vòng lặp thứ i có ni thao tác, và tất cả m vòng lặp GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌC Biên soạn : Gv. Phạm Phúc Thịnh Trang 17 không thể thực hiện 2 vòng lặp nào một cách đồng thời. Do đó số thao tác để thực hiện xong đoạn chương trình trên là n1 + n2 + + nm. Đây cũng chính là giá trị cuối cùng của k. 3. Nguyên lý nhân : Mệnh đề: Cho A và B là 2 tập hợp hữu hạn rời nhau. Khi ấy ta có: | A x B | = | A | . | B | Một cách tổng quát: Nếu A1, A2, , An là các tập hợp hữu hạn thì số phần tử của tích Descartes của các tập hợp trên bằng tích của các số lượng phần tử của các tập hợp trên: | A1 x A2 x . . . x An | = | A1 | . | A2 | . . . . . | An | Giả sử ta phải thực hiện một thủ tục bao gồm hai công việc kế tiếp nhau. Để thực hiện công việc thứ nhất ta có n1 cách, và ứng với mỗi cách chọn thực hiện công việc thứ nhất ta có n2 cách thực hiện công việc thứ hai. Vậy ta có số cách thực hiện thủ tục là n1 x n2. Nguyên lý nhân trên có thể được mở rộng và có dạng tổng quát như sau: Giả sử một thủ tục bao gồm m công việc kế tiếp nhau T1, T2, . . ., Tm. Nếu công việc T1 có thể được thực hiện theo n1 cách, và sau khi chọn cách thực hiện cho T1 ta có n2 cách thực hiện T2, v.v… cho đến cuối cùng, sau khi chọn cách thực hiện các công việc T1, T2, . . ., Tm-1 ta có nm cách thực hiện Tm. Vậy ta có n1.n2. .nm cách để thực hiện thủ tục. Nguyên lý nhân ở dạng tổng quát nầy có thể được chứng minh bằng qui nạp từ qui tắc nhân cho trường hợp thủ tục gồm 2 công việc. Ví dụ: Theo qui tắc nhân ta thấy rằng sau khi thực hiện đoạn chương trình dưới đây thì giá trị của biến k sẽ là n1.n2. .nm. k := 0 for i1 = 1 to n1 do for i1 = 1 to n2 do . . . for i1 = 1 to nm do k := k + 1 III. Nguyên lý Dirichlet tổng quát: 1. Mệnh đề: Nếu có N đồ vật được đặt vào trong k hộp thì sẽ tồn tại một hộp chứa ít nhất ]N/k[ đồ vật. 2. Các ví dụ : • Có năm loại học bổng khác nhau. Hỏi rằng phải có ít nhất bao nhiêu sinh viên để chắc chắn rằng có ít ra là 6 người cùng nhận học bổng như nhau. Gọi N là số sinh viên, khi đó ]N/5[ = 6 khi và chỉ khi 5 < N/5 ≤ 6 hay 25 < N ≤ 30. Vậy số N cần tìm là 26. • Số mã vùng cần thiết nhỏ nhất phải là bao nhiêu để đảm bảo 25 triệu máy điện thoại trong nước có số điện thoại khác nhau, mỗi số có 9 chữ số (giả sử số điện thoại có dạng 0XX - 8XXXXX với X nhận các giá trị từ 0 đến 9). Có 107 = 10.000.000 số điện thoại khác nhau có dạng 0XX - 8XXXXX. Vì vậy theo nguyên lý Dirichlet tổng quát, trong số 25 triệu máy điện thoại ít nhất có ]25.000.000/10.000.000[ = 3 có cùng một số. Để đảm bảo mỗi máy có một số cần có ít nhất 3 mã vùng. 3. Một số ứng dụng của nguyên lý Dirichlet. GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌC Biên soạn : Gv. Phạm Phúc Thịnh Trang 18 • Trong một phòng họp có n người, bao giờ cũng tìm được 2 người có số người quen trong số những người dự họp là như nhau. Số người quen của mỗi người trong phòng họp nhận các giá trị từ 0 đến n − 1. Rõ ràng trong phòng không thể đồng thời có người có số người quen là 0 (tức là không quen ai) và có người có số người quen là n − 1 (tức là quen tất cả). Vì vậy theo số lượng người quen, ta chỉ có thể phân n người ra thành n −1 nhóm. Vậy theo nguyên lý Dirichlet tồn tai một nhóm có ít nhất 2 người, tức là luôn tìm được ít nhất 2 người có số người quen là như nhau. • Trong một tháng gồm 30 ngày, một đội bóng chuyền thi đấu mỗi ngày ít nhất 1 trận nhưng chơi không quá 45 trận. Chứng minh rằng tìm được một giai đoạn gồm một số ngày liên tục nào đó trong tháng sao cho trong giai đoạn đó đội chơi đúng 14 trận. Gọi aj là số trận mà đội đã chơi từ ngày đầu tháng đến hết ngày j. Khi đó 1 ≤ a1 < a2< < a30< 45 15 ≤ a1+14< a2+14 < < a30+14 < 59. Sáu mươi số nguyên a1, a2, , a30, a1+ 14, a2 + 14, , a30+14 nằm giữa 1 và 59. Do đó theo nguyên lý Dirichlet có ít nhất 2 trong 60 số này bằng nhau. Vì vậy tồn tại i và j sao cho ai= aj+ 14 (j < i). Điều này có nghĩa là từ ngày j + 1 đến hết ngày i đội đã chơi đúng 14 trận. • Chứng tỏ rằng trong n + 1 số nguyên dương không vượt quá 2n, tồn tại ít nhất một số chia hết cho số khác. Ta viết mỗi số nguyên a1, a2, , an+1 dưới dạng aj = jk2qj trong đó kj là số nguyên không âm còn qj là số dương lẻ nhỏ hơn 2n. Vì chỉ có n số nguyên dương lẻ nhỏ hơn 2n nên theo nguyên lý Dirichlet tồn tại i và j sao cho qi = qj = q. Khi đó ai= ik2q và aj = jk2q. Vì vậy, nếu ki ≤ kj thì aj chia hết cho ai còn trong trường hợp ngược lại ta có ai chia hết cho aj. • Giả sử trong một nhóm 6 người mỗi cặp hai hoặc là bạn hoặc là thù. Chứng tỏ rằng trong nhóm có ba người là bạn lẫn nhau hoặc có ba người là kẻ thù lẫn nhau. Gọi A là một trong 6 người. Trong số 5 người của nhóm hoặc là có ít nhất ba người là bạn của A hoặc có ít nhất ba người là kẻ thù của A, điều này suy ra từ nguyên lý Dirichlet tổng quát, vì ]5/2[ = 3. Trong trường hợp đầu ta gọi B, C, D là bạn của A. nếu trong ba người này có hai người là bạn thì họ cùng với A lập thành một bộ ba người bạn lẫn nhau, ngược lại, tức là nếu trong ba người B, C, D không có ai là bạn ai cả thì chứng tỏ họ là bộ ba người thù lẫn nhau. Tương tự có thể chứng minh trong trường hợp có ít nhất ba người là kẻ thù của A. IV. CHỈNH HỢP 1. Ðịnh nghĩa Cho X là một tập hợp gồm n phần tử, và r là một số nguyên dương nhỏ hơn hoặc bằng n. Mỗi phép chọn r phần tử phân biệt của X theo một thứ tự nào đó sẽ cho ta một chỉnh hợp n chọn r. Nói cách khác, ta có thể xem một chỉnh hợp như là một dãy hay một bộ gồm r phần tử phân biệt được chọn từ n phần tử cho trước. Ví dụ. Cho tập hợp S = { 1, 2, 3} . Dãy gồm 2 phần tử 3, 2 là một chỉnh hợp 3 chọn 2. Sự sắp xếp các phần tử thành dãy 3, 1, 2 cho ta một chỉnh hợp 3 chọn 3. Chỉnh hợp 3 chọn 3 nầy còn được gọi là một hoán vị của 3 phần tử. Một chỉnh hợp n chọn n được gọi là một hoán vị của n phần tử. Nói cách khác, một hoán vị n phần tử là một cách sắp xếp n phần tử theo một thứ tự nào đó. Mỗi hoán vị n phần tử của tập X cũng có thể được xem như một song ánh từ X vào X. 2. Công thức chỉnh hợp GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌ Ðịnh lý I.1. Số các chGhi chú: 0! = 1 n! = (n-1)! n (n lớn hV. TỔ HỢP 1. Ðịnh nghĩa Cho X là một tập hợbằng n. Mỗi phép chọn r phầcho ta một tổ hợp n chọn r. Nói cách khác, ta có thhợp con gồm r phần tử của mVí dụ : Cho tập hợp S = Số các tổ hợp n chọn r đVí dụ : C(4,2) = 6 vì ta có thhợp có 4 phần tử và th2. Công thức tổ hợp Ðịnh lý. Số các tổ hợp n chọn r , v Ví dụ : Số danh sách không kngười là C(10,5) = 10! / (5!5!) = 252.VI. CÔNG THỨC NHỊ TH1. Ðịnh lý. Cho x và y là 2 biến th2. Hệ quả 1. Cho n là một số nguyên không âm tùy ý. Ta có: 3. Hệ quả 2. Cho n là một số nguyên không âm. Ta có: VII. MỘT SỐ TÍNHa. Với mọi số tự nhiC(n, 0) = 1 C(n, n) = 1 b. Cho n và r là 2 sC(n,r) = C(n,nc. Cho n và k là 2 sC(n, k) = C(nNG TIN HỌC Biên so các chỉnh hợp n chọn r là ớn hơn 0) ập hợp gồm n phần tử, và r là một số nguyên không âm nhn r phần tử phân biệt của X mà không phân bin r. Nói cách khác, ta có thể xem một tổ hợp n cha một tập hợp có n phần tử. p S = { 1, 2, 3, 4} . Ta có tập S’ = { 1, 3, 4} là mọn r được ký hiệu là C(n,r). : C(4,2) = 6 vì ta có thể liệt kê ra tất cả các tập hợp con 2 phà thấy có tất cả là 6 tập con. n r , với n và r là các số nguyên thỏa 0 ≤ r ≤ n, l danh sách không kể thứ tự trước sau gồm 5 người của mà C(10,5) = 10! / (5!5!) = 252. Ị THỨC NEWTON: ến thực, n là một số nguyên không ấm tùy ý. Ta có:(x+y)n= ên không âm tùy ý. Ta có: ên không âm. Ta có: TÍNH CHẤT KHÁC CỦA TỔ HỢP nhiên n ta có: ố nguyên không âm và r ≤ n. Ta có: C(n,r) = C(n,n-r) Cho n và k là 2 số nguyên sao cho 0 < k < n. Khi đó ta có:C(n, k) = C(n-1, k) + C(n-1, k-1). Biên soạn : Gv. Phạm Phúc Thịnh Trang 19 ên không âm nhỏ hơn hoặc à không phân biệt thứ tự trước sau sẽ ợp n chọn r như là một tập là một tổ hợp 4 chọn 3. p con 2 phần tử của một tập ≤ n, là i của một lớp học gồm 10 ùy ý. Ta có: ó ta có: GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌ d. Công thức Vandermonde: Cho m, n, và r là các scó: VIII. HOÁN VỊ LẶP V1. Hoán vị lặp a. Định nghĩa Cho n đối tượng trong n1+ n2,…+ nk= n), Mỗlặp của n. b. Ðịnh lý 1: Giả sử có n vật hay n2 đối tượng thuộc loại 2, . . ., vKhi ấy số cách sắp xếp n tượng, là : n! / (n1! n2! . . . nVí dụ:Giả sử n và k là 2 ssố nguyên. Giải: Xét n ký hiệu x1, xhiệu nầy làn! / (2! 2! . . . 2!) = n!/ 2c. Ðịnh lý 2: (x1 + x2 + . . . + xm)n = Σ {n} trong đó các hệ số c(n, r. . . rm!) Ví dụ: Tìm hệ số của x3yGiải: Áp dụng định lý ta có: trong khai tridạng C(7, 3, 2, 2) x3(2y)Suy ra hệ số của x3y2z2 làIX. Tổ hợp lặp 1. Ðịnh nghĩa: Mỗi cách chọn ra k vchọn lại nhiềulần) được gọi lký hiệu là 2. Công thức tính tổ hợp lặSố các tổ hợp lặp chập k củ3. Các hệ quả: a. Hệ quả 1 : Số nghiệm nguyên không âm (x1,x2,…,xn) (mphương trình x1+ x2+…+ xnb. Hệ quả 2 : Số cách chia k vật đồlặp chập k của n làNG TIN HỌC Biên soc Vandermonde: Cho m, n, và r là các số nguyên không âm với r nhỏ hơn ho ẶP VÀ TỔ HỢP LẶP ợng trong đó có ni đối tượng loại i giống hỗi cách sắp xếp có thứ tự n đối tượng đã cho gật hay đối tượng trong đó có n1 đối tượng thuộại 2, . . ., và nr đối tượng thuộc loại thứ r, với n = nếp n đối tượng trên thành dãy có thứ tự, hay s! . . . nr!) à k là 2 số nguyên dương sao cho n = 2k. Chứng minh r, x1, x2, x2, . . ., xk, xk. Theo định lý trên ta có sàn! / (2! 2! . . . 2!) = n!/ 2kSuy ra rằng n!/ 2k là một số nguy Σ {C(n, r1, …, rm) : 0 ≤ ri ≤ố c(n, r1, …, rm) được tính theo công thứcC(n, ry2z2 trong khai triển của (x + 2y - 3z)7. nh lý ta có: trong khai triển của (x + 2y - 3z)7 , số h(2y)2(-3z)2 là C(7, 3, 2, 2) 22(-3)2 = 36 x 7! / (3! 2! 2!) = 7560n ra k vật từ n loại vật khác nhau(trong đó mỗọi là tổ hợp lặp chập k của n.Số cáctổ hợp lp lặp: ập k của n được tính theo công thức ên không âm (x1,x2,…,xn) (mỗi xi đều nguyn = k là ật đồng chất nhau vào n hộp phân biệt cũng chính b Biên soạn : Gv. Phạm Phúc Thịnh Trang 20 ơn hoặc bằng m và n. Ta ng hệt nhau (i =1,2,…,k ; ã cho gọi là một hoán vị ng thuộc loại 1 (giống nhau), ới n = n1 + n2 + . . . + nr. hay số hoán vị của n đối ng minh rằng n!/ 2k là một ên ta có số hoán vị của n ký t số nguyên. ≤ n, r1 + r2 + . . . + rm = cC(n, r1, …, rm) = n! / (r1! r2! ố hạng chứa x3y2z2 có = 36 x 7! / (3! 2! 2!) = 7560 ó mỗi loại vật có thể được ợp lặp chập k của n được đều nguyên không âm) của ũng chính bằng số tổ hợp GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌC Biên soạn : Gv. Phạm Phúc Thịnh Trang 21 Ví dụ: Tìm số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 có ít nhất 5 bi, biết rằng hộp 2 và 3 chứa không quá 6 bi. • Trước hết ta tìm số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 có ít nhất 5 bi. • Nhận xét rằng ta cần lấy 5 bi để xếp trước vào hộp 1, do đó số bi còn lại chỉ là 25. Suy ra số cách xếp trong trường hợp này bằng số cách xếp 25 bi vào 5 hộp mà không có điều kiện gì thêm. Số đó là ܭହଶହൌܥହାଶହିଵଶହ=23751 • Tương tự ta có Số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 chứa ít nhất 5 bi, hộp 2 chứa ít nhất 7 bi là:ܭହଵ଼ൌܥହାଵ଼ିଵଵ଼ • Tương tự ta có Số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 chứa ít nhất 5 bi, hộp 3 chứa ít nhất 7 bi là:ܭହଵ଼ൌܥହାଵ଼ିଵଵ଼ • Số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 chứa ít nhất 5 bi, mỗi hộp 2 và 3 chứa ít nhất 7 bi là:ܭହଵଵൌܥହାଵଵିଵଵଵ • Sử dụng công thức|ܣ ∪ ܤ|ൌ|ܣ|൅|ܤ|െ|ܣ תܤ| ta suy ra số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 chứa ít nhất 5 bi, đồng thời hộp 2 hay hộp 3 chứa ít nhất 7 bi làܭହଵ଼൅ ܭହଵ଼െ ܭହଵଵൌܥଶଶଵ଼൅ ܥଶଶଵ଼െ ܥଵହଵଵൌ13265 GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌC Biên soạn : Gv. Phạm Phúc Thịnh Trang 22 Chương 3 : QUAN HỆ I. Quan hệ hai ngôi 1. Định nghĩa Cho một tập hợp X khác rỗng. Một quan hệ 2 ngôi trên X là một tập hợp con R của X2. Cho 2 phần tử x và y của X, ta nói x có quan hệ R với y khi và chỉ khi (x,y) ∈ R, và viết là x R y. Như vậy:x R y ⇔ (x,y) ∈ R; Khi x không có quan hệ R với y, ta viết: x ࡾഥy. Ví dụ: Trên tập hợp X = { 1,2,3,4} , xét quan hệ 2 ngôi R được định nghĩa bởi:R = { (1,1), (1,3), (2,2), (2,4), (3,1), (3,3), (4,2), (4,4)}Với quan hệ nầy ta có: 2 R 4, nhưng 2 ࡾഥ3. Trên tập hợp các số nguyên Z ta định nghĩa một quan hệ 2 ngôi R như sau:x R y nếu và chỉ nếu x-y là số chẳn.hay nói cách khác:R = { (x,y) ∈ Z2 x-y = 2k với k ∈ Z } Quan hệ R nầy chính là quan hệ đồng dư modulo 2. Ghi chú : Người ta còn định nghĩa một quan hệ (2 ngôi) giữa một tập hợp A và một tập hợp B là một tập hợp con của AxB. Ví dụ: A = { 1, 2, 3, 4, 5} , B = { 0, 1} . Ta có R = { (1,1), (2,0), (3,1), (4,0), (5,0)} là một quan hệ giữa A và B. Tổng quát hơn, ta có thể định nghĩa một quan hệ giữa các tập hợp A1, A2, . . ., An là một tập hợp con của A1 x A2 x . . . x An (tích Descartes của các tập hợp A1, A2, . . ., An). Như vậy, khi R là một quan hệ giữa các tập A1, A2, . . ., An thì mỗi phần tử của R là một bộ n (a1, a2, . . ., an) với ai∈ Ai (i=1, …, n). 2. Cách xác định một quan hệ: Dựa vào các phương pháp xác định một tập hợp, ta có thể xác định một quan hệ bằng các phương pháp sau đây: a. Liệt kê: Liệt kê tất cả các cặp hay bộ phần tử có quan hệ R (tức là thuộc R). b. Nêu tính chất đặc trưng cho quan hệ R : Nêu tính chất hay tiêu chuẩn để xác định các phần tử thuộc R hay không. c. Các tính chất của quan hệ 2 ngôi Giả sử R là một quan hệ 2 ngôi trên một tập hợp X • Tính phản xạ Quan hệ R có tính phản xạ nếu và chỉ nếu x R x với mọi x ∈ X. • Tính đối xứng Quan hệ R có tính đối xứng nếu và chỉ nếu x R y ⇒ y R x với mọi x,y ∈ X. • Tính phản xứng Quan hệ R có tính phản xứng nếu và chỉ nếu (x R y và y R x) ⇒ x = y với mọi x,y ∈ X. • Tính bắc cầu Quan hệ R có tính truyền hay bắc cầu nếu và chỉ nếu (x R y và y R z) ⇒ x R z với mọi x,y,z ∈ X. 3. Biểu diễn quan hệ 2 ngôi dưới dạng ma trận Giả sử R là một quan hệ 2 ngôi giữa một tập hợp hữu hạn A = { a1, a2, , am} và một tập hữu hạn B = { b1, b2, , bm} . Quan hệ R có thể được biểu diễn bởi ma trận MR = GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌC Biên soạn : Gv. Phạm Phúc Thịnh Trang 23 [mij] gồm m dòng và n cột (tức là ma trận cấp mxn), trong đó mij = 1 nếu (ai, bj) ∈ Rmij = 0 nếu (ai, bj) ∉ RTa gọi ma trận MR là ma trận biểu diễn của quan hệ R. Ví dụ: Với A = { 1,2,3} và B = { a, b, c} , thì các quan hệ sau đây: R = { (1,a), (1,b), (1,c)} S = { (1,a), (1,b), (1,c), (2,b), (2,c), (3,c)} có các ma trận biểu diễn là MR =൥૚ ૚ ૚૙ ૙ ૙૙ ૙ ૙൩ MS =൥૚ ૚ ૚૚ ૚ ૙૙ ૙ ૚൩ Trong trường hợp R là một quan hệ 2 ngôi trên một tập X hữu hạn và có n phần tử thì ma trận biểu diễn của R là một ma trận có n dòng và n cột (tức là ma trận vuông cấp n). Ghi chú: Ngoài cách biểu diễn quan hệ dưới dạng ma trận ta còn biểu đồ (dạng đồ thị) để biểu diễn quan hệ. Cách biểu diễn nầy sẽ được xét đến trong phần sau, khi nói về biểu đồ Hasse của một cấu trúc thứ tự. II. Quan hệ tương đương 1. Khái niệm Một quan hệ 2 ngôi R trên một tập hợp X được gọi là một quan hệ tương đương nếu và chỉ nếu nó thỏa 3 tính chất: phản xạ, đối xứng, truyền. Ví dụ: Quan hệ đồng dư modulo n trên Z. Ta đã biết quan hệ nầy có 3 tính chất phản xạ, đối xứng, truyền. Quan hệ ≤ trên Z không phải là một quan hệ tương đương vì nó không có tính chất đối xứng. 2. Lớp tương đương và tập hợp thương Với mỗi phần tử x∈ X, ta định nghĩa lớp tương đương chứa x, ký hiệuxത , là tập hợp tất cả những phần tử (thuộc X) có quan hệ R với x:xത= { y ∈ X : y R x } Như vậy mỗi lớp tương đương là một tập hợp con của X. Tập hợp các lớp tương đương của quan hệ tương đương R trên X tạo thành một "phân hoạch" của tập hợp X, tức là tập các lớp tương đương khác nhau cho ta một họ các tập con của X rời nhau đôi một và có phần hội bằng X. Tập hợp các lớp tương đương của quan hệ tương đương R trên Xnầy (là một tập con của P(X)) được gọi là tập hợp thương (của quan hệ tương đương R trên X). Ví dụ Quan hệ đồng dư modulo n trên Z có tập hợp thương tương ứng, được ký hiệu là Zn, gồm n phần tử :Zn = {1ത; 2ത; 3ത… ;n െ 1തതതതതതതሽ trong đó kത(k∈Z) là tập hợp tất cả những số nguyên đồng dư với k modulo n. 3. Đồng dư a. Định nghĩa Cho n là một số nguyên dương. Ta nói 2 số nguyên a và b đồng dư modulo n nếu các số dư trong phép chia a cho n và chia b cho n bằng nhau. Trong trường hợp nầy ta cũng nói là a đồng dư với b modulo n, và viết:a ≡ b (mod n). Như vậy, theo định nghĩa ta có:a ≡ b (mod n) ⇔ a mod n = b mod n. b. Các định lý • Định lý 1: Cho n là một số nguyên dương, a và b là 2 số nguyên tùy ý. Ta có các phát biểu sau đây là tương đương: a ≡ b (mod n) GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌC Biên soạn : Gv. Phạm Phúc Thịnh Trang 24 n (a-b) (n chia hết hiệu a và b) tồn tại một số nguyên k sao cho a = b + k.n • Định lý 2. Cho n là một số nguyên dương. Giả sử a ≡ b (mod n) và c ≡ d (mod n). Khi đó ta có : a ± c ≡ b ± d (mod n) a.c ≡ b.d (mod n) • Hệ quả : Nếu a ≡ b (mod n) thì k.a ≡ k.b (mod n) với mọi số nguyên k. Nếu a ≡ b (mod n) thì ak ≡ bk (mod n) với mọi số nguyên dương k. • Định lý 3. (Fermat) Cho p là một số nguyên tố và a là một số nguyên không phải là bội số của p. Khi đó ta có hệ thức sau:ap-1≡ 1 (mod p) III. Phép toán số học trên Zn 1. Tập hợp số tự nhiên, tập hợp số nguyên Ta dùng ký hiệu N để chỉ tập hợp các số tự nhiên, tức là tập hợp các số nguyên không âm. Tập hợp các số nguyên sẽ được ký hiệu là Z. Chúng ta biết rằng trên các tập hợp N và Z có hai phép toán cơ sở: phép cộng (+) và phép nhân (.) thỏa một số tính chất thông thường: • a + b = b + a • (a+b)+c = a+(b+c) • a+0 = a • với mọi số nguyên a, có duy nhất một số nguyên được ký hiệu là -a thỏa:a + (-a) = 0 • a.b = b.a • (a.b).c = a.(b.c) • a.1 = a • a.(b+c) = a.b + a.c Trong các tính chất trên các ký hiệu a, b, c là các số tự nhiên hay các số nguyên tùy ý. Từ tính chất (4), trong tập hợp các số nguyên Z ta có một phép toán trừ được định nghĩa như sau : a - b = a + (-b). Ngoài các tính chất nêu trên các tập hợp N và Z còn là những tập hợp có thứ tự và đếm được. Quan hệ thứ tự trên N và Z được ký hiệu bởi ≤ (đọc là: "nhỏ hơn hoặc bằng"). Ngoài ra chúng ta còn dùng một số ký hiệu so sánh khác rất quen thuộc như: "≥ ", "<", ">", "=", "≠ ". Thứ tự "≤ " trên tập số tự nhiên N có một tính chất rất quan trọng được phát biểu trong định lý dưới đây: Định lý. Mọi tập hợp con khác rỗng của tập hợp các số tự nhiên N đều có duy nhất một tử nhỏ nhất. 2. Phép chia số nguyên a. Định lý.(Thuật chia Euclide) Cho a là một số nguyên bất kỳ và b là một số nguyên khác 0. Khi đó, có duy nhất 2 số nguyên q, r thỏa mãn các điều kiện: (1) a = b.q + r (2) 0 ≤ r < | b |. Số q trong định lý trên được gọi là thương số của phép chia a cho b; và r được gọi là dư số (hay số dư). Thương số trong phép chia a cho b thường được viết dưới dạng: a div b, và ký hiệu "div" được dùng để chỉ phép toán chia lấy thương số. Dư số trong phép chia a cho b được viết là: a mod b. b. Các định nghĩa về sự “chia hết”, “chia hết cho”, “ước số", "bội số", "ước số chung lớn nhất". GIÁO TRÌNH TOÁN ỨNG DỤNG TIN HỌ • Ta nói một số nguysố dư trong phép chia a cho b bhết cho số nguyq.b. Trong trường hKhi a chia hết cho b, ta cb  a (đọc là: "b chia h• Ta nói một số nguysố nguyên q thỏchỉ rằng “a là bsố của a", và sử dc. Các mệnh đề về sựchung lớn nhất".• Mệnh đề 1: Sự chia ha a với mọNếu a b và b Như vậy trong trường hợp a vthể kết luận a = b. Nếu a b và b c thì a• Mệnh đề 2: Cho a, b, c, d là các sa 0 1 a Nếu a b và cNếu a b và a• Hệ quả. Từ các tính chdàng suy ra các hNếu a b thNếu a b thì an3. Ước Số Chung Lớn Nhấa. Định nghĩa: (ước sCho a và b là 2 số nguyb (tức là số nguyên vừa là ưnhất của a và b nếu ước số chung d nNhư vậy, ước số chung lđây: • d a và d b• Nếu d’ a, d’b. Nhận xét : Ta có số 1 là một ưhoặc bằng | a |. Do đó tập hợrỗng các số nguyên. Suy ra U có duy nhước số chung lớn nhất của 2 sdương, và duy nhất. Ta ký hiệNếu m ≠ 0 thì (m,0) = |m|.c. Ghi chú : Trong đại số, người ta là một số nguyên d thỏa mãn 2 NG TIN HỌC Biên soố nguyên a chia hết cho một số nguyên b (b trong phép chia a cho b bằng 0. Nói một cách khác, s nguyên b (b ≠ 0) khi và chỉ khi có một số nguyờng hợp nầy ta viết: (đọc là: "a chia hết cho b").ết cho b, ta cũng có thể nói rằng "b chia hết a" và vià: "b chia hết a"). ố nguyên a làbội số của một số nguyên b khi và chỏa điều kiện: a = q.b. Ở đây ta vẫn dùng cách vià bội số của b". Trong trường hợp nầy ta cũng nói rử dụng cách viết "b  a". ề sự “chia hết”, “chia hết cho”, “ước số", "bt". ự chia hết có các tính chất sau đây: i mọi số nguyên a. b và b a thì | a | = | b |. ợp a và b là các số tự nhiên, thì từ điều kiện ac thì a c. Cho a, b, c, d là các số nguyên tùy ý. Ta có các tính chb và c d thì (a.c) (b.d) b và a c thì a (b ± c). ừ các tính chất được phát biểu trong mệnh đề trdàng suy ra các hệ quả sau đây: b thì a (b.c) b thì an bn, với mọi số nguyên dương n. n Nhất và Bội Số Chung Nhỏ Nhất ớc số chung lớn nhất dương) ố nguyên không đồng thời bằng 0. Một ước sà ước số của a vừa là ước số của b) được gọi lố chung d nầy lớn hơn mọi ước số chung khác cố chung lớn nhất d của a và b được đặc trưng bb a, d’ b, và d’≠ d thì d’ < d. ước số chung của a và b; và mọi ước số chung ập hợp U gồm các ước số chung của a và b là mên. Suy ra U có duy nhất một phần tử lớn nhất. Điềủa 2 số nguyên a và b (a, b không đồng tht. Ta ký hiệu ước số chung lớn nhất của a và b là: (a,b).0 thì (m,0) = |m|. ời ta định nghĩa ước số chung lớn nhất của 2 sãn 2 điều kiện: Biên soạn : Gv. Phạm Phúc Thịnh Trang 25ên b (b ≠ 0) khi và chỉ khi t cách khác, số nguyên a chia ố nguyên q sao cho a = ết cho b"). a" và viết: ên b khi và chỉ khi có một dùng cách viết " " để ũng nói rằng "b là ước ", "bội số", "ước số u kiện a b và b a ta có ên tùy ý. Ta có các tính chất sau: đề trên chúng ta dễ ớc số chung d của a và ọi là ước số chung lớn chung khác của a và b. ưng bởi 2 điều kiện sau c số chung đều nhỏ hơn à b là một tập hợp khác ều nầy chứng tỏ rằng ồng thời bằng 0) tồn tại, à b là: (a,b). ủa 2 số nguyên a và b