Cho 2 tập A, B với A = {1,a,2,b,3,c,d}, B = {x,5,y,6,c,1,z}. Số phần tử của tập (A – B) là.

Gọi $a_n$ là số xâu nhị phân độ dài $n$ không chứa 6 số 0 liên tiếp.

Ta có thể xây dựng xâu nhị phân độ dài $n$ bằng cách thêm một bit (0 hoặc 1) vào xâu nhị phân độ dài $n-1$.

Nếu xâu độ dài $n-1$ kết thúc bằng 1, ta có thể thêm 0 hoặc 1 vào cuối.
Nếu xâu độ dài $n-1$ kết thúc bằng 0, ta cần xem xét số lượng số 0 liên tiếp ở cuối xâu.

Ta gọi $a_{n, k}$ là số xâu nhị phân độ dài $n$ kết thúc bằng $k$ số 0 liên tiếp và không chứa 6 số 0 liên tiếp.

Khi đó $a_n = a_{n, 0} + a_{n, 1} + a_{n, 2} + a_{n, 3} + a_{n, 4} + a_{n, 5}$.

Ta có công thức truy hồi:
$a_{n, 0} = a_{n-1}$ (xâu độ dài $n-1$ cộng thêm 1 vào cuối)
$a_{n, 1} = a_{n-1, 0}$ (xâu độ dài $n-1$ kết thúc bằng 0, cộng thêm 0 vào cuối)
$a_{n, 2} = a_{n-1, 1}$ (xâu độ dài $n-1$ kết thúc bằng 1 số 0, cộng thêm 0 vào cuối)
$a_{n, 3} = a_{n-1, 2}$ (xâu độ dài $n-1$ kết thúc bằng 2 số 0, cộng thêm 0 vào cuối)
$a_{n, 4} = a_{n-1, 3}$ (xâu độ dài $n-1$ kết thúc bằng 3 số 0, cộng thêm 0 vào cuối)
$a_{n, 5} = a_{n-1, 4}$ (xâu độ dài $n-1$ kết thúc bằng 4 số 0, cộng thêm 0 vào cuối)
Tuy nhiên, cách này phức tạp.

Ta sẽ tính số xâu nhị phân độ dài 8 chứa 6 số 0 liên tiếp trở lên. Sau đó lấy tổng số xâu nhị phân độ dài 8 trừ đi số xâu vừa tìm được.
Tổng số xâu nhị phân độ dài 8 là $2^8 = 256$.

Các xâu chứa 6 số 0 liên tiếp:
- 000000xx: xx có 4 khả năng (00, 01, 10, 11)
- 1000000x: x có 2 khả năng (0, 1)
- x1000000: x có 2 khả năng (0, 1)
- 00000000: 1 trường hợp
- 0000001x: x có 2 khả năng
- x0000001: x có 2 khả năng
- 11000000
- 01000000
- 00000001
-10000001

Các xâu chứa 7 số 0 liên tiếp:
- 0000000x : x có 2 khả năng
- x0000000 : x có 2 khả năng
- 00000000 : 1

Các xâu chứa 8 số 0 liên tiếp:
- 00000000 : 1

Các xâu chứa 6 số 0 liên tiếp: 00000000, 00000001, 10000000, 01000000, 11000000, 00000010, 00000011, 10000001
Các xâu chứa 7 số 0 liên tiếp: 00000000, 10000000, 00000001
Các xâu chứa 8 số 0 liên tiếp: 00000000

Số xâu có ít nhất 6 số 0 liên tiếp là: 4 + 2 + 2 -1 +1 = 8

Các xâu có 6 số 0 liên tiếp: 00000011, 00000010, 10000001, 01000000, 11000000, 00000100, 00000000
Các xâu có 7 số 0 liên tiếp: 10000000, 00000001,
Các xâu có 8 số 0 liên tiếp: 00000000

Số các xâu chứa 6 số 0 liên tiếp trở lên là: 3+2+2-1 = 7, 6+7+8 = 8+2+2+4-1 = 15
Số xâu chứa ít nhất 6 số 0 liên tiếp là: 8.
Vậy số xâu nhị phân độ dài 8 không chứa 6 số 0 liên tiếp là: 256 - 8 = 248
Tổng số các xâu có ít nhất 6 số 0 liên tiếp:
00000000
00000001
00000010
00000011
10000000
01000000
10000001
11000000
Tổng cộng có 8 xâu.
Vậy, có 256 - 8 = 248 xâu không chứa 6 số 0 liên tiếp.

Gọi A là tập hợp các xâu nhị phân độ dài 5 có 2 bit đầu tiên là 0, B là tập hợp các xâu nhị phân độ dài 5 có 2 bit cuối cùng là 1.

\n

Ta cần tính |A ∪ B|.

\n

Theo công thức bù trừ, |A ∪ B| = |A| + |B| - |A ∩ B|.

\n

\n
• |A|: Hai bit đầu tiên cố định là 0, 3 bit còn lại có thể là 0 hoặc 1. Vậy |A| = 2³ = 8.
\n
• |B|: Hai bit cuối cùng cố định là 1, 3 bit còn lại có thể là 0 hoặc 1. Vậy |B| = 2³ = 8.
\n
• |A ∩ B|: Hai bit đầu tiên là 0 và hai bit cuối cùng là 1. Bit ở giữa có thể là 0 hoặc 1. Vậy |A ∩ B| = 2¹ = 2.
\n

\n

Do đó, |A ∪ B| = 8 + 8 - 2 = 14.

Một quan hệ R trên tập A là phản đối xứng nếu với mọi a, b thuộc A, nếu (a, b) thuộc R và (b, a) thuộc R thì a = b.

* Phương án A: R = {(a,a), (a,b), (b,c), (b,d), (c,c), (c,b), (d,a), (d,b)}. Ta thấy (b, c) thuộc R và (c, b) thuộc R nhưng b ≠ c. Vậy R không phản đối xứng.
* Phương án B: R = {(a,a), (a,c), (a,d), (c, b),(c,c), (d,b), (d,c)}. Ta thấy không có cặp (x, y) và (y, x) nào mà x ≠ y. Vậy R phản đối xứng.
* Phương án C: R = {(a,a), (a,b), (a,c), (b,b), (b,c), (c,c), (c,a), (d,d), (d,b)}. Ta thấy (a, c) thuộc R và (c, a) thuộc R nhưng a ≠ c. Vậy R không phản đối xứng.
* Phương án D: R = {(a,a), (a,c), (b,b), (b,d), (c,c), (c,a), (d,d), (d,c)}. Ta thấy (a, c) thuộc R và (c, a) thuộc R nhưng a ≠ c. (d, c) thuộc R và (c, d) không thuộc R. Vậy R không phản đối xứng.

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

Để xác định ma trận biểu diễn quan hệ R, ta cần xem xét các cặp phần tử trong R. Ma trận sẽ có kích thước 6x6, với hàng và cột tương ứng với các phần tử của tập A = {1, 2, 3, 4, 5, 6}. Phần tử (i, j) của ma trận sẽ là 1 nếu (i, j) thuộc R, và là 0 nếu (i, j) không thuộc R.

* Hàng 1:
* (1, 1) thuộc R => a11 = 1
* (1, 3) thuộc R => a13 = 1
* (1, 5) thuộc R => a15 = 1
* Các phần tử còn lại: a12 = a14 = a16 = 0
* Hàng 2:
* (2, 2) thuộc R => a22 = 1
* (2, 4) thuộc R => a24 = 1
* (2, 6) thuộc R => a26 = 1
* Các phần tử còn lại: a21 = a23 = a25 = 0
* Hàng 3:
* (3, 3) thuộc R => a33 = 1
* (3, 1) thuộc R => a31 = 1
* (3, 5) thuộc R => a35 = 1
* Các phần tử còn lại: a32 = a34 = a36 = 0
* Hàng 4:
* (4, 4) thuộc R => a44 = 1
* (4, 2) thuộc R => a42 = 1
* (4, 6) thuộc R => a46 = 1
* Các phần tử còn lại: a41 = a43 = a45 = 0
* Hàng 5:
* (5, 5) thuộc R => a55 = 1
* (5, 1) thuộc R => a51 = 1
* (5, 3) thuộc R => a53 = 1
* Các phần tử còn lại: a52 = a54 = a56 = 0
* Hàng 6:
* (6, 6) thuộc R => a66 = 1
* (6, 2) thuộc R => a62 = 1
* (6, 4) thuộc R => a64 = 1
* Các phần tử còn lại: a61 = a63 = a65 = 0

Đối chiếu với các đáp án, ta thấy đáp án A phù hợp.