Giáo trình Cấu trúc rời rạc - Bài tập chương 1: Luận lý mệnh đề
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
Bài tập chương 1
Luận lý mệnh đề
1 Dẫn nhập
Trong bài tập dưới đây, chúng ta sẽ làm quen với cách diễn đạt trong luận lý mệnh đề và việc diễn
dịch chúng trong ngôn ngữ thông thường. Sinh viên cần ôn lại lý thuyết của chương 1 trước khi làm
các bài tập bên dưới.
2 Bài tập bắt buộc
Câu 1.
Trong các câu sau, câu nào là mệnh đề? Xác định giá trị chân trị của mệnh đề đó rồi tìm phủ định
của nó.
Ví dụ. Miami là thủ phủ của bang Florida.
→ là mệnh đề Đúng.
→ Phủ định: Miami không phải là thủ phủ của bang Florida.
a) “Phan-xi-păng là ngọn núi cao nhất Việt Nam.”
b) “Hai số nguyên tố cùng nhau chỉ có ước chung là 1.”
c) “Tích 3 số nguyên liên tiếp thì chia hết cho 3.”
d) “Hãy đứng lên!”
e) “x+1=0”
f) “Hình lập phương có 8 đỉnh.”
g) “0 là một số dương.”
h) “Phương trình: x2 + 5x + 6 = 0 vô nghiệm.”
i) “2 có phải là số nguyên tố không?”
j) “Phương trình mx2 + 2x − 1 = 0 có nghiệm duy nhất khi và chỉ khi m=-1.”
k) “Có số nguyên tố là số chẵn.”
l) “x2 + 1 > 0.”
m) “Bao giờ lớp mình đi dã ngoại?”
n) “Thủy ngân không phải là kim loại.”
o) “320 > 230.”
p) “Máy bay là phương tiện di chuyển nhanh nhất”
q) “Năm 2002 là năm nhuận.”
r) “Có vô số số nguyên tố.”
s) “210 − 1 chia hết cho 11.”
t) “Cấm hút thuốc lá nơi công cộng.”
Giáo trình Cấu Trúc Rời Rạc
Trang 1/10
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
u) “Mọi số nguyên dương chẵn lớn hơn 2 là tổng của hai số nguyên tố.”
v) “Số x là nguyên tố nếu nó không có ước số khác 1, x.”
Câu 2.
Gọi P, Q, R là các mệnh đề:
• P: “Bình đang học Toán”.
• Q: “Bình đang học Tin học”.
• R: “Bình đang học Anh Văn”.
Hãy viết lại các mệnh đề dưới đây dưới dạng hình thức trong đó sử dụng các phép nối.
Ví dụ. Bình đang học Toán và Anh Văn nhưng không học Tin học: P ∧ R ∧ ¬Q
a) Bình đang học Toán và Tin học nhưng không học cùng một lúc Tin học và Anh Văn.
b) Không đúng là Bình đang học Anh Văn mà không học Toán.
c) Không đúng là Bình đang học Anh Văn hay Tin học mà không học Toán.
d) Bình không học Tin học lẫn Anh Văn nhưng đang học Toán.
Câu 3.
Lập bảng chân trị cho các mệnh đề sau:
Ví dụ. ¬p → (p ∨ q)
p
T
T
F
F
q
¬p p ∨ q ¬p → (p ∨ q)
T
F
T
F
F
F
T
T
T
T
T
F
T
T
T
F
Ví dụ. ¬p → (¬q ∨ r)
p
q
r
¬p ¬q ¬q ∨ r ¬p → (¬q ∨ r)
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
F
F
F
F
T
T
T
T
F
F
T
T
F
F
T
T
T
F
T
T
T
F
T
T
T
F
T
T
T
F
T
T
a) (p ∧ q) → ¬q
b) (p ∨ r) → (r ∨ ¬p)
c) (p → q) ∨ (q → p)
d) (p ∨ ¬q) ∧ (¬p ∨ q)
Giáo trình Cấu Trúc Rời Rạc
Trang 2/10
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
e) (p → ¬q) ∨ (q → ¬p)
f) ¬(¬p ∧ ¬q)
g) (p ∨ q) → (p ⊕ q)
h) (p ∧ q) ∨ (r ⊕ q)
Câu 4.
Hãy chỉ ra hằng đúng trong các dạng mệnh đề sau:
Gợi ý: dùng bảng chân trị.
a) (p ∨ q) → (p ∧ q)
b) (p ∧ q) → (p ∨ q)
c) p → (¬q → p)
d) p → (p → q)
e) p → (p → p)
f) (p → q) → [(p → r) → (q → r)]
Câu 5.
Lấy phủ định rồi đơn giản mệnh đề phủ định đó.
Ví dụ. p → (¬q ∧ r)
[Bằng cách sử dụng bảng chân trị, ta dễ dàng chứng minh được hai dạng mệnh đề p → q và ¬p ∨ q
là tương đương logic]
Phủ định: ¬(p → (¬q ∧ r))
≡ ¬(¬p ∨ (¬q ∧ r))
≡ p ∧ ¬(¬q ∧ r)
≡ p ∧ (q ∨ ¬r)
a) p ∧ (q ∨ r) ∧ (¬p ∨ ¬q ∨ r)
b) (p ∧ q) → r
c) p ∨ q ∨ (¬p ∧ ¬q ∧ r)
d) [[[(p ∧ q) ∧ r] ∨ [(p ∧ r) ∧ ¬r]] ∨ ¬q] → s
Câu 6.
Chứng minh các mệnh đề sau đây là tương đương logic.
Gợi ý: dùng bảng chân trị hoặc dùng các phép biến đổi tương đương logic mệnh đề.
a) ¬(p ↔ q) và ¬p ↔ q
b) (p → q) ∧ (p → r) và p → (q ∧ r)
c) (p → r) ∧ (q → r) và (p ∨ q) → r
d) (p → q) ∨ (p → r) và p → (q ∨ r)
Giáo trình Cấu Trúc Rời Rạc
Trang 3/10
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
e) ¬p → (q → r) và q → (p ∨ r)
f) p ↔ q và (p → q) ∧ (q → p)
Câu 7.
Hai mệnh đề được cho dưới đây có tương đương logic nhau không? Chứng minh?
a) p ∧ (p → q) và p ∧ q
b) p → q và ¬p ∨ (p ∧ q)
c) p → q và ¬p → ¬q
d) ¬p và ¬(p ∨ q) ∨ (¬p ∧ q)
e) [(p ↔ q) ∧ (q ↔ r) ∧ (r ↔ p)] và [(p → q) ∧ (q → r) ∧ (r → p)]
f) [(p ∧ q) ∨ (q ∧ r) ∨ (r ∧ p)] và [(p ∨ q) ∧ (q ∨ r) ∧ (r ∨ p)]
Câu 8.
Xác định chân trị của các mệnh đề sau. Hãy phát biểu mệnh đề đảo và phản đảo của chúng.
a) “Nếu ABCD là hình chữ nhật thì AB vuông góc CD.”
b) “Nếu 14 là số lẻ thì 15 chia hết cho 4.”
c) “Hai tam giác bằng nhau thì có diện tích bằng nhau.”
d) “Phương trình bậc hai ax2 + bx + c = 0 có tích a.c < 0 thì nó có nghiệm.”
e) “Nếu hai số x và y đều chia hết cho n thì (x + y) cũng chia hết cho n.”
f) “Nếu 45 tận cùng là 5 thì 45 chia hết cho 5.”
√
√ √
g) “Nếu 2 là số vô tỷ thì 2. 2 là số vô tỷ.”
h) “Nếu Pythagore là người Pháp thì Việt Nam thuộc về châu Á.”
i) “Nếu 3n + 2 là số nguyên lẻ thì n là số nguyên lẻ.”
j) “Nếu 8 < 9 thì 5 là một số nguyên tố.”
k) “Một tứ giác là hình thoi khi nó có 2 đường chéo vuông góc.”
l) “Nếu 5 < 3 thì 7 là một số nguyên tố.”
Câu 9.
Tìm chân trị các mệnh đề sau (có giải thích ngắn gọn):
a) “∀x ∈ N, x2 + 5x + 6 không phải là số nguyên tố.”
b) “∃x ∈ R, x2 + x + 1 ≤ 0”
c) “∃n ∈ N, (n3 − n) không là bội của 3.”
d) “∀n ∈ N∗, n2 − 1 là bội của 3.”
e) “∀x, ∀y ∈ R, x2 + y2 > 2xy”
f) “∃r ∈ Q, 3 < r < π”
Giáo trình Cấu Trúc Rời Rạc
Trang 4/10
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
g) “∃n ∈ N, n2 + 1 chia hết cho 8”
h) “∀x ∈ R, |x| < 3 ⇔ x2 < 9”
i) “∃a, b ∈ R, (a + b)2 > 2(a2 + b2)”
j) “Mọi số thực đều dương.”
k) “Có kim loại ở thể lỏng.”
l) “Mọi tam giác đều đều bằng nhau.”
m) “Tất cả các chất khí đều không dẫn điện.”
n) “Có những tứ giác không có đường tròn ngoại tiếp.”
o) “Tồn tại số tự nhiên n, để với mọi số thực x, ta có f(x) = x2 − 2x + n nhận giá trị không âm.”
p) “Với mọi số nguyên dương x, với mọi số nguyên dương y ta đều có x ≤ y.”
q) “Với mọi số nguyên dương x, có một số nguyên dương y để x ≤ y.”
r) “Có ít nhất một số nguyên dương x để với mọi số nguyên dương y ta đều có x ≤ y.”
s) “Tồn tại số nguyên dương x và một số nguyên dương y để có x ≤ y.”
Câu 10.
Sáu đội bóng A, B, C, D, E, F tham dự một giải vô địch. Dưới đây là 5 khẳng định khác nhau về 2
đội có mặt trong trận chung kết:
a. A và C
b. B và E
c. B và F
d. A và F
e. A và D
Biết rằng có 4 khẳng định đúng một nửa và một khẳng định sai hoàn toàn. Hãy cho biết 2 đội nào
được thi đấu trong trận chung kết?
Câu 11.
Trên màn hình có 20 viên bi màu xanh, 18 viên bị màu đỏ, 13 viên bi màu vàng. Một sinh viên điều
khiển các viên bi chạm nhau theo luật trò chơi như sau: nếu 2 viên bị khác màu chạm nhau thì cả 2
sẽ chuyển sang màu còn lại. Hỏi có khả năng nào để sinh viên đó chuyển toàn bộ số bi đó sang cùng
1 màu hay không?
Câu 12.
Có n đội bóng dự giải, đấu vòng tròn một lượt. Đội thắng được 2 điểm, đội hòa được 1 điểm và đội
thua được 0 điểm. Các đội có cùng số điểm sẽ được xếp hạng theo các chỉ số phụ. Kết thúc giải, đội
vô địch: 8 điểm, đội thứ hai: 6 điểm, đội thứ ba: 5 điểm. Các đội còn lại có số điểm khác nhau. Tìm
số đội dự giải và điểm của các đội còn lại.
Giáo trình Cấu Trúc Rời Rạc
Trang 5/10
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
3 Bài tập làm thêm
Câu 13.
Trong các khẳng định sau, cho biết khẳng định nào là mệnh đề:
a) Trần Hưng Đạo là một vị tướng tài.
b) x + 1 là một số nguyên dương.
c) 9 là một số chẵn.
d) Hôm nay trời đẹp làm sao!
e) Nếu bạn đến trể thì tôi sẽ đi xem đá bóng trước.
Câu 14.
Trong các câu dưới đây, câu nào là một mệnh đề? Xác định giá trị chân lý của mệnh đề đó và tìm
phủ định của nó.
a) 1+1=2.
b) Hãy tìm giá trị của x nếu biết x + 2 = 5
c) Đây là đường một chiều.
d) Bây giờ là mấy giờ?
e) Đất đỏ bazane trồng cây rất tốt.
f) x + y = y + z nếu x = z.
g) Hôm nay là thứ năm
h) Không có ô nhiễm ở Bảo Lộc, nhưng có nhiều ô nhiễm ở Đà Lạt.
i) Mùa hè ở thành phố Seville thì nóng và nắng.
Câu 15.
Cho p và q là hai mệnh đề với:
• p: ’Hùng thích đọc sách’
• q: ’Hùng học giỏi’
Diễn đạt các mệnh đề sau bằng các câu thông thường:
a) ¬p
b) p → q
c) p ∨ q
d) p ∧ q
e) p ↔ q
f) ¬p → ¬q
g) ¬p ∨ (p ∧ q).
Câu 16.
Gọi P, Q là các mệnh đề:
Giáo trình Cấu Trúc Rời Rạc
Trang 6/10
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
• P: “Minh giỏi Toán”
• Q: “Minh yếu Anh văn”
Hãy viết lại các mệnh đề sau dưới dạng hình thức trong đó sử dụng các phép nối.
(Giả sử đảo nghĩa của học ’giỏi’ là học ’yếu’.)
a) Minh giỏi Toán nhưng yếu Anh văn
b) Minh yếu cả Toán lẫn Anh văn
c) Minh giỏi Toán hay Minh vừa giỏi Anh văn nhưng vừa yếu Toán
d) Nếu Minh giỏi Toán thì Minh giỏi Anh văn
e) Minh giỏi Toán và Anh văn hay Minh yếu Toán nhưng giỏi Anh
Câu 17.
Hãy lấy phủ định các mệnh đề sau:
a) Ngày mai nếu trời mưa hay trời lạnh thì tôi sẽ không ra ngoài.
b) 15 chia hết cho 3 nhưng không chia hết cho 4.
c) Hình tứ giác này không phải là hình chữ nhật mà cũng không phải là hình thoi.
d) Nếu An không đi làm ngày mai thì sẽ bị đuổi việc.
e) Mọi tam giác đều có góc bằng 60◦
Câu 18.
Cho biết chân trị các mệnh đề sau:
a) π = 2 và tổng các góc trong tam giác bằng 180◦
b) π = 3, 1416 kéo theo tổng các góc trong tam giác bằng 170◦
c) π = 3 kéo theo tổng các góc trong tam giác bằng 170◦
d) Nếu 2 > 3 thì nước sôi ở 100◦
e) Nếu 3 < 4 thì 4 < 3
f) Nếu 4 < 3 thì 3 < 4
Câu 19.
Lập bảng giá trị chân lý cho các mệnh đề phức hợp sau đây:
a) p ∧ ¬q
b) p ∨ ¬q
c) p ⊕ ¬q
d) ¬p ⊕ ¬q
e) (p ∧ ¬q) → q
f) (p ∧ q) → (p ∨ q)
g) (p ∨ q) → (p ⊕ q)
h) (p → q) ↔ (¬q → ¬p)
Giáo trình Cấu Trúc Rời Rạc
Trang 7/10
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
i) (p → q) → (q → p)
j) (p ∨ q) ∧ r
k) (p ∧ q) ∨ ¬r
l) (p ∧ q) ∨ (r ⊕ q)
Câu 20.
Dùng bảng chân lý chứng minh các mệnh đề sau là hằng đúng:
a) (p ∧ ¬q) → q
b) p → (p ∨ q)
c) ¬p → (p → q)
d) (p ∧ q) → (p → q)
e) ¬(p → q) → p
f) ¬(p → q) → ¬q
g) [¬p ∧ (p ∨ q)] → q
h) [(p → q) ∧ (q → r)] → (p → r)
i) [p ∧ (p → q)] → q
j) [(p ∨ q) ∧ (p → r) ∧ (q → r)] → r
k) ¬(p ⊕ q) ∨ (p ↔ q)
Câu 21.
Lấy phủ định các mệnh đề sau:
a) Với mọi số nguyên n, nếu n không chia hết cho 2 thì n là số lẽ.
b) Nếu bình phương một số nguyên là lẻ thì số nguyên ấy là lẻ.
c) Nếu k, l, m là các số nguyên sao cho k − m và m − n là số lẻ thì k − n là số chẵn.
d) Nếu x là số thực sao cho x2 > 16 thì x < −4 hay x > 4.
e) Với mọi số thực x, nếu |x − 3| < 7 thì −4 < x < 10.
Câu 22.
Đối ngẫu của một mệnh đề phức hợp chỉ chứa các toán tử logic ∧, ∨ và ¬ là một mệnh đề nhận được
bằng cách thay mỗi ∨ bằng ∧, mỗi ∧ bằng ∨, mỗi T bằng F và mỗi F bằng T. Đối ngẫu của s được
ký hiệu là s∗.
Tìm đối ngẫu của các mệnh đề sau:
a) p ∧ ¬q ∧ r
b) (p ∧ q ∧ r) ∨ s
c) ¬p ∧ (p ∨ q)
d) (p ∧ q) ∨ (¬p ∨ q)
e) ¬(p ∧ T) ∨ (q ∨ T)
Giáo trình Cấu Trúc Rời Rạc
Trang 8/10
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
Câu 23.
Chứng minh rằng (s∗)∗ = s.
Câu 24.
Lập mệnh đề phức hợp gồm các mệnh đề p, q, và r sao cho nó đúng khi p và q là đúng và r là sai,
nhưng là sai trong mọi trường hợp còn lại (Gợi ý: dùng hợp của mọi mệnh đề hoặc phủ định của nó).
Câu 25.
Lập mệnh đề phức hợp gồm các mệnh đề p, q, và r sao cho nó đúng chỉ khi hai trong ba mệnh đề p, q
và r là đúng và sai trong mọi trường hợp còn lại (Gợi ý: lập tuyển các hội. Đối với mỗi tổ hợp các giá
trị sao cho mệnh đề là đúng, ta đưa vào một hội. Mỗi một hội này lại chứa ba mệnh đề p, q, r hoặc
phủ định của chúng).
Câu 26.
Phát biểu mệnh đề đảo và phản đảo của các mệnh đề kéo theo sau đây:
a) Nếu hôm nay trời không mưa, tôi sẽ đi xin việc làm.
b) An chỉ đến lớp vào đầu học kỳ và mỗi khi có kỳ thi.
c) Một số là nguyên dương nếu như giá trị của nó lớn hơn không.
d) Số chính phương là một số nguyên dương nếu giá trị của nó bằng bình phương của một số nguyên
khác.
e) Dàn mướp sẽ có nhiều trái to nếu như trời chỉ mưa nhiều trong vài ngày.
Câu 27.
Một nhà thám hiểm X bị một nhóm cướp biển bắt cóc. Trong nhóm cướp biển này, có hai loại người:
loại luôn nói thật và loại luôn nói dối. Ông tướng cướp tuyên bố rằng nếu nhà thám hiểm không xác
định được tên cướp Y nào đó trong bọn họ luôn luôn nói dối hay nói thật và ông X chỉ được phép
hỏi tên Y một câu hỏi duy nhất.
a) Hãy giải thích tại sao câu hỏi “Anh là người nói dối” không mang lại kết quả?
b) Tìm câu hỏi mà nhà thám hiểm X đã dùng để xác định tên cướp Y là luôn nói dối hay nói thật.
Câu 28.
(Zebra puzzle). Năm người đàn ông có quốc tịch khác nhau và làm các công việc khác nhau sống
trong dãy năm căn nhà sát nhau. Những ngôi nhà này sơn màu khác nhau. Những người này có vật
nuôi khác nhau và cũng thích các loại thức uống khác nhau.
Hãy xác định xem ai sở hữu ngựa vằn và ai là người thích uống nước khoáng, với các thông tin như
sau:
a) Người Anh sống ở ngôi nhà màu đỏ.
b) Người Tây Ban Nha có một con chó.
c) Người Nhật là họa sĩ.
d) Người Ý uống trà.
e) Người Na Uy sống trong ngôi nhà đầu tiên bên trái.
f) Ngôi nhà xanh lá cây nằm ngay bên phải nhà màu trắng.
g) Nhiếp ảnh gia nuôi ốc sên.
Giáo trình Cấu Trúc Rời Rạc
Trang 9/10
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
h) Nhà ngoại giao sống trong căn nhà màu vàng.
i) Người ở ngôi nhà chính giữa uống sữa.
j) Chủ nhân ngôi nhà màu xanh lá cây uống cà phê.
k) Nhà của người Na Uy kế bên ngôi nhà màu xanh dương.
l) Nghệ sĩ vĩ cầm uống nước cam.
m) Có một con cáo trong ngôi nhà kế bên nhà nhà vât lý.
n) Con ngựa sống trong nhà kế bên nhà của nhà ngoại giao.
[Gợi ý: Lập bảng với hàng là những người đàn ông, cột là màu căn nhà, công việc, thú nuôi, và thức
uống ưa thích. Dùng suy luận logic để xác định các ý trong bảng.]
4 Tổng kết
Thông qua các bài tập trong phần này, chúng ta đã làm quen với việc sử dụng, khai báo các mệnh đề
trong luận lý mệnh đề và việc diễn dịch chúng trong ngôn ngữ thông thường. Và các bài tập này cũng
đã giúp chúng ta phần nào hiểu thêm về lý thuyết luận lý mệnh đề (tham khảo chi tiết trong chương
1).
Giáo trình Cấu Trúc Rời Rạc
Trang 10/10
10 trang
26/04/2022
4780
Bạn đang xem tài liệu "Giáo trình Cấu trúc rời rạc - Bài tập chương 1: Luận lý mệnh đề", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_cau_truc_roi_rac_bai_tap_chuong_1_luan_ly_menh_de.pdf
