Giáo trình Cấu trúc rời rạc - Bài tập chương 2: Luận lý vị từ và Chứng minh

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 2

Luận lý vị từ và Chứng minh

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 về luận lý vị từ và

làm quen với các phương pháp chứng minh bao gồm chứng minh trực tiếp, phản chứng, phản đảo và

quy nạp Sinh viên cần ôn lại lý thuyết của chương 2, phần luận lý vị từ và chứng minh trước khi làm

bài tập bên dưới.

Các vị từ sau được dùng cho câu 1, câu 2, câu 5, câu 6

• 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

Câu 1.

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:

a) ‘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’.

b) ‘Bất cứ người nào là cha thì sẽ không thể là mẹ được’

Lời giải.

a) ∀x∃y∃z∃y₁∃y₂∃z₁∃z₂(F(y, x) ∧ M(z, x) ∧ F(y₁, y) ∧ M(y₂, y) ∧ F(z₁, z) ∧ M(z₂, z)).

b) ∃x∃y∀z(F(x, y) → ¬M(x, z)).

2

Câu 2.

Hãy diễn dịch những mệnh đề luận lý vị từ sau đây.

a) B(c, m) ∧ (O(c, m) ∨ O(m, c)).

b) B(c, m) ∧ F(a, m) → O(a, c) ∧ F(a, c).

Lời giải.

a) c hoặc là anh hoặc là em trai của m.

b) 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

Câu 3.

.

Chứng minh rằng ’với mọi giá trị nguyên n ≥ 1, 10ⁿ⁺¹+ 11^2n−1..111’.

Lời giải. Chúng ta có thể chứng minh bằng phép qui nạp như sau.

Giáo trình Cấu Trúc Rời Rạc

Trang 1/11

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) Với n = 1, biểu thức bên trái có trị bằng 10²+ 11¹= 111. Do vậy, mệnh đề trên đúng với n = 1.

.

b) Giả sử mệnh đề này đứng với n = k nghĩa là 10^k+1+ 11^2k−1.^.111 . Nói một cách khác, tồn tại một

số nguyên x sao cho 10^k+1+ 11^2k−1= 111.x.

Chúng ta cần chứng minh mệnh đề trên cũng đúng với n = k + 1, nghĩa là 10^k+2+ 11^2k+1..111.

.

Khai triển biểu thức bên trái, ta có:

10^k+2+ 11^2k+1= (10^k+2− 11².10^k+1) + (11².10^k+1+ 11^2k+1) = 10^k+1(10 − 11²) + 11²(10^k+1

+

.

11^2k−1) = 10^k+1(−111) + 121(10^k+1+ 11^2k−1).^.111.

.

Do đó, 10^k+2+ 11^2k+1..111; và vì thế mệnh đề này đúng với mọi số nguyên n ≥ 1 do qui nạp.

2

Câu 4.

Hãy chứng minh bằng qui nạp rằng tổng của 1 + 3 + 5 + 7 + ... + 2n − 1 là một số chính phương, với

mọi n ≥ 1.

Lời giải. Đầu tiên, ta đặt S_n= 1 + 3 + 5 + 7 + ... + 2n − 1.

Do vậy, ta có S_n+1= S_n+ (2n + 1).

a) Kết quả dễ dàng được chứng minh đúng với n = 1, vì bản thân số 1 là một số chính phương.

b) Giả sử S_nlà một số chính phương với n ≥ 1, nghĩa là tồn tại một số nguyên x sao cho S_n= x².

Chúng ta cần chứng minh rằng mệnh đề ’S_n+1là một số chính phương’ cũng đúng.

Ta có S_n+1= S_n+ (2n + 1) = x²+ 2n + 1.

Chọn x = n, ta sẽ có được S_n+1= (x + 1)².

Do vậy, kết quả đã được chứng minh đúng với mọi số nguyên n ≥ 1 bằn phương pháp qui nạp.

2

3 Bài tập bắt buộc

Câu 5.

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:

a) ‘Anh ta có chị gái và em trai’.

b) ‘Tất cả anh em trai của cô ta đều nhỏ tuổi hơn cô ấy’.

c) ‘Thuyên chỉ có duy nhất một người chồng’.

d) ‘Một trong những chị em gái của anh ta thì nhỏ tuổi hơn anh ấy’.

Câu 6.

Hãy diễn dịch những mệnh đề luận lý vị từ sau đây.

a) ∀x∀y(S(x, m) ∧ B(c, y) → x = y).

b) ∃x((S(x, m) ∨ H(c, x)) ∨ ∃x(H(x, m) ∧ O(x, m))).

c) ∀x∀y(S(x, m) ∧ S(y, m) → O(x, y) ∨ O(y, x))

Câu 7.

Chuyển các câu sau sang vị từ, lượng từ và toán tử logic:

Giáo trình Cấu Trúc Rời Rạc

Trang 2/11

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) 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.

e) Chỉ vài sinh viên máy tính lập trình tốt.

f) Không một sinh viên máy tính nào không cần cù.

g) Không phải tất cả các sinh viên máy tính đều thông minh.

h) Tất cả người Pompei hoặc trung thành với Caesar hoặc ghét ông ta.

i) Mỗi người đều trung thành với một người nào đó.

j) Người ta chỉ muốn ám sát những nhà cầm quyền mà người ta không trung thành.

k) Hai đường thẳng x và y cắt nhau trừ khi chúng song song hoặc không nằm trên cùng một mặt

phẳng

l) Nếu một cửa hàng bán lẻ gạo ở Việt Nam biết một cửa hàng gạo nào đó tăng giá thì cửa hàng đó

hoặc sẽ tăng giá hoặc cửa hàng đó thuộc siêu thị.

m) Nếu một người nào đó là phụ nữ và đã sinh con, thì người đó sẽ là mẹ của một người nào khác.

n) Mọi ngân hàng Việt Nam cho người nào đó vay tiền chỉ nếu người ấy có tài sản thế chấp hoặc được

một ai đó có tài sản thế chấp bảo lãnh.

Câu 8.

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)

Câu 9.

Cho vị từ N(x) “x học ở lóp hơn 5 giờ mỗi ngày trong tuần” 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) ∃x¬N(x)

Giáo trình Cấu Trúc Rời Rạc

Trang 3/11

Trường Đại Học Bách Khoa Tp.Hồ Chí Minh

Khoa Khoa Học và Kỹ Thuật Máy Tính

d) ∀x¬N(x)

Câu 10.

Cho P(x) là câu "x nói được tiếng Nga" và Q(x) là câu "x biết ngôn ngữ Java". 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 liên từ logic. Cho không gian đối với các lượng từ

là tập hợp tất cả sinh viên ở trường bạn

a) Có một sinh viên ở trường bạn nói được tiếng Nga và biết Java.

b) Có một sinh viên ở trường bạn nói được tiếng Nga nhưng không biết Java.

c) Mọi sinh viên ở trường bạn đều nói được tiếng Nga hoặc biết Java.

d) Không có một sinh viên nào ở trường bạn nói được tiếng Nga hoặc biết Java.

Câu 11.

Xét vị từ p(x) :⁰⁰x²− 3x + 2 = 0⁰⁰. Cho biết chân trị các mệnh đề sau:

a) p(0)

b) p(1)

c) p(2)

d) ∃x, p(x)

e) ∀x, p(x)

Câu 12.

Xét vị từ theo 2 biến nguyên tự nhiên: p(x, y): “x là ước của y”

Hãy xác định chân trị các mệnh đề sau:

a) p(2, 3)

b) p(2, 6)

c) ∀y, p(1, y)

d) ∀x, p(x, x)

e) ∀x∃y, p(x, y)

f) ∃y∀x, p(x, y)

g) ∀x∀y, (p(x, y) ∧ p(y, x)) → (x = y)

h) ∀x∀y∀z(p(x, y) ∧ p, (y, z)) → (p(x, z))

Câu 13.

Hãy cho biết công thức vị từ của đoạn mã giả (pseudo code) sau:

for (i = 0; i<numObjects; i++) {

Object x = Objects(i);

if isMushroom(i)

if isPoisonous(x) && isPurple(x)

return false;

}

return true;

Giáo trình Cấu Trúc Rời Rạc

Trang 4/11

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 14.

Hãy cho biết công thức vị từ của đoạn mã giả (pseudo code) sau:

for (i=0; i<numObjects; i++) {

Object x = Objects(i);

if isMushroom(i) && isPoisonous(x) && isPurple(x)

return true;

}

return false;

Câu 15.

Cho đoạn mã giả (pseudo code) sau:

//--- Look for first match

for (x=0; x<numKids; x++)

if isParent(Peter, kids[x])

match1Found = true;

//--- Now look for a second match

for (y=0; y<numKids; y++)

if isParent(Peter, kids[y])

match2Found = true;

return match1Found && match2Found;

Biết rằng: Mảng kids gồm 3 phần tử: { Alice, Bob, Charles } và Peter chỉ có 1 con là Alice.

Hãy cho biết công thức vị từ của câu "Peter có ít nhất 2 con".

Câu 16.

Hãy chứng minh rằng nếu n là số nguyên dương và 7n + 9 là số chẵn thì n là số lẻ bằng cách:

1. Chứng minh trực tiếp.

2. Chứng minh gián tiếp (phản đảo).

3. Chứng minh phản chứng.

Câu 17.

Hãy chứng minh các đẳng thức sau bằng cách sử dụng phương pháp chứng minh quy nạp:

1. 1.2 + 2.5 + 3.8 + . . . + n.(3n − 1) = n²(n + 1), n ≥ 1

1

1+2

1

1+2+3+...+n

2n

2. 1 +

+

+ . . . +

=

_n+1, n ≥ 1

1+2+3

P

n

i=1

i−1

3.

2

= 2ⁿ− 1

4. Chứng minh log₅(2) là số vô tỷ.

Câu 18.

Hãy sử dụng phương pháp chứng minh quy nạp để chứng minh:

1. Chứng minh rằng với mọi số nguyên n ≥ 1, 3²ⁿ⁻¹+ 1 chia hết cho 4.

2. Chứng minh rằng với mọi số nguyên n ≥ 1, 6ⁿ− 1 đều chia hết cho 5.

3. Chứng minh rằng với mọi số nguyên n ≥ 1, 5²ⁿ⁻¹+ 1 đều chia hết cho 6.

Giáo trình Cấu Trúc Rời Rạc

Trang 5/11

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. Chứng minh rằng với mọi số nguyên n ≥ 1, 8ⁿ− 1 đều chia hết cho 7.

5. Chứng minh rằng với mọi số nguyên n ≥ 1, 4ⁿ+ 15n − 1 đều chia hết cho 9.

Câu 19.

Hãy chứng minh các bất đẳng thức sau bằng cách sử dụng phương pháp chứng minh quy nạp:

1. Chứng minh rằng với mọi số nguyên n ≥ 1, 3ⁿ> n².

2. Chứng minh rằng với mọi số nguyên n ≥ 4, n! > 2ⁿ.

Câu 20.

1

2

Chứng minh rằng số lượng đường chéo trong một đa giác lồi với n đỉnh là n(n − 3), với n ≥ 4

Câu 21.

Trong một ngôi đền có ba cây cột gồm hai cột vàng và một cột bạc trong đó cây cột vàng thứ nhất

được lồng vào một chồng đĩa gồm 64 đĩa có kích thước khác nhau với đĩa lớn ở dưới, đĩa nhỏ ở trên

(xem hình). Mỗi người khi bước vào đền có nghĩa vụ lấy một đĩa (trên cùng) ở một cột và lồng vào

một cột khác sao cho luôn luôn đĩa lớn phải ở dưới và đĩa nhỏ phải ở trên. Bài toán đặt ra là tìm cách

chuyển hết chồng 64 đĩa từ cột vàng thứ nhất qua cột vàng thứ hai. Hãy cho biết

1. Có thể chuyển được hay không?

2. Nếu chuyển được thì hãy dùng 1 trong những phương pháp chứng minh đã học để chứng minh?

Hình 1: Một bộ mẫu của Tháp Hà Nội

4 Bài tập làm thêm

Câu 22.

Lớp Phân tích Thuật toán (PTTT) có 110 sinh viên ghi tên học trong đó có:

• 15 sinh viên Toán - Tin học năm Thứ 3

• 5 sinh viên Toán năm Thứ 3

• 25 sinh viên Toán - Tin học năm Thứ 4

• 5 sinh viên Toán năm thứ 4

• 50 sinh viên Công nghệ Thông tin năm Thứ 4

• 5 sinh viên Toán - Tin học Cao h5c

Giáo trình Cấu Trúc Rời Rạc

Trang 6/11

Trường Đại Học Bách Khoa Tp.Hồ Chí Minh

Khoa Khoa Học và Kỹ Thuật Máy Tính

• 5 sinh viên Công nghệ Thông Tin Cao học

Xét các vị từ sau:

• l(x): Sinh viên x ghi tên học môn PTTT

• b(x): x là sinh viên năm Thứ 3,

• c(x): x là sinh viên năm Thứ 4,

• d(x): x là sinh viên Cao học,

• r(x): x là sinh viên Công nghệ Thông Tin,

• s(x): x là sinh viên Toán - Tin học,

• t(x): x là sinh viên Toán.

Hãy viết mệnh đề dưới đây theo dạng lượng từ hóa

a) Có sinh viên năm Thứ 3 trong lớp PTTT

b) Có sinh viên trong lớp không phải là sinh viên Công nghệ Thông tin

c) Mọi sinh viên trong lớp là sinh viên Toán - Tin học hay Công nghệ Thông tin

d) Không có sinh viên Cao học Toán trong lớp PTTT

e) Mọi sinh viên năm Thứ 3 trong lớp thuộc ngành Toán hay Toán - Tin học

f) Có sinh viên ở Trường không thuộc ngành Toán - Tin học và cũng không thuộc ngành Công nghệ

Thông tin

Câu 23.

Chuyển các câu sau sang vị từ, lượng từ và toán tử logic:

a) Nếu a, b và p là số nguyên dương, p là số nguyên tố và p chia hết tích ab (ký hiệu p|ab) thì hoặc

p chia hết cho a hoặc p chia hết cho b (với không gian, universe of discourse, là tập số nguyên

dương).

b) Để cho hai đường thẳng x và y không có điểm chung tương đương với x song song với y thì cần có

x và y cùng nằm trên một mặt phẳng (với không gian là tập các đường thẳng).

c) Có những người không giúp đỡ ai khác ngoại trừ những người thân trong gia đình hay là những

người có giúp đỡ mình (với không gian là tập con người).

d) Nếu một người kết hôn với một người nào đó thì có một người thứ ba bị từ chối kết hôn.

Câu 24.

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.

Giáo trình Cấu Trúc Rời Rạc

Trang 7/11

Trường Đại Học Bách Khoa Tp.Hồ Chí Minh

Khoa Khoa Học và Kỹ Thuật Máy Tính

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.

Câu 25.

Cho L(x,y) là câu "x yêu y", với không gian của cả x và y là tập hợp mọi người trên thế giới. Hãy

dùng các lượng từ để diễn đạt các câu sau

a) Mọi người đều yêu Jerry.

b) Mọi người đều yêu một ai đó.

c) Có một người mà tất cả mọi người đều yêu.

d) Không có ai yêu tất cả mọi người.

e) Có một người mà Lydia không yêu.

f) Có một người mà không ai yêu.

g) Có đúng một người mà tất cả mọi người đều yêu.

h) Có đúng hai người mà Lynn yêu.

i) Mọi người đều yêu chính mình.

j) Có một người nào đó không yêu ai ngoài chính mình.

Câu 26.

Cho các vị từ:

.

-P(x): "x là một vấn đề toán học".

-Q(x): "x khó" (theo một tiêu chuẩn được định nghĩa tốt nào đó).

-R(x): "x dễ" (theo một tiêu chuẩn được định nghĩa tốt nào đó - giống như trên).

-S(x): "x không thể giải được".

Diễn giải những công thức vị từ sau dưới dạng ngôn ngữ tự nhiên

a) ∀x(P(x) → (Q(x) ⇐⇒ ¬R(x)))

b) ∃x(S(x) ∧ ¬P(x))

Câu 27.

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)

Câu 28.

Cho biết chân trị của các mệnh đề sau trong đó x, y là các biến thực:

a) ∃x∃y, xy = 1.

b) ∃x∀y, xy = 1.

Giáo trình Cấu Trúc Rời Rạc

Trang 8/11

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) ∀x∃y, xy = 1.

d) ∀x∀y, sin²x + co²x = sin²y + cos²y.

e) ∃x∃y, (2x + y = 5) ∧ (x − 3y = −8).

Câu 29.

Cho những vị từ sau:

P(x,y) : x > y

Q(x,y) : x ≤ y

R(x) : x - 7 = 2

S(x) : x > 9

Cho không gian là tập số thực. Hãy cho biết chân trị của các công thức vị từ sau:

a) ∀x∀y(P(x, y) ∨ Q(x, y))

b) ∀x∀y((R(x) ∧ S(y)) → Q(x, y))

Câu 30.

Trong những công thức chỉnh dạng (well-formed formula), biến nào bị ràng buộc (bound) và biến nào

là tự do (free)? Giải thích lý do rõ ràng

a) ∀x(∃y(P(x, y) ∧ Q(x)) → ∃z(¬P(y, z)))

b) ∃xP(x) ∧ (∀y(Q(y) ∨ P(x)) → Q(y))

Câu 31.

Chứng tỏ rằng:

a) ∀xP(x) ∧ ∃xQ(x) và ∀x∃y(P(x) ∧ Q(y)) là tương đương logic.

b) ∀xP(x) ∨ ∃xQ(x) và ∀x∃y(P(x) ∨ Q(y)) là tương đương logic.

Câu 32.

Hãy chứng minh rằng nếu n là số nguyên dương và n³+ 2015 là số lẻ thì n là số chẵn bằng cách:

1. Chứng minh gián tiếp (phản đảo).

2. Chứng minh phản chứng.

Câu 33.

Hãy chứng minh các đẳng thức sau bằng cách sử dụng phương pháp chứng minh quy nạp:

1. 1.1! + 2.2! + 3.3! + . . . + n.n! = (n + 1)! − 1, n ≥ 1

1

2

2. x + 4x + 7x + . . . + (3n − 2)x = n(3n − 1)x, n ≥ 1 và x là hằng số.

3. Đặt {a_n} là dãy các số tự nhiên sao cho a₁= 5, a₂= 13 và a_n+2= 5a_n+1− 6a_ncho tất cả các

số tự nhiên n. Chứng minh rằng a_n= 2ⁿ+ 3ⁿ

Câu 34.

Hãy sử dụng phương pháp chứng minh quy nạp để chứng minh:

Giáo trình Cấu Trúc Rời Rạc

Trang 9/11

Trường Đại Học Bách Khoa Tp.Hồ Chí Minh

Khoa Khoa Học và Kỹ Thuật Máy Tính

1. Chứng minh rằng với mọi số nguyên dương n ≥ 1, 2.7ⁿ+ 3.5ⁿ− 5 chia hết cho 24.

2. Chứng minh rằng với mọi số nguyên dương n ≥ 1, 7ⁿ⁺²+ 8²ⁿ⁺¹chia hết cho 57.

3. Chứng minh rằng với mọi số nguyên dương n ≥ 1, 3²ⁿ⁺²− 8n − 9 chia hết cho 64.

4. Chứng minh rằng với mọi số nguyên dương n ≥ 0, 11ⁿ⁺²+ 12²ⁿ⁺¹chia hết cho 133.

5. Giả sử x₁, x₂là hai nghiệm của phương trình x²− 27x + 14 = 0, n là một số tự nhiên bất kỳ.

Chứng minh rằng S_n= xⁿ₁+ xⁿ₂không chia hết cho 715.

6. Nếu x, y là 2 số tự nhiên bất kỳ khác nhau. Chứng minh rằng xⁿ− yⁿlà bội số của x − y, n là

một số tự nhiên bất kỳ.

Câu 35.

Chứng minh rằng n đường thẳng khác nhau trên một mặt phẳng đi qua một điểm chia mặt phẳng ra

2n phần.

Câu 36.

Chứng minh rằng n đường thẳng phân biệt sẽ chia mặt phẳng ra thành tối đa (n²+ n + 2)/2 miền.

5 Trắc nghiệm

Câu 37.

Cho các vị từ sau:

.

- P(x): Chương trình x đáp ứng chuẩn ABET.

- Q(x,y): Chương trình x có mục tiêu đào tạo giống chương trình y.

- R(x): Kết quả đầu ra của chương trình x là có thể kiểm chứng được.

Câu sau được biểu diễn bằng mệnh đề vị từ nào: "Mọi chương trình đào tạo nếu có mục tiêu giống

một chương trình khác đã đáp ứng chuẩn ABET và kết quả đầu ra có thể kiểm chứng được thì cũng

tuân theo chuẩn ABET"

a) ∀x(P(x) ∧ ¬Q(x)) → ∃x(R(x))

b) ∀x(∃y(Q(x, y) ∧ P(y) ∧ R(x)) → P(x))

c) ∀x(∃y(Q(x, y) ∧ P(y) ∧ R(x)) → P(x) ∨ R(x))

d) ∀x(∀y(Q(x, y) ∧ P(y) ∨ R(x)) → P(x))

Câu 38.

Trong câu hỏi này giả sử các vị từ:

.

- P(x,y): x là phụ huynh của y.

- M(x): x là nam giới .

Nếu cho: F(v, w) = M(v) ∧ ∃x∃y(P(x, y) ∧ P(x, v) ∧ (y = v) ∧ p(y, w)), thì F(v,w) có nghĩa là

a) v là anh của w

b) v là cháu trai của w

c) v là chú của w

d) v là ông của w

Giáo trình Cấu Trúc Rời Rạc

Trang 10/11

Trường Đại Học Bách Khoa Tp.Hồ Chí Minh

Khoa Khoa Học và Kỹ Thuật Máy Tính

6 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ý, diễn dịch chúng trong ngôn ngữ thông thường và đã làm quen với các phương pháp

chứng minh. 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

về luận lý vị từ và việc lý giải đúng sai trong các bài toán thực tế (tham khảo chi tiết trong chương

2).

Giáo trình Cấu Trúc Rời Rạc

Trang 11/11