Đăng ký Đăng nhập
Trang chủ Giáo dục - Đào tạo Cao đẳng - Đại học Cơ sở groebner và chứng minh định lý hình học bằng máy tính....

Tài liệu Cơ sở groebner và chứng minh định lý hình học bằng máy tính.

.PDF
61
120
75

Mô tả:

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC BÙI ĐỨC THẮNG CƠ SỞ GROEBNER VÀ CHỨNG MINH ĐỊNH LÝ HÌNH HỌC BẰNG MÁY TÍNH LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2015 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC BÙI ĐỨC THẮNG CƠ SỞ GROEBNER VÀ CHỨNG MINH ĐỊNH LÝ HÌNH HỌC BẰNG MÁY TÍNH Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60.46.01.13 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: TS. Nguyễn Danh Nam THÁI NGUYÊN - 2015 Công trình được hoàn thành tại Trường Đại học Khoa học – Đại học Thái Nguyên Người hướng dẫn khoa học: TS. Nguyễn Danh Nam Phản biện 1: PGS.TS. Nguyễn Việt Hải Phản biện 2: PGS.TS. Trịnh Thanh Hải Luận văn sẽ được bảo vệ trước hội đồng chấm luận văn họp tại: Trường Đại học Khoa học – Đại học Thái Nguyên Ngày 31 tháng 5 năm 2015 Có thể tìm hiểu tại: Thư viện Trường Đại học Khoa học và Trung tâm Học liệu - Đại học Thái Nguyên 0 MỤC LỤC Trang MỤC LỤC .................................................................................................................. 1 MỞ ĐẦU .................................................................................................................... 2 CHƯƠNG 1: CƠ SỞ GROEBNER ......................................................................... 4 1.1. Thứ tự từ .............................................................................................................. 5 1.2. Iđêan khởi đầu và cơ sở Groebner . ..................................................................... 6 1.3. Định lý Hilbert về không điểm . ........................................................................ 10 CHƯƠNG 2: PHẦN MỀM MAPLE VÀ GÓI LỆNH GEOPROVER .............. 12 2.1. Phần mềm Maple ............................................................................................... 12 2.2. Gói câu lệnh GeoProver . ................................................................................... 13 CHƯƠNG 3: CHỨNG MINH ĐỊNH LÝ HÌNH HỌC BẰNG MÁY TÍNH ..... 16 3.1. Đại số hóa giả thiết và kết luận của định lý ....................................................... 16 3.2. Quy trình chứng minh định lý hình học bằng máy tính ..................................... 20 3.3. Chứng minh một số định lý hình học ................................................................. 25 KẾT LUẬN .............................................................................................................. 56 TÀI LIỆU THAM KHẢO ...................................................................................... 57 1 MỞ ĐẦU Với sự phát triển nhanh chóng của công nghệ thông tin và truyền thông, các phương tiện - thiết bị dạy học hiện đại đã và đang được sử dụng một cách có hiệu quả trong giáo dục. Phần mềm dạy học là một trong những phương tiện dạy học hỗ trợ giáo viên thực hiện được phần nào các ý tưởng sư phạm của mình. Maple là một phần mềm toán học tạo ra một cách tiếp cận mới sinh động và sáng tạo. Ngoài các câu lệnh có chức năng kiểm tra, tính toán, minh hoạ hình ảnh,…nó còn cho phép các giáo viên có thể sử dụng ngôn ngữ lập trình của Maple để tạo các công cụ mới, các gói câu lệnh mới. Vì thế, Maple có khả năng đầy đủ để giảng dạy và học tập từ bậc phổ thông (các gói chức năng về đại số, số học, giải tích, hình học,…) lên đại học (đại số tuyến tính, phương trình vi phân, hình học cao cấp, đại số hiện đại,…). Xuất phát từ ý tưởng rằng có rất nhiều định lý hình học hoàn toàn được mô tả bằng các khái niệm đại số bằng cách biểu diễn các hình hình học trong toạ độ Đề-các vuông góc. Khi đó, hầu hết các hình hình học và biên của nó có thể xem là tập không điểm của các đa thức, và các quan hệ giữa chúng đều có thể mô tả bằng các phương trình đa thức cũng như tập không điểm phải xét trên trường số thực. Như vậy, để kiểm tra tính đúng - sai của một giả thuyết hay một định lý hình học nào đó hoàn toàn có thể thực hiện được nhờ những kết quả quan trọng liên quan đến khái niệm cơ sở Groebner được nhà toán học Bruno Buchberger đưa ra năm 1965 trong luận án phó tiến sĩ của mình. Tính toán hình thức hay còn gọi là Đại số máy tính, xuất hiện khoảng ba chục năm nay và gần đây trở thành một chuyên ngành độc lập. Đây là một chuyên ngành kết hợp chặt chẽ toán học và khoa học máy tính. Nó được ra đời dưới ảnh hưởng của sự phát triển và phổ cập máy tính cá nhân. Một mặt, sự phát triển này đòi hỏi phải xây dựng các lý thuyết toán học làm cơ sở cho việc thiết lập thuật toán và các phần mềm toán học. Mặt khác, khả năng tính toán mỗi ngày một tăng của máy tính giúp triển khai tính toán thực sự nhiều thuật toán. Sự phát triển của Đại số máy tính cũng có tác dụng tích cực trở lại trong nghiên cứu toán học lý thuyết. 2 Nhiều kết quả lý thuyết đã được phán đoán hoặc có được phản ví dụ nhờ sử dụng máy tính. Hầu hết những vấn đề mà lý thuyết cơ sở Groebner cho lời giải bằng thuật toán đã được biết trước đó, đó là tính giải được. Tuy nhiên giữa việc chứng minh tính giải được và thực hiện tính toán trên thực tế là khoảng cách lớn. Hơn nữa, nhiều đối tượng trong các ngành khá trừu tượng như Đại số giao hoán và Hình học đại số có thể tính toán thông qua cơ sở Groebner chứng tỏ có một tầm quan trọng của lý thuyết này. Mục đích của luận văn là giới thiệu thuật toán tính cơ sở Groebner cho các Iđêan đa thức, để trình bày một số ứng dụng của lý thuyết cơ sở Groebner trong tính toán hình thức bằng máy tính là Đại số giao hoán và Hình học đại số. Hiện nay, có nhiều phần mềm xử lý toán học như Maple, Macaulay, CoCoA ... để phục vụ cho việc tính toán. Nhưng luận văn này chọn phần mềm Maple để trình bày cách đại số hóa bài toán hình học và chứng minh định lý hình học bằng máy tính. Tuy nhiên, nếu chỉ đơn thuần sử dụng gói công cụ Groebner của Maple thì giáo viên nhiều khi khó thực hiện được kịch bản sư phạm của mình. Giải pháp cho vấn đề này là giáo viên sử dụng ngôn ngữ lập trình của Maple để xây dựng các gói công cụ phù hợp. Do đó, chúng tôi đã xây dựng gói GeoProver để hỗ trợ chứng minh một số định lý hình học sơ cấp. 3 Chương 1 CƠ SỞ GROEBNER Khái niệm cơ sở Groebner ra đời trong những năm 1970 để giải quyết bài toán chia đa thức. Sau hơn 20 năm khái niệm này đã có những ứng dụng to lớn trong nhiều chuyên ngành toán học khác nhau từ Đại số đến Hình học, Tô pô, Tổ hợp và Tối ưu [9]. Việc sử dụng các hệ đa thức giống như cơ sở Groebner đã xuất hiện từ đầu thế kỉ này với các công trình của Gordan, Macaulay, Hilbert. Người đầu tiên thấy được tầm quan trọng của thuật toán chia là nhà toán học người Áo Broebner. Ông đã đặt vấn đề tính cơ sở Groebner làm một đề tài luận án phó tiến sĩ cho học trò của ông là Buchberger. Năm 1970, Buchberger tìm thấy một thuật toán hữu hiệu để tính cơ sở Groebner. Sau này người ta mới phát hiện ra rằng Groebner đã biết những nét cơ bản của thuật toán này từ những năm 50. Cùng thời gian này cũng xuất hiện những kĩ thuật tương tự giống như thuật toán chia trong các công trình của Hironaka về giải kì dị, của Grauert trong Giải tích phức và của Cohn trong Lý thuyết vành không giao hoán [9]. Cơ sở Groebner được nghiên cứu đúng thời kì máy tính cá nhân ra đời và bắt đầu trở nên phổ cập. Ngay lập tức người ta thấy rằng có thể lập trình thuật toán chia để giải quyết các bài toán với các biến số mà ngày nay được gọi là tính toán hình thức (symbol computation). Bản thân thuật toán chia đã chứa đựng những thuận lợi cơ bản cho việc lập trình như: (1) Việc sắp xếp thứ tự các hạng tử của một đa thức cho phép ta biểu diễn một đa thức như một véc-tơ các hệ số và do đó ta có thể đưa dữ liệu về các đa thức vào trong máy tính một cách dễ dàng. (2) Việc xét hạng tử lớn nhất của các đa thức cho phép máy tính chỉ cần thử tọa độ đầu tiên của các véc-tơ tương ứng. Về mặt lý thuyết khái niệm cơ sở Groebner cũng đưa ra những phương pháp và vấn đề nghiên cứu mới. Trước tiên, người ta thấy rằng nhiều khi chỉ cần xét tập hợp các hạng tử đầu của cơ sở Groebner là đủ để có các thông tin cần thiết về hệ đa 4 thức ban đầu. Có thể thay các hạng tử này bằng các đơn thức nên thực chất là ta phải xét một số hữu hạn các bộ số tự nhiên ứng với các số mũ của các biến trong đơn thức. Ta có thể coi các bộ số tự nhiên này như những điểm nguyên là các điểm có tọa độ là các số nguyên. Vì vậy, nhiều bài toán Hình học và Đại số có thể quy về việc xét các tính chất tổ hợp hay tô pô của một tập hợp hữu hạn các điểm nguyên. Sau đây luận văn trình bày một số kiến thức cơ bản về cơ sở Groebner trước khi đưa ra thuật toán để chứng minh định lý hình học. 1.1. THỨ TỰ TỪ 1.1.1. Định nghĩa Định nghĩa 1.1. Thứ tự từ  là một thứ tự toàn phần trên tập M tất cả các đơn thức của vành K[x] thoả mãn các tính chất sau: i) Với mọi m  M, 1  m. ii) Nếu m1, m2, m  M mà m1  m2 thì mm1  mm2. 1.1.2. Một số thứ tự từ Định nghĩa 1.2. Thứ tự từ điển là thứ tự lex xác định như sau: x11 ...xn n lex x11 ...xnn nếu thành phần đầu tiên khác không kể từ bên trái của véctơ 1  1,...,  n  n  là một số âm. Nói cách khác, nếu tồn tại 0  i  n sao cho 1  1,...,n  n , nhưng i1  i1 . Thứ tự từ điển tương tự như cách sắp xếp các từ trong từ điển, và do đó có tên gọi như vậy. Định nghĩa 1.3. Thứ tự từ điển phân bậc là thứ tự  glex xác định như sau: x11 ...xnn  glex x11 ...xnn nếu deg( x1 ...xn )  deg( x1 ...xn ) hoặc deg( x11 ...xnn )  deg( x11 ...xnn ) 1 n 1 n và thành phần đầu tiên khác không kể từ bên trái của véctơ 1  1,...,  n  n  là     một số âm. Nói cách khác, x1 1 ...xn n  glex x1 1 ...xn n nếu 1  ...   n  1  ...   n   hoặc 1  ...   n  1  ...   n và x11 ...xn n lex x11 ...xn n . Định nghĩa 1.4. Thứ tự từ điển ngược là thứ tự  rlex xác định như sau: x11 ...xn n rlex x11 ...xnn nếu deg( x11 ...xn n )  deg( x11 ...xnn ) hoặc deg( x11 ...xnn )  deg( x11 ...xnn ) 5 và thành phần đầu tiên khác không kể từ bên phải của véctơ 1  1,...,  n  n  là   một số dương. Nói cách khác, x11 ...xn n  rlex x11 ...xn n nếu 1  ...   n  1  ...   n hoặc 1  ...   n  1  ...   n và và tồn tại 1  i  n sao cho n  n ,...,i1  i1 nhưng  i   i . Thứ tự từ điển ngược được định nghĩa như theo sơ đồ của thứ tự từ điển phân bậc, chứ không phải của thứ tự từ điển - một điều tưởng chừng không tự nhiên. Thực ra việc so sánh bậc tổng thể trước trong trường hợp này là bắt buộc để đảm bảo đơn thức 1 là nhỏ nhất. Mệnh đề 1.1. Ba thứ tự kể trên là các thứ tự từ. 1.2. IĐÊAN KHỞI ĐẦU VÀ CƠ SỞ GROEBNER 1.2.1. Từ khởi đầu, đơn thức khởi đầu Định nghĩa 1.5. Cho  là một thứ tự từ và f  R  K  x1 ,..., xn  . Từ khởi đầu của f , kí hiệu là in  f  , là từ lớn nhất của đa thức f đối với thứ tự từ  . a Nếu in  f    x ,0    K , thì lc  f    được gọi là hệ số đầu và lm  f   xa là đơn thức đầu của f đối với thứ tự từ  . Nếu thứ tự từ  đã được ngầm hiểu, ta sẽ viết in  f  (tương ứng lc  f  , lm  f  ) thay cho in  f  (tương ứng lc  f  , lm  f  ). Từ khởi đầu của đa thức 0 được xem là không xác định (có thể nhận giá trị tuỳ ý). Từ khởi đầu còn gọi là từ đầu hay từ đầu tiên. Như vậy nếu trong biểu diễn chính tắc của đa thức f ta viết các từ theo thứ tự giảm dần, thì in  f  sẽ xuất hiện đầu tiên. Đương nhiên cách viết này cũng như từ khởi đầu của f phụ thuộc vào thứ tự từ đã chọn. 6 1.2.2. Iđêan khởi đầu và cơ sở Groebner Định nghĩa 1.6. Cho I là iđêan của R và  là một thứ tự từ, Iđêan khởi đầu của I, kí hiệu là in  I  , là iđêan của R sinh bởi các từ khởi đầu của các phần tử của I, nghĩa là:  in  I   in  f  f  I  Cũng như trên ta sẽ viết in  I  thay vì in  I  nếu  đã rõ. Rõ ràng cũng có   in  I   Im  f  f  I nên in  I  là iđêan đơn thức. Vấn đề đặt ra là làm thế nào để xác định được iđêan khởi đầu in  I  của một iđêan I cho trước. Cách tốt nhất là tìm một hệ sinh tối tiểu của nó. Tuy nhiên, mọi iđêan đơn thức đều có một tập sinh đơn thức và tập đó hữu hạn. Do đó ta có thể đưa vào khái niệm quan trọng sau đây: Định nghĩa 1.7. Cho  là một thứ tự từ và I là iđêan của R. Tập hữu hạn các đa thức khác không g1 ,..., g s  I được gọi là một cơ sở Groebner của I đối với thứ tự từ  , nếu: in  I    in  g1  ,..., in  g s   Tập g1 ,..., g s  I được gọi là một cơ sở Groebner, nếu nó là cơ sở Groebner của iđêan sinh bởi chính các phần tử này. Mệnh đề 1.2. Cho I là một iđêan tuỳ ý của R. Nếu g1 ,..., g s  I là cơ sở Groebner của I đối với một thứ tự từ nào đó, thì g1,..., g s là cơ sở của I. Định nghĩa 1.8. Cơ sở Groebner rút gọn của iđêan I đối với một thứ tự từ đã cho là một cơ sở Groebner G của I thoả mãn các tính chất sau: i) lc  g   1 với mọi g  G . ii) Với mọi g  G và mọi từ m của g không tồn tại g '  G \  g để in  g ' | m . Mệnh đề 1.3. Cho I  0 . Khi đó đối với mỗi thứ tự từ, I có duy nhất một cơ sở Groebner rút gọn. Mọi cơ sở Groebner rút gọn đều là cơ sở Groebner tối tiểu. 7 Định nghĩa 1.9. Cho I là iđêan của vành R. Tập hợp: I  r  R n  N : r n  I  lập thành một iđêan. Iđêan này được gọi là căn của I. Rõ ràng I  I . Nếu I  I thì I được gọi là một iđêan căn. 1.2.3. Một số tính chất của cơ sở Groebner Cơ sở Groebner có một số tính chất sau: (i) Cho I là một iđêan tuỳ ý của R. Nếu g1 ,..., g s là cơ sở Groebner của I đối với một thứ tự từ nào đó thì g1 ,..., g s là cơ sở của iđêan I. (ii) Cho  là một thứ tự từ. Khi đó mọi iđêan đều có cơ sở Groebner tối tiểu và mọi cơ sở Groebner tối tiểu của cùng một iđêan đều chung số lượng phần tử và chung tập từ khởi đầu. (iii) Cho I  0 . Khi đó đối với mỗi thứ tự từ, I có duy nhất một cơ sở Groebner rút gọn. (iv) Cho trước s là một số nguyên dương. Khi đó tồn tại iđêan I sinh tối tiểu bởi f1 ,..., f s nhưng in( I ) thực sự chứa (in( f1 ),..., in( f s )) . Định lý 1.1. Cho G  I là một cơ sở hữu hạn của iđêan I. Khi đó, G là cơ sở Groebner của I nếu và chỉ nếu với mọi f  I , in( f ) chia hết cho in( g ) với g  G nào đó. Chứng minh. G là cơ sở Groebner của I  in( I )  (in( g1 ),...,in( gs )) . (với G   g1 ,..., g s  ). Cần chứng minh in( I )  (in( g1 ),..., in( gs )) khi và chỉ khi với mọi f  I , in( f ) chia hết cho in( g ) với g  I nào đó. s Thuận: Với mọi f  I , do I  ( g1 ,..., g s ) nên f   f i g i . i 1 Ta có in( f )  in( I )  in( f )  (in( g1 ),..., in( gs ))  in( f ) chia hết cho in( g k ) với 1  k  s . 8 Nghịch: Rõ ràng (in( g1 ),..., in( gs ))  in( I ) . Với f  I , hay in( f )  in( I ) thì in( f ) chia hết cho in( g ) với g  I nào đó  in( f )  (in( g1 ),..., in( gs ))  in( I )  (in( g1 ),..., in( gs ))  in( I )  (in( g1 ),..., in( gs )) . Định lý 1.2. Với mỗi đa thức f  R  K [x] , kí hiệu M(f) là tập tất cả các đơn thức của f. Cho  là một thứ tự từ trên M. Với f , g  R ta định nghĩa f * g  M ( f )  ' M ( g ) , nghĩa là: - Nếu M ( f )  M ( g ) thì f * g và g * f . - Nếu M ( f )  M ( g ) thì f * g . - Nếu M ( f )  M ( g ) , sắp xếp các đơn thức của M ( f ) và M ( g ) theo thứ tự giảm dần. Tại cặp đơn thức khác nhau đầu tiên kể từ bên trái, đa thức nào có đơn thức bé hơn thì bé hơn. Khi đó * là giả thứ tự tốt trên R và là mở rộng của giả thứ tự trên tập các từ của R. Chứng minh. Vì  là thứ tự từ nên nó là thứ tự tốt. Kiểm tra được * giả thứ tự toàn phần. Cần chứng minh nó là giả thứ tự tốt. Giả sử nó không là giả thứ tự tốt suy ra tồn tại tập A   gồm các đa thức trên R và A không có phần tử nhỏ nhất theo giả thứ tự *. Trên A: Gọi A1 là tập các đa thức có cùng đơn thức đầu bé nhất (điều này là tồn tại do  là thứ tự tốt trên M). Trên A1: Gọi A2 là tập các đa thức có cùng đơn thức thứ hai bé nhất (đa thức được viết theo thứ tự giảm dần các đơn thức). … Trên An: Gọi An+1 là tập các đa thức có cùng đơn thức thứ n + 1 bé nhất. Rõ ràng A  A1  ...  An  ... Gọi mi là đơn thức thứ i của Ai , i = 1, 2, … m1  m2  ...  mn  ... Điều này mâu thuẫn với M(A) tập các đơn thức của các đa thức của A là có phần tử nhỏ nhất. 9 Định lý 1.3. Cho I là iđêan của vành R = K[x]. Trên R cố định một thứ tự từ và cho T  in( I ) là một từ nào đó. Khi đó tập các đa thức f  I với in( f )  T chỉ có một phần tử tối tiểu (theo giả thứ tự định nghĩa như ở Định lý 1.2). Chứng minh. Theo Định lý 1.2 thì tập đó có phần tử tối tiểu. Bây giờ chứng minh nó duy nhất. Thật vậy, giả sử ngược lại, tập đó có ít nhất 2 phần tử tối tiểu khác nhau f và g. Khi đó chúng có dạng: f  T  1 x a1   2 x a 2  ...   n x an g  T  1 x a1  2 x a 2  ...  n x an trong đó  i ,  i  0, i  1, n . Gọi k là chỉ số nhỏ nhất mà  k   k . Không mất tính tổng quát ta giả sử k  1. Do I là iđêan và f , g  I  1. f ,1.g  I  1. f  1.g  I .  ( 1  1 )T  (11  11 ).x a1  ( 2 1  1 2 ).x a 2  ...  ( n 1  1 n ).x an  I  (1  1 )T  ( 2 1  1 2 ).x a 2  ...  ( n 1  1 n ).x an  I . Do 1  1  1  1  0 , và do K là một trường nên tồn tại   K sao cho   (1  1 )1  0 . Từ đó suy ra:  ((1  1 )T  ( 2 1  12 ).x a 2  ...  ( n 1  1 n ).x an )  I .  T   ( 2 1  1 2 ).x a 2  ...   ( n 1  1 n ).x an  I . Điều này mâu thuẫn với f, g là phần tử tối tiểu. 1.3. ĐỊNH LÝ HILBERT VỀ KHÔNG ĐIỂM Không gian afin n - chiều trên trường K là tập AKn gồm các điểm  a1,..., an   K n . Khi K đã rõ, ta chỉ kí hiệu đơn giản là An . Mỗi đa thức f  x   K  x  xác định một hàm từ An vào K biến mỗi điểm  a1 ,..., an  thành phần tử f  a1 ,..., an  . Thông thường khi xét không gian afin n - chiều ta đôi khi xét cùng với vành đa thức n - biến K  x  . Để nói rõ mối liên quan này, đôi khi x1,..., xn còn gọi là các toạ độ của không gian An . 10 Với mỗi tập A  K  x  , kí hiệu Z  A  là tập nghiệm chung của các đa thức f  A trong không gian An :   Z  A   a1,..., an   An f  a1,..., an   0, f  A Mỗi phần tử của tập này còn được gọi là không điểm của tập đa thức A. Định lý 1.4. (Định lý Hilbert về không điểm) Cho K là trường, K là bao đóng đại số của K và f , f1 ,..., f n  K  x  . Các điều khẳng định sau tương đương: n i) Với mọi a  AK , f1  a   ...  f n  a   0 suy ra f  a   0 . ii) Tồn tại 0  s  N sao cho f   f1,..., f n  . s Chú ý rằng hai điều kiện trên có thể diễn đạt như sau: i) Z  f1 ,..., f n   Z  f  , trong đó các tập không điểm xét trong AKn . ii) f   f1,..., f n  . Định lý 1.5. Cho I   f1 ,..., f n  là iđêan và f là đa thức của K  x  . Gọi G là cơ sở Groebner của iđêan  f1,..., f n ,1  fy  trong vành K  x, y  , trong đó y là biến mới. Khi đó các điều kiện sau tương đương: i) f  I . ii) G chứa một đa thức hằng. iii)  f1,..., f n ,1  fy   K  x, y  . Hệ quả. Cho I   f1 ,..., f n  là iđêan và f là đa thức của K  x  . Khi đó, ta có f I khi và chỉ khi 1 là cơ sở Groebner rút gọn của iđêan I   f1 ,..., f n ,1  fy   K  x, y  . 11 Chương 2 PHẦN MỀM MAPLE VÀ GÓI LỆNH GEOPROVER 2.1. PHẦN MỀM MAPLE Một thực tế là những bài toán đặt ra trong thực tiễn thường là không thể giải quyết bằng những mẹo mực tính toán mang tính thủ công, mà phải dùng tới năng lực tính toán của máy tính điện tử. Phần mềm tính toán ra đời nhằm đáp ứng nhu cầu của thực tiễn, đưa các tính toán phức tạp trở thành công cụ làm việc dễ dàng cho mọi người. Phần mềm Maple là kết quả nghiên cứu của nhóm các nhà khoa học Trường Đại học Waterloo (Canada) và là một trong những bộ phần mềm toán học được sử dụng rỗng rãi nhất hiện nay. Maple là phần mềm có môi trường tính toán khá phong phú, hỗ trợ hầu hết các lĩnh vực của toán học như: Giải tích số, đồ thị, đại số hình thức, ... do đó ta dễ dàng tính được các giá trị gần đúng, rút gọn biểu thức, giải phương trình, bất phương trình, hệ phương trình, tính giới hạn, đạo hàm, tích phân của hàm số, vẽ đồ thị, tính diện tích, thể tích, số phức,... và lập trình giải các bài toán với cấu trúc chương trình đơn giản. Ngoài ra, với phần mềm này ta dễ dàng biên soạn các sách giáo khoa điện tử với chức năng Hyperlink tạo các siêu liên kết văn bản rất đơn giản mà không cần đến sự hỗ trợ của bất kì một phần mềm nào khác (chẳng hạn Page Text, Word, FrontPage...). Với các chức năng trên, Maple là công cụ hỗ trợ đắc lực cho những người làm Toán. Phân mềm Maple tích hợp gói Groebner làm công cụ khai thác những ứng dụng của cơ sở Groebner trong giải một số bài toán hình học phẳng. Một thứ tự từ được gọi là một termorder. Khi xét các thứ tự từ dễ sử dụng nhất là thứ tự từ điển ngược. Thứ tự từ điển được gọi là plex (tức pure lexicographic) và thứ tự từ điển ngược được gọi là tdeg (tức total degree). Maple cần biết termorder muốn dùng plex hay tdeg và một danh sách các biến. Các lệnh sử dụng phổ biến trong gói Groebner của Maple là normalf để thực hiện thuật toán chia và gbasis để tính một cơ sở Groebner. Kết quả là phần dư của đa thức f trong phép chia cho các đa thức thuộc danh sách polylist sử dụng thứ tự từ quy định bởi termorder. 12 Nếu sử dụng các đa thức với hệ số nguyên hay hữu tỷ trong normalf hay gbasic, Maple sẽ giả định rằng ta đang thực hiện trên trường ℚ. Chú ý rằng ở đây không giới hạn trên kích thước của các hệ số. Để Maple cố định một biến trong trường cơ sở (một tham số), ta chỉ cần bỏ qua nó trong danh sách các biến trong termorder. Ta thấy Maple là một ngôn ngữ lập trình bậc cao, rất mạnh nhưng cũng dễ tiếp cận. Về lập trình tính toán vượt xa các ngôn ngữ khác trên cả hai phương diện: mạnh và đơn giản, bởi vì mỗi hàm của nó tương đương với cả một gói chương trình con. Nắm được phần này, người đọc có thể tự mình thiết lập nhưng gói chương trình phục vụ cho mục đích riêng của mình (chưa sẵn có trong Maple). Maple cho ta công cụ lý tưởng để soạn giáo trình và giáo án điện tử. Tóm lại, đây là phương tiện để người thầy thiết lập công cụ hỗ trợ cho phương pháp và phong cách giảng dạy của mình, không bị lệ thuộc vào những gì có sẵn. 2.2. GÓI LỆNH GEOPROVER Gói Groebner trong Maple chưa cung cấp đủ những câu lệnh đủ mạnh giúp đại số hoá các định lý hình học. Vì vậy, gói GeoProver được xây dựng dựa trên ngôn ngữ lập trình Maple để giải quyết vấn đề này, từ đó ta có thể dùng máy tính để kiểm tra tính đúng sai của một giả thuyết hình học. Sau đây là các câu lệnh được sử dụng trong gói: [> restart: with(Groebner): [> read(“D:/Maple/GeoProver.mpl”): with(geoprover): Để sử dụng gói này, chúng ta phải chú ý đường dẫn đến file GeoProver.mpl trong câu lệnh trên. Cần chú ý, kết quả trả lại của các câu lệnh trong gói này là 0 nếu giả thiết đưa ra luôn đúng. Sau đây là một số câu lệnh cơ bản trong gói câu lệnh GeoProver: Kiểm tra ba điểm thẳng hàng: [> A:= Point(x1, x2): B:= Point(x3, x4): C:= Point(x5, x6): [> is_collinear(A, B, C); x1x4 – x1x6 – x3x2 + x5x2 – x5x4 13 Điều trên có nghĩa là với điều kiện ba điểm A, B, C thẳng hàng thì ta có đa thức trên. Kiểm tra ba đường thẳng đồng quy: [> D_:= Point(1, 2): E:= Point(3, 0): F:= Point(0, 1): [> is_concurrent(pp_line(A, B), pp_line(C, D_), pp_line(E, F)); –x4x6 + 2x4x5 + x2x6 – 2x2x5 + 2x2x3 – 2x1x4 – x6x2x3 + x6x1x4 Kiểm tra hai đường thẳng trực giao: [> is_orthogonal(pp_line(A, B), pp_line(C, D_)); 2x4 – 2x2 – x4x6 + x2x6 + x1x5 – x3x5 – x1 + x3 Kiểm tra hai đường thẳng song song: [> is_parallel(pp_line(A, B), pp_line(C, D_)); x4x5 – x4 – x2x5 + x2 – 2x1 + x1x6 + 2x3 – x3x6 Kiểm tra đường thẳng tiếp xúc với đường tròn: [> is_cl_tangent(p3_circle(D_, E, F), pp_line(A, B)); –4x22x32 – 4x12x42 + 16x1x42 + 16x22x3 + 8x12x4 + 8x2x32 – 8x42 + 16x4x2 – 8x22 + 4x12 – 8x1x3 + 4x32 + 16x1x2 – 8x3x1x4 – 16x2x3 – 16x1x4 – 8x1x2x3 – 16x4x2x3 + 8x2x3x1x4 – 16x2x1x4 + 16x3x4 Kiểm tra hai đường tròn tiếp xúc với nhau: [> is_cc_tangent(p3_circle(D_, E, F), p3_circle(Point(0, 0), Point(-1, 0), C)); 92x62 – 4x52 – 8x53 – 8x5x62 – 40x5x6 – 4x54 – 8x52x62 – 40x52x6 – 4x64 – 40x63 Kiểm tra điểm thuộc đường thẳng: [> on_line(E, pp_line(A, B)); 3x – 3x2 + x2x3 – x1x4 Kiểm tra điểm thuộc đường tròn: [> on_circle(A, p3_circle(D_, E, F)); –x12 – x22 + 4x1 + 2x2 – 3 Kiểm tra bốn điểm cùng thuộc một đường tròn: [> is_concyclic(A, F, C, E); –8x1x6 + 8x2x5 + 6x6 – 6x2 + 2x12x6 + 2x22x6 – 2x2x52 – 2x2x62 14 Kiểm tra khoảng cách bằng nhau (AB = EF), hai góc bằng nhau: [> eq_dist(A, B, E, F); x12 – 2x1x3 + x32 + x42 – 2x4x2 + x22 – 4 [> eq_angle(A, B, C, D_, E, F): Ngoài ra còn nhiều câu lệnh để khai báo và kiểm tra khác như: khai báo điểm, trung điểm của đoạn thẳng, đường thẳng qua hai điểm, đường tròn qua ba điểm, đường cao, trung tuyến của tam giác, trọng tâm, trực tâm của tam giác, tâm và bán kính đường tròn nội tiếp, tâm và bán kính đường tròn ngoại tiếp, đường tròn Ơle, đường thẳng qua một điểm và vuông góc (song song) với một đường thẳng, góc giữa hai đường thẳng (hoặc góc xác định bởi ba điểm), khoảng cách, diện tích tam giác, điểm đối xứng qua một điểm (đường thẳng, đường tròn), điểm ngẫu nhiên, giao điểm của hai đường thẳng, giao điểm thứ hai (khác giao điểm đã cho) của hai đường tròn (đường thẳng và đường tròn), vẽ đồ thị... Với các câu lệnh trên, về cơ bản ta có thể đại số hóa được hầu hết các bài toán hình học trong mặt phẳng và kiểm nghiệm tính đúng sai của nó. 15 Chương 3 CHỨNG MINH ĐỊNH LÝ HÌNH HỌC BẰNG MÁY TÍNH 3.1. ĐẠI SỐ HÓA ĐỊNH LÝ HÌNH HỌC 3.1.1. Các bước đại số hóa định lý hình học Người ta nhận thấy rằng rất nhiều định lý hình học hoàn toàn được mô tả bằng các khái niệm đại số. Khi biểu diễn các hình hình học trong toạ độ Đề-các vuông góc thì hầu hết các hình hình học và biên của nó có thể xem là tập không điểm của các đa thức, và các quan hệ giữa chúng đều có thể mô tả bằng các phương trình đa thức cũng như tập không điểm phải xét trên trường số thực. Quy trình chứng minh định lý hình học trên Maple được tóm tắt thông qua các bước sau đây: Bước l: Đại số hóa bài toán hình học. Bước 2: Chạy trên phần mềm Maple tìm cơ sở Groebner của iđêan (f1 = 0,..., fs, 1 - yg) với chú ý xem các biến độc lập như tham số. Bước 3: Cơ sở Groebner của iđêan (f1 = 0, ... , fs, 1 - yg) chứa các đa thức 1 khi và chỉ khi định lý hình học cần chứng minh là đúng. Nếu tại bước 2 ta vẫn xem các biến độc lập là biến, thì tại bước 3 nếu cơ sở Groebner của iđêan (f1 = 0, ..., fs, 1 - yg) chứa đa thức 1 hoặc chứa đa thức chỉ chứa biến độc lập, thì ta vẫn kết luận được định lý hình học cần chứng minh là đúng. Tuy nhiên điều ngược lại chỉ đúng nếu ta chọn thứ tự từ khử đối với các biến không độc lập và y (chẳng hạn dùng plex và xếp các biến độc lập ở sau cùng). 3.1.2. Đại số hóa một số định lý hình học Giả sử cho định lý hình học với: Giả thiết: Được mô tả bởi hệ phương trình 𝑓1 = ⋯ = 𝑓𝑠 = 0. Kết luận: Khi đó mọi nghiệm thực của nó phải thoả mãn hệ phương trình 𝑔1 = ⋯ = 𝑔𝑟 = 0 với 𝑓1 , … , 𝑓𝑠 , 𝑔1 , … , 𝑔𝑟 ∈ ℝ[𝑢1 , … , 𝑢𝑡 , 𝑥1 , … , 𝑥𝑛 ] là những đa thức với hệ số thực. Các biến 𝑢1 , … , 𝑢𝑡 độc lập đại số (tức là toạ độ của các điểm tương ứng với các biến này có thể chọn tuỳ ý), còn các biến 𝑥1 , … , 𝑥𝑛 là phụ thuộc, nghĩa là từng biến trong danh sách này phải xuất hiện trong ít nhất một đa thức fi nào đó. 16 Ta sử dụng ngôn ngữ đại số để mô tả một số định lý hình học sau đây: Ví dụ 3.1. Trong một tam giác, ba đường trung trực đồng quy. Hình 3.1 Đại số hóa định lý trên như sau: Không mất tính chất tổng quát, ta có thể đặt tọa độ các điểm A(0, 0), B(c, 0) và điểm C(a, b). Giả sử các đường trung trực của các cạnh AB và BC cắt nhau tại điểm O1(x1, y1). Các đường trung trực hoàn toàn được xác định bởi các điểm A, B, C và O1 và ta có các phương trình sau đây: 𝑐 (p1): 𝑥1 − = 0 2 (p2): 𝑐−𝑎 𝑏 . 𝑥1 − 𝑦1 + 𝑏2 −𝑐 2 +𝑎2 2𝑏 =0 Giả sử rằng các đường trung trực của AB và AC cắt nhau tại điểm O2(x2, y2). Điều này dẫn đến hai phương trình khác như sau: 𝑐 (𝑝1′ ): 𝑥2 − = 0 2 (𝑝3 ): 𝑎 𝑏 𝑎2 . 𝑥2 + 𝑦2 − − =0 𝑏 2 2𝑏 Từ đó, ta có hệ 𝐺 = {𝑝1 , 𝑝2 , 𝑝1′ , 𝑝3 }. Ta cần chứng minh 𝑂1 ≡ 𝑂2 nghĩa là (𝑥1 , 𝑦1 ) = (𝑥2 , 𝑦2 ). Để sử dụng phương pháp cơ sở Groebner, cơ sở Groebner G’ của G được tính và mục tiêu là chứng minh 𝑥1 − 𝑥2 → 𝐺 ′ = 0 và 𝑦1 − 𝑦2 → 𝐺 ′ = 0. Với đa thức phía trái của phương trình là mệnh đề được mô tả. Ví dụ 3.2. (Định lý con bướm) Cho đường tròn tâm O. Các điểm A, B, C, D thuộc đường tròn trên. Gọi P là giao điểm của AC và BD. Gọi F, G tương ứng là giao điểm của đường thẳng đi qua P và vuông góc với OP với đường thẳng AB, CD. Khi đó P là trung điểm của FG. 17
- Xem thêm -

Tài liệu liên quan