Ktl-icon-tai-lieu

Toán rời rạc

Được đăng lên bởi Billintones CL
Số trang: 30 trang   |   Lượt xem: 1347 lần   |   Lượt tải: 0 lần
QUAN HỆ

Bài tập chương 3:

1. Kiểm chứng R là một quan hệ thứ tự trên S. R là quan hệ thứ tự toàn phần
hay bán toàn phần?
Vẽ sơ đồ Hasse cho (S,R) và tìm min, max các phần tử tối đại tối tiểu (nếu
có):
a)

S={2,3…,11,12}, ∀ x,y ∈ S:xRy  (x lẻ và y chẵn) hay (x-y chẵn và x
≤

y)

b)

S={2,4,6,8,10,12,16,20}, ∀ x,y ∈ S:xRy  x|y

c)

S={2,3,4,6,8,16,24,32,48,96},

d)

S={0,5,10,15,20,25,30,40,50},

e)

S={2,3,4,5,7,8,24,48,96},

∀

x,y ∈ S:xRy  x ⋮ y

f)

S={96,768,6,48,384,3,24},

∀

x,y ∈ S:xRy  ∃ k ∈ N:y=2kx (k phụ

∀

∀

x,y ∈ S:xRy  x|y
x,y ∈ S:xRy  x ⋮ y

thuộc vào x và y)
Giải
a) R={(2,2),(2,4),(2,6),(2,8),(2,10),(2,12),(3,2),(3,3),(3,4),(3,6),(3,8),(3,10),
(3,12), (4,4),(4,6),(4,8),(4,10),(4,12),(5,2),(5,4),(5,5),(5,6),(5,8),(5,10),
(5,12),(6,6),(6,8),(6,10),(6,12), (7,2),(7,4),(7,6),(7,7),(7,8),(7,10),(7,12),
(8,8),(8,10),(8,12), (9,2),(9,4),(9,6),(9,8),(9,9),(9,10),(9,12), (10,10),(10,12),
(11,11),(11,2),(11,4),(11,6),(11,8),(11,10),(11,12),(12,12) }
R phản xạ: ∀ x ∈ S={2,3…,11,12}, xRx
(2R2,3R3,4R4,5R5,6R6,7R7,8R8,9R9,10R10,11R11,12R12)
R phản xứng:

R truyền:

3

5

7

∀

9

∀

x,y

x,y,z

11

 R là thứ tự toàn phần
Min=3,max=12

∈

∈

S={2,3…,11,12},

{

S={2,3…,11,12},

2

4

6

8

{xRy
yRx


x=y

xRy
yRz
xRz

10

12

b).
Sơ đồ Hasse:

R không phải là thứ tự toàn phần, min=2, tối đại: 12,16,20.
Các câu còn lại tự giải
2. Cho n là số nguyên dương. Đặt Un là tập các ước số nguyên dương của n.
a) Tìm U12 , U30 ( viết các tập dưới dạng liệt kê).
b) Trên U n định nghiã quan hệ chia hết như sau: x, y ∈U n , x|y ⇔ tồn tại số
nguyên dương k sao cho y = kx. Ta nói khi đó x chia hết y ( hay y chia hết
cho x = x là ước số của y).
i) Chứng tỏ quan hệ chia hết định nghĩa như trên là quan hệ thứ tự trên
U12 và trên U30 . Tổng quát quan hệ chia hết là quan hệ chia hết Và quan hệ
thứ tự trên tập các số nguyên dương.
ii) Cho biết x|y là quan hệ thứ tự trên U10 . Tìm phần tử tối đại, tối
tiểu, lớn nhất, bé nhất (nếu có). Hỏi tương tự cho U12 , U30 .
Giải
a). U12={1,2,3,4,6,12}; U30={1,2,3,5,6,10,15,30}
b). - Quan Hệ R gọi là quan hệ thứ tự nếu nó có tính phản xạ, tính Phản đối
xứng, tính bắc cầu.
i)
- Tính Phản Đối Xứng: với mọi x,y∈ Un (x R y và y R x)  x = y
- Tính Phản Xạ: Với Mọi: x ∈ Un, x Un x x|y => Un có tính phản
xạ.
-Tính Bắc Cầu: Với Mọi: x,y,z ∈ Un,(x Un y) & (y Un z) (x| y & y|z)
 x|z =>Un có tính bắc cầu.

* U12={1,2,3,4,6,12}
R={(2,1),(3,1) ,(4,1) ,(6,1) ,(12,1) ,(12,6) ,(12,4) ,(12,3) ,(12,2) ,(6,3) ,
(6,2) ,(4,2) ,(1,1),(2,2) ,(3,3)...
Bài tập chương 3 QUAN HỆ
1. 

!"#$%&'##()*+,-*./0%10)2
3+
a) 456*78*99*96:*
.*
.).;,<+).=<,.
+
b) 456*>*?*@*9A*96*9?*6A:*
.*
..B
c) 456*7*>*?*@*9?*6>*76*>@*C?:*
.*
..B
d) 45A*D*9A*9D*6A*6D*7A*>A*DA:*
.*
..
e) 456*7*>*D*E*@*6>*>@*C?:*
.*
..
f) 45C?*E?@*?*>@*7@>*7*6>:*
.*
.
F
G46
F
.)FH
,.,+
Giải
+45)6*6+*)6*>+*)6*?+*)6*@+*)6*9A+*)6*96+*)7*6+*)7*7+*)7*>+*)7*?+*)7*@+*)7*9A+*
)7*96+*)>*>+*)>*?+*)>*@+*)>*9A+*)>*96+*)D*6+*)D*>+*)D*D+*)D*?+*)D*@+*)D*9A+*
)D*96+*)?*?+*)?*@+*)?*9A+*)?*96+*)E*6+*)E*>+*)E*?+*)E*E+*)E*@+*)E*9A+*)E*96+*
)@*@+*)@*9A+*)@*96+*)C*6+*)C*>+*)C*?+*)C*@+*)C*C+*)C*9A+*)C*96+*)9A*9A+*)9A*96+*
)99*99+*)99*6+*)99*>+*)99*?+*)99*@+*)99*9A+*)99*96+*)96*96+:
I.1
.
456*78*99*96:*..
)66*77*>>*DD*??*EE*@@*CC*9A9A*9999*9696+
I.
.*
456*78*99*96:*
{
xRy
yRx
.4
J
.**K
456*78*99*96:*
{
xRy
yRz
xRz
7 D E C 99 6 > ? @ 9A 96

L47*.496
Toán rời rạc - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
Toán rời rạc - Người đăng: Billintones CL
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
30 Vietnamese
Toán rời rạc 9 10 490