Rate this post

Nó là một công cụ hữu ích, mô tả đầy đủ quan hệ thứ tự từng phần. Do đó, nó còn được gọi là sơ đồ Order. Rất dễ dàng chuyển đổi một đồ thị có hướng của một quan hệ trên tập A thành một biểu đồ Hasse tương đương. Do đó, trong khi vẽ biểu đồ Hasse phải ghi nhớ những điểm sau.

  1. Các đỉnh trong biểu đồ Hasse được biểu thị bằng điểm chứ không phải bằng vòng tròn.
  2. Vì thứ tự từng phần là phản xạ, do đó mỗi đỉnh của A phải liên quan đến chính nó, vì vậy các cạnh từ một đỉnh đến chính nó sẽ bị xóa trong biểu đồ Hasse.
  3. Vì một thứ tự từng phần có tính bắc cầu, do đó bất cứ khi nào aRb, bRc, chúng ta có aRc. Loại bỏ tất cả các cạnh được ngụ ý bởi thuộc tính bắc cầu trong biểu đồ Hasse, tức là, xóa cạnh từ a đến c nhưng giữ lại hai cạnh còn lại.
  4. Nếu đỉnh ‘a’ được nối với đỉnh ‘b’ bằng một cạnh, tức là aRb, thì đỉnh ‘b’ xuất hiện phía trên đỉnh ‘a’. Do đó, mũi tên có thể bị bỏ qua khỏi các cạnh trong biểu đồ Hasse.

Biểu đồ Hasse đơn giản hơn nhiều so với biểu đồ có hướng của thứ tự từng phần.

Các bài viết liên quan:

Ví dụ: Xét tập A = {4, 5, 6, 7}. Gọi R là quan hệ ≤ trên A. Vẽ đồ thị có hướng và giản đồ Hasse của R.

Lời giải: Quan hệ ≤ trên tập A được cho bởi

             R = {{4, 5}, {4, 6}, {4, 7}, {5, 6}, {5, 7}, {6, 7}, {4, 4}, {5, 5} , {6, 6}, {7, 7}}

Đồ thị có hướng của quan hệ R như được minh họa trong hình:

Để vẽ biểu đồ Hasse về thứ tự từng phần, hãy áp dụng các điểm sau:

  1. Xóa tất cả các cạnh được ám chỉ bởi thuộc tính phản xạ, tức là

(4, 4), (5, 5), (6, 6), (7, 7)

  1. Xóa tất cả các cạnh được bao hàm bởi thuộc tính bắc cầu, tức là

(4, 7), (5, 7), (4, 6)

  1. Thay các vòng tròn biểu diễn các đỉnh bằng các dấu chấm.
  2. Bỏ qua các mũi tên.

Sơ đồ Hasse như thể hiện trong hình:

Upper Bound: Coi B là tập con của tập có thứ tự một phần A. Một phần tử x ∈ A được gọi là cận trên của B nếu y ≤ x với mọi y ∈ B.

Lower Bound: Coi B là một tập con của tập có thứ tự một phần A. Một phần tử z ∈ A được gọi là cận dưới của B nếu z ≤ x với mọi x ∈ B.

Ví dụ: Xét poset A = {a, b, c, d, e, f, g} được sắp xếp trong hình. Cũng cho B = {c, d, e}. Xác định cận trên và cận dưới của B.

Lời giải: Giới hạn trên của B là e, f và g vì mọi phần tử của B là ‘≤’ e, f và g.

Các giới hạn dưới của B là a và b vì a và b là ‘≤’ mọi phần tử của B.

Least Upper Bound (SUPREMUM)

Cho A là một tập con của tập có thứ tự từng phần S. Một phần tử M trong S được gọi là giới hạn trên của A nếu M nối tiếp mọi phần tử của A, tức là nếu, với mọi x trong A, chúng ta có x <= M

Nếu giới hạn trên của A đứng trước mọi giới hạn trên khác của A, thì nó được gọi là giới hạn trên của A và được ký hiệu là Sup (A)

Greatest Lower Bound (INFIMUM)

Một phần tử m trong tập hợp S được gọi là giới hạn dưới của tập con A của S nếu m đứng trước mọi phần tử của A, tức là nếu, với mọi y trong A, chúng ta có m <= y

Nếu một giới hạn dưới của A kế tiếp mọi giới hạn dưới khác của A, thì nó được gọi là infimum của A và được ký hiệu là Inf (A)

Ví dụ: Xác định giới hạn trên nhỏ nhất và giới hạn dưới lớn nhất của B = {a, b, c} nếu chúng tồn tại, của poset có biểu đồ Hasse được hiển thị trong hình:

Lời giải: Giới hạn trên nhỏ nhất là c.

Giới hạn dưới lớn nhất là k.

Leave a Reply

Call now
%d bloggers like this: