[PDF]Bài giảng Cấu trúc rời rạc cho Khoa học máy tính: Chapter 1 – ĐH Bách Khoa.pdf
ĐẠ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:
SV thực hiện:
Nguyễn An Khương
Đ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ố
x2 − a2
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
(
p =⇒ r
r =⇒ p
(2)
a`, kí hiệu pa` khi
(
p`r
r`p
(3)
≡, kí hiệu p≡r khi
(
p |= r
r |= p
3
(4)
Exercise 3
3.1
1.
a. We chose p to stand for” The sun shines today”, and q denotes ” The sun shines tomorrow.”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.
p → (p → q)
premise
2.
p
premise
3.
p→q
(→e 1,2)
4.
q
(→e 1,3)
g. We prove the validity of p ` q → (p ∧ q)
1.
p
premise
2.
q
assum
3.
p∧q
(∧i 1,2)
4.
p → (p∧ q)
(→i 1,3)
m. We prove the validity of p ∨q ` r → (p ∨ q) ∧ r
1.
p∨q
premise
2.
r
premise
3.
(p ∨ q) ∧ r
(∧i1, 2)
4.
r → (p ∨ q) ∧ r
(→ i2, 3)
p. We prove the validity of ` q → (p→(p→(q→p)))
3
1.
q
assum
2.
p
assum
3.
q→p
(→ i 1, 2)
4.
p → (q → p)
(→ i 2, 3)
5.
p → (p → (q → p))
(→ i 2 − 4)
6.
q → (p → (p → (q → p)))
(→ i 1 − 5)
u. We prove the validity of p→q ` ¬q → ¬p
1.
p→q
premise
2.
¬q
assum
3.
p
assum
4.
q
(→ e 1, 3)
5.
⊥
(¬e 4, 2)
6.
¬p
(¬i 3, 5)
7.
¬q → ¬p
(→ i 2, 6)
w. We prove the validity of r,p →(r→q) ` p→(q∧r)
1.
r
premise
2.
p → (r → q)
premise
3.
p
assum
4.
r→q
(→ e 2, 3)
5.
q
(→ e 1, 4)
6.
q∧r
(∧i 1, 5)
7.
p → (q ∧ r)
(→ i 3 − 6)
3.
a.We prove the validity of ¬ p →p ` p by
1.
¬p → p
premise
2.
¬p
assum
3.
p
(→ e 1, 2)
4.
⊥
(¬e 2, 3)
5.
p
(¬i 2 − 4)
b.We prove the validity of ¬p ` p→ q
1.
¬p
premise
2.
p
assum
3.
⊥
(¬e 1, 2)
4.
q
(⊥ e 3)
5.
p→q
(→ i 2 − 4)
4
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINHTRƯỜNG ĐẠI HỌC BÁCH KHOAKHOA KHOA HỌC – KỸ THUẬT MÁY TÍNHCẤU TRÚC RỜI RẠC CHO KHMT (CO1007)Nhóm: 18..TDTT— HomeworkCHAPTER 1APropositional LogicGVHD:SV thực hiện:Nguyễn An KhươngĐinh Minh Tân – 1613074Trương Minh Tiến – 1613544Vũ Đào Anh Tuấn – 1613938Nguyễn Thị Trà My – 51305086Tp. Hồ Chí Minh, Tháng 10/2016Exercise 11/ fallacy là Ngụy biệnví 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ậtparadox là nghịch lý ví dụ: Càng thất bại nhiềuu, càng có khả năng thành côngcounterexample 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àmsốx2 − a2y=x−aexample là ví dụ2/ premise là tiền đềassumption là giả thuyếtaxiom là tiên đềhypothesis là giả thiếtconjecture là sự giả định3/ tautology là hằng đúngvalid là có giá trị hiệu lựcsatisfiable là thỏa mãn4/ soundness là tính đúng đắncompleteness là điều kiện đủ5/ sequent là dãyconsequence là hệ quảimplication là phép kéo theoentailment là phép suy diễndeduction là phép suy luậninference là suy luậnExercise 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 khip −→ r(1)r −→ p⇐⇒, kí hiệu p⇐⇒r khip =⇒ rr =⇒ p(2)a`, kí hiệu pa` khip`rr`p(3)≡, kí hiệu p≡r khip |= rr |= p(4)Exercise 33.11.a. We chose p to stand for” The sun shines today”, and q denotes ” The sun shines tomorrow.”The corresponding formula is thenp →¬qb. We chose p to stand for ” Robert was jealous of Yvonne ” and q to stand for ” He was not ina good mood”. The corresponding formula is thenp ∨qc. We chosep:” The barometer falls”q:” It will rain”r:” It will snow”The corresponding formula is thenp→q∨rd. We chosep:” A request occurs” q:” The request will eventually he acknowledged.” r:” The requestingprocess will eventually make progess.” The formula representing the declarative sentence is thenp→q∨¬rh. We chose p:” Today it will rain” q:” Today it will shine” The formula representing thedeclarative sentence is thenp∨q ∧ ¬ (p∧q)i. We chosep:”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 thenp→(q∨r)2.d.p∨((¬q)→(p∧r))g.The expression p∨q∧r is proplematic since ∧ and ∨ have the same binding priorities, so wehave to insist on additional brackes in order to resole this conflict.3.21.d.We prove the validity of p→(p→q),p`q by1.p → (p → q)premise2.premise3.p→q(→e 1,2)4.(→e 1,3)g. We prove the validity of p ` q → (p ∧ q)1.premise2.assum3.p∧q(∧i 1,2)4.p → (p∧ q)(→i 1,3)m. We prove the validity of p ∨q ` r → (p ∨ q) ∧ r1.p∨qpremise2.premise3.(p ∨ q) ∧ r(∧i1, 2)4.r → (p ∨ q) ∧ r(→ i2, 3)p. We prove the validity of ` q → (p→(p→(q→p)))1.assum2.assum3.q→p(→ i 1, 2)4.p → (q → p)(→ i 2, 3)5.p → (p → (q → p))(→ i 2 − 4)6.q → (p → (p → (q → p)))(→ i 1 − 5)u. We prove the validity of p→q ` ¬q → ¬p1.p→qpremise2.¬qassum3.assum4.(→ e 1, 3)5.(¬e 4, 2)6.¬p(¬i 3, 5)7.¬q → ¬p(→ i 2, 6)w. We prove the validity of r,p →(r→q) ` p→(q∧r)1.premise2.p → (r → q)premise3.assum4.r→q(→ e 2, 3)5.(→ e 1, 4)6.q∧r(∧i 1, 5)7.p → (q ∧ r)(→ i 3 − 6)3.a.We prove the validity of ¬ p →p ` p by1.¬p → ppremise2.¬passum3.(→ e 1, 2)4.(¬e 2, 3)5.(¬i 2 − 4)b.We prove the validity of ¬p ` p→ q1.¬ppremise2.assum3.(¬e 1, 2)4.(⊥ e 3)5.p→q(→ i 2 − 4)
