Bài giảng Toán rời rạc - Phần II: Vị từ và lượng từ

Nội dung text: Bài giảng Toán rời rạc - Phần II: 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ử, Phần II ứ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ừ Vị từ và lượng từ theo một biến (xác định trên A) 1 2 Vị từ và lượng từ Predicates and Quantifiers Propositional functions or predicates are propositions • Định nghĩa: which contain variables Example Let P denote the Predicate “is greater than 0” and P(x) denote “x > 0” 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 x is called a variable (x ,x ,.,x ) = (a ,a ,.,a ) A A A , ta The predicate become a proposition once the variable 1 2 n 1 2 n 1 2 n x has been assigned a value. cĩ một mệnh đề p(a1,a2,.,an). Khi đĩ ta nĩi p Example What is the truth value of p(5), p(0) and p(-2)? = p(x1,x2,.,xn) là một vị từ theo n biến(xác “5>0” is true, “0>0” is false and “-2>0” is false định trên A1 A2 An) 3 4 1
2. Vị từ và lượng từ Vị từ và lượng từ • Ví dụ 1: • Ví dụ 2 Xét p(n) = “n > 2” là một vị từ một biến xác định Xét p(x,y) = “x2 + y = 1” là một vị từ theo hai biến trên tập các số tự nhiên N. xác định trên R2, ta thấy p(0,1) là một mệnh đề Ta thấy với n = 3; 4 ta được các mệnh đề đúng đúng, trong khi p(1,1) là một mệnh đề sai. p(3), p(4), cịn với n = 0,1 ta được mệnh đề sai p(0), p(1). 5 6 Examples Vị từ và lượng từ Example: • Định nghĩa: Cho trước các vị từ p(x), q(x) theo Let Q(x,y) denote the statement “y =x + 2”. một biến x A. Khi ấy, What is the truth value of Q(2,4,) and Q(4, 1) – Phủ định của vị từ p(x) kí hiệu là p(x) là vị từ mà khi “4 = 2+2” is true and “1 = 4+2” is false thay x bởi một phần tử cố định của A thì ta được mệnh đề (p(a)) Q(2,y)  Q(0,3) is a proposition??? – Phép nối liền(tương ứng nối rời, kéo theo ) của p(x) Q(1,3)  Q(0,1) is a proposition ??? và q(x) được ký hiệu bởi p(x)  q(x)( tương ứng là p(x)q(x), p(x) q(x)) là vị từ theo biến x mà khi thay Q(2,y)  Q(0,3) is not a proposition: y is not bounded x bởi phần tử cố định a của A ta được mệnh đề Q(1,3)  Q(0,1) is a proposition which is true p(a) q(a) ( tương ứng là p(a)  q(a), p(a) q(a)) 7 8 2
3. Vị từ và lượng từ Universe of Discourse • Định nghĩa: Question Let R be the three-variable predicate R(x,y,z): Cho p(x) là một vị từ theo một biến xác định trên A. Ta x+y = z định nghĩa các mệnh đề lượng từ hĩa của p(x) như sau: Find the truth value of – Mệnh đề “Với mọi x thuộc A,p(x)”, kí hiệu bởi “x A, p(x)”, là R(2,-1,5), R(3,4,7) R(x,3,z) 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 . A universe of discourse (U) is a domain for the – Mệnh đề “Tồn tại(ít nhất )(hay cĩ (ít nhất) một x thuộc A, p(x))” kí variables of a propositional function. 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(a ) đúng. Example 0 Let U = Z, the integers = { , -2, -1, 0, 1, 2, } • 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. 9 10 Universal quantifier Existential quantifier The Universal Quantifier of P(x): The Existential Quantifier of P(x): is the proposition is the proposition “P(x) is true for every x in the universe of discourse” “P(x) is true for some x in the universe of discourse” Notation: x P(x) Notation: x P(x) `For all x, P(x)‟ `For every x, P(x)‟ „For some x P(x)‟ „For at least an x in P(x)‟ Example: Example: U = {1, 2, 3} x P(x) P(1)  P(2)  P(3) U = {1, 2, 3}, x P(x) P(1)  P(2)  P(3) Example Example What is the truth value of x P(x) if P(x) is “3x <10”and What is the truth value of x P(x) if P(x) is “3x <10”and U is positive integers not exceeding 4 U is positive integers not exceeding 4 P(1)  P(2)  P(3)  P(4) is false P(1)  P(2)  P(3)  P(4) is True 11 12 3
4. Vị từ và lượng từ Vị từ và lượng từ 1) Mệnh đề “x R, x2 + 3x + 1 0” là một mệnh đề sai Mệnh đề “x R, x2 + 1 2x” là một mệnh đề đúng hay đúng ? hay sai? R 2 Mệnh đề sai vì tồn tại x0 = 1 mà x0 + 3x0 + 1 0 Mệnh đề đúng vì với x R, , ta luôn luôn có 2) Mệnh đề “x R, x2 + 3x + 1 0” là một mệnh đề đúng hay sai? x2-2x + 1 0 Mệnh đề “x R, x2 + 1 < 0” là một mệnh đề 2 Mệnh đề đúng vì tồn tại x0 = –1 R mà x0 + 3x0 + 1 0. đúng hay sai? 13 14 Vị từ và lượng từ Vị từ và lượng từ • Định nghĩa: Xét vị từ p(x, y) = “x + 2y < 1” theo hai biến x, y xác định trên R2 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, Mệnh đề“x R, y R, x + 2y < 1” đúng hay sai? y) như sau: “x A,y B, p(x, y)” = “x A, (y B, p(x, y))” Mệnh đề sai vì tồn tại x0 = 0, y0 = 1 R mà x0 + 2y0 1. “x A, y B, p(x, y)” = “x A, (y B, p(x, y))” Mệnh đề“x R, y R, x + 2y < 1” đúng hay sai? “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))” 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. 15 16 4
5. Vị từ và lượng từ Translate into English Example Mệnh đề “x R, y R, x + 2y < 1” đúng hay sai Translate the statement x(C(x)  y(C(y) F(x,y))) into English Where C(x) is “x has a computer” Mệnh đề sai vì khơng thể cĩ x = a R để bất đẳng thức F(x,y) is “x and y are friends” a + 2y < 1 được thỏa với mọi y R (chẳng hạn, y =–a/2 + 2 and U is x and y are students in your school khơng thể thỏa mãn bất đẳng thức này) Mệnh đề“x R, y R, x + 2y < 1” đúng hay sai? For every student x in your school x has a computer or there is a student y such that y has a computer and x and y are friends. Mệnh đề đúng vì tồn tại x0 = 0, y0 = 0 R chẳng hạn, thỏa mãn x0 + 2y0 < 1. 17 18 Example Vị từ và lượng từ Example:Let U = R, the real numbers. P(x,y): xy = 0 Cho p(x, y) là một vị từ theo hai biến x, y xác định xy P(x,y) False trên A B. Khi đó: x y P(x,y) x y P(x,y) True 1) “x A, y B, p(x, y)” x y P(x,y) True “y B, x A, p(x, y)” True 2) “x A, y B, p(x, y)” “y B, x A, p(x, y)” Example: Let U={1, 2, 3}. Find an expression equivalent to x y P(x,y) where the variables are bound by substitution instead: 3) “x A, y B, p(x, y)” “y B, x A, p(x, y)” Solution: y P(1,y)  y P(2,y)  y P(3,y) [P(1,1)  P(1,2)  P(1,3)]  Chiều đảo của 3) nói chung không đúng. [P(2,1)  P(2,2)  P(2,3)]  [P(3,1)  P(3,2)  P(3,3)] 19 20 5
6. Ví dụ thể hiện chiều đảo của 3 là chưa chắc đúng: Vị từ và lượng từ • Gọi p(x,y) là vị từ theo 2 biến thực p(x,y) = “x + y = 1”, • Chứng minh 3) • Nếu thay y tuỳ ý thì x = 1 - y để cho x + y = 1 Giả sử “x A, y B, p(x, y)” là đúng. nên mệnh đề x A, p(x, y) là đúng. Nên mệnh đề “y B, x A, p(x, y)” là đúng. Khi đĩ, tồn tại a A sao cho “y B, p(x, y)” • Ngược lại, nếu chọn x = a tuỳ ý, ta cĩ thể chọn à đúng, nghĩa là nếu thay y = b bất kỳ thì l B y = -a để “y B, p(x, y)” là sai. p(a,b) đúng. Như vậy, y = b B tuỳ chọn thì ta Điều này chứng tỏ, “x A, y B, p(x, y)” là sai. cĩ thể chọn x = a để “x A, p(x, y)” là đúng. • Do đĩ, phép kéo theo sau là sai: Do đĩ, “y B, x A, p(x, y)” là mệnh đề “y B, x A, p(x, y)” -> “x A, y B, p(x, đúng. y)” 21 22 Vị từ và lượng từ Vị từ và lượng từ • Trong một mệnh đề lượng từ hố từ một Định lý: vị từ theo nhiều biến độc lập, nếu ta hốn a) Với p(x) là một vị từ theo một biến xác định trên vị hai lượng từ đứng cạnh nhau thì: A, ta có: x A,, p x  x A p x 1. Mệnh đề mới vẫn cịn tương đương logic với x A,, p x  x A p x mệnh đề cũ nếu hai lượng từ này cùng loại. b) Phủ định của mệnh đề lượng từ hóa từ vị từ p(x , 2. Mệnh đề mới này sẽ là một hệ quả logic của 1 x2, , xn) có được bằng cách thay lượng từ  bằng mệnh đề cũ nếu hai lượng từ trước khi hốn lượng từ  và ngược lại, và thay vị từ p(x1, x2, , vị cĩ dạng   xn) bằng vị từ . 23 p x12, x , , xn 24 6
7. Negation Vị từ và lượng từ Phủ định của mệnh đề “Hôm nay, mọi sinh viên lớp Equivalence involving the negation operator TH1đều có mặt” là gì ? x P(x) x P(x) x P(x) x P(x) “Hôm nay, có (ít nhất) một sinh viên lớp TH1vắng mặt”. Multiple Quantifiers: read from left to right 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”. 25 26 Vị từ và lượng từ Vị từ và lượng từ Phủ định của mệnh đề “x A, 2x + 1 0” là gì ? Qui tắc đặc biệt hố phổ dụng: Phủ định của mệnh đề trên là “x A, 2x + 1 > 0”. Nếu một mệnh đề đúng cĩ dạng lượng từ Phủ định của mệnh đề hố trong đĩ một biến x A bị buộc bởi “ > 0,  > 0, x R,  x – a 0,  > 0, x R,  x – a <   (f(x) – f(a) )”. 27 28 7
8. Vị từ và lượng từ Vị từ và lượng từ Ví dụ: • Qui tắc tổng quát hố phổ dụng: “Mọi người đều chết” Nếu trong một mệnh đề lượng từ hố, khi “Socrate là người” thay một biến buộc bởi lượng từ  bằng Vậy “Socrate cũng chết” 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. 29 30 Inference Rules for Quantifiers Example Every man has two legs, John Smith is a man. • x P(x) Therefore, John Smith has two legs. P(o) (substitute any object o) Predicates: M(x): x is a man • P(g) (for g a general element of u.d.) L(x): x has two legs x P(x) J: John Smith is a member of the universe 1. x[M(x) L(x)] • x P(x) 2. M(J) L(J) P(c) (substitute a new constant c) Proof 1. x[M(x) L(x)] Hypothesis 1 • P(o) (substitute any extant object o) 2. M(J) L(J) Step 1 and UI x P(x) 3. M(J) Hypothesis 2 31 4. L(J) Step 2 and 3 and modus32 ponens 8
9. Đề thi Đề thi 1) Hãy xác đinh chân trị của mệnh đề sau: 3) Kiểm tra tính đúng đắn của suy luận sau: a) 2002 a) 2005 2 x R,(x -4x -5=0)→(x>0) x R(P(x)  Q(x)) b) 2004 x R(P(x) Q(x)→R(x)) x R,(x 3 - 4x2 +5x -2=0)(x2-3x+2 = 0) ___  x R(R(x)→P(x)) 2) 2003 b) 2006 Lấy phủ định của mệnh đề sau: x R, P(x)  x R, Q(x)) ‟ >0,>0, x, x R,(|x-x‟ |< →|f(x)-f(x‟) |< ) x R, P(x) ___ 33 x R,Q(x) 34 Đề thi Đề thi c) 2007 4) 2007.Cho biết suy luận sau đúng khơng ?Tại sao? x(P(x) Q(x))  x (P(x) Q(x)) x(Q(x) R(x)) R(a)  x (P(x)   R(x)) ___  P(a)  x (Q(x)   R(x)) Trong đĩ P(x), Q(x) và R(x) là 3 vị từ và a là một trong đĩ P(x), Q(x) và R(x) là 3 vị từ phần tử của tập vũ trụ 35 36 9
10. Đề thi Đề thi 5) 2009. 6) 2010. Kiểm tra tính đúng đắn của suy luận sau a) Một dãy số thực {xn}được nĩi là thuộc O(n) nếu tồn tại số x(P(x) Q(x)) thực dương C và số tự nhiên m sao cho xn< Cn mỗi khi x(Q(x)R(x)) n m. Hãy sử dụng mệnh đề lượng từ hĩa để viết lại định x  P(x) nghĩa trên. ___ b) Viết ra mệnh đề lượng từ hĩa cho một dãy số thực {x } n x R(x) khơng thuộc O(n). Trong đĩ P(x), Q(x) và R(x) là 3 vị từ 37 38 Bài tập Tài liệu tham khảo 7) • [1]GS.TS Nguyễn Hữu Anh, Tốn rời rạc, Xét chân trị và tìm phủ định của các mệnh đề sau: a) x R, x2 – 3x + 2 0; NXB Giáo dục b) x R, x2 – 3x + 2 0; c) x N, y R, x + y 0; • [2]TS. Trần Ngọc Hội, Tốn rời rạc d) x N, y R, x + y 0; • [3] Dr.Kossi Edoh,Department of Computer e) y R, x N, x + y 0; Science, Montclair State University f) x N, y R, x + y 0; g) x Z, y R, x + y 0; • [4] Michael P.Frank „s slides h) x Z, y R, x + y 0; 39 40 10