Cần tuyển chọn tối thiểu ra bao nhiêu người để chắc chắn có ít nhất 2 người có cùng ngày sinh trong năm 2016?

Câu 14:

Cho tập A = {1, 2, 3, 4, 5, 6} và quan hệ R ⊆ A x A với. R= {(1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (1,3), (3,1), (1, 5), (5, 1), (2, 4), (4, 2), (2,6), (6,2), (3,5), (5,3), (4,6), (6,4)}

Đồ thị biểu diễn quan hệ R là

Lời giải:

Đáp án đúng: A

Quan hệ R được biểu diễn bằng đồ thị có hướng. Các cặp (x, y) trong R được biểu diễn bằng cung từ đỉnh x đến đỉnh y.

* Các cặp (x, x): Được biểu diễn bằng vòng lặp tại đỉnh x.
* Các cặp (x, y) và (y, x): Được biểu diễn bằng cung hai chiều giữa đỉnh x và đỉnh y.
* Các cặp (x, y) mà không có (y, x): Được biểu diễn bằng cung một chiều từ đỉnh x đến đỉnh y.

Kiểm tra từng phương án, ta thấy phương án A phù hợp với quan hệ R đã cho:

* Vòng lặp: Có vòng lặp tại tất cả các đỉnh từ 1 đến 6, tương ứng với các cặp (1,1), (2,2), (3,3), (4,4), (5,5), (6,6).
* Cung hai chiều:
* Giữa 1 và 3, tương ứng với (1,3) và (3,1).
* Giữa 1 và 5, tương ứng với (1,5) và (5,1).
* Giữa 2 và 4, tương ứng với (2,4) và (4,2).
* Giữa 2 và 6, tương ứng với (2,6) và (6,2).
* Giữa 3 và 5, tương ứng với (3,5) và (5,3).
* Giữa 4 và 6, tương ứng với (4,6) và (6,4).

Do đó, đáp án đúng là A.

Câu 15:

Nhận xét nào sau đây là SAI.

Lời giải:

Đáp án đúng: D

Câu A đúng. Ma trận biểu diễn quan hệ có tính phản xạ khi các phần tử trên đường chéo chính đều bằng 1.

Câu B đúng. Ma trận biểu diễn quan hệ có tính đối xứng là ma trận đối xứng qua đường chéo chính.

Câu C đúng. Đồ thị biểu diễn quan hệ có tính phản xạ khi mỗi đỉnh đều có khuyên.

Câu D sai. Tính bắc cầu yêu cầu: nếu có cung từ a đến b và từ b đến c thì phải có cung từ a đến c, chứ không phải từ b đến c như câu D nêu.

Câu 16:

Cho A = {11, 12, 13, 14, 15}. Quan hệ R được xác định: ∀a,b ∈ A, aRb ⇔ a + b = 2k (k=1,2,...) Quan hệ R được biểu diễn là.

Lời giải:

Đáp án đúng: D

Quan hệ R được xác định bởi điều kiện aRb ⇔ a + b = 2k, nghĩa là a + b phải là một số chẵn.

Để a + b là số chẵn, cả a và b phải cùng chẵn hoặc cùng lẻ.

Xét các phần tử của tập A = {11, 12, 13, 14, 15}:
- Các số lẻ là: 11, 13, 15.
- Các số chẵn là: 12, 14.

Vậy quan hệ R bao gồm các cặp:
- (11, 11), (13, 13), (15, 15)
- (12, 12), (14, 14)
- (11, 13), (13, 11)
- (11, 15), (15, 11)
- (13, 15), (15, 13)
- (12, 14), (14, 12)

Kết hợp lại ta được: R = {(11, 11), (12, 12), (13, 13), (14, 14), (15, 15), (11,13), (13, 11), (11, 15), (15, 11), (13, 15), (15, 13), (12, 14), (14, 12)}.

Vậy đáp án đúng là D.

Câu 17:

Cho tập A = {1, 2, 3, 4, 5, 6} và quan hệ tương đương R trên A như sau: R = {(1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (1,2), (2,1), (4,5), (5,4)}. Xác định phân hoạch do R sinh ra.

Lời giải:

Đáp án đúng: B

Quan hệ tương đương R trên tập A tạo ra một phân hoạch của A, trong đó mỗi phần tử của phân hoạch là một lớp tương đương. Hai phần tử a và b thuộc cùng một lớp tương đương nếu (a, b) thuộc R.

Ta có R = {(1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (1,2), (2,1), (4,5), (5,4)}.

- Phần tử 1 tương đương với 1 và 2 (vì (1,1) và (1,2) thuộc R), vậy lớp tương đương chứa 1 là {1, 2}.

- Phần tử 2 tương đương với 2 và 1 (vì (2,2) và (2,1) thuộc R), vậy lớp tương đương chứa 2 là {1, 2}.

- Phần tử 3 chỉ tương đương với chính nó (vì chỉ có (3,3) thuộc R), vậy lớp tương đương chứa 3 là {3}.

- Phần tử 4 tương đương với 4 và 5 (vì (4,4) và (4,5) thuộc R), vậy lớp tương đương chứa 4 là {4, 5}.

- Phần tử 5 tương đương với 5 và 4 (vì (5,5) và (5,4) thuộc R), vậy lớp tương đương chứa 5 là {4, 5}.

- Phần tử 6 chỉ tương đương với chính nó (vì chỉ có (6,6) thuộc R), vậy lớp tương đương chứa 6 là {6}.

Vậy phân hoạch do R sinh ra là: A1 = {1, 2}, A2 = {3}, A3 = {4, 5}, A4 = {6}.

Câu 18:

Biểu thức hằng đúng là?

Lời giải:

Đáp án đúng: B

Biểu thức hằng đúng (tautology) là biểu thức logic luôn luôn đúng, bất kể giá trị chân lý của các biến mệnh đề trong biểu thức đó là gì. Điều này có nghĩa là, cho dù các biến mệnh đề nhận giá trị đúng (True) hay sai (False) thì biểu thức vẫn luôn cho ra kết quả là đúng (True).

* Phương án A: Sai. Biểu thức chỉ đúng khi các biến mệnh đề đúng không phải là định nghĩa của hằng đúng. Hằng đúng phải đúng trong mọi trường hợp.
* Phương án B: Đúng. Đây chính là định nghĩa của biểu thức hằng đúng.
* Phương án C: Sai. Biểu thức nhận chân trị sai trong mọi trường hợp là biểu thức hằng sai (contradiction), không phải hằng đúng.
* Phương án D: Sai. Biểu thức chỉ sai khi các biến mệnh đề sai không phải là định nghĩa của hằng đúng. Hằng đúng phải đúng trong mọi trường hợp.

Câu 19:

Để chứng minh tích của 3 số tự nhiên liên tiếp luôn chia hết cho 6, người ta chứng minh như sau:

- Đặt P(n) = n(n+1)(n+2). P(n) chia hết cho 6 với n>0.

- Ta có, với n = 1; P(1) = 1.2.3 = 6, chia hết cho 6

- Giả sử P(n) đúng, ta đi chứng minh (n+1)(n+2)(n+3) chia hết cho 6.

- Ta có, (n+1)(n+2)(n+3) = n(n+1)(n+2) + 3(n+1)(n+2).

- Ta đã có n(n+1)(n+2) chia hết cho 6. Mặt khác (n+1)(n+2) luôn chia hết cho 2 (kết quả này đã được chứng minh). Do vậy, 3(n+1)(n+2) chia hết cho 6. Như vậy ta được điều phải chứng minh.

Đoạn trên sử dụng phương pháp nào?

Lời giải: