Tài liệu Cấu trúc rời rạc cho khoa học máy tính

ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH

TRƯỜNG ĐẠI HỌC BÁCH KHOA

KHOA KHOA HỌC - KỸ THUẬT MÁY TÍNH

CẤU TRÚC RỜI RẠC CHO KHMT (CO1007)

Nhóm:18-TDTT —- Homework

CHAPTER 2

Proving Methods

GVHD: Nguyễn An Khương

SV thực hiện: Đinh Minh Tân – 1613074

Trương Minh Tiến – 1613544

Vũ Đào Anh Tuấn – 1613938

Nguyễn Thị Trà My – 51305086

Tp. Hồ Chí Minh, Tháng 11/2016

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

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

Chứng minh bất đẳng thức Cauchy bằng qui nạp

Với n=2^k,k=1,2,...

Gọi P(k) là mệnh đề A≥G, trong đó A,G là trung bình cộng và trung bình nhân của tập hợp

n=2^ksố thực dương.

Bước cơ sở:

k=1 và n=2¹=2.

√

Ta có ( a₁− a₂)²≥0 hay khai triển biểu thức đó ra ta được a₁− 2 a₁a₂+ a₂≥0, tức là

√

(a₁+ a₂)/2≥ a₁a₂.

Bước qui nạp

Giả sử P(k) là đúng, với n=2^k.

Ta sẽ chứng minh rằng P(k+1) là đúng .

Ta có: 2^k+1= 2n và (a₁+ a₂+ ... + a_2n)/(2n) = [(a₁+ a₂+ ... + a_n)/n + (a_n+1+ .... + a_2n)/n]/2

1/(2n)

1/n 1/2

đồng thời (a₁a₂.....a_2n

)

= [(a₁...a_n)^1/n(a_n+1...a_2n

)

]

.

Để

bình

đơn

cộng

giản

và

kí

trung

và

hiệu,

gọi

bình

A(x,y...)

nhân của

G(x,y...)≤G(x’,y’...).Vì

và

G(x,y...)

lần

x,y...Nếu

lượt

là

trung

các

số

thế

x≤x’,y≤y’..thì

A(x,y...)≤A(x’,y’...)

A(a₁, ..., a_2n

)

=

A(A(a₁, ...., a_n), A(a_n+1..., a_2n))≥A(G(a₁, ..., a_n), G(a_n+1, ..., a_2n))≥G(G(a₁, ..., a_n), G(a_n+1, .., a_2n)) =

G(a₁, ..., a_2n).

Điều này kết thúc chứng minh cho trường hợp n là lũy thừa của 2 .Nếu n không là lũy thừa của 2

,gọi m là lũy thừa bậc 2 với bậc cao hơn liền sát và a_n+1, ..., a_mtất cả đều bằng A(a₁, ..., a_n) = a.

1/m

Khi đó, ta có ((a₁a₂...a_n)(a)^m−n

)

≤A(a₁, a₂, ..., a_m) vì m là lũy thừa của 2.

Vì A(a₁, a₂, ...a_m) = a, suy ra (a₁a₂...a_n)^1/m(a)^1−n/m≤(a)^n/m. Nâng cả 2 vế lên lũy thừa bậc

m/n ta được G(a₁, ..., a_n)≤A(a₁...a_n). Bất đẳng thức được chứng minh.

Exercise 3.

a) TRUE

b) TRUE

c) FALSE

Exercise 4.

a) TRUE

b) TRUE

c) FALSE

d) TRUE

e) FALSE

f) TRUE

g) FALSE

Chương 2: Homework

Trang 1/8

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

a) There exists student x, x spends more than five hours every weekday in class.

b) For every student x, x spends more than five hours every weekday in class.

c) There exists student x, x spends less than or equal five hours every weekday in class.

d) For every student x, x spends less than or equal five hours every weekday in class.

Exercise 6.

a) For every people x, if x is a comedian, then x is funny.

b) For every people x, x is a comedian and x is funny.

c) There exists people x, if x is a comedian, then x is funny.

d) There exists people x, x is a comedian and x is funny.

Exercise 7.

a) ∃x (P(x) ∧ Q(x))

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

c) ∀x (P(x) ∨ Q(x))

d) ∀x¬ (P(x) ∧ Q(x))

Exercise 8.

a) There exists student x and student y such that x has sent an e-mail message to y.

b) There exists student x, for every student y such that x has sent an e-mail message to y.

c) For every student x, exists student y such that x has sent an e-mail message to y.

d) There exists student y, for all student such that x has sent an e-mail message to y.

e) For every student y, exists student x such that x has sent an e-mail message to y.

f) For every student x and student y, x has sent an e-mail message to y.

Exercise 9.

a) ∀x(L(x, Jerry))

b) ∀x∃y(L(x, y))

c) ∃y∀x(L(x, y))

d) ∃y(¬L(Lydia, y))

e) ∃y∀x¬(L(x, y))

f) ∃!y∀x(L(x, y))

Chương 2: Homework

Trang 2/8

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

a) ¬M(Chou, Koko)

b) ¬(M(Arlene, Sarah) ∧ T(Arlene, Sarah))

c) ¬(M(Deborah, Jose))

d) ∀x(M(x, Ken))

e) ∀x(¬(T(x, Nina)))

f) ∀x(T(x, Avi) ∧ M(x, Avi))

Exercise 11.

a) ∃!x(C(x) ∧ D(x) ∧ F(x))

b) ∀x(C(x) ∨ D(x) ∨ F(x))

c) ∃x(C(x) ∧ F(x) ∧ ¬D(x))

d) ∀x¬(C(x) ∧ D(x) ∧ F(x))

e) (∃!xC(x)) ∧ (∃!yD(y)) ∧ (∃!zF(z))

Exercise 12.

a) ∀xA(x)

b) M(file system, locked) → ∀xG(x, mailbox)

c) S(proxy server, diagnostic) → S(firewall, diagnostic)

d) T(100) ∧ ¬T(500) ∧ S(proxy server, diagnostic) → ∃xS(x, functioning normally)

Exercise 13.

a) Introduction of Disjunction

b) Elimination of Conjunction

c) Elimination of Implication

d) Modus Tollens

e) Elimination of Implication and Introduction of Implication

Exercise 14.

This argument can be true or false, because it is "exist", not "for every".

Chương 2: Homework

Trang 3/8

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

1.

2.

∀x(P(x) ∨ Q(x))

∀x(¬Q(x) ∨ S(x))

premise

3.

∀x(R(x) → ¬S(x)) premise

4.

∃x¬P(x)

x₀¬P(x₀)

P(x₀) ∨ Q(x₀)

P(x₀)

premise

5.

assumption

∀x e 1

assumption

copy 5

6.

7.

8.

¬P(x₀)

⊥

Q(x₀)

9.

¬ e 7, 8

⊥ e 9

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

Q(x₀)

assumption

∨ e 6, 7–10, 11

∀x e 2

Q(x₀)

¬Q(x₀) ∨ S(x₀)

¬Q(x₀)

Q(x₀)

assumption

copy 12

⊥

S(x₀)

¬ e 14, 15

⊥ e 16

S(x₀)

assumption

∨ e 13, 14–17, 18

∀x e 3

S(x₀)

R(x₀) → ¬S(x₀)

¬¬S(x₀)

¬R(x₀)

∃x¬R(x)

¬¬ i 19

MT 20, 21

∃x i 22

∃x e 4, 5–23

Exercise 16.

Let a = 2m + 1 and b = 2n + 1 is two odd integers.

Sum of a and b is a+b=2m+1+2n+1=2(m+n+1). This is even integer.

Exercise 17.

Let a = 2m + 1 and b = 2n + 1 is two odd numbers.

Product of a and b is ab = (2m + 1)(2n + 1) = 4mn + 2m + 2n + 1 = 2(2mn + m + n) + 1. This

is odd number.

Exercise 18.

Let the odd number is 2k + 1.

We have 2k + 1 = k²+ 2k + 1 − k²= (k + 1)²− k²is the difference of two squares.

Chương 2: Homework

Trang 4/8

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

We have n + m = 2a and n + p = 2b.

So n + m + n + p = 2a + 2b

⇒ m + p = 2(a + b − n). This is a even integer and I use direct proof.

Exercise 20.

a

c

Let and is two rational numbers, where a, b, c, d are integers.

b

d

a

b

c

d

ad+bc

bd

We have

+

=

is a rational number because ad + bc and bd are integers.

Exercise 21.

Let x is irrational number and ^a, where a, b are integer, is rational number.

Assum that sum of x and is r^bational number, we have

a

b

a

b

x +

=

m

n

^m_n, where m, n are integer.

−

a

b

mb−na

=

So x =

is rational number because mb − na and nb are integer.

This is contradictioⁿn^bbecause the premise is x is irrational number.

So we have sum of rational number and irrational number is irrational number.

Exercise 22.

1

x

1

x

Assum that is rational number, we have

=

^a_b, where a and b are integer.

b

So x = is rational number, this is contradiction.

a

Exercise 24.

a) Proof by contraposition

Assum that n is odd integer, then n = 2k + 1, where k is integer.

We need proof that n³+ 2015 is even number.

We have

n³+ 2015 = (2k + 1)³+ 2015

= 8k³+ 12k²+ 6k + 2016

= 2(4k³+ 6k²+ 3k + 1013)

This is even number.

b) Proof by contradiction

Assum that n is odd integer, then n = 2k + 1, where k is integer.

We have

n³+ 2015 = (2k + 1)³+ 2015

= 8k³+ 12k²+ 6k + 2016

= 2(4k³+ 6k²+ 3k + 1013)

This is even number, so contradict with premise that n³+ 2015 is odd number.

Chương 2: Homework

Trang 5/8

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

a) Proof by contraposition

Assum that n is odd integer, then n = 2k + 1, where k is integer.

We need proof that 3n + 2 is odd number.

We have 3n + 2 = 3(2k + 1) + 2 = 6k + 5 is odd number.

b) Proof by contradiction

Assum that n is odd integer, then n = 2k + 1, where k is integer.

We have 3n + 2 = 3(2k + 1) + 2 = 6k + 5 is odd number. That is contradict with 3n + 2 is

even number.

Exercise 26.

1. Proof 5n + 6 is odd if n is odd

Let n = 2k + 1, where k is integer.

5n + 6 = 5(2k + 1) + 6 = 10k + 11 is odd.

2. Proof n is odd if 5n + 6 is odd

Assum that n is even, we have n = 2k, then 5n + 6 = 10k + 6 is even, that is contradiction.

So n must be odd.

Exercise 27.

• Proof (i) ⇔ (ii)

3x + 2 is even, so 3x + 2 = 2k, where k is integer

⇔ x + 5 = 2k − 2x + 3 = 2(k − x) + 3 is odd.

• Proof (ii) ⇔ (iii)

x + 5 is odd, so x + 5 = 2k + 1, where k is integer.

⇔ x = 2k − 4 = 2(k − 2)

⇔ x²= 4(k − 2)²is even.

Exercise 28.

n is even, so n = 2k, where k is integer

• Proof (i) ⇔ (ii) n + 1 = 2k + 1 is odd

• Proof (i) ⇔ (iii) 3n + 1 = 3 ∗ 2k + 1 = 6k + 1 is odd

• Proof (i) ⇔ (iv) 3n = 3 ∗ 2k = 6k is even.

Exercise 29.

1∗(1+1)∗(2∗1+1)

With n = 1, 1²=

is true.

6

k(k+1)(2k+1)

Assum that it is true where n = k where k ≥ 1, 1²+ 2²+ ... + k²=

6

Chương 2: Homework

Trang 6/8

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

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

We have

k(k + 1)(2k + 1)

1²+ 2²+ ... + k²+ (k + 1)²=

+ (k + 1)²

6

ꢀ

ꢁ

2k²+ k

= (k + 1)

+ k + 1

6

ꢂ

ꢃ

2k²+ 7k + 6

= (k + 1)

6

(k + 1)(k + 1 + 1)(2(k + 1) + 1)

=

6

It is true with n = k + 1 so it is true with all n is natural number.

Exercise 30.

With n = 3, we have 2³= 8 > 2 ∗ 3 = 6, it is true.

Assum that it is true with n = k where k > 3, 2^k> 2k

With n = k + 1, we have

2ⁿ= 2^k+1

= 2^k+ 2^k

> 2k + 2k

> 2k + 2

= 2(k + 1)

It is true with n = k + 1 and n = 3, so it is true for every positive integer n > 2

The proof is complete.

Exercise 31.

.

With n = 1 we have 3²ⁿ⁻¹+ 1 = 3¹+ 1 = 4.4, it is true.

.

Suppose it is true with n = k > 1, that is 3^2k−1+ 1.4

We need proof that it is true with n = k + 1.

With n = k + 1 we have:

3^2(k+1)−1+ 1 = 3^2k+1+ 1

= 9.3^2k−1+ 1

= 8.3^2k−1+ 3^2k−1+ 1

.

Because 8.3^2k−1.4 and 3^2k−1+ 1.4 (assumption), so 3^2(k+1)−1+ 1.4.

The proof is complete.

Exercise 32.

.

We have 6ⁿ− 1 = (6 − 1)(6ⁿ⁻¹+ 6ⁿ⁻²+ ... + 6 + 1).5

Chương 2: Homework

Trang 7/8

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

With n = 4 we have n! = 4! = 24 > 2⁴= 16.

Suppose it is true with n = k > 4, that is k! > 2^k.

We need proof it is true with n = k + 1, we have:

(k + 1)! = (k + 1).k! > 2.2^k= 2^k+1

It is true. The proof is complete.

Exercise 34.

We have F₀= 0, F₁= 1, so we have F₂= 1 and F₃= 2.

As we see, F₃is even, so it is true with n = 1.

Suppose it is true with n = k > 1, that is F_3kis even.

We need proof it is true with n = k + 1.

We have:

F_3(k+1)= F_3k+3

= F_3k+2+ F_3k+1= F_3k+1+ F_3k+ F_3k+1

= 2F_3k+1+ F_3k

Because F_3kis even (assumption) and 2F_3k+1is even so F_3(k+1)is even. The proof is complete.

Exercise 35.

Of course, it is true with n = 1, n = 2 and n = 3.

Suppose it is true with n = k > 3, that is T_k< 2^k.

We need proof it is true with n = k + 1.

Indeed:

T_k+1= T_k+ T_k−1+ T_k−2< T_k+ T_k−1+ T_k−2+ T_k−3= T_k+ T_k= 2T_k< 2.2^k= 2^k+1

The proof is complete.

Chương 2: Homework

Trang 8/8

Tài liệu Cấu trúc rời rạc cho khoa học máy tính - Chapter 2: Proving Methods