TRƯỜNG CĐ KỸ THUẬT CAO THẮNG ĐỀ THI KẾT THÚC MÔN TOÁN RỜI RẠC LỚP: CĐN QTM, SCMT 15 NGÀY THI: 04/3/16 THỜI GIAN: 75 phút KHOA ĐIỆN TỬ - TIN HỌC ĐỀ 2

Câu 1. Cho s, t, u là các biến mệnh đề. Chứng minh rằng:

1. ((s  t) Ù (t  u))  (s  u) là một hằng đúng. (1.5 điểm)

2. Kiểm tra suy luận sau: (1.5 điểm)

Câu 2.

1. Lớp học có 10 bạn nam và 15 bạn nữ. Hãy cho biết có bao nhiêu cách chọn đội văn nghệ của lớp gồm 8 thành viên trong các trường hợp sau:

a. Không có điều kiện gì thêm. (1.0 điểm)

b. Số bạn nam bằng số bạn nữ. (1.0 điểm)

c. Nhóm có cả nam và nữ. (1.0 điểm)

2. Hãy cho biết, có bao nhiêu Byte (8 bit) với các bit chỉ là 0, 1 mà trong đó (1.0 điểm) mỗi bit 0, 1 có mặt ít nhất 1 lần?

3. Có bao nhiêu chuỗi kí khác nhau lập được từ các chữ cái của từ (1.0 điểm) EVERGREEN, yêu cầu dùng lại tất cả các chữ cái?

Câu 3. Cho đồ thị có hướng như sau:

1. Hãy cho biết ma trận kề của đồ thị trên? (1.0 điểm)

2. Duyệt đồ thị (bắt đầu từ đỉnh A) theo chiều rộng (BFS). (1.0 điểm)

----------Hết---------

Bộ môn Tin học Giáo viên ra đề

TRƯỜNG CĐ KỸ THUẬT CAO THẮNG ĐÁP ÁN ĐỀ THI MÔN TOÁN RR& LTĐT LỚP: CĐTH 15AB NGÀY THI: 03/03/16 THỜI GIAN: 75 phút KHOA ĐIỆN TỬ - TIN HỌC ĐỀ 2

Câu 1. Cho s, t, u là các biến mệnh đề. Chứng minh rằng:

1. ((s  t) Ù (t  u))  (s  u) là một hằng đúng. (1.0 điểm)

//kéo theo

//De Morgan

//De Morgan

Ú(s̅Úu) Û((s̅Út)Ù(t̅Úu)) Ú(s̅Úu)) Ú(t̅Úu) Û((s̅Út) Û((sÙt̅)Ú(tÙu))Ú(s̅Úu) Û((sÚt)Ù(sÚu)Ù(t̅Út)Ù(t̅Úu))Ú(s̅Úu) //phân phối Û ((sÚtÚs̅Úu)Ù(sÚuÚs̅Úu)Ù(t̅ÚuÚs̅Úu)) //phân phối

//phần tử bù Û TÙTÙTÛ T(đpcm)

3. Kiểm tra suy luận sau: (1.5 điểm)

//tiền đề

//tiền đề

//khẳng định 1. u 2. u → t̅ 3. t̅

//tiền đề 4. s̅

//tiền đề

//De Morgan 5. s̅ Ù t̅ 6. s Ú t

//tiền đề 7. r → (s Ú t)

//phủ định 8. r̅

//tiền đề

//phủ định 9. ( p Ú q) → r 10. p Ú q

//De Morgan 11. p Ù q

12. p đpcm

Câu 2.

1. Lớp học có 15 bạn nam và 10 bạn nữ. Hãy cho biết có bao nhiêu cách chọn đội văn nghệ của lớp gồm 8 thành viên trong các trường hợp sau:

(1.0 điểm)

(1.0 điểm)

x C

(1.0 điểm)

a. Không có điều kiện gì thêm = C b. Số bạn nam bằng số bạn nữ = C c. Nhóm có cả nam và nữ = C

− C

− C 2. Hãy cho biết, có bao nhiêu Byte (8 bit) với các bit chỉ là 0, 1 mà trong đó (1.0 điểm)

mỗi bit 0, 1 có mặt ít nhất 1 lần? Ta có số số Byte (8 bit), với các bit là 0, 1 là: 28

Gọi:

A: tập các Byte với các bit 0 (không có 1).  |A| = 18 B: tập các Byte với các bit 1 (không có 0).  |A| = 18

X là tập các số thỏa yêu cầu = 28 - 18 - 18

3. Có bao nhiêu chuỗi kí khác nhau lập được từ các chữ cái của từ (1.0 điểm) EVERGREEN, yêu cầu dùng lại tất cả các chữ cái?

!

= !!!!!

Câu 4. Cho đồ thị có hướng như sau:

1. Hãy cho biết ma trận kề của đồ thị trên? (1.0 điểm)

0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 A B C D E F 0 1 A 0 1 B 0 0 C 0 0 D 1 0 E 0 1 F

2. Duyệt đồ thị (bắt đầu từ đỉnh A) theo chiều rộng (BFS). (1.0 điểm)

A  B  C  D  E  F

----------Hết---------