Bài giảng môn Toán rời rạc - Chương 1: Vị từ và lượng từ

Nội dung text: Bài giảng môn Toán rời rạc - Chương 1: Vị từ và lượng từ

1. Vị từ và lượng từ • Định nghĩa: Cho A là một tập hợp khác rỗng. Giả sử, ứng với mỗi x = a A ta cĩ một mệnh đề p(a). Khi đĩ, ta nĩi p = p(x) là một vị từ theo một biến (xác định trên A)
2. Vị từ và lượng từ • Định nghĩa: Tổng quát, cho A1, A2, A3 là n tập hợp khác trống. Giả sử rằng ứng với mỗi (x1,x2,.,xn) = (a1,a2,.,an) A1 A2 An, ta cĩ một mệnh đề p(a1,a2,.,an). Khi đĩ ta nĩi p = p(x1,x2,.,xn) là một vị từ theo n biến(xác định trên A1 A2 An)
3. Vị từ và lượng từ • Ví dụ 1: Xét p(n) = “n > 2” là một vị từ một biến xác định trên tập các số tự nhiên N. Ta thấy với n = 3;4 ta được các mệnh đề đúng p(3),p(4), cịn với n = 0,1 ta được mệnh đề sai p(0),p(1)
4. Vị từ và lượng từ • Ví dụ 2 2 Xét p(x,y) = “x + y = 1” là một vị từ theo hai biến xác định trên R2, ta thấy p(0,1) là một mệnh đề đúng, trong khi p(1,1) là một mệnh đề sai.
5. Vị từ và lượng từ • Định nghĩa: Cho trước các vị từ p(x), q(x) theo một biến x A. Khi ấy, – Phủ định của mệnh đề p kí hiệu là p là vị từ mà khi thay x bởi 1 phần tử cố định của A thì ta được mệnh đề (p(a)) – Phép nối liền(tương ứng nối rồi, kéo theo ) của p và q được ký hiệu bởi pq( tương ứng là p q, p q) là vị từ theo biến x mà khi thay x bới phần tử cố định a của A ta được mệnh đề p(a)q(a) ( tương ứng là p(a) q(a), p(a) q(a))
6. Vị từ và lượng từ • Định nghĩa: Cho p(x) là một vị từ theo một biến xác định trên A. Ta định nghĩa các mệnh đề lượng từ hĩa của p(x) như sau: – Mệnh đề “Với mọi x thuộc A,p(x)”, kí hiệu bởi “x A, p(x)”, là mệnh đề được định bởi “x A, p(x)” đúng khi và chỉ khi p(a) luơn đúng với mọi giá trị a A – Mệnh đề “Tồn tại(ít nhất )(hay cĩ (ít nhất) một x thuộc A, p(x))” kí hiệu bởi :“x A, p(x)” , là mệnh đề được định bởi “x A, p(x)” đúng khi và chỉ khi cĩ ít nhất một giá trị x = a0 nào đĩ sao cho mệnh đề p(a0) đúng. • Chú ý: Các mệnh đề lượng từ hĩa ở trên đều là các mệnh đề cĩ chân trị xác định chứ khơng cịn là các vị từ theo biến x nữa.
7. Vị từ và lượng từ 1) Mệnh đề “x R, x2 + 3x + 1 0” là một mệnh đề sai hay đúng ? 2 Mệnh đề sai vì tồn tại x0 = 1 R mà x0 + 3x0 + 1 0 2) Mệnh đề “x R, x2 + 3x + 1 0” là một mệnh đề đúng hay sai? 2 Mệnh đề đúng vì tồn tại x0 = –1 R mà x0 + 3x0 + 1 0.
8. Vị từ và lượng từ Mệnh đề “x R, x2 + 1 2x” là một mệnh đề đúng hay sai? Mệnh đề đúng vì với x R, , ta luơn luơn cĩ x2-2x + 1 0 Mệnh đề “x R, x2 + 1 < 0” là một mệnh đề đúng hay sai?
9. Vị từ và lượng từ • Định nghĩa: Cho p(x, y) là một vị từ theo hai biến x, y xác định trên A B. Ta định nghĩa các mệnh đề lượng từ hóa của p(x, y) như sau: “x A,y B, p(x, y)” = “x A, (y B, p(x, y))” “x A, y B, p(x, y)” = “x A, (y B, p(x, y))” “x A, y B, p(x, y)” = “x A, (y B, p(x, y))” “x A, y B, p(x, y)” = “x A, (y B, p(x, y))”
10. Vị từ và lượng từ Xét vị từ p(x, y) = “x + 2y < 1” theo hai biến x, y xác định trên R2 Mệnh đề “x R, y R, x + 2y < 1” đúng hay sai? Mệnh đề sai vì tồn tại x0 = 0, y0 = 1 R mà x0 + 2y0 1. Mệnh đề “x R, y R, x + 2y < 1” đúng hay sai? Mệnh đề đúng vì với mỗi x = a R, tồn tại ya R như ya = –a/2, sao cho a + 2ya < 1.
11. Vị từ và lượng từ Mệnh đề “x R, y R, x + 2y < 1” đúng hay sai Mệnh đề sai vì khơng thể cĩ x = a R để bất đẳng thức a + 2y < 1 được thỏa với mọi y R (chẳng hạn, y =–a/2 + 2 khơng thể thỏa bất đẳng thức này). Mệnh đề “x R, y R, x + 2y < 1” đúng hay sai? Mệnh đề đúng vì tồn tại x0 = 0, y0 = 0 R chẳng hạn thỏa x0 + 2y0 < 1.
12. Vị từ và lượng từ Cho p(x, y) là một vị từ theo hai biến x, y xác định trên A B. Khi đĩ: 1) “x A, y B, p(x, y)” “y B, x A, p(x, y)” 2) “x A, y B, p(x, y)” “y B, x A, p(x, y)” 3) “x A, y B, p(x, y)” “y B, x A, p(x, y)” Chiều đảo của 3) nĩi chung khơng đúng.
13. Vị từ và lượng từ • Chứng minh 3) Giả sử “x A, y B, p(x, y)” là đúng. Khi đĩ, tồn tại a A sao cho “y B, p(x, y)” là đúng, nghĩa là nếu thay y = b B bất kỳ thì p(a,b) đúng. Như vậy, y = b B tuỳ chọn thì ta cĩ thể chọn x = a để “x A, p(x, y)” là đúng. Do đĩ, “y B, x A, p(x, y)” là mệnh đề đúng.
14. Ví dụ thể hiện chiều đảo của 3 là chưa chắc đúng: • Gọi p(x,y) là vị từ theo 2 biến thực p(x,y) = “x + y = 1”, • Nếu thay y tuỳ ý thì x = 1 - y để cho x + y = 1 nên mệnh đề x A, p(x, y) là đúng. Nên mệnh đề “y B, x A, p(x, y)” là đúng. • Ngược lại, nếu chọn x = a tuỳ ý, ta cĩ thể chọn y = -a để “y B, p(x, y)” là sai. Điều này chứng tỏ, “x A, y B, p(x, y)” là sai. • Do đĩ, phép kéo theo sau là sai: “y B, x A, p(x, y)” -> “x A, y B, p(x, y)”
15. Vị từ và lượng từ • Trong một mệnh đề lượng từ hố từ một vị từ theo nhiều biến độc lập, nếu ta hốn vị hai lượng từ đứng cạnh nhau thì: 1. Mệnh đề mới vẫn cịn tương đương logic với mệnh đề cũ nếu hai lượng từ này cùng loại. 2. Mệnh đề mới này sẽ là một hệ quả logic của mệnh đề cũ nếu hai lượng từ trước khi hốn vị cĩ dạng  
16. Vị từ và lượng từ Định lý: a) Với p(x) là một vị từ theo một biến xác định trên A, ta có: b) Phủ định của mệnh đề lượng từ hóa từ vị từ p(x1, x2, , xn) có được bằng cách thay lượng từ  bằng lượng từ  và ngược lại, và thay vị từ p(x1, x2, , xn) bằng vị từ .
17. Phủ Định x P(x) x P(x) x P(x) x P(x)
18. Vị từ và lượng từ Phủ định của mệnh đề “Hơm nay, mọi sinh viên lớp TH1 đều cĩ mặt” là gì ? “Hơm nay, cĩ (ít nhất) một sinh viên lớp TH1vắng mặt”. Phủ định của mệnh đề “Trong lớp TH2cĩ (ít nhất một) sinh viên được thưởng” là gì? “Trong lớp TH2khơng cĩ sinh viên nào được thưởng”.
19. Vị từ và lượng từ Phủ định của mệnh đề “x A, 2x + 1 0” là gì ? Phủ định của mệnh đề trên là “x A, 2x + 1 > 0”. Phủ định của mệnh đề “ > 0,  > 0, x R,  x – a 0,  > 0, x R,  x – a <   (f(x) – f(a) )”.
20. Vị từ và lượng từ Qui tắc đặc biệt hố phổ dụng: Nếu một mệnh đề đúng cĩ dạng lượng từ hố trong đĩ một biến x A bị buộc bởi lượng từ phổ dụng , khi ấy nếu thay thế x bởi a A ta sẽ được một mệnh đề đúng.
21. Vị từ và lượng từ Ví dụ: “Mọi người đều chết” “Socrate là người” Vậy “Socrate cũng hi sinh”
22. Vị từ và lượng từ • Qui tắc tổng quát hố phổ dụng: Nếu trong một mệnh đề lượng từ hố, khi thay một biến buộc bởi lượng từ  bằng một phần tử cố định nhưng tuỳ ý của tập hợp tương ứng mà mệnh đề nhận được cĩ chân trị 1 thì bản thân mệnh đề lượng từ hố ban đầu cũng cĩ chân trị 1.
23. Inference Rules for Quantifiers • x P(x) P(o) (substitute any object o) • P(g) (for g a general element of u.d.) x P(x) • x P(x) P(c) (substitute a new constant c) • P(o) (substitute any extant object o) x P(x)
24. P(PQ) (P  1)(PQ) P  (1Q) P  (1) P