Chương 1: Đại số mệnh đề - Sau mỗi câu lệnh ( nghĩa là khi qua câu lệnh mới thì gán lại n = 7) - Sau tất cả các lệnh ( sử dụng kết quả của câu lệnh trước để tính toán cho câu sau) 4/ Cho đoạn chương trình sau : a/ if n-m = 5 then n:= n-2 ; b/ if ((2*m=n) and (n div 4 =1) then n:= 4*m - 3 ; c/ if ((n<8) or (m div 2=2)) then n:= 2*m else m:= 2*n ; d/ if ((n<20) and (n div 6 =1) then m:= m-n-5 ; e/ if ((n= 2*m) or (n div 2= 5)) then m:= m+2 ; f/ if ((n div 3 = 3) and (m div 3 <>1)) then m:= n ; g/ if m*n <> 35 then n:= 3*m+7 ; Ban đầu biến nguyên n = 8 và m = 3. Hãy xác định giá trị của m, n trong các trường hợp sau : - Sau mỗi câu lệnh ( nghĩa là khi qua câu lệnh mới thì gán lại n = 7) - Sau tất cả các lệnh ( sử dụng kết quả của câu lệnh trước để tính toán cho câu sau) 5/ Vòng lặp Repeat. Until trong một đoạn chương trình Pascal như sau : Repeat. Until ((x<>0) and (y>0)) or ( not ((w>0) and (t=3)) ; Với mỗi cách gán giá trị biến như sau, hãy xác định trong trường hợp nào thì vòng lặp kết thúc.
a/ x= 7, y= 2, w= 5, t= 3 b/ x= 0, y= 2, w= -3, t= 3 c/ x= 0, y= -1, w= 1, t= 3 d/ x= 1, y= -1, w= 1, t= 3 6/ Trong một phiên tòa xử án 3 bị can có liên quan đến vấn đề tài chánh, trước tòa cả 3 bị cáo đều tuyên thệ khai đúng sự thật và lời khai như sau : Anh A: Chị B có tội và anh C vô tội Chị B : Nếu anh A có tội thì anh C cũng có tội Anh C: Tôi vô tội nhưng một trong hai người kia là có tội Trang 25 Chương 1: Đại số mệnh đề Hãy xét xem ai là người có tội ? 7/ Cho các mệnh đề được phát biểu như sau, hãy tìm số lớn nhất các mệnh đề đồng thời là đúng. a/ Quang là người khôn khéo b/ Quang không gặp may mắn c/ Quang gặp may mắn nhưng không khôn khéo d/ Nếu Quang là người khôn khéo thì nó không gặp may mắn e/ Quang là người khôn khéo khi và chỉ khi nó gặp may mắn f/ Hoặc Quang là người khôn khéo, hoặc nó gặp may mắn nhưng không đồng thời cả hai. 8/ Cho a và b là hai số nguyên dương. Biết rằng, trong 4 mệnh đề sau đây có 3 mệnh đề đúng và 1 mệnh đề sai.
Hãy tìm mọi cặp số (a, b) có thể có. 1/ a+1 chia hết cho b 2/ a = 2b + 5 3/ a+b chia hết cho 3 4/ a+7b là số nguyên tố 9/ Không lập bảng chân trị, sử dụng các công thức tương đương logic, chứng minh rằng các biểu thức mệnh đề sau là hằng đúng a/ (P∧Q)→P b/ P→(¬ P → P) c/ P→((Q→ (P∧Q)) d/ ¬ (P ∨ ¬Q)→¬ P e/ ((P→Q) ∧ (Q→R)) → (P→R) 10/ Không lập bảng chân trị, sử dụng các công thức tương đương logic, xét xem biểu thức mệnh đề G có là hệ quả của F không ? a/ F = P∧(Q∨R) G = (P∧Q)∨R b/ F = (P→Q)∧(Q→R) G = P→ (Q →R) c/ F = P∧Q G = (¬P→Q) ∨ (P→ ¬Q) 11/ Tương tự bài tập 9 và 10, chứng minh các tương đương logic sau đây: a/ (P∨Q)∧¬ (¬P∧Q) ⇔ P Trang 26 Chương 1: Đại số mệnh đề b/ ¬(¬((P∨Q)∧R) ∨ ¬Q) ⇔ Q∧R c/ ((P∨Q) ∧ (P ∨ ¬Q)) ∨ Q ⇔ P∨Q d/ ¬(P∨Q) ∨ ((¬P ∧Q) ∨ ¬Q) ⇔ ¬(Q∧P) e/ (P→Q) ∧ (¬Q ∧ (R ∨ ¬Q)) ⇔ ¬ (Q∨P) f/ P ∨ (P ∧ (P∨Q) ⇔ P g/ P ∨ Q ∨ (¬P ∧ ¬Q ∧ R) ⇔ P∨Q∨R h/ ((¬P ∨ ¬Q) → (P∧Q∧R ) ⇔ P∧Q i/ P ∧ ((¬Q → (R∧R)) ∨ ¬ (Q ∨ (R∧S) ∨ (R ∧ ¬S))) ⇔ P j/ (P∨Q∨R) ∧ (P ∨ S ∨ ¬Q) ∧ (P ∨ ¬S ∨ R) ⇔ P ∨ (R ∧ (S ∨ ¬Q) Trang 27 Chương 1: Đại số mệnh đề CHƯƠNG 1 : ĐẠI SỐ MỆNH ĐỀ. Định nghĩa mệnh đề. Các phép tính mệnh đề.
Phép phủ định (NEGATION). Phép toán trên bit. Phép kéo theo (IMPLICATION). Phép tương đương (BICONDITIONAL).
Biểu thức mệnh đề (LOGICAL CONNECTIVES). Các ứng dụng của Logic (EVERDAY LOGICAL). Các thuật ngữ chuyên ngành (SOME TERMINOLOGY). Định nghĩa Hằng đúng (Tautologie):.
Định nghĩa Hằng sai (Contradiction):. Định nghĩa tiếp liên (Contingency):. Mệnh đề hệ quả. Tương đương Logic (LOGICALLY EQUIVALENT).
Tổng kết chương 1. Bài tập chương 1 .24 Trang 28 Chương 2: Suy luận toán học & Các phương pháp chứng minh CHƯƠNG 2 : SUY LUẬN TOÁN HỌC & CÁC PHƯƠNG PHÁP CHỨNG MINH 2. Tổng quan • Mục tiêu của chương 1 Học xong chương này, sinh viên phải nắm bắt được các vấn đề sau: - Khái niệm về suy luận toán học - Các phương pháp chứng minh và biết vận dụng các phương pháp này để chứng minh một bài toán cụ thể. • Kiến thức cơ bản cần thiết Các kiến thức cơ bản trong chương này bao gồm: - Các phép toán đại số, hình học cơ bản để có thể đưa ra ví dụ minh họa trong từng phương pháp.
- Hiểu rõ qui tắc của phép kéo theo ở chương 1. • Tài liệu tham khảo Phạm văn Thiều, Đặng Hữu Thịnh. Toán rời rạc ứng dụng trong tin học. Nhà xuất bản Khoa học và Kỹ thuật, Hà Nội - 1997 (chương 3, trang 208 - 228).
• Nội dung cốt lõi - Khái niệm về suy luận toán học - Trình bày các phương pháp chứng minh bao gồm:. Chứng minh rỗng. Chứng minh tầm thường. Chứng minh trực tiếp.
Chứng minh gián tiếp. Chứng minh phản chứng. Chứng minh qui nạp Trang 28 Chương 2: Suy luận toán học & Các phương pháp chứng minh 2. Suy luận toán học 2.
Khái niệm Suy luận được xem là một trong những nền tảng xây dựng nên các ngành khoa học tự nhiên. Từ xưa đến nay, nhờ suy luận mà người ta có thể nhận thức được cái chưa biết từ những cái đã biết. Suy luận còn là cơ sở của sự sáng tạo. Từ các phán đoán, đưa đến các chứng minh để chấp nhận hay bác bỏ một vấn đề nào đó.
Suy luận toán học dựa trên nền tảng của các phép toán mệnh đề, chủ yếu là phép kéo theo. Để chứng minh một vấn đề nào đó, thông thường người ta phải xác định điểm ban đầu (có thể gọi là giả thiết) và điểm kết thúc (gọi là kết luận). Quá trình đi từ giả thiết đến kết luận gọi là quá trình chứng minh và quá trình này đươc thực thi bằng cách nào thì gọi đó là phương pháp chứng minh. Các phương pháp chứng minh là rất quan trọng vì không những chúng thường được sử dụng trong toán học mà còn được áp dụng nhiều trong tin học.
Ví dụ, sự kiểm tra tính đúng đắn của một chương trình, của một hệ điều hành, xây dựng các luật suy diễn trong lĩnh vực trí tuệ nhận tạo. Do đó, chúng ta cần phải nắm vững các phương pháp chứng minh. Tuy nhên, có những phương pháp chứng minh đúng vì nó được dựa trên cơ sở của một mệnh đề đúng (hằng đúng) và có những phương pháp chứng minh sai. Các phương pháp chứng minh sai này là cố ý hoặc vô ý.
Khi phương pháp chứng minh dựa trên một hằng sai thì sẽ mang lại kết quả sai nhưng người ta vẫn cho là đúng thì được gọi là cố ý. Đôi khi có những phương pháp chứng minh dựa trên một tiếp liên (có khi mệnh đề là đúng nhưng cũng có lúc sai) mà người ta tưởng lầm là hằng đúng nên cho là kết quả bao giờ cũng đúng thì trường hợp này gọi là vô ý (hay ngộ nhận). Sau đây, chúng ta sẽ đi tìm hiểu các qui tắc suy luận. Các qui tắc suy luận Như đã giới thiệu ở trên, những suy luận có dùng các qui tắc suy diễn gọi là suy luận có cơ sở.
Khi tất cả các suy luận có cơ sở là đúng thì sẽ dẫn đến một kết luận đúng. Một suy luận có cơ sở có thể dẫn đến một kết luận sai nếu một trong các mệnh đề đã dùng trong suy diễn là sai. Sau đây là bảng các qui tắc suy luận đúng. Trang 29 Chương 2: Suy luận toán học & Các phương pháp chứng minh Quy Tắc Hằng đúng Tên Luật P P→(P∨Q) Cộng ∴P ∨Q P∧Q (P∧Q)→P Rút gọn ∴P P (P∧(P→Q))→Q Modus Ponens P→Q ∴Q ¬Q (¬Q∧(P→Q)) → ¬P Modus Tollens P→Q ∴ ¬P P→Q ((P→Q)∧(Q→R)) → Tam đoạn luận giả Q→R định (P→R) ∴P → R P∨Q (P∨Q) → Q Tam đoạn luận tuyển ∴Q Trong các phân số của qui tắc thì các giả thiết được viết trên tử số, kết luận được viết dưới mẫu số.
Kí hiệu ∴ có nghĩa là "vậy thì", "do đó",. Ví dụ : Qui tắc suy luận nào là cơ sở của suy diễn sau : • " Nếu hôm nay trời mưa thì cô ta không đến, Nếu cô ta không đến thì ngày mai cô ta đến, Vậy thì, nếu hôm nay trời mưa thì ngày mai cô ta đến." Đây là suy diễn dựa trên qui tắc tam đoạn luận giả định. • "Nếu hôm nay tuyết rơi thì trường đại học đóng cửa. Hôm nay trường đại học không đóng cửa.
Do đó, hôm nay đã không có tuyết rơi " Đây là suy diễn dựa trên qui tắc Modus Tollens • " Alice giỏi toán. Do đó, Alice giỏi toán hoặc tin" Đây là suy diễn dựa trên qui tắc cộng. Ngụy biện Trang 30 Chương 2: Suy luận toán học & Các phương pháp chứng minh Các phương pháp chứng minh sai còn được gọi là ngụy biện. Ngụy biện giống như qui tắc suy luận nhưng không dựa trên một hằng đúng mà chỉ là một tiếp liên.
Đây chính là sự khác nhau cơ bản giữa suy luận đúng và suy luận sai. Loại suy luận sai này được gọi là ngộ nhận kết luận. Ví dụ : Xét xem suy diễn sau là có cơ sở đúng không ? " Nếu bạn đã giải hết bài tập trong sách toán rời rạc 2 này thì bạn nắm vững logic. Bạn nắm vững logic vậy thì bạn đã giải hết bài tập trong sách toán rời rạc 2 này".
Nhận thấy suy diễn này là dựa trên mệnh đề sau : ((P→Q) ∧ Q) → P Trong đó: P = "Bạn đã giải hết bài tập trong sách toán rời rạc 2" Q = "Bạn nắm vững logic" Mệnh đề ((P→Q) ∧ Q) → P không phải là hằng đúng vì nó sẽ sai khi P là F và Q là T. Do đó, suy diễn này không hoàn toàn có cơ sở đúng.