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  TS. Đặng Xuân Thọ  Mobile: 091.2629.383  Email: thodx@hnue.edu.vn  Website: Toán rời rạc - ĐHSPHN 2 NỘI DUNG  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 3 Chương 4. Suy luận và kiểm chứng chương trình  Đ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 4 Các quy tắc suy luận Toán Rời Rạc - ĐHSPHN 5 Các suy diễn có cơ sở  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 6 Các suy diễn có cơ sở  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 7 Các suy diễn có cơ sở  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 8 Các suy diễn có cơ sở  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 9 Các suy diễn có cơ sở  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 10 Các suy diễn có cơ sở  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 11 Các suy diễn có cơ sở 12 Các suy diễn có cơ sở 13 Luyện tập  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 14 Vị ngữ, lượng từ, định lý Toán Rời Rạc - ĐHSPHN 15 Biến và vị ngữ  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 16 Lượng từ với mọi  Đị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 17 Lượng từ với mọi  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 18 Lượng từ tồn tại  Đị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 19 Lượng từ tồn tại  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 20 Biến ràng buộc  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 21 Biến ràng buộc  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 22 Biến ràng buộc  Quy tắc phủ định  Ví dụ:  Phủ định của lượng từ với mọi: “Với mọi x ta có x2  0”  Là lượng từ tồn tại: “Tồn tại x sao cho x2 < 0”  Phủ định của lượng từ tồn tại: “Tồn tại x sao cho x2+1=0”  Là lượng từ với mọi: “Với mọi x ta có x2+10” ( ) ( )xP x xP x  ( ) ( )xP x xP x  Toán Rời Rạc - ĐHSPHN 23 Định lý và lượng từ  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 24 Định lý và lượng từ  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  a) nghiệm cụ thể 𝑥1,2 = −𝑎± 𝑎2+4 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 25 Luyện tập Toán Rời Rạc - ĐHSPHN 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ử. Đệ Quy Toán Rời Rạc - ĐHSPHN 27 Đệ Quy  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 28 Định nghĩa các hàm bởi đệ quy  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 29 Định nghĩa các hàm bởi đệ quy  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 30 K62 – CTDL> Tháng thứ 3 Tháng thứ 4 Tháng thứ 5 Tháng thứ 2 Tháng thứ 1 31 K62 – CTDL> 𝐹𝑖𝑏 𝑛 = 1 𝑛 ≤ 2 𝐹𝑖𝑏 𝑛 − 1 + 𝐹𝑖𝑏 𝑛 − 2 𝑛 ≥ 2 Định nghĩa các tập hợp bởi đệ quy  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 32 Kiểm Chứng Chương Trình Toán Rời Rạc - ĐHSPHN 33 Kiểm chứng chương trình  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 34 Kiểm chứng chương trình  Đị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 35 Kiểm chứng chương trình  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 36 Các quy tắc suy luận  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. 1 2 1 2 {S }q q{S }r {S S }r p p Toán Rời Rạc - ĐHSPHN 37 Các quy tắc suy luận  Câu lệnh điều kiện: If (điều kiện) r then S ( ){S}q ( ) q {If r then S}q p r p r p     1. CM p đúng, r đúng thì q đúng khi S kết thúc 2. CM p đúng, r sai thì q đúng Toán Rời Rạc - ĐHSPHN 38 Các quy tắc suy luận  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 39 Các quy tắc suy luận  Câu lệnh điều kiện: If (điều kiện) r then S1 else S2 1 2 1 2 ( ){S }q ( ){ }q {If r then S else S }q p r p r S p    1. CM p đúng, r đúng thì q đúng khi S1 kết thúc 2. CM p đúng, r sai thì q đúng khi S2 kết thúc Toán Rời Rạc - ĐHSPHN 40 Các quy tắc suy luận  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 41 Các quy tắc suy luận  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 42 Các quy tắc suy luận  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: ( ){S}q {W r do S}(p r) p r p hile    Toán Rời Rạc - ĐHSPHN 43 p Các quy tắc suy luận  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 44 Các quy tắc suy luận  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 45 Đoạn chương trình nhiều câu lệnh  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); if n<0 then a:= - n else a:= n; k := 0; x := 0; while k<a do begin x:=x+m; k:=k+1; end; if n<0 then product := -x else product := x; S1 S2 S3 S4 Toán Rời Rạc - ĐHSPHN 46 q: “(a=|n|)” r: “(k=0)(x=0)” s: “x=ma và a=|n|” t: “product = mn” p: “m và n là các số nguyên” Đoạn chương trình nhiều câu lệnh  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 47 Luyện tập  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 48 Luyện tập  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 49 THANK YOU!