Top 12 # Bài Tập Toán Rời Rạc Có Lời Giải Chương 2 / 2023 Xem Nhiều Nhất, Mới Nhất 12/2022 # Top Trend | Caffebenevietnam.com

Tổng Hợp Bài Tập Toán Rời Rạc Có Đáp Án Rời Rạc Có Lời Giải, Bài Tập Toán Rời Rạc Có Lời Giải / 2023

Giải Toán 6 Đề CươngGiải Toán Lớp 6 Đề CươngGiải Toán 7 Đề CươngĐề Cương Toán Rời Rạc Có GiảiGiải Toán 9 Đề CươngGiải Toán Lớp 5 Đề CươngĐề Cương ôn Tập Toán 8 Thcs Long Toàn Có Đáp ánPhương Hướng,nội Dung,giải Pháp Phát Huy Sức Mạnh Toàn Dân Tộc Trong Giai Đoạn Hiện NayBài Giải Vật Lý Đại Cương A2Bài Giải Vật Lý Đại CươngGiải Bài Hoá Đại Cương 2Bài Giải Vật Lý Đại Cương 2Bài Giải Hóa Đại CươngGiải Đề CươngGiải Hóa 8 Đề CươngGiải Bài Tập Vật Lý Đại Cương 1Bài Giải Logic Học Đại CươngĐề Cương Giải Tích 2

Giải Toán 6 Đề Cương,Giải Toán Lớp 6 Đề Cương,Giải Toán 7 Đề Cương,Đề Cương Toán Rời Rạc Có Giải,Giải Toán 9 Đề Cương,Giải Toán Lớp 5 Đề Cương,Đề Cương ôn Tập Toán 8 Thcs Long Toàn Có Đáp án,Phương Hướng,nội Dung,giải Pháp Phát Huy Sức Mạnh Toàn Dân Tộc Trong Giai Đoạn Hiện Nay,Bài Giải Vật Lý Đại Cương A2,Bài Giải Vật Lý Đại Cương,Giải Bài Hoá Đại Cương 2,Bài Giải Vật Lý Đại Cương 2,Bài Giải Hóa Đại Cương,Giải Đề Cương,Giải Hóa 8 Đề Cương,Giải Bài Tập Vật Lý Đại Cương 1,Bài Giải Logic Học Đại Cương,Đề Cương Giải Tích 2,Đề Cương Giải Tích 3,Giải Bài Tập Quản Trị Học Đại Cương,Giải Bài Tập Excel Tin Học Đại Cương,Giai Bai Tap Thien Van Dai Cuong,Bài Giải Đề Cương ôn Thi Ppnckh,Đề Cương Bài Tập Giải Tích 2,Đề Cương Giải Tích 3 Hust,Đề Cương 45 Năm Giải Phóng Miền Nam,Đề Cương 40 Năm Giải Phóng Miền Nam,Đề Cương Giải Tích 2 Sami,Giải Bài Tập 24 Cường Độ Dòng Điện,Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình Tiếp,Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình Violet,Lười Giải Phiếu Bài Tập Toán Cuối Tuần Toán 4tuân 16,Toán 9 Giải Bài Toán Bằng Cách Lập Phương Trình Violet,Toán Đại 8 Giải Bài Toán Bằng Cách Lập Phương Trình,Toán 9 Giải Bài Toán Bằng Cách Lập Phương Trình,Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình,Toán Lớp 8 Giải Bài Toán Bằng Cách Lập Phương Trình,Toán 9 Giải Bài Toán Bằng Cách Lập Hệ Phương Trình,Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình Tt,Giải Toán Lớp 5 Toán Phát Chiển Năng Lực Tư Tuần 14 Đến 15,16,Các Dạng Toán Và Phương Pháp Giải Toán 8,Các Dạng Toán Và Phương Pháp Giải Toán 6,Phương Pháp Giải Toán Qua Các Bài Toán Olympic,Các Dạng Toán Và Phương Pháp Giải Toán 8 Tập 1,Đề Cương Sơ Bộ Giải Quyết Tranh Chấp Về Thừa Kế,Đề Cương Tuyên Truyền 39 Năm Giải Phóng Miền Nam,Giải Pháp Tăng Cường Công Tác Tư Tưởng Của Đảng,Giải Toán Cuối Tuần 12 Lớp 3 Môn Toán,Toán Lớp 5 Bài Giải Toán Về Tỉ Số Phần Trăm,Đề Cương Toán Lớp 7 Học Kì 2,Đề Cương Kì 2 Toán 7,Đề Cương Toán Lớp 5,Đề Cương Toán Lớp 4 Học Kỳ 1,Đề Cương Toán Lớp 4,Đề Cương Toán Lớp 3,Đề Cương ôn Tập Học Kì 1 Toán 9,Đề Cương Toán Lớp 2 Học Kỳ 1,Đề Cương Học Kì 2 Toán 8,Đề Cương Toán Lớp 5 Học Kì 1,Đề Cương Toán Lớp 5 Học Kỳ 1,Đề Cương ôn Tập Học Kì 2 Toán 6,Đề Cương Toán Rời Rạc,Đề Cương Toán Lớp 5 Học Kỳ 2,Đề Cương ôn Tập Kì 2 Toán 6,Đề Cương ôn Tập Toán 6 Học Kì 1,Đề Cương ôn Tập Kì 1 Toán 9,Đề Cương ôn Tập Toán 8 Kì 1 Có Đáp án,Đề Cương ôn Tập Học Kì 2 Toán 8,Đề Cương ôn Tập Học Kì 2 Toán 7,Đề Cương Học Kì 2 Toán 7,Đề Cương Học Kì 2 Toán 6,Đề Cương Toán 5 Học Kì 1,Đề Cương Toán 5 Học Kì 2,Đề Cương Toán 5 Học Kỳ 1,Đề Cương Toán 6,Đề Cương Toán 6 Học Kì 1,Đề Cương ôn Tập Môn Toán Rời Rạc,Đề Cương Toán 6 Học Kì 2,Đề Cương ôn Tập Môn Toán Lớp 7,Đề Cương ôn Tập Môn Toán Lớp 6,Đề Cương ôn Tập Môn Toán Lớp 5,Đề Cương ôn Tập Môn Toán Lớp 4,Đề Cương Toán 6 Học Kỳ 1,Đề Cương ôn Tập Môn Toán Lớp 3 Học Kì 1,Đề Cương Toán 7 Học Kì 1,Đề Cương Toán 7,Đề Cương Toán 6 Kì 2,Đề Cương ôn Tập Môn Toán Lớp 3,Đề Cương Toán 5,Đề Cương Toán 7 Học Kì 2,Đề Cương Học Kì 2 Toán 11,Đề Cương Học Kì 2 Toán 10,Đề Cương Toán 9 Học Kì 2 Có Đáp án,Đề Cương Toán 9 Học Kì 2,Đề Cương Học Kì 1 Toán 8,Đề Cương Toán 9 Học Kì 1,Đề Cương Học Kì 1 Toán 7,Đề Cương ôn Tập Học Kì 1 Toán 8,Đề Cương Học Kì 1 Toán 6,Đề Cương Toán 8 Học Kì 2,

Giải Toán 6 Đề Cương,Giải Toán Lớp 6 Đề Cương,Giải Toán 7 Đề Cương,Đề Cương Toán Rời Rạc Có Giải,Giải Toán 9 Đề Cương,Giải Toán Lớp 5 Đề Cương,Đề Cương ôn Tập Toán 8 Thcs Long Toàn Có Đáp án,Phương Hướng,nội Dung,giải Pháp Phát Huy Sức Mạnh Toàn Dân Tộc Trong Giai Đoạn Hiện Nay,Bài Giải Vật Lý Đại Cương A2,Bài Giải Vật Lý Đại Cương,Giải Bài Hoá Đại Cương 2,Bài Giải Vật Lý Đại Cương 2,Bài Giải Hóa Đại Cương,Giải Đề Cương,Giải Hóa 8 Đề Cương,Giải Bài Tập Vật Lý Đại Cương 1,Bài Giải Logic Học Đại Cương,Đề Cương Giải Tích 2,Đề Cương Giải Tích 3,Giải Bài Tập Quản Trị Học Đại Cương,Giải Bài Tập Excel Tin Học Đại Cương,Giai Bai Tap Thien Van Dai Cuong,Bài Giải Đề Cương ôn Thi Ppnckh,Đề Cương Bài Tập Giải Tích 2,Đề Cương Giải Tích 3 Hust,Đề Cương 45 Năm Giải Phóng Miền Nam,Đề Cương 40 Năm Giải Phóng Miền Nam,Đề Cương Giải Tích 2 Sami,Giải Bài Tập 24 Cường Độ Dòng Điện,Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình Tiếp,Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình Violet,Lười Giải Phiếu Bài Tập Toán Cuối Tuần Toán 4tuân 16,Toán 9 Giải Bài Toán Bằng Cách Lập Phương Trình Violet,Toán Đại 8 Giải Bài Toán Bằng Cách Lập Phương Trình,Toán 9 Giải Bài Toán Bằng Cách Lập Phương Trình,Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình,Toán Lớp 8 Giải Bài Toán Bằng Cách Lập Phương Trình,Toán 9 Giải Bài Toán Bằng Cách Lập Hệ Phương Trình,Toán 8 Giải Bài Toán Bằng Cách Lập Phương Trình Tt,Giải Toán Lớp 5 Toán Phát Chiển Năng Lực Tư Tuần 14 Đến 15,16,Các Dạng Toán Và Phương Pháp Giải Toán 8,Các Dạng Toán Và Phương Pháp Giải Toán 6,Phương Pháp Giải Toán Qua Các Bài Toán Olympic,Các Dạng Toán Và Phương Pháp Giải Toán 8 Tập 1,Đề Cương Sơ Bộ Giải Quyết Tranh Chấp Về Thừa Kế,Đề Cương Tuyên Truyền 39 Năm Giải Phóng Miền Nam,Giải Pháp Tăng Cường Công Tác Tư Tưởng Của Đảng,Giải Toán Cuối Tuần 12 Lớp 3 Môn Toán,Toán Lớp 5 Bài Giải Toán Về Tỉ Số Phần Trăm,Đề Cương Toán Lớp 7 Học Kì 2,

Bài Tập Toán Rời Rạc Có Lời Giải / 2023

Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai BT Toan roi rac 1

BÀI TẬP CHƯƠNG I Bài 1: Số mã vùng cần thiết nhỏ nhất là bao nhiêu để đảm bảo 25 triệu máy điện thoại khác nhau. Mỗi điện thoại có 9 chữ số có dạng 0XX-8XXXXX với X nhận giá trị từ 0 đến 9.

Giải:

Vì số mã vùng có dạng: 0XX-8XXXXX, với X nhận các giá trị từ 0 đến 9 (10 số), có 07 ký tự X do vậy sẽ có 107 trường hợp. Do đó, theo nguyên lý Dirichlet với 10 triệu máy điện thoại thì số mã vùng cần thiết là: ][35,2000.000.10000.000.25

Bài 2: Biển số xe gồm 8 ký tự, dạng NN-NNNN-XN, ví dụ 75_1576_F1. Hai số đầu là mã tỉnh, X là chữ cái (26 chũ cái). N gồm các số 0, 1, …, 9. Hỏi một tỉnh nào đó cần đăng ký cho 10 triệu xe thì cần bao nhiêu serial (X).

Giải

Bài toán này có 02 cách hiểu: serial ở đây có thể là 02 ký tự NN đầu tiên hoặc là 02 ký tự XN cuối cùng. Cách hiểu 1: (serial là 02 ký tự XN cuối cùng). Hai số NN đầu là mã tỉnh, do nhà nước quy định nên không ảnh hưởng đến kết quả bài toán. Sáu ký tự còn lại có 5 ký tự là N, như vậy có 510 trường hợp. Theo nguyên lý Dirichlet, số serial X tối thiểu phải thỏa mãn: 100000.100000.000.10=⎢⎣⎡⎥⎦⎤. Điều này không hợp lý vì số ký tự chữ cái chỉ là 26. Do vậy, nếu bài toán sửa lại là 1 triệu bảng số xe thì kết quả hợp lý hơn, khi đó số serial là: 10000.100000.000.1=

⎢⎣⎡⎥⎦⎤. Cách hiểu 2: (serial là 02 ký tự NN đầu tiên) Bốn ký tự NNNN sẽ có 104 trường hợp, 02 ký tự XN sẽ có 26*10 = 260 trường hợp. Theo quy tắc nhân, tổng số trường hợp sẽ là: 104*260 = 2.600.000. Do đó, theo nguyên lý Dirichlet, số serial tối thiểu phải là:

Bài 3: Có bao nhiêu xâu nhị phân có độ dài 10: a. Bắt đầu bằng 00 hoặc kết thúc bằng 11. b. Bắt đầu bẳng 00 và kết thúc bằng 11.

Giải

a. Bắt đầu bằng 00 hoặc kết thúc bằng 11. Xâu nhị phân bắt đầu bằng 00 có dạng: 00.xxxxxxxx. Ký tự x có thể là 0 hoặc 1, có 8 ký tự x do vậy có 82 xâu. Xâu nhị phân kết thúc bằng 11 có dạng: xxxxxxxx11. Tương tư ta cũng tính được có 82 xâu. Xâu nhị phân bắt đầu bằng 00 và kết thúc bằng 11 có dạng 00.xxxxxx11. Tương tự như trên, ta cũng tính được có 62 xâu. Vậy số xâu nhị phân bắt đầu bằng 00 hay kết thúc bằng 11 là: Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

BT Toan roi rac 2 4486451222*268=−=−=n xâu. b. Bắt đầu bằng 00 và kết thúc bằng 11. Xâu nhị phân thỏa mãn đề bài phải có dạng: 00.xxxxxx11. Hai ký tự đầu và 02 ký tự cuối là không đổi, do vậy chỉ còn 06 ký tự ở giữa. Do đó số xâu nhị phân thỏa mãn đề bài là: 26

xâu.

Bài 4: Khóa 29 CNTT có 150 SV học NNLT Java, 160 SV hoc Delphi, 40 SV học cả hai môn trên. a. Tìm tất cả SV của khóa 29 biết rằng SV nào cũng phải học ít nhất 01 môn. b. Biết tổng số SV là 285, hỏi có bao nhiêu SV không học Java hoặc Delphi.

Giải

Gọi J: SV học Java D: SV học Delphi a. Số SV của khóa 29 là: 270401601501=−+=−+== DJDJDJn IU SV b. Câu b có 02 cách hiểu: Cách 01: không học ít nhất 01 môn. Số SV không học Java hoặc Delphi là (áp dụng nguyên lý bù trừ) ta tính được: 245402852=−=−= DJnn I SV Cách 02: không học Java cũng chẳng học Delphi: Theo cách hiểu này, áp dụng nguyên lý bù trừ ta tính được số SV như sau: 1540160150285‘2=+−−=+−−== DJDJnDJn IU SV

Giải

Bài toán này cũng có thể được hiểu theo 02 cách. Cách 01: phân biệt chữ thường với chữ hoa. Chữ cái thường: 26 Chữ cái hoa: 26 Chữ số: 10 Do đó, tổng cộng có 26 + 26 + 10 = 62 ký tự khác nhau. Nếu password có n ký tự. Tổng số trường hợp: n62 Số password không có chữ số: n52 Suy ra số password có ít nhất 01 chữ số: nnnn 5262 −= Áp dụng cho các trường hợp n = 6, 7, 8. Tổng số password thỏa yêu cầu đề bài là: 040.583.949.410.167526252625262887766876=−+−+−=++= nnnn

Cách 02: không phân biệt chữ thường với chữ hoa: Cách làm hoàn toàn tương tự, nhưng thay vì sử dụng các số 62 và 52 thì ở đây sử dụng 02 số: 36 và 26. Kết quả sẽ là:

063.3602.684.483.263626362636887766876=−+−+−=++= nnnnBài 6: Có n lá thư bỏ vào n bì thư. Hỏi xác suất để xảy ra trường hợp không có lá thư nào bỏ đúng được bì thư của nó.

Giải Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

Bài 7: Chỉ ra rằng nếu chọn 5 số từ tập 8 số {1, 2, …, 7, 8} thì bao giờ cũng có ít nhất 01 cặp số có tổng là 9.

Giải

Từ 8 số ở trên, ta chia thành 04 cặp: {1, 8}, {2, 7}, {3, 6}, {4, 5} và tổng của mỗi cặp đều bằng 9. Như vậy, đề bài sẽ trở thành chọn 5 số từ 4 cặp số trên. Theo nguyên lý Dirichlet, phải có ít nhất 01 cặp số được chọn hết. Vậy bài toán đã được chứng minh.

Bài 8: Chứng minh rằng trong bất kỳ một nhóm 27 từ tiếng Anh nào cũng có ít nhất 2 từ bắt đầu từ cùng 01 chữ cái.

Giải

Bảng chữ cái của tiếng anh gồm 26 ký tự: a, b, c, …, x, y, z. Vì có 27 từ tiếng Anh và mỗi từ bắt đầu bằng 01 chữ cái nên theo nguyên lý Dirichlet phải có ít nhất 02 từ bắt đầu bằng cùng 01 chữ cái.

Bài 9: Cần phải có bao nhiêu SV ghi tên vào lớp TRR để chắc chắn có ít nhất 65 SV đạt cùng điểm thi, giả sử thang điểm thi gồm 10 bậc.

Giải Gọi n là số sinh viên tối thiểu thỏa mãn đề bài, theo nguyên lý Dirichlet thì ] [6510=n. Do vậy 641164*10 =+=n SV.

Bài 10: Tìm hệ thức truy hồi và cho điều kiện đầu để tính số các xâu nhị phân có độ dài n và không có 2 số 0 liên tiếp. Có bao nhiêu xâu nhị phân như thế có độ dài bằng 5.

Giải

Với xâu nhị phân có độ dài n, ta chia thành 02 trường hợp: Nếu ký tự cuối cùng là 1 thì ký tự trước đó (ký tự thứ n – 1) có thể là 1 hay là 0 đều được. Nếu ký tự cuối cùng là 0 thì ký tự trước đó (ký tự thứ n – 1) chỉ có thể là 1 (vì nếu là 0 thì vi phạm yêu cầu bài toán) nhưng ký tự trước đó nữa (thứ n – 2) có thể là 0 hay 1 đều được. Từ 02 trường hợp trên ta suy ra được: 21 −−+=nnnfff Các điều kiện đầu: 21=f , 32=f Có 13 xâu nhị phân có độ dài 5 và không có 2 số 0 liên tiếp. Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

BT Toan roi rac 4

Giải

Giải

Vậy nghiệm của hệ thức truy hồi là: nnna 3)2(35 −−+=

Bài 13: Tìm hệ thức truy hồi và nr . Với nr là số miền của mặt phẳng bị phân chia bởi n đường thẳng. Biết rằng không có 2 đường thẳng nào song song và cũng không có 03 đường thẳng nào đi qua cùng 1 điểm.

Giải

Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

BT Toan roi rac 5 Với n đường thẳng, theo đề bài thì đường thẳng thứ n sẽ cắt n – 1 đường thẳng còn lại tại n – 1 điểm, tức là sẽ cắt n – 1 + 1 = n phần mặt phẳng. Do đó, số phần mặt phẳng tăng lên là n. Từ đó, ta có được hệ thức truy hồi: nrrnn+=−1. Các điều kiện đầu là: n = 0: r0 = 1. n = 1: r1 = 2.

BÀI TẬP CHƯƠNG II

Bài 14 Chứng minh rằng trong một đơn đồ thị luôn có ít nhất 02 đỉnh có cùng bậc.

Giải

Trong đồ thị đơn, số bậc tối đa cung TH1: Giả sử đồ thì không có đỉnh treo, do đó số bậc tối thiểu của các đỉnh là 1, số bậc tối đa của các đỉnh là n-1 (vì là đơn đồ thị). Có n đỉnh, số bậc của các đỉnh đi từ 1 đến n-1 (n-1) giá trị. Do đó theo nguyên lý Dirichlet phải có ít nhất 02 đỉnh có cùng bậc. TH2: Giả sử đồ thị có ít nhất 01 đỉnh treo, khi đó số bậc tối thiểu của các đỉnh là 0, và số bậc tối đa chỉ là n-2 (vì là đơn đồ thị, đồng thời có đỉnh treo). Có n đỉnh, số bậc của các đỉnh chỉ có thể đi từ 0 đến n-2 (n-1) giá trị. Do đó theo nguyên lý Dirichlet phải có ít nhất 02 đỉnh có cùng bậc.

Bài 15: Tính tổng số bậc của nK (đơn đồ thị đủ).

Giải

Với đồ thị đủ thì mỗi đỉnh đều nối với các đỉnh còn lại. Do vậy, khi có n đỉnh thì mỗi đỉnh đều nối với n -1 đỉnh còn lại, tức là bậc của mỗi đỉnh đều bằng n – 1. Vậy, tổng số bậc của cả đồ thị là: n*(n – 1) bậc.

II. Các bài tập trong giấy kiểm tra lần 1. Bài 16: (giống bài 12 phần trước).

Bài 17: Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

BT Toan roi rac 6

Trong tổng số 2504 sinh viên của một khoa công nghệ thông tin, có 1876 theo học môn NNLT Pascal, 999 học môn ngôn ngữ Fortran và 345 học môn ngôn ngữ C. Ngoài ra còn biết 876 sinh viên học cả Pascal và Fortran, 232 học cả Fortran và C, 290 học cả Pascal và C. Nếu 189 sinh viên học cả 03 môn Psacal, Fortran và C thì trong trường hợp đó có bao nhiêu sinh viên không học môn nào trong cả 03 môn nói trên.

Giải

Gọi P: là tập gồm các SV học Pascal F: là tập gồm các SV học Fortran C: là tập gồm các SV học C N: là tổng số SV (2504 SV) Gọi K là số SV học ít nhất 01 môn Theo nguyên lý bù trừ, ta có: KPFCPFCPFFCCPPFC==++−−−+UU I I I II 4932011250420111892902328763459991876 =−=−=⇒=+−−−++= KNKK SV Vậy có 493 SV không học môn nào trong 03 môn: Pascal, Fortran và C.

Bài 18: Hãy tìm số đỉnh, số cạnh, số bậc của mỗi đỉnh và xác định các đỉnh cô lập, đỉnh treo, ma trận liền kề, ma trận liên thuộc trong mỗi đồ thị vô hướng sau:

Giải

Câu 18.1. Số đỉnh: 8 Số cạnh: 11 Đỉnh cô lập: D Đỉnh treo: không có

Tên đỉnh a b C d e g h i Bậc của định 3 2 4 0 5 3 2 3

Câu 18.2. Số đỉnh: 5 Số cạnh: 12 Đỉnh cô lập: không có Đỉnh treo: không có

Tên đỉnh a b c d e Bậc của định 6 5 5 5 3

Giải

Dựa vào ma trận liền kề của hai đơn đồ thị ta có thể vẽ lại các đồ thị bằng hình vẽ: Theo hình vẽ của hai đơn đồ thị ta thấy chúng không có cùng số cạnh, một bên có 4 cạnh và một bên có 5 cạnh. Vậy hai đồ thị có ma trận liền kề đã cho ở trên không đẳng cấu. Bài toán này có thể không cần vẽ hình lại cũng được, từ ma trận kề ta cũng có thể dễ dàng xác định được số cạnh của mỗi đồ thị lần lượt là 4 và 5. Do vậy chúng không thể đẳng cấu.

Bài 20: Xét xem các đồ thị cho sau đây có đẳng cấu với nhau không?

Giải

a. Hình 01. Hai đồ thị cho ở trên có: số đỉnh, số cạnh, tổng số bậc và số bậc của mỗi đỉnh bằng nhau. Đặc biệt, các đỉnh của đồ thị thứ nhất và thứ hai khi sắp theo thứ tự sau đây thì chúng hoàn toàn tương đương về mọi mặt:

Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

BT Toan roi rac 9Số bậc của mỗi đỉnh 3 4 4 3 5 5

Chính vì vậy, hai đồ thị trên là đẳng cấu. b. Hình 02. Hai đồ thị có hướng cho ở trên khi sắp theo thứ tự sau đây về các đỉnh thì chúng tương đương về tất cả các mặt: từ số đỉnh, tổng số bậc, bậc vào, bậc ra của mỗi đỉnh, tổng số cạnh, thứ tự và chiều của các cạnh đều tương ứng:

Vì vậy, hai đồ thị có hướng ở trên là đẳng cấu với nhau.

Bài 21: (3.1) Cho G là đồ thị có v đỉnh và e cạnh, còn m và M tương ứng là bậc nhỏ nhất và lớn nhất các đỉnh của G. Chứng tỏ rằng: 2emMv≤≤

Giải

Vì m và M tương ứng là bậc nhỏ nhất và lớn nhất các đỉnh của G, do đó ta dễ dàng có được:

Bài 22: (3.2) Chứng minh rằng nếu G là đơn đồ thị phân đôi có v đỉnh và e cạnh, khi đó chứng minh bất đẳng thức sau đây: 2(1)4ve ≤Giải

Bài 24: (3.6) Tìm ma trận liền kề cho các đồ thị sau:

Hai đồ thị với ma trận liền kề ở trên không thể đẳng cấu với nhau vì: chúng có số cạnh khác nhau: đồ thị thứ nhất có 4 cạnh, đồ thị thứ hai có 5 cạnh.

Bài 26: (3.9)

Thưa thầy, theo em nghĩ thì đây là hai ma trận liên thuộc chứ không phải là hai ma trận liền kề. Và nếu là hai ma trận liên thuộc thì chúng đẳng cấu với nhau vì: Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

Giải

Bài này hoàn toàn giống bài số 20 đã giải ở trên.

Bài 28: (3.11) Cho V = {2, 3, 4, 5, 6, 7, 8} và E là tập hợp các cặp phần tử (u, v) của V sao cho u < v và u với v là các số nguyên tố cùng nhau. Hãy vẽ đồ thị có hướng (),GVE= . Tìm số đường đi phân biệt độ dài 3 từ đỉnh 2 tới đỉnh 8. Giải 72438Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

BT Toan roi rac 13 Bài 29: (3.12)

Hãy tìm số đường đi độ dài n giữa hai đỉnh liền kề (t.ư không liền kề) tùy ý trong K3,3 với mỗi giá trị của n sau: a. n = 2, b. n = 3, c. n = 4, d. n = 5.

Giải

Hai đỉnh liền kề phải ở 2 phần khác nhau. Một cạnh chỉ có thể nối từ 1 đỉnh ở phần (I) đến 1 đỉnh ở phần (II) và ngược lại. Gọi m là số đường đi giữa 2 đỉnh bất kỳ trong K3,3 có độ dài n. TH1: n chẵn. Nếu n chẵn thì đỉnh đầu và đỉnh cuối của đường đi phải ở cùng 1 phần, do vậy chúng không thể liền kề. TH2: n lẻ.

Nếu n lẻ thì đỉnh đầu và đỉnh cuối của đường đi phải ở trên 2 phần khác nhau, do vậy chúng phải liền kề (vì đây là K3,3). Mặc khác mỗi một đỉnh ở phần này luôn có 3 phương án để đi qua 1 đỉnh ở phần kia. Do vậy ta có được các kết luận sau đây: o Hai đỉnh liền kề, n chẵn: m = 0, o Hai đỉnh liền kề, n lẻ: m = 3n-1, o Hai đỉnh không liền kề, n chẵn: m = 3n-1, o Hai đỉnh không liền kề, n lẽ: m = 0.

Áp dụng cho các trường hợp:

BT Toan roi rac 14Bài tập chương III

Câu 1: Cho G là đồ thị có v đỉnh và e cạnh, còn M, m tương ứng là bậc lớn nhất và nhỏ nhất của các đỉnh của G. Chứng tỏ rằng: m ≤ ve2 ≤ M. Câu 2: Chứng minh rằng nếu G là đơn đồ thị phân đôi có v đỉnh và e cạnh, khi đó e ≤ v2/4.

BT Toan roi rac 15Câu 10: Các đồ thị G và G’ sau có đẳng cấu với nhau không? a) b) Câu 11: Cho V={2,3,4,5,6,7,8} và E là tập hợp các cặp phần tử (u,v) của V sao cho u<v và u,v nguyên tố cùng nhau. Hãy vẽ đồ thị có hướng G=(V,E). Tìm số các đường đi phân biệt độ dài 3 từ đỉnh 2 tới đỉnh 8.

Câu 12: Hãy tìm số đường đi độ dài n giữa hai đỉnh liền kề (t.ư. không liền kề) tùy ý trong K3,3 với mỗi giá trị của n sau: a) n=2, b) n=3, c) n=4, d) n=5. u1

Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

BT Toan roi rac 16Câu 1:

Vì m và M tương ứng là bậc nhỏ nhất và lớn nhất các đỉnh của G, do đó ta dễ dàng có được: deg() , i=1,vimvM≤≤ ⇔

Khi đó, số cạnh nhiều nhất sẽ là:12 12 (2)ddd edd=× ⇔≤ Ta dễ dàng có được: 22 22 212 1 122 1 122 12()0 2 0 2 4dd d ddd d ddd dd− ≥⇔− +≥⇔+ +≥

Câu 4:

Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

BT Toan roi rac 20Câu 8: Dựa vào ma trận liền kề của hai đơn đồ thị ta có thể vẽ lại các đồ thị bằng hình vẽ: Dựa vào hình vẽ của hai đơn đồ thị ta thấy hai đơn đồ thị không có cùng số cạnh, một bên có 4 cạnh và một bên có 5 cạnh. Vậy hai đơn đồ thị có ma trận liền kề đã cho không đẳng cấu.

Câu 9: Theo em dề ra là hai ma trận liên thuộc Dựa vào hai ma trận liên thuộc ta có thể vẽ lại đồ thị của hai ma trận như sau:

Hai đồ thị có các cạnh tương ứng là:

Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

b/ Hai đồ thị có hướng G1, G2 cho ở trên khi sắp lại thứ tự về các đỉnh thì chúng tương đương về tất cả các mặt: từ số đỉnh, tổng số bậc, bậc vào, bậc ra của mỗi đỉnh, tổng số cạnh, thứ tự và chiều đi và đến của các cạnh đều tương ứng với nhau:

Bậc vào: 1 2 1 2 2 1 Bậc ra: 2 1 2 1 1 2

Vì vậy, hai đồ thị G1,G2 có hướng cho ở trên là đẳng cấu với nhau. Câu 12: Hai đỉnh liền kề phải ở 2 phần khác nhau cảu đồ thị. Một cạnh chỉ có thể nối từ 1 đỉnh ở phần (I) đến 1 đỉnh ở phần (II) và ngược lại. Gọi b là số đường đi giữa 2 đỉnh bất kỳ trong K3,3 có độ dài n. TH1: n chẵn. Nếu n chẵn thì đỉnh đầu và đỉnh cuối của đường đi phải ở cùng 1 phần, do vậy chúng không thể liền kề. TH2: n lẻ. Nếu n lẻ thì đỉnh đầu và đỉnh cuối của đường đi phải ở trên 2 phần khác nhau, do vậy chúng phải liền kề (vì đây là K3,3). Mặc khác mỗi một đỉnh ở phần này luôn có 3 đường đi để đi qua 1 đỉnh ở phần kia. Do vậy ta có được các kết quả sau đây rút ra từ suy luận trên: o Hai đỉnh liền kề, n chẵn: b = 0, o Hai đỉnh liền kề, n lẻ: b = 3n-1, (II) (I) 1 43 2 56Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

BT Toan roi rac 22o Hai đỉnh không liền kề, n chẵn: b = 3n-1, o Hai đỉnh không liền kề, n lẽ: b = 0. Áp dụng cho các trường hợp:

Số cạnh n = 2 n = 3 n = 4 n = 5 Liền kề 0 9 0 81 Không liền kề 3 0 27 0

BÀI TẬP CHƯƠNG 4 ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON Bài 1: Với giá trị nào của n thì các đồ thị sau đây là đồ thị Euler? a. Kn b. Cn c. Wn d. QnGiải:

Bài 2:

Với các giá trị nào của m và n thì đồ thị phân đôi đầy đủ Km,n có: a. Chu trình Euler. b. Đường đi Euler.

Giải

a. Vì các đỉnh của đồ thị phân đôi đủ Km,n có bậc là m hoặc n. Do vậy, để nó là đồ thị Euler thì m và n đều phải là một số chẵn. b. Để một đồ thị có đường đi Euler thì phải có đúng 2 đỉnh bậc lẻ, các đỉnh còn lại phải là bậc chẵn. Vậy một trong 2 giá trị m, n phải là 2, giá trị còn lại phải là số lẻ. Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

BT Toan roi rac 23Bài 3: Với giá trị nào của m và n thì đồ thị phân đôi đầy đủ Km,n có chu trình Hamilton.

Giải

Theo định lý Dirac, nếu G là đơn đồ thị có n đỉnh và mọi đỉnh của G đều có bậc không nhỏ hơn 2n thì G là một đồ thị Hamilton. Với Km,n các đỉnh có bậc m hoặc n, nên để đồ thị đầy đủ Km,n là đồ thị Hamilton thì phải có điều kiện sau:

Câu 4: Chứng minh rằng đồ thị lập phương Qn là một đồ thị Hamilton. Vẽ cây liệt kê tất cả các chu trình Hamilton của đồ thị lập phương Q3.

Câu 5: Trong một cuộc họp có 15 người mỗi ngày ngồi với nhau quanh một bàn tròn một lần. Hỏi có bao nhiêu cách sắp xếp sao cho mỗi lần ngồi họp, mỗi người có hai người bên cạnh là bạn mới, và sắp xếp như thế nào ?

Câu 6: Hiệu trưởng mời 2n (n ≥ 2) sinh viên giỏi đến dự tiệc. Mỗi sinh viên giỏi quen ít nhất n sinh viên giỏi khác đến dự tiệc. Chứng minh rằng luôn luôn có thể xếp tất cả các sinh viên giỏi ngồi xung quanh một bàn tròn, để mỗi người ngồi giữa hai người mà sinh viên đó quen. Giải Giả sử có đồ thị G = (V, E) mà trong đó ta có: V là tập hợp các sinh viên được mời dự tiệc, E = (u,v) với u, v thuộc V và u, v có quan hệ là quen biết nhau (theo giả thiết của đề bài). Như vậy theo giả thiết của bài toán ta sẽ xác lập được một đồ thị là một đơn đồ thị có 2n đỉnh, mỗi đỉnh có bậc tối thiểu là n (vì theo đề bài cho: mỗi sinh viên quen biết với ít nhất là n sinh viên khác).Cho nên ta có: số bậc của mỗi đỉnh 2

Do đó, theo định lý Dirac thì G là đồ thị Hamilton. Mặc khác, đây là đồ thị vô hướng Vậy theo các lập luận trên thì luôn luôn có thể xếp tất cả các sinh viên giỏi ngồi xung quanh một bàn tròn, để mỗi người ngồi giữa hai người mà sinh viên đó quen. (đpcm) Câu 7: Một ông vua đã xây dựng một lâu đài để cất báu vật. Người ta tìm thấy sơ đồ của lâu đài (hình sau) với lời dặn: muốn tìm báu vật, chỉ cần từ một trong các phòng bên ngoài cùng (số 1, 2, 6, 10, ), đi qua tất cả các cửa phòng, mỗi cửa chỉ một lần; báu vật được giấu sau cửa cuối cùng. Hãy tìm nơi giấu báu vật? 21 3 4 567Links downloaded from ToanDHSP.COMBai tap toan roi rac co giai

Câu 9: Giải bài toán người phát thư Trung Hoa với đồ thị cho trong hình sau:

Đồ thị G có đường đi Hamilton từ s tới r nhưng không có chu trình Hamilton thì ta cần tìm một đường đi từ s tới r qua tất cả các đỉnh còn lại nhưng không trở về đỉnh xuất phát . Đường đi Hamilton là : s Æ a Æ b Æ c Æ e Æ f Æ g Æ d Æ h Æ r Từ đồ thị ta nhận thấy sẽ không có bất kỳ chu trình Hamilton nào xuất phát từ s và lại trở về s. Câu 11: Cho thí dụ về: a) Đồ thị có một chu trình vừa là chu trình Euler vừa là chu trình Hamilton; b) Đồ thị có một chu trình Euler và một chu trình Hamilton, nhưng hai chu trình đó không trùng nhau; c) Đồ thị có 6 đỉnh, là đồ thị Hamilton, nhưng không phải là đồ thị Euler; d) Đồ thị có 6 đỉnh, là đồ thị Euler, nhưng không phải là đồ thị Hamilton. Giải a) b) acbsrfedgh13 2 1 2 34 65

Đề Thi Trắc Nghiệm Toán Rời Rạc Có Lời Giải / 2023

Đề Thi Trắc Nghiệm Toán Rời Rạc Có Lời Giải, Đề Thi Trắc Nghiệm Giải Phẫu 1, Giải Bài Tập Trắc Nghiệm Mai Lan Hương Lớp 7, Trắc Nghiệm Giải Phẫu, Trắc Nghiệm Giải Phẩu Hệ Tim, Trắc Nghiệm Giải Phẫu Bệnh, Trắc Nghiệm Giải Phẫu Hệ Tim Mạch, Trắc Nghiệm Giải Phẫu Hệ Mạch, Giải Bài Tập Trắc Nghiệm Tiếng Anh 7 Mai Lan Hương, Đề Thi Trắc Nghiệm Giải Phẫu Bệnh, Trắc Nghiệm Giải Phẫu Bệnh Yds, Đề Thi Trắc Nghiệm Công Nghệ Chế Tạo Máy Có Lời Giải, Trắc Nghiệm Thi Giải Quyết Tranh Chấp, Đề Thi Trắc Nghiệm Toán Lớp 3, Câu Hỏi Trắc Nghiệm Toán 6 Số Học Kì 2, Trắc Nghiệm Toán 3, Bài Tập Trắc Nghiệm Toán ôn Thi Đại Học, Đề Trắc Nghiệm Toán 10, Đề Thi Trắc Nghiệm Toán Lớp 3 Học Kỳ 2, Đề Trắc Nghiệm Toán 11, Đề Trắc Nghiệm Toán 12, Đề Thi Trắc Nghiệm Học Kì 2 Toán 10, Đề Thi Trắc Nghiệm Toán Lớp 2, Câu Hỏi Trắc Nghiệm Toán 6, Đề Thi Trắc Nghiệm Toán 10 Học Kì 2, Trắc Nghiệm Kế Toán, Đề Thi Trắc Nghiệm Vào 10 Môn Toán, Bài Thi Trắc Nghiệm Toán Lớp 5, Câu Hỏi Trắc Nghiệm Toán 6 Học Kì 2, Câu Hỏi Trắc Nghiệm Toán 7 Học Kì 2, Đề Thi Trắc Nghiệm Vào Lớp 10 Môn Toán, Đề Thi Trắc Nghiệm Môn Toán 3, Bài Thi Trắc Nghiệm Toán Lớp 1, Bài Thi Trắc Nghiệm Toán Lớp 2, Toán Lớp 6 Trắc Nghiệm, Đề Thi Trắc Nghiệm Toán Rời Rạc, Trắc Nghiệm Toán 9, Trắc Nghiệm 11 Toán, Đề Thi Trắc Nghiệm Kế Toán Kho Bạc, Bài Thi Trắc Nghiệm Môn Toán Lớp 1, Đề Thi Trắc Nghiệm Môn Toán Lớp 5, Đề Thi Trắc Nghiệm Học Kì 2 Toán 11, Trắc Nghiệm Toán 8, Đề Thi Trắc Nghiệm Môn Toán Lớp 3, Trắc Nghiệm Toán 12, Bài Thi Trắc Nghiệm Toán Lớp 3, Trắc Nghiệm Toán 4, Trắc Nghiệm Toán 5, Trắc Nghiệm Toán 6, Trắc Nghiệm Toán 6 Học Kì 2, Trắc Nghiệm Toán 7, Đề Thi Trắc Nghiệm Toán 9, Đề Thi Trắc Nghiệm Môn Toán Lớp 9, Đề Thi Trắc Nghiệm Môn Toán 4, Đề Thi Trắc Nghiệm Toán 8 Học Kì 2, Đề Thi Trắc Nghiệm Toán 4, Đề Thi Trắc Nghiệm Toán 6, Đề Thi Trắc Nghiệm Toán 6 Học Kì 2, Đề Thi Trắc Nghiệm Học Kì 1 Toán 10, Đề Thi Trắc Nghiệm Toán Lớp 5, Đề Thi Trắc Nghiệm Toán 9 Học Kì 2, Đề Thi Trắc Nghiệm Toán Lớp 5 Có Đáp án, Đề Thi Trắc Nghiệm Toán Lớp 1, Đề Thi Trắc Nghiệm Toán 9 Học Kì 1, Đề Thi Trắc Nghiệm Toán 8, Đề Thi Trắc Nghiệm Toán Lớp 6 Học Kì 1, Đề Thi Trắc Nghiệm Toán 7 Học Kì 1, Đề Thi Trắc Nghiệm Toán Lớp 4, Đề Thi Trắc Nghiệm Toán Lớp 7 Học Kì 2, Trắc Nghiệm Toán 1 Tập 1, Đề Thi Trắc Nghiệm Toán 5, Đề Thi Trắc Nghiệm Toán 7 Hk2, Đề Thi Trắc Nghiệm Toán 7, Đề Thi Trắc Nghiệm Toán 8 Học Kì 1, Đề Thi Trắc Nghiệm Toán Lớp 4 Học Kỳ 1, Đề Thi Trắc Nghiệm Học Kì 1 Toán 11, Trắc Nghiệm Giải Phẫu Bệnh Tuyến Giáp , Đề Thi Trắc Nghiệm Kế Toán Tài Chính, Đáp án 1500 Câu Trắc Nghiệm Toán 11, Trắc Nghiệm An Toàn Điện, Trắc Nghiệm Kế Toán Tài Chính 3, Đề Thi Trắc Nghiệm Toán Lớp 5 Violet, Trắc Nghiệm Tổng Hợp Toán 11, Đề Thi Trắc Nghiệm Kế Toán Tài Chính 1, Trắc Nghiệm Lý Thuyết Toán, Trắc Nghiệm Toán 11 Chương 3 Đại Số, Bài Thi Trắc Nghiệm An Toàn Điện, Đề Thi Trắc Nghiệm An Toàn Bảo Mật Thông Tin Có Đáp An, Đề Thi Trắc Nghiệm An Toàn Điện, Trắc Nghiệm Toán Hình, Trắc Nghiệm Toán Hình 10 Có Đáp án, Trắc Nghiệm Toán Thpt, Trắc Nghiệm An Toàn Điện Có Đáp án, Đề Kiểm Tra Trắc Nghiệm Môn Toán Lớp 6, Trắc Nghiệm Toán 6 Hay Nhất, Đề Thi Trắc Nghiệm Nguyên Lý Kế Toán, Đề Thi Trắc Nghiệm Môn Kiểm Toán Ueh, Trắc Nghiệm An Toàn Bảo Mật Thông Tin, Trắc Nghiệm Online Toán 12, Câu Hỏi Trắc Nghiệm Nguyên Lý Kế Toán,

Đề Thi Trắc Nghiệm Toán Rời Rạc Có Lời Giải, Đề Thi Trắc Nghiệm Giải Phẫu 1, Giải Bài Tập Trắc Nghiệm Mai Lan Hương Lớp 7, Trắc Nghiệm Giải Phẫu, Trắc Nghiệm Giải Phẩu Hệ Tim, Trắc Nghiệm Giải Phẫu Bệnh, Trắc Nghiệm Giải Phẫu Hệ Tim Mạch, Trắc Nghiệm Giải Phẫu Hệ Mạch, Giải Bài Tập Trắc Nghiệm Tiếng Anh 7 Mai Lan Hương, Đề Thi Trắc Nghiệm Giải Phẫu Bệnh, Trắc Nghiệm Giải Phẫu Bệnh Yds, Đề Thi Trắc Nghiệm Công Nghệ Chế Tạo Máy Có Lời Giải, Trắc Nghiệm Thi Giải Quyết Tranh Chấp, Đề Thi Trắc Nghiệm Toán Lớp 3, Câu Hỏi Trắc Nghiệm Toán 6 Số Học Kì 2, Trắc Nghiệm Toán 3, Bài Tập Trắc Nghiệm Toán ôn Thi Đại Học, Đề Trắc Nghiệm Toán 10, Đề Thi Trắc Nghiệm Toán Lớp 3 Học Kỳ 2, Đề Trắc Nghiệm Toán 11, Đề Trắc Nghiệm Toán 12, Đề Thi Trắc Nghiệm Học Kì 2 Toán 10, Đề Thi Trắc Nghiệm Toán Lớp 2, Câu Hỏi Trắc Nghiệm Toán 6, Đề Thi Trắc Nghiệm Toán 10 Học Kì 2, Trắc Nghiệm Kế Toán, Đề Thi Trắc Nghiệm Vào 10 Môn Toán, Bài Thi Trắc Nghiệm Toán Lớp 5, Câu Hỏi Trắc Nghiệm Toán 6 Học Kì 2, Câu Hỏi Trắc Nghiệm Toán 7 Học Kì 2, Đề Thi Trắc Nghiệm Vào Lớp 10 Môn Toán, Đề Thi Trắc Nghiệm Môn Toán 3, Bài Thi Trắc Nghiệm Toán Lớp 1, Bài Thi Trắc Nghiệm Toán Lớp 2, Toán Lớp 6 Trắc Nghiệm, Đề Thi Trắc Nghiệm Toán Rời Rạc, Trắc Nghiệm Toán 9, Trắc Nghiệm 11 Toán, Đề Thi Trắc Nghiệm Kế Toán Kho Bạc, Bài Thi Trắc Nghiệm Môn Toán Lớp 1, Đề Thi Trắc Nghiệm Môn Toán Lớp 5, Đề Thi Trắc Nghiệm Học Kì 2 Toán 11, Trắc Nghiệm Toán 8, Đề Thi Trắc Nghiệm Môn Toán Lớp 3, Trắc Nghiệm Toán 12, Bài Thi Trắc Nghiệm Toán Lớp 3, Trắc Nghiệm Toán 4, Trắc Nghiệm Toán 5, Trắc Nghiệm Toán 6, Trắc Nghiệm Toán 6 Học Kì 2,

400 Câu Trắc Nghiệm Toán Rời Rạc Có Đáp Án / 2023

ĐÊ CƢƠNG ÔN TẬP MÔN TOÁN RỜI RẠC

1 2 3 4 5

6

7

8 9 10 11 12 13 14 15

16

17

18

C. {(1,2), (2,2), (3,a)} Xác định tập lũy thừa của tập A={ôtô, Lan} D. {{ôtô}, {Lan},  , {ôtô, Lan}}

19

Xác định tích đề các của 2 tập A={1,a} và B={1,b}: B.{(1,1), (1,b), (a,1), (a,b)}

20 21

22

23 24

25

26

27

28

29 30 31 32 33

34

35

36

37

38

39

40

41

42

Cho tập A={1,2,4,5,7,9}, tập B={2,4,6,8,10}. Tập A-B là: 3

B. 20 C. 30

44

45

B.100 C.50 D.0

46

Cho biết số phần tử của A  B  C nếu mỗi tập có 200 phần tử và nếu có 100 phần tử chung của mỗi cặp 2 tập và có 50 phần tử chung của cả 3 tập. A.100 B.200 C.250 D.350

47

Cho X={1, 2, 3, 4, 5, 6, 7, 8, 9} A = {3, 4, 6}, B={1, 2, 5, 8}, C={5, 6, 7, 8} Tìm xâu bit biểu diễn tập: (A C)  B A.010010010 B.000010010 C.000011000 D.111100000

48

Cho X={1,2,3,4,5,6,7,8,9}, A={2, 5, 6, 7, 8} Tìm xâu bit biểu diễn tập ̅ A.010011110 B.000111101 4

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

D.1022 Số hàm từ tập A có k phần tử vào tập B có n phần tử là: chúng tôi B.(n-k)! chúng tôi D.(n!/k!) Có bao nhiêu xâu nhị phân độ dài là 8 hoặc bắt đầu bởi 00 hoặc kết thúc bởi 11 A.112 B.128 C.64 D.124 Có bao nhiêu xâu nhị phân độ dài bằng 8 và không chứa 6 số 0 liên tiếp A.246 B.248 C.256 D.254 Có bao nhiêu xâu nhị phân độ dài bằng 8 bắt đầu bởi 00 và kết thúc bởi 11 A.64 B.16 C.32 D.128 Một sinh viên phải trả lời 8 trong số 10 câu hỏi cho một kỳ thi. Sinh viên này có bao nhiêu sự lựa chọn nếu sinh viên phải trả lời ít nhất 4 trong 5 câu hỏi đầu tiên? A.35 B.75 C.25 D.20 Cho tập A = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19} hỏi ta cần lấy ít nhất bao nhiêu phần tử từ tập A để chắc chắn rằng có một cặp có tổng bằng 20. A. 6 B. 7 C. 8 D. 9 Có 12 sinh viên trong một lớp học. Có bao nhiêu cách để 12 sinh viên làm 3 đề kiểm tra khác nhau nếu mỗi đề có 4 sinh viên làm. A.220 B.3465 C.34650 D.650 Một dãy XXXYYY độ dài 6. X có thể gán bởi một chữ cái. Y có thể gán một chữ số. Có bao nhiêu dãy được thành lập theo cách trên A.108 B.1000000 C.17576 D.17576000 Một phiếu trắc nghiệm đa lựa chọn gồm 10 câu hỏi. Mỗi câu có 4 phương án trả lời. Có bao nhiêu cách điền một phiếu trắc nghiệm nếu câu hỏi có thể bỏ trống. 6

67

68

69

70

71

72

73

74

A.410 B.510 C.40 D.50 Kết quả của một cuộc điều tra ở Hà Nội cho thấy 96% các gia đình có máy thu hình, 98% có điện thoại và 95% có điện thoại và máy thu hình. Tính tỷ lệ % các gia đình ở Hà Nội không có thiết bị nào? A.4% B.5% C.1% D.2% Trong lớp CNTT có 50 sinh viên học tiếng Anh; 20 sinh viên học tiếng Pháp và 10 sinh viên học cả Anh và Pháp. Cho biết sĩ số của lớp là 80. Hỏi có bao nhiêu sinh viên không học tiếng Anh, Pháp. A.0 B.5 C.10 D. 20 Cho tập A gồm 10 phần tử. Số tập con của tập A là A.10 B.100 C.1024 D. 1000 Mỗi người sử dụng thẻ ATM đều có mật khẩu dài 4 hoặc 6 ký tự. Trong đó mỗi ký tự là một chữ số. Hỏi có bao nhiêu mật khẩu? A.10000 B.1010000 C.410+610 D. 1110000 Có bao nhiêu số nguyên dương không lớn hơn 1000 chia hết cho 7 hoặc 11? A. 220 B. 200 C. 142 D. 232 Có bao nhiêu số nguyên dương không lớn hơn 1000 không chia hết cho 7 hoặc 11. A. 220 B. 780 C. 768 D. 1768 Có 8 đội bóng thi đấu vòng tròn. Hỏi phải tổ chức bao nhiêu trận đấu? A. 64 B. 56 C. 28 D. 32 Một tập hợp 100 phần tử có bao nhiêu tập con có ít hơn ba phần tử? A. 2100 7

75

76

77

78

79

80

B. 5050 C. 297 D. 5051 Một tập hợp 100 phần tử có bao nhiêu tập con có 2 phần tử ? A. 298 B. 4950 C. 50 D. 9900 Có 20 vé số khác nhau trong đó có 3 vé chứa các giải Nhất, Nhì, Ba. Hỏi có bao nhiêu cách trao giải thưởng cho 20 người, mỗi người giữ một vé? A. 1140 B. 8000 C. 2280 D. 6840 Một tổ bộ môn có 10 nam và 15 nữ. Có bao nhiêu cách chọn một hội đồng gồm 6 ủy viên, trong đó số ủy viên nam gấp đôi số ủy viên nữ? A. 22050 B. 315 C. 54600 D. 575 Công thức nào sau đây đúng. Cho n là số nguyên dương, khi đó ∑ là: A. 2n-1 B. 2n C. 2n+1 D. 2n -1 Công thức nào sau đây đúng. Cho n và k là các số nguyên dương với n k. Khi đó: A. C(n+1,k) = C(n,k-1) + C(n,k) B. C(n+1,k) = C(n-1,k) + C(n-1,k-1) C. C(n+1,k) = C(n,k) + C(n-1,k) D. C(n+1,k) = C(n-1,k-1) + C(n,k-1) Công thức nào sau đây đúng. Cho x, y là 2 biến và n là một số nguyên dương. Khi đó: A. (x+y)n = ∑ B. (x+y)n = ∑ C. (x+y)n = ∑ D. (x+y)n = ∑ Hệ số của x12y13 trong khai triển (x+y)25 là: A. 25!

81

82

Cho n, r là các số nguyên không âm sao cho r 83

84

85

86

87

88

89

90

A.C(n, r)=C(n+r-1, r) B.C(n, r)=C(n, r-1) C.C(n, r)=C(n, n-r) D.C(n, r)=C(n-r, r) Trong khai triển (x+y)200 có bao nhiêu số hạng? A.100 B. 101 C.200 D.201 Tìm hệ số của x9 trong khai triển của (2-x)20 A. C(20,10).210 B. C(20,9).211 C. –C(20,9)211 D. – C(20,10)29 Có bao nhiêu cách tuyển 5 trong số 10 cầu thủ của một đội quần vợt để đi thi đấu tại một trường khác? A. 252 B. 250 C 120 D. 30240 Có bao nhiêu khả năng có thể xảy ra đối với các vị trí thứ nhất, thứ nhì và thứ ba trong cuộc đua có 12 con ngựa, nếu mọi thứ tự tới đích đều có thể xảy ra? A. 220 B. 1320 C 123 D. 312 Có bao nhiêu số tự nhiên có 3 chữ số khác nhau được tạo từ tập các chữ số{1,3,5,7,9} A. 30 B. 60 C 90 D. 120 Có bao nhiêu số tự nhiên có 3 chữ số được tạo từ tập các chữ số {1,3,5,7,9} A. 125 B. 60 C. 65 D. 120 Có bao nhiêu số lẻ có 3 chữ số được tạo từ tập các chữ số {0,1,2,3,4,5} A. 48 B. 60 C.90 D. 75 Trong một khoa có 20 sinh viên xuất sắc về Toán và 12 sinh viên xuất sắc về CNTT. Hỏi có bao nhiêu cách lựa chọn hai đại diện sao cho một là sinh viên Toán, một là sinh viên CNTT? A. 20 9

91

92

93

94

95

96

97

98

B. 12 C 32 D. 240 Có bao nhiêu xâu nhị phân có độ dài bằng 5 mà hoặc có 2 bít đầu tiên là 0 hoặc có 2 bít cuối cùng là 1? A.16 B. 14 C. 2 D.32 Mỗi thành viên trong câu lạc bộ Toán tin có quê ở 1 trong 20 tỉnh thành. Hỏi cần phải tuyển bao nhiêu thành viên để đảm bảo có ít nhất 5 người cùng quê? A. 81 B. 99 C. 101 D. 90 Số xâu nhị phân độ dài 4 có bít cuối cùng bằng 1 là: A. 8 B. 12 C. 16 D. 18 Một phiếu trắc nghiệm đa lựa chọn gồm 10 câu hỏi. Mỗi câu có 4 phương án trả lời. Có bao nhiêu cách điền một phiếu trắc nghiệm nếu mọi câu hỏi đều được trả lời. A.410 B.104 C.40 D.210 Có bao nhiêu hàm số khác nhau từ tập có 4 phần tử đến tập có 3 phần tử: A. 81 B. 64 C. 4 D. 12 Số các xâu nhị phân có độ dài là 8 là: A.1024 B.256 C.16 D.8 Số các xâu nhị phân có độ dài nhỏ hơn hoặc bằng 8 là: A.1024 B. 512 C. 510 D.1022 Số hàm từ tập A có 5 phần tử vào tập B có 4 phần tử là: A.1024 B. 625 C. 5 10

99

100

101

102

103

104

105

106

D. 20 Có bao nhiêu xâu nhị phân độ dài là 10 bắt đầu bởi 00 A.112 B.128 C.64 D.256 Có bao nhiêu xâu nhị phân độ dài bằng 6 và chứa 4 số 0 liên tiếp A. 4 B. 8 C. 10 D. 12 Có bao nhiêu xâu nhị phân độ dài bằng 10 bắt đầu bởi 11 và kết thúc bởi 00 A.64 B.128 C.256 D.1024 Một sinh viên phải trả lời 20 câu hỏi cho một kỳ thi, mỗi câu hỏi có 4 phương án trả lời. Biết rằng sinh viên bắt buộc phải lựa chọn phương án nào đó cho 10 câu hỏi đầu tiên, còn 10 câu hỏi sau câu trả lời có thể bỏ trống. Hỏi sinh viên này có bao nhiêu sự lựa chọn? A. 430 B.410+510 C. 2010 D. 304 + 1 Trong 100 người có ít nhất mấy người cùng tháng sinh? A. 10 B. 9 C. 8 D. 7 Cần phải có tối thiểu bao nhiêu sinh viên ghi tên vào lớp Toán rời rạc để chắc chắn sẽ có ít nhất 6 sinh viên đạt cùng một điểm thi nếu thang điểm gồm 5 bậc? A.30 B. 25 C. 26 D. 27 Một dãy XXYYY độ dài 4. X có thể gán bởi một chữ số. Y có thể gán một chữ cái. Có bao nhiêu dãy được thành lập theo cách trên A.102 x 263 B. 102+263 C. 103 x 262 D. 103 + 262 Mỗi sinh viên trong lớp K38CNTT của khoa Công nghệ đều có quê ở một trong 61 tỉnh thành trong cả nước. Cần phải tuyển bao nhiêu sinh viên để đảm bảo trong lớp K38CNTT có ít nhất 2 sinh viên cùng quê? A. 62 B. 122 11

107

108

109

110

111

C. 123 D. 61 Cần phải tung một con xúc xắc bao nhiêu lần để có một mặt xuất hiện ít nhất 3 lần? A.12 B.13 C.18 D.19 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? A. 365 B. 366 C. 367 D. 368 Trong lớp CNTT có 45 sinh viên học tiếng Anh; 25 sinh viên học tiếng Pháp và 5 sinh viên không học môn nào. Cho biết sĩ số của lớp là 60. Hỏi có bao nhiêu sinh viên học cả tiếng Anh, Pháp. A. 5 B. 10 C. 15 D. 20 Cho tập A = {1, 2, 3, 4, 5, 6, 7, 8, 9} . . Hỏi tập A có bao nhiêu tập con? A. 10 B. 128 C. 512 D. 256 Một quan hệ hai ngôi R trên một tập hợp X (khác rỗng) được gọi là quan hệ tương đương nếu và chỉ nếu nó có 3 tính chất sau: A. Phản xạ – Đối xứng – Bắc cầu B. Phản xạ- Phản đối xứng – Bắc cầu C . Đối xứng – Phản đối xứng – Bắc cầu D. Phản xạ – Đối xứng – Phản đối xứng.

Một quan hệ hai ngôi R trên một tập hợp X (khác rỗng) được gọi là quan hệ thứ tự nếu và chỉ nếu nó có 3 tính chất sau: A. Phản xạ – Đối xứng – Bắc cầu 112 B. Phản xạ- Phản đối xứng – Bắc cầu C . Đối xứng – Phản đối xứng – Bắc cầu D. Phản xạ – Đối xứng – Phản đối xứng. Cho biết quan hệ nào là quan hệ tương đương trên tập {0, 1, 2, 3}: A. {(0,0),(1,1),(2,2),(3,3),(0,1),(0,2),(0,3)} 113 B. {(0,0),(1,1),(2,2),(3,3),(0,1),(1,0)} C .{(0,0),(0,2),(2,0),(2,2),(2,3),(3,2),(3,3)} D. {(0,0),(1,1),(1,3),(2,2),(2,3),(3,1),(3,2),(3,3)} Cho A ={1, 2, 3, 4, 5}. Quan hệ R được xác định: ⇔ 114 . Quan hệ R được biểu diễn là: A. {(1,1),(2,2),(3,3),(4,4), (1,3),(3,1),(1,5),(5,1), (2,4),(4,2)} 12

]

B. [

]

C. [

]

D. [

]

115

116

117

118

119

120

Cho A={1,2,3,4,5}. Trên A xác định quan hệ R như sau: ⇔ . Quan hệ R được biểu diễn là: A. {(1,2),(1,4),(2,3),(2,5)} B. {(1,1),(2,2),(3,3),(4,4),(5,5), (1,2),(1,4),(2,3),(2,5)} C. {(1,2),(2,1),(1,4),(4,1), (2,5), (5,2)} D. {(1,2),(2,1),(1,4),(4,1), (2,5), (5,2),(3,4),(4,3),(2,3),(3,2),(4,5),(5,4)} Cho tập A ={1,2,3,4,5}. Cho A1={1}, A2={2,3}, A3={4,5}. Quan hệ tương đương R trên A sinh ra phân hoạch A1, A2, A3 là: A. {(1,1),(2,3),(4,5),(2,2),(3,3), (3,2),(4,4),(5,5),(5,4)} B. {(1,1),(2,2),(3,3),(4,4),(5,5), (1,2),(1,3),(1,4),(1,5)} C. {(1,1),(2,3),(3,2),(4,5), (5,4)} D. {(2,2),(2,3),(3,2),(3,3), (4,4), (4,5),(5,4),(5,5), (1,1),(1,2),(2,1),(1,3),(3,1)} Cho tập A ={1,2,3,4,5,6}. Cho A1={1,2}, A2={3,4}, A3={5,6}. Quan hệ tương đương R trên A sinh ra phân hoạch A1, A2, A3 là: A. {(1,1),(2,3),(4,5),(2,2),(3,3), (3,2),(4,4),(5,5),(5,4),(6,6),(5,6),(6,5)} B. {(1,1),(2,2),(3,3),(4,4),(5,5), (6,6),(1,2),(2,1),(3,4),(4,3),(5,6),(6,5)} C. {(1,1),(1,2),(2,2),(3,4), (3,3),(5,6),(4,4),(5,5),(6,6)} D. {(2,2),(2,3),(1,1),(3,3), (4,4), (3,4),(4,3),(2,1), (1,1),(1,2),(2,1),(5,6),(6,5)} Cho tập A={1,2,3,4,5} và quan hệ tương đương R trên A như sau: R={(1,1),(2,2),(3,3),(4,4),(5,5),(2,4),(4,2)}. Xác định phân hoạch do R sinh ra: A. A1={1,3,5}, A2={2,4} B. A1={1}, A2={2,4}, A3={3,5} C. A1={1}, A2={2,4}, A3={3}, A4={5} D. A1={1,2}, A2={3,4}, A3={5} Cho A ={1, 2, 3, 4, 5}. Quan hệ R được xác định: ⇔ . Xác định phân hoạch do R sinh ra: A. A1={1,3}, A2={2,4}, A3={5} B. A1={1}, A2={2,4}, A3={3}, A4={5} C. A1={1}, A2={2}, A3={3}, A4={4},A5={5} 13

D. A1={1,3,5}, A2={2,4} Cho tập A ={1,2,3,4,5}, hãy tìm ma trận biểu diễn quan hệ R trên A sau đây: R={(1,1),(2,2),(3,3),(4,4),(5,5),(1,2),(2,3),(3,2),(2,1)} A. [

]

[

]

[

]

[

]

B. 121 C.

D.

Hãy liệt kê quan hệ R trên tập hợp {1,2,3,4,5} biết ma trận biểu diễn như sau:

122

[

]

[

]

B.

16

[

]

[

]

[

]

C.

D.

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à A. 1

3

2

5

6

3

2

5

6

4

138

B. 1

4

C. 17

1

3

2

5

6

4

Nhận xét nào sau đây là SAI A. Một quan hệ có tính phản xạ khi và chỉ khi ma trận biểu diễn nó có tất cả các phần tử trên đường chéo chính đều bằng 1 B. Một quan hệ có tính đối xứng khi và chỉ khi ma trận biểu diễn nó là một ma 139 trận đối xứng qua đường chéo chính C. Một quan hệ có tính phản xạ khi và chỉ khi đồ thị biểu diễn nó tại mỗi đỉnh đều có khuyên. D. Một quan hệ có tính bắc cầu khi và chỉ khi đồ thị biểu diễn nó có cung đi từ đỉnh a đến đỉnh b thì cũng có cung đi từ đỉnh b đến đỉnh c. Cho A là một tập hữu hạn khác rỗng. Quan hệ R⊆ AxA Phát biểu nào sau đây là ĐÚNG A. Quan hệ R có tính phản xạ nếu mọi phần tử a thuộc A đều có quan hệ R với 140 chính nó. B. Quan hệ R có tính đối xứng nếu mọi a, b thuộc A thì a phải có quan hệ R với b. C. Quan hệ R có tính bắc cầu nếu mọi a, b, c thuộc A thì a phải có quan hệ R với b và b phải có quan hệ R với c Cho biết quan hệ nào là quan hệ tương đương trên tập {a, b, c, d}: A. {(a, a), (b, b), (c, c), (d, d), (a, b), (a, c), (a, d)} 141 B. {(a, a), (b, b), (c, c), (d, d), (a, b), (b, a)} C .{(a, a), (a, c), (c, a), (c, c), (c, d), (d, c), (d, d)} D. {(a, a), (b, b), (c, c), (d, d) , (c, d), (d, c), (d, a), (b, d)} Cho A ={11, 12, 13, 14, 15}. Quan hệ R được xác định: ⇔ . Quan hệ R được biểu diễn là: A. {(11, 11), (12, 12), (13, 13), (14, 14), (11, 13), (13, 11), (11, 15), (15, 11), (12, 14), (14, 12)} 142 B. {(11, 11), (12, 12), (13, 13), (14, 14), (15, 15), (11, 13), (11, 15), (13, 15), (12, 14)} C. {(11, 13), (13, 11), (11, 15), (15, 11), (13, 15), (15, 13), (12, 14), (14, 12)} D. {(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)} Cho A={11, 12, 13, 14, 15}. Trên A xác định quan hệ R như sau: ⇔ . Quan hệ R được biểu diễn là: 143

A. {(11, 12), (11, 14), (12, 13), (12, 15)} B. {(11, 11), (12, 12), (13, 13), (14,14), (15,15), (11, 12), (11, 14), (12, 13), (12, 15)} C. {(11, 12), (12, 11), (11, 14), (14, 11), (12, 15), (15, 12)} D. {(11, 12), (12, 11), (11, 14), (14, 11), (12, 15), (15, 12), (13, 14), (14, 13), (12, 18

13), (13, 12), (14, 15), (15, 14)} Cho tập A ={1, 2, 3, 4, 5, 6}. Cho A1={1}, A2={2}, A3={3, 4}, A4={5, 6}. Quan hệ tương đương R trên A sinh ra phân hoạch A1, A2, A3, A4 là: A. {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (3, 4), (4, 3), (5, 6), (6, 5)} 144 B. {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (1, 2), (2, 1), (3, 4), (4, 3)} C. {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (2, 3), (3, 2), (4, 5), (5, 4)} D. {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (4, 5), (5, 4), (1, 2), (2, 1), (1, 3), (3, 1)} Cho tập A ={1, 2, 3, 4, 5, 6}. Cho A1={1, 2, 3}, A2={4, 5}, A3={6}. Quan hệ tương đương R trên A sinh ra phân hoạch A1, A2, A3 là: A. {(1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (1,2), (2,1), (1,3), (3,1), (2,3), (3,2), (4,5), 145 (5,4)} B. {(1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (1,2), (2,1), (1,3),(3, 1),(5, 6), (6,5)} C. {(1,1), (1,2), (2,2), (3,4), (3,3), (5,6), (4,4), (5,5), (6,6)} D. {(1,1), (2,2), (3,3), (4,4), (5,5), (6, 6), (1,2), (2,1), (1,3), (3,1), (3,4), (4,3)} 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: 146 A. A1 = {1, 2, 3}, A2={4, 5, 6} B. A1 = {1, 2}, A2={3}, A3={4,5}, A4 ={6} C. A1 = {1}, A2 = {2,4}, A3 = {3}, A4={5, 6} D. A1 = {1,2}, A2={3, 4}, A3={5, 6} Cho A ={1, 2, 3, 4, 5, 6}. Quan hệ R được xác định: ⇔ . Xác định phân hoạch do R sinh ra: A. A ={1,3}, A 1 2={2,4}, A3={5} 147 B. A1={1}, A2={2,4}, A3={3}, A4={5} C. A1={1}, A2={2}, A3={3}, A4={4},A5={5} D. A1={1,3,5}, A2={2,4} Cho tập A ={1,2,3,4,5}, hãy tìm ma trận biểu diễn quan hệ R trên A sau đây: R={(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),(3,1),(3,2),(2,3)} A.

148

[

]

[

]

[

]

B.

C.

19

D. [

]

Hãy liệt kê quan hệ R trên tập hợp {1,2,3,4,5} biết ma trận biểu diễn như sau:

149

150

151

152

153

155

156

157

158

a

159

c

d

B. a

d

b

c 21

b

a

c

d

C. Cho tập A = { a, b, c, d } và quan hệ R ⊆ A x A với: R= {(a,b), (b,a), (a,c), (c,a), (a,d), (b,c), (c,d), (d, d)} Đồ thị biểu diễn quan hệ R là:

A. a

d

b

c

160 B. a

d

b

c

C. a

b

22 d

c

Giả sử P và Q là 2 mệnh đề. Tuyển của 2 mệnh đề (P v Q) là một mệnh đề… ? A. Chỉ đúng khi cả P và Q cùng đúng 161 B. Chỉ sai khi cả P và Q cùng sai C. Chỉ đúng khi P đúng Q sai D. Chỉ sai khi P đúng Q sai Hãy cho biết khẳng định nào sau đây không phải là 1 mệnh đề ? A. 2+3 B. Là 1 mệnh đề nhận chân trị đúng khi P và Q cùng đúng, sai khi P và Q cùng sai. C. Là một mệnh đề nhận chân trị đúng khi một trong hai hoặc cả 2 mệnh đề cùng đúng, nhận chân trị sai trong các trường hợp còn lại. D. Là một mệnh đề nhận chân trị đúng khi P sai hoặc cả P và Q cùng đúng. Nhận chân trị sai khi và chỉ khi P đúng Q sai. Biểu thức hằng đúng là… ? A. Biểu thức chỉ nhận chân trị đúng khi các biến mệnh đề nhận chân trị đúng. B. Biểu thức nhận chân trị đúng trong mọi trường hợp về chân trị của bộ biến 167 mệnh đề. C. Biểu thức nhận chân trị sai trong mọi trường hợp về chân trị của bộ biến mệnh đề D. Biểu thức chỉ nhận chân trị sai khi các biến mệnh đề nhận chân trị sai. Biểu thức hằng sai là… ? A. Biểu thức chỉ nhận chân trị đúng khi các biến mệnh đề nhận chân trị đúng. B. Biểu thức nhận chân trị đúng trong mọi trường hợp về chân trị của bộ biến 168 mệnh đề. C. Biểu thức nhận chân trị sai trong mọi trường hợp về chân trị của bộ biến mệnh đề D. Biểu thức chỉ nhận chân trị sai khi các biến mệnh đề nhận chân trị sai. Hai biểu thức mệnh đề E, F (có cùng bộ biến mệnh đề) được gọi là tương đương logic nếu … ? A. Nếu E có chân trị đúng thì F có chân trị sai và ngược lại. 169 B. E và F cùng có chân trị đúng. C. E và F cùng có chân trị sai. D. E và F có cùng chân trị trong mọi trường hợp về chân trị của bộ biến mệnh đề. Trong các luật sau, luật nào là luật hấp thụ ? A. p(pq)  p ; p(pq)p 170 B. p11 ; p00 C. p0p ; p1p D. ppp ; ppp Trong các luật sau, luật nào là luật thống trị? A. p(pq)  p ; p(pq)p 171 B. p11 ; p00 C. p0p ; p1p D. ppp ; ppp Trong các luật sau, luật nào là luật luỹ đẳng? A. p(pq)  p ; p(pq)p 172 B. p11 ; p00 C. p0p ; p1p D. ppp ; ppp 173 Trong các luật sau, luật nào là luật về phần tử trung hoà ? 24

A. p(pq)  p ; p(pq)p B. p11 ; p00 C. p0p ; p1p D. ppp ; ppp Luật P→Q tương đương với luật nào sau đây ?   Q 174

B.

Q

C. P D. P Luật nào trong các luật sau là luật phân bố (phân phối) ? A. p  (q  r)  (p  q)  (p  r); p  (q  r)  (p  q)  (p  r) B. p  (q  r)  (p  q)  r; p  (q  r)  (p  q)  r 175 C. p  (q  r)  (p  q)  (p  r); p  (q  r)  (p  q)  (p  r) D. Luật nào trong các luật sau là luật đối ngẫu (De Morgan) A. p  (q  r)  (p  q)  (p  r); p  (q  r)  (p  q)  (p  r) B. p  (q  r)  (p  q)  r; p  (q  r)  (p  q)  r 176 C. p  (q  r)  (p  q)  (p  r); p  (q  r)  (p  q)  (p  r) D. Luật nào trong các luật sau là luật kết hợp? A. p  (q  r)  (p  q)  (p  r); p  (q  r)  (p  q)  (p  r) B. p  (q  r)  (p  q)  r; p  (q  r)  (p  q)  r 177 C. p  (q  r)  (p  q)  (p  r); p  (q  r)  (p  q)  (p  r) D.

25

Luật nào sau đây là luật tương đương (kéo theo 2 chiều) ? A. p  q  (p  q)  (q  p) 178 B. p  q  (p  q)  (q  p) C. p  q  q  p D. p  q  q  p Một công thức được gọi là có dạng chuẩn tắc hội nếu …? A. Nó là hội của các biểu thức hội cơ bản 179 B. Nó là hội của các biểu thức tuyển cơ bản C. Nó là tuyển của các biểu thức hội cơ bản D. Nó là tuyển của các biểu thức tuyển cơ bản Một công thức được gọi là có dạng chuẩn tắc tuyển nếu …? A. Nó là hội của các biểu thức hội cơ bản 180 B. Nó là hội của các biểu thức tuyển cơ bản C. Nó là tuyển của các biểu thức hội cơ bản D. Nó là tuyển của các biểu thức tuyển cơ bản Giả sử p1, p2, … , pn là các biến mệnh đề. Một biểu thức logic F theo các biến mệnh đề p1, p2, … , pn được gọi là một biểu thức hội cơ bản nếu nó có dạng? 181

A.F = q1  q2  …  qn với qj = pj hoặc qj = B. F = p1  p2  …  pn C. F = p1  p2  …  pn

(j = 1, …, n)

D. F = q1  q2  …  qn với qj = pj hoặc qj = (j = 1,… ,n) Giả sử p1, p2, … , pn là các biến mệnh đề. Một biểu thức logic F theo các biến mệnh đề p1, p2, … , pn được gọi là một biểu thức tuyển cơ bản nếu nó có dạng? 182

A. F = q1  q2  …  qn với qj = pj hoặc qj = B. F = p1  p2  …  pn C. F = p1  p2  …  pn

(j = 1, … , n)

D. F = q1  q2  …  qnvới qj = pj hoặc qj = (j = 1, … , n) Biểu thức (P  Q)  (P  Q) tương đương logic với biểu thức nào sau đây? A. (P  Q)  (P  Q) 183 B. (P  Q)  ( C. (

)

) (P  Q)

D. ( ) (P  Q) Biểu thức (P  Q)  (P  Q) tương đương logic với biểu thức nào? 184

A. (P  Q)  (P  Q)

26

B. (P  Q)  (

)

C.

 (P  Q)

D.

 (P  Q)

Biểu thức (P  Q)→Q tương đương logic với biểu thức nào sau đây? A. 1 B. 0 185

C. (P  Q) D. ( 

)Q

Xác định chân trị của biểu thức ( P → Q ) Λ ( Q → R ) và (P → R) khi P = Q = 1, R=0? 186 A. 1 và 1 B. 0 và 0 C. 1 và 0 D. 0 và 1 Biết chân trị của mệnh đề P→Q là 0, thì chân trị của các mệnh đề PΛQ và Q→P tương ứng là? A. 0 và 1 187 B. 1 và 0 C. 0 và 0 D. 1 và 1 Mệnh đề P(PQ) tương đương logic với mệnh đề nào sau đây? A. PQ 188 B. Q C. PQ D. P Mệnh đề A. PQ

(PQ) tương đương logic với mệnh đề nào sau đây?

189 B. P C. P D. Mệnh đề P→Q tương đương logic với mệnh đề nào sau đây? A.

190 B. → C. PQ D. P 27

Mệnh đề nào sau đây có dạng chuẩn tắc tuyển? A. (pqr)(p r) (pr ) 191 B. (pqr)(p r) (p ) C. (pqr)(p r) (pq ) D. (pqr)(p r) (pq ) Mệnh đề nào sau đây có dạng chuẩn tắc hội? A. (pqr)(p r) (pr ) 192

B. (pqr)(p r) (p ) C. (pqr)  (p r)  (pq ) D. (pqr)(p r) (pq )

Phương pháp phản chứng là phương pháp? A. Quy bài toán ban đầu về bài toán con đơn giản hơn. B. Giả sử điều cần chứng minh là sai để từ đó suy ra mâu thuẫn. 193 C. Liệt kê tất cả các khả năng để từ đó đưa ra quyết định. D. Biểu diễn nghiệm của bài toán bằng các dữ kiện ban đầu Quy tắc suy luận nào sau đây là Modus Tollens (Phủ định)? A. (P(P→Q))→Q 194 B. ( (P→Q))→Q C. (

(P→Q))→

D. ( (P→Q))→ Quy tắc suy luận nào sau đây là Modus Ponens (khẳng định)? A. (P(P→Q))→Q 195 B. ( (P→Q))→Q C. (

(P→Q))→

D. ( (P→Q))→ Quy tắc suy luận nào sau đây là quy tắc tam đoạn luận? A. (P(P→Q))→Q 196 B. ((P→Q)(Q→R)) →(P→R) C. ((P→Q)(Q→R)) →(Q→R) D. ((P→Q)(Q→R)) →(P→R) Qui tắc suy luận nào là cơ sở của suy diễn sau: ” Nếu hôm nay trời mưa thì cô ta không đến, 197 Nếu cô ta không đến thì ngày mai cô ta đến, Vậy thì, nếu hôm nay trời mưa thì ngày mai cô ta đến.” A. Modus Ponens (Khẳng định) 28

B. Modus Tollens (Phủ định) C. Tam đoạn luận (Bắc cầu) D. Từng trường hợp Có bao nhiêu trường hợp về chân trị của bộ biến mệnh đề (q1,q2,..,qn)? A. 2n 198 B. 2n C. 2n+1 D. 2n-1 Bảng chân trị của biểu thức logic E(q1,q2,..,qn) là…? A. Bảng liệt kê tất cả các giá trị của biểu thức E theo từng trường hợp về chân trị của bộ biến mệnh đề q1,q2,..,qn. 199 B. Bảng giá trị của biểu thức E C. Bảng liệt kê các trường hợp của bộ biến mệnh đề q1,q2,..,qn. D. Bảng liệt kê các phép toán logic theo các trường hợp về chân trị của bộ biến mệnh đề. Cho mô hình suy diễn sau : Ā B ̅ C ̅

200

Công thức cơ sở của mô hình trên là : ̅ A. ((Ā B) ( ̅ C)) ̅ B. ((Ā B) ( ̅ C)) ̅ C. ((Ā B) ( ̅ C)) ̅ D. ((Ā B) ( ̅ C)) Cho mô hình suy diễn sau : A B C ̅ D

B ) Công thức cơ sở của mô hình trên là : A. ((A B) ( C) ( ̅ D)) B ) B. ((A B) ( C) ( ̅ D) B )) C. ((A B) ( C) ( ̅ D)) B ) D.. ((A B) ( C) ( ̅ D)) B ) Quy tắc (luật )suy luận nào là cơ sở của suy diễn sau : Là phi công thì phải biết lái máy bay. An là phi công nên An biết lái máy bay 202 A. Luật cộng B. Luật rút gọn C. Luật khẳng định 201

29

D. Luât phủ định Quy tắc (luật )suy luận nào là cơ sở của suy diễn sau : Nếu là sinh viên CNTT của trường DHCN Việt Hung thì phải học Toán rời rạc. An không học Toán rời rạc nên An không phải là sinh viên CNTT của trường ĐHCN Việt Hung. 203 A. Luật khẳng định B. Luật phủ định C. Luật tam đoạn luận D. Luật tam đoạn luận rời Quy tắc (luật )suy luận nào là cơ sở của suy diễn sau : Trường chất lượng cao thì có cán bộ giảng dạy giỏi. Trường có cán bộ giảng dạy giỏi thì có sinh viên giỏi. Vậy trường chất lượng cao thì có sinh viên giỏi 204 A. Luật khẳng định B. Luật phủ định C. Luật tam đoạn luận D. Luật tam đoạn luận rời Quy tắc (luật )suy luận nào là cơ sở của suy diễn sau : Được khen thưởng nếu học giỏi hoặc công tác tốt. An được khen thưởng, nhưng An không học giỏi nên An phải công tác tốt. 205 A. Luật khẳng định B. Luật phủ định C. Luật tam đoạn luận D. Luật tam đoạn luận rời Hãy cho biết quy tắc (Luật) nào là cơ sở của mô hình suy diễn sau : A

206

207

A ) A. Luật rút gọn B. Luật cộng C. Luật khẳng đinh D. Luật tam đoạn luận Hãy cho biết quy tắc (Luật) nào là cơ sở của mô hình suy diễn sau : A B A A. Luật rút gọn B. Luật cộng C. Luật khẳng định D. Luật tam đoạn luận 30

Hãy cho biết quy tắc (Luật) nào là cơ sở của mô hình suy diễn sau : A A 208

B A. Luật rút gọn B. Luật cộng C. Luật khẳng định D. Luật tam đoạn luận Hãy cho biết quy tắc (Luật) nào là cơ sở của mô hình suy diễn sau : A ̅ ̅

209

A. Luật khẳng định B. Luật phủ định C. Luật tam đoạn luận rời D. Luật tam đoạn luận (bắc cầu) Hãy cho biết quy tắc (Luật) nào là cơ sở của mô hình suy diễn sau : A ̅

210

211

A A. Luật khẳng định B. Luật phủ định C. Luật tam đoạn luận rời D. Luật tam đoạn luận (bắc cầu) Hãy cho biết quy tắc (Luật) nào là cơ sở của mô hình suy diễn sau : A B A

A. Luật khẳng định B. Luật phủ định C. Luật tam đoạn luận rời D. Luật tam đoạn luận Hãy cho biết quy tắc (Luật) nào là cơ sở của mô hình suy diễn sau : A 212 C 31

(A A. Luật khẳng định B. Luật từng trường hợp C. Luật tam đoạn luận rời D. Luật tam đoạn luận Quy tắc (luật )suy luận nào là cơ sở của suy diễn sau : Nếu An học giỏi thì An sẽ được khen thưởng. Và nếu An nhiệt tình tham gia các hoạt động Đoàn thì An cũng được khen thưởng. Vậy Nếu An học giỏi hoặc tham gia nhiệt tình các hoạt động Đoàn thì An sẽ được khen thưởng. 213 A. Luật khẳng định B. Luật phủ định C. Luật tam đoạn luận D. Luật từng trường hợp Quy tắc (luật )suy luận nào là cơ sở của suy diễn sau : Nếu An học giỏi thì An sẽ tốt nghiệp loại A. Và nếu An tốt nghiệp loại A thì An sẽ có nhiều cơ hội tìm việc làm khi ra trường. Vậy nếu An học giỏi thì An sẽ có nhiều cơ hội tìm việc làm khi ra trường. 214 A. Luật khẳng định B. Luật phủ định C. Luật tam đoạn luận D. Luật từng trường hợp Luật nào sau đây là luật kéo theo ? A. p 215 B. p C. p D. p

q̅ q̅ qp qp

q q q q

Luật nào trong các luật sau là luật giao hoán? A. p  (q  r)  (p  q)  (p  r); p  (q  r)  (p  q)  (p  r) 216 B. p  q  q  p ; p  q  q  p C. p  q  q  p; p  q  q  p D. p q  ̅  ̅ ; p  q  ̅   ̅ Luật nào trong các luật sau là luật kết hợp? A. p  (q  r)  (p  q)  (p  r); p  (q  r)  (p  q)  (p  r) 217 B. p  q  q  p ; p  q  q  p C. (p  q)  r  ( p r)  q ; ( p q)  r  p r q) D.( p q)  r  p q  r ); ( p q)  r  p q r ) 218 Luật nào trong các luật sau là luật lũy đẳng? 32

A. q  q  q ; q  q q B. q   q ; q   q C. p q  q p D. q   0 ; q    1 Luật nào trong các luật sau là luật hấp thụ? A. q  q  q ; q  q q 219 B. p q  q p C. pp  q)  p ; pp q)  p D.( p q)  r  p q  r ); ( p q)  r  p q r ) Xác định chân trị của biểu thức ( P → Q ) Λ ( Q → R ) và (P → R) khi P = Q = 0, R=1? 220 A. 1 và 1 B. 0 và 0 C. 1 và 0 D. 0 và 1 Xác định chân trị của biểu thức ( P → Q ) Λ ( Q → R ) và (P → R) khi P = R = 0, Q=1? 221 A. 1 và 1 B. 0 và 0 C. 1 và 0 D. 0 và 1 Xác định chân trị của biểu thức ( P → Q ) Q=1; R=0?

( Q → R ) và (P → R) khi P = 1,

222 A. 1 và 1 B. 0 và 0 C. 1 và 0 D. 0 và 1 Xác định chân trị của biểu thức ( X→Y ) Y=Z=1?

( Y → Z ) và (X →Z) khi X =

223 A. 1 và 1 B. 0 và 0 C. 1 và 0 D. 0 và 1 Xác định chân trị của biểu thức ( X→Y ) Y=Z=0?

( Y → Z ) và (X →Z) khi X =

224 A. 1 và 1 B. 0 và 0 C. 1 và 0 D. 0 và 1 225 Xác định chân trị của biểu thức (

X→Y ) 33

(

Y → Z ) và (X →Z) khi X =

Y=Z=0? A. 1 và 1 B. 0 và 0 C. 1 và 0 D. 0 và 1 Xác định chân trị của biểu thức (

X→Y )

(

Y → Z ) và ( X →Z) khi X =

Y=Z=1? 226 A. 1 và 1 B. 0 và 0 C. 1 và 0 D. 0 và 1 Xác định chân trị của biểu thức ( X→ Y ) v ( Y → Z ) và ( X → Z) khi X = Y=0, Z= 1? 227 A. 1 và 1 B. 0 và 0 C. 1 và 0 D. 0 và 1 Xác định chân trị của biểu thức ( X→ Y ) = Y=0, Z= 1?

( Y → Z ) và ( X → Z) khi X

228 A. 1 và 1 B. 0 và 0 C. 1 và 0 D. 0 và 1 Xác định chân trị của biểu thức ( Y=0, Z= 1?

X→Y )

229 A. 1 và 1 B. 0 và 0 C. 1 và 0 D. 0 và 1 Câu nào sau đây KHÔNG là một mệnh đề A. Hôm nay không phải Thứ hai 230 B. Lan học giỏi Tin học C. Không phải Hiếu được khen thưởng D. Thật vui vì Lan ở nhà. Câu nào sau đây KHÔNG là một mệnh đề A. Có ai ở nhà không? 231 B. Hà Nội là thủ đô của Việt Nam C. Hôm nay trời mưa D. 2+1=5 232

Câu nào sau đây KHÔNG là một mệnh đề chúng tôi là sinh viên khoa CNTT 34

(

Y → Z ) và ( X →Z) khi X =

B.An không phải học Trí tuệ nhân tạo C. X là sinh viên không phải học Trí tuệ nhân tạo D. An là sinh viên CNTT nhưng không phải học Trí tuệ nhân tạo. Câu nào sau đây là một mệnh đề A. Hãy cẩn thận! 233 B. X+Y=1 C. An hôm nay có phải đi học không? D. An là học sinh giỏi. Dạng chuẩn tắc HỘI của công thức: (A  B)  (B  A) là A. (A  B  C)  (B  B  A) 234 B. (A  B  C)  (B  B  A) C. ) D ) Dạng chuẩn tắc TUYỂN của công thức (A  B)  (B  A) là: A. 1 235 B. C. D

)

Dạng chuẩn tắc TUYỂN của công thức A. 1 236 B. C. D

) là:

)

Dạng chuẩn tắc TUYỂN của công thức A. A 237 B. C. D. ) Dạng chuẩn tắc HỘI của công thức A. A 238 B. C. D. )

là:

là:

Dạng chuẩn tắc TUYỂN của công thức A. A 239 B. C. D. ) Dạng chuẩn tắc TUYỂN của công thức (A B) 240 A. B. 35

là:

B

) là:

C. D. Dạng chuẩn tắc TUYỂN của công thức (A B) A. 241 B. C. D.

B

Dạng chuẩn tắc HỘI của công thức (A B)

) là:

B

) là:

A. 242 B. C. D. Dạng chuẩn tắc HỘI của công thức (A B) A. 243 B. C. D. Dạng chuẩn tắc HỘI của công thức ( A B) A. 244 B. C. D.

B

Dạng chuẩn tắc TUYỂN của công thức ( A B) A. 245 B. C. D.

) là:

B

) là:

B

Cho công thức logic mệnh đề : A = với p = 1, q = 0, r =1, hãy cho biết giá trị của A là gì? 246 A. 0 B. 1 C. Không xác định được Cho công thức logic mệnh đề : A = với p = 1, q = 0, r =1, hãy cho biết giá trị của A là gì? 247 A. 0 B. 1 C. Không xác định được Cho công thức logic mệnh đề : A = với p = 1, q = 0, r =1, hãy cho biết giá trị của A là gì? 248 A. 0 B. 1 C. Không xác định được 36

) là:

Cho công thức logic mệnh đề : A = với p = 1, q = 0, r =1, hãy cho biết giá trị của A là gì? 249 A. 0 B. 1 C. Không xác định được Cho biết giá trị của công thức sau: 250 A.1 B.0 Xác định hàm Boole f được cho bởi mạch sau?

251 A. A.B.C+(A+D) B.

.B.C(

C.

.B.C+(

D. A.

)

.(

) )

Xác định hàm Boole f được cho bởi mạch sau?

252

A. AC+BC+AB ̅ B. ̅C+BC+AB ̅ C. AC+B ̅ +BC ̅ D. A ̅ +B ̅ +̅BC 37

253

254

255

256

257

258

Cho X là 1 biến Boole. Xác định biểu thức sai trong các biểu thức sau? A. X.0=0 B. X.1=1 C. X+0=X D. X+1=1 Cho X là 1 biến Boole. Xác định biểu thức sai trong các biểu thức sau? A. X+0=X B. X+1=X C. X + (Y + Z) = (X + Y) + Z = X + Y + Z D. (W + X)(Y + Z) = WY + XY + WZ + XZ Hàm Boole f=x+xy tương đương với hàm nào sau đây? A. f=xy B. f=y C. f=x+y D. f=x Đại số Boole là…? A. Một tập hợp với 2 phép toán cộng (+) và nhân (.) B. Một tập hợp với các phép toán cộng (+) và nhân (.) và lấy phần bù. C. Một tập hợp với các phép toán cộng (+) và nhân (.) và lấy phần bù; các phép cộng, nhân thoả các tính chất giao hoán, kết hợp, phân bố và có phần tử trung hoà. D. Một tập hợp với các phép toán cộng (+) và nhân (.); các phép cộng, nhân thoả các tính chất giao hoán, kết hợp, phân bố và có phần tử trung hoà. Giả sử x1,x2, …, xn là các biến Boole. Một từ đơn là…? A. Một hàm boole có dạng xi B. Một hàm boole có dạng ̅ C. Một hàm boole có dạng xi . ̅ D. Một hàm boole có dạng xi hoặc ̅ Một biểu thức Boole theo các biến x1,x2, …, xn là một tích cơ bản nếu…? A. Nó có dạng xi. ̅ B. Nó có dạng x1. x2… xn. C. Nó có dạng y1. y2… yn trong đó yi= xi hoặc yi = ̅ (i=1,2,..,n) D. Nó có dạng ̅ ̅ …̅ Đầu ra của cổng logic sau là gì?

259 A. AB B.

+

C. . D. A+B 260 Đầu ra của cổng logic sau là gì? 38

A. AB B.

+

C. . D. A+B Đầu ra của cổng logic sau là gì? A. 261 B.

+

C. . D. A+B Đầu ra của cổng logic sau là gì?

262 A. B. A.B C. D. A+B Một đơn thức là? A. Một tích khác không của một số hữu hạn các từ đơn (xi hoặc ̅ ) 263 B. Một tổng khác không của một số hữu hạn các từ đơn (xi hoặc ̅ ) C. Một tích khác không của đúng n từ đơn D. Một tổng khác không của đúng n từ đơn Công thức đa thức là? A. Công thức biểu diễn hàm Boole thành tích của các tích cơ bản (từ tối tiểu) 264 B. Công thức biểu diễn hàm Boole thành tổng của các tích cơ bản (từ tối tiểu) C. Công thức biểu diễn hàm Boole thành tổng của các từ đơn D. Công thức biểu diễn hàm Boole thành tổng của các đơn thức Dạng chính tắc tuyển (nối rời chính tắc) của hàm Boole là…? A. Công thức biểu diễn hàm Boole thành tổng của các tích cơ bản (từ tối tiểu) 265 B. Công thức biểu diễn hàm Boole thành tích của các tích cơ bản (từ tối tiểu) C. Công thức biểu diễn hàm Boole thành tổng của các đơn thức 39

Chọn đáp án đúng để điền vào dấu … trong câu sau: “Một tế bào là một tập hợp gồm …. ô kề nhau có giá trị bằng 1” 266 A. 2n (n = 0,1,2…) B. 2n (nZ+) C. n(nZ+) Trong bảng Karnaugh, 2 ô gọi là kề nhau nếu…? A. Chúng nằm trên cùng 1 hàng B. Chúng nằm trên cùng 1 cột 267 C. Nếu chúng cùng nằm trên 1 hàng, 1 cột hoặc chúng là ô đầu, ô cuối của cùng một hàng hoặc 1 cột nào đó D. Nếu chúng là hai ô liền nhau hoặc chúng là ô đầu và ô cuối của cùng một hàng hoặc 1 cột nào đó Tế bào sau là biểu đồ Karnaugh của đơn thức nào?

268

A. yt B. xt C. y ̅ D. z. ̅ Cho bảng Kar(f) như sau

269

A. xz B. zyt 40

C. ̅ . ̅ z Cho bảng Kar(f) sau: Đơn thức nào sau đây không phải là một tế bào tối đại của bảng Kar(f)?

270

A. xy B. ̅ . ̅ ̅ C. xz D. x ̅ Cho hàm Boole như sau:

Bảng Karnaugh sau là bảng Karnaugh của hàm Boole f ở trên đúng hay sai

271

A. Đúng B. Sai

41

272

A. 3 B. 2 C. 1

273

A. 4 B. 5 C. 6

274

A. B. C. Hãy cho biết có bao nhiêu tế báo tối đại trong bảng Karnaugh dươi đây 275 z

x

x

1

1

̅

̅

1

̅ 42

z

1

1

̅

1

1

̅

1

1

̅

y

1 1

t 1

y

t

̅

̅

A.3 B. 4 C. 5 D.6 Hãy cho biết có bao nhiêu tế báo tối đại trong bảng Karnaugh dươi đây x

276

̅

x

̅ ̅

z

1

1

z

1

1

t

̅

1

1

t

̅

1

1

̅

y

̅

̅

y

A.1 B. 2 C. 3 D. 4 Hãy cho biết có bao nhiêu tế báo tối đại trong bảng Karnaugh dươi đây x x ̅ ̅ ̅ z 1 1 z 1 1 t ̅ 1 1 t 277 ̅ 1 1 ̅ y y ̅ ̅ A. 1 B. 2 C. 3 D. 4 Hãy cho biết có bao nhiêu tế báo tối đại trong bảng Karnaugh dươi đây 278

x

x

̅

̅

43

z

1

z

1

1

1

̅

1 t

̅

t

̅ ̅

1

1

1

y

y

̅

̅

A. 1 B. 2 C. 3 D. 4 Hãy cho biết có bao nhiêu tế báo tối đại trong bảng Karnaugh dươi đây

z

x

x

̅

̅

1

1

1

1

1

1

z

̅

t

̅

279

̅

t 1

1

1

1

̅

y

y

̅

̅

A. 1 B. 2 C. 3 D. 4 Hãy cho biết có bao nhiêu tế báo tối đại trong bảng Karnaugh dươi đây

z 280

x

x

1

1

z

1

̅

̅

̅ ̅

1 1

̅

t 1 1

̅

y

y

t ̅

̅

A. 3 B. 4 44

C. 5 D. 6 Hãy cho biết có bao nhiêu tế báo tối đại trong bảng Karnaugh dươi đây x

x

̅

1

1

1

z

1

1

̅

1

1

z

281

̅ ̅

t 1

̅

t ̅

1 ̅

y

̅

y

A. 3 B. 4 C. 5 D. 6 Hãy cho biết có bao nhiêu tế báo tối đại trong bảng Karnaugh dươi đây x x ̅ ̅ ̅ z 1 1 1 1 z 1 1 t 1 1 t ̅ ̅ ̅ 1 1 1 1 282 y y ̅ ̅ A. 2 B. 3 C. 4 D. 5 Hãy cho biết có bao nhiêu tế báo tối đại trong bảng Karnaugh dươi đây

283

̅

̅

x

x

z

1

1

z

1

1

1

1

1

1

1

1

y

̅

̅ ̅ ̅

y

̅

t t ̅

A. 2 B. 3 45

284

x

x

z

1

1

z

1

1

̅

̅ ̅

t

̅

t ̅

̅ ̅

y

̅

y

z

285

x

x

̅

̅

1

1

1

1

̅

z

t

̅

t ̅

̅ ̅

y

y

̅

x

̅

̅

286 z z

1

̅

1 t

46

̅ ̅

t 1 ̅

̅

1 y

̅

y

287

1

1

1

̅

1

z

t

̅

t

̅

1

1

1

1

̅

y

y

̅

̅

288

̅

̅

x

x

z

1

1

z

1

1

t

̅

1

1

t

̅

1

1

̅

y

̅

̅

y

̅

x

x

̅

̅

z

1

1

1

z

1

1

1

t

̅

1

1

1

t

̅

1

1

1

̅

y

y

̅

̅ ̅

290

̅

̅

x

x

z

1

1

1

z

1

1

1

t

̅

1

1

1

t

̅

1

1

1

̅

y

̅

̅

̅

y

̅

̅

z

1

1

1

z

1

1

1

t

̅

1

1

1

t

̅

1

1

1

y

y

̅

x

291

̅

̅

̅

48

292

̅

z

1

1

1

z

1

1

1

t

̅

1

1

1

t

̅

1

1

1

y

̅

̅

y

̅

293

x

x

̅

̅

z

1

1

1

1

z

1

1

1

1

t

̅

1

1

1

1

t

̅

̅

̅ ̅

y

y

̅

294

x

x

̅

̅

Z

1

1

1

1

z

1

1

1

1

̅ ̅

̅

t t

1

1

1

1

̅

y

y

̅

̅

49

x

̅

x

̅ ̅

Z

295

z

1

1

1

1

t

̅

1

1

1

1

t

̅

1

1

1

1

̅

y

y

̅

̅

z

x

x

̅

̅

1

1

1

1

̅

z 296

t

̅

1

1

1

1

̅

1

1

1

1

̅

y

y

̅

t ̅

z

1

̅

1 ̅

1 1 y

y

̅

A. 1 50

x

̅

̅

1 1

1

̅

y

1

298 y

̅

x

̅

̅

z

1

̅

1

1

1

y

y

̅

299 ̅

̅

̅

z

1

1

1

̅

1

1

y

y

x

300 ̅

̅

x

x

̅

̅ 51

z

1

̅ ̅

1

1

1

1

y

y

1

̅

x

z

1

1

̅

1

̅

̅

1 1

302 ̅

y

̅

y

x

̅

̅

z

1

1

̅

1

1

303

̅

y

y

̅

x

̅

̅

z

1

1

1

1

̅

1

1

̅

y

304 1 y

̅ 52

x

̅

z

1

1

1

̅

1

̅

1

305 ̅

y

y

̅

̅

̅

z

1

1

1

̅

1

x

1

306 ̅

y

y

̅

x

z

1

1

̅

1

1

̅

y

̅

̅

y

̅

307

x

̅

z

1

1

̅

1

1

y

y

x

̅

̅

̅

z 309

x

x

̅

̅

1

1

1

1

̅

y

y

̅

̅

x

̅

̅

1

1

1

1

̅

y

y

̅

z ̅

310

̅

z

1

1

̅

1

1

x 311

x

54

̅

y

y

̅

312

x

̅

̅

z

1

1

̅

1

1

̅

y

y

̅

1

̅

1

x

̅

̅

y

y

̅

313 ̅

x

̅

z

1

̅

1

̅

314 ̅

y

y

̅

A. ̅ B. x. ̅ C. x D. ̅ 55

315

x

z

1

̅

1 ̅

y

̅

̅

y

̅

x

̅

̅

z

1

̅

1

316 ̅

y

y

̅

x

z

̅

̅

1

1

y

̅

̅

317 ̅

y

318

x

x

1

1

̅

̅

z ̅

56

̅

y

y

̅

z 319

x

x

1

1

̅

y

̅

̅

y

̅

̅

x

̅

̅

1

1

y

̅

z 320

̅ ̅

y

x

̅

1

̅

1

321 ̅ ̅

y

y

̅

x

̅

1

1

y

y

̅

z 322

̅ ̅

̅

57

x

̅

1

1

y

y

̅

̅ ̅

̅

x

̅

̅

z 324 ̅

1 ̅

1 y

y

̅

̅

y

1

̅

1

58

331

B. G không có đường đi Euler Nếu G = (V, E) là một đơn đồ thị vô hướng thì? 332 C. 2 cặp đỉnh bất kỳ được nối với nhau bởi nhiều nhất là 1 cạnh Giả sử G=(V,E) là đồ thị vô hướng. Đỉnh x gọi là đỉnh treo nếu? 333 B. x có bậc 1 Cho G là đơn đồ thị có hướng. Cho biết đâu là tính chất đúng của G? 334 C. Giữa 2 đỉnh bất kỳ i,j có nhiều nhất là 1 cung nối; có kể đến thứ tự các đỉnh i,j Cho đồ thị G=(V,E). Ta nói hai đỉnh u,v V là kề nhau nếu? 335 B. Có cung (cạnh) nối u với v Đồ thị vô hướng G=(V,E) được gọi là liên thông nếu? D. Giữa 2 cặp đỉnh u,v E bất kỳ của đồ thị G đều có đường đi Ma trận kề của đồ thị vô hướng G=(V,E) có tính chất? 337 A. Là ma trận đối xứng. 336

59

Đồ thị vô hướng G có n đỉnh, mỗi đỉnh có bậc bằng 6 thì có bao nhiêu cạnh? 338 C. 3n cạnh D. n cạnh Đồ thị đầy đủ n đỉnh có bao nhiêu cạnh? 339 D. n(n-1)/2 Cho biết đâu là chu trình đơn của đồ thị?

340

A. a,b,c,d,e,c,a Cho biết đâu là chu trình sơ cấp của đồ thị?

341

Đồ thị vô hướng liên thông G=(V,E) là đồ thị nửa Euler khi và chỉ khi? 346 C. Có đúng 2 đỉnh bậc lẻ, các đỉnh khác bậc chẵn. Đồ thị vô hướng liên thông G=(V,E) là đồ thị Euler khi và chỉ khi? D. Tất cả các đỉnh đều bậc chẵn Một đơn đồ thị vô hướng liên thông có 9 đỉnh, các đỉnh có bậc lần lượt là 2, 2, 2, 348 3, 3, 3, 4, 4, 5. Tìm số cạnh của đồ thị? D. 14 349 Cho đồ thị G có trọng số như hình sau: 347

60

G là đồ thị có phải đồ thị Euler không? Vì sao? A. Có vì các đỉnh của đồ thị đều có bậc chẵn B. Không, vì nó chứa các đỉnh bậc lẻ (a,k,m,c,d,h) C. Không, vì nó chứa các đỉnh bậc chẵn (a,k,m,c,d,h) D. Có, vì nó chứa các đỉnh bậc chẵn (a,k,m,c,d,h) Tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại trong đồ thị sau. Đỉnh E được gán trọng số nhỏ nhất là?

350

A. 6 Chu trình Hamilton là…? 351 D. Là chu trình sơ cấp đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng 1 lần Hãy cho biết đồ thị nào sau đây là đồ thị Euler?

352

353

354

355 356 357

A. Đồ thị A Cây là đồ thị vô hướng liên thông…? C. Không có chu trình Giả sử G=(V,E) là đồ thị vô hướng liên thông có n đỉnh. T là cây khung (cây bao trùm) của đồ thị G. Khẳng định nào sau đây không tương đương với các khẳng định còn lại? D. T liên thông và các đỉnh đều có bậc chẵn Giả sử G=(V,E) là đồ thị vô hướng liên thông có n đỉnh. T=(V,H) được gọi là cây khung (cây bao trùm) của đồ thị G nếu…? C. T liên thông, có n-1 cạnh và HE Cây là đồ thị vô hướng liên thông…? C. Không có chu trình Cho ma trận kề của đồ thị G= (V,E) như sau: 61

Cho ma trận kề của đồ thị G= (V,E) như sau:

C.

359 Cho đồ thị G như hình vẽ: 62

Tìm cây bao trùm nhỏ nhất theo thuật toán Prim?

D. T={(3,4),(3,6),(2,3),(6,7), (5,6),(5,8), (8,11),(8,9),(9,10),(1,2)}

Cho đồ thị G như hình vẽ: Tìm cây bao trùm nhỏ nhất theo thuật toán Kruskal?

360

D. T={(3,4),(3,6),(2,3),(6,7), (8,11), (8,9),(5,6),(9,10),(5,8), (1,2)}

364

Tìm cây khung của đồ thị theo thuật toán DFS(f) (ưu tiên theo chiều sâu gốc f) A.

63

Cho đồ thị G như hình vẽ:

Tìm cây khung của đồ thị theo thuật toán BFS(f) (ưu tiên theo chiều rộng gốc f)? C. 365

366 Tìm cây bao trùm của đồ thị G được xây dựng bằng thuật toán DFS(1)

64

A. T={(1,2),(2,3),(3,4),(4,5),(5,7),(7,6)} Tìm cây bao trùm của đồ thị G được xây dựng bằng thuật toán BFS(1)

367

B. T={(1,2),(1,3),(1,4),(2,6),(3,5),(3,7)} Cho đồ thị như hình vẽ:

368

Tìm chu trình Hamilton của đồ thị? A. 1,2,3,6,7,8,9,10,5,4,1. Cho đồ thị G như hình vẽ

369 Thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại, nhãn cực tiểu của đỉnh 4 là bao nhiêu? C. 9 65

Cho đồ thị G như hình vẽ

370 Thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh 9 cho kết quả đường đi ngắn nhất là? B. 1→3→4→8→9 Cho đồ thị như hình vẽ:

371

Thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại, nhãn cực tiểu của đỉnh 5 là bao nhiêu? B. 11 Cho đồ thị như hình vẽ:

372

Đường đi ngắn nhất từ đỉnh 1 đến đỉnh 9 là…? C. 1→3→5→8→9 Thuật toán Dijkstra áp dụng cho? 373 C. Đồ thị vô hướng, có hướng có trọng số không âm 374 Thuật toán Dijkstra được dùng để? 66

D. Tìm đường đi ngắn nhất từ 1 đỉnh đến các đỉnh còn lại của đồ thị Thuật toán Prim dùng để…? 375 D. Tìm cây khung nhỏ nhất của đồ thị Có thể xây dựng cây khung của đồ thị (không trọng số) bằng thuật toán….? 376 A. BFS,DFS

377

378

379

380

381

Phát biểu nào sau đây là đúng: A. Đồ thị G là đơn đồ thị khi và chỉ khi G không có khuyên và bất kỳ hai đỉnh phân biệt nào cũng được nối với nhau bởi không quá một cạnh. B. Đồ thị G là đơn đồ thị khi và chỉ khi G có khuyên và bất kỳ hai đỉnh phân biệt nào cũng được nối với nhau bởi không quá một cạnh. C. Đồ thị G là đơn đồ thị khi và chỉ khi G không có khuyên và trong G có tồn tại một cặp đỉnh phân biệt được nối với nhau bởi nhiều hơn một cạnh. D. Đồ thị G là đơn đồ thị khi và chỉ khi G có khuyên và trong G có tồn tại một cặp đỉnh phân biệt được nối với nhau bởi nhiều hơn một cạnh. Phát biểu nào sau đây là đúng: A. Đồ thị G là đa đồ thị khi và chỉ khi G không có khuyên và bất kỳ hai đỉnh phân biệt nào cũng được nối với nhau bởi không quá một cạnh. B. Đồ thị G là đa đồ thị khi và chỉ khi G có khuyên và bất kỳ hai đỉnh phân biệt nào cũng được nối với nhau bởi không quá một cạnh. C. Đồ thị G là đa đồ thị khi và chỉ khi G không có khuyên và trong G có tồn tại một cặp đỉnh phân biệt được nối với nhau bởi nhiều hơn một cạnh. D. Đồ thị G là đa đồ thị khi và chỉ khi G có khuyên và trong G có tồn tại một cặp đỉnh phân biệt được nối với nhau bởi nhiều hơn một cạnh Phát biểu nào sau đây là đúng: A. Đồ thị G là giả đồ thị khi và chỉ khi G không có khuyên và bất kỳ hai đỉnh phân biệt nào cũng được nối với nhau bởi không quá một cạnh. B. Đồ thị G là giả đồ thị khi và chỉ khi G có khuyên và bất kỳ hai đỉnh phân biệt nào cũng được nối với nhau bởi không quá một cạnh. C. Đồ thị G là giả đồ thị khi và chỉ khi G không có khuyên và trong G có tồn tại một cặp đỉnh phân biệt được nối với nhau bởi nhiều hơn một cạnh. D. Đồ thị G là giả đồ thị khi và chỉ khi G có khuyên và trong G có tồn tại một cặp đỉnh phân biệt được nối với nhau bởi nhiều hơn một cạnh Cho G là đồ thị có hướng, phát biểu nào sau đây là chính xác nhất: A. G là đơn đồ thị có hướng khi và chỉ khi trong G đối với mỗi cặp đỉnh khác nhau có không quá một cung (cùng chiều) nối với nhau và có thể có khuyên. B.G là đơn đồ thị có hướng khi và chỉ khi trong G đối với mỗi cặp đỉnh khác nhau có không quá một cung nối với nhau và không có khuyên. C.G là đơn đồ thị có hướng khi và chỉ khi trong G có một cặp đỉnh khác nhau được nối với nhau bởi nhiều hơn một cung (cùng chiều) và không có khuyên. D.G là đơn đồ thị có hướng khi và chỉ khi trong G có một cặp đỉnh khác nhau được nối với nhau bởi nhiều hơn một cung (cùng chiều) và có thể có khuyên Cho G là đồ thị có hướng, phát biểu nào sau đây là chính xác nhất: A. G là đa đồ thị có hướng khi và chỉ khi trong G đối với mỗi cặp đỉnh khác nhau có không quá một cung (cùng chiều) nối với nhau và có thể có khuyên. B.G là đa đồ thị có hướng khi và chỉ khi trong G đối với mỗi cặp đỉnh khác nhau 67

Phát biểu nào sau đây là chính xác nhất: A. Cho G là đồ thị bất kỳ. Một đường đơn trong G là đường Euler khi và chỉ khi đường đơn đó đi qua tất cả các cạnh trong G và mỗi cạnh xuất hiện đúng một lần. chúng tôi G là đồ thị bất kỳ. Một đường đơn trong G là đường Euler khi và chỉ khi 390 đường đơn đó đi qua tất cả các đỉnh trong G và mỗi đỉnh xuất hiện đúng một lần. C. Cho G là đồ thị bất kỳ. Một đường đi trong G là đường Euler khi và chỉ khi đường đơn đó đi qua các cạnh trong G. chúng tôi G là đồ thị bất kỳ. Một đường đơn trong G là đường Euler khi và chỉ khi đường đơn đó đi qua tất cả các đỉnh trong G. Phát biểu nào sau đây là chính xác nhất: A. Cho G là đồ thị bất kỳ. Một đường đi trong G là đường Hamilton khi và chỉ khi đường đi đó đi qua tất cả các cạnh trong G và mỗi cạnh xuất hiện đúng một lần. chúng tôi G là đồ thị bất kỳ. Một đường sơ cấp trong G là đường Hamilton khi và chỉ 391 khi đường đi đó đi qua tất cả các đỉnh trong G và mỗi đỉnh xuất hiện đúng một lần. C. Cho G là đồ thị bất kỳ. Một đường sơ cấp trong G là đường Hamilton khi và chỉ khi đường đi đó đi qua tất cả các cạnh trong G. chúng tôi G là đồ thị bất kỳ. Một đường đi trong G là đường Hamilton khi và chỉ khi 68

đường đi đó đi qua tất cả các đỉnh trong G. 392 Phát biểu nào sau đây là chính xác nhất: 393 Cho đồ thị G =. Chu trinh sơ cấp trong G là: B. Chu trình mà trong chu trình đó mỗi đỉnh xuất hiện đúng một lần.. Cho đồ thị G bất kỳ, số đỉnh bậc lẻ trong G luôn luôn là một số: 394 A. Số chẵn Cho G= là đồ thị bất kỳ. Bậc của đồ thị G bằng … 395 A. Hai lần số cạnh Cho đồ thị G có bậc là 10. Số cạnh của đồ thị G là: 396 B. 5 Cho đồ thị G có 5 đỉnh có bậc lần lượt là 2, 2, 3, 4, 5 397 Bậc của đồ thị G là: B. 16 Cho đồ thị vô hướng cạnh có trọng số như hình vẽ.

398

Cây khung nhỏ nhất có tổng trọng số là: B. 10 Một cây có ít nhất mấy đỉnh treo? 399 B. 2 Cho đồ thị G có 9 đỉnh có bậc lần lượt là 1, 2, 2, 3, 3, 4, 4, 4,5 400 Số cạnh của đồ thị G là: C. 14

69