Lý Thuyết Và Bài Tập Toán Học Rời Rạc Chương Logic - Tài Liệu Text

Có thể bạn quan tâm

Tải bản đầy đủ (.pdf) (40 trang)

Trang chủ

Giáo án - Bài giảng

Toán học

Lý thuyết và bài tập Toán học rời rạc Chương Logic

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (824.74 KB, 40 trang )

Chương 3. Lôgic và suy luận toán họcChương 3. LÔGIC VÀ SUY LUẬN TOÁN HỌCI. ĐẠI SỐ MỆNH ĐỀ1. Mệnh đề sơ cấpCác phát biểu khẳng định không thể chia nhỏ được và có giá trị hoặc đúng (1, true, yes)hoặc sai (0, false, no) được gọi là mệnh đề sơ cấp. Giá trị của mệnh đề sơ cấp được gọi là giá trịchân lý. Kí hiệu các mệnh đề sơ cấp bởi các chữ cái X, Y, Z, ...Trong bài giảng này để biểu thị giá trị chân lý "đúng", "sai" ta dùng 1 (true) và 0 (false).Ví dụ 1: "3 là số nguyên tố" là một mệnh đề có giá trị chân lý là 1 "x chia hết cho 3" không phải là mệnh đề vì nó chỉ trở thành khẳng định với x cụ thểhoặc khi thêm các lượng từ với mọi, tồn tại vào trước mệnh đề. "Bao giờ cho đến tháng mười" không phải là một mệnh đề vì nó không phải là khẳngđịnh.2. Mệnh đề, công thức mệnh đềCác mệnh đề được thành lập từ các mệnh đề sơ cấp bằng các phép toán mệnh đề.a. Phép toánCác phép toán : hội (), tuyển (), phủ định (, _), kéo theo () . Bảng chân trịXYXYXYXXY111001100000010011000111Các phép toán trên tương đương với các liên từ "và", "hoặc", "không", "kéo theo"Chú ý bảng chân trị của phép kéo theo  qua các câu sau đây : Vì mặt trời mọc ở hướng đông nên trái đất tròn Vì mặt trời mọc ở hướng tây nên trái đất tròn Vì mặt trời mọc ở hướng đông nên trái đất vuông Vì mặt trời mọc ở hướng tây nên trái đất vuôngVề mặt thực tế khó nói được tính đúng sai của 4 khẳng định dạng trên. Tuy nhiên áp dụnghệ toán mệnh đề có thể thấy các câu i. ii. là đúng và câu iii. là sai và đặc biệt một câu vô nghĩanhư câu iv. lại là đúng.b. Công thức mệnh đề1Chương 3. Lôgic và suy luận toán họci.ii.Các giá trị 1, 0 và các mệnh đề sơ cấp : X, Y, Z, ... là các công thức mệnh đềNếu A, B, C ... là các công thức mệnh đề thì (A  B), (A  B), (A), (A  B) là cáccông thức mệnh đề.Dựa vào định nghĩa trên để nhận biết một công thức. Ví dụ : A  B   A không là côngthức. Để đơn giản (nếu không nhầm lẫn) có thể bỏ bớt các dấu ngoặc bao ngoài.Ví dụ 2: "Nếu anh ta cao kều, đăm chiêu và lặng lẽ thì trời mưa".Có nhiều cách để biểu diễn câu trên thành một công thức mệnh đề : Nếu đặt X, Y, Z, T tương ứng là các mệnh đề sơ cấp : "Anh ta cao kều"; "Anh ta đămchiêu"; "Anh ta lặng lẽ", "Trời mưa" thì ta có công thức mệnh đề là (X  Y  Z)  T Nếu đặt A là công thức : "Anh ta cao kều, đăm chiêu" ; B là công thức "lặng lẽ" và C làcông thức "Trời mưa" thì công thức cho câu trên là (A  B)  C. Đặt A = "Nếu anh ta cao kều, đăm chiêu và lặng lẽ thì trời mưa". Công thức là A.Như vậy giá trị của một công thức (hoặc của mệnh đề) cũng được tính qua giá trị của cáccông thức thành phần, như A, B, C hoặc A, B, C kết hợp bởi các phép toán trên bằng cách lậpbảng chân trị. Vì vậy các công thức mệnh đề cũng được xem là một mệnh đề.3. Tính tương đương của các công thứcHai công thức được gọi là tương đương nếu nó bằng nhau với mọi bộ giá trị của các mệnhđề sơ cấp tham gia trong công thức (thực chất nó là tương đương lôgic, nghĩa là chỉ trùng nhau vềmặt giá trị chân lý chứ không trùng nhau hoàn toàn về mặt cấu trúc). Kí hiệu A  B để chỉ haicông thức A và B tương đương.Để kiểm tra tính tương đương ta lập bảng chân trị. Các phần sau sẽ cho thấy các cách khácđể kiểm tra tính tương đương (ví dụ dùng các phép biến đổi tương đương).Ví dụ 3: Lập bảng chân trị cho các công thức tương đương sau (bài tập)i. A  B  A  Bii. (A  B)  A  Biii. A  ABằng cách lập bảng chân trị ta dễ dàng chứng minh được các cặp công thức tương đươngsau :Một số công thức tương đươngTên gọiTương đươngLuật đồng nhấtA1A0ALuật nuốtA  1  1; A  0  0, A  A  1; A  A  0Luật luỹ đẳngAAAAALuật phủ định képA  ALuật hấp thụA  (A  B)  A; A  (A  B)  ALuật giao hoánA  B  B  A; A  B  B  BLuật kết hợp(A  B)  C  A  (B  C); (A  B)  C  A  (B  C)2Chương 3. Lôgic và suy luận toán họcLuật phân phốiA  (B  C)  (A  B)  (A  C);A  (B  C)  (A  B)  (A  C)Luật De Morgan(A  B)  A  B; (A  B)  A  BCác công thức khácA  B  A  BTừ bảng các công thức tương đương trên (mà ta có thể xem như các luật) ta có thể sử dụngđể tìm tương đương rút gọn của các công thức khác.Ví dụ 4: Chứng minh rằng (A  (A  B))  A  BA  (A  B)):A  (A  B):(A  A)  (A  B):0  (A  B):(A  B)Ví dụ 2 : Chứng minh A  (A  B) = A(A  0)  (A  B):A  (0  B):A  (B  0):A0:A:De MorganDe Morganphân phốiđồng nhấtđồng nhấtphân phốigiao hoánnuốtđồng nhất(x + 0y = (x+0)(x+y))4. Công thức đồng nhất đúng (sai, tiếp liên)c. Định nghĩaNếu hoàn toàn đúng (đồng nhất đúng) hoặc hoàn toàn sai (đồng nhất sai) với mọi bộ giá trịcủa các mệnh đề sơ cấp. Trường hợp còn lại gọi là tiếp liên.Nếu A là đồng nhất đúng thì A là đồng nhất sai và ngược lại.Ví dụ 5: A  A, A  A, A, là các công thức đồng nhất đúng, đồng nhất sai, tiếp liên.Để chứng minh A là đồng nhất đúng ta có thể chứng minh bằng nhiều cách : Lập bảng chân trị (trong trường hợp ít mệnh đề sơ cấp) khi đó cột chân trị của A hoàntoàn bằng 1. Chứng minh A  1 bằng các biến đổi tương đương dựa trên bảng các công thức tươngđương ở trên. Dùng một số cách chứng minh gián tiếp khác như phản chứng. Khi đó ta giả thiết có mộtbộ chân trị của các mệnh đề sơ cấp sao cho A nhận giá trị 0, từ giả thiết này bằng các lậpluận ta dẫn về một khẳng định vô lý hoặc mâu thuẫn với các kết quả đã biết.Ví dụ 6: Chứng minh công thức (A  B)  (A  B) là đồng nhất đúng. Lập bảng chân trị :ABABAB(A  B)  (A  B)111113Chương 3. Lôgic và suy luận toán học100110101100001 Biến đổi trực tiếp : (A  B)  (A  B)  (A  B)  (A  B)  A  B  A  B  1 Phản chứng : Giả thiết tồn tại một bộ giá trị của A, B sao cho công thức trên nhận giá trịcủa 0. Từ bảng chân trị của phép toán X  Y (chỉ sai khi X đúng và Y sai) ta phải có A B đúng còn A  B sai. Hai khẳng định này là mâu thuẫn nhau do A  B đúng khi vàchỉ khi cả A lẫn B đúng còn A  B sai khi và chỉ khi cả A lẫn B sai. Do đó công thứctrên là đồng nhất đúng.d. Tính chấtĐịnh lý 1: Giả sử A, B là các công thức. A  B khi và chỉ khi A  B và B  A làcác đồng nhất đúng.Chứng minh: bài tập.Định lý này cho thấy mối quan hệ giữa tính tương đương và tính đồng nhất đúng.Ví dụ 7: A  A vì cả A  A và A  A đều là các đồng nhất đúng. A  (B  A) là công thức đồng nhất đúng nhưng không thể khẳng định A  B  A, vì(B  A)  A chỉ là tiếp liên.5. Luật đối ngẫuGiả sử A là một công thức chỉ chứa các phép toán , ,  mà không chứa phép toán .Trong A đối chỗ vai trò hai phép toán ,  cho nhau và thay giá trị của cặp 1, 0 ta được côngthức A* gọi là công thức đối ngẫu của A. Từ định nghĩa dễ dàng thấy được nếu B là công thứcđối ngẫu của A thì A cũng là đối ngẫu của BVí dụ 8: Đối ngẫu của công thức X  (Y  X) là công thức X  (Y  X)Định lý 2: Cho A(X) và B(X) là các công thức, trong đó X là bộ các mệnh đề sơ cấpvà B(X) là công thức đối ngẫu của A(X). Khi đó ta có :i. A(X)  B(X) và B(X) = A(X)ii. A(X)  B(X) và B(X)  A(X)Chứng minh: Chứng minh theo định nghĩa đệ quy của công thức A và dùng luật De Morgan.Ví dụ 9:Chota có :A(X, Y, Z) = (X  Y)  (Y  Z)  A*(X, Y, Z) = (X  Y)  (Y  Z)A*((X, Y, Z))((X  Y)  (Y  Z)(X  Y)  (Y  Z)(De Morgan)(X  Y)  (Y  Z)4Chương 3. Lôgic và suy luận toán họcAVậy A(X, Y, Z)  A*((X, Y, Z)).Định lý 3: Đối ngẫu của 2 công thức tương đương là 2 công thức tương đương.Chứng minh: Qui nạp theo định nghĩa của công thức.Ví dụ 10:A  (A  B)  ALuật hấp thụA  (A  B)  Acũng đúng và là hấp thụ(đối ngẫu của A  (A  B) là A  (A  B), còn đối ngẫu của A là A)hoặc các công thức khác như công thức De Morgan, công thức phân phối, kết hợp ...6. Luật thay thếGiả sử A là công thức mệnh đề chứa kí hiệu mệnh đề sơ cấp X. Khi đó thay một hoặc mộtsố bất kỳ vị trí X trong A bởi một công thức mệnh đề B nào đó ta sẽ nhận được công thức mệnhđề mới kí hiệu A(X|B).Định lý 4: Nếu A(X) là đồng nhất đúng thì A(X|B) cũng là đồng nhất đúng với mọicông thức B bất kỳ.Chứng minh: chứng minh theo định nghĩa của công thức đồng nhất đúng.Ví dụ 11: (A  B)  A là đồng nhất đúng. Do đó thay A bởi (B  A) ta nhận được công thức((B  A)  B)  (B  A) cũng là đồng nhất đúng.7. Luật kết luậnĐịnh lý 5: Nếu A và A  B là các công thức đồng nhất đúng thì B cũng là công thứcđồng nhất đúngChứng minh: Phản chứng.II. BÀI TOÁN THOẢ ĐƯỢCMột công thức mệnh đề A gọi là thoả được nếu tồn tại một bộ giá trị của các mệnh đề sơcấp sao cho công thức có giá trị đúng (1).Như vậy một công thức A là không thoả được khi nó không phải là đồng nhất sai tức Akhông phải là đồng nhất đúng. Do vậy để giải bài toán thoả được ta đưa về xét bài toán đồng nhấtđúng. Nếu A không là đồng nhất đúng thì A là thoả được.Dễ thấy có tồn tại thuật toán tìm đồng nhất đúng. Ví dụ lập bảng chân trị. Tuy nhiênphương pháp này có độ phức tạp lớn (O(2n)). Do vậy ta đưa ra một cách khác kiểm tra tính đồngnhất đúng với độ phức tạp bé hơn.Giả thiết cần kiểm tra một công thức A là đồng nhất đúng ? Giả sử A chứa 64 biếnmệnh đề sơ cấp. Nếu làm theo phương pháp liệt kê bảng chân trị ta sẽ thu được bảng5Chương 3. Lôgic và suy luận toán họcvới 264 dòng. Giả thiết một máy tính kiểm tra được giá trị của công thức với tốc độ 1tỷ dòng/giây. 1 tỷ = 103x3  210x3. Khi đó để kiểm tra hết bảng chân trị máy tính phảimất 264 / 230 = 234 giây. Mỗi năm có 365 x 24 x 3600 giây < 512 x 32 x 4096 = 29 x 25x 214 = 228 giây. Do vậy thời gian cần là 26 năm = 64 năm.1. Tuyển (hội) sơ cấpĐịnh nghĩa : Tuyển (hội) các mệnh đề và phủ định của nó được gọi là tuyển (hội) sơ cấpĐịnh lý 6: Điều kiện cần và đủ để một TSC đồng nhất đúng là trong tuyển đó cóchứa một mệnh đề đồng thời với phủ định của nó và để một HSC đồng nhất sai làtrong hội đó có chứa một mệnh đề đồng thời với phủ định của nó.Chứng minh: bài tập2. Dạng chuẩn tắc tuyển (hội)Định nghĩaGiả sử A là một công thức và A' là công thức tương đương của A. Nếu A' là một tuyển củacác HSC thì A' được gọi là dạng chuẩn tắc tuyển của A.Giả sử A'' là công thức tương đương của A. Nếu A' là một hội của các TSC thì A' được gọilà dạng chuẩn tắc hội của A.Định lý 7: Điều kiện cần và đủ để A đồng nhất đúng là trong dạng chuẩn tắc hội củanó mọi TSC đều phải chứa ít nhất một mệnh đề sơ cấp cùng với phủ định của nó.Điều kiện cần và đủ để A đồng nhất sai là trong dạng chuẩn tắc tuyển của nó mọi HSC đềuphải chứa ít nhất một mệnh đề sơ cấp cùng với phủ định của nó.Chứng minh: bài tập3. Thuật toán kiểm tra hằng đúngĐể xây dựng dạng chuẩn tắc tuyển ta theo các bước : Khử  Dùng De Morgan và phân phối đưa về chỉ 3 phép toán , , . Đưa công thức về dạng chuẩn tắcVí dụ 12: X  (Y  X) = X  Y  Xlà dạng chuẩn tắc tuyển với ba HSC là X, Y, Xlà dạng chuẩn tắc hội với một TSC là X  Y  X nên là đồng nhất đúng.III. VỊ NGỮ VÀ LƯỢNG TỪ4. Vị ngữi.Xét các câu có liên quan đến biến như :P(x) := x > 36Chương 3. Lôgic và suy luận toán họcii. Q(x,y) := x = y + 3iii. R(x,y,z) := x + y + z = 0Các câu trên có giá trị (1, 0, 1, 0) chỉ khi x, y, z nhận giá trị cụ thể.P, Q, R được gọi là các hàm mệnh đề, x, y, z là các biến và "tính chất", "ràng buộc" của x,y, z là vị ngữ. Ví dụ đối với hàm mệnh đề P(x), x là biến và "lớn hơn 3" là vị ngữ.Với các giá trị cụ thể của x, y, z thì P, Q, R có giá trị chân lý. Ví dụ P(1) = 0, P(4) = 1.5. Lượng từĐề hàm mệnh đề nhận giá trị ta cần xét giá trị cụ thể của các biến. Tuy nhiên một hàmmệnh đề cũng có thể được lượng từ hoá để nhận giá trị.a. Lượng từ "với mọi"xP(x) = 1  P(x) đúng với mọi x trong không gian.Ví dụ 13: x. x  0 là một mệnh đề đúng. Hàm mệnh đề P(x) là x2  0.2Trong trường hợp không gian là hữu hạn thì P(x)  P(x1)  P(x2)  ...  P(xn)b. Lượng từ "tồn tại"xP(x) = 1  P(x) đúng với một x nào đó trong không gian.Ví dụ 14: x. x2 = 0 là một mệnh đề đúng. Hàm mệnh đề P(x) là x2 = 0.Trong trường hợp không gian là hữu hạn thì P(x)  P(x1)  P(x2)  ...  P(xn)c. Biến ràng buộc và tự doRàng buộc nếu được lượng từ hoá và tự do thì ngược lại.Như vậy để một hàm mệnh đề trở thành mệnh đề thì tất cả các biến của nó phải ràng buộc.Chú ý : Thứ tự của các lượng từ là quan trọng.Ví dụ 15: xy. xy = 1 (x  R\{0}) có giá trị 1 còn yx. xy = 1 có giá trị 0.d. Biểu thức logic với lượng từMột biểu thức lôgic (công thức) không có các biến tự do sẽ thành một mệnh đề thôngthường. Từ đó ta cũng có thể áp dụng các phép toán lôgic trên nó và có thể xét tính đồng nhấtđúng hoặc tính tương đương của 2 công thức lôgic như trong đại số mệnh đề.Có thể kết hợp các lượng từ thành một biểu thức lôgic :Ví dụ để định nghĩa L là giới hạn của hàm f(x) :  x (0 < |x - a| <   |f(x) - L| < )Hoặc có thể dễ dàng chứng minh được (bài tập cho sinh viên)xP(x)  xP(x) và xP(x)  xP(x)6. Dịch câu sang biểu thức lôgicCũng giống như dịch các câu nói thông thường sang mệnh đề trong tiết trước, ở đây ta cũngcần tách câu thành các hàm mệnh đề liên quan nhau bởi các phép toán lôgic. Biểu diễn từng hàmmệnh đề một và nối lại bằng phép toán.7Chương 3. Lôgic và suy luận toán họcVí dụ 16: "Mọi người đều có một và chỉ một người bạn tốt nhất"Có thể tách thành 2 hàm mệnh đề : “mọi người đều có một người bạn tốt nhất” và“mọi người đều có chỉ một người bạn tốt nhất”. Đây là 2 hàm mệnh đề có liên quan đếnnhau và có thể biểu diễn được bởi một hàm mệnh đề : B(x,y) = "y là bạn tốt nhất của x"x y (B(x,y)  z(z  y  B(x,z))Ví dụ 17: bài tập "Tất cả sư tử đều hung dữ" "Một số sư tử không uống cà phê" "Một số sinh vật hung dữ không uống càfê "x(P(x)  Q(x))x(P(x)  R(x))x(Q(x)  R(x))P(x) = "x là sư tử", Q(x) = "x hung dữ", R(x) = "x uống cà phêCần phân biệt x(P(x)  R(x)) và x(P(x)  R(x)) (bài tập)IV. CÁC PHƯƠNG PHÁP CHỨNG MINH1. Các qui tắc suy diễnĐịnh lý là một mệnh đề có thể chứng minh là đúng đắn. Để chứng minh tính đúng củamệnh đề ta có thể xuất phát từ các mệnh đề được chấp nhận đúng ban đầu gọi là tiên đề và từnhiều phương pháp bằng nhiều qui tắc suy luận toán học ta rút ra các mệnh đề đúng tiếp theo kéothành dãy và kết thúc thành mệnh đề cần chứng minh. Trong thực tế ta thường xuất phát từ nhữngmệnh đề trung gian (hoặc các bổ đê) đã được chứng minh là đúng đắn.Bảng sau là một số qui tắc suy luận quan trọng thường đặt trên cơ sở các đồng nhất đúngtrong lôgic mệnh đề và lôgic vị từ. Chúng ta có thể xây dựng rất nhiều các qui tắc suy diễn nhưvậy dựa trên các đồng nhất đúng tuy nhiên ta chỉ xét các suy diễn tương đối đơn giản dễ nhớ vàdễ áp dụng.Tên gọiĐồng nhất đúngQui tắc suy diễnCộngp  (p  q)ppqRút gọn(p  q)  ppqpKết luận (modus ponens)((p  q)  p)  qpq,pqKết luận phủ định(modus tollens)((p  q)  q)  pp  q , q  pTam đoạn luận((p  q)(q  r))(p  r)pq,qrprTam đoạn luận tuyển((p  q)  p)  qp  q , p  qCác ví dụ : Mặt trời mọc ở hướng đông hoặc quả đất vuông là một định lý. Tam giác là đa giác có 3 cạnh và 3 góc. Do vậy tam giác là đa giác có 3 cạnh. Ta đã biết 2 định lý : 3 là số lẻ và nếu n là một số lẻ thì n+1 chia hết cho 2. Vậy 4 = 3+1chia hết cho 2 vì 3 là một số lẻ. n là một số lẻ thì n+1 chia hết cho 2. 8+1 không chia hết cho 2 vậy 8 không phải là số lẻ.8Chương 3. Lôgic và suy luận toán học Đã biết : nếu năm chia chẵn cho 4 thì là năm nhuận và nếu năm nhuận thì tháng 2 có 29ngày. Vậy tháng 2 năm 2000 có 29 ngày. Hiện nay trời đang mưa hoặc có nhiều mây. Nếu hiện nay trời không mưa thì có nhiềumây.Suy luận có cơ sở : Các suy luận dùng qui tắc suy diễn dựa trên công thức đồng nhất đúng.Nguỵ biện : Các suy luận dùng qui tắc suy diễn dựa trên đồng nhất sai hoặc tiếp liênMột suy luận có cơ sở có thể dẫn đến kết quả đúng hoặc sai tuỳ thuộc vào các giả thiếtđúng hoặc sai. Một nguỵ biện luôn luôn dẫn đến kết quả không được chấp nhận (luôn luôn sai).Ví dụ về suy luận có cơ sở : Cắt chân cào cào, hô nhảy cào cào không nhảy vậy tai cào cào nằm ở chân. Nếu a = b thì a2 = ab  a2 - b2 = ab - b2 = b(a - b). Mặt khác a2 - b2 = (a - b)*(a + b).Đơn giản a - b ta được a + b = b  2 = 1 là các suy luận có cơ sở nhưng dẫn đến các kếtquả sai vì đã sử dụng nhầm giả thiết.Ví dụ về nguỵ biện : Nếu có tiền tôi sẽ mua ô tô, vì tôi mua ô tô nên tôi có tiền. Sử dụng sai công thức : ((p q)  q)  p) Nếu n là số nguyên tố thì n2 là số lẻ. Vì 81 là số lẻ nên 9 là số nguyên tố. Sử dụng saicông thức : ((p  q)  q)  p) Sữa có màu trắng, con cò cũng có màu trắng, vậy sữa là con cò. Sử dụng sai công thức :((p  q)  (r  q))  (p  r)Dựa trên các qui tắc suy diễn ta có các phương pháp chứng minh sau.2. Các phương pháp chứng minha.Cần chứng minh pDùng phản chứng. Giả thiết p  0. Vì p  0 đúng  p sai. Ví dụ : căn 2 là vô tỷ.b.Cần chứng minh p  qrỗng : Chỉ ra p saitầm thường : Chỉ ra q đúngtrực tiếp : Dùng trung gian từ p đến q. Ví dụ : n lẻ  n2 lẻ.gián tiếp : Dựa trên công thức p  q  q  p. Ta sẽ chứng minh q  p bằng trựctiếp hoặc bằng một cách bất kỳ nào đó. Từ đó suy ra p  q. Ví dụ : nếu 3n + 2 lẻ thì nlẻ.Cách chứng minh này cũng có thể được quan niệm như chứng minh bằng phản chứng,chứng minh bằng mâu thuẫn phụ thuộc vào cách trình bày. Chứng minh bằng phản chứng khi taquan niệm mệnh đề p  q như một mệnh đề p không cần phân chia. Chứng minh bằng mâuthuẫn (hoặc cũng gọi là phản chứng) khi ta giả thiết p đúng và q đúng khi đó suy ra được p,tức dẫn đến mâu thuẫn vì có p và p. Minh hoạ cho nhận xét này là chứng minh A  (B  A) làhằng đúng : Phản chứng : giả thiết A  (B  A) = 0  A = 1 và B  A = 0  B = 1 và A = 0, nhưvậy ta có A = 1 và A = 0 => mâu thuẫn Gián tiếp : xem p = A và q = B  A, giả thiết q tức B  A = 0  B = 1, A = 0 tức p9Chương 3. Lôgic và suy luận toán họcvậy p  q Mâu thuẫn : Giả thiết có p tức A = 1, và q tức B  A = 0 tức A = 0 dãn đến mâuthuẫn.c. Cần chứng minh (p1  p2  ...  pn)  qChứng minh từng trường hợp : (p1  q)  (p2  q)  ...  (pn  q).Ví dụ : Nếu n không chia hết cho 3 thì n2  1 (mod 3). 1ách n thành 2 trường hợp chia 3 dư1 và chia 3 dư 2.d. Cần chứng minh p  qChứng minh p  q và q  p.Ví dụ : Cho R là một quan hệ tương đương. Các điều sau đây là tương đươngi. aRbii. [a]R = [b]Riii. [a]  [b]  e. Cần chứng minh xP(x) Chứng minh bằng kiến thiết : Chỉ ra x. Ví dụ : với mọi n, tồn tại n số nguyên liên tiếp làhợp số. Tức nx (x + i) là hợp số (i=1..n). Lấy x = (n + 1)! + 1. Trực tiếp hoặc phản chứng : Ví dụ x3 - 3x + 1 = 0 có nghiệm trên [0, 1]. Áp dụng định lýđổi dấu. Hoặc cần chứng minh với bất kỳ dãy 5 số liên tiếp luôn tồn tại một số chia hếtcho 5.f. Cần chứng minh xP(x) đúngChứng minh trực tiếp hoặc qui nạp nếu x  N.Ví dụ 18: n.1+2+...+ n = n(n+1)/2. Có n/2 cặp n+1 (n chẵn) hoặc (n+1)/2 cặp n (n lẻ, thêm 0).g. Cần chứng minh xP(x) saiChứng minh xP(x) đúng, tức chỉ ra phản ví dụ để P(x) sai.Ví dụ 19: chứng minh với mọi x nguyên tố x + 2 là nguyên tố.V. PHƯƠNG PHÁP QUI NẠP1. Phương pháp qui nạpa. Phương phápQuy nạp toán học là phương pháp rất quan trọng, thường dùng để chứng minh các mệnh đềdạng nP(n) trong đó n là một số nguyên dương tùy ý.Quá trình chứng minh P(n) là đúng với mọi số nguyên dương n bao gồm hai bước:i. Bước cơ sở. Chỉ ra mệnh đề P(1) là đúng.ii. Bước quy nạp. Chứng minh phép kéo theo P(n)  P(n+1) là đúng với mọi số nguyêndương n, trong đó P(n) được gọi là giả thiết quy nạp.Theo cách viết của các quy tắc lôgic chứng minh này có dạng như sau:(P(1)  n(P(n)  P(n+1))  nP(n)10Chương 3. Lôgic và suy luận toán họcKhi sử dụng quy nạp toán học để chứng minh định lý, trước tiên ta chỉ ra P(1) là đúng. Sauđó ta biết P(2) là đúng, vì P(1) suy ra P(2). Tiếp theo P(3) đúng vì P(2) suy ra P(3). Cứ tiếp tụcnhư vậy ta có P(k) đúng với mọi k nguyên dương tùy ý.Có thể giải thích phương pháp này bằng hình ảnh của dãy người xếp hàng liên tiếp nhau.Giả sử có một tin mật và nếu một người trong dãy biết tin này thì lập tức anh ta sẽ tiết lộ chongười đứng sau mình. Khi đó nếu người 1 biết tin mật này thì P(1) là đúng, sau đó P(2) cũngđúng vì người một nói cho người hai, người hai lại nói cho người 3, tức là P(3) đúng v..v. Cứ nhưvậy, theo quy nạp toán học, mọi người trong hàng đều biết điều bí mật. Một cách minh họa kháclà một dãy quân cờ đô-mi-nô có nhãn là 1,2,3,.. đang đứng trên mặt bàn. Giả sử P(n) là mệnh đề“quân đô-mi-nô n bị đổ”. Nếu quân 1 bị đổ, tức là P(1) đúng, và nếu quân n đổ thì quân (n+1)cũng đổ, tức là nếu P(n)  P(n+1) là đúng, thì khi đó tất cả các quân đô-mi-nô đều bị đổ.b. Tính đúng đắn của phương pháp qui nạpĐể chứng minh phương pháp quy nạp toán học là đúng đắn ta cần giải thích chúng dựa trêntiên đề sắp tốt của tập các số nguyên.Tiên đề phát biểu : Mọi tập số nguyên không âm luôn có phần tử nhỏ nhất.Giả sử ta đã chứng minh P(1) là đúng và mệnh đề P(n)  P(n+1) cũng đã được chứng minhlà đúng với mọi số nguyên dương n. Giả thiết có ít nhất một số nguyên dương sao cho P(n) là sai.Khi đó tập S bao gồm các số nguyên dương n mà P(n) sai là không rỗng. Theo tiên đề sắp tốt, Scó phần tử nhỏ nhất, gỉa sử là k. Vì P(1) đúng nên k > 1. Do 0 < k-1 < k nên k-1 không thuộc S,tức là P(k-1) đúng. Nhưng vì mệnh đề P(k-1)  P(k) là đúng, ta suy ra P(k) là đúng. Điều này vôlý vì k thuộc S. Do vậy, P(n) là đúng với mọi n nguyên dương.(Ví dụ về tiên đề sắp tốt : Chứng minh : nếu a là một số nguyên và d là một số nguyêndương khi đó có duy nhất các số nguyên q và r sao cho 0  r < d và a = dq + r.Chứng minh: Giả sử S là tập các số nguyên không âm dạng a - dq trong đó q là một số nguyên.Tập này không rỗng vì -dq có thể lớn tùy ý bằng cách chọn q âm có trị tuyệt đối đủ lớn.Theo tính được sắp tốt, S có số nhỏ nhất là r = a - dq0. Rõ ràng r < d, vì nếu ngược lại ta xétsố a - d(q0+1) = (a - dq0) - d = r - d  0 tức là a - d(q0+1) thuộc tập S mà lại nhỏ hơn r. Đó làđiều vô lý. Do vậy có các số nguyên q, r sao cho a = dq + r và 0  r < d. Tính duy nhất củaq và r cho có thể được chứng minh dễ dàng)Chú ý : ở bước cơ sở thay cho 1 có thể là một k nào đó, khi đó ở bước qui nạp cần chứngminh P(n)  P(n+1) với n  k.c. Ví dụVí dụ 1: 1 + 2 + ... + n = n(n+1)/2Ví dụ 2: Mọi số nguyên lớn hơn 1 đều có thể phân tích thành tích của các thừa số ng. tốVí dụ 3: Số hạng dãy Fibonaci f(n) =5 1nn1 5 1 5      22 Ví dụ 4: Màu ngựa giống nhauVí dụ 5: an = 1. a0 = 1. Giả sử đúng với n. an+1 = an*a = an/an-1 * anVí dụ 6: Các số điều hòa Hk, k = 1,2,3,... được định nghĩa như sau :Hk  11213 . . . .1k11Chương 3. Lôgic và suy luận toán họcVí dụ 7: Chứng minh rằng:nH2n  12trong đó n là số nguyên không âm.Chứng minh: Giả sử P(n) là mệnh đề “ H 2Bước cơ sở : P(0) là đúng vìn 1n2“.0H 20  H1  1  1 Bước quy nạp : Giả sử P(n) đúng, tức là ta có2.H2n  1n2. Để chứng minh P(n+1) đúng,ta thực hiện các phép biến đổi như sau:H 2 n1  1 1123 H2n  (1 n22 (1 212n11n)  2 .n21 . . . .n1) 12n12n11 . . .2n11 . . .2 (1 n1n1) 22n11 . . .2(do giả thiết quy nạp)n1(vì có 2n số hạng mỗi số không nhỏ hơn 1/2n+1) 1n 12Đó là điều cần chứng minh. Như vậy bất đẳng thức về các số điều hòa đúng với các sốnguyên không âm.nVí dụ 8: Bằng quy nạp toán học chứng minh định luật DeMorgan tổng quát: nAk k 1trong đó A1, A2,..., An là các tập con của tập toàn thể U và nAkk 12.Chứng minh: Giả sử P(n) là đẳng thức cần chứng minh.Bước cơ sở : Rõ ràng P(2) là đúng vìta đã chứng minh trong chương 1.A1  A 2  A1  A 2chính là định luật DeMorgan mànBước quy nạp : Giả sử P(n) là đúng, tức là :k 1nAk Akk 1Để chứng minh P(n+1) đúng ta giả sử A1, A2,...,An, An+1 là các tập con của tập toàn thể U.Khi đó sử dụng giả thiết quy nạp ta có:n 1 n A k    A k k 1k 1 n  An 1    Ak k 1Đây chính là điều cần chứng minh.  An 1n1 n   Ak   An  1   Ak k 1k 12. Dạng tổng quát của quy nạp toán học12Chương 3. Lôgic và suy luận toán họca. Phương pháp Bước cơ sở : Chỉ ra mệnh đề P(k)  P(k+1)  …  P(k+m) là đúng. Bước quy nạp : Chứng tỏ [P(k)  P(k+1)  ...  P(n)]  P(n+1) là đúng với mọi nnguyên dương, trong đó 1 k  n.Việc chứng minh tính đúng đắn tương tự dạng nguyên thuỷ (bài tập).b. Ví dụVí dụ 1: Chỉ ra rằng nếu n là một số nguyên lớn hơn 1, khi đó n có thể viết dưới dạng tích của cácsố nguyên tố.Chứng minh: Gọi P(n) là mệnh đề “n có thể viết dưới dạng tích của các số nguyên tố”.Bước cơ sở : P(2) là đúng vì 2 là tích của chính nó.Bước quy nạp : Gỉa sử P(k) là đúng với k = 2, 3, .., n. Ta phải chứng minh P(n+1) là đúng.Thật vậy, nếu (n+1) là số nguyên tố thì hiển nhiên P(n+1) là đúng. Nếu (n+1) là hợp số thì nó cóthể viết như sau n+1 = a.b, trong đó 2  a  b < n+1. Theo giả thiết quy nạp a và b lại có thể viếtthành tích của các số nguyên tố. Như vậy nếu n+1 là hợp số thì nó cũng có thể được viêt dướidạng tích các số nguyên tố. Tóm lại, bất kể trường hợp nào thì “n có thể viết dưới dạng tích củacác số nguyên tố”.Ví dụ 2: Chứng tỏ mọi bưu phí bằng hay lớn hơn 12 xu đều có thể tạo ra bằng các con tem 4 hay5 xu.Chứng minh: Giả sử P(n) là mệnh đề “mọi bưu phí n xu (n  12) đều có thể tạo ra bằng các contem 4 hay 5 xu”.Bước cơ sở : P(12) là đúng vì có thể dùng 3 con tem 4 xu.Bước quy nạp : Giả sử P(n) đúng. Nếu có ít nhất một con tem 4 xu thì ta chỉ việc đổi contem này bằng tem 5 xu thì sẽ tạo được bưu phí n+1 xu. Nếu không có con tem 4 xu nào, tức làcước phí n xu tạo nên chỉ bằng các con tem 5 xu. Vì n  12 nên ít nhất ta đã dùng 3 con tem 5 xu.Thay 3 con tem này bằng 4 con tem 4 xu, ta sẽ tạo được cước phí n+1 xu.Bây giờ chúng ta sẽ chứng minh bằng dạng thứ hai của quy nạp toán học.Bước cơ sở : Dễ kiểm tra lại rằng P(12), P(13), P(14), P(15) là đúng.Bước quy nạp : Giả sử n  15 và P(k) là đúng với 12  k  n. Để tạo ra bưu phí n+1 xu tadùng các con tem đã tạo ra bưu phí n-3 xu, và thêm một tem 4 xu nữa. Vậy là chúng ta đã hoàntất bước quy nạp, và kết thúc chứng minh.Chúng ta sẽ thảo luận hai áp dụng quan trọng của quy nạp toán học trong mục tới. Đó làdùng quy nạp để định nghĩa một dãy số khi không biết công thức tường minh của các số hạng, vàsau đó là chứng minh tính đúng đắn của một chương trình.VI. ĐỆ QUI1. Định nghĩa bằng đệ quyĐôi khi định nghĩa một đại lượng tường minh là khó. Dùng phương pháp định nghĩa đệ quilà định nghĩa đại lượng này thông qua giá trị của chính nó tại các thời điểm trước đó. Cách dùngnày áp dụng cho nhiều lĩnh vực. Ví dụ để định nghĩa một hàm xác định trên tập các số nguyênkhông âm, chúng ta cho:13Chương 3. Lôgic và suy luận toán học Giá trị của hàm tại các giá trị ban đầu. Công thức tính giá trị của nó tại số nguyên n từ các giá trị của nó tại các số nguyên nhỏhơn.a. Ví dụ về định nghĩa đệ quiVí dụ 1: Dãy Fibonaci- f(1) = f(2) = 1Ví dụ 2: Tập số chẵn-2SVí dụ 3: Xâu-  là một xâu - x là một xâu và c là chữ cái thì xc là một xâu.Ví dụ 4: Độ dài xâu- l() = 0- f(n) = f(n - 1) + f(n - 2)- Nếu x  S và y  S thì x + y  S.- l(xc) = l(x) + 1Ví dụ 5: Hàm : UCLN(a,b) Nếu a = b thì UCLN(a, b) = a Nếu a > b thì UCLN(a-b, b) Nếu a < b thì UCLN(a, b-a)nVí dụ 6: Hàm F(n) = akk00F (0) ak= a0.k0n 1F ( n  1) ak0   a k   a n 1  F ( n )  a n 1 k0nkVí dụ 7: Biểu thức lôgic : 1, 0 và p, trong đó p là một biến mệnh đề, là biểu thức. (  p ), ( p  q ), ( p  q ), ( p  q ) là các biểu thức nếu p và q là các biểu thức.Việc chứng minh các đại lượng được định nghĩa đệ quy thường bằng phương pháp quinạp thông qua cấu trúc đệ qui của chúng.Ví dụ 8: Chỉ ra rằngfn  n2, trong đó fn là số Fibonaci và 1 5với n3.2Chứng minh: Bước cơ sở : Ta có :  < 2 = f3, 2 = (3+ 5 )/2 < 3 = f4, tức P(3) và P(4) đúng. Bước qui nạp : Bây giờ giả sử P(k) là đúng với mọi k nguyên sao cho 3  k  n, trong đón  4. Ta cần chỉ ra P(n+1) đúng. Thật vậy, vì  nghiệm của phương trình x2 - x - 1 = 0,nên suy ra 2 =  + 1. Do đó : n-1 = 2. n-3 = (+1). n-3= . n-3 + n-3 = n-2 + n-3.Theo giả thiết quy nạp nếu n5 ta suy ra :fn-1 > n-3, fn > n-2.do vậy : fn+1= fn+fn-1 > n-2 +n-3= n-1. Đó là điều cần chứng minh.Ví dụ 9: Chứng minh l(xy) = l(x) + l(y), trong đó x và y là các xâu thuộc *.Chứng minh: Ta chứng minh theo độ dài của y. Bước cơ sở : Dễ kiểm tra lại rằng trường hợp y =  khẳng định trên là đúng vì : l(x) =l(x) = l(x) + 0 = l(x) + l() với mọi xâu x.14Chương 3. Lôgic và suy luận toán học Bước quy nạp : Giả sử l(xy) là đúng, ta phải chứng minh l(x(yc)) đúng với mọi ctức là l(x(yc)) = l(x) + l(yc). Theo định nghĩa của xâu và độ dài xâu ta có: ,l(x(yc)) = l(xyc) = l(xy) + 1, theogiả thiết quy nạp ta có= l(x) + l(y) +1 = l(x) + l(yc).2. Thuật toán đệ quiMột thuật toán được gọi là đệ quy nếu nó giải bài toán bằng cách rút gọn liên tiếp bài toánban đầu tới bài toán cũng như vậy nhưng có dữ liệu đầu vào nhỏ hơn.Ví dụ 10: Tìm thuật toán đệ quy tính giá trị n!Định nghĩa đệ quy hàm UCLN của hai số nguyên a, b không âm cũng cho luôn thuật toánthuật toán tính UCLN.3. Đệ quy và lặpĐịnh nghĩa đệ quy biểu diễn giá trị của hàm tại một số nguyên qua giá trị của nó tại các sốnguyên nhỏ hơn. Điều này có nghĩa là ta có thể xây dựng một thuật tóan đệ quy tính giá trị củahàm được định nghiã bằng đệ quy tại một điểm nguyên.Ví dụ 11: Thủ tục đệ quy sau đây cho ta giá trị của n! với n nguyên dương.Procedure Factorial (n: nguyên dương);BeginIf n =1 then Factorial (n ):=1else Factorial (n ):=i Factorial (n-1);End;Có cách khác tính hàm giai thừa của một số nguyên từ định nghĩa đệ quy của nó. Thay choviệc lần lượt rút gọn việc tính toán cho các giá trị nhỏ hơn, chúng ta có thể xuất phát từ giá trị củahàm tại 1 và lần lượt áp dụng định nghĩa đệ quy để tìm giá trị của hàm tại các số nguyên lớn dần.Đó là thủ tục lặp. Nói cách khác để tìm n! ta xuất phát từ n!=1 (với n=1), tiếp theo lần lượt nhânvới các số nguyên cho tới khi bằng n.Function Iteractive Factorial (n: nguyên dương);Beginx:=1;For i:=1 to N do x:=i*x;Return x;End;Sau khi thi hành đoạn mã nguồn này giá trị của biến x là n!, ví dụ, sau khi đi qua vòng lặp 6lần x = 6! = 1.2.3.4.5.6 = 720.Thông thường để tính một dãy các giá trị được định nghĩa bằng đệ quy, nếu dùng phươngpháp lặp thì số các phép tính sẽ ít hơn là dùng thuật toán đệ quy(trừ khi dùng các máy đệ quychuyên dụng). Chúng ta sẽ xem xét bài toán tính các số hạng thứ n của dãy Fibônaxi.Function Fibonacci(n: nguyên không âm);Beginif n = 0 or n = 1 then return 0else Fibonacci(n):= Fibonacci(n-1) + Fibonacci(n-2);End;Theo thuật toán này, để tìm fn ta biểu diễn fn = fn-1 + fn-2. Sau đó thay thế cả hai số này bằng15Chương 3. Lôgic và suy luận toán họctổng của hai số Fibôna xi bậc thấp hơn, cứ tiếp tục như vậy cho tới khi f0 và f1 xuất hiện thì đượcthay bằng các giá trị của chúng theo định nghĩa.Bây giờ ta tính số các phép toán cần dùng để tính fn khi sử dụng phương pháp lặp.Thuật toán này khởi tạo x như f0 = 0 và y như f1 = 1. Khi vòng lặp được duyệt qua tổng củax và y được gán cho biến phụ z. Sau đó x được gán giá trị của y và y được gán giá trị của z. Vậysau khi đi qua vòng lặp lần 1, ta có x = f1 và y = f0+f1 = f2. Khi qua vòng lặp n-1 lần thì x = fn-1còn y = fn. Như vậy chỉ có n-1 phép cộng được dùng để tìm fn khi n > 1.Function Iteractive Fibonacci (n: nguyên không âm);Beginif n = 0 then return 0else beginx:=0; y:=1;for i:=1 to (n-1) dobeginz := x+y; x := y; y := z;end;Return y;end;End;Chúng ta đã chỉ ra rằng số các phép toán dùng trong thuật toán đệ quy nhiều hơn khi dùngphương pháp lặp. Tuy nhiên đôi khi người ta vẫn thích dùng thủ tục đệ quy hơn ngay cả khi nó tỏra kém hiệu quả so với thủ tục lặp. Đặc biệt, có những bài toán chỉ có thể giải bằng thủ tục đệ quymà không thể giải bằng thủ tục lặp.16Chương 3. Lôgic và suy luận toán họcBÀI TẬPI. ĐẠI SỐ MỆNH ĐỀ1.Cho p, q, r là những mệnh đề :p: bạn bị cúmq: bạn thi trượt kỳ thi cuối khoár: bạn được lên lớpHãy diễn đạt những mệnh đề sau thành câu thông thường :a. p  qb. q  rc. q  rd. p  q  re. (p  r)  (q  r)f. (p  q)  (q  r)Chứng minh:a. Nếu bạn bị cúm thì bạn sẽ thi trượt kỳ thi cuối khoáb. Bạn không thi trượt kỳ thi cuối khoá có nghĩa bạn được lên lớpc. Nếu bạn thi trượt kỳ thi cuối khoá thì bạn sẽ không được lên lớpd. Bạn bị cúm hoặc bạn thi trượt kỳ thi cuối khoá hoặc bạn được lên lớpe. Nếu bạn bị cúm hoặc nếu bạn thi trượt kỳ thi cuối khoá thì bạn không được lên lớpf. hoặc bạn bị cúm và bạn thi trượt kỳ thi cuối khoá hoặc bạn không thi trượt kỳ thicuối khoá và bạn được lên lớp 2.Cho p và q là 2 mệnh đề :p: bạn lái xe với tốc độ trên 65 km/hq: bạn bị phạt vì quá tốc độ cho phépViết các mệnh đề sau thành công thức mệnh đề :a. Bạn không lái xe trên 65 km/hb. Bạn lái xe trên 65 km/h nhưng bạn không bị phạt vì quá tốc độ cho phépc. Bạn sẽ bị phạt vì quá tốc độ cho phép Nếu bạn lái xe trên 65 km/h.d. Nếu bạn không lái xe với tốc độ trên 65 km/h thì bạn sẽ không bị phạt vì quá tốc độ chophépe. Lái xe với tốc độ 65 km/h là đủ để bị phạt vì quá tốc độ cho phépf. Bạn bị phạt vì quá tốc độ cho phép nhưng bạn không lái xe trên 65 km/hg. Mỗi lần bị phạt vì quá tốc độ cho phép là bạn đã lái xe trên 65 km/h.Chứng minh:3.a. pb. p  qc. p  qe. p  qf. p  qg. q  pd. p  qCó hai nhóm người : nhóm luôn luôn nói dối và nhóm luôn luôn nói thật.a. Giải thích vì sao câu hỏi "có phải anh là người nói dối ?" hoặc "có phải anh là ngườinói thật ?" sẽ không thể xác định được người trả lời là nói dối hay nói thật.b. Tìm câu hỏi để biết được người trả lời thuộc nhóm nói dối hay nói thật.17Chương 3. Lôgic và suy luận toán học4.Viết các mệnh đề sau dưới dạng “p nếu và chỉ nếu q” trong ngôn ngữ thông thườnga. Để nhận được điểm giỏi trong khoá học này cần và đủ là phải học giải được các bàitập của toán học rời rạcb. Nếu đọc báo mỗi ngày bạn sẽ thạo tin tức và ngược lạic. Trời mưa nếu là ngày cuối tuần và là ngày cuối tuần nếu trời mưa.d. Bạn có thể nhìn thấy lão phù thuỷ nếu lão không ở trong đó và lão không ở trong đónếu bạn nhìn thấy lão.Chứng minh:a. Bạn nhận được điểm giỏi trong khoá học này nếu và chỉ nếu bạn học giải được các bàitập của toán học rời rạc.b. Bạn sẽ thạo tin tức nếu và chỉ nếu bạn đọc báo mỗi ngày.c. Trời mưa nếu và chỉ nếu là ngày cuối tuần.d. Bạn có thể nhìn thấy lão phù thuỷ nếu và chỉ nếu lão không ở trong đó.5.Lập bảng chân trị cho các công thức mệnh đề sau :a. (p  q)  rb. (p  q)  rc. (p  q)  rd. (p  q)  re. (p  q)  rf. (p  q)  rg. (p  q)  (q  r) h. (p  q)  (q  r)Chứng minh:pqr(a)(b)(c)(d)(e)(f)(g)(h)11110101111110111010101011001111110011101011011100111110101110001100110011011000001010116.Các phép toán XOR (), NAND (|), NOR () được định nghĩa như sau :XOR : A  B = 1 khi và chỉ khi A, B nhận giá trị khác nhauNAND : A | B = 0 khi và chỉ khi A, B nhận giá trị 1NOR : A  B = 1 khi và chỉ khi A, B nhận giá trị 0Hãy lập bảng chân trị cho các mệnh đề sau :a. (p  q)  (p  q)b. (p  q) | (q  r)c. (p  q)  (q  r)d. (A  B)  Ce. (A | B)  (B  C)f. (A  B)  (B | C)g. p  qh. (p  q)  (p  q)i. (p  q)  (p  q)18Chương 3. Lôgic và suy luận toán họcChứng minh:a. (p  q)  (p  q)pqpqp  q(a)11101100110101100101b. (p  q) | (q  r)c. (p  q)  (q  r)pqrp  qqrqr(c)111011110110001100101101001100110010011110010010101001001001100000011110d. (A  B)  C(b) p  qe. (A | B)  (B  C)f. (A  B)  (B | C)ABCA  B(d)A | BBC(e)ABB | C(f)11111101110110111011101010110100110000111110011010001100100100011000111101100000111111107.Lập bảng chân trị để chứng minh các công thức tương đương đã học8.Dùng bảng chân trị để chứng minh các công thức tương đương sau :19Chương 3. Lôgic và suy luận toán họca. p  q  (p  q)  (p  q)b. p  p | pc. p  p  pd. p | q  (p  q)e. p  q  (p  q)Chứng minh:a. p  q  (p  q)  (p  q)pqpqp  qp  q(p  q)  (p  q)110000101101011011000000b. p  p | p9.c. p  p  pd. p | q  (p  q)e. p  q  (p  q)pqpp|pppp|q(p  q)pq(p  q)110000000100001100011111100001111111Bằng các phép biến đổi tương đương chứng minh tính tương đương của các cặp công thứcsau :a. p  q và q  pb. p  q và p  qc. (p  q) và p  qd. (p  q) và p  qe. p  q và (p | q) | (p | q)f. p  q và (p | p) | (q | q)g. p  q và (x  y)  (x  y)h. p  q và (p  p)  (q  q)Chứng minh:a. Ta có p  q  p  q  q  p  (q)  (p)  q  pb. Ta có p  q  (p  q)  (q  p)  (q  p)  (p  q)  p  qc. Ta có (p  q)  ((p  q)  (p  q))  (p  q)  (p  q)  (p  q)  (q p)  p  qd. Ta có (p  q)  (p  q)  (q  p)  (p  q)  (q  p)  (p  q)  (p  p)  (q  q)  (q  p)  (p  q)  (q  p)  p  qe. Ta có p  q  (p | q)  (p | q) | (p | q)f. Ta có p  q  (p  q)  (p | p) | (q | q)20Chương 3. Lôgic và suy luận toán họcg. Ta có p  q  (p  q)  (p  q)  (p  q)h. Ta có p  q  (p  q)  (p  p)  (q  q)10.Tìm mệnh đề tương đương với p  q chỉ chứaa. phép toán NANDb. phép toán NORChứng minh:a. Ta có p  q  p  q  (p | p) | (q | q)  ((p | p) | (p | p)) | (q | q)b. Ta có p  q  p  q  (p  q)  ((p  p)  q))  (p  p)  q)  (p  p)  q)11. Lập công thức mệnh đề từ các mệnh đề p, q, r sao cho nó đúng khi và chỉ khi p và q đúng vàr là saiChứng minh: A = p  q  r12. Lập công thức mệnh đề từ các mệnh đề p, q, r sao cho nó đúng khi và chỉ khi 2 trong 3 mệnhđề là đúngChứng minh: A = (p  q  r)  (q  r  p)  (r  p  q13. Biểu diễn câu sau chỉ dưới dạng phép tuyển và phủ định : "Nếu CSDL danh bạ được mở thìmonitor được đặt ở trạng thái đúng, nếu hệ không ở trạng thái ban đầu của nó". Sau đó phátbiểu lại câu nói này theo công thức vừa tìm được.Chứng minh: Đặt p = “hệ ở trạng thái ban đầu” , q = “CSDL danh bạ mở”, r = “monitor ở trạngthái đúng”. Ta có công thức : A = p  (q  r)  p  (q  r) có nghĩa : hệ ở trạng tháiban đầu của nó hoặc CSDL danh bạ là đóng hoặc monitor ở trạng thái đúng.II. LÔGIC VỊ TỪ14. Cho P(x) là câu “x học ở lớp hơn 5 giờ mỗi ngày trong tuần”, không gian là tập hợp các sinhviên. hãy diễn đạt các biểu thức lôgic sau thành câu thông thường :a. xP(x)b. xP(x)c. xP(x)d. x P(x)Chứng minh:a. Có một sinh viên học ở lớp hơn 5 giờ mỗi ngày trong tuầnb. Mọi sinh viên đều học ở lớp hơn 5 giờ mỗi ngày trong tuầnc. Có một sinh viên không học ở lớp hơn 5 giờ mỗi ngày trong tuầnd. Mọi sinh viên học ở lớp không quá 5 giờ mỗi ngày trong tuần15. 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 sinh viên trong lớp,không gian của y là tập hợp các môn học. Hãy diễn đạt các mệnh đề sau thành câu thôngthườnga. 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)21Chương 3. Lôgic và suy luận toán họcChứng minh:a. Có ít nhất một sinh viên đã học ít nhất một môn học nào đó trong trườngb. Có ít nhất một sinh viên đã học mọi môn học trong trườngc. Mọi sinh viên đều đã học ít nhất một môn học nào đó trong trườngd. Có một môn học mà mọi sinh viên đều đã họce. Với bất kỳ môn học nào trong trường đều có ít nhất một sinh viên đã học môn đóf. Mọi sinh viên đều đã học mọi môn học trong trường 16. Cho L(x, y) là câu “x yêu y”, không gian của x, y là tập hợp người. Dùng lượng từ diễn đạtcác câu saua. Mọi người đều yêu Jerryb. 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êud. Không có ai yêu tất cả mọi ngườie. Có một người mà Lindya không yêuf. Có một người mà không ai yêug. Có đúng một người mà tất cả mọi người đều yêuh. Có đúng 2 người mà Lynn yêui. Mọi người đều yêu chính mìnhj. Có một người không yêu ai ngoài chính mìnhChứng minh:a. xL(x, „Jerry‟)b. x y L(x, y)c. y x L(x, y)d. (x y L(x, y))e. y L(„Lindya‟, y)f. y x L(x, y)g. y(xL(x, y)  z (xL(x, z)  (z = y)))h. y z ((y  z)  L(„Lynn‟, y)  L(„Lynn‟, z)  w (L(„Lynn‟, w)  (w = y  w = z)))i. xL(x, x)j. x(L(x, x)  y (y  x  L(x, y)))Chú ý : Mệnh đề xy (L(x, y)  x = y)  xy (x  y  L(x, y)) vẫn thiếu L(x, x)17. Dùng lượng từ diễn đạt các câu saua. Tất cả sinh viên tin học đều phải học môn toán học rời rạcb. Có một sinh viên lớp này đã có máy vi tínhc. Tất cả sinh viên lớp này đã học ít nhất một môn tin họcd. Có một sinh viên lớp này đã học ít nhất một môn tin họce. Mỗi sinh viên trong 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ả sinh viên lớp này ít nhất đã ở một phòng trong tất cả các nhà của kí túc xáChứng minh:22Chương 3. Lôgic và suy luận toán họca. xL(x,‟THRR‟) với x  {sinh viên tin học} và L(x, y) := x học môn yb. xH(x, „vi tính‟) với x  {sinh viên lớp này} và H(x, y) := x có yc. x y L(x, y) với x  {sinh viên lớp này}, y  {các môn tin học{, L(x, y) := x họcmôn yd. x y L(x, y) với x  {sinh viên lớp này}, y  {các môn tin học{, L(x, y) := x họcmôn ye. x y L(x, y) với x  {sinh viên lớp này}, y  {nhà của KTX{, L(x, y) := x ở trongyf. x y z (H(z, y)  L(x, z)) với x  {sinh viên lớp này}, y  {nhà của KTX{, z {phòng}. H(y, z) := z là phòng của nhà y; L(x, z) := x đã ở trong z.g. x y z (H(z, y)  L(x, z)) với x  {sinh viên lớp này}, y  {nhà của KTX{, z {phòng}. H(y, z) := z là phòng của nhà y; L(x, z) := x đã ở trong z. 18. Giả sử không gian của hàm mệnh đề P(x, y) gồm các cặp số x, y với trên tập {1, 2, 3}. Dùngphé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)Chứng minh:a. x P(x,3) = P(1,3)  P(2,3)  P(3,3)b. y P(1,y) = P(1,1)  P(1,2)  P(1,3)c. xy P(x,y) = P(1,1)  P(1,2)  P(1,3)  P(2,1)  P(2,2)  P(2,3)  P(3,1)  P(3,2) P(3,3)d. xy P(x,y)= P(1,1)  P(1,2)  P(1,3)  P(2,1)  P(2,2)  P(2,3)  P(3,1) P(3,2)  P(3,3)e. xy P(x,y)= (P(1,1)  P(1,2)  P(1,3))  (P(2,1)  P(2,2)  P(2,3))  (P(3,1) P(3,2)  P(3,3))f. yx P(x,y) = (P(1,1)  P(2,1)  P(3,1))  (P(1,2)  P(2,2)  P(3,2))  (P(1,3) P(2,3)  P(3,3)) 19. Chứng minh rằng xP(x)  xQ(x) và x (P(x)  Q(x)) là không tương đương.Chứng minh: Lấy ví dụ phản chứng, giả sử x  {1, 2}, khi đóxP(x)  xQ(x) = (P(1)  P(2))  (Q(1)  Q(2)) == (P(1)  Q(1))  (P(1)  Q(2))  (P(2)  Q(1))  (P(2)  Q(2))(1)x(P(x)  Q(x)) = (P(1)  Q(1))  (P(2)  Q(2)).(2)Hai mệnh đề trên rõ ràng là khác nhau, ví dụ nếu lấy P(1) = Q(2) = 1 và P(2) = Q(1) = 0 thì(1) nhận giá trị 0 còn (2) nhận giá trị 1.Ví dụ phản chứng trên gợi ý cho ta biểu thức: xP(x)  xQ(x)  x(P(x)  Q(x)) làđồng nhất đúng. Độc giả tự chứng minh trường hợp này. 20. Chứng minh rằng xP(x)  xQ(x) và x (P(x)  Q(x)) là không tương đươngChứng minh:23Chương 3. Lôgic và suy luận toán họcTương tự bài tập trên ta có :xP(x)  xQ(x) = (P(1)  P(2))  (Q(1)  Q(2)) == (P(1)  Q(1))  (P(1)  Q(2))  (P(2)  Q(1))  (P(2)  Q(2))(1)x(P(x)  Q(x)) = (P(1)  Q(1))  (P(2)  Q(2)).(2)Hai mệnh đề trên rõ ràng là khác nhau, ví dụ nếu lấy P(1) = Q(2) = 1 và P(2) = Q(1) = 0 thì(1) nhận giá trị 1 còn (2) nhận giá trị 0.Ví dụ phản chứng trên gợi ý cho ta biểu thức : x (P(x)  Q(x))  xP(x)  xQ(x) làđồng nhất đúng. Độc giả tự chứng minh trường hợp này. 21. *Chứng minh rằng xP(x)  xQ(x) và xy (P(x)  Q(y)) là tương đươngChứng minh: Mệnh đề xP(x)  xQ(x) sai khi và chỉ khi x để P(x) sai và y để Q(y) sai.Mệnh đề xy (P(x)  Q(y)) sai khi và chỉ khi có x và đồng thời y để cả P(x) và Q(y)cùng sai.Do 2 điều trên là tương đương nên ta có xP(x)  xQ(x)  xy (P(x)  Q(y)). 22. *Chứng minh các cặp mệnh đề sau là tương đươnga. xP(x)  xQ(x) và xy (P(x)  Q(y)) là tương đươngb. xP(x)  xQ(x) và xy (P(x)  Q(y)) là tương đươngChứng minh:Lập luận tương tự bài tập trên ta có :a. Mệnh đề xP(x)  xQ(x) đúng khi và chỉ khi x ta có P(x) đúng và y để Q(y)đúng, điều này là tương đương với xy (P(x)  Q(y)) đúngb. xP(x)  xQ(x) sai khi và chỉ khi x để P(x) sai và y ta có Q(y) saixy(P(x)  Q(y)) sai khi và chỉ khi không xảy ra x có P(x) đúng và không tồn tại y đểQ(y) đúng hay x để P(x) sai và tương tự y ta có Q(y) sai. Hai điều trên là tương đương đfcm. 23. !x P(x) kí hiệu cho mệnh đề “Tồn tại duy nhất x sao cho P(x)”. Nếu không gian là tập cácsố nguyên, hãy xác định chân trị của các mệnh đề sau :a. !x (x > 1)b. !x (x2 = 1)c. !x (x + 3 = 2x)d. !x (x = x + 1)Chứng minh:a. 0b. 0c. 1d. 024. Xác định chân trị của các mệnh đề sau :a. !x P(x)  x P(x)b. x P(x)  !x P(x)c. !x P(x)  x P(x)Chứng minh:a. 1b. 0c. 125. *Biểu diễn lượng từ !x P(x) qua lượng từ phổ dụng (), lượng từ tồn tại () và các phéptoán lôgicChứng minh: !x P(x)  xP(x)  (yP(y)  y = x)24Chương 3. Lôgic và suy luận toán họcIII. QUI TẮC SUY LUẬN26. Quy tắc suy luận nào được dùng trong mỗi một lập luận sau:a. Alice là giỏi môn toán. Do đó Alice là giỏi môn toán hoặc môn tin.b. Jerry là giỏi môn toán và môn tin. Do vậy Jerry giỏi môn toán.c. Nếu trời mưa thì bể bơi sẽ đóng cửa.Trời mưa. do đó bể bơi đóng cửa.d. Nếu hôm nay tuyết rơi thì trường đại học sẽ đóng cửa. Hôm nay trường đại học khôngđóng cửa. Do vậy hôm nay đã không tuyết rơi.e. Nếu tôi đi bơi thì tôi sẽ phơi nắng được nhiều. Nếu tôi phơi nắng nhiều thì tôi rám nắng.Do đó nếu tôi đi bơi thì tôi sẽ rám nắng.Chứng minh:a. Qui tắc cộng (p / p  q)b. Qui tắc rút gọn (p  q / p)c. Qui tắc kết luận (p  q, p / q)d. Qui tắc kết luận phủ định (p  q, q / p)e. Qui tắc tam đoạn luận (p  q, q  r / p  r)27. Quy tắc suy luận nào được dùng trong mỗi một lập luận sau:a. Những con Kanguroo sống ở Australia và là loài thú có túi. Do đó Kanguroo là loài thúcó túi.b. Hoặc là hôm nay trời nóng trên 100 độ hoặc là sự ô nhiễm là nguy hại. Hôm nay nhiệtđộ ngoài trời nhỏ hơn 100 độ. Do đó ô nhiễm là nguy hại.c. Linđa là vận động viên bơi tuyệt vời. Nếu Linđa là vận động viên bơi tuyệt vời, khi đócô ta có thể làm việc như một người cứu đắm ở bể bơi. Do đó Linđa có thể làm việcnhư một người cứu đắm ở bể bơi.d. Steve sẽ làm việc ở một công ty tin học vào mùa hè này. Do dó mùa hè này anh ta sẽlàm việc ở một công ty tin học hoặc là một kẻ lang thang ngoài bãi biển.e. Nếu tôi cả đêm làm bài tập này, thì tôi có thể trả lời được tất cả các bài tập. Nếu tôi trảlời được tất cả các bài tập thì tôi sẽ hiểu được tài liệu này. Do đó nếu tôi cả đêm làm bàitập này thì tôi sẽ hiểu được tài liệu này.Chứng minh:a. Qui tắc rút gọnb. Qui tắc tam đoạn luận tuyểnc. Qui tắc kết luậnd. Qui tắc cộnge. Qui tắc tam đoạn luận28. Xác định xem mỗi suy luận sau là có căn cứ không. Nếu một suy luận là có căn cứ thì nódùng quy tắc suy luận nào. Nếu không hãy chỉ ra ngụy biện nào đã được sử dụng.a. Nếu n là một số thực lớn hơn 1 khi đó n2 > 1. Giả sử n2 > 1. Khi đó n > 1.b. log23 là vô tỷ nếu nó không là tỷ số của hai số nguyên. Do đó, vì log23 không thể viếtdưới dạng a/b với a và b là hai số nguyên, nên nó là vô tỷ.c. Nếu n là một số thực và n > 3 khi đó n2 > 9. Giả sử n2  9. Khi đó n  3.d. Một số nguyên dương hoặc là số chính phương hoặc có một số chẵn các ước nguyêndương. Giả sử n là một số nguyên dương có một số lẻ các ước nguyên dương. Khi đó n25