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

Chia sẻ: Ngo DUC HAI | Ngày: | Loại File: DOC | Số trang:120

Thêm vào BST

Báo xấu

1.545
lượt xem 515
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Giáo trình môn toán rời rạc đào tạo ở trường kinh tế quốc dân. Các quy tắc của logic cho ý nghĩa chính xác của các mệnh đề. Các quy tắc này dùng được sử dụng để phân biệt giữa các lập luận toán học đúng hoặc không đúng.

Chủ đề:

Bình luận(1) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình môn toán rời rạc

Giáo trình Toán rời rạc
MỤC LỤC A..................................................................................................................................................................... 97 B..................................................................................................................................................................... 97 C..................................................................................................................................................................... 97 D..................................................................................................................................................................... 97 E..................................................................................................................................................................... 97 F..................................................................................................................................................................... 97 H..................................................................................................................................................................... 97 I...................................................................................................................................................................... 97
CHƯƠNG 1. LÝ THUYẾT CƠ SỞ BÀI 1: LOGIC VÀ MỆNH ĐỀ 1. Mở đầu: - Các quy tắc của logic cho ý nghĩa chính xác của các mệnh đề. Các quy tắc này dùng đ ược s ử dụng để phân biệt giữa các lập luận toán học đúng hoặc không đúng. - Các quy tắc của logic đóng vai trò quan trọng trong suy luận toán học và nhiều ứng dụng trong lĩnh vực tin học như: thiết kế các mạng trong máy tính, xây dựng các chương trình máy tính, kiểm tra tính đúng đắn của các chương trình và nhiều ứng dụng khác. 2. Mệnh đề: • Khái niệm: Một mệnh đề là một câu trần thuật đúng hoặc sai, chứ không thể vừa đúng vừa sai. • Ví dụ: + Ví dụ 1: Xét các câu sau: 1. Hà nội là thủ đô của Việt nam 2. Việt trì là một thành phố biển. 3. 1 + 1 = 2 4. 2 + 4 = 5 Các câu 1 và 3 là đúng, trong khi các câu 2 và 4 là sai và như vậy c ả 4 câu trên là các m ệnh đề. + Ví dụ 2: Xét các câu sau: 1. Hôm nay là thứ mấy? 2. Vấn đề này cần được xem xét cẩn thận. 3. x + 1 = 2 4. x + y = z Các câu 1 và 2 không phải là mệnh đề vì chúng không phải là câu trần thuật. Còn các câu 3 và 4 không phải là mệnh đề vì chúng chẳng đúng cũng chẳng sai bởi các biến trong các câu đó còn chưa được gán cho giá trị cụ thể nào. Từ các câu loại này có thể tạo thành các mệnh đề bằng nhiều cách khác nhau (xem phần sau của chương này). • Phân loại mệnh đề: - Mệnh đề đơn (sơ cấp): Là những mệnh đề chỉ có một câu. - Mệnh đề phức hợp: Là những mệnh đề được kết hợp từ nhiều mệnh đề. • Quy ước: - Các mệnh đề và các biến được ký hiệu bởi các chữ cái như: p,q,r,s,...
- Giá trị chân lý của một mệnh đề là đúng và sẽ được ký hiệu là T nếu đó là một mệnh đ ề đúng, và là sai và được ký hiệu là F, nếu đó là một mệnh đề sai. - Một bảng chân lý trình bày mối quan hệ giữa các giá trị chân lý của các mệnh đ ề. Bảng giá trị chân lý đặc biệt có ý nghĩa trong việc xác định giá trị chân lý của các mệnh đề được tạo ra từ các mệnh đề đơn giản hơn. 3. Các định nghĩa phép toán mệnh đề: Phép toán mệnh đề là phương pháp tạo ra các mệnh đề mới từ các mệnh đề đã có – Geogre Boole “Các định luật của tư duy”. + Định nghĩa 1: Giả sử p là một mệnh đề. Câu “không phải là p” là một mệnh đề, được gọi là phủ định của p. Phủ định của p được ký hiệu là ¬p (hoặc p ) - Bảng chân lý: p ¬p T F F T - Ví dụ: Tìm phủ định của mệnh đề: “Hôm nay là chủ nhật”. Phủ định của mệnh đề trên là: “Hôm nay không phải là chủ nhật”. Phủ định của một mệnh đề cũng có thể được xem như là kết quả tác dụng của toán tử phủ định lên một mệnh đề. Toán tử phủ định xây dựng một mệnh mới từ mệnh đề đơn hiện có. + Định nghĩa 2: Giả sử p và q là hai mệnh đề. Mệnh đề “p và q” được ký hiệu bởi p ^ q là đúng khi cả p và q là đúng, còn sai trong các trường hợp còn lại. Mệnh đề p ^ q được gọi là hội của p và q. - Bảng chân lý: p Q p^q T T T T F F F T F F F F - Ví dụ: Giả sử p là mệnh đề “Hôm nay là chủ nhật” và q là mệnh đề “Hôm nay trời mưa”. Tìm hội của các mệnh đề p và q. Giải: Hội của hai mệnh đề p ^ q là mệnh đề “Hôm nay là chủ nhật và trời mưa”. Mệnh đề này là đúng vào hôm chủ nhật trời mưa và là sai vào bất kỳ ngày nào không phải là chủ nhật và vào ngày chủ nhật nhưng trời không mưa. + Định nghĩa 3: Giả sử p và q là hai mệnh đề. Mệnh đề “p hoặc q”, được ký hiệu là p ۷ q, là mệnh sai khi cả p và q đều sai, và đúng trong các trường hợp còn lại ( có nghĩa là hoặc q là đúng, hoặc q là đúng, hoặc cả p và q cùng đúng). Mệnh đề p ۷ q được gọi là tuyển của p và q. - Bảng chân lý:
p Q pvq T T T T F T F T T F F F - Ví dụ 1: Giả sử p là mệnh đề “Hôm nay là chủ nhật” và q là mệnh đề “Hôm nay trời mưa”. Tìm tuyển của các mệnh đề p và q. Giải: Tuyển của p và q (p ۷ q) là mệnh đề: “Hôm nay là chủ nhật hoặc hôm nay trời mưa”. Mệnh đề này đúng vào bất kỳ ngày nào là chủ nhật hoặc ngày trời mưa (kể cả ngày chủ nhật có mưa). Nó chỉ sai khi ngày đó không phải là ngày chủ nhật và trời không mưa. - Ví dụ 2: Giả sử p là mệnh đề “Các sinh viên đã học giải tích có thể theo học lớp này.” và q là mệnh đề “Các sinh viên đã học đại số có thể theo học lớp này.”. Tìm tuyển của các mệnh đề p và q. Giải: Tuyển của p và q (p ۷ q) là mệnh đề: “Các sinh viên đã học giải tích hoặc đại số có thể theo học lớp này.” Mệnh đề trên còn có thể hiểu: “Các sinh viên đã học giải tích hoặc đại số, nhưng không phải cả hai môn, đều có thể theo học lớp này.” Ở đây, người ta muốn nói rằng + Định nghĩa 4: Giả sử p và q là hai mệnh đề. Mệnh đề tuyển loại trừ của p và q, ký hiệu là p ⊕ q là một mệnh đề chỉ đúng khi một trong hai mệnh đề p và q là đúng và sai trong mọi trường hợp còn lại (mệnh đề p ⊕ q chỉ đúng trong trường hợp p hoặc q là đúng). - Bảng chân lý: p Q p⊕ q T T F T F T F T T F F F - Ví dụ: Giả sử p là mệnh đề “Tôi sẽ mua một chiếc máy tính để bàn.” và q là mệnh đ ề “Tôi sẽ mua một chiếc máy tính sách tay.”. Tìm tuyển loại trừ của các mệnh đề p và q. Giải: Mệnh đề tuyển loại trừ của p và q (p ⊕ q) là mệnh đề: “Tôi sẽ mua một chiếc máy tính để bàn hoặc sách tay.”. Mệnh đề trên có nghĩa là: “Tôi sẽ mua một chiếc máy tính để bàn hoặc sách tay nhưng không phải mua cả hai.”
+ Định nghĩa 5: Giả sử p và q là hai mệnh đề. Mệnh đề kéo theo “p → q” là một mệnh đ ề ch ỉ sai khi p đúng và q sai, còn đúng trong mọi trường hợp còn lại. Trong phép kéo theo nói trên p được gọi là giả thuyết còn q được gọi là kết luận. - Bảng chân lý: p q p→q T T T T F F F T T F F T - Ví dụ: Giả sử p là mệnh đề “Hôm nay là thứ ba.” và q là mệnh đề “Hôm nay học toán r ời rạc.”. Tìm mệnh đề p kéo theo q. Giải: Mệnh đề kéo theo của mệnh đề p và q là mệnh đề: “Nếu hôm nay là th ứ ba, thì chúng ta sẽ học toán rời rạc.” Mệnh đề kéo theo trên rõ ràng là chỉ sai khi hôm nay là thứ ba mà chúng ta không học toán rời rạc. • Phép kéo theo xuất hiện ở nhiều chỗ trong các suy luận toán học, nên có rất nhiều thuật ngữ được dùng để diễn đạt p → q. Dưới đây là một số ví dụ: o “Nếu p thì q” o “p kéo theo q” o “p là điều kiện đủ của q” o “q là điều kiện cần của p”. o Trong ngôn ngữ lập trình kép theo được thể hiện trong câu lệnh lập trình nếu p thì S (if p then S) trong đó p là mệnh đề còn S là một đợn chương trình (gồm một hoặc nhiều câu lệnh cần được thực hiện). • Có một số phép kéo theo liên quan có thể được tạo từ p → q: o q → p: được gọi là mệnh đề đảo của mệnh đề p → q. o ¬q → ¬p: được gọi là mệnh đề phản đảo của mệnh đề p → q. + Định nghĩa 6: Cho p và q là hai mệnh đề. Mệnh đề tương đương “p ↔ q” là một mệnh đ ề chỉ đúng khi p và q có cùng giá trị chân lý và sai trong mọi trường hợp còn lại. - Bảng chân lý: p Q p↔q T T T T F F F T F F F T
- Chú ý: Mệnh đề tương đương p ↔ q là đúng chỉ khi hai mệnh đ ề kéo theo p → q và q → p đều đúng ( p ↔ q ⇔ (p → q) ∧ (q ← p) ). Vì thế mệnh đề tương đương p ↔ q còn được phát biểu: “p nếu và chỉ nếu q” hay “p là cần và đủ đối với q”. + Độ ưu tiên của các toán tử logic: Ưu tiên mức 1: () Ưu tiên mức 2: ¬. Ưu tiên mức 3: ^, ۷. Ưu tiên mức 4: →, ↔. 4. Các phép toán logic và các phép toán bit: 4.1 Khái niệm: o Biểu diễn thông tin dưới dạng nhị phân (bit): 0 – không có năng lượng, 1 – có năng lượng. o Biểu diễn giá trị chân lý: 1- đúng, 0 – sai. o Biến Boole chỉ nhận giá trị đúng hoặc sai. 4.2 Phép toán bit: Các phép toán bit trong máy tính tương ứng với các liên từ logic: ^, ۷, ⊕ tương ứng là AND, OR và XOR. Bảng chân lý của các phép toán bit: OR 0 1 AND 0 1 XOR 0 1 0 0 1 0 0 0 0 0 1 1 1 1 1 0 1 1 1 0 4.3 Định nghĩa: Một xâu bit (hoặc xâu nhị phân) là dãy không hoặc nhiều bit. Chiều dài của xâu là số các bit trong xâu đó. 4.4 Ví dụ: Tìm AND, OR, XOR đối với hai xâu: 01101 10110 và 11000 11101. 01101 10110 11000 11101 __________ OR bit 11101 11111 AND bit 01000 10100 XOR bit 10101 01011 5. Sự tương đương của các mệnh đề: Tương đương mệnh đề có nghĩa là các mệnh đề khác nhau nhưng có cùng giá trị chân lý. Trong các lập luận thường thay thế các mệnh đề phức hợp bởi các mệnh đ ề tương đương đơn giản hơn. 5.1 Định nghĩa 1(Phân loại mệnh đề phức hợp theo giá trị chân lý):
o Một mệnh đề phức hợp mà luôn đúng với bất kỳ giá trị chân lý của các mệnh đề thành phần của nó được gọi là hằng đúng. o Một mệnh đề mà luôn luôn sai được gọi là mâu thuẫn. o Một mệnh đề không phải là hằng đúng, cũng không phải là mâu thuẫn được gọi là tiếp liên. o Ví dụ: Cho mệnh đề p. Xét bảng chân lý của các mệnh đề p ۷ ¬p và p ^ ¬p. Mệnh đề p ۷ ¬p luôn cho giá trị đúng với mọi giá trị của p do đó nó hằng đúng, mệnh đề p ^ ¬p luôn cho giá trị sai với mọi p do đó nó là một mâu thuẫn. P ¬p p ۷ ¬p p ^ ¬p T F T F F T T F 5.2 Định nghĩa 2 (Tương đương logic): Các mệnh đề p và q được gọi là tương đương logic nếu p ↔ q là hằng đúng. Ký hiệu p ⇔ q để chỉ p và q là tương đương logic. (Để xác định hai mệnh đề có tương đương hay không ta dùng bảng chân lý.) • Ví dụ 1: Chứng minh rằng ¬(p ۷ q) và ¬p ^ ¬q là tương đương logic. p q ¬p ¬q p۷q ¬(p ۷ q) ¬p ^ ¬q T T F F T F F T F F T T F F F T T F T F F F F T T F T T Bảng chân lý đối với ¬(p ۷ q) và ¬p ^ ¬q. • Ví du 2: Chứng mimh rằng p → q và ¬p ۷ q là tương đương logic. p q ¬p p→q ¬p ۷ q T T F T T T F F F F F T T T T F F T T T Bảng chân lý đối với rằng p → q và ¬p ۷ q. • Ví du 3: Chứng mimh rằng p ⊕ q và ¬(p ↔ q) là tương đương logic. p q p→q p←q p↔q ¬(p ↔ q) p⊕ q T T T T T F F T F F T F T T F T T F F T T F F T T T F F Bảng chân lý đối với p ⊕ q và ¬(p ↔ q). 5.3 Bảng tương đương logic: TƯƠNG ĐƯƠNG TÊN GỌI
p ^ T p Luật đồng nhất p ۷ F p p ۷ T T Luật nuốt p ^ F F p ۷ p p Luật lũy đẳng p ^ p p ¬p(¬q) p Luật phủ định kép p ۷ q q ۷ p Luật giao hoán p ^ q q ^ p p ۷ q ۷ r (p ۷ q) ۷ r p ۷ (q ۷ r) Luật kết hợp p ^ q ^ r (p ^ q) ^ r p ^ (q ^ r) p ۷ (q ^ r) (p ۷ q) ^ (p ۷ r) Luật phân phối p ^ (q ۷ r) (p ^ q) ۷ (p ^ r) ¬(p ^ q) ¬p ۷ ¬q Luật De Morgan ¬(p ۷ q) ¬p ^ ¬q p ۷ ¬p T p ^ ¬q F Luật DeMorgan mở rộng (p → q) (¬p ۷ q) (Bảng tương đương logic). Ví dụ 1: Chứng minh rằng ¬(p ۷ (¬p ^ q)) và ¬p ^ ¬q là tương đương. Biến đổi vế trái theo bảng tương đương logic. Ví dụ 2: Chứng minh rằng (p ^ q) → (p ۷ q) là hằng đúng. o Mệnh đề (p ^ q) → (p ۷ q) là hằng đúng khi mệnh đề luôn đúng với bất kỳ giá trị chân lý nào của các mệnh đề thành phần. Điều đó có nghĩa là mệnh đề tương đương logic với T. o Sử dụng phép biến đổi tương đương (p → q) ⇔ (¬p ۷ q). 6. Vị ngữ và lượng từ: 6.1 Vị ngữ: o Xét các câu: “x > 3 – x lớn hơn 3”; “ x = y + 3”; … o Hàm mệnh đề là một câu gồm 2 phần: phần chủ ngữ - biến, phần vị ngữ cho biết một tính chất mà chủ ngữ có thể có. o Gọi x1, x2, …, xn là các biến. Hàm mệnh đề P(x1, x2, …, xn) có giá tr ị phụ thuộc vào x1, x2, …, xn xác định một mệnh đề, P được gọi là vị ngữ. Ví dụ 1: Cho câu P(x): “x > 3”. Xác định giá trị chân lý của P(4) và P(2). Giải: Mệnh đề P(4) nhận được khi thay x = 4 vào câu “x > 3”. Do đó P(4) tức là câu “4 > 3” là đúng. Còn mệnh đề P(2) tức là câu “2 > 3” là sai. Ví dụ 2: Cho câu Q(x,y): “x = y + 3”. Xác định giá trị chân lý của Q(1,2) và Q(3,0). Giải: Mệnh đề Q(1,2) nhận được khi thay x = 1 và y =2 vào câu “x = y + 3”. Do đó mệnh đề Q(1,2) là mệnh đề “1 = 2+3” là sai. Còn mệnh đề Q(3,0) là mệnh đề “3 = 0 + 3” là đúng. 6.2 Lượng từ:
Cách biến hàm mệnh đề thành các mệnh đề được gọi là sự lượng hoá. Có hai loại lượng hoá (còn gọi là lượng từ) là lượng từ phổ dụng (luợng từ “với mọi”) và lượng từ tồn tại. a. Định nghĩa 1: Lượng từ với mọi của P(x) là mệnh đề “P(x) đúng với mọi giá tr ị của x trong không gian”. Lượng từ với mọi của P(x) được ký hiệu là: ∀ x P(x). Mệnh đề ∀ x P(x) cũng được diễn đạt như: “Đối với mọi x P(x)” Ví dụ: Diễn đạt câu: “Tất cả sinh viên ở lớp này đều đã học giải tích” như một lượng từ với mọi. Giải: Cho P(x) là ký hiệu câu: “x đã học giải tích”. Khi đó câu “Tất cả sinh viên ở lớp này đều đã học giải tích”có thể được viết ∀ x P(x), ở đây không gian gồm tất cả sinh viên trong lớp học đó. b. Định nghĩa 2: Lượng từ tồn tại của P(x) là mệnh đề “Tồn tại một phần tử trong không gian sao cho P(x) là đúng”. Lượng từ tồn tại của P(x) được ký hiệu là: ∃xP(x) . Lượng từ tồn tại ∃xP(x) cũng được diễn đạt như sau: “Tồn tại x sao cho P(x)”. “Tồn tại ít nhất một x sao cho P(x)”. “Đối với một x nào đó P(x)”. Ví dụ: Cho P(x) là câu “x > 3”. Tìm giá trị chân lý của ∃xP(x) với không gian là tập các số thực. Giải: Vì “x > 3” là đúng với x = 4, nên lượng tử tồn tại của P(x) là đúng. BÀI 2: TẬP HỢP 1. Một số khái niệm cơ bản: a. Khái niệm: Các đối tượng trong một tập hợp cũng được gọi là phần tử của tập hợp đó. Tập h ợp đ ược nói là chứa các phần tử của nó. b. Cách mô tả tập hợp:  Cách 1: Mô tả tập hợp bằng cách liệt kê các phần tử của tập hợp nếu có thể. Ký hiệu tập hợp T = {phần tử thứ 1, phần tử thứ 2, …}. Ví dụ 1: Tập các nguyên âm, V = {a, e, i, o, u}. Tập các số nguyên dương lẻ nhỏ hơn 10, O = {1, 3, 5, 7, 9}.  Cách 2: Mô tả tập hợp bằng cách chỉ rõ các thuộc tính đặc trưng của các phần tử của tập hợp đó. Ví dụ mô tả tập hợp các số nguyên dương lẻ nhỏ hơn 10, O = {x | x là số nguyên dương lẻ nhỏ hơn 10}. R = {x | x là số thực}.
 Cách 3: Mô tả tập hợp bằng hình vẽ hay giản đồ Venn (do nhà toán học người Anh John Venn đưa ra lần đầu tiên vào năm 1881). c. Quy ước:  Để biểu diễn một phần tử a thuộc một tập hợp A ta ký hiệu: a ∈ A .  Để biểu diễn một phần tử a không thuộc một tập hợp A ta ký hiệu: a ∉ A .  Tập hợp không chứa một phần tử nào được gọi là tập rỗng và được ký hiệu là Ø. Ví dụ tập hợp các số lẻ chia hết cho 2. d. Định nghĩa 2: Hai tập hợp là bằng nhau nếu và chỉ nếu chúng có cùng phần tử. Ví dụ: Các tập {1, 3, 5}, {5, 3, 1} và {1, 3, 3, 5, 5, 5} là bằng nhau vì chúng có cùng các phần tử. Trật tự các phần tử trong mô tả tập hợp và phần tử được liệt kê nhiều lần là không quan trọng. ( Xem lại định nghĩa ) e. Định nghĩa 3: Tập A được gọi là tập con của tập B nếu và chỉ nếu mỗi phần tử của A đều là một phần tử của B. Chúng ta dùng ký hiệu A ⊆ B để chỉ A là tập con của B. Chúng ta thấy rằng A ⊆ B nếu và chỉ nếu lượng từ ∀x( x ∈ A → x ∈ B ) là đúng. Ví dụ: A = {x | x là số nguyên dương lẻ nhỏ hơn 10} B = {x | x là số nguyên dương nhỏ hơn 10} => A ⊆ B . - Tập rỗng là tập con của mọi tập hợp (cần chứng minh mệnh đề “nếu x ∈ ∅ thì x ∈ S là đúng”. Mệnh đề này luôn đúng vì x ∈ ∅ luôn sai). - Mọi tập hợp đều là tập con của chính nó. - Nếu tập A là con của tập B và tồn tại b ∈ B sao cho b ∉ A thì tập A được gọi là tập con thực sự của tập B. Ký hiệu A ⊂ B . - Hai tập hợp A và B được gọi là bằng nhau nếu tập A là con của tập B và ngược lại. - Các tập cũng có thể có các phần tử là các tập hợp khác. f. Định nghĩa 4: Cho S là một tập hợp. Nếu có chính xác n phần tử phân biệt trong S, với n là số nguyên không âm thì ta nói rằng S là một tập hữu hạn và n là bản số của S. Bản số của S được ký hiệu là | S|. 2. Phép toán trên tập hợp: a. Định nghĩa 1 (Phép hợp): A ∪ B = {x | x ∈ A ∨ x ∈ B} b. Định nghĩa 2 (Phép giao): A ∩ B = {x | x ∈ A ∧ x ∈ B}
c. Định nghĩa 3: Hai tập hợp được gọi là rời nhau nếu giao của chúng bằng rỗng. d. Định nghĩa 4 (Phép trừ): A – B = {x | x ∈ A ∧ x ∉ B} e. Định nghĩa 4 (Phần bù): A = {x | x ∉ A} f. Các hằng đẳng thức tập hợp: Cho U là không gian. HẰNG ĐẲNG THỨC TÊN GỌI A∪∅ = A Luật đồng nhất A ∩U = A A ∪U = U Luật nuốt A∩∅ = ∅ A∪ A = A Luật lũy đẳng A∩ A = A A= A Luật bù A∪ B = B ∪ A Luật giao hoán A∩ B = B ∩ A A ∪ ( B ∩ C ) = ( A ∪ B) ∩ ( A ∪ C ) Luật kết hợp A ∩ ( B ∪ C ) = ( A ∩ B) ∪ ( A ∩ C ) A ∪ ( B ∪ C ) = ( A ∪ B) ∪ C = A ∪ B ∪ C Luật phân phối A ∩ ( B ∩ C ) = ( A ∩ B) ∩ C = A ∩ B ∩ C A∪ B = B ∩ A Luật De Morgan A∩ B = B ∪ A g. Tích Đề các. i. Định nghĩa 1: Gọi dãy (bộ) 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, … và an là phần tử thứ n. Hai dãy (bộ) sắp thứ tự là bằng nhau nếu và chỉ nếu các phần tử tương ứng của chúng là bằng nhau. ii. Định nghĩa 2: Cho A và B là hai tập hợp. Tích đề các của A và B được ký hiệu là AxB là tập hợp của tất cả các cặp (a,b) với a ∈ A và b ∈ B . Từ đó: A x B = {(a, b) | a ∈ A ∧ b ∈ B} Tổng quát: A1 x A2 x … x An = {(a1, a2, …, an) | a1 ∈ A1^ a2 ∈ A2^...^ an ∈ An}
BÀI 3: ÁNH XẠ VÀ HÀM 1. Định nghĩa: a. Định nghĩa: Cho A và B là hai tập hợp. Một hàm f từ A đến B là sự gán chính xác một phần tử của B cho mỗi phần tử của A. Ta viết f(a) = b nếu b là phần tử duy nhất của B được gán bởi hàm f cho phần tử a của A. Ký hiệu f : A → B . - A: được gọi là miền xác định của hàm f. - B: được gọi là miền giá trị của hàm f. - Nếu f(a) = b ta nói b là ảnh của a và a là nghịch ảnh của b. Ký hiệu f-1(b) = a. - Tập hợp tất cả các ảnh của các phần tử thuộc A được gọi là ảnh của A qua hàm f. f(A) = {f(a) | a ∈ A} . - Hàm f từ A đến B còn được gọi là ánh xạ từ A đến B. b. Ví dụ: Ví dụ 1: Giả sử f : Z → Z, f : x → x2.  Miền xác định: tập hợp các số nguyên.  Miền giá trị: tập hợp tất cả các số nguyên không âm là số chính phương. Ví dụ 2: Viết hàm lấy phần nguyên của một số thực: function floor (x: real): integer  Miền xác định: tập các số thực  Miền giá trị: tập các số nguyên. c. Hàm hợp: Cho 2 hàm 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. d. Tính chất: Cho 2 hàm f:X→Y g:X→Y Khi đó: f + g : X → Y và f.g : X → Y được xác định như sau: (f + g)(x) = f(x) + g(x) và (f.g)(x) = f(x).g(x).
2. Các hàm đơn ánh và toàn ánh: a. Đơn ánh: Hàm f : X → Y được gọi là một đơn ánh khi các ảnh của 2 phần tử khác nhau tùy ý thì khác nhau, nghĩa là với mọi x và x' thuộc X ta có: x ≠ x' => f(x) ≠ f(x') hay f(x) = f(x') => x = x' b. Toàn ánh: Hàm f : X → Y được gọi là một toàn ánh khi mọi phần tử của Y đều là ảnh của ít nhất một phần tử x thuộc X, nghĩa là f(X) = Y. c. Song ánh: Hàm f : X → Y được gọi là một song ánh khi nó vừa là đơn ánh vừa là toàn ánh. Khi ấy với mỗi y ∈ Y , có duy nhất phần tử x ∈ X sao cho f(x) = y. Như thế phép tương ứng liên kết y với x sẽ cho ta một hàm từ Y vào X. Ta gọi hàm này là hàm ngược của f và ký hiệu là f -1. Vậy ta có: f-1 : Y → X, xác định bởi f-1(y) = x, với f(x) = y. d. Ví dụ: Ví dụ 1: Hàm f : Z → N xác định bởi f(n) = n2+1 không phải là một đơn ánh vì f(-1) = f(1) = 2 mà -1 ≠ 1. Ví dụ 2: Hàm f : N → N xác định bởi f(n) = n2+1 là một đơn ánh vì ta có thể thấy rằng với mọi n và n' thuộc N ta có: nếu f(n) = f(n') thì n = n'. Ví dụ 3: Cho a và b là 2 số thực tùy ý và a ≠ 0. Hàm f : R → R xác đ ịnh bởi f(x) = a.x+b là một song ánh vì với mọi số thực y thì phương trình ax + b = y có nghiệm thực x duy nhất là x = (y-b) / a. Từ đó ta cũng có ánh xạ ngược được xác đ ịnh bởi f-1(y) = (y- b) / a. 3. Biểu diễn hàm (Đồ thị của hàm): a. Định nghĩa: Cho hàm f: A → B. Đồ thị của hàm f là tập các cặp sẵp thứ tự: {(a, b) | a ∈ A và f(a) = b} . b. Ví dụ: Ví dụ 1: Vẽ đồ thị hàm f(n) = 2n + 1. Ví dụ 2: Vẽ đồ thị hàm f(x) = x2
BAI TÂP CHƯƠNG I ̀ ̣ Bài 1: Logic và mệnh đề 1. Dùng bảng chân lý để chứng minh luật giao hoán: a. pV q⇔qVp b. pʌ q⇔qʌp 2. Dùng bảng chân lý để chứng minh luật kết hợp: a. (p V q) V r ⇔ p V (q V r) b. (p ʌ q) ʌ r ⇔ p ʌ (q ʌ r) 3. Dùng bảng chân lý để chứng minh luật phân phối: p ʌ (q V r) ⇔ (p ʌ q) V (p ʌ r) 4. Dùng bảng chân lý để chứng minh tương đương: ¬ (p ʌ q) ⇔ ¬ p V ¬ q 5. Dùng bảng chân lý để chứng minh các mệnh đề kéo theo sau là hằng đúng: a. (p ʌ q) → p b. p → (p V q) c. ¬ p → (p → q) d. (p ʌ q) → (p → q) e. ¬ (p → q) → p f. ¬ (p → q) → ¬ q 6. Bằng cách dùng bảng chân lý chứng minh rằng các mệnh đề kéo theo sau là hằng đúng: a. [¬q ʌ (p V q)] → q b. [(p → q) ʌ (q → r)] → (p → r) c. [p ʌ (p → q)] → q d. [(p V q) ʌ (p → r) ʌ (q → r)] → r 7. Cho P(x) là câu “x học ở lớp hơn 5 giờ mỗi ngày trong tuần”, ở đây không gian là tập hợp các sinh viên. Hãy diễn đạt các lượng từ sau thành câu thông thường: a. Ǝx P(x) b. ∀x P(x) c. Ǝx ¬P(x) d. ∀x ¬P(x) 8. Cho P(x, y) là câu “x đã học môn y”, với không gian của x là tập hợp tất cả sinh viên trong lớp bạn, và không gian của y là tập hợp tập hợp tất cả các môn tin học ở tr ường bạn. Hãy diễn đạt các lượng từ sau thành câu thông thường: a. Ǝx Ǝy P(x, y) b. Ǝx ∀y P(x, y) c. ∀x Ǝy P(x, y) d. Ǝy ∀x P(x, y) e. ∀y Ǝ x P(x, y) f. ∀x ∀y P(x, y)
9. Cho P(x) và câu “x nói được tiếng Nga” và Q(x) là câu “x biết ngôn ngữ C++”. Hãy diễn đạt các câu sau bằng cách dùng P(x), Q(x), các lượng từ và các liên từ logic. Cho không gian đối với các lượng từ là tập hợp tất cả sinh viên ở trường bạn: a. Có một sinh viên ở trường bạn nói được tiếng Nga và biết C++. b. Có một sinh viên ở trường bạn nói được tiếng Nga và không biết C++. c. Mọi sinh viên ở trường bạn đều nói được tiếng Nga hoặc biết C++. d. Không có một sinh viên nào ở trường bạn nói được tiếng Nga hoặc biết C++. 10. Cho Q(x) là câu “x đã là người tham gia cuộc thi y”. Hãy di ễn đ ạt các câu sau b ằng cách dùng Q(x, y), các lượng từ và các liên từ logic. Cho không gian của x là t ập hợp t ất c ả sinh viên của trường bạn, còn không gian của y là tập hợp tất cả các cuộc thi trên truyền hình. a. Có một sinh viên ở trường bạn đã tham gia cuộc thi trên truyền hình. b. Không có một sinh viên nào ở trường bạn đã tham gia cuộc thi trên truyền hình. c. Có một sinh viên ở trường bạn đã tham gia cuộc thi Jeopardy và Wheel of Fortune trên truyền hình. d. Mọi cuộc thi trên truyền hình đều có một sinh viên ở trường bạn tham gia. e. Ít nhất có hai sinh viên ở trường bạn đã tham gia cuộc thi Jeopardy trên truyền hình. 11. Cho L(x, y) là một câu “x yêu y”, với không gian của cả x và y là t ập h ợp m ọi ng ười trên thế giới. Hãy dùng các lượng từ để diễn đạt các câu sau: a. Mọi người đều yêu Jerry b. Mọi người đều yêu một ai đó c. Có một người mà tất cả mọi người đều yêu d. Không có ai yêu tất cả mọi người e. Có một người mà Lydia không yêu f. Có một người mà không ai yêu g. Có đúng một người mà tất cả mọi người đều yêu h. Có đúng hai người mà Lynn yêu i. Mọi người đều yêu chính mình j. Có một người nào đó không yêu ai ngoài chính mình 12. Cho F(x, y) là câu “x có thể lừa gạt y”, với không gian là t ập h ợp m ọi ng ười trên th ế gi ới. Hãy dùng các lượng từ để diễn đạt các câu sau: a. Mọi người đều có thể lừa gạt Fred b. Evelyn có thể lừa gạt được mọi người c. Mọi người đều có thể lừa gạt được ai đó d. Không có ai có thể lừa gạt được tất cả mọi người e. Mọi người đều có thể bị lừa gạt bởi ai đó f. Không ai có thể lừa gạt được cả Fred lẫn Jerry g. Nancy có thể lừa được chính xác hai người h. Có chính xác một người mà ai cũng lừa gạt được i. Không ai có thể lừa gạt được chính mình
j. Có một người nào đó có thể lừa gạt được chính xác một người trừ bản thân mình. 13. Dùng các lượng từ để diễn đạt các câu sau: a. Tất cả các sinh viên tin học đều cần phải học môn toán học rời rạc b. Có một sinh viên ở lớp này đã có máy vi tính c. Tất cả các sinh viên ở lớp này đã học ít nhất một môn tin học d. Có một sinh viên ở lớp này đã học ít nhất một môn tin học e. Mỗi sinh viên ở lớp này ở một nhà trong ký túc xá f. Có một sinh viên ở lớp này đã ở tất cả các phòng của ít nhất một nhà trong ký túc xá g. Tất cả các sinh viên ở lớp này ít nhất đã ở một phòng trong t ất cả các nhà trong ký túc xá. 14. Lớp toán học rời rạc có một sinh viên ngành toán năm thứ nhất, 12 sinh viên ngành toán năm thứ hai, 15 sinh viên tin học năm thứ hai, hai sinh viên toán năm thứ ba, hai sinh viên tin học năm thứ ba và một sinh viên tin học năm thứ tư (năm cuối cùng). Di ễn đ ạt các câu sau bằng cách dùng các lượng từ rồi sau đó xác định giá trị chân lý của chúng: a. Có một sinh viên trong lớp là sinh viên năm thứ ba b. Mọi sinh viên trong lớp đều là sinh viên ngành tin học. c. Có một sinh viên trong lớp không phải là sinh viên ngành toán và cũng không ph ải sinh viên năm thứ ba. d. Mọi sinh viên trong lớp hoặc là sinh viên năm thứ hai hoặc là sinh viên ngành tin. e. Có một ngành học sao cho mỗi khóa học có một sinh viên ở lớp này học ngành đó. 15. Cho P(x) là câu “x = x2”. Nếu không gian là tập hợp các số nguyên, thì giá trị chân lý của các mệnh đề sau là như thế nào? a. P(0) b. P(1) c. P(2) d. P(-1) e. Ǝx Q(x) f. ∀x P(x) 16. Cho Q(x, y) là câu “x + y = x - y”. Nếu không gian của hai bi ến là t ập hợp các s ố nguyên, hãy xác định giá trị chân lý của các mệnh đề sau: a. Q(1, 1) b. Q(2, 0) c. ∀y Q(1, y) d. Ǝx Q(x, 2) e. Ǝx Ǝy Q(x, y) f. ∀x Ǝy Q(x, y) g. Ǝy ∀x Q(x, y) h. ∀x ∀y Q(x, y)
17. Giả sử không gian của hàm mệnh đề P(x, y) gồm các cặp số x và y với x là 1, 2 hoặc 3 và y là 1, 2 hoặc 3. Dùng các phép hội và tuyến viết các mệnh đề sau: a. Ǝx P(x, 3) b. ∀y P(1, y) c. ∀x ∀y P(x, y) d. Ǝx Ǝy P(x, y) e. Ǝx ∀y P(x, y) f. ∀y Ǝx P(x, y) 18. Dùng các lượng từ diễn đạt phủ định các mệnh đề sau, rồi dịch các phủ định đó ra các câu thông thường. a. Mọi sinh viên ở lớp này đều thích môn toán. b. Có một sinh viên trong lớp này chưa hề bao giờ nhìn thấy một chiếc máy tính. c. Có một sinh viên trong lớp này đã học tất cả các môn toán được dạy ở trường này. d. Có một sinh viên ở lớp này đã ở ít nhất một phòng trong tát cả các tòa nhà ở ký túc xá. 19. Cho P(x), Q(x) và R(x) là các câu “x là giáo sư”, “x là kẻ ngu dốt” và “x là k ẻ vô tích s ự”, tương ứng. Bằng cách dùng các lượng từ, các liên từ logic cùng với P(x), Q(x) và R(x) di ễn đạt các câu sau với không gian là tập hợp toàn thể loài người. a. Không có giáo sư nào là kẻ ngu dốt. b. Mọi kẻ ngu dốt đều là vô tích sự. c. Không có giáo sư nào là vô tích sự d. (c) có thể suy ra từ (a) và (b) không? Nếu không, liệu có một kết luận đúng nào không? 20. Cho P(x), Q(x) và R(x) tương ứng là các câu “x là lời giải thích rõ ràng”, “x là thỏa đáng” và “x là một lý do”. Giả sử không gian c ủa biến x là t ập hợp toàn b ộ văn b ản. Dùng các lượng từ, các liên từ logic cùng với P(x), Q(x) và R(x) diễn đạt các câu sau: a. Tất cả các giải thích rõ ràng đều là thỏa đáng. b. Một số lý do là không thỏa đáng. c. Một số lý do không phải là giải thích rõ ràng. d. (c) có thể suy ra từ (a) và (b) không? Nếu không, liệu có một kết luận đúng không? 21. Cho P(x), Q(x), R(x) và S(x) tương ứng là các câu “x là một đứa bé”, “x là logic”, “x có khả năng cai quản một con cá sấu” và “x bị coi thường”. Giả sử không gian là tập hợp tất cả mọi người. Hãy dùng các lượng từ, các liên từ logic cùng với P(x), Q(x), R(x) và S(x) đ ể di ễn đ ạt các câu sau: a. Những đứa bé là không logic. b. Không ai bị coi thường nếu cai quản được cá sấu. c. Những người không logic bị coi thường. d. Những đứa bé không cai quản được cá sấu. e. (d) có thể suy ra từ (a), (b) và (c) không? Nếu không, liệu có một kết luận đúng không?
22. Cho P(x), Q(x), R(x) và S(x) tương ứng là các câu sau: “x là một con vịt”, “x là một trong số gia cầm của tôi”, “x là một viên sĩ quan” và “s ẵn lòng khiêu vũ”. Dùng các l ượng t ừ, các liên từ logic cùng với P(x), Q(x), R(x) và S(x) để diễn đạt các câu sau: a. Không có con vịt nào sẵn lòng khiêu vũ cả. b. Không có viên sĩ quan nào từ chối khiêu vũ cả. c. Toàn bộ đàn gia cầm của tôi đều là vịt. d. Đàn gia cầm của tôi không phải là các sĩ quan. e. (d) có thể suy ra từ (a), (b) và (c) không? Nếu không,liệu có một kết luận đúng không? 23. Chứng tỏ rằng các câu ¬ Ǝx ∀y P(x, y) và ∀x Ǝy ¬ P(x, y) có cùng giá trị chân lý 24. Chứng tỏ rằng ∀x (P(x) ∧ Q(x)) và ∀x P(x) ∧ ∀x Q(x) có cùng giá trị chân lý 25. Chứng tỏ rằng Ǝx (P(x) ∨ Q(x)) và Ǝx P(x) ∨ Ǝx Q(x) có cùng giá trị chân lý 26. Xác lập các tương đương logic sau, trong đó A là một mệnh đề không có chứa các lượng từ. a. (∀x P(x)) ∨ A ⇔ ∀x (P(x) ∨ A) b. (Ǝx P(x) ∨ A ⇔ Ǝx (P(x) ∨ A) 27. Xác lập các tương đương logic sau, trong đó A là một mệnh đề không có liên quan v ới lượng từ nào: a. (∀x P(x)) ∧ A ⇔ ∀x (P(x) ∧ A) b. (Ǝx P(x) ∧ A ⇔ Ǝx (P(x) ∧ A) 28. Chứng minh rằng ∀x P(x) ∨ ∀x Q(x) và ∀x (P(x) ∨ Q(x)) là không t ương đ ương logic. 29. Chứng minh rằng Ǝx P(x) ∧ Ǝx Q(x) và Ǝx (P(x) ∧ Q(x)) là không t ương đ ương logic. 30. Chứng minh rằng ∀x P(x) ∨ ∀x Q(x) và ∀x ∀y (P(x) ∨ Q(y)) là t ương đ ương logic. (Biến mới y được dùng để kết hợp một cách đúng đắn các lượng từ). 31. Chứng tỏ rằng: a. ∀x P(x) ∧ Ǝx Q(x) và ∀x Ǝy (P(x) ∧ Q(y)) là tương đương logic. b. ∀x P(x) ∨ Ǝx Q(x) và ∀x Ǝy (P(x) ∨ Q(y)) là tương đương logic. 32. Ǝ!x P(x) là kí hiệu của mệnh đề “Tồn tại duy nhất một x sao cho P(x) là đúng”. Nếu không gian là tập các số nguyên, hãy xác định giá trị chân lý của các lượng từ sau: a. Ǝ!x (x > 1). b. Ǝ!x (x2 = 1). c. Ǝ!x (x + 3 = 2x). d. Ǝ!x (x = x + 1). Bài 2: Tập hợp 1. Dùng các cách chỉ rõ các thuộc tính đặc trưng mô tả các tập hợp sau: a. {0, 3, 6, 9, 12}. b. {-3, -2, -1, 0, 1, 2, 3}. c. {m, n, o, p}.
2. Xác định xem mỗi cặp tập hợp sau đây có bằng nhau không? a. {1, 3, 3, 3, 5, 5, 5, 5, 5} và {5, 3, 1}. b. {{1}} và {1, {1}}. c. Ø và {Ø}. 3. Giả sử rằng A = {2, 4, 6}, B = {2, 6}, C = {4, 6} và D = {4, 6, 8}. Hãy xác định các tập nào là những tập con của tập nào. 4. Xác định xem các mệnh đề sau đúng hay sai: a. x ∈ {x} c. {x} ⊆ {x} b. {x} ∈ {x} d. {x} ∈ {{x}} c. {Ø} ⊆ {x} e. {Ø } ∈ {x} 5. Dùng giản đồ Ven minh hoạ mối quan hệ A ⊆ B và B ⊆ C 6. Giả sử A, B và C là các tập hợp sau cho A ⊆ B và B ⊆ C . Chứng minh A ⊆ C 7. Tìm hai tập hợp A, B sao cho A ∈ B và A ⊆ B 8. Xác định bản số của các tập hợp sau: a. {a} b. {{a}} c. {a, {a}} d. {a, {a}, {a, {a}} 9. Xác định bản số của các tập hợp sau: a. Ø b. {Ø} c. {Ø, {Ø}} d. {Ø, {Ø}, {Ø, {Ø}} } 10. Tìm tập hợp luỹ thừa của các mỗi tập hợp sau: a. {a} b. {a, b} c. {Ø, {Ø}} 11. Có thể kết luận rằng A = B nếu A và B là hai tập có luỹ thừa như nhau không? 12. Mỗi tập sau có bao nhiêu phần tử a. P({a, b, {a, b}}) b. P({Ø, a, {a}, {{a}}}) c. P(P(Ø)) 13. Xác định xem mỗi tập dưới đây có là tập luỹ thừa c ủa một tập nào đó không? a. Ø b. {Ø, {a}} c. {Ø, {a}, {Ø}, a}