Chào mừng quý vị đến với Trang riêng Phạm Phương Lan....

Quý vị chưa đăng nhập hoặc chưa đăng ký làm thành viên, vì vậy chưa thể tải được các tư liệu của Thư viện về máy tính của mình.
Nếu đã đăng ký rồi, quý vị có thể đăng nhập ở ngay ô bên phải.

Chương 1_Quan hệ và suy luận

(Tài liệu chưa được thẩm định)
Nguồn:
Người gửi: Phạm Thị Phương Lan (trang riêng)
Ngày gửi: 21h:55' 16-02-2012
Dung lượng: 1.3 MB
Số lượt tải: 74
Số lượt thích: 0 người
BÀI GIẢNG
1. Quan hệ hai ngôi
1.1. Khái niệm về quan hệ hai ngôi
Cho tập X khác rỗng và một tính chất được thỏa mãn với một cặp phần tử a, b nào đó của X. Ta nói a có quan hệ với b và viết
Lúc đó được gọi là một quan hệ hai ngôi trong X.
Ví dụ:
Trong tập số thực R, quan hệ “a=b” là một quan hệ 2 ngôi.
Trong tập N, quan hệ “a là ước của b” là một quan hệ 2 ngôi.
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.

Chương 1:QUAN HỆ-SUY LUẬN TOÁN HỌC
1.2. Các tính chất của quan hệ 2 ngôi:

Tính phản xạ:

Tính đối xứng:

Tính phản đối xứng:

Tính bắc cầu:

Chương 1:QUAN HỆ-SUY LUẬN TOÁN HỌC

Ví dụ 1: Cho A={1,2,3,4,5},và quan hệ R trên A:
R={(1,1),(2,2),(2,3),(3,3),(3,4), (3,5),(4,2) ,(4,4), (5,1), (5,5)}R có tính phản xạ.
Ví dụ 2: Cho A = {1,2,3,4} và quan hệ R trên A:
R2= {(1,1),(2,1), (3,1), (3,2), (4,4), {3,3)}.Ta thấy 2A như (2,2)R2 nên R2 không có tính phản xạ.
Ví dụ 3: A={1,2,3}, xét quan hệ trên A
R3 = {(1,1), (3,2), (1,3), (3,1), (2,3)} là quan hệ đối xứng
R4 = {(2,1), (1,2), (3,2), (1,3), (3,1), (3,3)} là quan hệ không đối xứng
Ví dụ 4: Quan hệ “” trên tập số thực R, có tính phản xứng.
Vì: x,yR, (xy ) (y x)  x= y
Ví dụ 5:Các quan hệ “=“, “” trên R là các quan hệ có tính bắt cầu
Quan hệ ”” trên R không có tính bắt cầu
1.3. Quan hệ tương đương:
Định nghĩa: Quan hệ được gọi là tương đương nếu nó có tính chất phản xạ, đối xứng và bắc cầu.
Trong trường hợp này ta viết thay vì .
Ví dụ: Quan hệ song song giữa các đường thẳng trong tập mọi đường thẳng của không gian(coi hai đường thẳng trùng nhau là song song với nhau); quan hệ đồng dạng giữa các tam giác; quan hệ cùng tỉnh của một tập hợp dân một thành phố là các ví dụ trực quan về quan hệ tương đương.
Lớp tương đương: Trong một quan hệ tương đương, tập tất cả các phần tử có quan hệ với a được gọi là lớp tương đương của a. Ký hiệu :


Ví dụ : Trên z định nghĩa quan hệ R: a,b z, aRb  “a cùng tính chẵn lẻ với b”, R: là quan hệ tương đương
Lớp tương đương chứa 2 là: [2]={Các số chẵn}
={…-4, -2, 0, 2, 4,…}
Lớp tương đương chứa 1 là: [1] ={Các số lẻ}
= {…-5, -3, -1, 1, 3,5,…}
Phân hoạch: Cho tập hợp S và A1, A2, …, An là các tập con của S thỏa các tính chất:
Ai  i{1,2,…,n}
AiAj =  i,j {1,2,…,n}, ij
A1A2…An = S
Thì A1, A2, …, An: gọi là một phân hoạch của S
Ví dụ 1: Một phân hoạch của S thành 7 tập con
Ví dụ 2: Cho S={0,1,2,3,4,5,6,7} và A={1,3,5,7}, B={2,4,6}, C={0}.
Ta có: A, B và C
AB=; AC= ; BC=
ABC=S
Vậy A, B, C là một phân hoạch của S
1.4. Quan hệ thứ tự:
Định nghĩa: Quan hệ được gọi là thứ tự nếu nó có tính chất phản xạ, phản đối xứng và bắc cầu
Ví dụ: Cho tập A={a1,a2, a3, a4, a5, a6, a7}, Xét quan hệ: R={(a1, a1), (a2,a2), (a3,a3), (a4,a4), (a5,a5),(a6,a6),(a7,a7), (a1,a3), (a3, a5),(a1,a5), (a5,a7), (a3,a7), (a1,a7)}. R có phải là một quan hệ thứ tự trên A?
Giải: Ta thấy:aA, aRa. nên R phản xạ
a,bA, aRb  a=b nên R phản xứng
a,b,cA, aRb  bRc  aRc nên R bắt cầu
Vậy R là một quan hệ thứ tự trên A
2. Suy luận toán học
2.1. Quy nạp toán học
Nhiều định lý phát biểu rằng P(n) là đúng với mọi n nguyên dương, trong đó P(n) là một hàm mệnh đề. . Qui nạp toán học là một kĩ thuật chứng minh các định lý thuộc thể loại như thế. Nói cách khác qui nạp toán học thường được sử dụng để chứng minh các mệnh đề dạng n P(n), trong đó n là số nguyên dương tùy ý.
Quá trình chứng minh quy nạp bao gồm 2 bước:
Bước cơ sở: Chỉ ra P(1) đúng.
Bước quy nạp: Chứng minh nếu P(n) đúng thì P(n+1) đúng. Trong đó P(n) được gọi là giả thiết quy nạp.

Gọi P(n) là mệnh đề “tổng n số nguyên dương lẻ đầu tiên là n2”.
Bước cơ sở: P(1): “tổng 1 số nguyên dương lẻ đầu tiên là 12”.Hiển nhiên P(1) đúng vì 1= 12.
Bước quy nạp:
- Giả sử P(n) đúng, tức là
- Ta phải chỉ ra rằng P(n+1) đúng, tức là

Từ giả thiết quy nạp ta có:


- Suy ra, P(n+1) đúng.
Vậy theo nguyên lý quy nạp P(n) đúng với mọi số nguyên dương n
Ví dụ 1: Bằng quy nạp hãy chứng minh rằng tổng n số nguyên dương lẻ đầu tiên là n2.

Bài tập tại lớp:
1. Chứng minh với mọi


2. Chứng minh với mọi


2.2. Định nghĩa bằng đệ quy
Các hàm được định nghĩa bằng đệ quy
Giá trị của hàm tại n=0
Công thức tính giá trị của nó tại số nguyên n từ các giá trị của nó tại các số nguyên nhỏ hơn.
Ví dụ: Cho hàm f xác định như sau:

Tìm các giá trị
------------------










Các tập hợp được định nghĩa bằng đệ quy
Đưa ra tập xuất phát
Quy tắc tạo các phần tử mới từ các phần tử đã biết
Ví dụ: Tập S được định nghĩa như sau:


Ta chỉ ra rằng S là tập các số nguyên dương chia hết cho 3.
---------------------



Giải:
Gọi A là tập các số nguyên dương chia hết cho 3. Để chứng minh A = S ta sẽ chứng minh A là một tập con của S và S là tập con của A.
Để chứng minh A là tập con của S, giả sử P(n) là mệnh đề “3n thuộc tập S”. P(1) đúng vì theo định nghĩa của S “3.1=3ЄS”
3+ 3n = 3(n + 1) Є S. Điều này có nghĩa P(n+1 ) đúng. Theo qui nạp toán học mọi số có dạng 3n, với n nguyên dương, thuộc S, hay nói cánh khác A là tập con của S.
Giả sử P(n) đúng, tức là 3nЄS. Vì 3ЄS và 3nЄS nên theo định nghĩa:
Ngược lại 3ЄS, hiển nhiên 3 chia hết cho 3 nên 3ЄA.

Tiếp theo ta chứng minh tất cả các phần tử của S sinh ra do phần tử thứ hai của định nghĩa, cũng thuộc A.

Giả sử x, y là hai phần tử của S, cũng là hai phần tử của A. Theo định nghĩa của S thì x+ y cũng là một phần tử của S, vì x và y đều chia hết cho 3 nên x+ y cũng chia hết cho 3, tức là : x+ y Є A. Vậy S là tập con của A.
2.3. Các thuật toán đệ quy:

Định nghĩa: Một thuật toán được gọi là đệ quy nếu nó giải bài toán bằng cách rút gọn liên tiếp bài toán ban đầu tới bài toán tương tự nhưng với đầu vào nhỏ hơn.

Ví dụ 1: Tìm thuật toán đệ quy tính giá trị an và a là số thực khác không và n là số nguyên không âm.
an+1=an.a
Giải:
Ta xây dựng thuật toán đệ quy nhờ định nghĩa đệ quy của an, đó là an+1 = a.an với n>0 và khi n = 0 thì a0 = 1. Vậy để tính an ta qui về các trường hợp số mũ n nhỏ hơn, cho đến khi n = 0. Xem thuật toán 1 sau đây:
THUẬT TOÁN 1: THUẬT TOÁN ĐỆ QUY TÍNH an

Ham luy thua (aЄR và a≠0, nЄN và n≠0)
if n = 0 then luythua(a,n) := 1
else luythua(a,n) := a*luythua(a,n-1)
Ví dụ 2: Thuật toán đệ quy tính n! với n là số nguyên dương

Ham giaithua (n: nguyên dương)
if n = 1 then giaithua(n) := 1
else giaithua(n) :=n*giaithua(n-1)
THUẬT TOÁN 2: THỦ TỤC ĐỆ QUY TÍNH GIAI THỪA
THUẬT TOÁN 3: THỦ TỤC LẶP TÍNH GIAI THỪA
Ham lapgiaithua(n; nguyenduong);
x:=1;
for i:= 1 to n
x:= i*x
{x là n!}
2.4. Tính đúng đắn của chương trình
Mở đầu: Giả sử rằng chúng ta đã thiết kế được một thuật toán để giải một bài toán nào đó và đã viết chương trình để thể hiện nó. Liệu ta có thể tin chắc rằng chương trình có luôn luôn cho lời giải đúng hay không?
Sau khi tất cả các sai sót về mặt cú pháp được loại bỏ, chúng ta có thể thử chương trình với các đầu vào mẫu. Tuy nhiên, ngay cả khi chương trình cho kết quả đúng với tất cả cá đầu vào mẫu, nó vẫn có thể không luôn luôn tạo ra các câu trả lời đúng( trừ khi các đầu vào có thể đã thử). Chúng ta cần chứng minh rằng chương trình luôn luôn cho đầu ra đúng.
Kiểm tra chương trình: Một chương trình gọi là đúng đắn nếu mọi đầu vào khả dĩ, nó cho đầu ra đúng. Việc chứng minh tính đúng đắn của chương trình gồm hai phần. Phần đầu chỉ ra rằng nếu chương trình kết thúc thì nhận được kết quả đúng. Phần này xác minh tính đúng đắn bộ phận của chương trình. Phần thứ hai chứng tỏ chương trình luôn luôn là kết thúc.
Để định rõ thế nào là một chương trình cho thông tin ra đúng, người ta thường dùng hai mệnh đề sau:
- Thứ nhất là khẳng định đầu, nó đưa ra những tính chất mà thông tin đầu vào cần có.
- Mệnh đề thứ hai là khẳng định cuối,nó đưa ra những tính chất mà thông tin đầu ra cần phải có, tùy theo mục đích của chương trình. Khi kiểm tra chương trình cần phải chuẩn bị các khẳng định đầu và khẳng định cuối thích hợp.
Định nghĩa: Chương trình hay đoạn chương trình S được gọi là đúng dắn bộ phận đối với khẳng định đầu vào p và khẳng định đầu cuối q, nếu p là đúng với các giá trị vào của S và nếu S kết thúc thì q là đúng với các giá trị ra của S. Ký hiệu p{S}q có nghĩa là chương trình hay đoạn chương trình S là đúng đắn bộ phận đối với khẳng định đầu p và khẳng định cuối q.
Chú ý: Khái niệm đúng đắn bộ phận không đề cập đến việc chương trình có kết thúc hay không. Nó chỉ nhằm kiểm tra xem chương trình có làm được cái mà nó định làm hay không, nếu nó kết thúc.
Câu lệnh điều kiện:
Trước tiên, chúng ta sẽ trình bày những quy tắc suy luận đối với câu lệnh điều kiện. Giả sử một đoạn chương trình có dạng:
If điều_kiện then
S
trong đó S là một khối lệnh. Khối S sẽ được thi hành nếu điều kiện là đúng và S không được thi hành nếu điều kiện là sai.
Tương tự, giả sử một đoạn chương trình có dạng:
If điều_kiện then
S1
else
S2
Nếu điều kiện là đúng thì S1 được thi hành, nếu điều kiện là sai thì S2 được thi hành.

* Bất biến vòng lặp:
Tiếp theo chúng ta sẽ trình bày cách chứng minh tính đúng đắn của vòng lặp while. Để xây dựng quy tắc suy luận cho đoạn chương trình dạng:

While điều_kiện
S

Hãy lưu ý rằng S được lặp đi lặp lại cho tới khi nào điều kiện trở nên sai. Ta gọi một điều khẳng định nào đó là bất biến vòng lặp nếu nó vẫn còn đúng sau mỗi lần S thi hành.
BÀI TẬP
1. Dùng phương pháp quy nạp để chứng minh điều sau:



2. Tìm
nếu ta cho f(0)=1 và hàm f được định nghĩa đệ quy như sau:

BÀI TẬP
3. Trong các quan hệ xây dựng trên tập X= {0,1,2,3} dưới đây,quan hệ nào là quan hệ tương đương?
Kết thúc chương 1_Hẹn gặp laị các em ở chương 2!
 
Gửi ý kiến

↓ CHÚ Ý: Bài giảng này được nén lại dưới dạng RAR và có thể chứa nhiều file. Hệ thống chỉ hiển thị 1 file trong số đó, đề nghị các thầy cô KIỂM TRA KỸ TRƯỚC KHI NHẬN XÉT  ↓

print