Một số khái niệm cơ bản về lôgic, tập hợp và suy luận toán học

số thực R cũng là một quan hệ 2 ngôi. 5. Cho E là một tập hợp, đặt X = P(E). Mỗi phần tử thuộc X là một tập hợp con của E. Trên E có các quan hệ quen thuộc sau đây: - quan hệ bao hàm, ký hiệu bởi Ì - quan hệ chứa, ký hiệu bởi É - quan hệ bằng nhau, ký hiệu bởi = Ghi chú : Người ta còn định nghĩa một quan hệ (2 ngôi) giữa một tập hợp A và một tập hợp B là một tập hợp con của AxB. Ví dụ: A = { 1, 2, 3, 4, 5} , B = { 0, 1} . Ta có R = { (1,1), (2,0), (3,1), (4,0), (5,0)} là một quan hệ giữa A và B. Tổng quát hơn, ta có thể định nghĩa một quan hệ giữa các tập hợp A1, A2, . . ., An là một tập hợp con của A1 x A2 x . . . x An (tích Descartes của các tập hợp A1, A2, . . ., An). Như vậy, khi R là một quan hệ giữa các tập A1, A2, . . ., An thì mỗi phần tử của R là ột bộ n (a1, a2, . . ., an) với ai Î Ai (i=1, �, n). Cách xác định một quan hệ: Dựa vào các phương pháp xác định một tập hợp, ta có thể xác định một quan hệ bằng các phương pháp sau đây: Liệt kê: liệt kê tất cả các cặp hay bộ phần tử có quan hệ R (tức là thuộc R). Trong ví dụ 1 ở trên, quan hệ R được cho theo cách liệt kê. Nêu tính chất đặc trưng cho quan hệ R, tức là tính chất hay tiêu chuẩn để x�c định c�c phần tử thuộc R hay kh�ng. Trong c�c v� dụ 2 và 3 ở trên, quan hệ R được cho bằng cách nêu lên tính chất xác định quan hệ. 4.1.2 Các tính chất của quan hệ 2 ngôi Một quan hệ 2 ngôi trên một tập hợp có thể có một số tính chất nào đó làm cho tập hợp có một cấu trúc nhất định. Dưới đây là định nghĩa một số tính chất thường được xét đối với một quan hệ 2 ngôi.     Định nghĩa : Giả sử R là một quan hệ 2 ngôi trên một tập hợp X.  R có tính phản xạ (reflexive) nếu và chỉ nếu x R x với mọi x Î X. R có tính đối xứng (symmetric) nếu và chỉ nếu x R y Þ y R x với mọi x,y Î X. R có tính phản xứng (antisymmetric) nếu và chỉ nếu (x R y và y R x) Þ x = y với mọi x,y Î X. R có tính bắc cầu (transitive) nếu và chỉ nếu (x R y và y R z) Þ x R z với mọi x,y,z Î X. Ví dụ: Trong ví dụ nầy chúng ta đề cập đến một số quan hệ đã được nêu lên trong các ví dụ của mục 1.1 ở trên, và phát biểu các tính chất của chúng. Việc kiểm chứng các tính chất nầy khá dễ dàng. 1. Quan hệ đồng dư modulo n trên Z có 3 tính chất: phản xạ, đối xứng, truyền. 2. Quan hệ £ trên tập hợp các số thực có 3 tính chất: phản xạ, phản xứng, truyền. 3. Cho E là một tập hợp. Quan hệ Í trên P(E) có 3 tính chất: phản xạ, phản xứng, truyền. 4.1.3 Biểu diễn quan hệ 2 ngôi dưới dạng ma trận     Ngoài phương pháp biểu diễn một quan hệ 2 ngôi dưới dạng tập hợp các cặp phần tử người ta còn có thể sử dụng ma trận để biểu diễn cho quan hệ trong trường hợp các tập hợp là hữu hạn. Khái niệm ma trận sẽ được định nghĩa và khảo sát chi tiết hơn trong phần "Đại số Tuyến tính". Ở đây chúng ta chỉ cần hiểu ma trận một cách đơn giản là một bảng liệt kê các phần tử thành các dòng và các cột. Ví dụ, bảng liệt kê 6 số nguyên thành 2 dòng và 3 cột sau đây là một ma trận:     Một ma trận M gồm m dòng, n cột sẽ được gọi là một ma trận có cấp mxn. Nếu m = n thì ta nói M là một ma trận vuông cấp n.     Giả sử R là một quan hệ 2 ngôi giữa một tập hợp hữu hạn A = { a1, a2, ... , am} và một tập hữu hạn B = { b1, b2, ... , bm} . Quan hệ R có thể được biểu diễn bởi ma trận MR = [mij] gồm m dòng và n cột (tức là ma trận cấp mxn), trong đó: mij = 1 nếu (ai , bj) Î R mij = 0 nếu (ai , bj) Ï R Ta gọi ma trận MR là ma trận biểu diễn của quan hệ R. Ví dụ: Với A = { 1,2,3} và B = { a, b, c} , thì các quan hệ sau đây: R = { (1,a), (1,b), (1,c)} S = { (1,a), (1,b), (1,c), (2,b), (2,c), (3,c)} có các ma trận biểu diễn là MR = , MS = Trong trường hợp R là một quan hệ 2 ngôi trên một tập X hữu hạn và có n phần tử thì ma trận biểu diễn của R là một ma trận có n dòng và n cột (tức là ma trận vuông cấp n). Ghi chú: Ngoài cách biểu diễn quan hệ dưới dạng ma trận ta còn biểu đồ (dạng đồ thị) để biểu diễn quan hệ. Cách biểu diễn nầy sẽ được xét đến trong phần sau, khi nói về biểu đồ Hasse của một cấu trúc thứ tự. 4.2. Quan hệ tương đương ĐN: Quan hệ trên A được gọi là quan hệ tương đương nếu nó có ba tính chất phản xạ, đối xứng, bắc cầu. Cho là quan hệ tương đương trên tập A và phần tử . Tập con của A gồm các phần tử b có quan hệ với a được gọi là lớp tương đương của phần tử a, ký hiệu là . Cho và quan hệ tương đương . Khi đó , (lớp tương đương của một pt bất kỳ khác rỗng) hoặc ,hoặc . Từ đó tập các lớp tương đương của tạo thành một phân hoạch của tập A. Một ví dụ minh hoạ cho quan hệ tương đương là quan hệ đồng dư theo môđun m trên tập hợp các số nguyên ( m là số tự nhiên lớn hơn 1), mỗi lớp tương đương là tập các số nguyên có cùng số dư theo môđun m. Trong số học nó còn được gọi là các lớp thặng dư theo môdun m. 4.3. Quan hệ thứ tự Quan hệ trên tập A được gọi là quan hệ thứ tự trên A nếu nó có ba tính chất phản xạ, phản đối xứng và bắc cầu. Ví dụ về các quan hệ thứ tự là các quan hệ "≤", "≥" trên các tập hợp số. Một ví dụ khác là quan hệ chia hết "\" trên tập số tự nhiên, quan hệ bao hàm "" (quan hệ tập con) trong các tập hợp cũng là các quan hệ thứ tự. Sau đây ta dùng ký hiệu để chỉ một quan hệ thứ tự trong trường hợp tổng quát. Quan hệ thứ tự được gọi là quan hệ thứ tự toàn phần trên tập A nếu với hai phần tử bất kỳ một trong hai quan hệ hoặc sẽ xẩy ra. Trong trường hợp ngược lại nó được gọi là quan hệ thứ tự bộ phận. Khi đó, tương ứng ta nói tập A được sắp thứ tự toàn phần/bộ phận. Khi không muốn nói vào chi tiết ta đơn giản gọi chúng là tập được sắp. Các quan hệ "≤" và "≥" trên tập số thực là quan hệ thứ tự toàn phần. Quan hệ chia hết trên tập số nguyên, quan hệ bao hàm trên các tập hợp là các quan hệ thứ tự bộ phận. * Các phần tử đặc biệt trong tập được sắp Trong tập A được sắp theo quan hệ , một phần tử m được gọi là nhỏ nhất nếu với mọi . Ví dụ như phần tử nhỏ nhất của tập các số tự nhiên dương là 1, phần tử nhỏ nhất theo quan hệ bao hàm trên các tập hợp là tập rỗng, theo quan hệ chia hết trên tập các số tự nhiên phần tử nhỏ nhất là số 1. Cho S là tập con của tập được sắp A theo quan hệ . Phần tử m (nếu có) được gọi là infimum của S, kí hiệu là ìn(S) hay ^S, nếu với mọi và nếu thì . Nếu S= {a, b} thì inf({x,y}) được ký hiệu là x^y. Trong quan hệ chia hết trên tập các số tự nhiên, x^y chính là ƯCNN(x,y), còn theo quan hệ bao hàm giữa các tập hợp, A^B chính là tập . Khái niệm tương tự theo chiều ngược lại là khái niệm supremum, ký hiệu là sub(S) Suy luận toán học 5.1 Các phương pháp chứng minh 5.1.1 Chứng minh trực tiếp Trong chứng minh trực tiếp, kết luận có được bằng cách phối hợp một cách lôgic các tiên đề, định nghĩa, và các định lý trước đó. Ví dụ, chứng minh rằng tổng của hai số nguyên chẵn luôn luôn là số chẵn: x, y 2Z: ta có x = 2a và y = 2b (a, b Z), x + y = 2a + 2b = 2(a + b) 2Z đcpcm. 5.1.2 Chứng minh bằng quy nạp toán học Trong cách chứng minh bằng quy nạp toán học, đầu tiên "trường hợp cơ sở" sẽ được chứng minh, sau đó sẽ dùng một "luật quy nạp" để chứng minh (thường là vô tận) các trường hợp khác. Vì trường hợp cơ sở là đúng, tất cả các trường hợp khác cũng phải đúng, thậm chí nếu ta không thể chứng minh trực tiếp tất cả chúng là đúng vì số lượng vô tận của nó. Một dạng con của quy nạp là phương pháp xuống thang. Phương pháp xuống thang được dùng để chứng minh sự vô tỷ của căn bậc 2 của 2. Nguyên tắc quy nạp toán học như sau: Cho N = { 1, 2, 3, 4, ... } là tập các số tự nhiên và P(n) là một phát biểu toán học liên quan tới một số tự nhiên n thuộc N sao cho: (i) P(1) là đúng, tức là, P(n) là đúng khi n = 1 (ii) Giả sử P(n) đúng, ta chứng minh P(n + 1) cũng đúng. Kết luận: P(n) đúng với mọi số tự nhiên n Các nhà toán học thường dùng cụm từ "chứng minh bằng quy nạp" để nói tắt cho chứng minh bằng quy nạp toán học. Tuy vậy, thuật ngữ "chứng minh bằng quy nạp" cũng được dùng trong logic để nói đến một tranh luận sử dụng suy diễn quy nạp. 5.1.3 Chứng minh bằng chuyển vế Chứng minh bằng chuyển vế sẽ hình thành kết luận "nếu p thì q" bằng cách chứng minh phát biểu tương phản tương đương "nếu không q thì không p". 5.1.4 Chứng minh bằng phản chứng Trong chứng minh bằng phản chứng (còn được gọi là reductio ad absurdum, tiếng La tinh có nghĩa là "thu giảm đến sự vô lý"), người ta sẽ chứng minh nếu một phát biểu nào đó xảy ra, thì dẫn đến mâu thuẫn về lôgic, vì vậy phát biểu đó không được xảy ra. Phương pháp này có lẽ là phương pháp phổ biến nhất trong chứng minh toán học. Một ví dụ nổi tiếng về cách chứng minh phản chứng là để chứng minh là một số vô tỷ: Giả sử là số hữu tỷ, ta sẽ biểu diễn được trong đó a và b là các số nguyên khác không có ước chung lớn nhất là 1 (theo định nghĩa số hữu tỷ). Do đó, . Bình phương hai vế cho ra 2b2 = a2. Vì vế trái chia hết cho 2, nên vế phải cũng phải chia hết cho 2 (vì chúng bằng nhau và đều là số nguyên). Do đó a2 là số chẵn, có nghĩa là a cũng phải là số chẵn. Dẫn đến ta có thể viết a = 2c, trong đó c cũng là số nguyên. Thay vào phương trình ban đầu cho ra 2b2 = (2c)2 = 4c2. Chia hai vế cho 2 ta được b2 = 2c2. Nhưng khi đó, tương tự như trên, b2 chia hết cho 2, nên b phải là số chẵn. Nhưng nếu a và b đều là số chẵn, chúng sẽ có chung một ước số là 2. Điều này trái với giả thuyết, do đó mà chúng ta buộc phải kết luận rằng là số vô tỷ. 5.1.5 Chứng minh bằng dẫn chứng Chứng minh bằng dẫn chứng, là đưa ra một dẫn chứng cụ thể với một thuộc tính nào đó để chứng minh rằng có tồn tại một thứ có tính chất như vậy. Ví dụ như Joseph Liouville đã chứng minh tồn tại số siêu việt bằng cách đưa ra một ví dụ rõ ràng. 5.1.6 Chứng minh vét cạn Trong chứng minh vét cạn, kết luận sẽ có được bằng cách chia nhỏ nó ra thành một số trường hợp hữu hạn và chứng minh mỗi trường hợp một cách riêng rẽ. Số trường hợp đôi khi rất lớn. Ví dụ như, cách chứng minh định lý bốn màu đầu tiên là một chứng minh vét cạn với 1.936 trường hợp. Cách chứng minh này còn gây tranh cãi vì đa số các trường hợp được kiểm chứng bằng chương trình máy tính, chứ không phải bằng tay. Cách chứng minh đã biết tới ngắn nhất của định lý bốn màu ngày nay vẫn có tới hơn 600 trường hợp. 5.1.7 Chứng minh với sự hỗ trợ của máy tính Cho đến thế kỷ thứ 20 người ta đã giả thiết rằng, trên nguyên tắt, tất cả các chứng minh đều có thể được một nhà toán học giỏi xác nhận sự đúng đắn của nó. Tuy nhiên, ngày nay máy tính được dùng cả để chứng minh các định lý lẫn thực hiện các phép toán quá dài mà con người hoặc một nhóm người có thể kiểm tra nổi; cách chứng minh định lý bốn màu đầu tiên là một ví dụ về một cách chứng minh có sự hỗ trợ từ máy tính. Một số nhà toán học lo ngại rằng khả năng xảy ra lỗi trong một chương trình máy tính hoặc lỗi khi tính toán có thể khiến cho sự đúng đắn của các cách chứng minh bằng máy tính bị đặt dấu hỏi. Trên thực tế, cơ hội xảy ra lỗi để bác bỏ một chứng minh của máy tính có thể giảm thiểu bằng cách đưa vào sự trùng lặp và tự kiểm tra khi tính toán, và bằng cách phát triển nhiều cách tiếp cận và chương trình độc lập nhau. 5.2 Quy nạp toán học (đọc trong TL1) 5.3 Đệ quy và ứng dụng (đọc trong TL1) Bài tập: Từ trang 37 đến trang 44 - TL1 Phạm Thế Long, Toán rời rạc, Nhà xuất bản ĐHSP, 2004 Phụ lục 1 (tài liệu của GV)