TAILIEUCHUNG - Bài giảng Cấu trúc rời rạc cho Khoa học máy tính: Chapter 3 – ĐH Bách Khoa
Chương này bao gồm các bài tập tóm tắt về vấn đề sử dụng, biểu diễn tri thức và suy diễn, trước khi đi sâu trình bày về biểu diễn tri thức và suy diễn với logic. . | ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA KHOA HỌC - KỸ THUẬT MÁY TÍNH CẤU TRÚC RỜI RẠC CHO KHMT (CO1007) Nhóm:18-TDTT —- Homework CHAPTER 2 Proving Methods GVHD: SV thực hiện: Nguyễn An Khương Đinh Minh Tân – 1613074 Trương Minh Tiến – 1613544 Vũ Đào Anh Tuấn – 1613938 Nguyễn Thị Trà My – 51305086 Tp. Hồ Chí Minh, Tháng 11/2016 Trường Đại Học Bách Khoa Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính Chứng minh bất đẳng thức Cauchy bằng qui nạp Với n=2k ,k=1,2,. Gọi P(k) là mệnh đề A≥G, trong đó A,G là trung bình cộng và trung bình nhân của tập hợp n=2k số thực dương. Bước cơ sở: k=1 và n=21 =2. √ √ √ Ta có ( a1 − a2 )2 ≥0 hay khai triển biểu thức đó ra ta được a1 − 2 a1 a2 + a2 ≥0, tức là √ (a1 + a2 )/2≥ a1 a2 . Bước qui nạp Giả sử P(k) là đúng, với n=2k . Ta sẽ chứng minh rằng P(k+1) là đúng . Ta có: 2k+1 = 2n và (a1 + a2 + . + a2n )/(2n) = [(a1 + a2 + . + an )/n + (an+1 + + a2n )/n]/2 đồng thời (a1 a2 .a2n )1/(2n) = [(a1 .an )1/n (an+1 .a2n )1/n ]1/2 . Để đơn giản kí hiệu, gọi A(x,y.) và G(x,y.) lần lượt là trung bình cộng và trung bình nhân của các số x, x≤x’,y≤y’thì A(x,y.)≤A(x’,y’.) và G(x,y.)≤G(x’,y’.).Vì thế A(a1 , ., a2n ) = A(A(a1 , , an ), A(an+1 ., a2n ))≥A(G(a1 , ., an ), G(an+1 , ., a2n ))≥G(G(a1 , ., an ), G(an+1 , , a2n )) = G(a1 , ., a2n ). Điều này kết thúc chứng minh cho trường hợp n là lũy thừa của 2 .Nếu n không là lũy thừa của 2 ,gọi m là lũy thừa bậc 2 với bậc cao hơn liền sát và an+1 , ., am tất cả đều bằng A(a1 , ., an ) = a. Khi đó, ta có ((a1 a2 .an )(a)m−n )1/m ≤A(a1 , a2 , ., am ) vì m là lũy thừa của 2. Vì A(a1 , a2 , .am ) = a, suy ra (a1 a2 .an )1/m (a)1−n/m ≤(a)n/m . Nâng cả 2 vế lên lũy thừa bậc m/n ta được G(a1 , ., an )≤A(a1 .an ). Bất đẳng thức được chứng minh. Exercise 3. a) TRUE b) TRUE c) FALSE Exercise 4. a) TRUE b) TRUE c) FALSE d) TRUE e) FALSE f) TRUE g) FALSE Chương 2: Homework Trang 1/8 Trường Đại Học .
đang nạp các trang xem trước
