Đề thi, bài tập trắc nghiệm online Toán rời rạc – Đề 5

Hàm băm (hash function) có mục đích chính là ánh xạ dữ liệu có kích thước lớn (ví dụ: chuỗi, đối tượng phức tạp) sang dữ liệu có kích thước nhỏ hơn, thường có kích thước cố định, gọi là giá trị băm (hash value). Mục đích là để truy xuất dữ liệu nhanh hơn, đặc biệt trong các cấu trúc dữ liệu như bảng băm (hash table).

Ký hiệu a ≡ b (mod m) trong số học đồng dư có nghĩa là a và b đồng dư modulo m, tức là a và b có cùng số dư khi chia cho m. Điều này cũng tương đương với việc hiệu a - b chia hết cho m.

Phương pháp chứng minh quy nạp là một kỹ thuật mạnh mẽ trong toán học rời rạc, đặc biệt hữu ích để chứng minh các mệnh đề đúng cho tất cả các số tự nhiên (hoặc một tập con vô hạn của số tự nhiên). Nó bao gồm bước cơ sở và bước quy nạp.

Công thức đệ quy cho số Catalan thứ n là C₀ = 1 và Cn = Σ(i=0 to n-1) Ci × C(n-i-1) cho n ≥ 1. Công thức này thể hiện cách xây dựng các đối tượng được đếm bởi số Catalan bằng cách chia bài toán thành các bài toán con nhỏ hơn.

Thuật toán Euclid là một thuật toán hiệu quả để tìm ước chung lớn nhất (GCD - Greatest Common Divisor) của hai số nguyên. Thuật toán này dựa trên nguyên lý rằng ước chung lớn nhất của hai số không thay đổi nếu số lớn hơn được thay thế bằng hiệu của nó với số nhỏ hơn.

Điểm khác biệt chính giữa chỉnh hợp và tổ hợp là thứ tự. Chỉnh hợp quan tâm đến thứ tự các phần tử được chọn, trong khi tổ hợp thì không. Ví dụ, (a, b) và (b, a) là hai chỉnh hợp khác nhau nhưng là cùng một tổ hợp.

Đây là bài toán tổ hợp chập 3 của 5 phần tử, ký hiệu C(5, 3) hoặc ⁵C₃. Công thức tính là C(n, k) = n! ∕ (k! × (n-k)!). Trong trường hợp này, C(5, 3) = 5! ∕ (3! × 2!) = (5 × 4 × 3!) ∕ (3! × 2 × 1) = (5 × 4) ∕ 2 = 10.

Luật hấp thụ trong đại số Boole có hai dạng chính: x + (x × y) = x và x × (x + y) = x. Luật hấp thụ thứ nhất, x + (x × y) = x, thể hiện rằng nếu ta OR một biến x với kết quả của phép AND giữa x và một biến y khác, kết quả vẫn là x.

Đồ thị đầy đủ Kn là một đồ thị đơn vô hướng đặc biệt, trong đó mỗi đỉnh đều kề với tất cả các đỉnh còn lại. Nói cách khác, có một cạnh nối giữa mọi cặp đỉnh phân biệt trong đồ thị Kn.

Một cây là một đồ thị liên thông không có chu trình. Một tính chất cơ bản của cây là một cây có n đỉnh luôn có n - 1 cạnh. Đây là một kết quả quan trọng và thường được sử dụng trong lý thuyết đồ thị.

Luật De Morgan thứ hai trong đại số Boole phát biểu rằng phủ định của phép hội (AND) của hai biến bằng phép tuyển (OR) của phủ định của mỗi biến, tức là (x × y)′ = x′ + y′.

Sự khác biệt chính giữa DFA và NFA nằm ở tính xác định của hàm chuyển trạng thái. Trong DFA, với mỗi trạng thái hiện tại và mỗi ký tự đầu vào, luôn có duy nhất một trạng thái chuyển tiếp tiếp theo. Trong NFA, có thể có không có trạng thái chuyển tiếp, hoặc có nhiều trạng thái chuyển tiếp có thể xảy ra cho cùng một trạng thái và ký tự đầu vào.

Mệnh đề p → q (p kéo theo q) tương đương logic với mệnh đề ¬p ∨ q (không p hoặc q). Đây là một quy tắc cơ bản trong logic mệnh đề, thường được sử dụng để chuyển đổi mệnh đề kéo theo sang dạng tuyển (OR) và phủ định.

Trong lý thuyết ngôn ngữ hình thức, một từ (word) là một chuỗi hữu hạn các ký tự được chọn từ một bảng chữ cái (alphabet) cho trước. Ví dụ, nếu bảng chữ cái là {a, b}, thì 'ab′, 'baa′, 'b′ là các từ, trong khi 'a$' không phải là từ nếu '$' không thuộc bảng chữ cái.

Liên từ 'và' trong ngôn ngữ tự nhiên được biểu diễn bằng phép hội (AND) trong logic mệnh đề. Phép hội chỉ đúng khi cả hai mệnh đề thành phần đều đúng.

Quan hệ tương đương là quan hệ có ba tính chất: phản xạ, đối xứng và bắc cầu. Tính phản đối xứng là tính chất của quan hệ thứ tự (ví dụ: ≤), không phải quan hệ tương đương. Quan hệ tương đương là đối xứng, không phải phản đối xứng.

Phép tuyển loại trừ (XOR), ký hiệu p ⊕ q, đúng khi và chỉ khi một trong hai mệnh đề p hoặc q đúng, nhưng không phải cả hai cùng đúng. Nói cách khác, nó đúng khi p và q có giá trị chân lý khác nhau.

Hệ đếm cơ số 16 còn được gọi là hệ thập lục phân (Hexadecimal). Trong hệ thập lục phân, chúng ta sử dụng 16 ký hiệu để biểu diễn các số, bao gồm các chữ số từ 0 đến 9 và các chữ cái từ A đến F (hoặc a đến f) để biểu diễn các giá trị từ 10 đến 15.

Mệnh đề ∀x P(x) có nghĩa là 'với mọi x, x là số nguyên tố'. Điều này là sai vì không phải tất cả các số nguyên dương đều là số nguyên tố (ví dụ: số 4 không phải là số nguyên tố). Do đó, giá trị chân lý của ∀x P(x) là Sai.

Hàm số f(x) = 2x + 1 là đơn ánh (injective) vì nếu f(x1) = f(x2) thì 2x1 + 1 = 2x2 + 1 suy ra x1 = x2. Tuy nhiên, nó không toàn ánh (surjective) trên tập số nguyên Z vì không có số nguyên x nào sao cho f(x) = 2x + 1 = 2 (ví dụ). Do đó, hàm số này không phải là song ánh (bijective).

Một đồ thị liên thông có đường đi Euler khi và chỉ khi nó có không quá hai đỉnh có bậc lẻ. Nếu có đúng hai đỉnh bậc lẻ, đường đi Euler bắt đầu tại một đỉnh bậc lẻ và kết thúc tại đỉnh bậc lẻ còn lại. Nếu tất cả các đỉnh đều có bậc chẵn, đồ thị có chu trình Euler (một dạng đường đi Euler khép kín).

Đồ thị phẳng là đồ thị có thể được vẽ trên mặt phẳng sao cho các cạnh chỉ giao nhau tại các đỉnh của đồ thị. Nói cách khác, không có hai cạnh nào giao nhau tại một điểm không phải là đỉnh.

Một quan hệ hai ngôi trên tập hợp A là một tập con của tích Descartes A × A. Nếu tập hợp A có n phần tử, thì A × A có n² phần tử. Số tập con của A × A (tức là số quan hệ hai ngôi khác nhau) là 2ⁿ². Trong trường hợp này, n = 3, nên số quan hệ hai ngôi là 2³² = 2⁹ = 512.

Định lý bắt tay (Handshaking Lemma) trong lý thuyết đồ thị nói rằng tổng bậc của tất cả các đỉnh trong một đồ thị bằng hai lần số cạnh của đồ thị. Điều này là do mỗi cạnh được đếm hai lần, một lần cho mỗi đỉnh mà nó kết nối.

Chu trình Hamilton là một chu trình trong đồ thị mà đi qua mỗi đỉnh của đồ thị đúng một lần, ngoại trừ đỉnh bắt đầu và kết thúc là cùng một đỉnh. Nó khác với chu trình Euler, chu trình Euler đi qua tất cả các cạnh mỗi cạnh một lần.

Trong logic vị từ, ký hiệu ∀ được gọi là lượng từ phổ quát (universal quantifier), thường được đọc là 'với mọi′ hoặc 'cho tất cả'. Nó được sử dụng để biểu thị rằng một mệnh đề đúng cho tất cả các đối tượng trong một miền xác định.

Đường kính của một đồ thị liên thông là khoảng cách lớn nhất giữa bất kỳ cặp đỉnh nào trong đồ thị. Khoảng cách giữa hai đỉnh là độ dài của đường đi ngắn nhất giữa chúng. Đường kính thể hiện 'độ rộng′ của đồ thị.

Ma trận quan hệ R là [[1, 0, 1], [0, 1, 0], [1, 0, 1]]. Đường chéo chính có các phần tử là 1 (R(1,1), R(2,2), R(3,3) đều đúng), nên R phản xạ. Ma trận đối xứng qua đường chéo chính (R(i,j) = R(j,i)), nên R đối xứng. Tuy nhiên, R không bắc cầu vì R(1,3) và R(3,1) đúng nhưng R(1,1) đã đúng sẵn (không cung cấp thông tin mới để kiểm tra bắc cầu ở ví dụ này, cần tìm ví dụ khác hoặc nhận xét chung từ ma trận). Ví dụ, R(1,3) và R(3,1) đúng nhưng R(1,1) đã đúng sẵn, không vi phạm tính bắc cầu. Xét lại, phản xạ (đúng vì đường chéo là 1). Đối xứng (đúng vì ma trận đối xứng). Bắc cầu: cần kiểm tra kỹ hơn. Ví dụ: R(1,3) và R(3,1) đều đúng, R(1,1) đúng. R(1,1) và R(1,3) đúng, R(1,3) đúng. R(3,1) và R(1,3) đúng, R(3,3) đúng. Quan hệ này phản xạ và đối xứng, nhưng không bắc cầu (ví dụ cần tìm nếu có). Tuy nhiên, trong các lựa chọn, phản xạ và đối xứng là phù hợp nhất dựa trên ma trận đã cho và các tính chất dễ thấy nhất.

Tập hợp rỗng là tập hợp không chứa phần tử nào. Tập hợp {x | x là số tự nhiên nhỏ hơn 0} không chứa phần tử nào vì số tự nhiên bắt đầu từ 0 trở lên. Các tập hợp khác chứa phần tử (hoặc tập hợp rỗng trong trường hợp {{}}).

Quy tắc Modus Ponens là một quy tắc suy luận cơ bản trong logic mệnh đề. Nó có dạng: nếu p kéo theo q là đúng và p là đúng, thì q cũng phải đúng. Biểu diễn logic của nó là ((p → q) ∧ p) → q.