Bài giảng Toán ứng dụng tin học - Phạm Phúc Thịnh

3/5/2009 1 Phạm Phúc Thịnh PHẦN MỞ ĐẦU Các kiến thức sẽ học 1. Cơ Sở Logic a) Mệnh đề & chân trị b) Các phép toán mệnh đề c) Dạng mệnh đề & Luật logic d) Quy tắc suy diễn e) Vị từ & lượng từ f) Tập hợp – Các phép toán tập hợp g) Quy nạp toán học – Định nghĩa đệ quy Các kiến thức sẽ học 2. Phép đếm a) Định nghĩa – tính chất cơ bản. b) Nguyễn lý cộng - nguyên lý nhân c) Nguyên lý Chuồng bồ câu d) Chỉnh hợp – Tổ hợp. Công thức nhị thức e) Tổ hợp có lặp 3. Quan hệ a) Quan hệ & Các tính chất b) Biễu diễn quan hệ c) Quan hệ tương đương – Đồng dư. d) Quan hệ thứ tự Các kiến thức sẽ học 4. Đại số Bool a) Hàm Bool. Dạng nối rời chính tắc b) Công thức đa thức tối tiểu c) Phương pháp biểu đồ Karnaugh d) Mạng các cổng Thời gian học tập Tổng số tiết : 45 (Bao gồm lý thuyết + bài tập a) Lý thuyết : 30 tiết b) Bài tập : 14 tiết c) Kiểm tra : 1 tiết
Mục tiêu của học phần: Nhằm trang bị cho sinh viên những kiến thức cơ bản về Logic, Lý thuyết tập hợp, Các nguyên lý đếm, Quan hệ, và Hàm Bool.
Tài liệu tham khảo: -Các giáo trình toán rời rạc của bậc học Cao đẳng (Có thể tìm thấy trong thư viện hoặc trên mạng Internet) -- Bài giảng của giáo viên quan trang blog : Chuottau.blogtiengviet.net 3/5/2009 2 CHƯƠNG 1 PHẦN 1 Khái niệm mệnh đề và chân trị
Các đối tượng cơ bản mà chúng ta khảo sát ở đây là các phát biểu hay các mệnh đề.Tuy nhiên, ta chỉ xét đến các mệnh đề toán học, và chúng ta nói vắn tắt các mệnh đề toán học là các mệnh đề.
Mệnh đề toán học là những 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. Khái niệm mệnh đề và chân trị
Tính chất cơ bản 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 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. Các ví dụ về mệnh đề 1. 6 là một số nguyên tố. 2. 5 là một số nguyên tố. 3. -3 < 2 4. Tam giác cân có hai góc bằng nhau. 5. H2O là một axít.
Các mệnh đề 2, 3, và 4 trong ví dụ trên là những mệnh đề đúng.
Các mệnh đề 1, 5 là những mệnh đề sai. Các ví dụ về mệnh đề
Các phát biểu sau đây không phải là các mệnh đề (toán học) vì tính đúng sai của chúng không xác định. 1. Ai đang đọc sách? (một câu hỏi) 2. Hãy đóng cửa lại đi! 3. Anh ta rất thông minh. 4. Cho x là một số nguyên dương. 5. a là một số chính phương. 6. x + y = z. 3/5/2009 3 Mệnh đề sơ cấp – Mệnh đề phức hợp
Phân loại mệnh đề : mệnh đề sơ cấp (elementary), mệnh đề phức hợp (compound).
Mệnh đề sơ cấp là các mệnh đề không thể phân tích được 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.... Ví dụ về phân loại mệnh đề 1. p = “15 chia hết cho 3”. 2. q = “2 là một số nguyên tố và là một số lẻ”.
Ta có p là một mệnh đề sơ cấp. Nhưng q là một mệnh đề phức hợp, vì mệnh đề q được tạo thành từ hai mệnh đề “2 là một số nguyên tố” và “2 là một số lẻ” nhờ vào liên kết logic “và”. PHẦN 2 Bảng chân trị của một mệnh đề
V
n đ : làm thế nào để tính toán chân trị của các mệnh đề phức hợp theo các mệnh đề sơ cấp cấu thành mệnh đề phức hợp đó nhờ vào các phép toán logic.
Các phép toán logic là các ký hiệu được dùng thay cho các từ liên kết logic như “không”, “và”, “hay”, “hoặc”, “suy ra” hay “nếu ... thì ...”, “nếu và chỉ nếu”. Bảng chân trị của một mệnh đề
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ị cho ta 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.
Bảng chân trị được dùng với mục đích : 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. Phép Phủ định
Cho p là một mệnh đề, 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
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/5/2009 4 Phép Phủ định
Ví dụ 1 : Nếu ta ký hiệu p là mệnh đề “5 < 3” thì ¬p là ký hiệu cho mệnh đề “5 ≥ 3”. Trong trường hợp nầy p sai, ¬ p đúng. Ta có thể viết p = 0, ¬ p = 1. Phép Phủ định p ¬ p ¬ (¬ p) 0 1 0 1 0 1
Ví dụ 2 : Chỉ ra rằng ¬(¬p) và p luôn có cùng chân trị. Giải. Lập bảng chân trị của mệnh đề ¬(¬ p): Trên mỗi dòng giá trị trong bảng chân trị ta có chân trị của p và ¬(¬p) đều bằng nhau (so sánh cột 1 và cột 3 trong bảng). Vậy ¬(¬p) và p có cùng chân trị. Ta cũng nói rằng ¬(¬p) tương đương logic với p. Mệnh đề ¬(¬p) thường được viết là ¬¬p. 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 1 0 0 1 1 1 Phép Hội
Qua định nghĩa trên ta nhận thấy rằng các mệnh đề p Λ q và q Λ p luôn luôn có cùng chân trị, hay tương đương logic. Tuy nhiên, trong ngôn ngữ thông thường các mệnh đề “p và q” và “q và p” đôi khi có ý nghĩa khác nhau theo ngữ cảnh. Ví d: Cho các mệnh đề p = “5 > -7”, q = “2721 là một số nguyên tố”, r = “một tam giác đều cũng là một tam giác cân”. Khi đó ta có : p Λ q = 0 (p Λ q sai, tức là có chân trị bằng 0, vì p = 1 và q = 0), p Λ r = 1 (p Λ r đúng, tức là có chân trị bằng 1, vì p = 1 và r = 1). Phép Hội
Nhận xét: Bằng cách lập bảng chân trị, ta có: 1. Các mệnh đề p và p Λ p luôn có cùng chân trị. 2. Mệnh đề p Λ¬ p luôn có chân trị bằng 0 (tức là một mệnh đề luôn sai). 3. Một mệnh đề phức hợp luôn luôn có chân trị là sai trong mọi trường hợp chân trị của các mệnh đề sơ cấp tạo thành nó sẽ được gọi là một sự mâu thuẩn. Phép Tuyển
Cho p và q là hai mệnh đề. Ta ký hiệu mệnh đề “p hay q” là p ∨ q. Phép “hay”, 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 1 1 0 1 1 1 1 3/5/2009 5 Phép Tuyển
Chân trị của mệnh đề p ∨ q phụ thuộc vào các chân trị của 2 mệnh đề p, q. Trong 4 trường hợp chỉ có một trường hợp mệnh đề p ∨ q sai, đó là trường hợp p sai và q sai.
Qua định nghĩa trên ta nhận thấy rằng các mệnh đề p ∨ q và q ∨ p luôn luôn có cùng chân trị, hay tương đương logic. Phép Tuyển Ví dụ : Cho các mệnh đề • p = “5 > 7”, • q = “2721 là một số nguyên tố”, • r = “một tam giác đều cũng là một tam giác cân”. Khi đó ta có : p V q = 0, p V r = 1. Phép Tuyển Nhận xét : 1. Cho p là một mệnh đề. Lập bảng chân trị của mệnh đề p ∨¬ p ta có mệnh đề p ∨¬ p luôn luôn đúng. p ¬ p p∨¬ p 0 1 1 1 0 1 Phép Kéo theo Phép kéo theo, ký hiệu bởi → , được đưa ra để mô hình cho loại phát biểu điều kiện có dạng : “nếu . . . thì . . .”. Cho p và q là 2 mệnh đề, ta sẽ viết p→ q để diễn đạt phát biểu “nếu p thì q”. Phép toán kéo theo → được định nghĩa bởi bảng chân trị sau đây: p q p
q 0 0 1 0 1 1 p q p
q 1 0 0 1 1 1 Phép Kéo theo Mệnh đề p → q, được đọc là “nếu p thì q”, còn được phát biểu dưới các dạng khác sau đây: ”q nếu p”. ”p chỉ nếu q”. ”p là điều kiện đủ cho q”. ”q là điều kiện cần cho p”. Phép Kéo theo 2 chiều Phép kéo theo 2 chiều hay phép tương đương, ký hiệu bởi ↔, được đưa ra để mô hình cho loại phát biểu điều kiện hai chiều có dạng : “. . . nếu và chỉ nếu . . .”. Cho p và q là 2 mệnh đề, ta viết p↔q để diễn đạt phát biểu “p nếu và chỉ nếu q”. Phép toán tương đương được định nghĩa bởi bảng chân trị sau đây p q p ↔q 0 0 1 0 1 0 p q p ↔q 1 0 0 1 1 1 3/5/2009 6 Phép Kéo theo 2 chiều Mệnh đề p↔ q, được đọc là “p nếu và chỉ nếu q”, còn được phát biểu dưới các dạng khác sau đây: ”p khi và chỉ khi q”. ”p là điều kiện cần và đủ cho q”. Mệnh đề p↔q có chân trị đúng (=1) trong các trường hợp p và q có cùng chân trị. Độ ưu tiên của các toán tử Logic Tương tự như đối với các phép toán số học, để tránh phải dùng nhiều dấu ngoặc trong các biểu thức logic, ta đưa ra một thứ tự ưu tiên trong việc tính toán. Ở trên ta có 5 toán tử logic:¬ (không) , ∧ (và), ∨ (hay), → (kéo theo), ↔ ( tương đương) Thứ tự ưu tiên : ¬ ∧ , ∨ → ↔ trong đó, các toán tử liệt kê trên cùng dòng có cùng độ ưu tiên. Độ ưu tiên của các toán tử Logic Ví dụ : 1. ¬ p∨q có nghĩa là ((¬ p) ∨ q). 2. ¬ p∨ q→ r ∧ s có nghĩa là (((¬ p) ∨ q)→ (r ∧ s)). 3. ¬ p∨ q∧ r là không rõ ràng, trong trường hợp này cần phải dùng các dấu ngoặc để chỉ rõ nghĩa. PHẦN 2 Định nghĩa biểu thức Logic Biểu thức logic là biểu thức được xây dựng từ : 1. Các mệnh đề hay các giá trị hằng. 2. Các biến mệnh đề. 3. Các phép toán logic, và cả các dấu ngoặc “( )” để chỉ rõ thứ tự thực hiện của các phép toán. Giả sử E, F là 2 biểu thức logic, khi ấy ¬ E, E ∧ F, E → F, E ↔ F cũng là các biểu thức logic. Ví dụ: Biểu thức E(p,q,r) = (((¬ p) ∨ q)→ (r ∧ s)) là một biểu thức logic trong đó p, q, r là các biến mệnh đề. Bảng chân trị của biểu thức Logic  Bảng chân trị của một biểu thức logic là bảng liệt kê chân trị của biểu thức logic theo các trường hợp về chân trị của tất cả các biến mệnh đề trong biểu thức logic hay theo các bộ giá trị của bộ biến mệnh đề.  Với một biến mệnh đề, ta có 2 trường hợp là 0 (sai) hoặc 1 (đúng). Với 2 biến mệnh đề p, q ta 4 trường hợp chân trị của bộ biến (p,q) là các bộ giá trị (0,0), (0,1), (1,0), và (1,1).  Trong trường hợp tổng quát, với n biến mệnh đề thì ta có 2n trường hợp chân trị cho bộ n biến đó. 3/5/2009 7 Bảng chân trị của biểu thức Logic Ví dụ 1: Bảng chân trị của các biểu thức logic p→ q và ¬ p ∨ q theo các biến mệnh đề p,q như sau: p 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 Bảng chân trị của biểu thức Logic Ví dụ 2: Bảng chân trị của các biểu thức logic p ∨ ( q ∧ r) theo các biến mệnh đề p, q, r như sau: p q r q ∧ r p ∨ ( q ∧ r) 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 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.  Ví d: từ bảng chân trị của các biểu thức logic p → q và ¬ p∨q theo các biến mệnh đề p, q ta có: p → q ⇔ ¬ p∨q Biểu thức hằng đúng, 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.  Như vậy, 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. Biểu thức hằng đúng, hằng sai  Ví dụ: Biểu thức p ∧ ¬ p là hằng sai. Biểu thức là p → q ↔ ¬ p∨ q là hằng đúng.  Lu ý: 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). PHẦN 3 3/5/2009 8 Luật Logic là gì ?  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 nhằm 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.  Các luật nầy có thể được suy ra trực tiếp từ các bảng chân trị của các biểu thức logic. Các Luật Logic  Luật về phép phủ định  ¬ ¬ p ⇔ p (luật phủ định của phủ định)  ¬ 1 ⇔ 0  ¬ 0 ⇔ 1  Luật giao hoán  p ∧ q ⇔ q ∧ p  p ∨ q ⇔ q ∨ p  Luật kết hợp  p ∧ (q ∧ r) ⇔ (p ∧ q) ∧ r  p ∨ (q ∨ r) ⇔ (p ∨ q) ∨ r Các Luật Logic  Luật phân bố  p ∧ (q ∨ r) ⇔ (p ∨ q) ∧ (p ∨ r)  p ∨ (q ∧ r) ⇔ (p ∧ q) ∨ (p ∧ r)  Luật De Morgan  ¬ (p ∧ q) ⇔ ¬ p ∨ ¬ q  ¬ (p ∨ q) ⇔ ¬ p ∧ ¬ q  Luật về phần tử bù  p ∨ ¬ p ⇔ 1  p ∧ ¬ p ⇔ 0 Các Luật Logic  Luật kéo theo  p ∧ (q ∨ r) ⇔ (p ∨ q) ∧ (p ∨ r)  p ∨ (q ∧ r) ⇔ (p ∧ q) ∨ (p ∧ r)  Luật tương đương  ¬ (p ∧ q) ⇔ ¬ p ∨ ¬ q  ¬ (p ∨ q) ⇔ ¬ p ∧ ¬ q Các Luật của phép Hội  p ∨ p ⇔ p (tính lũy đẳng)  p ∨ 1 ⇔ 1 (Luật thống trị)  p ∨ 0 ⇔ p (Luật trung hòa)  p ∨ (p ∧ q) ⇔ p (Luật hấp thụ) Các Luật của phép Hội  p ∧ p ⇔ p (tính lũy đẳng)  p ∧ 1 ⇔ p (Luật trung hòa)  p ∨ 0 ⇔ 0 (Luật thống trị)  p ∧ (p ∨ q) ⇔ p (Luật hấp thụ) 3/5/2009 9 PHẦN 4 Các quy tắc thay thế 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. Ví dụ: Cho biểu thức logic E = q ∨¬ p. Thay thế q trong biểu thức E bởi biểu thức ¬ ¬ q (tương đương với q) ta được một biểu thức mới E' = ¬ ¬ q ∨¬ p. Theo qui tắc thay thế 1 ta có: q ∨ ¬ p ⇔ ¬ ¬ q ∨ ¬ p Các quy tắc thay thế 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. Ví dụ: Ta có biểu thức E(p,q) = (p → q) ↔ ( ¬ p ∨ q) là một hằng đúng. Thay thế biến q trong biểu thức E bởi biểu thức q ∧ r ta được biểu thức logic mới: E’(p,q,r) = (p → (q ∧ r)) ↔ ( ¬ p ∨ (q ∧ r)) Theo qui tắc thay thế 2 ta có biểu thức E’(p,q,r) cũng là một hằng đúng. Các ví dụ quy tắc thay thế Ví dụ 1: Chứng minh rằng (p → q) ⇔ (¬ q → ¬ p) Giải : Ta có (p → q) ⇔ (¬ p ∨ q) (luật kéo theo) ⇔ (q ∨ ¬ p) (luật giao hoán) ⇔ (¬ ¬ q ∨ ¬ p) (luật phủ định) ⇔ (¬ q
¬ p) (luật kéo theo) Bài tập nhỏ: hãy chứng minh a) ((p → q) ∧ p) → q là một hằng đúng. b) p ∧ q → p là một hằng đúng. c) p → p ∨ q là một hằng đúng