Các bài tập về logic mệnh đề toán rời rạc

2/ Nếu Q có chân trị là T, hãy xác định chân trị của các biến mệnh đề P, R, S nếu biểu thức mệnh đề sau cũng là đúng

[Q  [[P R]  S ]]  [S  [R Q]]

3/ Cho đoạn chương trình sau a/ if [n>5] n=n+2 ; b/ if [[n+2 == 8] || [n-3==6]] n= 2*n + 1 ; c/ if [[n-3==16] && [n / 5==1]] n= n + 3 ; d/ if [[n21] && [n-7==15]] n= n - 4 ; e/ if [[n / 5 == 2] || [n+1==20]] n=n+1 ; Ban đầu biến nguyên n được gán trị là 7. Hãy xác định giá trị n trong các trường hợp sau:

• Sau mỗi câu lệnh [nghĩa là khi qua câu lệnh mới thì gán lại n = 7]
• Sau tất cả các lệnh [sử dụng kết quả của câu lệnh trước để tính toán cho câu sau]

4/ Cho đoạn chương trình C như sau: a/ if [n-m == 5] n= n-2 ; b/ if [[2m==n] && [n / 4 ==1]] n=4m - 3 ; c/ if [[n0] && [t=3]]]]; Với mỗi cách gán giá trị biến như sau, hãy xác định trong trường hợp nào thì vòng lặp kết thúc. a/ x= 7, y= 2, w= 5, t= 3

b/ x= 0, y= 2, w= -3, t= 3 c/ x= 0, y= -1, w= 1, t= 3 d/ x= 1, y= -1, w= 1, t= 3 6/ Trong một phiên tòa xử án 3 bị can có liên quan đến vấn đề tài chánh, trước tòa cả 3 bị cáo đều tuyên thệ khai đúng sự thật và lời khai như sau: Anh A: Chị B có tội và anh C vô tội Chị B: Nếu anh A có tội thì anh C cũng có tội Anh C: Tôi vô tội nhưng một trong hai người kia là có tội Hãy xét xem ai là người có tội?

7/ Cho các mệnh đề được phát biểu như sau, hãy tìm số lớn nhất các mệnh đề đồng thời là đúng. a/ Quang là người khôn khéo b/ Quang không gặp may mắn c/ Quang gặp may mắn nhưng không khôn khéo d/ Nếu Quang là người khôn khéo thì Quang không gặp may mắn e/ Quang là người khôn khéo khi và chỉ khi Quang gặp may mắn f/ Hoặc Quang là người khôn khéo, hoặc Quang gặp may mắn nhưng không đồng thời cả hai.

8/ Cho a và b là hai số nguyên dương. Biết rằng, trong 4 mệnh đề sau đây có 3 mệnh đề đúng và 1 mệnh đề sai. Hãy tìm mọi cặp số [a, b] có thể có. 1/ a+1 chia hết cho b 2/ a = 2b + 5 3/ a+b chia hết cho 3 4/ a+7b là số nguyên tố

9/ Không lập bảng chân trị, sử dụng các công thức tương đương logic, chứng minh rằng các biểu thức mệnh đề sau là hằng đúng a/ [PQ]P

b/ P[P P] c/ P[[Q [PQ]]]

d/ QP P

e/ [[PQ]  [QR]]  [PR]

10/ Không lập bảng chân trị, sử dụng các công thức tương đương logic, xét xem biểu thức mệnh đề G có là hệ quả của F không? a/ F = P[QR] G = [PQ]R b/ F = [PQ][QR] G = P [Q R]

c/ F = PQ G = [PQ]  [P Q]

11/ Tương tự bài tập 9 và 10, chứng minh các tương đương logic sau đây:

a/ [PQ] QP  P

b/ ][  QRQP  QR

c/ [[PQ]  [P  Q]]  Q  PQ

d/ QP  [[P Q]  Q]  PQ

1. Có ít nhất 1 số nguyên chẵn.
2. Tồn tại 1 số nguyên dương là số chẵn.
3. Nếu x chẵn, thì x không chia hết cho 5.
4. Không có số nguyên chẵn nào là chia hết cho 5.
5. Tồn tại 1 số nguyên chẵn chia hết cho 4.
6. Nếu x chẵn và x là số chính phương, thì x chia hết cho 4. b] Xác định chân trị của mỗi mệnh đề a]. Với mỗi mệnh đề sai, hãy cho một dẫn chứng cụ thể. c] Viết thành lời các dạng ký hiệu sau:
7. x [R[x]  P[x]] 2. x [S[x]  Q[x]]
8. x [S[x]  T[x]] 4. x [S[x] R[x]]
9. x [R[x] Q[x]  S[x]]

17/ Cho các vị từ trên không gian là tập số thực như sau: P[x] = {x  0] Q[x] = {x 2  0} R[x] = {x 2 - 3x -4 = 0} S[x] = {x 2 - 3  0} Xác định giá trị đúng, sai của những biểu thức mệnh đề sau. Cho dẫn chứng hoặc giải thích cụ thể: a] x [P[x]  R[x]] b] x [P[x]  Q[x]] c] x [Q[x]  S[x]] d] x [R[x]  S[x]] e] x [R[x]  P[x]]

18/ Cho 3 vị từ P[x], Q[x], R[x] được xác định như sau: P[x] = {x 2 - 8x + 15 = 0] Q[x] = {x là số lẻ} R[x] = {x  0} Trên tập không gian là tất cả các số nguyên, hãy xác định giá trị đúng, sai của những biểu thức mệnh đề sau. Cho dẫn chứng hoặc giải thích cụ thể: a] x [P[x]  Q[x]] b] x [Q[x]  P[x]] c] x [P[x]  Q[x]] d] x [Q[x]  P[x]] e] x [R[x]  P[x]] f] x [P[x]  R[x]]

1. x [R[x]  P[x]] h] x [Q[x] P[x]]

1. x [P[x]  [Q[x]  R[x]]] j] x [[P[x]  Q[x]  R[x]]

19/ Cho 3 vị từ P[x], Q[x], R[x] như sau: P[x] = {x 2 - 7x + 10 = 0] Q[x] = {x 2 - 2x -3 = 0} R[x] = {x  0} a] Xác định giá trị đúng, sai của những biểu thức mệnh đề sau, cho dẫn chứng hoặc giải thích, nếu không gian là tập số nguyên.

1. x [P[x] R[x]] 2. x [Q[x]  R[x]]
2. x [Q[x]  R[x]] 4. x [P[x]  R[x]] b] Câu hỏi như phần a] nhưng không gian là tập Z+ c] Câu hỏi như phần a] nhưng không gian chỉ gồm 2 số nguyên 2, 5.

20/ Cho P[x] = {x học ở lớp hơn 5 giờ mỗi ngày trong tuần} Không gian là tập hợp các sinh viên. Hãy diễn đạt các lượng từ sau thành câu thông thường. a] x P[x] b] x P[x]

1. x P[x] d] x P[x] 21/ Cho vị từ P[x,y] = {x đã học môn y} với không gian của x là tập hợp tất cả các sinh viên lớp bạn và không gian của y là tập hợp tất cả các môn tin học của học kỳ mà bạn đang học. Hãy diễn đạt các lượng từ sau thành các câu thông thường: a] x y P[x,y] b] x y P[x,y] c] x y P[x,y] d] y x P[x,y] e] y x P[x,y] f] x y P[x,y] 22/ Cho vị từ: P[x] = {x nói được tiếng anh} Q[x] = {x biết ngôn ngữ C++} Cho không gian là tập hợp các sinh viên lớp bạn. Hãy diễn đạt các câu sau bằng cách dùng P[x], Q[x], các lượng từ và các phép toán logic. a] Có một sinh viên ở lớp bạn nói được tiếng Anh và biết C++ b] Có một sinh viên ở lớp bạn nói được tiếng Anh nhưng không biết C++ c] Mọi sinh viên ở lớp bạn đều nói được tiếng Anh hoặc biết C++ d] Không có một sinh viên nào ở lớp bạn nói được tiếng Anh hoặc biết C++ 23/ Cho vị từ: P[x] = {x là sinh viên] Q[x] = {x là kẻ ngu dốt} R[x] = {x là kẻ vô tích sự} Bằng cách dùng các lượng từ, các phép toán logic và với các vị từ P[x], Q[x], R[x]. Hãy diễn đạt các câu sau với không gian là toàn thể sinh viên: a] Không có sinh viên nào là kẻ ngu dốt b] Mọi kẻ ngu dốt đều là vô tích sự. c] Không có sinh viên nào là vô tích sự.

a/ Môn toán là không dễ nếu nhiều sinh viên thích môn logic. b/ Không có nhiều sinh viên thích môn logic nếu môn toán là không dễ. c/ Môn toán là dễ hoặc môn logic là khó. d/ Môn logic là không khó hoặc môn toán là không dễ. e/ Nếu không có nhiều sinh viên thích môn logic khi đó hoặc là môn toán không dễ hoặc là logic không khó.

9/ Một lớp học có 30 học sinh. Các hoc sinh tham gia vào 3 nhóm năng khiếu: nhóm Toán có 17 em, nhóm Văn có 13 em và Anh văn có 11 em, còn 10 em không tham gia vào nhóm nào. Chứng minh rằng trong lớp có em tham gia đồng thời cả 3 nhóm.

10/ Mười điểm trên một đường tròn được đánh một số phân biệt từ 0 đến 9. Chứng minh rằng, với mọi cách đánh số, luôn tìm được 3 điểm liên tiếp mà tổng các số đánh cho chúng lớn hơn 13.

11/ Dùng nguyên lý qui nạp, chứng minh các biểu thức tổng sau:

1. 



 

n

i

nnn i 1

2 6

]12][1[

1. 



 

n

i

nnnn iii 1 4

]3][2][1[ ]2][1[

1. ]!1[!][ 1

 



nii

n

i

• 1
• 

 

 

n

i ni

i 1 ]!1[

1 1 ]!1[

1. 

 

  

n

i nn

nn 1 iii ]2][1[

]3[ ]2][1[

1

1. 



 

n

i

ni ni 1

2].1[22. 1

1. 



 

n

i

ni 1

1 133.

1. 



 

n

i

nnn ii 1 6

]72][1[ ]2[

12/ Tìm công thức tính các tổng sau và sử dụng nguyên lý qui nạp để chứng minh công thức vừa tìm được

1. 





n

i

i 1

]12[

1. 





n

i

i 1

21

1. 





n

i

ii 1

]13[

1. 

 

n

i 1 ii ]1[

1

1. 





n

i

i 1

]12[ 2

1. 





n

i

ii 1

]1[

1. 



n

i

xi 1 13/ Dùng nguyên lý qui nạp, chứng minh các bất đẳng thức sau: a. n > 3: 2 n < n! b. n > 4: n 2 < 2n c. n >= 6: 4n < n 2 - 7 d. n > 10: n - 2 < [n 2 - n]/

14/ n là số nguyên lớn hơn 1, x là số thực khác 0.

Chứng minh rằng nếu x

1 x là một số nguyên thì n n x

1 x  cũng là một số

nguyên 15/ n là số nguyên lớn hơn 1. Tìm chữ số tận cùng của A 2 1 2 n   và chứng minh kết luận đó.

16/ Chứng minh rằng tích của 3 số liên tiếp luôn chia hết cho 6.

17/ Chứng minh rằng nếu n là một số nguyên lớn hơn 1, khi đó n có thể được viết dưới dạng tích của các số nguyên tố.

18/ Chứng minh rằng mọi bưu phí bằng hay lớn hơn 12 xu đều có thể tạo ra bằng các con tem 4 xu hay 5 xu.

Nguyên lý Dirichlet

19/ Chứng minh rằng trong 5 số nguyên tùy ý bao giờ cũng tìm được 3 số có tổng chia hết cho 3.

20/ Chứng minh rằng trong 11 số nguyên tùy ý bao giờ cũng tìm được 2 số mà hiệu bình phương của chúng chia hết cho 20.

21/ Chứng minh rằng trong nhóm có n 2 người tùy ý bao giờ cũng tìm được 2 người có số người quen trong nhóm bằng nhau.

12/ Cho A là l đại số bool và X khác rỗng là một tập hợp con của A. X được gọi là một đại số con của A khi các điều kiện sau đây được thỏa:

Xx 3].

Xy x2].

Xy x1].

x,y X:







 

Chứng minh rằng: a]- Nếu X được gọi là một đại số con của A thì 0 X và 1 X. b]- Nếu X khác rỗng và thỏa:

Xx 2].

Xy x1].

x,y X:





 

thì X là một đại số con của A

13/ Cho [A,R] là một đại số bool, a là một phần tử thuộc A. Xét tập hợp   }xRa/Ax{X Vậy ]R,X[ có phải là một đại số bool không? Chứng minh.

CHƯƠNG IV [Hàm bool]

1/ Lập một hàm bool 4 biến sao cho khi thay đổi giá trị của một biến bất kỳ thì giá trị của hàm cũng thay đổi theo. 2/ Hàm bool 2 biến được gọi là đối xứng nếu:

21 2  1221 ]xx[f]xx[f,Bxx Hãy xác định các hàm bool 2 biến 3/ Hàm bool n biến f được gọi là chẵn nếu:

21 n n 21 n  21 xxxfxxxfBxxx n]...[]...[,...

và được gọi là hàm lẻ nếu:

21 n n 21 n  21 xxxfxxxfBxxx n]...[]...[,... a- Có bao nhiêu hàm bool chẵn, hàm bool lẻ n biến. b- Xác định chúng trong trường hợp n=2. 4/ Chứng minh rằng với mọi hàm bool 2 biến f đều viết được dưới dạng:

  ]x1[fx ]x0[fx]xx[f 

]x0[fx]x1[fx]xx[f

:Bxx

2121 1 2

2121 1 2

2 21







5/ Có bao nhiêu hàm bool 3 biến thỏa tính chất:

321 3  132321 ]xxx[f]xxx[f,Bxxx 6/ Một kỳ thi có 4 môn a, b, c, d với hệ số tương ứng là 8, 5, 4, 3. Mỗi môn được cho điểm là 0 hoặc 1. Để được đậu phải có tổng số điểm lớn hơn 10. Một hàm bool f có giá trị là 1nếu thí sinh đậu, là 0 nếu ngược lại. Xác định bảng chân trị, dạng tuyển chuẩn tắc và dạng hội chuẩn tắc của hàm bool f. 7/ E là tập hợp các số nguyên từ 5 đến 15. Hãy tìm phủ tối tiểu của E từ các tập hợp con của nó được xác định như sau: A1: tập hợp các số nguyên tố thuộc E. A2: tập hợp các phần tử thuộc E và là ước của 140. A3: tập hợp các phần tử của E và là bội của 3. A4: tập hợp các phần tửcủa E và códạng bình phương hoặc lập phương. A5: tập hợp các phần tử của E từ 9 đến 12. A6: tập hợp các phần tử của E mà tổng các chữ số của mỗi phần tử là từ4 đến 6. 8/ Xác định bảng chân trị và hàm truyền của các mạch điện sau:

 

a

b

c

a

c

c a b

b

 c 

a

CHƯƠNG V [ Đơn giản công thức]

1/ Tìm công thức tối tiểu bằng phương pháp Karnaugh của hàm bool f có dãy nhị phân tương ứng như sau: f = 1011 1100 1111 0111

2/ Cho hai hàm bool 4 biến f và g có công thức như sau:

   ]cb][da[f  ]db][ca[g a- Hãy vẽ sơ đồ Karnaugh của f và g. b- Suy ra sơ đồ Karnaugh của  gffgh c- Tìm công thức tối tiểu của h.

3/ Tìm công thức tối tiểu bằng phương pháp Consensus của hàm bool f sau đây:

f bcd abd abc abd abcd abcd

4/ Tìm công thức tối tiểu bằng phương pháp Quine Mc. Cluskey:

 cbacbabcacbaabcf

CHƯƠNG VI [Lý thuyết chia và đồng dư]

1- Chứng minh rằng trong m số nguyên liên tiếp có duy nhất một số chia hết cho m. Từ đó suy ra tích của m số nguyên liên tiếp chia hết cho m.

2- Chứng minh rằng trong hai số chẵn liên tiếp có một và chỉ một số chia hết cho 4

3- Chứng minh rằng:

a- Tích của hai số chẵn liên tiếp chia hết cho 8. b- Tổng của ba số nguyên liên tiếp chia hết cho 3. c- Tổng lập phương của ba số nguyên liên tiếp chia hết cho 9. d- Tích của một số chính phương và số tự nhiên đứng liền trước nó chia hết cho 12.

4- Chứng minh rằng nếu m-n chia hết mp+nq thì m-n chia hết mq+np

5- Chứng minh rằng nếu ba 22 chia hết cho 3 thì a và b đồng thời chia hết cho 3.

6- Chứng minh rằng nếu  cba 333 chia hết cho 9 thì ít nhất một trong ba số a, b, c chia hết cho 3.

7- Chứng minh rằng:

 19971997 19981999 chia hết cho 4

 19981997 19991998 không chia hết cho 4

8- Cho a là số nguyên. Chứng minh rằng:

a- 3  a11a chia hết cho 6.

b- 5 aa chia hết cho 30. c-   ]1a2][1a[a chia hết cho 6.

d- 35  a4a5a chia hết cho 120.

e- Nếu ba 22 chia hết cho 3 thì a chia hết cho 3 và b chia hết cho 3.

9- Tổng của n số nguyên liên tiếp có chia hết cho n hay không? Chứng minh.

10- Cho số nguyên n 1. Tích sau đây có chia hết cho 2 n không? Chứng minh.

#######         ]nn[]1n[n]...][2n][1n[

11- Với số nguyên n 1 , dùng phép chứng minh quy nạp chứng minh rằng:

a- n  1n37 chia hết cho 9.

b- n  1n1810 chia hết cho 27.

c-  32 nn  131 chia hết cho 5.

d- n  1n45 chia hết cho 16.

e- n 3  11 n chia hết cho 6.

f- 234  n6n11n6n chia hết cho 24.

g- 12  11  2n1n2 chia hết cho 133.

c- 



 

 2835]b,a[

15]b,a[

23- Cho k và n là hai số nguyên tùy ý lớn hơn 1. Chứng minh rằng:

1. ]!n[ k là ước của ]!nk[

b]  ]!k[,]!n[ nk  là ước của ]!nk[

24- Chứng minh minh rằng với n là số tự nhiên lớn hơn 1 thì các số sau đây là hợp số:

1. n 4  4

1. n n 24  1

25- Tìm các số nguyên tố p sao cho

1. p+4 và p+8 cũng là số chính phương. b] 4p+1 là một số chính phương. c] 2p+1 là lập phương của một số nguyên.

1. 2 1p4 và 2 1p6 cũng là các số nguyên tố.

1. p vừa là tổng của hai số nguyên tố, vừa là hiệu của hai số nguyên tố.

26- Tìm tất cả các số nguyên n sao cho:

n 4  4 là một số nguyên tố.

27- Các số 3, 5, 7 là một bộ 3 số lẻ liên tiếp và đều là các số nguyên tố. Hãy tìm tất cả các bộ như vậy.

28- Chứng minh rằng nếu p và q là số nguyên tố lớn hơn 3 thì

1. 2 1p chia hết cho 24.

1. qp 22 chia hết cho 24.

29- Biết rằng p và 8p+1 là hai số nguyên tố. Chứng minh rằng 8p-1 là hợp số.

30- Biết rằng p và 2 1p8 là hai số nguyên tố. Chứng minh rằng 2 1p8 và 2  1p2p đều là số nguyên tố.

31- Biết rằng p và 2 8p là những số nguyên tố. Chứng minh rằng 3 4p cũng là một số

nguyên tố.

32- Chứng minh rằng với số nguyên m>2 giữa m và m! có ít nhất một số nguyên tố. Từ kết quả này chứng tỏ rằng tập hợp các số nguyên tố là vô hạn.

33- Cho hai số tự nhiên mn. Chứng minh rằng 2 1 2 m  và 2 n 2 +1 là nguyên tố cùng nhau. Từ kết quả này hãy chứng tỏ rằng tập hợp các số nguyên tố là vô hạn

34- Chứng minh rằng nếu n1a với a là số nguyên lớn hơn 1 thì n 2 k

35- Giả sử n là số tự nhiên lớn hơn 1 và p là số nguyên tố. Ta gọi p ]n[V là số mũ của p

trong phân tích tiêu chuẩn của n thành tích các thừa số nguyên tố. Chứng minh rằng:

1.  ppp ]n[V]m[V]mn[V

1. m chia hết cho n khi và chỉ khi  pp ]n[V]m[V , và khi đó

]n[V]m[V n

m V   ppp 

  



36- Giải phương trình:

1.  5y41x

1.  23y367x

1.  112y48x

1.  109y117x

37- Một người mua 30 con chim gồm chim sẻ, chim ngói và bồ câu với giá 30 đồng. Trong đó cứ 3 con chim sẻ giá 1 đồng, cứ 2 con chim ngói cũng giá 1 đồng, còn mỗi con bồ câu giá 2 đồng. Hỏi mỗi loại chim có mấy con?

38- Tìm các số tự nhiên có hai chữ số chia hết cho 9, và khi cộng thêm 1 thì chia hết cho 25.

39- Hỏi có bao nhiêu cách trả số tiền 78 đồng bằng hai loại giấy bạc 3 đồng và 5 đồng ?.

40- Tìm năm sinh của nhà thơ Nguyễn Du, biết rằng năm 1786 thì tuổi của ông bằng tổng các chữ số của năm ông sinh ra.

41- Giải phương trình nguyên

1.   15z5y3x

1.   25z5y4x

42- Chứng minh rằng phương trình  zyx 444 không có nghiệm nguyên thỏa mãn điều

kiện 0z,y,x.

43- Chứng minh rằng: nếu  ]m[modbdac ,  ]m[moddc và [c,m] = 1 thì  ]m[modba

44- Chứng minh rằng 19

 b11a là số nguyên khi và chỉ khi 19

 n18a là một số nguyên

45- Cho a,b,c là các số nguyên. Chứng minh rằng 100a+10b+c chia hết cho 21 khi và chỉ khi a-2b+4c chia hết cho 21.

46- Tìm số dư khi:

a- Chia 5  11532 cho 9. b- Chia 10! cho 11.

47- Cho n là số tự nhiên. Chứng minh rằng 2 n5  1 chia hết cho 31.

48- Tìm số dư khi chia a cho 73, biết rằng:



 





 ]73[mod69a

]73[mod2a 101

100

49- Chứng minh rằng  55552222 22225555 chia hết cho 7

50- Với n là số tự nhiên chứng minh rằng:

1. 



 

 ]8[mod1x

]6[modax

1. 



 

 ]8[modax

]6[mod2x

Chương 1: Mệnh đề và Vị từ

Câu 1: Không lập bảng chân trị, hãy sử dụng các tương đương logic để chứng minh các mệnh đề sau là tương đương:

1.     Trueqpqp b]    Trueqqp

####### c]        Truerrqrpqp

1.         Falserqpqpqqr e]             Falsepsrsrqrqrpqpp f]             Flaseqrqqpqrqqpqp

Câu 2: Không lập bảng chân trị, hãy sử dụng các tương đương logic để chứng minh các mệnh đề sau là tương đương:

1.       rqprqrp b]       rqprpqp  c]          qrqqpqqpqp  d]         rqpqppqqr  e]           srsrqrqprpqpp 

Câu 3: Dịch các câu sau đây thành các biểu thức logic bằng cách sử dụng các vị từ, lượng từ và các liên từ. a] Không có ai là hoàn hảo b] Không phải mọi người đều hoàn hảo c] Tất cả các bạn của bạn là hoàn hảo. d] Một trong số các bạn của bạn là hoàn hảo. e] Mọi người đều là bạn của bạn và đều hoàn hảo. f] Không phải mọi người đều là bạn của bạn hoặc có ai đó không hoàn hảo.

Câu 4: Cho p và q là hai mệnh đề: p: Bạn lái xe với tốc độ trên 65km/h q: Bạn bị phạt vì vượt quá tốc độ cho phép. Hãy viết các mệnh đề sau bằng cách dùng p, q và các liên từ logic a] Bạn không lái xe với tốc độ trên 65km/h. b] Bạn lái xe với tốc độ trên trên 65km/h nhưng bạn không bị phạt vì vượt quá tốc độ cho phép. c] Bạn sẽ bị phạt vì vượt quá tốc độ cho phép nếu bạn lái xe với tốc độ trên 65km/h. d] Nếu bạn không lái xe với tốc độ trên 65km/h thì bạn sẽ không bị phạt vì vượt quá tốc độ cho phép. e] Lái xe với tốc độ trên 65km/h là đủ để bị phạt vì vượt quá tốc độ cho phép.