Bài giảng Toán rời rạc - Chương 4: Suy luận và kiểm chứng chương trình - Bùi Thị Thủy

 TOÁN RỜI RẠC 
(DISCRETE MATHEMATICS) 
 Bùi Thị Thủy 
 Đặng Xuân Thọ 
 Support 
2 
  TS. Đặng Xuân Thọ 
  Mobile: 091.2629.383 
  Email: thodx@hnue.edu.vn 
  Website:  
 Toán rời rạc - ĐHSPHN 
 NỘI DUNG 
3 
  Chương 1. Logic mệnh đề 
  Chương 2. Lý thuyết tập hợp 
  Chương 3. Một số công thức tổ hợp 
  Chương 4. Suy luận và kiểm chứng chương trình 
  Chương 5. Đại số Boole và cấu trúc mạch logic 
  Chương 6. Thuật toán 
  Chương 7. Lý thuyết đồ thị 
 Toán Rời Rạc - ĐHSPHN 
 Chương 4. Suy luận và kiểm chứng 
 chương trình 
4 
  Điều cần nhất cho người học CNTT là tư duy 
 chính xác phải được hình thành ngay từ đầu. 
  Mục tiêu của chương là cung cấp 
  Những suy luận đúng đắn 
  Những công cụ xây dựng nên các suy luận đó 
  Làm thế nào để kiếm chứng 1 chương trình 
 máy tính? 
  Thử với dữ liệu có sẵn? 
  Tính đúng đắn chỉ có thể bảo đảm được bằng 
 chứng minh nó luôn tạo ra kết quả đúng. 
 Toán Rời Rạc - ĐHSPHN 
5 Các quy tắc suy luận 
 Toán Rời Rạc - ĐHSPHN 
 Các suy diễn có cơ sở 
6 
  Suy diễn trực tiếp 
  Ví dụ: 
  p: “Trời mưa”; q: “Chúng ta không đi làm” 
  → 푞: “Nếu trời mưa thì chúng ta không đi làm” 
  Nếu p xảy ra, và nếu suy diễn này là đúng thì q 
 xảy ra 
 Toán Rời Rạc - ĐHSPHN 
 Các suy diễn có cơ sở 
7 
  Luật cộng 
  Ví dụ: 
  p: “Bây giờ trời đang mưa”; q: ”Trời tối” 
  Luật cộng có thể nói: “Bây giờ trời đang mưa 
 hoặc trời tối”. 
 Toán Rời Rạc - ĐHSPHN 
 Các suy diễn có cơ sở 
8 
  Luật rút gọn 
  Ví dụ: 
  p ^ q: “Bây giờ trời đang mưa và trời tối” 
  Thì ta có thể suy ra: “Bây giờ trời đang mưa” 
 Toán Rời Rạc - ĐHSPHN 
 Các suy diễn có cơ sở 
9 
  Luật gián tiếp 
  Ví dụ: 
  p: “Trời mưa”; q: “Trời sấm chớp” 
  Như vậy nếu mệnh đề “Trời mưa thì trời sấm 
 chớp” là đúng và không có “Trời sấm chớp” thì 
 suy ra không có “Trời mưa”. 
 Toán Rời Rạc - ĐHSPHN 
 Các suy diễn có cơ sở 
10 
  Tam đoạn luận 
  Ví dụ: 
  p: “Trời mưa”; q: “Chúng ta không đi chơi ngoài 
 trời hôm nay”; r: “Chúng ta đi chơi ngoài trời ngày 
 mai” 
  Như vậy chúng ta suy ra là “Trời mưa hôm nay 
 thì chúng ta đi chơi ngoài trời ngày mai”. 
 Toán Rời Rạc - ĐHSPHN 
 Các suy diễn có cơ sở 
11 
  Luật loại trừ 
  Ví dụ: 
  p: “Tôi có mặt tại hiện trường vụ án”; q: “Anh có 
 mặt tại hiện trường vụ án”. 
  Nếu (p v q) và p là đúng thì suy ra “Anh có mặt 
 tại hiện trường vụ án”. 
 Toán Rời Rạc - ĐHSPHN 
 Các suy diễn có cơ sở 
12 
 Các suy diễn có cơ sở 
13 
 Luyện tập 
14 
  Quy tắc suy diễn nào được sử dụng trong các lập luận sau: 
 1. Ai học giỏi môn Toán cũng sẽ học giỏi môn Toán hoặc môn 
 Tin. 
 2. Nêu bạn giỏi cả hai môn Toán và Văn thì bạn học giỏi môn 
 Toán. 
 3. Nếu trời mưa thì trận bóng đá sẽ bị hoãn lại. Hôm nay trời 
 mưa thật, thế thì trận bóng đá chắc chắn sẽ bị hoãn lại rồi. 
 4. Nếu hôm nay trời mưa thì trận đá bóng sẽ bị hoãn lại. Trận 
 bóng đá đã diễn ra, do vậy hôm nay trời không mưa. 
 5. Nếu bạn bơi lâu dưới nắng thì da bạn sẽ bị rám nắng. Da bạn 
 bị rám nắng thì trông thật là đen. Vậy nếu bạn bơi lâu dứoi 
 nắng thì trông bạn thật đen. 
 6. Nếu bạn làm bài tập thật chăm chỉ thì bạn có thể nắm vững 
 giáo trình này. Nếu bạn nắm vững giáo trình thì bạn sẽ thi đỗ 
 kỳ thi tốt nghiệp. Vậy nếu bạn làm bài tập thật chăm chỉ thì bạn 
 sẽ thi đỗ kỳ thi tốt nghiệp. 
 Toán Rời Rạc - ĐHSPHN 
15 Vị ngữ, lượng từ, định lý 
 Toán Rời Rạc - ĐHSPHN 
 Biến và vị ngữ 
16 
  Ví dụ: 
  “x là số nguyên” 
  “x thuộc đoạn [0, 1]” 
  Biến là chủ ngữ, khẳng định tính chất của x là 
 vị ngữ. 
  Sau đây ta sẽ xét câu có dạng P(x), mệnh đề 
 của x, tức là câu nói mà giá trị chân lý của nó 
 phụ thuộc vào biến x. 
  Ví dụ: x = 3 
 Toán Rời Rạc - ĐHSPHN 
 Lượng từ với mọi 
17 
  Định nghĩa: Cho trước một hàm mệnh đề P(x) 
 xác định trên một tập X. Khi đó câu “P(x) đúng 
 cho mọi giá trị x X” là một mệnh đề, kí hiệu 
 x P(x). Mệnh đề này gọi là lượng từ với mọi 
 của hàm mệnh đề P(x) cho trước. 
  Ví dụ: 
  P(x): “x tốt nghiệp”; x là biến “sinh viên”; X là miền 
 “sinh viên khóa 53” 
 xP(x):“mọi sinh viên khóa 53 đều đã tốt nghiệp” 
 Toán Rời Rạc - ĐHSPHN 
 Lượng từ với mọi 
18 
  Chú ý: 
  Lượng tử với mọi sai nếu có ít nhất một giá trị 
 của biến làm hàm mệnh đề sai. 
  Nếu miền xác định của P(x) có n phần tử (1, 2, 
 , n) thì xP(x) P(1)  P(2)    P(n) 
 Toán Rời Rạc - ĐHSPHN 
 Lượng từ tồn tại 
19 
  Định nghĩa: Cho trước một hàm mệnh đề P(x) 
 xác định trên một tập X. Khi đó câu “tồn tại x 
 X sao cho P(x) đúng” là một mệnh đề, kí hiệu 
 x P(x). Mệnh đề này gọi là lượng từ tồn tại 
 của hàm mệnh đề P(x) cho trước. 
  Ví dụ: 
  Cho P(x): “x2 + 1 = 0” trên miền số thực 
  xP(x): “tồn tại x sao cho x2 + 1 = 0” có giá trị F 
 Toán Rời Rạc - ĐHSPHN 
 Lượng từ tồn tại 
20 
  Chú ý: 
  Lượng tử tồn tại chỉ sai khi mọi giá trị của biến 
 đều làm hàm mệnh đề bị sai. 
  Nếu miền xác định của P(x) có n phần tử (1, 2, 
 , n) thì xP(x) P(1)  P(2)    P(n) 
 Toán Rời Rạc - ĐHSPHN 
 Biến ràng buộc 
21 
  Trong hàm logic nhiều biến, không phải biến 
 nào cũng được lựa chọn tự do, có những biến 
 có miền xác định phụ thuộc vào biến khác. 
  Thường được thể hiện trong phát biểu của 
 lượng tử tồn tại 
  Ví dụ: “Mọi số tự nhiên n đều có một ước 
 khác nó”. 
  Nếu gọi B(n, m) là hàm mệnh đề “m là ước của n” 
 thì ta có: nm((m n) B(n, m)) (m phụ thuộc n) 
 Toán Rời Rạc - ĐHSPHN 
 Biến ràng buộc 
22 
  Cho hàm mệnh đề P(x, y) với hai biến x, y, 
 trong đó y ràng buộc bởi x. Có các khả năng 
 sau: 
  xyP(x, y): với mọi x, P(x, y) luôn đúng cho mọi y 
  xyP(x, y): với mọi x, P(x, y) đúng cho một y nào đó 
  xyP(x, y): tồn tại x, P(x, y) luôn đúng cho mọi y 
  xyP(x, y): tồn tại x, P(x, y) đúng cho một y nào đó 
 Toán Rời Rạc - ĐHSPHN 
 Biến ràng buộc 
23 
  Quy tắc phủ định 
 xP()() x  xP x
 xP()() x  xP x
  Ví dụ: 
 2
  Phủ định của lượng từ với mọi: “Với mọi x ta có x 0” 
 Là lượng từ tồn tại: “Tồn tại x sao cho x2 < 0” 
 2
  Phủ định của lượng từ tồn tại: “Tồn tại x sao cho x +1=0” 
 Là lượng từ với mọi: “Với mọi x ta có x2+1 0” 
 Toán Rời Rạc - ĐHSPHN 
 Định lý và lượng từ 
24 
  Chứng minh tồn tại: chứng minh cho xP(x) 
  Phương pháp chứng minh: 
  Chứng minh kiến thiết: xác định giá trị x thỏa điều 
 kiện P(x). 
  Chứng minh không kiến thiết: đưa ra những lý 
 luận xác nhận sự tồn tại x, sao cho P(x) thỏa. 
 Toán Rời Rạc - ĐHSPHN 
 Định lý và lượng từ 
25 
  Ví dụ: chứng minh các phương trình sau luôn có 
 nghiệm với các số thực a tùy ý: 
  a) x2 + ax – 1 = 0 
  b) x2003 + ax + 1 = 0 
 − ± 2+4
  a) nghiệm cụ thể = 
 1,2 2
  b) với x > max{|a|,1} thì f=x2003+ax+1>0 
 với x < min{-|a|,-2} thì f=x2003+ax+1<0 
 do f là hàm liên tục nên tồn tại x0 sao cho f(x0)=0 
 Toán Rời Rạc - ĐHSPHN 
 Luyện tập 
26 
  Cho P(x) là câu “x học ở lớp hơn 5 giờ mỗi 
 ngày trong tuần”. Hãy diễn đạt các lượng từ 
 sau thành các câu thông thường: 
  x P(x) xP(x) 
  x≦P(x) x≦P(x) 
  Dùng lượng tử diễn đạt các câu nói sau, phủ 
 định chúng rồi dịch ngược lại: 
  Mọi người ai cũng thích môn Toán rời rạc. 
  Có một người đã học tất cả các môn Toán. 
  Chưa có ai nhìn thấy chiếc máy tính lượng tử. 
 Toán Rời Rạc - ĐHSPHN 
27 Đệ Quy 
 Toán Rời Rạc - ĐHSPHN 
 Đệ Quy 
28 
  Khái niệm 
  Đệ quy là cách định nghĩa một đối tượng qua 
 chính nó 
  Được sử dụng nhiều trong lập trình 
  Định nghĩa các hàm số, các tập hợp, các dãy số 
 Tam giác Sierpinski 
 Định nghĩa các hàm bởi đệ quy 
29 
  Quy tắc xây dựng hàm dạng f(n) 
  Xác định giá trị của hàm tại n = 0 
  Xác định mối quan hệ của f(n + 1) với f(n) 
  Ví dụ: f(n) = n! 
  f(0) = 1 
  f(n+1) = (n+1) f(n) 
 Toán Rời Rạc - ĐHSPHN 
 Định nghĩa các hàm bởi đệ quy 
30 
  Dãy số Fibonaci 
  Bài toán cổ về việc sinh sản các cặp thỏ: 
  Các con thỏ không bao giờ chết 
  Hai tháng sau khi ra đời một cặp thỏ mới sẽ sinh 
 ra một cặp thỏ con (một đực, một cái) 
  Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo 
 chúng lại sinh ra được một cặp con mới 
  Giả sử bắt đầu từ một cặp mới ra đời thì đến 
 tháng thứ n sẽ có bao nhiêu cặp? 
 Toán Rời Rạc - ĐHSPHN K62 – CTDL> 
 Tháng thứ 1 
31 
 Tháng thứ 2 
 Tháng thứ 3 
 Tháng thứ 4 
 Tháng thứ 5 
 1 푛 ≤ 2
 퐹푖 푛 = 
 퐹푖 푛 − 1 + 퐹푖 푛 − 2 푛 ≥ 2
 K62 – CTDL> 
 Định nghĩa các tập hợp bởi đệ quy 
32 
  Quy tắc xây dựng 
  Đưa ra tập xuất phát 
  Xây dựng phần tử mới từ những phần tử đã biết 
  Ví dụ: cho B là tập hữu hạn các chữ cái. Tập 
 B* là các từ xây dựng trên B là tập thỏa mãn: 
  Từ rỗng thuộc B* 
  Nếu w B* và b B* thì wb B* 
 Toán Rời Rạc - ĐHSPHN 
33 Kiểm Chứng Chương Trình 
 Toán Rời Rạc - ĐHSPHN 
 Kiểm chứng chương trình 
34 
  Khái niệm 
  Các bước chứng minh tính đúng đắn của một 
 chương trình: 
  Chứng minh chương trình khi kết thúc cho kết quả 
 đúng 
  Chứng minh chương trình luôn dừng sau một thời 
 gian chạy hữu hạn 
 Toán Rời Rạc - ĐHSPHN 
 Kiểm chứng chương trình 
35 
  Định nghĩa. Chương trình hay đoạn chương 
 trình S được gọi là đúng bộ phận đối với mệnh 
 đề khẳng định đầu p và mệnh đề khẳng định 
 cuối q, nếu p là đúng với các giá trị vào của S 
 và nếu S kết thúc thì q đúng với các giá trị đầu 
 ra của S. 
  Kí hiệu: p{S}q 
 Toán Rời Rạc - ĐHSPHN 
 Kiểm chứng chương trình 
36 
  Ví dụ: Cho đoạn chương trình: 
 y := 3; 
 z := x * y; 
 Hãy chỉ ra đoạn chương trình trên đúng với khẳng 
 định đầu p : “x = 0” và khẳng định cuối q : “z = 0” 
 Toán Rời Rạc - ĐHSPHN 
 Các quy tắc suy luận 
37 
  Quy tắc hợp thành 
  Chia nhỏ chương trình thành các đoạn chương 
 trình con và chứng minh mỗi đoạn chương trình 
 là đúng. 
 p{S1 }q
 q{S2 }r
  p{S12 S }r
 Toán Rời Rạc - ĐHSPHN 
 Các quy tắc suy luận 
38 
  Câu lệnh điều kiện: If (điều kiện) r then S 
 1. CM p đúng, r đúng thì 
 (pr ){S}q
 q đúng khi S kết thúc 
 (pr  ) q
  p{If r then S}q
 2. CM p đúng, r sai thì q 
 đúng 
 Toán Rời Rạc - ĐHSPHN 
 Các quy tắc suy luận 
39 
  Câu lệnh điều kiện: If (điều kiện) r then 
  Ví dụ: CMR đoạn chương trình If x>y then y:=x 
 đúng với khẳng định đầu p = T và khẳng định cuối 
 q: “y x” 
  Chứng minh: 
  Giả sử p = T đúng và có x > y thì y được gán giá trị 
 của x, tức là y = x thì khẳng định q: “y x” là đúng. 
  Khi p = T đúng và điều kiện x > y sai, nghĩa là x ≤ y thì 
 khẳng định q: “y x” vẫn đúng. 
 Toán Rời Rạc - ĐHSPHN 
 Các quy tắc suy luận 
40 
  Câu lệnh điều kiện: If (điều kiện) r then S1 
 else S2 
 1. CM p đúng, r đúng thì 
 q đúng khi S1 kết thúc 
 (pr ){S1 }q
 (p r ){ S2 }q
 p{If r then S12 else S }q
 2. CM p đúng, r sai thì q 
 đúng khi S2 kết thúc 
 Toán Rời Rạc - ĐHSPHN 
 Các quy tắc suy luận 
41 
  Ví dụ: CMR đoạn chương trình 
 If (x<0) then (abs := -x) else (abs := x) 
 đúng với khẳng định đầu p = T và khẳng định cuối 
 q: “abs = |x|”. 
  Chứng minh: 
  Giả sử p = T đúng và có x<0 thì abs được gán giá 
 trị - x, tức là abs = |x|. 
  Khi p = T đúng và điều kiện x<0 sai, nghĩa là x 0 
 thì abs được gán giá trị x, nghĩa là abs = x = |x|. 
 Toán Rời Rạc - ĐHSPHN 
 Các quy tắc suy luận 
42 
  Câu lệnh vòng lặp: While (điều kiện) r do S 
  S được thực hiện mãi cho tới khi r trở thành sai 
  Bất biến vòng lặp: là một khẳng định vẫn đúng 
 sau khi thực hiện S 
  Như thế, nếu (pr){S}p đúng thì p là bất biến 
 vòng lặp 
 Toán Rời Rạc - ĐHSPHN 
 Các quy tắc suy luận 
43 
  Câu lệnh vòng lặp: While (điều kiện) r do S 
  Giả sử p là một bất biến vòng lặp, thì p đúng 
 trước khi đoạn chương trình thực hiện và p, r 
 đúng sau khi kết thúc. 
  Quy tắc suy luận: 
 (pr ){S}qp 
 p{W hile r do S}(p   r)
 Toán Rời Rạc - ĐHSPHN 
 Các quy tắc suy luận 
44 
  Câu lệnh vòng lặp: While (điều kiện) r do S 
  Ví dụ: Dùng bất biến vòng lặp CM đoạn 
 chương trình: (n nguyên dương) 
 i := 1; giaithua := 1; 
 while (i < n) do 
 begin 
 i := i + 1; 
 giaithua := giaithua * i; 
 end; 
 là đúng với kết thúc: giaithua = n! 
 Toán Rời Rạc - ĐHSPHN 
 Các quy tắc suy luận 
45 
  Giả sử p: “giaithua := i! cho mọi i n” 
  Với i = 1 thì giaithua = 1 = 1! Nên p đúng 
  Giả sử p đúng sau i vòng lặp với i < n, khi đó 
 giaithua = i! 
  Vòng lặp được thực hiện thêm lần nữa, khi i 
 tăng lên 1 thành i+1 và vẫn chưa vượt n. Khi 
 đó giaithua = i! * (i+1) = (i+1)!. 
  Như vậy sau vòng i+1 thì p vẫn còn đúng. Vậy 
 p là bất biến vòng lặp. 
 Toán Rời Rạc - ĐHSPHN 
 Đoạn chương trình nhiều câu lệnh 
46 
  Ví dụ: hãy kiểm chứng chương trình sau đúng là 
 chương trình tính tích của hai số nguyên 
 procedure multiply(m,n: integer); p: “m và n là các số nguyên” 
 if n<0 then a:= - n 
 else a:= n; S1 q: “(a=|n|)” 
 k := 0; 
 r: “(k=0)(x=0)” 
 x := 0; S2 
 while k<a do 
 begin 
 x:=x+m; S3 s: “x=ma và a=|n|” 
 k:=k+1; 
 end; 
 if n<0 then product := -x 
 t: “product = mn” 
 else product := x; S4 
 Toán Rời Rạc - ĐHSPHN 
 Đoạn chương trình nhiều câu lệnh 
47 
  Gọi p là khẳng định đầu “m và n là các số 
 nguyên” 
  q là mệnh đề “p(a=|n|)” 
  r là mệnh đề “q(k=0)(x=0)” 
  s là mệnh đề “x=ma và a=|n|” 
  t là mệnh đề “product = mn” 
  Dễ thấy p{S1}q, q{S2}r, r{S3}s, s{S4}t là đúng 
 Toán Rời Rạc - ĐHSPHN 
 Luyện tập 
48 
  Hãy kiểm chứng đoạn chương trình 
 x := 3; 
 z := x + y; 
 if y>0 then z := z+1 
 else z := 0; 
 là đúng với khẳng định đầu y=3 và khẳng định 
 cuối z=7. 
 Toán Rời Rạc - ĐHSPHN 
 Luyện tập 
49 
  Dùng bất biến vòng lặp chứng minh đoạn 
 chương trình tính lũy thừa bậc nguyên dương 
 n của số thực x là đúng: 
 luythua := 1; 
 i := 0; 
 while i < n begin 
 luythua := luythua * x; 
 i := i + 1; 
 end; 
 Toán Rời Rạc - ĐHSPHN 
THANK YOU!