Toan rời rạc anh dao

CÁC KIẾN THỨC CƠ SỞ

MỤC TIÊU CHƯƠNG

Cung cấp cho sinh viên những kiến thức về:

 Mệnh đề và logic mệnh đề;

 Các quy tắc suy luận để xác định một suy diễn đúng hay sai;

 Khái niệm thuật toán và cách đánh giá độ phức tạp của thuật toán;

 Quy nạp toán học và đệ quy trong lập trình

Sau khi hoàn thành chương này, sinh viên sẽ có khả năng áp dụng các luật đại số mệnh đề để chứng minh và rút gọn biểu thức mệnh đề Họ cũng có thể đánh giá độ phức tạp của thuật toán, giúp tìm ra những giải thuật hiệu quả hơn Thêm vào đó, sinh viên sẽ biết cách áp dụng kiến thức vào thực tế để giải quyết các bài toán liên quan đến giải thuật đệ quy.

NỘI DUNG CHƯƠNG HỌC

Logic là một lĩnh vực thuộc triết học và toán học, tập trung vào việc nghiên cứu các nguyên tắc, phương pháp và tiêu chuẩn hình thức để xác định tính hợp lệ của suy luận và kiến thức Ứng dụng của logic rất đa dạng, bao gồm việc sử dụng trong suy luận toán học, thiết kế vi mạch, xây dựng và kiểm chứng chương trình trong khoa học máy tính, cũng như trong lĩnh vực trí tuệ nhân tạo.

Mệnh đề: là một phát biểu, một câu trần thuật, chỉ nhận 1 trong 2 giá trị hoặc đúng hoặc sai

Một số ví dụ về mệnh đề: o Ví dụ sau là mệnh đề

GV: Nguyễn Thị Anh Đào Trang 6

 Thành phố Đà Nẵng giáp với tỉnh Quảng Nam (nhận giá trị đúng) o Ví dụ sau không là mệnh đề

 Hôm nay là thứ mấy?

Logic không đảm nhiệm việc xác định đúng sai của một mệnh đề Một câu chỉ được coi là mệnh đề khi thời gian đã được xác định rõ ràng.

Trong logic, các ký hiệu như p, q, r được sử dụng để đại diện cho mệnh đề hoặc biến mệnh đề Giá trị chân lý của một mệnh đề có thể là True (1) hoặc False (0) Để thể hiện mối quan hệ giữa các giá trị chân lý của các mệnh đề, bảng chân trị được sử dụng như một công cụ hữu ích.

Cho mệnh đề p, phép phủ định của mệnh đề p được ký hiệu là p, đọc là phủ của p hoặc không p Chân trị của mệnh đề p được xác định dựa trên bảng chân trị, trong đó nếu p là đúng thì p sẽ là sai, và ngược lại.

Số 4 không phải là số nguyên tố, vì nó có các ước số khác ngoài 1 và chính nó Mệnh đề "4 là số nguyên tố" là sai, trong khi mệnh đề "4 không phải là số nguyên tố" là đúng.

Cho 2 mệnh đề p,q, phép hội của 2 mệnh đề p, q được ký hiệu là p  q ( đọc là p hội q hoặc p và q) Chân trị của p  q là 1 khi và chỉ khi cả p và q đều có chân trị 1, trong các trường hợp khác p  q có chân trị 0 Phép hội giữa p và q được xác định bởi bảng chân trị sau:

GV: Nguyễn Thị Anh Đào Trang 7 p q p  q

Cho 3 mệnh đề: o p: 5 > 3 o q: 4 là số nguyên tố o r: -3 < -2 thì mệnh đề: o p  q có chân trị là 0 (vì p có chân trị 1, q có chân trị 0) o p  r có chân trị là 1 (vì p có chân trị 1, r có chân trị 1)

Cho 2 mệnh đề p, q, phép tuyển của 2 mệnh đề p và q, ký hiệu là p  q (đọc là p tuyển q hoặc p hay q) Chân trị của p  q là 0 khi và chỉ khi cả p và q đều nhận chân trị là 0, các trường hợp còn lại đều nhận chân trị 1 Phép tuyển giữa p  q được xác định bởi bảng chân trị sau : p q p  q

Cho 2 mệnh đề như sau: o p: 5 > 3 o q: 4 là một số nguyên tố o r: 2 < -2

Thì mệnh đề: o p  q có chân trị là 1 (vì p có chân trị 1, q có chân trị 0) o q  r có chân trị là 0 (vì q và r đều có chân trị là 0)

Giả sử p và q là hai mệnh đề, mệnh đề “hoặc p hoặc q” được gọi là tuyển loại của hai mệnh đề này, ký hiệu là p  q Dưới đây là bảng chân trị cho p, q và p  q.

Xét ví dụ mệnh đề sau: “Hoặc là điểm của tôi được hơn 4.0 hoặc tôi sẽ bị học lại môn này” Trong đó:

P: Điểm của tôi được hơn 4.0

Q: Tôi bị học lại môn này

Khi đó mệnh đề như trên chính là : p  q

Cho 2 mệnh đề p, q, mệnh đề “nếu p thì q” được ký hiệu là p → q (đọc là p kéo theo q) Để xác định chân trị cho mệnh đề p → q ta xem bảng chân trị sau: p q p → q

Xét ví dụ mệnh đề sau: “Nếu tôi có 1 tỷ đồng thì tôi mua xe hơi”

Ta có các trường hợp như sau: o Tôi có 1 tỷ đồng, và tôi mua xe hơi: mệnh đề hiển nhiên là đúng

Nguyễn Thị Anh Đào cho rằng: "Tôi không có 1 tỷ đồng, tôi không mua xe hơi" là một mệnh đề đúng Cô cũng nêu rõ rằng "Tôi không có 1 tỷ đồng, nhưng tôi vẫn mua xe hơi" vẫn là một mệnh đề đúng Tuy nhiên, mệnh đề "Tôi có 1 tỷ đồng, nhưng tôi không mua xe hơi" lại là sai.

* Mệnh đề kéo theo chỉ sai khi “mệnh đề nếu” có chân trị 1 nhưng “mệnh đề thì” có chân trị 0

* Phép kéo theo trong logic tổng quát hơn quan hệ nhân quả trong ngôn ngữ tự nhiên

Ví dụ: Nếu hôm nay trời mưa thì 2+3 =5 (mệnh đề đúng dù trời có mưa hoặc không mưa)

Cho 2 mệnh đề p, q mệnh đề “nếu p thì q và ngược lại” được ký hiệu là p ↔ q (đọc là p khi và chỉ khi q, p nếu và chỉ nếu q, p là điều kiện cần và đủ để có q) Cả hai chiều p → q và q → p đều đúng nên nếu p đúng thì q cũng đúng và ngược lại Ta có bảng chân trị như sau: p q p ↔ q

Các mệnh đề phức hợp được hình thành từ mệnh đề sơ cấp thông qua các phép toán logic Việc xác định chân trị của những mệnh đề phức hợp dựa vào chân trị của các mệnh đề sơ cấp, cũng nhờ vào các phép toán logic Do đó, chúng ta chú trọng hơn vào việc xác định chân trị cho mệnh đề phức hợp.

Biểu thức logic chính là các mệnh đề phức hợp có giá trị là True (1) hoặc False

Trong đại số, các biểu thức đại số được hình thành từ các toán hạng như hằng số và biến, kết hợp với các toán tử theo một thứ tự nhất định Tương tự, trong biểu thức mệnh đề, các biểu thức logic được xây dựng từ các mệnh đề hoặc các giá trị hằng (chân trị).

GV: Nguyễn Thị Anh Đào Trang 10 đề cập đến các biến mệnh đề và các phép toán logic, bao gồm cả việc sử dụng dấu ngoặc để xác định thứ tự thực hiện của các phép toán logic một cách rõ ràng.

* Thứ tự ưu tiên của các phép toán trong biểu thức logic:

  ,  : phép hội và phép tuyển

 →, ↔: phép kéo theo, tương đương

Các phép toán trên cùng một dòng có độ ưu tiên ngang nhau và được thực hiện từ trái sang phải Đặc biệt, các phép toán trong dấu ngoặc ‘(…)’ sẽ được thực hiện trước các phép toán bên ngoài dấu ngoặc.

Ví dụ: E, F là các biểu thức logic

 Trong 2 biểu thức E, F trên thì p, q, r là các biến mệnh đề

TÀI LIỆU THAM KHẢO

1 Nguyễn Đức Nghĩa, Nguyễn Tô Thành, Toán rời rạc, 2009, NXB Đại học Quốc gia Hà Nội

2 Kenneth H.Rosen, Toán rời rạc và ứng dụng trong tin học, Phạm Văn Thiều, Đặng Hữu Thịnh (dịch), 1997, NXB Khoa học và kỹ thuật

3 PGS - TS Nguyễn Gia Định, Giáo trình toán rời rạc, 2003, Đại học Khoa học – Đại học Huế

4 PGS - TS Trần Quốc Chiến, Giáo trình toán rời rạc, Đại học Sư Phạm - Đại học Đà Nẵng

5 Lưu Văn Hiền, Bài giảng Toán rời rạc, 2010, Đại học Duy Tân

BÀI TẬP CHƯƠNG 1

1 Trong các câu sau đây, câu nào là mệnh đề? Xác định giá trị chân lý và đưa ra mệnh đề phủ định của mệnh đề đó a) 2 + 3 = 5 b) Năm 2014 trường Đại học Duy Tân kỷ niệm 20 năm thành lập c) x + 2 = 11 d) Hôm nay là thứ năm e) Không được đi qua lối này! f) Bây giờ là mấy giờ? g) Ồ đẹp quá! h) x + 1 = 5 nếu x = 1

2 Cho p và q là hai mệnh đề: p: Nhiệt độ không khí dưới 0 o q: Tuyết rơi

Sử dụng các ký hiệu lôgic p và q, ta có thể diễn đạt các mệnh đề như sau: a) p: Nhiệt độ không khí dưới 0 o, q: Tuyết rơi Mệnh đề a) là p và q; b) là p và không q; c) là không q thì không p; d) là p hoặc không q; e) là nếu p thì q; f) là p là điều kiện cần và đủ để q.

3 Xét mệnh đề R: “Vì 120 chia hết cho 6 nên chia hết cho 9”

Nếu viết mệnh đề R dưới dạng P→Q, hãy nêu nội dung của các mệnh đề P và Q Hỏi mệnh đề R đúng hay sai, tại sao?

4 Cho công thức logic mệnh đề: A = p → q ˄ r̅  (p → q̅) với p = 1, q = 0, r =1, hãy cho biết giá trị của A?

5 Dùng bảng chân trị để chứng minh luật kết hợp

6 Dùng bảng chân trị để chứng minh luật phân phối

7 Chứng minh các mệnh đề kéo theo sau là hằng đúng: a) (p ˄ q) → p

GV: Nguyễn Thị Anh Đào Trang 27 b) p → (p  q) c)  p → (p → q) d)  (p → q) →  q

8 Không dùng bảng chân trị xác định mệnh đề sau có là mệnh đề hằng đúng không? [(pq)r][(pr)(qr)]

9 Chứng minh các cặp biểu thức sau tương đương logic: a) p → q và q → p b) p ↔ q và p ↔ q c) p ↔ q và (p  q) d)  (p ↔ q) và p ↔ q

10 Chứng minh rằng p ↔ q và (p ˄ q)  ( p ˄  q) là tương đương

11 Cho không gian U = {2, 4, 8, 7, 9}, P(x,y)= “x chia hết cho y” Dùng các lượng từ để biểu diễn đúng P(x,y) trong U

12 Xác định giá trị chân lý của các vị từ sau biết rằng miền xác định của vị từ là tập các số nguyên n

13 Xác định chân trị cho các mệnh đề sau: a) x  R, (x 2 - 4x – 5 = 0) → (x > 0) b) x  R, (x 3 – 4x 2 + 5x – 2 = 0) ↔ (x 2 – 3x + 2 = 0)

14 Lấy phủ định của mệnh đề sau: a) x  R, x 2 – 3x + 2  0 b) x  R, x 2 – 3x + 2  0 c) y  R, x  N, x + y  0 d) x  N, y  R, x + y  0 e) x  Z, y  R, x + y  0

15 Dùng quy nạp toán học chứng minh rằng: a) 1 2 + 2 2 + …+ n 2 = 𝑛(𝑛+1)(2𝑛+1)

6 với n nguyên dương b) 2 n > n 2 với n nguyên, n>4

GV: Nguyễn Thị Anh Đào Trang 28 c) P(n): 1 + 4 +7+…+ (3n-2) = 𝑛(3𝑛−1)

16 Viết đoạn chương trình đệ quy cho các bài toán sau: a) Xuất đảo ngược một số nguyên dương ra màn hình b) Tìm số đảo ngược của một số nguyên dương c) Tìm ước chung lớn nhất của 2 số nguyên dương a, b

LÝ THUYẾT TỔ HỢP

Tập hợp

2.1.1 Các khái niệm cơ bản

Tập hợp là một khái niệm cơ bản trong toán học, được hiểu là một nhóm các đối tượng có chung đặc điểm Những đối tượng này được gọi là phần tử và thường được ký hiệu bằng các chữ cái in thường như a, b, c Tập hợp thường được biểu thị bằng các chữ cái in hoa như A, B, C, giúp phân biệt rõ ràng giữa các nhóm khác nhau.

Một phần tử a thuộc một tập A ta ký hiệu a  A

Một phần tử a không thuộc một tập A ta ký hiệu a  A

Một tập hợp A không có phần tử được gọi là tập rỗng ký hiệu A = 

 Tập hợp tất cả những sinh viên khoa tin

 Tập hợp tất cả các bạn nam yêu bóng đá của trường Duy Tân

 Tập những số nguyên tố nhỏ hơn 13

Biểu diễn 1 tập hợp: o Liệt kê các phần tử :

X = {x1, x2, , xn} o Biểu diễn tập hợp bằng cách mô tả tính chất :

Y = {x | 2x - 5 > 0} (đọc là “Y là tập hợp gồm các phần tử x mà thỏa mãn bất phương trình 2x – 5 > 0”)

Lực lượng tập hợp: Số phần tử của A, ký hiệu là A hoặc card(A) hoặc N(A) gọi là lực lượng của tập A

Tập con: Cho 2 tập hợp A, B, A được gọi là tập con của B khi và chỉ khi mọi phần tử của A đều thuộc B Ký hiệu A  B

 A không phải là tập con của B ký hiệu là: A  B

 Nếu là A  B và B  A thì A bằng B ký hiệu là A = B

 Tập tất cả các tập con của A được ký hiệu là P(A)

2.1.2 Các phép toán tập hợp

Cho hai tập A và B, ta có thể định nghĩa một số phép toán quan trọng Đầu tiên là phép hiệu, ký hiệu là A \ B, được xác định là tập hợp các phần tử thuộc A nhưng không thuộc B, tức là A \ B = {x | x ∈ A và x ∉ B} Tiếp theo là phần bù, với tập X và A ⊆ X, phần bù của A trong X được ký hiệu là A̅, với A̅ = X \ A Cuối cùng là phép hợp, ký hiệu là A ∪ B, được xác định là tập hợp các phần tử thuộc A hoặc thuộc B, tức là A ∪ B = {x | x ∈ A hoặc x ∈ B}.

B} o Phép giao: Giao của A và B, ký hiệu A  B là tập A  B = {xx  A & x 

 Nếu A  B = , ta nói A và B rời nhau

Nếu các tập X1, X2, , Xn thỏa mãn A = X1 ∪ X2 ∪ ∪ Xn và chúng rời nhau từng đôi một, thì {X1, X2, , Xn} được gọi là một phân hoạch của tập hợp A Khi A là tập con của B, có một số tính chất quan trọng liên quan đến các phép toán trên tập con.

 Bắc cầu A, B, C: A  B & B  C  A  C o Định lý 1(nguyên lí cộng): Giả sử {X1, X2, , Xn } là một phân hoạch của tập

S=X1+X2+ +Xn o Định lý 2: Cho các tập A, B, C trong tập vũ trụ U, khi đó ta có : a) Luật kết hợp

A = A e) Luật đối ngẫu De Morgan

*Tích Đề-các Định nghĩa o Tích Đề-các của hai tập A, B là tập A × B = {(a,b) a  A & b  B} o Tích Đề-các của các tập X1, X2, , Xn là tập X1× X2 × ×Xn = {(x1, x2, , xn)x1 X1 & x2  X2 & & xn  Xn}

Ví dụ: Cho A = {a, b} và B = {1, 5, 7} Ta có

Những nguyên lý đếm cơ bản

Lý thuyết tổ hợp nghiên cứu cách phân bổ các phần tử vào các tập hợp, thường là hữu hạn, với các điều kiện cụ thể theo yêu cầu của bài toán Phân bố này được gọi là cấu hình tổ hợp.

Bài toán đếm là một dạng bài toán phổ biến trong tổ hợp, nhằm xác định số lượng cấu hình thỏa mãn các điều kiện đã cho Phương pháp giải quyết dựa vào các nguyên lý cơ bản và kết quả đếm các cấu hình đơn giản Bài toán này có ứng dụng trong các lĩnh vực đánh giá, như tính xác suất của một sự kiện và độ phức tạp của thuật toán.

Cho A, B là 2 tập hợp hữu hạn rời nhau, thì:

Nguyên lý cộng mở rộng cho nhiều tập con rời nhau:

Nếu {A 1 , A 2 … A k } là phân hoạch của Tập X thì |X|= |A 1 |+ |A 2 | + + |A k |

Giả sử có hai công việc khác nhau, trong đó công việc thứ nhất có n1 cách thực hiện và công việc thứ hai có n2 cách thực hiện Nếu hai công việc này không thể được thực hiện đồng thời, tổng số cách thực hiện cả hai công việc sẽ là n1 + n2.

Khoa Tin có tổng cộng 25 giảng viên và 20 sinh viên ưu tú Để đại diện cho khoa trong một chương trình giao lưu, có thể chọn một giảng viên hoặc một sinh viên ưu tú Tổng số cách chọn sẽ là 25 giảng viên cộng với 20 sinh viên ưu tú, tức là có 45 lựa chọn khác nhau.

Có tổng cộng 45 cách để chọn đại diện cho khoa, bao gồm 25 cách chọn giảng viên và 20 cách chọn sinh viên ưu tú.

Một đoàn vận động viên tham gia hai môn thi là bắn súng và bơi, trong đó có 10 vận động viên nam Tổng số vận động viên bắn súng, bao gồm cả nam và nữ, là 14 Số vận động viên nữ thi bơi bằng số nam vận động viên thi bắn súng Hãy tính tổng số người trong đoàn.

Đoàn vận động viên được chia thành hai nhóm: nam và nữ Nhóm nữ tiếp tục được phân chia thành hai nhóm nhỏ hơn, gồm nữ vận động viên bắn súng và nữ vận động viên thi bơi Khi thay số nữ vận động viên thi bơi bằng số nam vận động viên bắn súng, tổng số nữ vận động viên bắn súng là 14 Theo nguyên lý cộng, tổng số vận động viên trong đoàn là 24 người, với 10 nam và 14 nữ.

Ví dụ 3 Sau khi thực hiện đoạn chương trình sau thì k nhận giá trị là bao nhiêu? int k=0; for (int i:= 1;i

Định dạng
Số trang	152
Dung lượng	4,03 MB