Luận văn Thạc sĩ Toán học: Cơ sở GROEBNER và chứng minh định lý hình học bằng máy tính

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:60

Thêm vào BST

Báo xấu

21
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầ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ác 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Cơ sở GROEBNER và chứng minh định lý hình học bằng máy tính

Đ 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.40 LU N VĂN TH C Sƾ TOÁN H C Ng ih 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 ih 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 CL 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ự  le x xác đ nh như sau: x1 1 ... x n n  le x x1 1 ... x n 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ự  g le x xác đ nh như sau: x 1 1 ... x n n  g le x x 1 1 ... x n n d eg ( x1 1 ... x n n )  d eg ( x1 1 ... x n n ) hoặc d eg ( x1 1 ... x n n )  d eg ( x1 1 ... x n n )             nếu 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 ... x n  g le x x 1 ... x n 1 n 1 n nếu  1  ...   n   1  ...   n hoặc  1  ...   n   1  ...   n và x1 ... x n  le x x1 ... x n . 1 n 1 n Đ nh nghƿa 1.4. Th tự từ điển ngược lƠ th tự  r le x xác đ nh như sau: x1 1 ... x n n  r le x x1 1 ... x n n d e g ( x1 1 ... x n n )  d e g ( x1 1 ... x n n ) d eg ( x1 1 ... x n n )  d eg ( x1 1 ... x n n )             nếu hoặc 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 ... x n  r le x x1 ... x n nếu  1  ...   n 1 n 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 , ..., x n  . 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ừ  . Nếu in   f    x a , 0    K , thì lc   f    được g i lƠ hệ số đầu và f là đ n th c đầu c a đối với th tự từ  . a lm  x f 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 g 1 , ..., 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   g 1  , ..., in   g s   Tập g 1 , ..., 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 g 1 , ..., g s  I là c sở Groebner c a I đối với một th tự từ nào đó, thì g 1 , ..., 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  I  n 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 g 1 , ..., g s là c sở Groebner c a I đối với một th tự từ nào đó thì g 1 , ..., 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 f 1 , ..., f s nhưng in ( I ) thực sự ch a ( in ( f 1 ) , ..., 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  i n ( I )  ( i n ( g 1 ) , ..., i n ( g s ) ) . (với G   g 1 , ..., g s  ). Cần ch ng minh in ( I )  ( in ( g 1 ) , ..., in ( g s ) ) khi vƠ chỉ khi với m i f  I , in ( f ) chia hết cho i n ( g ) với g  I nƠo đó. f  I  ( g 1 , ..., g s ) f   s Thuận: Với m i , do I nên fi g i . i 1 Ta có in ( f )  in ( I )  in ( f )  ( in ( g 1 ) , ..., in ( g s ) )  in ( f ) chia hết cho in ( g k ) với 1  k  s . 8
Nghịch: Rõ ràng ( in ( g 1 ) , ..., in ( g s ) )  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 ( g 1 ) , ..., in ( g s ) )  in ( I )  ( in ( g 1 ) , ..., in ( g s ) )  in ( I )  ( in ( g 1 ) , ..., in ( g s ) ) . Đ 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  ...  A n  ... G i mi lƠ đ n th c th i c a Ai , i = 1, 2, … m 1  m 2  ...  m n  ... Đ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   1x   2x  ...   n x a1 a2 an g  T  1x  2x  ...   n x a1 a2 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 a 1  ( 2  1   1  2 ). x a 2  ...  ( n  1   1  n ). x a n  I  ( 1   1 ) T  ( 2  1   1  2 ). x a2  ...  ( 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)  0 1 . Từ đó suy ra:  ((  1   1 ) T  ( 2  1   1  2 ). x  ...  ( n  1   1  n ). x )  I a2 an .  T   ( 2  1   1  2 ). x a 2  ...   ( n  1   1  n ). x a n  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 A Kn gồm các điểm  a 1 , ..., a n   K . Khi K đã rõ, ta chỉ kí hiệu đ n giản lƠ . Mỗi đa th c n n A  x   K  x  xác đ nh một hƠm từ vào K biến mỗi điểm  a 1 , ..., a n  thành n f A phần tử f  a 1 , ..., a n  . 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 x 1 , ..., x n còn g i lƠ các to độ c a không gian A n . 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 n trong không gian A : Z A   a 1 , ..., a n   A n f  a 1 , ..., a n   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 , f 1 , ..., f n  K  x  . Các điều khẳng định sau tư ng đư ng: i) Với mọi a  A Kn , f 1  a   ...  f n  a   0 suy ra f  a   0 . ii) Tồn tại 0  s  N sao cho f s   f 1 , ..., f n  . Chú ý rằng hai điều kiện trên có thể diễn đ t như sau: i) Z  f 1 , ..., f n   Z  f  , trong đó các tập không điểm xét trong A Kn . ii) f   f 1 , ..., f n . Đ nh lý 1.5. Cho I   f 1 , ..., 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  f 1 , ..., 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)  f 1 , ..., f n ,1  fy   K  x , y  . H qu . Cho I   f 1 , ..., 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   f 1 , ..., 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 − 2− 2+ 2 (p2): . 1 − 1 + =0 2 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 2 ( 3 ): . 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