tailieunhanh - Applied Mathematics for Database Professionals phần 3

Mặc dù cơ sở dữ liệu phát triển lớn hơn và lớn hơn những ngày này, chúng luôn luôn hữu hạn bởi định nghĩa như trái ngược với bộ trong toán học, mà đôi khi vô hạn. Nếu bạn làm việc với giới hạn bộ chỉ, bạn luôn có thể xử lý lượng hóa tồn tại và phổ quát như lặp OR và lặp và xây dựng, tương ứng. | 54 CHAPTER 3 SOME MORE LOGIC Quantifiers and Finite Sets Although databases grow larger and larger these days they are always finite by definition as opposed to sets in mathematics which are sometimes infinite. If you work with finite sets only you can always treat the existential and universal quantifiers as iterated OR and iterated AND constructs respectively. Iteration is done over all elements of the set from which the quantifier parameter is drawn for each element value the occurrences of the variable inside the predicate are replaced by that value. This alternative way of interpreting quantified expressions might help when you investigate their truth values. For example suppose P is the set of all prime numbers less than 15 P 2 3 5 7 11 13 Then these two propositions 3xeP x 12 VyeP y 3 are logically equivalent with the following two propositions Iterate x over all elements in P 2 12 Ú 3 12 Ú 5 12 Ú 7 12 Ú 11 12 Ú 13 12 Iterate y over all elements in P 2 3 Ù 3 3 Ù 5 3 Ù 7 3 Ù 11 3 Ù 13 3 You could now manually compute the truth value of both predicates. If you evaluate the truth value of every disjunct the first proposition becomes FALSE Ú FALSE Ú . Ú FALSE Ú TRUE which results in TRUE. If you do the same for the conjuncts of the second proposition you get FALSE Ù FALSE Ù TRUE Ù . Ù TRUE which results in fAlSE. Quantification Over the Empty Set The empty set 0 contains no elements. Because it still is a set you can quantify over the empty set. The following two expressions are valid propositions 3xe0 P x Vye0 Q y But what does it mean to say that there exists an element x in the empty set for which P x holds Clearly the empty set has no elements. Therefore regardless of the involved predicate P whenever we propose that there s such an element in the empty set we must be stating something that s unmistakably FALSE because it s impossible to choose an element from the empty set. The second proposition universal quantification over the empty set is less .