Bài tập thảo luận Toán học rời rạc

1 TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG KHOA CÔNG NGHỆ THÔNG TIN BÀI TẬP THẢO LUẬN TOÁN HỌC RỜI RẠC Số tín chỉ : 03 Hệ: Đại học chính qui Bộ môn giảng dạy: Bộ môn Khoa học máy tính – Khoa CNTT Năm 2015 2 BÀI TẬP CHƯƠNG 1 1.1 Bài tập về tập hợp, các phép toán trên tập hợp, quan hệ Bài 1 : 1.1 Cho P(x) và Q(x) là các đa thức. Gọi A là tập các nghiệm của phương trình P(x)=0, B là tập các nghiệm của phương trình Q(x)=0. Hãy biểu diễn mối quan hệ qua tập A, B tập nghiệm của các phương trình sau: a/ P(x).Q(x)=0 b/ P(x)+ Q(x) =0 c/ 0 )( )(  xQ xP 1.2 Cho tập X={1, 2,3}. Hãy xác định các khẳng định đúng a. 1 X b.{1} X c.{1} X d. {{2}} X 1.3 Cho tập vũ trụ X={ 1, 2, 3,,10} và các tập con A={1,2,3,4,5}; B={1,2,4,8}; C={1,2,3,5,7}; D={2,4,6,8} Hãy xác định các tập hợp: a. ( )A B C  b. ( )A B C  c. C D d. C D e. ( )A B C  f. ( )B C D  g. ( ))B C D  h. ( )A B C D   1.4 Đơn giản các biểu thức a. ( )A B A  b. ( )( )A B A B C   c. ( ) ( ( ) ( ))A B B C D C D      1.5 Cho X={2.3.4}; Y={2,5,7,9} a.Tính XxY b. Tính số quan hệ giữa X và Y c. Tính số quan hệ hai ngôi trên tập X, tập Y Bài 2: Cho A=-2. -1, 0, 1, 4 ; B= 0, 1, 2. Hãy xác định các tập sau đây: a/ (x, y)  A x B x<y  c/ (x, y)  A x B y là ước của x  b/ (x, y)  A x B x2  y2  d/ (x, y)  A x B xy=0  Bài 3: Trên tập Z xét tính chất của các quan hệ sau: a/ a R b nếu a+b lẻ b/ a R b nếu a + b chẵn c/ a R b nếu a b Bài 4: Trên tập R các số thực, xét quan hệ xTy nếu x = y a/ Chứng minh T là quan hệ tương đương trên R b/ Xác định lớp tương đương a, a  R Bài 5: Trên R xét 2 quan hệ 3 xSy nếu x3  y3 xTy nếu x2  y2 Chứng minh rằng S là quan hệ thứ tự toàn phần trên R ; T không phải là quan hệ thứ tự trên R 1.2 Bài tập về logic mệnh đề và các dạng chuẩn tắc, vị từ & lượng từ Bài 6: 6.1.Phát biểu nào sau đây là mệnh đề trong Logic mệnh đề: a. 5 không phải là số nguyên tố b. Tam giác đều là tam giác có các cạnh bằng nhau c. 1 + 1 = 0 d. Phương trình 5x+4=0 có nghiệm bằng bao nhiêu? e. 6 là số chia hết cho 2 và 3 6.2 Lập bảng giá trị chân lý cho các biểu thức logic sau: a/ ( )p p q  b/ ( )p r p q   c/ ( ) ( )p q p r q    d/ ( )x y yz xyz   e/ ( )x y z x y z     f/ ( ) ( )x z y z   6.3 Giả sử biến mệnh đề p nhận giá trị chân lý 1, hãy xác định tất cả các bộ giá trị chân lý của các biến mệnh đề q, r, s để các biểu thức logic sau nhận giá trị chân lý 1 a/ ( (( ) )) ( ( ))p q r s s r p      b/ ( (( ) )) ( ( ))p q r s s q p      Làm tương tự với p nhận giá trị chân lý 0? 6.4 Xét các vị từ P(x): “x5” Q(x):”x+3 là số chẵn” trong đó x là một số nguyên Hãy xác định giá trị chân lý của các mệnh đề sau: a/ P(1) b/ Q(1) c/ (2)P d/ (6) (6)P Q e/ ( 1) ( 1)P Q   f/ (2) (3) ( 2)P Q Q   6.5 Xét các vị từ theo biến thực x: P(x): x 2 -5x+6=0 Q(x): x 2 -4x-5=0 R(x): x>0 Hãy xác định giá trị chân lý cho các mệnh đề sau: a/ , ( ) ( )x P x R x  b/ , ( ) ( )x Q x R x  c/ , ( ) ( )x Q x R x  d/ , ( ) ( )x P x R x  Bài 7: 7.1 Tìm chính tắc tuyển của các biểu thức: a/ ( )x y yz  b/ ( )x z y z   c/ ( ) ( )x z y z   d/ ( )x y yz xy   e/ ( )x z y z  f/ ( )( )x z y z  7.2 Tìm chính tắc hội của các biểu thức: a/ ( )x y y z   b/ ( )x z y z   c/ ( ) ( )x z y z   d/ ( )x y yz  e/ ( )x z y z  f/ ( )( )x z yz Bài 8: 8.1 Tìm chính tắc tuyển của các biểu thức: 4 a/ ( )x y yz  b/ ( )x z y z   c/ ( ) ( )x z y z   d/ ( )x y yz xy   e/ ( )y z y z  f/ ( )( )x y x z  8.2 Tìm chính tắc hội của các biểu thức: a/ ( )x y y z   b/ ( )x z y z   c/ ( ) ( )y z x z   d/ ( )y z xz  e/ ( )( )y z x z  f/ ( )( )x y yz Bài 9: Chứng minh các đẳng thức sau: a. )()( rpqrqp  b. rqprqp  )( c. rqprpqp  )()( d. qpqp  ()(( )) p 0 Bài 10: 10.1 Xác định các biểu thức logic hằng đúng, hằng sai: a. ( ) ( )x y x y   b. ( )x y x  c. ( ) (( ) ( ))x y y z x z     c. ( )x y x  d. ( )x y z x z    e. ( ) ( )x y x y x y     10.2 Chỉ ra khẳng định đúng a. ( )x x y x y    b. ( )x y x x y    c. x y x y   d. ( ) ( ) ( ) ( ) ( ) ( )x y y z x z x y y z z x           10.3 Rút gọn các biểu thức a. ( ) ( )x y z x y z     b. x y z  c. ( )x x y x y    d. ( )x y x y z    Bài 11: a/Tìm miền đúng của các hàm mệnh đề xác định trên R: a1. 2x+1>3 a2. 5x 2– 4x-1  0 a3. 3x 2 + 5x + 10 >0 a4. x 2 +3x +4  0 a5. (x) (x>2) b/ (x) P(x) là kí hiệu cho mệnh đề:’ Tồn tại duy nhất một x sao cho P(x) là đúng. Hãy xác định giá trị chân lý cho mệnh đề sau trên R: b1/ (x) x3 =1 b2/ (x) (x2-3x+2=0) Bài 12: a/Cho biểu thức: E= ),(( yxPx  ),( yxyQ Hãy biến đổi tương đương để đưa biểu thức trên về dạng: Không có các dấu tương đương; không có các dấu kéo theo; không kể các dấu lượng từ thì nó là tuyển của các thành phần mà mỗi thành phần này lại là hội của các biểu thức không chứa các dấu tuyển và hội. b/ Cho biểu thức E= ))()(())()(( xxFxxRxxQxxP  Thực hiện các phép biến đổi tương đương sau đối với E: 1. Khử phép kéo theo 5 2. Đưa phép phủ định về trực tiếp liên quan tới các vị từ P, Q, R, F 3. Đưa các lượng từ lên trước biểu thức Bài 13: Cho các mệnh đề thuận a. x y x z   b. x y z x y    c. x y y z   Hãy xác định các mệnh đề liên kết với mệnh đề thuận. 1.3 Bài tập về các quy tắc suy diễn, chứng minh toán học Bài 14: Chứng minh qui tắc suy luận 1/ rp rqqp   , 2/ qp pqqp   , 3/ rqp rqrp   , 4/ rqp rpqp   , 5/ rp rqp   6/ q qpqp  , Bài 15: Kiểm tra các quy tắc suy luận a. , ,p q q r p r   b. , ,p q r q r p   c. ( ), ,p q r q p p r    d. ( ), ( ) p q r p r q    e. ( ),p p q q r r    Bài 16: Chứng minh rằng Sn= 1 + 3 + 5 + ... + (2n-1) = n 2 với mọi số tự nhiên n 1 Bài 17: 17.1 Chứng minh rằng nếu (n-1)! Chia hết cho n thì n không phải là số nguyên tố. 17.2 Giả sử p là số nguyên dương lớn hơn 1. Chứng minh rằng: Nếu (p-1)!+1 chia hết cho p thì p là số nguyên tố. Bài 18:Hãy chứng minh rằng: a/ 7 n –1 chia hết cho 6 với n=1,2,... b/ 1 2 –22 +32 - ... + (-1)n+1 n2 = (-1) n+1 n(n+1)/2 với n1, nN c/ 1 1 n  )2...(6.4.2 )12...(5.3.1 n n  với n=1,2,... d/ 1 3 + 2 3 +...+ n 3 = (1+2+...+n) 2 = 2 2 )1(       nn với *Nn e/ Chứng minh luật Demorgan ở dạng tổng quát với n=2,3... 6 BÀI TẬP CHƯƠNG 2 2.1. Bài tập về thuật toán, thuật toán đệ qui, quay lui Bài 1: Xây dựng thuật toán thực hiện: Cho 2 số tự nhiên a, b, tìm ước số chung lớn nhất của chúng Bài 2: Xây dựng thuật toán thực hiện: Cho một dãy số nguyên dương a1, a2, ...., an, hãy tìm từ dãy trên phần tử có giá trị là lớn nhất. Bài 3: Xây dựng thuật toán thực hiện: tìm USCLN của 2 số tự nhiên a, b. Bài 4: Lập sơ đồ khối biểu diễn thuật toán tìm USCLN của 2 số tự nhiên a, b Bài 5: Xây dựng thuật toán và lập chương trình thực hiện: liệt kê tất cả các dãy nhị phân độ dài n Bài 6: Xây dựng thuật toán và lập chương trình thực hiện: liệt kê tất cả các hoán vị của tập n số tự nhiên đầu tiên {1, 2, ..., n} Bài 7: Nhập vào một chuỗi ký tự S. Xuất ra màn hình tất cả các hoán vị khác nhau của các ký tự trong chuỗi S (Các ký tự trong S không nhất thiết khác nhau) 2.2. Bài tập về kỹ thuật đếm cơ bản & cao cấp 2.2.1 Bài tập về các nguyên lý đếm Bài 8:Giả sử trong nhóm 6 người mỗi cặp hai hoặc là bạn hoặc là thù. Chứng tỏ rằng trong nhóm có ba người là bạn lẫn nhau hoặc có ba người là kẻ thù lẫn nhau. Bài 9: Biết rằng có 100 sinh viên học tiếng Anh, 70 học sinh học tiếng Nga, và 50 học sinh học tiếng Pháp, 40 học sinh học cả tiếng Anh và tiếng Nga, 20 học sinh học cả tiếng Anh và tiếng Pháp, 12 học sinh hoạc cả tiếng Pháp và tiếng Nga. Néu tất cả 500 sinh viên đều theo học ít nhất một ngoại ngữ, thì có bao nhiêu sinh viên học cả ba thứ tiếng? Bài 10: Hỏi trong tập X = {1, 2, , 10000} có bao nhiêu số không chia hết cho bất cứ số nào trong các số 3,4,7? Bài 11. Có bao nhiêu số nguyên dương gồm đúng 3 chữ số: a/ Chia hết cho 4 b/ Chia hết cho 4 hoặc cho 3 c/ Chia hết cho 4 và chia hết cho 3 Bài 12: a/ Có bao nhiêu xâu nhị phân có dộ dài nhỏ hơn hoặc bằng 8. b/Có bao nhiêu xâu nhị phân độ dài là 8 hoặc là bắt đầu bởi 00 hoặc là kết thúc bởi 11? Bài 13: Cho tập A={0, 3, 5, 6, 8}. a/ Có bao nhiêu số gồm 4 chữ số khác nhau được thành lập từ A b/ Có bao nhiêu số gồm 4 chữ số được thành lập từ A c/ Có bao nhiêu số lẻ gồm 4 chữ số khác nhau được thành lập từ A 2.2.2 Bài tập về tổ hợp và hoán vị Bài 14. Cho tập A={1, 3, 5}. Có bao nhiêu số gồm 3 chữ số khác nhau được thành lập từ A. Bài 15. Cho A={0,1, ..., 9}, có thể lập được bao nhiêu số chẵn có 4 chữ số mà các chữ số đó đều khác nhau. 7 Bài 16. Cho 4 điểm tùy ý phân biệt A,B,C,D: a. Có bao nhiêu cách ghi 4 điểm đó lên trên một đường thẳng b. Có bao nhiêu véc tơ khác 0 được thành lập từ 4 điểm c. Giả sử trong 4 điểm trên không có ba điểm nào thẳng hàng. Có thể thành lập được bao nhiêu tam giác d. Có thể thành lập từ 4 điểm trên bao nhiêu đoạn thẳng. Bài 17: Một lớp có 30 học sinh nam và 15 học sinh nữ. Có 6 học sinh được chọn ra để lập một nhóm tốp ca. Hỏi có bao nhiêu cách chọn khác nhau: a. Nếu phải có ít nhất là 2 nữ b. Nếu chọn tùy ý Bài 18: Cho A={1,2,3,4,5,6}. Có thể thành lập được bao nhiêu số gồm 4 chữ số khác nhau, trong đó có bao nhiêu số chia hết cho 5? Bài 19: Cho A={1,2,..,10}. Có thể thành lập được bao nhiêu số gồm 6 chữ số khác nhau, sao cho trong các số đó đều có mặt số 0 hoặc số 1? Bài 20: Cho tập hợp A có n phần tử, tìm số tập con khác rỗng của A? 8 BÀI TẬP CHƯƠNG 3 3.1 Bài tập về biểu diễn đồ thị, bậc, các phương pháp duyệt đồ thị Bài 1.Cho đồ thị vô hướng G1, G2 a. Tính bậc các đỉnh của đồ thị, bậc của đồ thị? b. Hãy liệt kê các đường đi có độ dài là 5 c. Hãy liệt kê các chu trình có độ dài là 4 d. Xác định tính liên thông của đồ thị? số thành phần liên thông của đồ thị? e. Hãy lập ma trận lân cận kề của đồ thị G, ma trận liên thuộc của G? f. Đưa ra thứ tự duyệt đồ thị theo chiều rộng và chiều sâu, xây dựng cây khung tương ứng với 2 thứ tự duyệt này. g. Đồ thị trên có đường đi hoặc chu trình Euler (Hamilton) không? (G1) Bài 2. Hãy vẽ các đồ thị vô hướng được biểu diễn bởi ma trận liền kề sau: A G H D B C E I 3 6 7 2 5 1 4 K 9 a) 0 1 1 1 0 1 1 1 0           , b) 0 1 0 1 1 0 1 0 0 0 0 1 0 0 1 0             , c) 0 1 1 0 1 1 0 1 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 0                 . d) 1 2 3 2 0 4 3 4 0           , e) 1 2 0 1 2 0 3 0 0 3 1 1 1 0 1 0             , f) 0 1 3 0 4 1 2 1 3 0 3 1 1 0 1 0 3 0 0 2 4 0 1 2 3                 . Bài 3. Nêu ý nghĩa của tổng các phần tử trên một hàng (cột) của một ma trận liền kề đối với một đồ thị vô hướng ? Đối với đồ thị có hướng ? Bài 4: Chỉ ra thứ tự duyệt đồ thị theo BFS hoặc DFS trên các đồ thị G1, G2(bài 1); đồ thị a,b,c (bài2) Bài 5. Cho các đồ thị được biểu diễn bởi ma trận liền kề sau: a) 0 1 1 1 0 1 1 1 0           , b) 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0             , c) 0 1 1 0 1 1 0 1 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0                 . 5.1. Tính bậc của các đỉnh trên đồ thị a, b, c 5.2. Hãy chỉ ra thứ tự duyệt của đồ thị a và c Bài 6. Tìm ma trận liền kề cho các đồ thị sau: a) Kn , b) Cn, c) Wn , d) Km,n , e) Qn. Bài 7. 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. Bài 8. Hãy tìm số đường đi độ dài n giữa hai đỉnh 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. 3.2. Bài tập về đồ thị Euler, Hamilton, đồ thị phẳng, vấn đề tô màu đồ thị. Bài 9. Với giá trị nào của n các đồ thị sau đây có chu trình Euler ? a) Kn, b) Cn, c) Wn, d) Qn. Bài 10. Với giá trị nào của m và n các đồ thị phân đôi đầy đủ Km,n có chu trình Hamilton ? Bài 11. 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. Bài 12. Cho các đồ thị được biểu diễn bởi ma trận liền kề sau: 10 a) 0 1 1 1 0 1 1 1 0           , b) 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0             , c) 0 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 0 0 1 1 1 1 1 0                 . Hãy xác định đồ thị Euler, Hamilton, nửa Euler, nửa Hamilton (nếu có) trong các đồ thị a,b,c Đồ thị Euler: a; nửa Euler:b,c; Nửa Hamilton:c Bài 13. Cho các đồ thị được biểu diễn bởi các ma trận kề 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 G                2 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 G                3 0 0 0 1 1 0 1 1 0 1 1 0 1 1 1 1 0 1 0 1 0 1 1 1 0 G                a. Xác định tính vô hướng, có hướng, liên thông của các đồ thị b. Tính bậc cho các đỉnh của đồ thị c. Xác định đồ thị nào là Euler? Haminton? Căn cứ vào số bậc của các đỉnh sẽ kết luận được tính Euler hay Hamilton 3.3. Bài tập về thuật toán tìm đường đi ngắn nhất Dijkstra, Floyd Bài 14. Áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh 8 trên đồ thị G được biểu diễn bởi ma trận trọng số sau: a/ C=                                   0398 30551 9507 87046 5052 145014 6102 2420 b/ C=                                   0276 20551 7508 68047 5012 141014 7102 2420 Tương tự dùng thuật toán Dijkstra mở rộng tìm đường đi ngắn nhất từ đỉnh 1 tới các đỉnh còn lại. 11 Bài 15: Tìm đường đi ngắn nhất giữa mọi cặp đỉnh của đồ thị được cho bởi ma rận trọng số 1 0 5 10 45 0 25 40 50 5 0 5 5 60 0 C             2 0 20 34 2 0 6 45 7 23 0 3 8 2 0 5 1 2 0 C                   Bài 16. Cho đồ thị với trọng số dương như hình vẽ. Hãy xác định đường đi ngắn nhất từ đỉnh 1 đến đỉnh 7 ( xác định giá và vết của đường đi). Bài 17. Cho đồ thị với trọng số dương như hình vẽ. Hãy xác định đường đi ngắn nhất từ đỉnh 2 đến đỉnh 7 ( xác định giá và vết của đường đi). Bài 18: a/ Dùng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh a đến các đỉnh còn lại trong G: 3 5 5 2 4 6 7 5 3 1 5 1 4 2 7 6 7 5 1 4 5 2 5 2 4 6 7 5 3 1 6 1 2 2 1 7 3 2 1 5 12 b/ Dùng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh a đến các đỉnh khác trong đồ thị sau: Bài 19. Cho đồ thị có trọng số. Hãy tìm đường đi ngắn nhất từ đỉnh A đến đỉnh N. Bài 20. Tìm đường đi ngắn nhất giữa mọi cặp đỉnh trên đồ thị: 3.3 Bài tập về các thuật toán xây dựng cây khung nhỏ nhất, các phương pháp duyệt trên cây Bài 21. Cho đồ thị G1, G2 được biễu diễn bằng ma trận trọng số (C1), (C2) : 13 a/ Dùng thuật toán Kruskal tìm cây khung với giá nhỏ nhất trên G1, G2 b/ Dùng thuật toán Prim tìm cây khung với giá nhỏ nhất trên G1, G2 0511318 5011075 1110463 3104021 176209 853190 093175 902514 320326 15304 7124010 546100   (C1) ( C2) Bài 22. Cho đồ thị G được biểu diễn ở H1. Mỗi đỉnh là một địa điểm trong thành phố, trọng số trên các cạnh thể hiện khoảng cách giữa các điểm. Hãy xây dựng thuật toán thiết kế một mạng lưới giao thông qua tất cả các điểm, mỗi điểm đúng một lần sao cho tổng khoảng cách trên mạng lưới là nhỏ nhất. Sau đó áp dụng số với đồ thị H1 Bài 23. Cho đồ thị G được biểu diễn bởi ma trận trọng số: C=                                   0125 10552 25023 52041 5340233 12012 23102 3220 a/ Đồ thị có liên thông không? Tại sao? b/ Xây dựng cây khung ngắn nhất của đồ thị. 1 A G H D B C E 6 I 2 4 2 5 3 7 6 4 3 3 2 14 Bài 24: Xác định thứ tự duyệt trên cây Bài 25. Hãy tìm đường đi ngắn nhất từ đỉnh s đến các đỉnh còn lại của đồ thị. B F H D A C E G I K