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 1A

Propositional Logic

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 10/2016

1 Exercise 1

1/ fallacy là Ngụy biện

ví dụ: A:Tôi nghĩ trên đời này có ma?

B:Bằng chứng đâu??

A:Thì cậu có đưa ra được bằng chứng là không có ma không? Tức là trên đời này có ma!?

contradiction là sự mâu thuẫn ví dụ: chủ trương duy tâm mâu thuẫn với duy vật

paradox là nghịch lý ví dụ: Càng thất bại nhiềuu, càng có khả năng thành công

counterexample là phản ví dụ

ví dụ: nếu g(a)=0 thì hàm số

f(x)

F(x) =

g(x)

có tiệm cận đứng là x=a-> phản ví dụ: đường thẳng x=a không phải là tiệm cận đứng của hàm

số

x²− a²

y =

x − a

example là ví dụ

2/ premise là tiền đề

assumption là giả thuyết

axiom là tiên đề

hypothesis là giả thiết

conjecture là sự giả định

3/ tautology là hằng đúng

valid là có giá trị hiệu lực

satisfiable là thỏa mãn

4/ soundness là tính đúng đắn

completeness là điều kiện đủ

5/ sequent là dãy

consequence là hệ quả

implication là phép kéo theo

entailment là phép suy diễn

deduction là phép suy luận

inference là suy luận

2 Exercise 2

−→, là một phép toán logic, p−→r nghĩa là r là kết quả logic của p với p, r là các biểu thức logic

⇒, ta kí hiệu p→ khi p−→r luôn đúng

`, kí hiệu p`r nghĩa là r là kết quả logic của p với p, r là câu logic

|=, kí hiệu p|=r nghĩa là hệ quả logic của p, tức là với mọi bộ giá trị của các biến logic trong p,

r mà p đúng thì ta có r đúng

←→, kí hiệu p←→ r khi

(

p −→ r

(1)

r −→ p

1

⇐⇒, kí hiệu p⇐⇒r khi

a`, kí hiệu pa` khi

≡, kí hiệu p≡r khi

(

p =⇒ r

r =⇒ p

(2)

(3)

(4)

(

p ` r

r ` p

(

p |= r

r |= p

3 Exercise 3

3.1

1.

a. We chose p to stand for” The sun shines today", and q denotes " The sun shines tomor-

row."The corresponding formula is then

p →¬q

b. We chose p to stand for " Robert was jealous of Yvonne " and q to stand for " He was not in

a good mood". The corresponding formula is then

p ∨q

c. We chose

p:" The barometer falls"

q:" It will rain"

r:" It will snow"

The corresponding formula is then

p → q ∨ r

d. We chose

p:" A request occurs" q:" The request will eventually he acknowledged." r:" The requesting

process will eventually make progess." The formula representing the declarative sentence is then

p → q ∨ ¬ r

2

h. We chose p:" Today it will rain" q:" Today it will shine" The formula representing the

declarative sentence is then

p∨q ∧ ¬ (p∧q)

i. We chose

p:"Dick met Jane yesterday"

q:"They had a cup of cofee together"

r:"They took a walk in the park"

The formula representing the declarative sentence is then

p→(q∨r)

2.

d.p∨((¬q)→(p∧r))

g.The expression p∨q∧r is proplematic since ∧ and ∨ have the same binding priorities, so we

have to insist on additional brackes in order to resole this conflict.

3.2

1.

d.We prove the validity of p→(p→q),p`q by

1.

2.

3.

4.

p → (p → q) premise

p

premise

(→e 1,2)

(→e 1,3)

p → q

q

g. We prove the validity of p ` q → (p ∧ q)

1.

2.

3.

4.

p

premise

assum

q

p ∧ q

(∧i 1,2)

p → (p∧ q) (→i 1,3)

m. We prove the validity of p ∨q ` r → (p ∨ q) ∧ r

1.

2.

3.

4.

p ∨ q

premise

(∧i1, 2)

r

(p ∨ q) ∧ r

r → (p ∨ q) ∧ r (→ i2, 3)

p. We prove the validity of ` q → (p→(p→(q→p)))

3

1.

2.

3.

4.

5.

6.

q

assum

p

assum

q → p

(→ i 1, 2)

(→ i 2, 3)

(→ i 2 − 4)

p → (q → p)

p → (p → (q → p))

q → (p → (p → (q → p))) (→ i 1 − 5)

u. We prove the validity of p→q ` ¬q → ¬p

1.

2.

3.

4.

5.

6.

7.

p → q

¬q

p

premise

assum

q

(→ e 1, 3)

(¬e 4, 2)

(¬i 3, 5)

⊥

¬p

¬q → ¬p (→ i 2, 6)

w. We prove the validity of r,p →(r→q) ` p→(q∧r)

1.

2.

3.

4.

5.

6.

7.

r

premise

p → (r → q) premise

p

assum

r → q

q

(→ e 2, 3)

(→ e 1, 4)

(∧i 1, 5)

q ∧ r

p → (q ∧ r)

(→ i 3 − 6)

3.

a.We prove the validity of ¬ p →p ` p by

1.

2.

3.

4.

5.

¬p → p premise

¬p

p

assum

(→ e 1, 2)

(¬e 2, 3)

⊥

p

(¬i 2 − 4)

b.We prove the validity of ¬p ` p→ q

1.

2.

3.

4.

5.

¬p

p

premise

assum

⊥

q

(¬e 1, 2)

(⊥ e 3)

p → q (→ i 2 − 4)

4

c.We prove the validity of p∨q,¬q ` p

1.

2.

3.

4.

5.

6.

7.

p ∨ q premise

¬q

p

premise

assum

q

assum

⊥

q

(¬e 2, 4)

(⊥ e 5)

(∨e 1, 3, 4 − 6)

q

f.We prove the validity of p→q ` ¬p∨q by

1.

2.

3.

4.

5.

6.

7.

8.

p → q

premise

q ∨ ¬q (LEM)

assum

q

¬p ∨ q (∨i 3)

¬q

¬p

assum

(MT 1,5)

¬p ∨ q (∨i6)

¬p ∨ q (∨e4, 5 − 6, 7 − 9)

g.We prove the validity of ` ¬p ∨ q → (p→q) by

1.

2.

¬p ∨ q

premise

¬p

assum

3.

p

assum

4.

⊥

(¬e 2, 3)

(⊥ e 4)

(→ i 3 − 5)

assum

5.

q

6.

p → q

q

7.

8.

p

assum

9.

p → q

(→ i 7, 8)

(∨e1, 2 − 6, 7 − 9)

10.

11.

¬p ∨ q → (p → q) (→ i 1, 10)

l.We prove the validity of ¬ (p∧q) ` ¬p ∨ ¬q

5

1.

2.

¬(p ∧ q)

premise

¬(¬p ∨ ¬q) assum

3.

p

assum

4.

q

assum

5.

p ∧ q

⊥

(∧i)

6.

(¬e 1, 5)

(¬i 4 − 6)

(∨i7)

7.

¬q

8.

¬q ∨ ¬p

⊥

9.

(copy 8 )

(¬e 2, 9)

(¬e 2 − 10)

10.

11.

¬q ∨ ¬p

o.We prove the validity of ¬ (¬p ∨ ¬q) ` p∧q by

1.

2.

¬ (¬p ∨ ¬q) premise

¬ (p ∧ q)

assum

3.

p

assum

4.

q

assum

5.

p ∧ q

⊥

(∧i 3, 4)

(¬e 2, 5)

(¬i 4 − 6)

(∨i 7)

(¬e 1, 8)

(¬i 3 − 9)

(∨i 10)

(¬e 1, 11)

(¬e 2 − 12)

6.

7.

¬q

8.

¬q ∨ ¬p

⊥

9.

10.

11.

12.

13.

¬p

¬p ∨ ¬q

⊥

p ∧ q

6

Tài liệu Cấu trúc rời rạc cho khoa học máy tính - Chapter 1A: Propositional Logic