Bài giảng Toán rời rạc - Trần Minh Tuyết

 không thể nói về tính đúng sai của nó.Vị từ 2 biến x,y, q(x,y) = “x  y+3” , x,yR,Ta có q(1,2) đúng và q(4,0) sai. Tuy nhiên q(1,y) = “1  y+3” không phải là mệnh đề, nó là vị từ 1 biến y.Lượng từ phổ dụng  Cho p(x) là vị từ 1 biến x. Khi đó câu nói “với mọi x, p(x)” là một mệnh đề. Mệnh đề này ký hiệu là “x, p(x)” và gọi là mệnh đề lượng từ hóa phổ dụng của vị từ p(x). Lượng từ phổ dụng (hay: Lượng từ với mọi)  biến một vị từ 1 biến thành một vị từ 0 biến, nghĩa là thành một mệnh đề.* Cho p(x) = “x là số chẵn” và q(x) = “x chia hết cho 3” xác định trên tập X = 3, 6, 9, 12. Khi đó:x, p(x) là mệnh đề P = “với mọi xX, x là số chẵn”, mệnh đề này sai!x, q(x) là mệnh đề Q = “với mọi xX, x là chia hết cho 3”, mệnh đề này đúng!Lượng từ phổ dụng  Cho p(x) là vị từ 1 biến x. Khi đó câu nói “tồn tại x, p(x)” là một mệnh đề. Mệnh đề này ký hiệu là “ x, p(x)” và gọi là mệnh đề lượng từ hóa tồn tại của vị từ p(x). Lượng từ tồn tại  biến một vị từ 1 biến thành một vị từ 0 biến, nghĩa là thành một mệnh đề.* Cho p(x) = “x là số chẵn” và q(x) = “x chia hết cho 7” xác định trên tập X = 3, 6, 9, 12. Khi đó: x, p(x) là mệnh đề P = “Tồn tại xX, x là số chẵn”, mệnh đề này đúng! x, q(x) là mệnh đề Q = “Tồn tại xX, x chia hết cho 7”, mệnh đề này sai!	Aùp dụng n lần các lượng từ ,  lên vị từ n biến p(x1,, xn) chúng ta biến vị từ này thành một mệnh đề. Mệnh đề này được gọi là mệnh đề lượng từ hóa của vị từ p(x1,, xn).Chẳng hạn với vị từ 2 biến p(x,y) chúng ta có cả thảy 8 mệnh đề như sau:	x, y, p(x,y)	 y, x, p(x,y)	x, y, p(x,y)	 y, x, p(x,y)	x, y, p(x,y)	 y, x, p(x,y)	x, y, p(x,y) 	 y, x, p(x,y) * Một số trong các mệnh đề này trùng nhau!Cho vị từ 2 biến p(x,y) = “x2 + y2  1”, xR, yR. Ta có:	q = “x, y, p(x,y)” sai,	r = “x, y, p(x,y)” đúng.Xét vị từ p(x) = “x2 – 3x + 2  0”. Mệnh đề nào đúng ?	1) x, p(x)	2) x, p(x)Cho các vị từ biến x	p(x) = “x2 – 5x + 6 = 0”	q(x) = “x2 – 4x – 5 = 0”	r(x) = “x > 0”Hãy xác định giá trị chân lý của các mệnh đề sau	1)x, p(x) → r(x)	 2)x, q(x) → r(x)	3)x, q(x) → r(x)	 4)x, p(x) →r(x) 	* Các phủ định dưới đây có đúng không ? Nếu không đúng, hãy thay bằng phủ định đúng. Xác định giá trị chân lý của các mệnh đề này. 1) Với mọi số thực x, y, nếu x2 > y2 thì x > y.	Phủ định: Tồn tại các số thực x, y sao cho x2 > y2 nhưng x  y.	2) Với mọi số thực x, nếu x  0 thì x có nghịch đảo.	Phủ định: Tồn tại số thực x khác 0 mà không có nghịch đảo.	3) Tồn tại hai số nguyên lẻ có tích là số lẻ.	Phủ định: Tích của hai số lẻ bất kỳ là số lẻ.	4) Bình phương của mọi số hữu tỷ là số hữu tỷ.	Phủ định: Tồn tại số thực x sao cho nếu x vô tỷ thì x2 vô tỷ.Mệnh đề nào sau đây đúng ?	1) x, y, xy = 1	2) x, y, xy = 1	3) x, y, xy = 1	4) x, y, sin2x + cos2x = sin2y + cos2y 	5) x, y, (2x + y = 5)(x – 3y = - 8) Giả sử X = {x1, , xn}, khi đó ta có	x, p(x)  p(x1)    p(xn)	x, p(x)  p(x1)    p(xn)	x, p(x)  x, p(x)Từ đó suy ra quy tắc phủ định	Xem phát biểu bên phải nào tương ứng với các phát biểu 1), 2), 3), 4) bên trái ?1) (x, p(x)) đúng 	a) Với mọi x, p(x) sai.2) (x, p(x)) sai 	b) Với mọi x, p(x) đúng.3) (x, p(x)) đúng	c) Có ít nhất một x sao	 cho p(x) sai.4) (x, p(x)) sai 	d) Có ít nhất một x sao	 cho p(x) đúng.	Hãy phủ định mệnh đề lượng từ hóa từ vị từ 3 biến x, y, z sau đây	x, y, z, p(x, y, z) 	Hãy phủ định mệnh đề sau 	xR, yR, x2 + y2  1	Mệnh đề này đúng hay sai ?	Dãy (xn) được gọi là hội tụ nếu aR sao cho xn  a. Hãy phát biểu điều kiện để dãy (xn) không hội tụ.	Hàm số y = f(x) gọi là tăng (không ngặt) trên tập A nếu	xA, yA, (x  y)  (f(x)  f(y))	Hãy phát biểu điều kiện của hàm y = f(x) không tăng trên tập A.Giả sử f: A  B là ánh xạ từ tập A vào tập B.1) f gọi là đơn ánh nếu 	xA, yA, (x  y)  (f(x)  f(y))2) f gọi là toàn ánh nếu 	yB, xA, y = f(x)3) f gọi là song ánh nếu f toàn ánh và f đơn ánh.	Hãy phát biểu điều kiện để hàm f không song ánh.	Cho P = “Mọi người trong lớp đều đã làm hết các bài tập mà thầy đã cho”. Hãy phủ định mệnh đề này.Cho Q = “Chưa ai làm xong công việc của mình”. Hãy phủ định mệnh đề này! Phủ định các mệnh đề sau:1)Với mọi số nguyên n, nếu n không chia hết cho 2 thì n là số lẻ.2)Nếu bình phương của một số nguyên là lẻ thì số nguyên đó là số lẻ.3)Nếu k, m, n là các số nguyên sao cho k – m và m – n là số lẻ thì k – n là số chẵn.Phủ định các mệnh đề sau:1) Nếu x là một số thực sao cho x2 > 16 thì 	x 4.2) Với mọi số thực x, nếu (x – 3)2 < 49 thì 	– 4 < x < 10.Định lý về sự hoán vị thứ tự các lượng từ	1) x, y, p(x,y)		x, y, p(x,y)	2) x , y, p(x,y)		x , y , p(x,y)	Mọi người đều chết. 	Socrate là người	--------------------------	Do đó Socrate sẽ chết. Quy tắc tổng quát hóa phổ dụng* Quy tắc này được sử dụng để chứng minh mệnh đề ”x, p(x)” đúng, trong đó p(x) là vị từ 1 biến x. * Triết lý của quy tắc này là: Để chứng minh mệnh đề “x, p(x)” đúng, chúng ta chỉ cần chứng minh mệnh đề p(a) đúng với a được chọn bất kỳ trong tập xác định của biến x.	Chẳng hạn để chứng minh 	x, x2 + 1  1	Chúng ta lập luận như sau: 	Với a bất kỳ, ta có a2  0 suy ra a2 + 1  1. Do đó x, x2 + 1  1.Từ quy tắc này suy ra quy tắc tam đoạn luận “phiên bản” của vị từ như sau Những đứa bé thì không logic.Không ai bị coi thường nếu cai quản được cá sấu.Những người không logic đều bị coi thường.Vậy: Những đứa bé không cai quản được cá sấu.	Xét X là tập tất cả các con người đang sống trên thế giới!p(x) = x là đứa bé,q(x) = x thì không logic,r(x) = x bị coi thường,s(x) = x cai quản được cá sấu.	Suy luận nào sau đây là đúng ?Mọi người đưa thư đều mang theo túi thư.An là một người đưa thư.Vậy An mang theo túi đựng thư.Mọi công dân tốt đều đóng thuế.An đã đóng thuế.Vậy An là một công dân tốt.Mọi người quan tâm đến môi trường đều để riêng các túi nhựa bỏ đi.Hà không quan tâm đến môi trường.Vậy Hà không để riêng các túi nhựa bỏ đi.Mọi sinh viên nghiêm túc đều không nộp bài chưa làm xong.Minh không nộp bài chưa làm xong.Vậy Minh là sinh viên nghiêm túc.5. Nguyên lý quy nạp 	( induction principle )	Các số được nói đến ở đây đều là các số tự nhiên. Thủ tục quy nạp bao gồm hai bước như sau:	1) Bước cơ sở:	Kiểm tra p(0) đúng.	2) Bước quy nạp:	Giả sử p(n) đúng với n = k  0, chứng minh p(n) đúng với n = k + 1.Dùng phương pháp quy nạp để chứng minh số tập con của tập A có n phần tử bằng 2n. Dùng phương pháp quy nạp để chứng minh số song ánh từ tập A  A bằng n! , trong đó n là số phần tử của A.	6. Các vấn đề khácPhản ví dụ	Để chứng minh mệnh đề “x, p(x) ” sai chúng ta chứng minh mệnh đề phủ định của nó “x, p(x)” đúng bằng cách chỉ ra một trường hợp a của x (một ví dụ a của x) để p(a) sai. 	Đó là cách chứng minh bằng phản ví dụ.	Để chứng minh biểu thức mệnh đề P(p, q, r) không phải là một hằng đúng chúng ta chỉ ra một trường hợp , ,  của p, q, r sao cho mệnh đề P(, , ) sai. 	Đó là cách chứng minh bằng phản ví dụ.Nếu không được tăng lương thì Minh sẽ nghỉ việc.Nếu Minh nghỉ việc và vợ Minh bị mất việc thì Minh phải bán xe.Nếu vợ Minh hay đi làm trễ thì vợ Minh sẽ bị mất việc.Mà Minh được tăng lương.---------------------------------------------------------------Vậy: Nếu Minh không bán xe thì vợ Minh không đi làm trễ.	Trong đó:	p: Minh được tăng lương	q: Minh nghỉ việc	r: Vợ Minh bị mất việc	s: Minh phải bán xe	t: Vợ Minh đi làm trễPhán đoán đây là một suy luận sai. Chúng ta dùng một phản ví dụ để bác bỏ suy luận này! 	Việc này dẫn đến một “hệ phương trình logic” như sau.Giải hệ phương trình này chúng ta được:	p = t = r = 1, q = s = 0Khẳng định sau đúng hay sai ?	“Mọi ma trận vuông cấp 2 không suy biến đều có định thức dương”Định nghĩa đệ quy*	Đôi khi một đối tượng có thể được định nghĩa dễ dàng qua chính nó, đó là cách định nghĩa đệ quy. * Chúng ta có thể dùng phép định nghĩa đệ quy để định nghĩa dãy số Fibonacci. Chúng ta cũng có thể dùng định nghĩa đệ quy để định nghĩa định thức của các ma trận hoặc định nghĩa biểu thức mệnh đề hoặc định nghĩa các hàm sơ cấp,Hàm sơ cấp	1) Hàm lũy thừa, hàm mũ, hàm loga, hàm lượng giác và hàm lượng giác ngược là các hàm sơ cấp.	2) Nếu u, v là các hàm sơ cấp thì u  v, u  v, u/v là các hàm sơ cấp.	3) Hợp của các hàm sơ cấp là hàm sơ cấp.Biểu thức mệnh đề	Biểu thức mệnh đề theo các biến p, q, r.	1) p, q, r là các biểu thức mệnh đề.	2) Nếu P và Q là các biểu thức mệnh đề thì P, P  Q, P  Q là các biểu thức mệnh đề. Ví dụ khác	Định nghĩa đệ quy tập S:	1) 3  S	2) nếu x,y  S thì x+y  S	Ta có S chính là tập tất cả các bội số dương của số 3.	Bên cạnh định nghĩa đệ quy chúng ta còn có các thuật toán đệ quy. Thuật toán đệ quy	Một thuật toán gọi là đệ quy nếu nó cho phép quy việc giải một bài toán thông qua việc giải một bài toán khác tương tự như vậy, nhưng có các dữ kiện đơn giản hơn.Thuật toán	Tính định thức ma trận cấp n. Thuật toán	Tính giai thừa của một số nguyên n, bằng cách dựa vào hệ thức truy hồi 	n! = n(n-1)! Thuật toán	Tính dãy Fibonacci (an)