Lời cảm ơn
Để hoàn thành khóa luận "Ứng dụng của cơ sở Gr¨obner để giải hệ
phương trình đa thức", ngoài sự nổ lực của bản thân, tôi còn nhận được
sự giúp đỡ tận tình của các thầy giáo, cô giáo trong khoa Khoa học tự
nhiên, Trường Đại học Quảng Bình trong suốt thời gian thực hiện khóa
luận này. Trước tiên, tôi xin bày tỏ lòng cảm ơn sâu sắc tới thầy giáo
- Th.S Trần Mạnh Hùng, giảng viên Khoa Khoa học tự nhiên, Trường
Đại học Quảng Bình. Thầy đã giành nhiều thời gian quý báu tận tình
hướng dẫn tôi trong suốt quá trình thực hiện khóa luận tốt nghiệp.
Tôi cũng xin gửi lời cảm ơn chân thành và sâu sắc tới các thầy giáo,
cô giáo trong Khoa Khoa học tự nhiên, tới gia đình, bạn bè đã luôn sát
cánh bên tôi, nhiệt tình giúp đỡ, chia sẻ, động viên tôi trong suốt quá
trình học tập cũng như trong khi tôi thực hiện và hoàn chỉnh khóa luận
này.
Trong quá trình thực hiện khóa luận, tôi đã rất cố gắng để hoàn thiện
cả về nội dung lẫn hình thức nhưng vẫn không thể tránh khỏi những
thiếu sót. Nên tôi rất mong nhận được sự góp ý của các thầy giáo, cô
giáo và các bạn để khóa luận được hoàn thiện hơn.
Tôi xin chân thành cảm ơn!
Sinh viên

Trần Thị Viễn

1


Mục lục

Lời cảm ơn

1


. . . . . . . . . . . . . . . . . . . . . . . 19

1.4.1

Thứ tự từ . . . . . . . . . . . . . . . . . . . . . . 19

1.4.2

Iđêan khởi đầu và cơ sở Gr¨obner . . . . . . . . . 22

1.4.3

Thuật toán chia . . . . . . . . . . . . . . . . . . 27

1.4.4

Tiêu chuẩn Buchberger . . . . . . . . . . . . . . . 28

1.4.5

Thuật toán Buchberger . . . . . . . . . . . . . . . 31

2


2 Ứng dụng của cơ sở Gr¨
obner để giải hệ phương trình đa
thức


. . . . . . . . . . . . 48

KẾT LUẬN

58

TÀI LIỆU THAM KHẢO

59

3


MỞ ĐẦU
1. Lí do chọn đề tài
Tính toán hình thức (symbolic computation), hay còn gọi là Đại số
máy tính (Computer Algebra), 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. Nhờ sự ra đời của Đại số
máy tính người ta có thể giải phương trình với hệ số bằng chữ, tính tích
phân bất định,... điều mà trước đó máy tính chỉ thực hiện được với hệ
số hằng số, tính tích phân xác định. Đây là một chuyên ngành kết hợp
chặt chẽ toán học với khoa học máy tính. 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. Khi khả năng tính toán mỗi ngày một tăng
của máy tính sẽ 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ó tác dụng tích cực trong nghiên cứu
toán học lí thuyết.
Lý thuyết cơ cở Gr¨obner được nghiên cứu lần đầu tiên vào khoảng
thập niên 60 của thế kỉ XX, nó nhanh chóng trở thành hạt nhân của
ngành hạt nhân của ngành Đại số máy tính và là một công cụ hữu hiệu

Đối tượng nghiên cứu chính của khóa luận là ứng dụng của cơ sở
Gr¨obner trong hệ phương trình đa thức. Bên cạnh đó còn nghiên cứu
về vành, iđêan, trường, vành đa thức, cơ sở Gr¨obner, các kiến thức này
xem như là sự chuẩn bị cho các kiến thức chính của khóa luận.
5


4. Phương pháp nghiên cứu
- Phương pháp nghiên cứu lí luận: Đọc và nghiên cứu các tài liệu,
giáo trình về các vấn đề cần nghiên cứu như: vành, iđêan, vành đa thức,
iđêan đơn thức, quan hệ thứ tự, thứ tự từ, khái niệm cơ sở Gr¨obner,
thuật toán chia đa thức nhiều biến, thuật toán Buchberger để tìm cơ
sở Gr¨obner, một số thuật toán ứng dụng của cơ sở Gr¨obner trong hệ
phương trình đa thức.
- Phương pháp lấy ý kiến chuyên gia: Gồm ý kiến của các giảng viên
hướng dẫn khoa học và các giảng viên khác trong Bộ môn Toán, Khoa
Khoa học tự nhiên, Trường Đại học Quảng Bình.
5. Tầm quan trọng đối với khoa học và thực tiễn
Khóa luận có thể là tài liệu tham khảo cho những sinh viên chuyên
ngành Toán của Trường Đại học Quảng Bình có mong muốn tiếp tục
tìm hiểu về Đại số máy tính. Với bản thân, nghiên cứu về lí thuyết cơ
sở Gr¨obner giúp tôi hiểu rõ hơn về lí thuyết này và nắm được ứng dụng
của nó trong hệ phương trình đa thức. Qua đó tôi cũng thấy được sự
phát triển của khoa học máy tính ngày nay có tác dụng tích cực trong
nghiên cứu toán học lí thuyết.
6. Bố cục khóa luận
Ngoài các phần mở đầu, kết luận và tài liệu tham khảo, nội dung
khóa luận gồm 2 chương:
Chương 1: Kiến thức cơ sở
Chương này là hệ thống gồm một số kiến thức về vành, iđêan, vành


Định nghĩa 1.1.1. Vành là một tập hợp R = ∅ được trang bị phép
toán cộng "+":(a, b) → a + b và phép toán nhân "." : (a, b) → a.b
thỏa mãn các tính chất sau:
(i) Đối với phép cộng, R là một nhóm giao hoán.
(ii) Phép nhân có tính kết hợp, tức là với mọi a, b, c ∈ R :
a.(b.c) = (a.b).c.
(iii) Phép nhân có tính phân phối đối với phép cộng, tức là với mọi
a, b, c ∈ R : a.(b + c) = a.b + a.c và (b + c).a = b.a + c.a.
8


Nhận xét. Phần tử không của vành được kí hiệu là 0. Vành có một
phần tử 0 kí hiệu là 0. Vành R được gọi là vành có đơn vị nếu nó chứa
phần tử 1 thỏa mãn a1 = 1a = a với mọi a ∈ R. Vành R được gọi là
vành giao hoán nếu với mọi a, b ∈ R, ab = ba.
Trong toàn bộ khóa luận này chỉ xét đến vành giao hoán, có đơn
vị.
Ví dụ.
1. Tập các số nguyên Z, số thực R, số phức C cùng với các phép cộng
và phép nhân thông thường lập thành một vành. Tập N không phải
là vành.
2. Cho R = 0 là một vành (giao hoán, có đơn vị) và n ≥ 2 là một số
tự nhiên. Tập các ma trận vuông cấp n với các phần tử thuộc R
với phép cộng và phép nhân ma trận lập thành một vành có đơn vị
nhưng không giao hoán.
Định nghĩa 1.1.2. Cho R là một vành và a ∈ R. Phần tử a được gọi
là
(i) ước của không nếu a = 0 và tồn tại 0 = b ∈ R sao cho ab = 0,
(ii) khả nghịch (hoặc đơn vị) nếu tồn tại c ∈ R sao cho ac = 1.

Định nghĩa 1.1.8. Một tập con S ⊆ R đóng đối với phép cộng và
phép nhân của R được gọi là vành con nếu nó chứa phần tử 1 của R và
10


bản thân nó cùng với các phép toán cảm sinh lập thành một vành.
Ví dụ.
1. Một vành bao giờ cũng có ít nhất hai vành con là vành con tầm
thường 0 và chính nó. Vành Z chỉ có hai vành con đó.
2. Z cũng là vành con thực sự không tầm thường của Q.
3. Tập các đa thức một biến và tập các hàm hằng số là những vành
con thực sự không tầm thường của vành C[a, b].
Bổ đề 1.1.9. Cho R là vành và S ⊆ R. Khi đó S là vành con nếu và
chỉ nếu có các điều kiện sau:
(i) 1 ∈ S.
(ii) Nếu a, b ∈ S thì a − b ∈ S.
(iii) Nếu a, b ∈ S thì ab ∈ S.

1.2

Iđêan

Định nghĩa 1.2.1. Cho R là một vành. Tập con I = ∅ của R được gọi
là iđêan nếu thỏa mãn hai điều kiện:
(i) Với mọi a, b ∈ I, a + b ∈ I.
(ii) Với mọi a ∈ I và r ∈ R, ra ∈ I.
Nhận xét.
• Iđêan của R mà khác R được gọi là iđêan thực sự của R. Một iđêan
của R là iđêan thực sự khi và chỉ khi nó không chứa bất kỳ phần
tử khả nghịch nào của R.

1.3

Vành đa thức

Đơn thức
Cho R là một vành và x1 , ..., xn (n ≥ 1) là các biến.
Một biểu thức có dạng: xa11 ...xann gọi là đơn thức, trong đó (a1 , ..., an ) ∈
Nn được gọi là bộ số mũ của đơn thức.
Khi a1 = ... = an = 0 thì đơn thức được kí hiệu là 1.
Phép nhân trên tập các đơn thức được định nghĩa:
(xa11 ...xann )(xb11 ...xbnn ) = xa11 +b1 ...xann +bn .
Tức là phép nhân đơn thức ứng với phép cộng bộ số mũ trong nửa
nhóm cộng Nn .
Từ
Từ là biểu thức có dạng : αxa11 ...xann .
Trong đó α ∈ R được gọi là hệ số của từ.
Hai từ khác không αxa11 ...xann và βxa11 ...xann được gọi là đồng dạng với
nhau.
Đa thức
Ta kí hiệu: x = (x1 , ..., xn ), a = (a1 , ..., an ) ∈ Nn và xa = xa11 ...xann .
αa xa

Khi đó: Tổng hình thức của các từ f (x) =
a∈Nn

được gọi là đa thức n biến x1 , ..., xn trên vành R trong đó chỉ có một số
13


hữu hạn hệ số αa = 0.

βb xb ,
b∈Nn

trong đó βa = α và βb = 0 với mọi b = a.
Nếu α1 xa1 , ..., αp xap là tất cả các từ của f (x) thì có thể xem f (x) là
tổng đa thức của các từ này qua phép đồng nhất vừa nêu:
f (x) = α1 xa1 + ... + αp xap , (∗)
trong đó a1 , ..., ap ∈ Nn là bộ số mũ khác nhau. Biểu diễn này là duy
nhất và gọi là biểu diễn chính tắc của đa thức f (x).
Phép nhân đa thức được định nghĩa: (
a∈Nn

với γa =

αa xa )(
a∈Nn

βa xa ) =

γa xa
a∈Nn

αb βc .
b,c∈Nn ,b+c=a

Nhận xét rằng γa = 0 chỉ khi tồn tại b và c với αb = 0 và βc = 0 để
a = b + c. Do vậy chỉ có một số hữu hạn hệ số γa = 0 và phép nhân đa
14



được quy ước là một số tùy ý.
15


• Nhiều khi ta còn dùng bậc của đa thức đối với một tập con các
biến, chẳng hạn {x1 , ..., xk }, được định nghĩa như sau:
degx1 ,...,xk f (x) = max{a1 + ... + ak } | αa = 0},
trong đó k < n cố định. Nói cách khác, đó là bậc tổng thể của f (x)
xét như đa thức của vành K[xk+1 , ..., xn ][x1 , ..., xk ]
Mệnh đề 1.3.3. Nếu R là miền nguyên, thì với mọi đa thức f (x), g(x) ∈
R[x] đều có
deg(f (x)g(x)) = degf (x) + degg(x)
và
deg(f (x) + g(x)) ≤ max{degf (x), degg(x)}.
Hơn nữa, ta có bất đẳng thức chặt khi
degf (x) = degg(x) và fdegf (x) = −gdegg(x) .
Định lí 1.3.4. Cho R là vành giao hoán, có đơn vị là 1. Các điều kiện
sau là tương đương:
(i) Mọi tập khác rỗng các iđêan của R đều có phần tử cực đại (đối với
quan hệ bao hàm).
(ii) Mọi dãy tăng các iđêan trong R
I1 ⊆ I2 ⊆ ... ⊆ In ⊆ In+1 ⊆ ...,
là dừng, tức là tồn tại k để Ik = Ik+1 = ...
(iii) Mọi iđêan của R đều hữu hạn sinh; tức là với mọi iđêan I ⊆ R tồn
tại f1 , f2 , ..., fs ∈ I sao cho I = (f1 , f2 , ..., fs ).
Một vành thỏa mãn một trong ba điều kiện trên được gọi là vành
Noether.
16



Định nghĩa 1.3.12. Iđêan I ⊆ R[x] được gọi là iđêan đơn thức nếu nó
sinh bởi các đơn thức.
Một iđêan có dạng I = (xa ; a ∈ A), trong đó A ⊆ Nn .
Chú ý. Trong định nghĩa này không yêu cầu tập A hữu hạn.
Bổ đề 1.3.13. Cho I = (xa ; a ∈ A) là iđêan đơn thức. Đơn thức xb ∈ I
khi và chỉ khi xb chia hết cho một đơn thức xa với a ∈ A nào đó.
Bổ đề 1.3.14. Cho I là iđêan đơn thức và f ∈ K[x]. Các điều kiện sau
là tương đương:
(i) f ∈ I.
(ii) Mọi từ của f thuộc I.
(iii) f là tổ hợp tuyến tính trên K của các đơn thức thuộc I.
Hệ quả 1.3.15. Hai iđêan đơn thức trong một vành đơn thức bằng
nhau nếu chúng chứa cùng một tập đơn thức.
Bổ đề 1.3.16. Iđêan I là iđêan đơn thức khi và chỉ khi với mọi f ∈ I,
các từ của f đều thuộc I.
Bổ đề 1.3.17. (Bổ đề Dickson)
Mọi Iđêan đơn thức I = (xa ; a ∈ A) bao giờ cũng viết được dưới dạng
I = (xa(1) , ..., xa(s) ), trong đó a(1), ..., a(s) ∈ A. Nói riêng I là hữu hạn
sinh.

18


1.4

Cơ sở Gr¨
obner

1.4.1


Ví dụ.
• Quan hệ nhỏ hơn hoặc bằng thông thường trên R là một thứ tự
toàn phần nhưng là quan hệ thứ tự bộ phận trên C.
• Kí hiệu M là tập tất cả các đơn thức trong vành K[x]. Quan hệ
theo bậc tổng thể là một thứ tự bộ phận trên M (tức là m1 ≤ m2
nếu m1 = m2 hoặc deg(m1 ) < deg(m2 )). Nó là thứ tự toàn phần
nếu và chỉ nếu số biến là 1.
Định nghĩa 1.4.2. Cho X là một tập được sắp bởi thứ tự ≤ và A ⊆ X.
Phần tử a ∈ A được gọi là phần tử tối tiểu (tương ứng tối đại) nếu với
mọi b ∈ A mà b ≤ a (t.ư a ≤ b) thì a = b, tức là không có phần tử nhỏ
hơn (t.ư lớn hơn) a ở trong A.
Phần tử a ∈ A là phần tử nhỏ nhất (t.ư lớn nhất) nếu với mọi b ∈ A
ta có a ≤ b (t.ư b ≤ a).
Phần tử b ∈ X là chặn trên (t.ư chặn dưới) của A nếu với mọi a ∈ A
ta có a ≤ b (t.ư b ≤ a).
Tập X được gọi là tập được sắp tốt nếu nó được sắp hoàn toàn và
mọi tập con khác rỗng của nó có phần tử nhỏ nhất. Khi đó ta nói quan
hệ thứ tự tương ứng là quan hệ thứ tự tốt.
20


Ví dụ.
• Xét R với mối quan hệ nhỏ hơn hoặc bằng thông thường và S =
[0, 1]. Khi đó 0 và 1 tương ứng là phần tử nhỏ nhất và lớn nhất của
A.
Tập A = (0, 1) không có phần tử tối tiểu và cũng không có phần
tử tối đại nhưng bị chặn trên và chặn dưới trong R.
• Nếu X là một tập được sắp hoàn toàn thì mọi tập con hữu hạn của
nó đều có phần tử nhỏ nhất và phần tử lớn nhất.
Định nghĩa 1.4.3. Thứ tự từ ≤ là một thứ tự toàn phần trên tập M


• x21 x3 >lex x1 x22 >lex x2 nhưng x2
(iv) in(I)in(J)⊆ in(IJ).
(v) in(I) + in (J)⊆ in(I + J).
Định nghĩa 1.4.11. Cho ≤ là một thứ tự từ và I là một iđêan của I.
Tập hữu hạn các đa thức khác không g1 , ..., gs ∈ I được gọi là một cơ sở
Gr¨
obner của I đối với thứ tự từ ≤, nếu in≤ (I) = (in≤ (g1 ), ...,in≤ (gs )).
Tập g1 , ..., gs ∈ I được gọi là một cơ sở Gr¨obner, nếu nó là cơ sở Gr¨obner
của iđêan sinh bởi chính các phần tử này.
Bổ đề 1.4.12. Cho G là một cơ sở Gr¨obner của iđêan I đối với một
thứ thự từ nào đó. Nếu đa thức g ∈ G thỏa mãn, tồn tại đa thức g ∈ G
sao cho in(g )|in(g), thì G\{g} cũng là một cơ sở Gr¨obner của I.
24


Bổ đề 1.4.13. Cho I là một iđêan tùy ý của R. Nếu g1 , ..., gn là cơ sở
Gr¨obner của I đối với một thứ tự từ nào đó, thì g1 , ..., gn là cơ sở của
I.
Nhận xét. Việc xác định iđêan khởi đầu tương đương với việc tìm một
cơ sở Gr¨obner của I (đối với một thứ tự nào đó).
Với một cơ sở đã cho của I có thể là cơ sở Gr¨obner đối với thứ tự từ
này nhưng không phải cơ sở Gr¨obner đối với thứ tự từ khác.
Ví dụ.
• Cho I là iđêan của vành K[x]. Ta biết rằng trên vành này chỉ có
một thứ tự từ (theo bậc), theo Hệ quả 1.3.8 ta có I = (f ), với
f ∈ K[x]. Từ Bổ đề 1.4.8 (i), suy ra in(I) =(in(f )).
• Cho I = (xy 3 , y 5 ) ⊆ K[x, y] và f1 = xy 3 , f2 = xy 3 − y 5 . Cho x > y.
Khi đó in≤lex (f1 ) = in≤lex (f2 ) = xy 3 , nên {f1 , f2 } không là cơ sở
Gr¨obner của I đối với ≤lex , vì in≤lex (I) = I.
Ta thấy in≤glex (f1 ) = in≤rlex (f1 ) = xy 3 , in≤glex (f2 ) =in≤rlex (f2 ) =
y5