(NB) Giáo trình Cơ sở toán cho tin học cung cấp cho người học những kiến thức như: Quan hệ - Suy luận toán học; tính toán và xác suất; ma trận và thuật toán; phương pháp tính. Mời các bạn cùng tham khảo!
QUAN HỆ VÀ SUY LUẬN TOÁN HỌC
Suy luận toán học
2 Chương 2: Tính toán và xác suất 8 6 2
3 Chương 3 : Ma trận và thuật toán 8 7 0 1
1 Số xấp xỉ và sai số 1
2 Giải gần đúng các phương trình 2 1
3 Giải hệ thống phương trình đại số tuyến tính 2 1
4 Nội suy và phương pháp bình phương cực tiểu 2 1
5 Thi kết thúc môn học 1 1
CHƯƠNG 1: QUAN HỆ VÀ SUY LUẬN TOÁN HỌC
Mã chương: MHLTV 11-01 Giới thiệu:
Mệnh đề là mảng kiến thức khá đơn giản nhưng ảnh hưởng rất nhiều đến các định hướng logic trong toán học.
Mệnh đề có thể là một câu, nhưng không phải tất cả các câu đều là mệnh đề Trong khoa học và cuộc sống, câu có thể được phân thành hai loại: loại đầu tiên phản ánh tính đúng hoặc sai của một thực tế khách quan, trong khi loại thứ hai không phản ánh tính đúng hay sai nào.
Suy luận là quá trình rút ra các kết luận logic từ những mệnh đề đã được xác định là chân lý hoặc được giả định là đúng Các kết luận này được gọi là thành ngữ và quy tắc suy luận là một phần quan trọng trong nghiên cứu logic.
- Trình bày được các phép toán trong quan hệ hai ngôi;
- Trình bày được thứ tự các phép toán trong biểu thức;
- Biến đổi chính xác các quan hệ tương đương trong các bài toán theo dạng quan hệ;
- Trả lời chính xác các bảng trắc nghiệm về quan hệ hai ngôi và suy luận toán học;
- Kiểm tra tính đúng của một chương trình cụ thể;
- Áp dụng được giải thuật quy nạp và đệ qui;
- Thực hiện các thao tác an toàn với máy tính.
-Trình bày được các phép toán trong quan hệ hai ngôi;
-Trình bày được thứ tự các phép toán trong biểu thức;
-Biến đổi chính xác các quan hệ tương đương trong các bài toán theo dạng quan hệ.
1.1 Khái niệm về quan hệ hai ngôi
Giả sử tập X không rỗng và tồn tại một tính chất ℜ được thỏa mãn với một số cặp phần tử a, b trong X Khi đó, chúng ta nói rằng a có quan hệ ℜ với b, ký hiệu là a ℜ b, và ℜ được gọi là quan hệ hai ngôi trong tập X.
1) Trong tập R mọi số thực, quan hệ “a = b” hoặc quan hệ “a ≤ b” là quan hệ hai ngôi.
2) Trong tập mọi đường thẳng trên mặt phẳng, quan hệ vuông góc giữa hai đường thẳng là quan hệ hai ngôi.
3) Trên tập N* các số nguyên dương, “ a là ước số của b” là quan hệ hai ngôi.
4) Trên tập P(E) các phân tập của tập E quan hệ bao hàm A ⊂ B là quan hệ hai ngôi.
1.2 Các tính chất có thể có của quan hệ trong một tập hợp
Quan hệℜ trong tập X (tứcℜ ⊂X 2 ) có thể có các tính chất sau:
- Tính phản xạ : aℜ a ∀a∈ X (tức là (a, a)∈ ℜ ∀ a ∈ X )
- Tính đối xứng : a ℜ b ⇒ b ℜ a (tức nếu (a, b) ∈ ℜ thì (b, a) ∈ ℜ )
- Tính phản đối xứng : (a ℜb và b ℜa ) ⇒a = b
Trong tập hợp P(X) các phân tập của tập hợp X quan hệ bao hàm A⊂ B có tính phản xạ, phản đối xứng và bắc cầu mà không có tính đối xứng.
Trong tập hợp mọi đa thức của một biến số thực, quan hệ bằng nhau có tính phản xạ, đối xứng và bắc cầu.
Quan hệ ℜ trong tập X gọi là quan hệ tương đương nếu nó có tính phản xạ, đối xứng, bắc cầu.
Trong trường hợp này, ta viết a ~ b thay vì a ℜb
Trong không gian, các đường thẳng có thể có quan hệ song song, bao gồm cả trường hợp hai đường thẳng trùng nhau Bên cạnh đó, quan hệ đồng dạng giữa các tam giác và quan hệ cùng tỉnh giữa một tập hợp dân cư trong thành phố cũng là những ví dụ điển hình thể hiện mối quan hệ tương đương.
Giả sử ~ là một quan hệ tương đương trong tập hợp X Đối với mỗi phần tử a thuộc X, ta định nghĩa C(a) là tập hợp tất cả các phần tử trong X tương đương với a, và gọi C(a) là lớp tương đương chứa a.
Do tính phản xạ a ≈ a nên mỗi tập con C(a) không rỗng Hơn nữa nếu C(a)∩C(b)≠ỉ thỡ c(a) = c(b).
Thật vậy, giả sử c∈C(a)∩C(b), thì ta có : c∈C(a) và c∈C(b) Tức là c ~ a và c ~ b, hay b ~ c ~ a Từ đó do tính chất bắc cầu, suy ra b ~ a, vậy b∈C(a).
Lập luận tương tự ta cũng có a∈C(b), tức là C(a) = C(b).
Từ đó rút ra được định lý :
Một quan hệ tương đương trong X xác định một phân hoạch của X, mỗi phần tử của phân hoạch này là một lớp tương đương.
Họ các lớp tương đương này được gọi là tập thương, ký hiệu X/~.
Ví dụ 1.4: Trong tập các số nguyên Z.
⇒(a – c) = (a – b) + (b – c) = 2(p + q) bắc cầu Vậy ℜ là một quan hệ tương đương.
- Lớp tương đương ứng với b = 0 là các số chẳn.
- Lớp tương đương ứng với b = 1 là các số lẻ.
1.4 Quan hệ thứ tự Định nghĩa 1.1:Quan hệ ℜ trong X gọi là quan hệ thứ tự (hay quan hệ bộ phận) nếu có tính phản đối xứng và bắc cầu.
Nếu ngoài ra với bất kỳ hai phần tử nào x∈X, y∈Y đều có x ℜy hoặc y ℜx thì ℜgọi là quan hệ thứ tự toàn phần (hay thứ tự tuyến tính).
Khi ℜ là một quan hệ thứ tự trong tập hợp X, chúng ta nói rằng X được xếp thứ tự bởi ℜ Thay vì viết x ℜ y, ta sử dụng ký hiệu x ≤ y để diễn tả "x bé hơn y" hoặc "x đi trước y" Tương tự, ta viết y ≥ x để thể hiện "y lớn hơn x" hoặc "y đi sau x".
Nếu x≤ y và x≠ y ta viết x < y (hay y > x).
Quan hệ < hoặc≤ thông thường trong tập hợp các số thực là quan hệ thứ tự toàn phần, R là tập được sắp thứ tự.
Quan hệ bao hàm⊂ trong tập P(X) mọi tập con của tập X là quan hệ thứ tự bộ phận Tuy nhiên nó không là thứ tự toàn phần.
Quan hệ "a⋮ b" cho thấy a là bội số của b trong tập N*, tạo thành một quan hệ thứ tự bộ phận Tập X với quan hệ thứ tự đã được xác định được gọi là tập được sắp xếp.
-Trình bày chính xác về quy nạp toán học và đệ quy;
-Kiểm tra tính đúng của một chương trình cụ thể;
-Áp dụng được giải thuật quy nạp và đệ quy.
Quy nạp toán học là một kỹ thuật chứng minh hữu ích để xác nhận tính đúng đắn của các định lý dạng P(n) cho mọi n nguyên dương Phương pháp này thường được áp dụng để chứng minh các mệnh đề ∀P(n), trong đó n là số nguyên dương tùy ý.
Qua trình chứng minh P(n) là đúng với mọi số nguyên dương n bao gồm hai bước :
Bước cơ sở : Chỉ ra mệnh đề P(1) là đúng.
Bước quy nạp : chứng minh phép kéo theo P(n)" P(n + 1) là đúng với mọi số nguyên dương n, trong khi đó người ta gọi P(n) là giả thiết quy nạp.
Khi hoàn thành cả hai bước chúng ta đã chứng minh P(n) là đúng với mọi n nguyên dương, tức là đã chứng minh P(n) là đúng.
Ví dụ 2.1: Bằng quy nạp toán học hãy chứng minh rằng tổng n số nguyên dương lẻ đầu tiên là n 2
Để chứng minh mệnh đề P(n) “tổng n số nguyên dương lẻ đầu tiên là n^2”, trước tiên, ta cần xác minh bước cơ sở P(1) là đúng Tiếp theo, chúng ta sẽ thực hiện bước quy nạp, tức là chứng minh rằng nếu P(n) đúng, thì P(n + 1) cũng đúng.
Bước cơ sở : P(1) hiển nhiên là đúng vì 1 = 1 2
Bước quy nạp : Giả sử P(n) đúng, tức là với mọi n nguyên dương lẻ ta có :
Ta phải chỉ ra P(n+1) là đúng, tức là :
Do giả thuyết quy nạp ta suy ra :
= n 2 +(2n+1) = (n+1) 2 Đẳng thức này chứng tỏ P(n+1) được suy ra từ P(n).
Theo nguyên lý quy nạp toán học, nếu P(1) đúng và P(n) kéo theo P(n + 1) đúng với mọi n nguyên dương, thì P(n) sẽ đúng với mọi n nguyên dương.
2.2.Định nghĩa bằng đệ quy Đôi khi chúng ta rất khó định nghĩa một đối tượng một cách tường minh, nhưng có thể dễ dàng địng nghĩa đối tượng này qua chính nó.Kỹ thuật này được gọi là đệ quy. a Các hàm được định nghĩa bằng đệ quy Để định nghĩa một hàm xác định trên tập các số nguyên không âm, chúng ta cho:
• Giá trị của hàm tại n = 0.
Giá trị của một hàm tại số nguyên n có thể được tính dựa trên các giá trị của nó tại những số nguyên nhỏ hơn Phương pháp này được gọi là định nghĩa đệ quy hoặc định nghĩa quy nạp.
Ví dụ 2.2: Giả sử f được định nghĩa bằng đệ quy như sau : f(0) = 3, f(n+1) = 2f(n)+3 Hãy tìm f(1), f(2), f(3) và f(4).
Theo định nghĩa đệ quy, ta có thể tính giá trị của hàm f như sau: f(1) = 2f(0) + 3 = 9, f(1) = 2f(1) + 3 = 21, f(1) = 2f(2) + 3 = 45, và f(1) = 2f(3) + 3 = 93 Trong một số định nghĩa hàm đệ quy, giá trị của hàm được xác định tại k số nguyên dương đầu tiên và quy tắc tính toán giá trị cho các số nguyên dương lớn hơn được xây dựng từ k giá trị này Theo nguyên lý thứ hai của quy nạp toán học, cách định nghĩa này dẫn đến các hàm hoàn toàn xác định.
Các tập hợp thường được định nghĩa theo phương pháp đệ quy, bắt đầu bằng một tập xuất phát và quy tắc tạo ra các phần tử mới từ các phần tử đã biết Những tập hợp này được gọi là tập hợp định nghĩa tốt, và các định lý liên quan đến chúng có thể được chứng minh dựa trên định nghĩa đệ quy.
Ví dụ 2.3: Giã sử S được định nghĩa bằng đệ quy như sau :
Hãy chỉ ra rằng S là tập các số nguyên chia hết cho 3.
Gọi A là tập hợp các số nguyên dương chia hết cho 3 Để chứng minh A = S, chúng ta cần chứng minh rằng A là tập con của S và ngược lại, S là tập con của A Đầu tiên, để chứng minh A là tập con của S, giả sử P(n) là mệnh đề “3n thuộc tập S” Ta thấy P(1) đúng vì theo định nghĩa của S, 3.1 = 3 thuộc S.
TÍNH TOÁN VÀ XÁC SUẤT
Xác suất
3 Chương 3 : Ma trận và thuật toán 8 7 0 1
1 Số xấp xỉ và sai số 1
2 Giải gần đúng các phương trình 2 1
3 Giải hệ thống phương trình đại số tuyến tính 2 1
4 Nội suy và phương pháp bình phương cực tiểu 2 1
5 Thi kết thúc môn học 1 1
CHƯƠNG 1: QUAN HỆ VÀ SUY LUẬN TOÁN HỌC
Mã chương: MHLTV 11-01 Giới thiệu:
Mệnh đề là mảng kiến thức khá đơn giản nhưng ảnh hưởng rất nhiều đến các định hướng logic trong toán học.
Mệnh đề có thể được coi là một câu, nhưng không phải mọi câu đều là mệnh đề Trong khoa học và cuộc sống, các câu có thể được phân loại thành hai loại: loại thứ nhất phản ánh tính đúng hoặc sai của một thực tế khách quan, trong khi loại thứ hai không phản ánh tính đúng hoặc sai của bất kỳ thực tế nào.
Suy luận là quá trình rút ra các kết luận logic từ những mệnh đề đã được xác nhận hoặc giả định là đúng Những kết luận này thường được gọi là thành ngữ Quy tắc suy luận là một chủ đề quan trọng trong lĩnh vực logic.
- Trình bày được các phép toán trong quan hệ hai ngôi;
- Trình bày được thứ tự các phép toán trong biểu thức;
- Biến đổi chính xác các quan hệ tương đương trong các bài toán theo dạng quan hệ;
- Trả lời chính xác các bảng trắc nghiệm về quan hệ hai ngôi và suy luận toán học;
- Kiểm tra tính đúng của một chương trình cụ thể;
- Áp dụng được giải thuật quy nạp và đệ qui;
- Thực hiện các thao tác an toàn với máy tính.
-Trình bày được các phép toán trong quan hệ hai ngôi;
-Trình bày được thứ tự các phép toán trong biểu thức;
-Biến đổi chính xác các quan hệ tương đương trong các bài toán theo dạng quan hệ.
1.1 Khái niệm về quan hệ hai ngôi
Giả sử tập X không rỗng và có một tính chất ℜ được thỏa mãn với một số cặp phần tử a, b thuộc X Khi đó, ta nói rằng a có quan hệ ℜ với b, ký hiệu là a ℜ b, và ℜ được gọi là một quan hệ hai ngôi trong tập X.
1) Trong tập R mọi số thực, quan hệ “a = b” hoặc quan hệ “a ≤ b” là quan hệ hai ngôi.
2) Trong tập mọi đường thẳng trên mặt phẳng, quan hệ vuông góc giữa hai đường thẳng là quan hệ hai ngôi.
3) Trên tập N* các số nguyên dương, “ a là ước số của b” là quan hệ hai ngôi.
4) Trên tập P(E) các phân tập của tập E quan hệ bao hàm A ⊂ B là quan hệ hai ngôi.
1.2 Các tính chất có thể có của quan hệ trong một tập hợp
Quan hệℜ trong tập X (tứcℜ ⊂X 2 ) có thể có các tính chất sau:
- Tính phản xạ : aℜ a ∀a∈ X (tức là (a, a)∈ ℜ ∀ a ∈ X )
- Tính đối xứng : a ℜ b ⇒ b ℜ a (tức nếu (a, b) ∈ ℜ thì (b, a) ∈ ℜ )
- Tính phản đối xứng : (a ℜb và b ℜa ) ⇒a = b
Trong tập hợp P(X) các phân tập của tập hợp X quan hệ bao hàm A⊂ B có tính phản xạ, phản đối xứng và bắc cầu mà không có tính đối xứng.
Trong tập hợp mọi đa thức của một biến số thực, quan hệ bằng nhau có tính phản xạ, đối xứng và bắc cầu.
Quan hệ ℜ trong tập X gọi là quan hệ tương đương nếu nó có tính phản xạ, đối xứng, bắc cầu.
Trong trường hợp này, ta viết a ~ b thay vì a ℜb
Quan hệ song song giữa các đường thẳng trong không gian, trong đó coi hai đường thẳng trùng nhau là song song, là một ví dụ điển hình về quan hệ tương đương Tương tự, quan hệ đồng dạng giữa các tam giác cũng thể hiện tính chất này Bên cạnh đó, quan hệ cùng tỉnh giữa một tập hợp dân cư trong một thành phố cũng là một ví dụ minh họa cho khái niệm quan hệ tương đương.
Giả sử ~ là một quan hệ tương đương trong tập X Đối với mỗi phần tử a thuộc X, ta định nghĩa C(a) là tập hợp tất cả các phần tử trong X tương đương với a, và gọi C(a) là lớp tương đương chứa a.
Do tính phản xạ a ≈ a nên mỗi tập con C(a) không rỗng Hơn nữa nếu C(a)∩C(b)≠ỉ thỡ c(a) = c(b).
Thật vậy, giả sử c∈C(a)∩C(b), thì ta có : c∈C(a) và c∈C(b) Tức là c ~ a và c ~ b, hay b ~ c ~ a Từ đó do tính chất bắc cầu, suy ra b ~ a, vậy b∈C(a).
Lập luận tương tự ta cũng có a∈C(b), tức là C(a) = C(b).
Từ đó rút ra được định lý :
Một quan hệ tương đương trong X xác định một phân hoạch của X, mỗi phần tử của phân hoạch này là một lớp tương đương.
Họ các lớp tương đương này được gọi là tập thương, ký hiệu X/~.
Ví dụ 1.4: Trong tập các số nguyên Z.
⇒(a – c) = (a – b) + (b – c) = 2(p + q) bắc cầu Vậy ℜ là một quan hệ tương đương.
- Lớp tương đương ứng với b = 0 là các số chẳn.
- Lớp tương đương ứng với b = 1 là các số lẻ.
1.4 Quan hệ thứ tự Định nghĩa 1.1:Quan hệ ℜ trong X gọi là quan hệ thứ tự (hay quan hệ bộ phận) nếu có tính phản đối xứng và bắc cầu.
Nếu ngoài ra với bất kỳ hai phần tử nào x∈X, y∈Y đều có x ℜy hoặc y ℜx thì ℜgọi là quan hệ thứ tự toàn phần (hay thứ tự tuyến tính).
Khi ℜ là một quan hệ thứ tự trong tập hợp X, ta nói rằng X được xếp thứ tự bởi ℜ Thay vì viết x ℜ y, ta sử dụng ký hiệu x ≤ y để diễn đạt “x bé hơn y” hoặc “x đi trước y” Tương tự, ta có thể viết y ≥ x để diễn tả “y lớn hơn x” hoặc “y đi sau x”.
Nếu x≤ y và x≠ y ta viết x < y (hay y > x).
Quan hệ < hoặc≤ thông thường trong tập hợp các số thực là quan hệ thứ tự toàn phần, R là tập được sắp thứ tự.
Quan hệ bao hàm⊂ trong tập P(X) mọi tập con của tập X là quan hệ thứ tự bộ phận Tuy nhiên nó không là thứ tự toàn phần.
Quan hệ "a⋮ b" cho thấy a là bội số của b trong tập N*, và đây được xem là một quan hệ thứ tự bộ phận Tập X, với quan hệ thứ tự đã được xác định, được gọi là tập được sắp xếp.
-Trình bày chính xác về quy nạp toán học và đệ quy;
-Kiểm tra tính đúng của một chương trình cụ thể;
-Áp dụng được giải thuật quy nạp và đệ quy.
Quy nạp toán học là một phương pháp chứng minh các định lý dạng P(n) đúng với mọi n nguyên dương, trong đó P(n) là một hàm mệnh đề Kỹ thuật này thường được áp dụng để xác nhận tính đúng đắn của các mệnh đề ∀P(n) cho mọi n là số nguyên dương.
Qua trình chứng minh P(n) là đúng với mọi số nguyên dương n bao gồm hai bước :
Bước cơ sở : Chỉ ra mệnh đề P(1) là đúng.
Bước quy nạp : chứng minh phép kéo theo P(n)" P(n + 1) là đúng với mọi số nguyên dương n, trong khi đó người ta gọi P(n) là giả thiết quy nạp.
Khi hoàn thành cả hai bước chúng ta đã chứng minh P(n) là đúng với mọi n nguyên dương, tức là đã chứng minh P(n) là đúng.
Ví dụ 2.1: Bằng quy nạp toán học hãy chứng minh rằng tổng n số nguyên dương lẻ đầu tiên là n 2
Để chứng minh mệnh đề P(n) "tổng n số nguyên dương lẻ đầu tiên là n^2", trước tiên cần xác minh bước cơ sở bằng cách chứng minh P(1) là đúng Tiếp theo, thực hiện bước quy nạp bằng cách chỉ ra rằng nếu P(n) đúng thì P(n + 1) cũng đúng.
Bước cơ sở : P(1) hiển nhiên là đúng vì 1 = 1 2
Bước quy nạp : Giả sử P(n) đúng, tức là với mọi n nguyên dương lẻ ta có :
Ta phải chỉ ra P(n+1) là đúng, tức là :
Do giả thuyết quy nạp ta suy ra :
= n 2 +(2n+1) = (n+1) 2 Đẳng thức này chứng tỏ P(n+1) được suy ra từ P(n).
Theo nguyên lý quy nạp toán học, nếu P(1) đúng và P(n) kéo theo P(n + 1) đúng với mọi n nguyên dương, thì P(n) sẽ đúng với mọi n nguyên dương.
2.2.Định nghĩa bằng đệ quy Đôi khi chúng ta rất khó định nghĩa một đối tượng một cách tường minh, nhưng có thể dễ dàng địng nghĩa đối tượng này qua chính nó.Kỹ thuật này được gọi là đệ quy. a Các hàm được định nghĩa bằng đệ quy Để định nghĩa một hàm xác định trên tập các số nguyên không âm, chúng ta cho:
• Giá trị của hàm tại n = 0.
Giá trị của một hàm tại số nguyên n có thể được tính dựa trên các giá trị của nó tại những số nguyên nhỏ hơn, và cách định nghĩa này được gọi là định nghĩa đệ quy hoặc định nghĩa quy nạp.
Ví dụ 2.2: Giả sử f được định nghĩa bằng đệ quy như sau : f(0) = 3, f(n+1) = 2f(n)+3 Hãy tìm f(1), f(2), f(3) và f(4).
Từ định nghĩa đệ quy, ta có thể tính giá trị của hàm f như sau: f(1) = 2f(0) + 3 = 9, f(1) = 2f(1) + 3 = 21, f(1) = 2f(2) + 3 = 45, và f(1) = 2f(3) + 3 = 93 Trong một số định nghĩa hàm đệ quy, giá trị của hàm được xác định tại k số nguyên dương đầu tiên, và quy tắc tính giá trị cho các số nguyên dương lớn hơn được xây dựng từ k giá trị này Theo nguyên lý thứ hai của quy nạp toán học, cách định nghĩa này đảm bảo rằng các hàm được xác định hoàn toàn.
Các tập hợp thường được định nghĩa theo phương pháp đệ quy, bắt đầu bằng một tập xuất phát và sau đó áp dụng quy tắc để tạo ra các phần tử mới từ những phần tử đã biết Những tập hợp được định nghĩa theo cách này được gọi là các tập hợp định nghĩa tốt, và các định lý liên quan đến chúng có thể được chứng minh dựa trên định nghĩa đệ quy.
Ví dụ 2.3: Giã sử S được định nghĩa bằng đệ quy như sau :
Hãy chỉ ra rằng S là tập các số nguyên chia hết cho 3.
Gọi A là tập hợp các số nguyên dương chia hết cho 3 Để chứng minh A = S, trước tiên, ta cần chỉ ra rằng A là tập con của S Giả sử P(n) là mệnh đề “3n thuộc tập S” Khi n = 1, P(1) đúng vì theo định nghĩa của S, ta có 3.1 = 3 ∈ S.
![Hình 2.1: Tích A=[a ik ] mq và B=[b kj ] qn - Giáo trình Cơ sở toán cho tin học (Nghề: Lập trình viên máy tính - Cao đẳng) - Trường CĐ Nghề Kỹ thuật Công nghệ](https://media.store123doc.com/figures/006/164/hinh-tich-a-ik-mq-b-kj-qn-6164783.webp)
