Bài tập Cấu trúc rời rạc - Chương 2: Predicate Logic & Proof

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

Predicate Logic & Proof

1 Dẫn nhập

Trong bài tập dưới đây, chúng ta sẽ làm quen với logic vị từ và 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 về logic vị từ

và các phương pháp chứng minh trong chương 2, trước khi làm bài tập bên dưới.

2 Bài tập mẫu

Exercise 1.

.

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.

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

Exercise 2.

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

Exercise 3.

Let P(x) denote the statement "x ≤ 4". What are these truth values?

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

Trang 1/5

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) P(0)

b) P(4)

c) P(6)

Exercise 4.

Let Q(x) be the statement “x + 1 > 2x”. If the domain consists of all integers, what are these truth

values?

a) Q(0)

b) Q(−1)

c) Q(1)

d) ∃xQ(x)

e) ∀xQ(x)

f) ∃x¬Q(x)

g) ∀x¬Q(x)

Exercise 5.

Let P(x) be the statement “x spends more than five hours every weekday in class,” where the domain

for x consists of all students. Express each of these quantifications in English.

a) ∃xP(x)

b) ∀xP(x)

c) ∃x¬P(x)

d) ∀x¬P(x)

Exercise 6.

Translate these statements into English, where C(x) is “x is a comedian” and F(x) is “x is funny” and

the domain consists of all people.

a) ∀x(C(x) → F(x))

b) ∀x(C(x) ∧ F(x))

c) ∃x(C(x) → F(x))

d) ∃x(C(x) ∧ F(x))

Exercise 7.

Let P(x) be the statement “x can speak English” and let Q(x) be the statement “x knows the com-

puter language C++.” Express each of these sentences in terms of P(x), Q(x), quantifiers, and logical

connectives. The domain for quantifiers consists of all students at your school.

a) There is a student at your school who can speak English and who knows Java.

b) There is a student at your school who can speak English but who doesn’t know Java.

c) Every student at your school either can speak English or knows Java.

d) No student at your school can speak English or knows Java.

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

Trang 2/5

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

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

Exercise 8.

Let Q(x, y) be the statement “x has sent an e-mail message to y,” where the domain for both x and

y consists of all students in your class. Express each of these quantifications in English.

a) ∃x∃yQ(x, y)

b) ∃x∀yQ(x, y)

c) ∀x∃yQ(x, y)

d) ∃y∀xQ(x, y)

e) ∀y∃xQ(x, y)

f) ∀x∀yQ(x, y)

Exercise 9.

Let L(x, y) be the statement “x loves y,” where the domain for both x and y consists of all people in

the world. Use quantifiers to express each of these statements.

a) Everybody loves Jerry.

b) Everybody loves somebody.

c) There is somebody whom everybody loves.

d) There is somebody whom Lydia does not love.

e) There is somebody whom no one loves.

f) There is exactly one person whom everybody loves.

Exercise 10.

Let M(x, y) be "x has sent y an e-mail message" and T(x, y) be "x has telephoned y". where the

domain consists of all students in your class. Use quantifiers to express each of these statements

a) Chou has never sent an e-mail message to Koko.

b) Arlene has never sent an e-mail message to or telephoned Sarah.

c) Jose has never received an e-mail message from Deborah.

d) Every student in your class has sent an e-mail message to Ken.

e) No one in your class has telephoned Nina.

f) Everyone in your class has either telephoned Avi or sent him an e-mail message.

Exercise 11.

Let C(x) be the statement “x has a cat,” let D(x) be the statement “x has a dog,” and let F(x) be the

statement “x has a ferret.” Express each of these statements in terms of C(x), D(x), F(x), quantifiers,

and logical connectives. Let the domain consist of all students in your class.

a) A student in your class has a cat, a dog, and a ferret.

b) All students in your class have a cat, a dog, or a ferret.

c) Some student in your class has a cat and a ferret, but not a dog.

d) No student in your class has a cat, a dog, and a ferret.

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

Trang 3/5

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) For each of the three animals, cats, dogs, and ferrets, there is a student in your class who has this

animal as a pet.

Exercise 12.

Express each of these system specifications using predicates, quantifiers, and logical connectives.

A(x): User x has access to an electronic mailbox.

A(x, y): Group member x can access resource y.

S(x, y): System/Router x is in state y.

T(x): The throughput is at least x kbps.

M(x, y): Resource x is in mode y.

a) Every user has access to an electronic mailbox.

b) The system mailbox can be accessed by everyone in the group if the file system is locked.

c) The firewall is in a diagnostic state only if the proxy server is in a diagnostic state.

d) At least one router is functioning normally if the throughput is between 100 kbps and 500 kbps

and the proxy server is not in diagnostic mode.

Exercise 13.

What rule of inference is used in each of these arguments?

a) Alice is a mathematics major. Therefore, Alice is either a mathematics major or a computer science

major.

b) Jerry is a mathematics major and a computer science major. Therefore, Jerry is a mathematics

major.

c) If it is rainy, then the pool will be closed. It is rainy. Therefor, the pool is closed.

d) If it snows today, then university will close. The university is not closed today. Therefore, it did

not snow today.

e) If I go swimming, then I will stay in the sun too long. If I stay in the sun too long, then I will

sunburn. Therefore, if I go swimming, then I will sunburn.

Exercise 14.

What is wrong with this argument? Let H(x) be "x is happy." Given the premise ∃xH(x), we conclude

that H (Lola). Therefore, Lola is happy.

Exercise 15.

Use rules of inference to show that if ∀x(P(x) ∨ Q(x)), ∀x(¬Q(x) ∨ S(x)), ∀x(R(x) → ¬S(x)) and

∃x¬P(x) are true, then ∃x¬R(x) is true.

Exercise 16.

Use a direct proof to show that the sum of two odd integers is even.

Exercise 17.

Use a direct proof to show that the product of two odd numbers is odd.

Exercise 18.

Use a direct proof to show that every odd integer is the difference of two squares.

Exercise 19.

Proof that if n + m and n + p are even integers, where m, n, p are integers, then m + p is even. What

kind of proof did you use?

Exercise 20.

Prove that the sum of two rational numbers is rational.

Exercise 21.

Use a proof by contradiction to prove that the sum of an irrational number and a rational number is

irrational.

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

Trang 4/5

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

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

Exercise 22.

Prove that if x is irrational, then 1/x is irrational.

Exercise 23.

Use a proof by contraposition to show that if x + y ≥ 2, where x and y are real numbers, then x ≥ 1

or y ≥ 1.

Exercise 24.

Show that if n is an integer and n³+ 2015 is odd, then n is even using

a) a proof by contraposition.

b) a proof by contradiction.

Exercise 25.

Prove that if n is an integer and 3n + 2 is even, then n is even using

a) a proof by contraposition.

b) a proof by contradiction.

Exercise 26.

Prove that if n is a positive integer, then n is odd if and only if 5n + 6 is odd.

Exercise 27.

Show that these statements about the integer x are equivalent: (i) 3x + 2 is even, (ii) x + 5 is odd,

(iii) x²is even.

Exercise 28.

Prove that if n is an integer, these four statements are equivalent: (i) n is even, (ii) n + 1 is odd, (iii)

3n + 1 is odd, (iv) 3n is even.

Exercise 29.

n(n+1)(2n+1)

6

Prove by induction that 1²+ 2²+ · · · + n²=

Exercise 30.

Prove that 2ⁿ> 2n for every positive integer n > 2.

Exercise 31.

Prove that 3²ⁿ⁻¹+ 1 is divisible by 4 for all n ≥ 1

Exercise 32.

Prove that 6ⁿ− 1 is divisible by 5 for all n ≥ 1.

Exercise 33.

Prove that n! > 2ⁿfor all n ≥ 1.

Exercise 34.

Let the Fibonacci sequence be defined by F₀= 0, F₁= 1, F_n+2= F_n+ F_n+1for n ≥ 0. Prove that F_3n

is even for n ≥ 1.

Exercise 35.

Let the "Tribonacci sequence" be defined by T₁= T₂= T₃= 1 and T_n= T_n−1+ T_n−2+ T_n−3for

n ≥ 4. Prove that T_n< 2ⁿfor all n ≥ 1.

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

Trang 5/5