Toán rời rạc P2

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ử, ứ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
Predicates and Quantifiers
Propositional functions or predicates are propositions
which contain variables
Example Let P denote the Predicate “is greater than 0”
and P(x) denote “x > 0”
x is called a variable

The predicate become a proposition once the variable
x has been assigned a value.
Example
What is the truth value of p(5), p(0) and p(-2)?

“5>0” is true, “0>0” is false and “-2>0” is false
4
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).
5
Vị từ và lượng từ
Ví dụ 2
Xét p(x,y) = “x2 + 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.
6
Examples
Example:
Let Q(x,y) denote the statement “y =x + 2”.
What is the truth value of
Q(2,4,) and Q(4, 1)
“4 = 2+2” is true and “1 = 4+2” is false

Q(2,y)  Q(0,3) is not a proposition: y is not bounded
Q(1,3)  Q(0,1) is a proposition which is true
Q(2,y)  Q(0,3) is a proposition???
Q(1,3)  Q(0,1) is a proposition ???
7
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 vị từ p(x) kí hiệu là p(x) là vị từ mà khi thay x bởi một 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(x) 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 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))
8
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.
9
Universe of Discourse
Question
Let R be the three-variable predicate R(x,y,z):
x+y = z
Find the truth value of
R(2,-1,5), R(3,4,7) R(x,3,z)

A universe of discourse (U) is a domain for the
variables of a propositional function.

Example
Let U = Z, the integers = {…, -2, -1, 0, 1, 2, …}
10
Universal quantifier
The Universal Quantifier of P(x):
is the proposition
“P(x) is true for every x in the universe of discourse”
Notation: x P(x)
`For all x, P(x)’ `For every x, P(x)’

Example:
U = {1, 2, 3} x P(x)  P(1)  P(2)  P(3)
Example
What is the truth value of x P(x) if P(x) is “3x <10”and
U is positive integers not exceeding 4
P(1)  P(2)  P(3)  P(4) is false
11
Existential quantifier
The Existential Quantifier of P(x):
is the proposition
“P(x) is true for some x in the universe of discourse”
Notation: x P(x)
‘For some x P(x)’ ‘For at least an x in P(x)’

Example:
U = {1, 2, 3}, x P(x)  P(1)  P(2)  P(3)
Example
What is the truth value of x P(x) if P(x) is “3x <10”and
U is positive integers not exceeding 4
P(1)  P(2)  P(3)  P(4) is True
12
Vị từ và lượng từ
1) Mệnh đề "?x ? R, x2 + 3x + 1 ? 0" là một mệnh đề sai hay d�ng ?
2) Mệnh đề "?x ? R, x2 + 3x + 1 ? 0" l� một mệnh đề đúng hay sai?
M?nh d? sai vì tồn tại x0 = 1 ? R mà x02 + 3x0 + 1 ? 0
Mệnh đề đúng vì tồn tại x0 = -1 ? R mà x02 + 3x0 + 1 ? 0.
13
Vị từ và lượng từ
Mệnh đề "?x ? R, x2 + 1 ? 2x" là một mệnh đề đúng hay sai?
M?nh d? d�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 đề d�ng hay sai?
14
Vị từ và lượng từ
Định nghĩa:
Cho p(x, y) laø moät vò töø theo hai bieán x, y xaùc ñònh treân AB. Ta ñònh nghóa caùc meänh ñeà löôïng töø hoùa cuû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))”
15
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" d�ng hay sai?
M?nh d? 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 d? d�ng vì với mỗi x = a ? R, tồn tại ya ? R nhu
ya = -a/2, sao cho a + 2ya < 1.
16
Vị từ và lượng từ

Mệnh đề "?x ? R, ?y ? R, x + 2y < 1" d�ng hay sai
M?nh d? 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 d? d�ng vì tồn tại x0 = 0, y0 = 0 ? R chẳng hạn thỏa
x0 + 2y0 < 1.
17
Translate into English
Example
Translate the statement
x(C(x)  y(C(y) F(x,y))) into English
Where C(x) is “x has a computer”
F(x,y) is “x and y are friends”
and U is x and y are students in your school

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.
18
Example
Example:Let U = R, the real numbers. P(x,y): xy = 0
xy P(x,y)
x y P(x,y)
x y P(x,y)
x y P(x,y)
False
True
True
True
Example: Let U={1, 2, 3}. Find an expression equivalent to x y P(x,y) where the variables are bound by substitution instead:
Solution: y P(1,y)  y P(2,y)  y P(3,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)]
19
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.
20
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.
21
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)”

22
Vị từ và lượng từ
Trong một mệnh đề lượng từ hoá từ một vị từ theo nhiều biến độc lập, nếu ta hoán vị hai lượng từ đứng cạnh nhau thì:
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.
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 hoán vị có dạng  
23
Vị từ và lượng từ
Định lý:
a) Vôùi p(x) laø moät vò töø theo moät bieán xaùc ñònh treân A, ta coù:


b) Phuû ñònh cuûa meänh ñeà löôïng töø hoùa töø vò töø p(x1, x2, ..., xn) coù ñöôïc baèng caùch thay löôïng töø  baèng löôïng töø  vaø ngöôïc laïi, vaø thay vò töø p(x1, x2, ..., xn) baèng vò töø .
24
Negation
Equivalence involving the negation operator
x P(x)  x P(x)
x P(x)  x P(x)
Multiple Quantifiers: read from left to right

25
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ì ?
Phủ định của mệnh đề "Trong lớp TH2có (ít nhất một) sinh viên được thưởng" là gì?
"Hôm nay, có (ít nhất) một sinh viên lớp TH1vắng mặt".
"Trong lớp TH2không có sinh viên nào được thưởng".
26
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 đề
"?? > 0, ?? > 0, ?x ? R, ? x - a? < ? ? ?f(x) - f(a)? < ?".
(điều kiện để hàm số f(x) liên tục tại x = a)
Phủ định của mệnh đề tr�n l� "?x ? A, 2x + 1 > 0".
Phủ định của mệnh d? tr�n là:
"?? > 0, ?? > 0, ?x ? R, ? x - a? < ? ? (?f(x) - f(a)? ? ?)".
27
Vị từ và lượng từ
Qui t?c d?c bi?t hố ph? d?ng:
N?u m?t m?nh d? d�ng cĩ d?ng lu?ng t? hố trong dĩ m?t bi?n x ? A b? bu?c b?i lu?ng t? ph? d?ng ?, khi ?y n?u thay th? x b?i a ? A ta s? du?c m?t m?nh d? d�ng.
28
Vị từ và lượng từ
Ví d?:
"M?i ngu?i d?u ch?t"
"Socrate l� ngu?i"
V?y "Socrate cung ch?t"
29
Qui tắc tổng quát hoá phổ dụng:
Nếu trong một mệnh đề lượng từ hoá, 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ừ hoá ban đầu cũng có chân trị 1.
Vị từ và lượng từ
30
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)
Universal instantiation
Universal generalization
Existential instantiation
Existential generalization
31
Example
Every man has two legs, John Smith is a man.
Therefore, John Smith has two legs.
Predicates: M(x): x is a man
L(x): x has two legs
J: John Smith is a member of the universe
1. x[M(x)  L(x)]
2. M(J) L(J)
Proof 1. x[M(x)  L(x)] Hypothesis 1
2. M(J)  L(J) Step 1 and UI
3. M(J) Hypothesis 2
4. L(J) Step 2 and 3 and modus
ponens
32
Đề thi
1) Hãy xác đinh chân trị của mệnh đề sau:
a) 2002
xR,(x2-4x -5=0)→(x>0)
b) 2004
xR,(x 3 - 4x2 +5x -2=0)(x2-3x+2 = 0)

2) 2003
Lấy phủ định của mệnh đề sau:
>0,>0, x, x’R,(|x-x’ |< →|f(x)-f(x’) |< )
33
Đề thi
3) Kiểm tra tính đúng đắn của suy luận sau:
a) 2005
xR(P(x)  Q(x))
xR(P(x) Q(x)→R(x))
________________________
xR(R(x)→P(x))

b) 2006
xR, P(x)  xR, Q(x))
xR, P(x)
___________________
xR,Q(x)
34
Đề thi
c) 2007

 x (P(x)  Q(x))
 x (P(x)   R(x))

 x (Q(x)   R(x))
trong đó P(x), Q(x) và R(x) là 3 vị từ
35
Đề thi
4) 2007.Cho biết suy luận sau đúng không ?Tại sao?
x(P(x) Q(x))
x(Q(x)R(x))
R(a)
___________
P(a)
Trong đó P(x), Q(x) và R(x) là 3 vị từ và a là một
phần tử của tập vũ trụ
36
Đề thi
5) 2009.
a) Một dãy số thực {xn}được nói là thuộc O(n) nếu tồn tại số
thực dương C và số tự nhiên m sao cho xn< Cn mỗi khi
n  m. Hãy sử dụng mệnh đề lượng từ hóa để viết lại định
nghĩa trên.
b) Viết ra mệnh đề lượng từ hóa cho một dãy số thực {xn}
không thuộc O(n).
37
Bài tập
6). Xét chân trị và tìm phủ định của các mệnh đề sau:
a) ?x ? R, x2 - 3x + 2 ? 0;
b) ?x ? R, x2 - 3x + 2 ? 0;
c) ?x ? N, ?y ? R, x + y ? 0;
d) ?x ? N, ?y ? R, x + y ? 0;
e) ?y ? R, ?x ? N, x + y ? 0;
f) ?x ? N, ?y ? R, x + y ? 0;
g) ?x ? Z, ?y ? R, x + y ? 0;
h) ?x ? Z, ?y ? R, x + y ? 0;
38
Tài liệu tham khảo
[1]GS.TS Nguyễn Hữu Anh, Toán rời rạc, NXB Giáo dục
[2]TS. Trần Ngọc Hội, Toán rời rạc
[3] Dr.Kossi Edoh,Department of Computer Science, Montclair State University
[4] Michael P.Frank ‘s slides
39