Giáo trình Toàn rời rạc 1 - Bài tập chương 1: Luận lý mệnh đề và luận lý vị từ
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 đề và luận lý vị từ
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ý học bao gồm
luận lý mệnh đề và luận lý vị từ 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 2, phần luận lý mệnh đề và luận lý vị từ trước
khi làm bài tập bên dưới.
Cho các vị từ như sau.
• F(x, y) : x là cha của y,
• M(x, y) : x là mẹ của y,
• S(x, y) : x là chị em gái của y,
• B(x, y) : x là anh em trai của y,
• H(x, y) : x là người hôn phối (chồng hoặc vợ) của y,
• O(x, y) : x lớn tuổi hơn y.
2 Bài tập mẫu
Hãy xác định các biểu thức luận lý vị từ để diễn đạt các câu sau đây:
Câu 1.
‘Mọi người đều có một ông nội, một ông ngoại, một bà nội và một bà ngoại’.
Lời giải.
∀x∃y∃z∃y1∃y2∃z1∃z2 (F(y, x) ∧ M(z, x) ∧ F(y1, y) ∧ M(y2, y) ∧ F(z1, z) ∧ M(z2, z))
2
2
Câu 2.
‘Bất cứ người nào là cha thì sẽ không thể là mẹ được’.
Lời giải. ∃x∃y∀z(F(x, y) → ¬M(x, z))
Hãy diễn dịch những mệnh đề luận lý vị từ sau đây.
Giáo trình Toán Rời Rạc 1
Trang 1/12
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 3.
B(c, m) ∧ (O(c, m) ∨ O(m, c))
Lời giải. c hoặc là anh hoặc là em trai của m.
2
Câu 4.
B(c, m) ∧ F(a, m) → O(a, c) ∧ F(a, c)
Lời giải. Nếu c là anh em trai của m và a là cha của m, thì a lớn tuổi hơn c và a là cha
của c.
2
3 Bài tập cần giải
Hãy xác định các biểu thức luận lý vị từ để diễn đạt các câu sau đây:
Câu 5.
‘Anh ta có chị gái và em trai’.
Lời giải.
∃x∃y(S(x, m) ∧ O(x, m) ∧ B(y, m) ∧ ¬O(y, m))
2
Câu 6.
‘Tất cả anh em trai của cô ta đều nhỏ tuổi hơn cô ấy’.
Lời giải.
∀x(B(x, m) → ¬O(x, m))
2
Câu 7.
‘Thuyên chỉ có duy nhất một người chồng’.
Lời giải.
∃x∀y H(x, Thuyen) ∧ H(y, Thuyen) → (x = y)
hoặc
∃x∀y H(x, Thuyen) ∧ (x = y) → ¬H(y, Thuyen)
2
2
Câu 8.
‘Một trong những chị em gái của anh ta thì nhỏ tuổi hơn anh ấy’.
Lời giải.
∃x∀y(S(x, m) ∧ ¬O(x, m) ∧ S(y, m) ∧ (x = y) → O(y, m))
Hãy diễn dịch những mệnh đề luận lý vị từ sau đây.
Câu 9.
∀x∀y(S(x, m) ∧ B(c, y) → x = y)
Giáo trình Toán Rời Rạc 1
Trang 2/12
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
Lời giải.
Bất cứ ai là chị em của m, thì c cũng là anh em của người đó.
2
Câu 10.
∃x((S(x, m) ∨ H(c, x)) ∨ ∃x(H(x, m) ∧ O(x, m)))
Lời giải.
Có một người là chị của m hoặc c là chồng chị ta, hoặc có một người là chồng của m và
lớn tuổi hơn m.
2
Câu 11.
∀x∀y(S(x, m) ∧ S(y, m) → O(x, y) ∨ O(y, x))
Lời giải.
Tất cả các chị em của m đều lớn tuổi hoặc nhỏ tuổi hơn nhau.
2
Câu 12.
Chứng minh các mệnh đề sau đây tương đương:
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)
e) ¬p → (q → r) và q → (p ∨ r)
f) p ↔ q và (p → q) ∧ (q → p)
Lời giải. Dùng bảng chân lý:
p
q
r
¬p p → q p → r q → r q → p p ∧ r p ∨ r q ∧ r 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
T
T
F
F
T
T
T
T
T
F
T
F
T
T
T
T
T
F
T
T
T
F
T
T
T
T
T
T
F
F
T
T
T
F
T
F
F
F
F
F
T
T
T
T
T
F
T
F
T
F
F
F
T
F
F
F
T
T
T
F
T
T
T
F
(a) b) (c)
Giáo trình Toán Rời Rạc 1
Trang 3/12
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
(a)
(b)
(c)
p
q
r
¬(p ↔ q) ¬p ↔ q (p → q) ∧ (p → r) p → (q ∧ r) (p → r) ∧ (q → r) (p ∨ r) → 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
T
T
T
T
F
F
F
F
T
T
T
T
F
F
T
F
F
F
T
T
T
T
T
F
F
F
T
T
T
T
T
F
T
F
T
F
T
T
T
F
T
F
T
T
T
T
(d) (e) (f)
(d)
(e)
(f)
p
q
r
(p → q) ∨ (p → r) p → (q ∨ r) ¬p → (q → r) q → (p ∨ r) p ↔ q (p → q) ∧ (q → p)
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
T
T
T
F
T
T
T
T
T
T
T
F
T
T
T
T
T
T
T
T
T
F
T
T
T
T
T
T
T
F
T
T
T
T
F
F
F
F
T
T
T
T
F
F
F
F
T
T
KL: (c) sai
2
Câu 13.
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) Miami là thủ phủ của bang Florida.
b) 1+1=2.
c) Hãy tìm giá trị của x nếu biết x + 2 = 5
d) Đây là đường một chiều.
e) Bây giờ là mấy giờ?
f) Đất đỏ bazane trồng cây rất tốt.
g) x + y = y + z nếu x = z.
h) Hôm nay là thứ năm
Giáo trình Toán Rời Rạc 1
Trang 4/12
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) Không có ô nhiễm ở Bảo Lộc, nhưng có nhiều ô nhiễm ở Đà Lạt.
j) Mùa hè ở thành phố Seville thì nóng và nắng.
Lời giải.
a) là mệnh đề T.
Phủ định: Miami không phải là thủ phủ của bang Florida.
b) là mệnh đề T.
Phủ định: 1+1 = 3.
c) không là mệnh đề, vì không phải là phát biểu.
d) không là mệnh đề, vì không xác định đường nào.
e) không là mệnh đề. vì không phải là phát biểu.
f) là mệnh đề T.
phủ định: Đất đỏ bazane trồng cây rất xấu.
g) không là mệnh đề, vì có chứa biến giá trị. Tuy nhiên, nếu ta ngầm định phát biểu này
đang nhắc đến ∀x, y, z ∈ R, một việc rất thường xảy ra trong toán học, thì đây là một
mệnh đề.
h) không là mệnh đề, vì chưa xác định điểm thời gian
i) là mệnh đề, người giải chưa rõ chân trị vì không có điều kiện kiểm tra.
Phủ định: Có nhiều ô nhiễm ở Bảo Lộc, và không có ô nhiễm ở Đà Lạt.
j) là mệnh đề, người giải chưa rõ chân trị vì không có điều kiện kiểm tra.
Phủ định: Mùa hè ở thành phố Seville thì không nóng hoặc không có nắng.
2
Câu 14.
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
Giáo trình Toán Rời Rạc 1
Trang 5/12
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) p ∨ q
d) p ∧ q
e) p ↔ q
f) ¬p → ¬q
g) ¬p ∨ (p ∧ q).
Lời giải.
a) Hùng không thích đọc sách
b) Nếu Hùng thích đọc sách thì Hùng học giỏi
c) Hùng thích đọc sách hoặc Hùng học giỏi
d) Hùng thích đọc sách và Hùng học giỏi.
e) Nếu Hùng thích đọc sách thì Hùng học giỏi, và ngược lại, Hùng học giỏi thì Hùng thích
đọc sách.
f) Nếu Hùng không thích đọc sách thì Hùng không học giỏi
g) Hùng không thích đọc sách hoặc Hùng thích đọc sách và Hùng học giỏi.
2
Câu 15.
Cho vị từ N(x) “x đã từng đi chơi Đà Lạt” với tập vũ trụ là toàn bộ sinh viên trong lớp
Toán rời rạc 1.
Hãy phát biểu các vị từ sau:
a) ∃xN(x)
b) ∀xN(x)
c) ¬∃xN(x)
d) ∃x¬N(x)
e) ¬∀xN(x)
f) ∀x¬N(x)
Lời giải.
Giáo trình Toán Rời Rạc 1
Trang 6/12
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
a) Có sinh viên trong lớp Toán rời rạc 1 chưa đi chơi Đà Lạt.
b) Tất cả sinh viên trong lớp Toán rời rạc 1 đều đã từng đi chơi Đà Lạt.
c) Không tồn tại sinh viên nào trong lớp Toán rời rạc 1 đã từng đi chơi Đà Lạt.
d) Có một sinh viên trong lớp Toán rời rạc 1 chưa từng đi chơi Đà Lạt.
e) Không phải tất cả sinh viên trong lớp Toán rời rạc 1 đều đã từng đi chơi Đà Lạt.
f) Tất cả sinh viên trong lớp Toán rời rạc 1 đều chưa từng đi chơi Đà Lạt.
2
Câu 16.
Dịch các bản mô tả sau đây sang tiếng Việt trong đó F(p) là “Máy in p bị hỏng”, B(p) là
“Máy in p đang bận in tài liệu khác”, L(j) là “Việc in j đã bị mất”, và Q(j) là “Việc in j
đang trong hàng đợi.”
a) ∃p(F(p) ∧ B(p)) → ∃jL(j)
b) ∀pB(p) → ∃jQ(j)
c) ∃j(Q(j) ∧ L(j)) → ∃pF(p)
d) (∀pB(p) ∧ ∀jQ(j)) → ∃jL(j)
Lời giải.
a) Nếu có một máy in nào đó bị hỏng trong khi đang bận in tài liệu thì chắc chắn sẽ có
tài liệu bị mất.
b) Nếu tất cả máy in đều đang bận in tài liệu thì sẽ có tài liệu đang đợi được in.
c) Nếu một tài liệu đang được đợi in nhưng lại bị mất, chứng tỏ có máy in nào đó đã bị
hỏng.
d) Khi tất cả các máy in đều đang bận in tài liệu khác, mà tất cả các công việc in vẫn phải
chờ, thì sẽ có một việc in nào đó bị mất.
2
Giáo trình Toán Rời Rạc 1
Trang 7/12
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
4 Bài tập khác
Câu 17.
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)
i) (p → q) → (q → p)
j) (p ∨ q) ∧ r
k) (p ∧ q) ∨ ¬r
l) (p ∧ q) ∨ (r ⊕ q)
Câu 18.
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
Giáo trình Toán Rời Rạc 1
Trang 8/12
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) [(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 19.
Đố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)
Câu 20.
Chứng minh rằng (s∗)∗ = s.
Câu 21.
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 22.
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 23.
Tại sao đối ngẫu của hai mệnh đề phức hợp tương đương cũng là tương đương, nếu các
mệnh đề phức hợp đó chỉ chứa các toán tử ∧, ∨ và ¬?
Giáo trình Toán Rời Rạc 1
Trang 9/12
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 24.
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 25.
Chuyển các câu sau sang vị từ, lượng từ và toán tử logic:
a) Khi ổ cứng còn ít hơn 30 GB, một thông điệp cảnh báo sẽ được gửi tới mọi người dùng.
b) Không được mở bất kỳ thư mục nào trong hệ thống tập tin, cũng như không được đóng
tập tin nào lại khi phát hiện có lỗi hệ thống.
c) Không được sao lưu hệ thống tập tin nếu có một người nào đó đang đăng nhập vào hệ
thống.
d) Đoạn phim Youtube sẽ được buffer khi còn ít nhất 8 MB bộ nhớ và tốc độ đường tuyền
tối thiểu là 56 kbits/s.
Câu 26.
Chuyển các câu sau sang vị từ, lượng từ và toán tử logic:
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ả bạn bè của bạn đều hoàn hảo.
d) Ít nhất có một đứa 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à họ hoàn hảo.
f) Không phải tất cả mọi người là bạn của bạn hoặc có ai đó không hoàn hảo.
Giáo trình Toán Rời Rạc 1
Trang 10/12
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 27.
Kiểm tra các suy luận sau là đúng hay sai:
a) Những ai ăn nhiều rau xanh hàng ngày sẽ khỏe mạnh. Dung không khỏe, vậy Dung
không ăn nhiều rau xanh hàng ngày.
b) Mọi người khi vào học đại học đều từng ở Ký túc xá. Hải chưa bao giờ ở Ký túc xá,
nên Hải chưa từng học đại học.
c) Xe tay ga rất dễ đi. Xe của Minh không phải xe tay ga. Vậy xe Minh không dễ đi.
d) Tôi thích tất cả các phim hành động. Tôi thích phim Titanic. Vậy Titanic là phim hành
động.
e) Nếu n là số thực, nếu n > 1, thì n2 > 1. Vậy giả thiết n2 > 1 thì n > 1.
f) Nếu n là số thực và n > 3 thì n2 > 9. Giả sử n2 ≤ 9 suy ra n ≤ 3.
Câu 28.
Các đặc điểm sau có phi mâu thuẫn không?
a) “Hệ thống ở trạng thái nhiều người dùng nếu và chỉ nếu nó hoạt động bình thường. Nếu
một hệ thống hoạt động bình thường thì hạt nhân của nó cũng hoạt động. Hạt nhân
không hoạt động hoặc hệ thống ở dạng ngắt. Nếu hệ thống không ở trạng thái nhiều
người dùng thì nó ở trạng thái ngắt. Hệ thống hiện không ở trạng thái ngắt.”
b) “Nếu hệ thống tập tin không bị khóa thì các thông báo mới sẽ phải xếp hàng chờ. Nếu
hệ thống tập tin không bị khóa thì hệ thống đó sẽ họat động bình thường và ngược lại.
Nếu các thông báo mới không phải xếp hàng chờ thì chúng sẽ được gửi đến bộ đệm
thông báo. Nếu hệ thống tập tin không bị khóa, thì các thông báo mới sẽ được gửi đến
bộ đệm thông báo. Các thông báo mới sẽ không được gửi đến bộ đệm thông báo.”
Câu 29.
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.
Giáo trình Toán Rời Rạc 1
Trang 11/12
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 30.
(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.
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.]
5 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ý 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ý học bao gồm
luận lý mệnh đề và luận lý vị từ (tham khảo chi tiết trong chương 2).
Giáo trình Toán Rời Rạc 1
Trang 12/12
12 trang
21420
Free
Bạn đang xem tài liệu "Giáo trình Toàn rời rạc 1 - Bài tập chương 1: Luận lý mệnh đề và luận lý vị từ", để 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_toan_roi_rac_1_bai_tap_chuong_1_luan_ly_menh_de_v.pdf
